Loading...
Please wait, while we are loading the content...
Similar Documents
Efficient acceleration structures for ray tracing static and dynamic scenes
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ize, Thiago |
| Copyright Year | 2009 |
| Abstract | This dissertation presents efficient acceleration structures for ray tracing static and dynamic scenes. The first method for reducing render time shows how the general binary space partitioning (BSP) tree, unlike the kd-tree variant that uses axis aligned splitting planes, can be used to render static scenes roughly as fast to several times faster than other acceleration structures. The BSP is especially useful for handling geometry configurations that cause substantial slow downs in other acceleration structures; however, its slow build time limits it to applications where the scene can be built offline. Another method improves grid-based acceleration structure efficiency by analytically determining the optimal single or multilevel grid resolutions for various classes of scenes. In particular, we show for manifold-like models composed of compact triangles that storage is linear in the number of triangles, N, and render complexity goes from O(N 1/3) for single level grids to O(N 1/(2d+1)) for d levels. On the other hand, manifold-like models composed of long skinny triangles require super linear memory in order to achieve sublinear time complexity; for a single level grid, our analysis states that O(N3/2) cells must be used and that this gives a time complexity of O(N 1/2). If coherent ray packets are available, we show that using a frustum traversal allows us to simultaneously traverse a packet of rays through a grid, which results in a substantial speedup over the traditional single ray traversal. Dynamic scenes require that the acceleration structure be quickly updated each frame. Pairing the frustum traversal with a quick grid rebuild allows for interactive ray tracing of fully dynamic scenes. Furthermore, we present a highly efficient parallel grid build that scales to many processors. For dynamic scenes that are deformable, a bounding volume hierarchy (BVH) can be updated by quickly refitting its bounding volumes rather than performing a slow BVH rebuild. Unfortunately, refitting can degrade the quality of the tree and lead to worse render times. We maintain a high quality BVH without having to wait for the slow rebuild by refitting the BVH every frame while simultaneously building another BVH from scratch, possibly over the course of several frames. When the new BVH is complete, it replaces the older refitted BVH. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.utah.edu/~thiago/papers/thesis_ize.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
