Graphics Reference
In-Depth Information
Listing 37.10: C++ implementation of ray-primitive intersection in a list. The
method signature choices streamline the implementation.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/ * O(n) time for n = size() * /
bool firstRayIntersection( const Ray& ray, Value * & value, float & distance) const {
bool anyHit = false ;
for ( int i = 0; i < data.size(); ++i) {
if (Trait::intersectRay(ray, data[i], distance)) {
// distance was already updated for us!
value = &data[i];
anyHit = true ;
}
}
return anyHit;
}
Listing 37.11: C++ implementation of conservative ball-primitive
intersection in a list.
1
2
3
4
5
6
7
8
/ * O(n) time for n = size() * /
void getBallIntersection( const Ball& ball, std::vector<Value * >& result) const {
for ( int i = 0; i < data.size(); ++i) {
if (Trait::intersectsBall(ray, data[i])) {
result.push_back(&data[i]);
}
}
}
Both structures allow insertion of new elements in amortized O( 1 ) time. The
linked list prefers insertion at the head and the array at the end. Finding an element
to delete is a query, so it takes n operations. Once found, the linked list can delete
the element in O( 1 ) time by adjusting pointers. The array can also delete in O( 1 )
time—it copies the last element over the one to be deleted and then reduces the
element count by 1. Because the array is unordered, there is no need to copy more
elements. It is critical, however, that the array and its contents be private so that
there can be no external references to the now-moved last entry.
There may be some advantage to the array's packing of values in a cache-
friendly fashion, but only if the elements are small. If the values are large, then
they may not fit in cache lines anyway, and the cost of copying them during inser-
tion and removal may dwarf the main memory latency and bandwidth savings.
37.6 Trees
Just as they do for sorted data in one dimension, trees provide substantial speedups
in two or more dimensions. In 1D, “splitting” the real line is easy: We consider
all numbers greater than or less than some splitting value v . In higher dimensions,
we generally use hyperplanes for dividing space, and different choices for hyper-
planes lead to different data structures, some of which we now describe.
 
 
 
Search WWH ::




Custom Search