Re: [Algorithms] Octree octant classify
Brought to you by:
vexxed72
From: Robert D. <bli...@go...> - 2006-09-25 08:47:51
|
If you are using an axis aligned box, then surely quick rejection on each axis would be even more effective - at least in a reasonable proportion of cases - and that has the enormous benefit that once you know you are entirely in one side, then a simple 2D test on the remaining axes will tell you which octants are intersected. Of course you still need the other cases for when it doesn't all sit nicely on one side of one axes, however statistically speaking, for random triangles, you would expect 25% to get quick rejection in each axes, which with 3 axes means overall 57.8% would get a quick rejection in one of the three axes. _____ From: gda...@li... [mailto:gda...@li...] On Behalf Of Matt J Sent: 23 September 2006 21:56 To: Game Development Algorithms Subject: Re: [Algorithms] Octree octant classify Part of the trivial rejection phase of the Tri-Box routine does #2. The seperating axis test does #1 as well. But you give me an idea. It would seem to be more advantage to reorder the routine so the trivial rejection occurs in a different order, in this context. In other words, #1, #2, then the edge-axis tests. That should give good performance. Matthew 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 <http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV> &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 ------------------------------------------------------------------------- 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 <http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV> &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 -- ----- Matt Johnson http://otowngraphics.blogspot.com |