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.
ТипДокументы
1   2   3   4   5   6

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.
1   2   3   4   5   6

Похожие:

Object-object intersection comparison for photorealistic graphics rendering iconA 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

Object-object intersection comparison for photorealistic graphics rendering iconЛабораторная работа №3 Свойства в Delphi
Объектов (Object Inspector). Как Вы помните, Object Inspector имеет две “странички” “Properties” (Свойства) и “Events” (События)....

Object-object intersection comparison for photorealistic graphics rendering icon‘Non-Photorealistic Rendering: a marker Technique Approach’

Object-object intersection comparison for photorealistic graphics rendering iconObject-Oriented Object-Oriented Languages

Object-object intersection comparison for photorealistic graphics rendering iconA procedural Approach to Non-Photorealistic Rendering of Pen and Ink Illustrations from Three-Dimensional models

Object-object intersection comparison for photorealistic graphics rendering iconBeyond Photorealistic Rendering Nicholas Cameron 3C01 Individual Project 2005 Supervised by Dr Anthony Steed

Object-object intersection comparison for photorealistic graphics rendering iconObject Stacks and Application Policy for

Object-object intersection comparison for photorealistic graphics rendering iconCamera Recognition of a Moving Object

Object-object intersection comparison for photorealistic graphics rendering iconGslite is a simple, lightweight api for accessing some features of the Ghostscript graphics library, most importantly the font rendering and image decoding

Object-object intersection comparison for photorealistic graphics rendering iconUnit 1 : Introduction to Object Orientation ( 7 Hrs )

Разместите кнопку на своём сайте:
Библиотека


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