## 3.4Triangle-Triangle Intersection As detailed in the previous chapter, triangle-triangle intersections are used to make sure no clipping occurs in a 3d model. We introduced the separating axis test and robust interval overlap algorithms and have hypothesized that although the early stage rejections of both algorithms are similar, the former needs to invest less time in these checks and as such is expected to run faster in these cases.
However, in all other case the interval overlap method most definitely will outperform the SAT due to the immense different in computationally heavy code of the remaining phases of the algorithm. ### 3.4.1Test Setup The test setup will be based on each algorithm’s hypothesis expectations and their individual rejection and acceptance moments. As such the following tests will be simulated for the (a) separating axis test and (b) robust interval overlap algorithms:
No triangle/plane overlap to compare the algorithms’ early rejections Plane/triangle overlap, but no triangle/triangle overlap allows (a) to exit relatively early in the latter part of its algorithm Triangle/triangle overlap compare full running times Fully randomized average case scenario to compare real-life performances ### 3.4.2Test Results
**Test #** |
**(a) Running Time (ms)** |
**(b) Running Time (ms)** | 1) | 568 | 575 | 2) | 1985 | 1346 | 3) | 3629 | 1581 | 4) | 1118 | 971 |
**Table 4: Triangle-triangle intersection results** ### 3.4.3Comparison Results & Conclusions Although it seems our expectation of the SAT to result in a faster early rejection seems to be correct, the difference is too small to reliably come to any useful conclusions. However, for the remaining cases the interval overlap method definitely shows its predicted superiority over the SAT.
Although the extreme differences in running time seem to be mostly occurring at the edge cases, the real-life randomized scenario also shows a slight benefit in favor of the interval overlap method. Hence we can conclude that this method forms the logical choice for triangle-triangle intersection tests. ## 3.5Triangle-AABB Intersection As detailed in the previous chapter, triangle-AABB intersections are used when assigning triangle primitives into box-based spatial data structures. We introduced the triangle-box intersection and separating axis test algorithms and have hypothesized that the dual perspective of the triangle-box intersection approach will outperform the rejection-only approach of the separating axis test on positive triangle-AABB intersections.
In contrast to this the separating axis test seems to be superior in all other cases due to the heavy calculations involved in the triangle-box intersection algorithm. Further note should be taken of the fact that we can use the early trivial rejection of the triangle-box intersection algorithm for the separating axis test algorithm as well. ### 3.5.1Test Setup The test setup will be based on each algorithm’s hypothesis expectations and their individual rejection and acceptance moments. As such the following tests will be simulated for the (a) triangle-box intersection and (b) separating axis test algorithms:
Trivial internal vertices acceptances favoring (a)’s early acceptance No triangle-AABB intersections (a)’s box half-plane exclusion test No triangle-AABB intersections (a)’s dodecahedron half-plane exclusion test No triangle-AABB intersections (a)’s octahedron half-plane exclusion test Interior triangle protrusion (a)’s early ray-triangle acceptance test Interior box protrusion comparing full running time of algorithms Fully randomized average case scenario to compare real-life performances Fully randomized average case scenario with early trivial acceptance case for (b) to compare real-life performances with attempted improvement of (b) ### 3.5.2Test Results
**Test #** |
**(a) Running Time (ms)** |
**(b) Running Time (ms)** | 1) | 190 | 1727 | 2) | 172 | 337 | 3) | 409 | 763 | 4) | 426 | 774 | 5) | 1317 | 1830 | 6) | 1600 | 1777 | 7) | 258 | 505 | 8) | 250 | 471 |
**Table 5: Triangle-AABB intersection results** ### 3.5.3Comparison Results & Conclusions While comparing both algorithms for early acceptance, it is shown that an enormous difference in running times backs up our statement of the triangle-box intersection test outperforming the separating axis test in these cases.
However, further testing of the other scenarios shows our hypothesis concerning the remaining scenarios to be incorrect. Although the running time of the triangle-box intersection test rapidly increases as predicted, the growth for the separating axis test is actually higher. As such it can be concluded that the triangle-box intersection algorithm is superior for all cases. ## 3.6Sphere-AABB Intersection As detailed in the previous chapter, sphere-AABB intersections are used when spheres are supported as geometric primitives and these need to be sorted into box-based spatial data structures. Additionally, these kind of intersection routines are also needed in some spatially approximating global illumination algorithms such as photon mapping. We introduced the distance-based and quick rejection intertwined algorithms and have hypothesized that their performance is neigh-equal, except for the early termination in the quick-rejection intertwined test. ### 3.6.1Test Setup The test setup will be based on each algorithm’s hypothesis expectations and their individual rejection and acceptance moments. As such the following tests will be simulated for the (a) distance-based and (b) quick-rejection intertwined algorithms:
Sphere-AABB overlap expected to slightly benefit (a) No sphere-AABB overlap expected to slightly benefit (b) Fully randomized average case scenario to compare real-life performances ### 3.6.2Test Results
**Test #** |
**(a) Running Time (ms)** |
**(b) Running Time (ms)** | 1) | 112 | 90 | 2) | 137 | 85 | 3) | 126 | 101 |
**Table 6: Sphere-AABB intersection results** ### 3.6.3Comparison Results & Conclusions Although test 1 runs slightly faster for (a) than test 2 does (and vice versa for (b)), these expected benefits do not confirm our expectation of separate niche superiority, since in both cases the quick-rejection intertwined algorithm is better. This is also illustrated in the average case scenario as well, resulting in the conclusion that this algorithm consistently outperforms the distance-based approach. ## 4Summary & Future Work Seeing as how we’ve already discussed the conclusions for each specific object-object intersection type using the test results in the previous chapter, we shall limit ourselves here to a small summary of these conclusions. Ray-triangle intersection In case of intersection behind origin, plane intersection/inclusion is faster. In all other cases, including randomized, Möller-Trumbore is faster. Ray-sphere intersection: In case of intersection behind origin, geometry optimized test is faster. In case of misses, quadratic solution is slightly faster. In all other cases, including randomized, they perform equally. Ray-AABB intersection: In case no intersection location is needed, ray-slope algorithm is faster. When t is reported and multiple rays are handled, slab method is faster. In randomized scenario, ray-slope algorithm is faster. Triangle-triangle intersection: In case of early rejection, SAT seems slightly faster In all other cases, including randomized, interval overlap method is faster. Triangle-AABB intersection: In case of early acceptance, triangle-box intersection is significantly faster. In all other cases we have been proven wrong in our hypothesis; triangle-box overlap was expected to be faster due to lower computationally heavy code fragments, but instead triangle-box intersection is faster. Sphere-AABB intersection: Although we expected slightly faster running times for each algorithm’s specialty niche, the quick-rejection intertwined algorithm actually outperforms the distance-based approach slightly in all cases.
Concerning future work, it would be interesting to research the adaptability of these intersection algorithms to parallel architectures, with an emphasis per algorithm on the effect of early reject/accept exits on code divergences, the memory dependency of the algorithms and their associated memory latency hiding capacity. **Bibliography** *Haines, Eric, "Essential Ray Tracing Algorithms," Chapter 2 in Andrew Glassner, ed., An Introduction to Ray Tracing, Academic Press Inc., London, 1989. *
*Kay, T.L., and J.T. Kajiya, "Ray Tracing Complex Scenes," Computer Graphics (SIGGRAPH '86 Proceedings), pp. 269-278, August 1986. *
*Eisemann, Martin, Marcus Magnor, Thorsten Grosch, and Stefan Müller, "Fast Ray/Axis-Aligned Bounding Box Overlap Tests using Ray Slopes," journal of graphics tools, vol. 12, no. 4, pp. 35-46, 2007. *
*Peter Shirley. 2002. **Fundamentals** **of** **Computer** **Graphics**. A. K. Peters, Ltd., Natick, MA, USA*
*Wyvill, G. (1995). Practical Ray Tracing www.cs.otago.ac.nz/cosc342/2010-342/2010-notes/PracticalRayTracing.pdf*
*Akenine-Möller, Tomas, and Ben Trumbore, "Fast, Minimum Storage Ray-Triangle Intersection," journal of graphics tools, vol. 2, no. 1, pp. 21-28, 1997.*
*Akenine-Möller, Tomas, "Fast 3D Triangle-Box Overlap Testing," journal of graphics tools, vol. 6, no. 1, pp. 29-33, 2001.*
*Douglas Voorhies. 1992. Triangle-cube intersection. In **Graphics** **Gems** **III**, David Kirk (Ed.). Academic Press Professional, Inc., San Diego, CA, USA 236-239.*
*Arvo, James, "A Simple Method for Box-Sphere Intersection Testing," in Andrew S. Glassner, ed., Graphics Gems, Academic Press, pp. 335-339, 1990.*
*Larsson, Thomas, Tomas Akenine-Möller, and Eric Lengyel, "On Faster Sphere-Box Overlap Testing," journal of graphics tools, vol. 12, no. 1, pp. 3-8, 2007.*
*Boyd, Stephen, and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004.* *Möller, Tomas, "A Fast Triangle-Triangle Intersection Test," journal of graphics tools, vol. 2, no. 2, pp. 25-30, 1997.* *Akenine-Möller, Haines and Hoffman, “Real-Time Rendering, Third Edition”. A. K. Peters, Ltd., Natick, MA, USA. www.realtimerendering.com.* |