# Object-object intersection comparison for photorealistic graphics rendering

Скачать 114.71 Kb.
 Название Object-object intersection comparison for photorealistic graphics rendering страница 6/6 Дата 24.09.2012 Размер 114.71 Kb. Тип Документы

## 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:

1. No triangle/plane overlap  to compare the algorithms’ early rejections

2. Plane/triangle overlap, but no triangle/triangle overlap  allows (a) to exit relatively early in the latter part of its algorithm

3. Triangle/triangle overlap  compare full running times

4. 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:

1. Trivial internal vertices acceptances  favoring (a)’s early acceptance

2. No triangle-AABB intersections  (a)’s box half-plane exclusion test

3. No triangle-AABB intersections  (a)’s dodecahedron half-plane exclusion test

4. No triangle-AABB intersections  (a)’s octahedron half-plane exclusion test

5. Interior triangle protrusion  (a)’s early ray-triangle acceptance test

6. Interior box protrusion  comparing full running time of algorithms

7. Fully randomized average case scenario  to compare real-life performances

8. 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:

1. Sphere-AABB overlap  expected to slightly benefit (a)

2. No sphere-AABB overlap  expected to slightly benefit (b)

3. 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

1. Haines, Eric, "Essential Ray Tracing Algorithms," Chapter 2 in Andrew Glassner, ed., An Introduction to Ray Tracing, Academic Press Inc., London, 1989.

2. Kay, T.L., and J.T. Kajiya, "Ray Tracing Complex Scenes," Computer Graphics (SIGGRAPH '86 Proceedings), pp. 269-278, August 1986.

3. 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.

4. Peter Shirley. 2002. Fundamentals of Computer Graphics. A. K. Peters, Ltd., Natick, MA, USA

5. Wyvill, G. (1995). Practical Ray Tracing www.cs.otago.ac.nz/cosc342/2010-342/2010-notes/PracticalRayTracing.pdf

6. 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.

7. Akenine-Möller, Tomas, "Fast 3D Triangle-Box Overlap Testing," journal of graphics tools, vol. 6, no. 1, pp. 29-33, 2001.

8. Douglas Voorhies. 1992. Triangle-cube intersection. In Graphics Gems III, David Kirk (Ed.). Academic Press Professional, Inc., San Diego, CA, USA 236-239.

9. Arvo, James, "A Simple Method for Box-Sphere Intersection Testing," in Andrew S. Glassner, ed., Graphics Gems, Academic Press, pp. 335-339, 1990.

10. 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.

11. Boyd, Stephen, and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004.

12. Möller, Tomas, "A Fast Triangle-Triangle Intersection Test," journal of graphics tools, vol. 2, no. 2, pp. 25-30, 1997.

13. Akenine-Möller, Haines and Hoffman, “Real-Time Rendering, Third Edition”. A. K. Peters, Ltd., Natick, MA, USA. www.realtimerendering.com.

## Похожие:

 A part-object which is not any part of any object«part» in «part-object», so I must slip away from any kleinian world on pain of confusion Лабораторная работа №3 Свойства в DelphiОбъектов (Object Inspector). Как Вы помните, Object Inspector имеет две “странички” “Properties” (Свойства) и “Events” (События).... ‘Non-Photorealistic Rendering: a marker Technique Approach’ Object-Oriented Object-Oriented Languages A procedural Approach to Non-Photorealistic Rendering of Pen and Ink Illustrations from Three-Dimensional models Beyond Photorealistic Rendering Nicholas Cameron 3C01 Individual Project 2005 Supervised by Dr Anthony Steed Object Stacks and Application Policy for Camera Recognition of a Moving Object Gslite is a simple, lightweight api for accessing some features of the Ghostscript graphics library, most importantly the font rendering and image decoding Unit 1 : Introduction to Object Orientation ( 7 Hrs )
Разместите кнопку на своём сайте:
Библиотека

База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека