Re: [Algorithms] Octree octant classify

[Jon W. <hp...@mi...>]

The octants need to:

1) intersect the plane of the triangle
2) intersect the aabb of the triangle

Both of those are cheap tests, but may not be sufficient to get 100% 
accuracy. Once you have identified octants that fulfill both these 
tests, you can do triangle-box tests for each of them. Or, it may be 
faster to just accept some slop, and pass down vertices you don't 
necessarily have to.

Btw: In actuality, I think a worst-case triangle can actually pass 
through seven of the eight octants, but not through all eight (because 
at least one octant must be culled by the plane of the triangle, if that 
plane doesn't pass through the center of the cube -- and if so, more 
than one will be culled.).

Cheers,

          / h+


Matt J wrote:
> Given a triangle inside a cube, which is subdivided 8 times (i.e. an 
> octree), is there any optimal (clean) way of classifying which of the 
> octants one specific triangle intersects.
>
> The current approach is to check for a triangle and cube collision for 
> each octant (i.e. all 8), and then assign a bitflag, i.e. flag &= (1 
> << n) where n is the octant # from 0...7
>
> I thought about seperating axis test against the min, max of each 
> triangle edge u0, u1, or u2 (axises from the center) of the cube, but 
> I think that would not work because it wouldnt tell me which specific 
> octants it intersected the cube, because that info would be lost in 
> the projection. Im thinking another approach might have something to 
> do with intersecting the triangle edges with the planes of the cubes 
> formed by the axises from the center. Any ideas?
>
> Thanks,
>
> Matthew
> ------------------------------------------------------------------------
>
> -------------------------------------------------------------------------
> Take Surveys. Earn Cash. Influence the Future of IT
> Join SourceForge.net's Techsay panel and you'll get the chance to share your
> opinions on IT & business topics through brief surveys -- and earn cash
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
> ------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188