Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


#ActualBacterius

Posted 22 August 2013 - 03:47 PM

You need to traverse the quad-tree as follows:

 

1. start at root node.

2. intersect your ray with the root node's bounding box.

3. does it intersect it? if not, return (to the calling function) with no intersection (if you can't express "no intersection" in your algorithm, just use infinite distance)

4. if this is a leaf node:

  - intersect the ray with all the triangles in the node, and return (to the calling function) the closest intersection

else:

 - find out which children nodes the ray intersects, and sort them according to closest intersection (this is the trickiest part in my experience)

 - recurse to step 2 for each child node, in order of intersection, until the closest triangle found is closer than the distance to a child's bounding box (in which case any triangle inside that child will be further away than the one you've already found, so there's no need to traverse it)

 - return (to the calling function) the closest intersection you found

 

This is a recursive process, and will find the closest triangle intersecting the ray with complexity O(log(n)) where n is the number of triangles in your quadtree. You probably want to implement this with a stack instead of using recursion (at least once everything is working) for performance's sake. The really annoying part is getting the bounding box collisions right, I highly recommend you overlay your quadtree on top of your triangles using wireframe rectangles to debug any issues.


#2Bacterius

Posted 22 August 2013 - 03:46 PM

You need to traverse the quad-tree as follows:

 

1. start at root node.

2. intersect your ray with the root node's bounding box.

3. does it intersect it? if not, return (to the calling function) with no intersection (if you can't express "no intersection" in your algorithm, just use infinite distance)

4. if this is a leaf node:

  - intersect the ray with all the triangles in the node, and return (to the calling function) the closest intersection

else:

 - find out which children nodes the ray intersects, and sort them according to closest intersection (this is the trickiest part in my experience)

 - recurse to step 2 for each child node, in order of intersection, until the closest triangle found is closest than the distance to a child's bounding box (in which case any triangle inside that child will be further away than the one you've already found, so there's no need to traverse it)

 - return (to the calling function) the closest intersection you found

 

This is a recursive process, and will find the closest triangle intersecting the ray with complexity O(log(n)) where n is the number of triangles in your quadtree. You probably want to implement this with a stack instead of using recursion (at least once everything is working) for performance's sake. The really annoying part is getting the bounding box collisions right, I highly recommend you overlay your quadtree on top of your triangles using wireframe rectangles to debug any issues.


#1Bacterius

Posted 22 August 2013 - 03:45 PM

You need to traverse the quad-tree as follows:

 

1. start at root node.

2. intersect your ray with the root node's bounding box.

3. does it intersect it? if not, return (to the calling function) with no intersection (if you can't express "no intersection" in your algorithm, just use infinite distance)

4. if this is a leaf node:

  - intersect the ray with all the triangles in the node, and return (to the calling function) the closest intersection

else:

 - find out which children nodes the ray intersects, and sort them according to closest intersection (this is the trickiest part in my experience)

 - recurse to step 2 for each child node, in order of intersection, until the closest triangle found is closest than the distance to a child's bounding box (in which case any triangle inside that child will be further away than the one you've already found, so there's no need to traverse it)

 - return (to the calling function) the closest intersection you found

 

This is a recursive process, and will find the closest triangle intersecting the ray with complexity O(log(n)) where n is the number of triangles in your quadtree. You probably want to implement this with a stack instead of using recursion (at least once everything is working) for performance's sake. The really annoying part is getting the bounding box collisions right, I highly recommend you overlay your quadtree on top of your triangles using wireframe cubes to debug any issues.


PARTNERS