Jump to content

  • Log In with Google      Sign In   
  • Create Account

QuadTree ray collision


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 Tasaq   Members   -  Reputation: 1252

Like
1Likes
Like

Posted 22 August 2013 - 09:52 AM

Hi,

 

I am forced to ask this shameful question here. I've build a quadtree structure which contains 2D triangles. Everything would be nice, cool and fast if only I would knew how to use it rolleyes.gif

 

My aim is to cast a 2D ray from given point with given direction, and get the closest triangle position. And my question is how should I approach that? Should I add my ray to quadtree and there find collision? Or should I aproach it different way?

 

 



Sponsor:

#2 Bacterius   Crossbones+   -  Reputation: 9268

Like
2Likes
Like

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 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.


Edited by Bacterius, 22 August 2013 - 03:47 PM.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#3 Tasaq   Members   -  Reputation: 1252

Like
0Likes
Like

Posted 22 August 2013 - 04:23 PM

Thank You for answer :) I actually was thinking about somthing similar but i thought it's not the best way to do it.

 

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

 

I agree, that's the part that actually discouraged me, but it shouldn't be a problem for me (the real problem is that I am lazy laugh.png ).

I also display grid already so I can see how structure looks like.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS