tkessells01@cc.curtin.edu.au (05/09/91)
What is needed is a fast triangle/box test. I don't need to know the intersections, only whether they hit each other. Currently, I 'm doing : pre-1) usual bounding extent tests, etc ... 1) check if whether the box is completely above or below the plane fitting the triangle. 2) check if an edge of the triangle intersects the box. 3) check if an edge of the box intersects the triangle. I have fiddled the order of doing these tests with little change in speed. The reason a very fast test is needed, beause I am converting triangulations into blocked representations where there is a higher resolution near the triangles and grids of 400x400x400 are not uncommon. Any code, ideas or complete solutions would be appreciated Michael PSImail: psi%050529452300070::Kessells_SR Internet: Kessells_SR@cc.curtin.edu.au Bitnet: Kessells_SR%cc.curtin.edu.au@cunyvm.bitnet UUCP : uunet!munnari.oz!cc.curtin.edu.au!Kessells_SR
chrisg@cbmvax.commodore.com (Chris Green) (05/09/91)
In article <1991May9.144308.8054@cc.curtin.edu.au> tkessells01@cc.curtin.edu.au writes: > >What is needed is a fast triangle/box test. I don't need to know the >intersections, only whether they hit each other. > How about coding the vertex points of the triangle with respect to the box? Generate a 6 bit bit vector for each point. If ANDing all three of these together produces a non-zero result, then there is no intersection. If ORing them all together produces zero, then the thriangle is contained within the box. Otherwise, you'll have to do more tests (the bit vectors can be helpful here as well). The bits are generated by code like if (vertex.x<box.minx) code |= OFF_LEFT; You can make it faster by producing a tree of compare operations, with the leaf nodes containing code like " code=OFF_LEFT | OFF_RIGHT". That resmoves the rendundant comparisons for impossible cases (there are only 27 possible cases). -- *-------------------------------------------*---------------------------* |Chris Green - Graphics Software Engineer - chrisg@commodore.COM f | Commodore-Amiga - uunet!cbmvax!chrisg n |My opinions are my own, and do not - killyouridolssonicdeath o |necessarily represent those of my employer.- itstheendoftheworld r *-------------------------------------------*---------------------------d