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/
Detecting if a tri is inside an axis-aligned cube
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.
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.
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
i founded a SAT explanation here -> http://www.harveycartel.org/metanet/tutorials/tutorialA.html#section1
and tested on a paper ;P
thx again
oh god, this page has some amazing flash to demonstrate how the SAT works, no more paper needed o_O
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 :
Seen at the component level, stating AB is {x,y} this gives :
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 :
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement