ABSTRACT
A fast routine for testing whether a triangle and a box are overlapping in three dimensions is presented. The test is derived using the separating axis theorem, whereafter the test is simplified and the code is optimized for speed. We show that this approach is 2.3 vs. 3.8 (PC vs. Sun) times faster than previous routines for this. It can be used for faster collision detection and faster voxelization in interactive ray tracers. The code is available online.
- Eberly, David, 3D Game Engine Design: A Practical Approach to Real-Time Computer Graphics, Morgan Kaufmann Publishers Inc., San Francisco, 2000. http://www.magic-software.com/ Google ScholarDigital Library
- Graphics Gems III Errata Listing, http://www.graphicsgems.org/Google Scholar
- Gottschalk, S., M. C. Lin, and D. Manocha, "OBBTree: A Hierarchical Structure for Rapid Interference Detection," Computer Graphics (SIGGRAPH '96 Proceedings), pp. 171--180, August, 1996. http://www.cs.unc.edu/~geom/OBB/OBBT.html Google ScholarDigital Library
- Green, D. and D. Hatch, "Fast Polygon-Cube Intersection Testing," in Alan Paeth, ed., Graphics Gems V, AP Professional, Boston, pp. 375--379, 1995. http://www.graphicsgems.org/Google Scholar
- Haines, Eric, and John Wallace, "Shaft Culling for Efficient Ray-Traced Radiosity," in P. Brunet and F. W. Jansen, eds., Photorealistic Rendering in Computer Graphics (Proceedings of the Second Eurographics Workshop on Rendering), Springer-Verlag, New York, pp. 122--138, 1994. http://www.acm.org/tog/editors/erich/Google ScholarCross Ref
- Möller, Tomas, and Eric Haines, Real-Time Rendering, AK Peters Ltd., Natick, MA, 1999. http://www.realtimerendering.com/Google Scholar
- Terdiman, Pierre, Personal communication, 2001.Google Scholar
- Voorhies, Douglas, "Triangle-Cube Intersection," in David Kirk, ed., Graphics Gems III, AP Professional, Boston, pp. 236--239, 1992. http://www.graphicsgems.org/ Google ScholarDigital Library
Recommendations
Fast 3D triangle-box overlap testing
A fast routine for testing whether a triangle and a box are overlapping in three dimensions is presented. The test is derived using the separating axis theorem, whereafter the test is simplified and the code is optimized for speed. We show that this ...
Grey-box concolic testing on binary code
ICSE '19: Proceedings of the 41st International Conference on Software EngineeringWe present grey-box concolic testing, a novel path-based test case generation method that combines the best of both white-box and grey-box fuzzing. At a high level, our technique systematically explores execution paths of a program under test as in ...
Image-based fast small triangle rasterization
ICAT'06: Proceedings of the 16th international conference on Advances in Artificial Reality and Tele-ExistenceMany graphics and visualization applications require fast rendering and animation of fine detailed objects, which are named atomic primitives here. A primitive is a basic graphics shape such as a line or triangle that is directly rasterized into the ...
Comments