Скачать 114.71 Kb.
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.
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:
Table 4: Triangle-triangle intersection results
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.
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.
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:
Table 5: Triangle-AABB intersection results
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.
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.
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:
Table 6: Sphere-AABB intersection results
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.
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.
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.
«part» in «part-object», so I must slip away from any kleinian world on pain of confusion
Объектов (Object Inspector). Как Вы помните, Object Inspector имеет две “странички” “Properties” (Свойства) и “Events” (События)....