Practical Algorithms for 3D Computer Graphics, 2nd Edition

5.3. Ray tracin g optimization 175

(l)

(k)

8

7

3

2

1

6

5

4

Figure 5.5: Part of a model ma d e from a connected network of polygona l facets.

1. The subdivision is hierarchical. It continues until each rectangle holds on ly

one object or until you reach a maximum user defined depth.

2. The size of the rectangles are not uniform: some are large, some are small.

The size is chosen so that the objective, of “one object in each subdivision”,

is achieved with the fewest number of subdivisions. One way to do this

is to recursively choose a dividin g line at each step that places half the

objects to the right and half to the left of it.

3. The example shows discrete