[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: linuxgames@sunsite.dk*Subject*: Re: Triangle-Triangle Intersection Tests*From*: Steve Baker <sjbaker1@airmail.net>*Date*: Wed, 12 Feb 2003 08:59:38 -0600*Delivered-to*: archiver@seul.org*Delivered-to*: mailing list linuxgames@sunsite.dk*Delivery-date*: Wed, 12 Feb 2003 10:00:59 -0500*Mailing-list*: contact linuxgames-help@sunsite.dk; run by ezmlm*References*: <20030202143627.71FA3E43A@whouse.4orsi.it> <3E3D304A.90204@airmail.net> <20030202151533.4A655E43A@whouse.4orsi.it> <3E3D450E.3050501@airmail.net> <3E481ACA.C89B4715@gbl.com.br> <3E491CD4.7010409@gmx.de>*Reply-to*: linuxgames@sunsite.dk*User-agent*: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:0.9.8) Gecko/20020204

Miguel A. Osorio wrote:

I just recently finished coding my version of the algorithm for triangle-triangle intersection presented in the ERIT package (I got the algorithm outline in the book "Real-Time Rendering" from Moller and Haines, 2nd ed.). I believe it's working properly, but I'm not sure of it's efficiency.

The trick with these tests is not doing them! You need to apply 'early-out' testing wherever possible. Test bounding spheres or bounding boxes first - only if those intersect should you even consider testing triangles against each other. You should be able to avoid even transforming the triangle's vertices in most cases. Every triangle-triangle test that I've ever seen has been considerably expensive - but you can usually avoid doing all but a handful of them each frame. If the nature of your application is that there IS a need for a lot of actual tests, you can still do quite a lot to help. There are decisions you can make in implementing code within the triangle-triangle intersector that greatly influence performance if you know things like "90% ofmy tests result in no intersection"...or..."90% of my tests DO result in an intersection". Your algorithm needs to be sensitive to which of those is most likely. For example, it is common to compute the plane equation of one triangle and substitute in each of the vertices of your other triangle to get their (signed) distance from the plane - if all three vertex distances have the same sign - then you know there is no intersection - and you can punt the remainder of the test. If you expect 90% of the tests to fail to produce an intersection, it's worth doing that - but if you expect 90% of tests to result in valid intersections (perhaps because your previous bounding box test is so efficient) then you maybe don't want to waste time doing that test. So, if I were you, I'd look at the things you can do to avoid calling the ERIT test at all - and if despite that, you still do too many tests - then use your existing code to gather statistics about the most likely results of the test and optimise for that case. You should also consider whether you really NEED the results to the precision that a triangle-triangle test would produce? Would a simple bounding box test be enough? ---------------------------- Steve Baker ------------------------- HomeEmail: <sjbaker1@airmail.net> WorkEmail: <sjbaker@link.com> HomePage : http://www.sjbaker.org Projects : http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net http://prettypoly.sf.net

**Follow-Ups**:**Collision detection between BV hierarchies***From:*"Miguel A. Osorio" <maos@gbl.com.br>

**References**:**3d graphics***From:*"Francesco Orsenigo, Xarvh Project" <xarvh@lombardiacom.it>

**Re: 3d graphics***From:*Steve Baker <sjbaker1@airmail.net>

**Re: 3d graphics***From:*"Francesco Orsenigo, Xarvh Project" <xarvh@lombardiacom.it>

**Re: 3d graphics***From:*Steve Baker <sjbaker1@airmail.net>

**Triangle-Triangle Intersection Tests***From:*"Miguel A. Osorio" <maos@gbl.com.br>

**Re: Triangle-Triangle Intersection Tests***From:*Gregor Mückl <GregorMueckl@gmx.de>

- Prev by Date:
**Re: Triangle-Triangle Intersection Tests** - Next by Date:
**Re: OpenGL question** - Previous by thread:
**Re: Triangle-Triangle Intersection Tests** - Next by thread:
**Collision detection between BV hierarchies** - Index(es):