Sign in to follow this  

Concave polyhedra intersection tests

This topic is 3486 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been looking for examples on how to test the intersection between two concave polyhedra, but can't seem to find any. So, here's what I was thinking of doing: 1. Find if any of the triangles in polyhedron #1 intersect any of the triangles in polyhedron #2. If any do, then the polyhedra intersect. If not, move to 2. 2. Find if all of the vertices of polyhedron #2 are inside of polyhedron #1. If so, then the polyhedra intersect. If not, move to 3. 3. Find if all of the vertices of polyhedron #1 are inside of polyhedron #2. If so, then the polyhedra intersect. If not, then the polyhedra do not intersect. Is this the correct way to do it? If so, then I need help with 2 and 3: I tried to extend 2d point in polygon tests (send a ray outward to infinite x and count how many times it intersects a line) into 3d, but I could not think of how I would handle the ray hitting vertices. There could be an infinite number of triangles attached to a vertex in 3D, but in 2D there will always be 2 lines attached to a vertex. Is there a know way to handle that? The only other way that I can imagine to find if a point is in a concave polyhedra would be to find the closest triangle to the point and see if the normal points toward or away from the point. Is there some thing else that I am missing? Am I heading in the right direction? Greggles

Share this post


Link to post
Share on other sites
I would not start with your item 1. That's jumping into the slow path. Note that any concave polyhedron can be enclosed 100% by another polyhedron, a convex hull. Or a bounding volume...sphere or box, axis-aligned or oriented. You really must do a super fast test before digging into triangle/triangle tests. Really. You must! Pick some bounding volume. Spheres are cheapest, next axis-aligned boxes, then oriented boxes, then convex hulls. The concave bodies cannot intersect at all of the convex bounding volumes do not overlap.

A more sophisticated approach to bounding volumes would be something like an OBB tree, which subdivides concave meshes into a collection of oriented boxes (each convex of course). This is a hierarchical tree, and you basically traverse the tree and then only do triangle/triangle tests for a very few triangles at the leaves of the tree. The OBB Tree approach works well for both concave objects and animated objects, e.g., split the tree at joints so if a limb moves, it's portion of the tree also moves and you're all set to test animated object vs. animated object. But, for your project, you may not need to go sophisticated. I only put it out there so you'll think about your needs carefully.

As for your general approach, though slow your steps 1 to 3 should capture all the cases for volume intersection. Ultimately, to be strictly correct, you will have to go through something like those steps. The bounding volume idea mentioned above simply: a) very often will completely eliminate the need to go into your 1-2-3; and, b) can greatly reduce the number of triangles that need to be tested, e.g., if you were to do the OBB-tree approach it'll tell you to test these 3 triangles vs. these 9 rather than 1000 vs. 1000.

Hope that helps!

[Edited by - grhodes_at_work on May 28, 2008 11:13:18 AM]

Share this post


Link to post
Share on other sites
Oh, for the point-in-polyhedron test, you just need rules for dealing with rays that pass close to or through a vertex. If you build your mesh such that it is indexed (triangles all reuse the same vertex at coincident corners), you can attach a flag to each vertex. Reset the flags to false prior to running the ray test, then while running the trace, if the ray hits a vertex when testing against one triangle, set the flag to true. For other triangles, if the ray hits a vertex that is already marked with a true flag, do not in that case increment the hit count. Use some kind of fat/thick primitive approach to snap the ray when it is close to the vertex, otherwise floating point math may mess you up. See Christer Ericson's notes on geometric robustness over at the Essential Math site for ideas on thick primitives (see the sticky thread on physics engines and resources in this forum for a link to that site).

Share this post


Link to post
Share on other sites
Quote:
Original post by grhodes_at_work
I would not start with your item 1. That's jumping into the slow path. Note that any concave polyhedron can be enclosed 100% by another polyhedron, a convex hull. Or a bounding volume...sphere or box, axis-aligned or oriented. You really must do a super fast test before digging into triangle/triangle tests. Really. You must! Pick some bounding volume. Spheres are cheapest, next axis-aligned boxes, then oriented boxes, then convex hulls. The concave bodies cannot intersect at all of the convex bounding volumes do not overlap.


Yeah, actually, I had already planned on some sort of sphere or axis-aligned box bounding hierarchy, but I just forgot to mention it.

Quote:
If you build your mesh such that it is indexed


I would rather not be chained to indexed meshes, but what you suggeted will probably be what I use. I'm still open to suggestions for non-indexed geometry, though [smile].


Quote:
See Christer Ericson's notes on geometric robustness over at the Essential Math site for ideas on thick primitives (see the sticky thread on physics engines and resources in this forum for a link to that site).


Great link! I didn't visit that site when I was going through the resources links.

Thanks for all the help!

Share this post


Link to post
Share on other sites
Quote:
Original post by greggles
I would rather not be chained to indexed meshes, but what you suggeted will probably be what I use. I'm still open to suggestions for non-indexed geometry, though [smile].


The thing that indexing...and shared vertices gives you is....the topological connectivity that clearly defines an interior and exterior to your model volume. It is this explicit topology that enables computer algorithms to robustly reason about geometry without any requirements on the quality of the input. With a model that assembled using topological data structures such as indexing, it is rather easy for the computer to determine whether the model is manifold or watertight, or not. (Well, indexed models also potentially increased memory and operation efficiency for some operations.) Of course with non-indexed geometry you can still have a set of faces that happen to form a closed volume with a human-intuitive interior and exterior. It is just that the algorithm cannot easily know that this is true. It'll just give you dumb results, and you have to know to trust them.

So, if you know your geometry to be a non-indexed geometry that happens to be watertight (convex or concave matters not), there are probably numerous ways to robustly do point-in-polyhedron tests, AS LONG AS you realize your input mesh has to be in reasonably good shape. One approach to this is to use the concept of "co-edges" and "co-vertices." The idea here is to walk through the model and for each unique vertex location (within some thick vertex radius) create a "co-vertex" that will have the flag I mentioned. As you visit each triangle in a first pass, tag each mesh vertex with a pointer to the appropriate co-vertex. Once all mesh vertices are tagged, go back and do the same thing with edges, with co-edges defined as a connection between two co-vertices. Then, when doing your ray-trace, use co-vertices and co-edges to snap the ray to vertex/edge in order to determine whether you have already visited a shared vertex or shared edge. Effectively, the co-edges and co-vertices decorate your non-indexed mesh with enough connectivity information to deal with ray tracing problems at those shared edges/vertices, but without putting the indexed constraint on your modelers or procedural algorithms. Make sense?

There are some gotchas that can happen with this approach. Depending on your thick vertex radius, you could have vertices meant to be distinct snapping to the same co-vertex, effectively making some edges (and therefore some triangles) degenerate to zero area. If your thick vertex radius is too small, you can still end up with cracks in the, well, for lack of a better word, "co-model," e.g., you ray trace can still fail. These are par for the course and probably not a problem if the original mesh was built to reasonable tolerances, e.g., no large cracks between triangles.

If your model has T intersections, the approach above would have to be modified, e.g., you'd have to have the ability to split co-edges, and to have mesh edges point to potentially multiple co-edges (e.g., one long mesh edge maps to 2 or more shorter co-edges that are defined from the smaller mesh triangles adjacent to the long mesh edge).

One benefit to the co-model approach is that, although there are problems that can crop up, it really is analogous to the vertex welding that some 3D editors provide....it can close cracks that have small nonzero area....the co-model is somewhat "healed." (Geometry "healing" is a term used in the CAD industry.)

Hope that helps!

Share this post


Link to post
Share on other sites

This topic is 3486 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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