Detecting if a tri is inside an axis-aligned cube

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

Recommended Posts

how i do that? some approach to that is using ray-tracing collision and classifying the tri vertices about their side of cube planes, but i'm wondering if there is a faster way....

Share on other sites
you said axis-aligned so basically you're just checking against the box's min and max values along the axial directions.

bool isTriInside(Vertex *vertices){    for (int i = 0; i < 3; ++i )    {        if ( vertices.x < box.minX || vertices.x > box.maxX            || vertices.y < box.minY || vertices.y > box.maxY            || vertices.z < box.minZ || vertices.z > box.maxZ )        {            //this vertex is outside the box            return false;        }    }    return true;}

Share on other sites
the seperating planes algorithm is what you need.

google is better at explaining than me.

Share on other sites
Quote:
 Original post by Palidineyou said axis-aligned so basically you're just checking against the box's min and max values along the axial directions.*** Source Snippet Removed ***

quite incorrect.

Share on other sites
Quote:
 Original post by Eelcoquite incorrect.

no, it's correct. he said "axis-aligned", not Object Oriented BOunding Box, in which case you have to check against the planes. with axis aligned you just have to check the coords.

-me

Share on other sites
Palidine, your algorithm just check if the vertices is inside the cube
a poly could overlap a cube with all it's vertices outside the cube

Eelco, is "seperating planes algorithm" the fastest way for this case?

Share on other sites
Quote:
 Original post by Jungle BoyPalidine, your algorithm just check if the vertices is in the cubea poly could overlap an cube with all it's vertices outside the cubeEelco, is "seperating planes algorithm" the fastest way for this case?thx for your replies

Ah, you said inside, which i took to mean "contained by", not "intersecting".

-me

Share on other sites
sorry for the "axis-oriented", the correct is "axis-aligned"
just edited the title....

Share on other sites
Quote:
 Palidine, your algorithm just check if the vertices is inside the cubea poly could overlap a cube with all it's vertices outside the cube.
I take it from this that you don't want a 'tri in axis-aligned cube' test, but rather a 'tri intersects axis-aligned cube' test. In that case eelco's suggestion may be your best bet.

What's the test for? Is it a pre-processing step, e.g. octree construction? Or something else? Depending on the context, different solutions may be more or less appropriate. It's hard to say though without knowing more about the application.

Share on other sites
sorry again, it should be "tri intersects or inside an axis-aligned cube"
just a poor english issue

i need to know which tris are intersecting/inside octree's cubes

Share on other sites
separation axis theorem (SAT) is a solution. Another brute force is testing if vertices are inside the cube, testing if edges if the trinintersect the cube, of ig edges of cube intersects the tri.

SAT is not that difficult, will be faster, more robust, a lot less code, cleaner.

http://www.realtimerendering.com/int/
http://www.cs.lth.se/home/Tomas_Akenine_Moller/code/

Share on other sites
If it's octree construction, performance isn't super-critical (although you obviously want a reasonably efficient algorithm).

The separating axis test will return exact results - no false positives or negatives. So that would be my first choice for the narrow-phase test.

However, you can probably catch most cases without resorting to the SAT test. You could make a bounding box around your triangle, and test that against the octree node. That could return false positives, but no false negatives. You can also test the triangle vertices, as Palidine suggested - that could give false negatives, but no false positives.

If you don't want to bother with the SAT, you could test each vertex of the triangle for inclusion in the box, each edge of the triangle for intersection with a face of the box, and each edge of the box for intersection with the triangle. With that approach you should catch all but the degenerate cases.

So as you can see, there are a number of ways to go about it.

Share on other sites
very thanks, guys

i founded a SAT explanation here -> http://www.harveycartel.org/metanet/tutorials/tutorialA.html#section1
and tested on a paper ;P

thx again

Share on other sites
oh god, this page has some amazing flash to demonstrate how the SAT works, no more paper needed o_O

Share on other sites
Just found a very cool optimization concerning Tri vs Box
or ConvexPolyhedron vs Box more generally. Note that it can be coherent with error metrics. I hope some will have the courage to follow me. It's not that hard with a paper and a little time and concentration.

First the standard algo for SAT here must be adaptated to take benefit of axis alignement. As a result, each d-Facet against (2-d)-Facet case can be seen differently. The base of the optimization, is well known, it's the SAT applied to any convex polyhedron vs a Box (cf the old Graphic Gems 4 for instance). The rest are even more specialized, formal manipulations, to benefit of SIMD technologies.

Notations :
- A,B,C : triangle verts
- N : triangle Normal
- O, E : box center and extent

By a simple translation, A is chosen as the origin. This simplifies the math expressions and the computations.

- Box faces (2-facet) vs Tri verts (0-facet) <=> Box vs Box(Tri)

Reject if : | O(Tri) - O | > (E(Tri) + E)

- Box verts (0-facet) vs Tri face (2-facet) <=> nearest vertex trick

Reject if : (N*C + |N|*E) < 0

- Box edges (1-facet) vs Tri edges (1-facet) <=> nearest vertex trick on the 3 canonical projections.

Let's consider edge AB. (That is vector B since A is the origin). In the plane perp. to Z. Once the z component is dropped from each vector, the nearest vertex gives :
dist_zPerp(AB, Box)  = ((^AB)*O + |^AB|*E)/||AB||^AB denotes the "perp" of AB. If AB is {x,y}, then ^AB is {-y,x}

Seen at the component level, stating AB is {x,y} this gives :
dist_zPerp(AB, Box) = (x*Oy-y*Ox + |y|*Ex+|x|*Ey )  * rsqrt(x*x + y*y)

With the 3 projections grouped, we can easilly view several threads in a tight SSE code. Note that the intermediate computations are very similar to two 3D cross products :

dist_zPerp = ( x*Oy  + |x|*Ey  - y*Ox  + |y|*Ex )*rsqrt(x*x  + y*y) dist_yPerp = ( y*Oz  + |y|*Ez  - z*Oy  + |z|*Ey )*rsqrt(y*y  + z*z)dist_xPerp = ( z*Ox  + |z|*Ex  - x*Oz  + |x|*Ez )*rsqrt(z*z  + x*x)0          = ( 0*0   + |0|*0   - 0*0   + |0|*0  )*rsqrt( 1 (=0|1) )

Note that the rsqrt column is not necessary for a pure intersection routine, where only sign matters. This is only necessary if a metric tolerance (for instance penetration depth) is used as a bias.

We exploit the fast parallel absolute values and test of SSE at their best.
It's all about some swizzle, xor, and, mul, add and you are done ! You have a vector containing the distances in each projection. To finish, you can make three sign tests in //, compact them into a 3 bit mask, and do only one if() per edge in the end.

Still there is something I did not mention for clarity. It's how to determine which side of the edge is the rejecting one in each projection. It's not enough to make te perp of the edges. This depends on the winding order of the triangle on each projection. But this lacking information should in fact be retrieved from the signs of the components of N in 3D. Just a matter of additional and and xors in the code.

There is some beautiful magic in this manipulation. WE COMPUTE 3 2D CASES AT ONCE AS IF WE WERE DOING A SINGLE (WEIRD) 3D OPERATION !!!. I just find this kind of trick awesome coupled with the power of SSE.

The 3 projections in //ized SSE are certainly treated faster than each projection taken independently with a classical floating point library. I don't even mention the higher level geometrical tricks, seldom exploited, that are used to obtain the last formula. Thus a quasi certain 3X speedup on the most difficult part of the normal Tri/Box algo. In the classical SAT algo, you have to deal with 9 edge vs edge cases : 3(triangle edges) * 3(box axes) = 9 axes. 9 computations. Here only 3 are required.

I don't know if it's been done before. Anyone ? Unless I did not see a trivial equivalence with another known technique. The same principles also apply to any Convex_Polyhedron vs Box.