Using Spatial Subdivision

[ LiB ]

Using Spatial Subdivision

Spatial subdivision is the concept of dividing space into smaller regions based on a specific threshold. The reason why you would want to subdivide space is to limit your search to a specific area. Placing objects in a smaller area speeds up your search. The best way to visualize the purpose of subdividing space is by considering one floor of a building. Each room on the floor is a region of space. This means the overall space is subdivided among the rooms, as illustrated in Figure 13.1. The walls, ceilings, and floors of the rooms create the boundaries between the rooms and the doors define the partitioning between the rooms. Within every room are the walls, ceiling, and floor, which create a volume also known as a cell . The first part of a spatial subdivision algorithm is to divide the space into many smaller portions as well as to balance the subdivisions equally among the available cells .

Figure 13.1. The rooms on the floor of a building create the subdivision of space.Each room represents a volume, also known as a cell.

NOTE

TIP

Spatial subdivision subdivides space into smaller regions so that searching for relevant information is easier because the smaller regions can be searched individually.

The second part of spatial subdivision involves searching through the generated cells for the relevant information. Visualize three rooms on a floor. Room one contains books; room two contains toys; and room three contains food. If you were hungry, which room would you go to for some food? You would go to room three; you wouldn't want to look for food in a room full of toys. What you've just done is divide the space based on a series of parameters. In this example, the objects consist of food, toys, and books. You've limited your search by knowing which room contains the relevant objects you are interested in obtaining.

In the room containing food, you might have all sorts of foods. If you want a can of sausages, you might have to search in the cupboard through the canned products. But because you know where the foods are, you can find the food faster. This is the basic idea behind spatial subdivision.

Now back to the topic of photon mapping. You need to find a way to partition the photons in 3D space using spatial subdivision. A way to reduce the time spent searching for the nearest photons in the photon map is to subdivide the space into smaller regions based on point proximity between point sets. Point proximity refers to the relative distance or the local distance between one or more points in a specific area. For example, say you have a photon map of six photons. You can increase the speed when searching for photons through this incredibly small photon map. Before you get started, your point of intersection is located at 0, 0, and 5 and the nearest photon to search for is set to 2.

The photon locations in the photon map are as follows :

• Photon 1 (0, 0, 2)

• Photon 2 (1, 0, 4)

• Photon 3 (1, 0, 5)

• Photon 4 (0, 0, 2)

• Photon 5 (1, 0, 4)

• Photon 6 (2, 0, 6)

Figure 13.2 shows a top-down view of the photon map.

Figure 13.2. A top view of the points posi tioned in world space that are contained in the photon map.

Let's see how long it takes to find the nearest photons for the point of intersection (0, 0, 5). The method you'll use is known as the linear search method. The basic idea behind the linear search method is that you search one ele-ment at a time, beginning with the first element of the array.

This process is as follows:

1. Search element 1, photon 1(not close enough)

2. Search element 2, photon 2 (not close enough)

3. Search element 3, photon 3 (not close enough)

4. Search element 4, photon 4 (not close enough)

5. Search element 5, photon 5 (very close)

6. Search element 6, photon 6 (very close)

As you can see, the time required to search through elements 1 to 4 was a waste and the processor had to actually go through these unimportant steps until the two closest photons were found. The two closest photons next to the point of intersection (0, 0, 5) are Photon 5 (1, 0, 4) and Photon 6 (2, 0, 6).

One better method is to break the six-element array into two smaller arrays based on the relative position of the photons (or the points) located in 3D space. The objective is to split the space into smaller regions by using a split ting node . The splitting node will be a photon that has the best position in the input array. When using a splitting node such as a point to partition space, you are partitioning the space along the X, Y, and sometimes the Z axes.

Consider Figure 13.2 one more time and try to find a place where you can subdivide the space into two regions. The goal is to balance the photons divided on each side as much as possible. A good number is preferably three photons per side. After some careful planning, you might decide that the best point (photon) you can use as the splitting node to subdivide the space is Photon 4 (0, 0, 2). You should choose the photon that cuts the space into two halves on a specific dimension. The dimension utilized is the line that runs horizontally, which is the X axis. See Figure 13.3.

Figure 13.3. Partitioning the space equally on both sides is important because it limits the time required to search for relevant photons.

After you divide the space into two regions, you have two arrays that are divided by Photon 4. The first three elements of the photon map are Photons 1 through 3 (located in Array 1), and the remaining three elements are Photons 4 through 6 (located in Array 2).

Array 1 is composed of the following photons:

• Photon 1 (0, 0, 2)

• Photon 2 (1, 0, 4)

• Photon 3 (1, 0, 5)

Array 2 is composed of the following photons:

• Photon 4 (0, 0, 2)

• Photon 5 (1, 0, 4)

• Photon 6 (2, 0, 6)

Now you can try the process again and see whether this new method helps to speed up the searching process. Using the two-array method for searching for the nearest photons, the process is as follows. You already know that the point of intersection is not in Array 1 because all the photons in this array are behind Photon 4, so you can discard the whole array.

Searching through Array 2 would go as follows:

• Photon 4 (not close enough)

• Photon 5 (very close)

• Photon 6 (very close)

You have just cut the time it takes to find the closest photons in half. This was accomplished by splitting the list into two smaller child lists. This concept is known as binary searching .

The linear search algorithm runs in O(n) time whereas binary search takes only O(log_(n)) . So a 545 microsecond linear search may take only seven microseconds using the binary search. The choice of optimization is determined by how one builds and balances the binary tree (children upon children). You will see this with your own eyes at the end of the chapter. In this case, it doesn't really matter because you have a very small photon map. But just imagine the time you can save if you implement this technique with millions of photons. If it took 30 minutes to render a scene using photon mapping with the linear search method, it may take 15 minutes to 30 seconds using the binary search, which is a big time saver. You definitely increased the speed when rendering by using spatial subdivision. There are two- and three-component spatial subdivision algorithms that can be used to store and search for photons. A BSP Tree is a great candidate to store and retrieve pho-tons and has been used in some applications. A KD Tree works similar to the method just discussed, which is why you'll use it in this book.

[ LiB ]