Sign in to follow this  
Opwiz

3D Object Intersection Tests

Recommended Posts

I'm working on my 3d object intersection code.. Need to find the best known algorithms for intersection tests between different 3d objects. http://www.realtimerendering.com/int/ is a good page but I want algoritms that tests intersection as well as if object A is inside/outside object B.. Any good resources on the web on this? I suppose I could test for intersection with the described algorithms and then have another algorithm that checks if object A is inside/outside object B. That could be a better alternative if we often are only interested if the objects intersect or not (or only if object A contains B or not). I'm not sure how often this is the case.. what is the best way to go?

Share this post


Link to post
Share on other sites
So you're interested in both boolean tests and containment tests? As you noted, boolean tests will often not tell you whether one object is contained within another, and are faster because of it.

Out of curiousity,

1. What types of objects (spheres, AABBs, etc.) do you want to support, and,

2. What do you need the containment tests for?

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
So you're interested in both boolean tests and containment tests? As you noted, boolean tests will often not tell you whether one object is contained within another, and are faster because of it.

Out of curiousity,

1. What types of objects (spheres, AABBs, etc.) do you want to support, and,

2. What do you need the containment tests for?


1. Currently I plan on supporting spheres, AABBs, OOBs, Frustum & Planes..

2. The main use would be when performing frustum culling. E.g. if I use an octree or something similiar as spatial datastructure I first check if a node in my octree intersects the view frustum and if it entirely fits inside the frustum (the containment test) I do not need to perform any more intersection tests on the nodes children.

I have to choose between having one intersection algorithm that is optimized to do both intersection & containment test (frustum culling would be slightly more efficient) or I can have two seperate algorithms (those cases when we only are interested in either containment or intersection becomes more efficient).



Share this post


Link to post
Share on other sites
As you may already know, spheres, AABBs and OBBs can all be tested fairly easily against planes to see if they are behind, in front of, or intersecting the plane.

You may also already know that the way frustum culling with these bounding volumes is usually done is as follows:

1. Check the BV against each of the 6 planes of the frustum.

2. If the BV is entirely behind any plane, it is outside the frustum and you're done.

3. If the BV is enitrely in front of all planes, it is inside the frustum and you can trivially mark all of its contents as visible.

4. If the BV intersects one or more planes, mark it as visible if it is terminal (i.e. a leaf or an object), or test each of its children if it's a node.

This method will return a few false positives, i.e. objects or nodes that are outside the frustum will be flagged as visible. These false positives can be avoided by doing a more complete test. But it's really not worth the extra work to catch these cases, so generally the plane test is sufficient.

Anyway, that may have all been stuff you already know...

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
As you may already know, spheres, AABBs and OBBs can all be tested fairly easily against planes to see if they are behind, in front of, or intersecting the plane.

...


Yes, I already knew this but thanks anyway.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this