1.5. Ray Shooting

1.5. Ray Shooting

Ray shooting is an elementary task that frequently arises in ray tracing, volume visualization, and games for collision detection or terrain following. The task is, basically, to find the earliest hit of a given ray when following that ray through a scene composed of polygons or other objects.

A simple way to avoid checking the ray against all objects is to partition the universe into a regular grid (see Figure 1.12). With each cell, we store a list of objects that occupy that cell (at least partially). Then we just walk along the ray from cell to cell, and check the ray against all those objects that are stored with that cell .

image from book
Figure 1.12: Ray shooting can be implemented efficiently with a grid.

In this scheme (and others), we need a technique called mailboxes that prevents us from checking the ray twice against the same object [Glassner 89]. Every ray gets a unique ID (we just increment a global variable holding that ID whenever we start with a new ray); during traversal, we store the rays ID with the object whenever we have performed an intersection test with it. But before doing an intersection test with an object, we look into its mailbox to see whether the current rays ID is already there; if so, we know that we have already performed the intersection test in an earlier cell.

In the following, we will present two methods that use octrees to further reduce the number of objects considered .



Geometric Data Structures for Computer Graphics2006
Geometric Data Structures for Computer Graphics2006
ISBN: N/A
EAN: N/A
Year: 2005
Pages: 69

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net