Darwin Baines and Dr. Robert P. Burton, Computer Science
Overview
Voxel-Selected Ray Tracing (VSRT) is a technique that uses undersampling to reduce the computation time necessary to render realistic looking animations. Although undersampling tends to reduce the quality of an image, VSRT includes error checking techniques that minimize the reduction in quality of the animation. I produced a basic working model of VSRT that reduced the number of voxels calculated. I explored a way to improve the algorithm even further by making the sampling adaptive so that we could find more similarity between picture frames and therefore reduce the number of calculations. Although I found it possible to implement such an algorithm, I concluded it to be impractical because of the unwanted effect that it would have on the VSRT algorithm and the memory strain that it would create. Instead I determined that an approach to reduce the memory requirements would be more appropriate.
Investigation
In my proposal, I included several tasks that I wished to accomplish.
· Determine the placement of the originally sampled rays in later frames, after virtual camera movement and adjustment.
· Determine how to choose the rays to sample in the first frame.
· Adapt the VSRT algorithm so that it can handle different intervals between sampled rays.
Challenges
Determining the placement of the originally sampled rays in later frames, after virtual camera movement and adjustment
There are several algorithms that successfully adapt to movement in a scene and use that information to interpolate calculations in a later frame of an animation.1,2 I investigated implementing these algorithms with VSRT, but found that they could be implemented only at a great expense to the algorithm. Therefore I looked at other means of improving the algorithm.
Determining how to choose the rays to sample in the first frame
VSRT is an algorithm that unenhanced requires greater than average memory. Because the algorithm bases the interpolation of most voxels on certain neighboring voxels, information for each voxel must be stored. First the status of a voxel is stored, whether calculated, interpolated, or unknown. Once a ray is calculated for a voxel, the ray and intersection information must be stored pertaining to that voxel. Another piece of information required for each voxel is its final color value. After this information has been calculated and placed in memory, only then can it be written to disk. This memory requirement is acceptable for the small and simple animations that I have been creating (13.8Mb for a 200 pixels x 200 pixels x 6 frames animation). For larger pictures, several frame (real time animation requires 24 frames/second), and a large number of objects in the scene, the memory requirements become unacceptable.
Although the VSRT algorithm appears to be rather complex with its 3D application, it is really quite elegant. The routine is recursively defined and avoids redundancies and excess calculations. Since the algorithm deals with cubes and shapes related to cubes, a common distance between the sampled voxels is assumed. Should we lose this organization, information would have to be stored as to how voxels are associated together. This would increase the demand for memory. If the algorithm has too high of a memory demand, then the algorithm becomes impractical. Implementing any of these algorithms would imply storing that organizational information and putting a further strain on memory.
Adapting the VSRT algorithm so that it can handle different intervals between sampled rays.
There is a second reason I found the implementation of these algorithms with VSRT to be impractical. With the basic geometry of the algorithm being destroyed, the elegance is lost. No longer would the algorithm involve a simple iteration assuming sampled voxels at common intervals. Each sample region would have to be dealt with as a special case, destroying the elegance of the algorithm. It would make it difficult to calculate the center of the deformed sample space and would make it difficult to subdivide. For these reasons, I decided to explore different means of improving the algorithm. These alternative means are topics for continuing research described next.
Future Work
I am continuing to work on ways of reducing required memory and implementing common techniques that will not significantly increase the demand for memory.
The technique that I am currently implementing involves writing some data to the file before every frame has been sampled and calculated. This process involves calculating a section of animation and saving the preceding half of the section in the image file. The second half is used when calculating the next section and also is checked for errors that may be caught in the latter section. This technique does limit the amount of error checking that can be done through time, but it also allows us more memory since only a section of the ray and intersection calculations are stored at a certain time.
Other techniques that I intend to implement include a bounding hyper-box hierarchy.3 This is a common technique that when implemented reduces the number of intersection calculations. It should not dramatically increase the memory requirement of the algorithm. It should make the algorithm more practical for animation of complex scenes (i.e. scenes with many objects in them).
Accomplishments
Since January, I have made good progress on the VSRT algorithm. I have implemented a working model of VSRT. I have explored several options for improving the algorithm. I am investigating ways of reducing the required memory for the algorithm and reducing the computational time even further. I am working to have the algorithm sufficiently established to warrant publication in the professional literature.
Conclusion
Although my investigation found in impractical to implement the adaptive algorithms with VSRT, the VSRT algorithm is a promising algorithm that when completed will offer significant calculation reductions, without straining the memory capacity of a computer.
References
- Adelson, S.J. and Hodges, L.F. May 1995. IEEE Computer Graphics and Applications: 43-52.
- Badt Jr. S. 1988. The Visual Computer 4:123-132.
- Glassner, A.S. March 1988. IEEE Computer Graphics and Applications: 60-70.