GPGPU Programming for Games and Science

Sample Applications 371

FIGURE 7.4: Intersection of a meshes for a cylinder and a torus.

2. Precompute a tree of bounding volumes and perform the localized search

on the CPU to generate sets of triangles that you know do intersect.

Then process those sets with the GPU triangle-triangle intersector.

3. Precompute the tree of bounding volumes on the GPU and use the GPU

triangle-triangle intersector.

I leave these alternatives as exercises.

7.6 Shortest Path in a Weighted Graph

Consider a directed graph G =(V, E), where V is the set of vertices and

E is the set of directed edges connecting vertices. Assuming V is finite, we

may index the n vertices as V