• Advertisement
Sign in to follow this  

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.

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

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 this post


Link to post
Share on other sites
Advertisement
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 this post


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

google is better at explaining than me.

Share this post


Link to post
Share on other sites
Quote:
Original post by Palidine
you 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 this post


Link to post
Share on other sites
Quote:
Original post by Eelco
quite 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 this post


Link to post
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?

thx for your replies

Share this post


Link to post
Share on other sites
Quote:
Original post by Jungle Boy
Palidine, your algorithm just check if the vertices is in the cube
a poly could overlap an cube with all it's vertices outside the cube

Eelco, 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 this post


Link to post
Share on other sites
Quote:
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.
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 this post


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

it's all about octree construction
i need to know which tris are intersecting/inside octree's cubes

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement