载入中。。。 'S bLog
 
载入中。。。
 
载入中。。。
载入中。。。
载入中。。。
载入中。。。
载入中。。。
 
填写您的邮件地址,订阅我们的精彩内容:


 
关于格网索引grid base index的一些资料
[ 2011/6/11 21:05:00 | By: 梦翔儿 ]
 

关于格网索引grid base index的一些资料

这里有一些比较明白的中文解释:

http://www.dreamflier.net/blog/user1/3/2178.html

Grid (spatial index)-wiki

http://en.wikipedia.org/wiki/Grid_(spatial_index)#Grid-based_spatial_indexing

Grid reference

http://en.wikipedia.org/wiki/Grid_reference

Grid Traversal

Probably the best and most famous grid traversal algorithm uses a simple loop that for each iteration takes one more step in the grid. It works in both 2D and 3D.

Java code:

   public boolean isFreePath(float startX, float startZ, float endX, float endZ)
   {
      // calculate the direction of the ray (linear algebra)
      dirX = (endX - startX);
      dirY = (endZ - startZ);
      float length = (float) Math.sqrt(dirX * dirX + dirY * dirY);
      dirX /= length; // normalize the direction vector
      dirY /= length;
 
      tDeltaX = MAP_RESOLUTION / Math.abs(dirX); // how far we must move in the ray direction before we encounter a new voxel in x-direction
      tDeltaY = MAP_RESOLUTION / Math.abs(dirY); // same but y-direction
 
      // start voxel coordinates
      x = (int) (worldCoordToMapCoord(startX));  // use your transformer function here
      y = (int) (worldCoordToMapCoord(startZ));
 
      // end voxel coordinates
      endX1 = (int) (worldCoordToMapCoord(endX));
      endY1 = (int) (worldCoordToMapCoord(endZ));
 
      // decide which direction to start walking in
      stepX = (int) Math.signum(dirX);
      stepY = (int) Math.signum(dirY);
 
      float tMaxX, tMaxY;
      // calculate distance to first intersection in the voxel we start from
      if(dirX < 0)
      {
         tMaxX = (mapToWorld(x)-startX) / dirX;
      }else
      {
         tMaxX = (mapToWorld(x+1)-startX) / dirX;
      }
 
      if(dirY < 0)
      {
         tMaxY = (mapToWorld(y)-startY) / dirY;
      }else
      {
         tMaxY = (mapToWorld(y+1)-startY) / dirY;
      }
 
      // check if first is occupied
      if (isMapPositionOccupied(x, y)) // use your function here
         return false;
 
      boolean reachedX = false, reachedY = false;
 
      while (true)
      {
         if (tMaxX < tMaxY)
         {
            tMaxX += tDeltaX;
            x += stepX;
         } else
         {
            tMaxY += tDeltaY;
            y += stepY;
         }
 
         if (stepX > 0.0f)
         {
            if (x >= endX1)
            {
               reachedX = true;
            }
         } else if (x <= endX1)
         {
            reachedX = true;
         }
 
         if (stepY > 0.0f)
         {
            if (y >= endY1)
            {
               reachedY = true;
            }
         } else if (y <= endY1)
         {
            reachedY = true;
         }
 
         if (isMapPositionOccupied(x, y))
         {
            return false;
         }
 
         if (reachedX && reachedY)
         {
            break;
         }
      }
 
      return true;
   }

Here’s an applet showing it in action.
The white tiles are free, the gray tiles are blocking. The ray starts at the green dot and ends at the red dot. The gray spheres are the visited grid sections. Use leftclick to position the green dot and the right button to position the red dot.
 


Hi There


Link to paper:
http://www.flipcode.com/archives/A%20faster%20voxel%20traversal%20algorithm%20for%20ray%20tracing.pdf

Some discussion on GameDev:
http://www.gamedev.net/community/forums/topic.asp?topic_id=385303

Implementations:
http://www.clockworkcoders.com/oglsl/rt/gpurt3.htm
http://www.devmaster.net/articles/raytracing_series/part4.php

Full source of the applet:

  1. Comment by Durnus — September 1, 2009 @ 7:43 pm

    Awesome. I saw the paper but couldn’t quite make it work. This helps.

    But I notice that the code you gave doesn’t work when I try to implement it (slight inaccuracies in the line: moves down/up too early/late). Maybe you could release the full applet source code, or at least have more code to work from. I might be able to make it work on my own, but I’ll be looking at this page for updates.

  2. Comment by Durnus — September 16, 2009 @ 8:25 pm

    I just fixed it by myself. First I tried to decompile your code then compile it again to see how it worked, but somehow that didn’t work. Finally I just figured out what I did wrong and did it right.

    If you want to see my full applet code, go ahead here to pick up the source: . It may not be the prettiest, but I think it’s better to see how to implement this function and make it work rather than see the program around it.

    Hope someone besides me finds this useful.

  3. Comment by Durnus — September 16, 2009 @ 8:41 pm

    It appears my url got swallowed by the blog software, here it is again:

    http://snipt.org/moY

  4. Comment by admin — September 27, 2009 @ 10:51 pm

    Sorry for responding so late. But I’ve uploaded the code now. I hope someone finds good use in it!

http://www.gamerendering.com/2009/07/20/grid-traversal/

这里有对上面代码的休正:

http://snipt.org/moY

 
 
  • 标签:格网索引 grid base index 
  • 发表评论:
    载入中。。。

     
     
     

    梦翔儿网站 梦飞翔的地方 http://www.dreamflier.net
    中华人民共和国信息产业部TCP/IP系统 备案序号:辽ICP备09000550号

    Powered by Oblog.