Name
Abstract | ||
|---|---|---|
The ray shooting problem arises in many different contexts. For example, solving it efficiently would remove a bottleneck when images are ray-traced in computer graphics. Unfortunately, theoretical solutions to the problem are not very practical, while practical solutions offer few provable guarantees on performance. In particular, the running times of algorithms used in practice on different data sets vary so widely as to be almost unpredictable.Since theoretical guarantees seem unavailable, we aim at obtaining a simple, easy to compute way of estimating the performance without running the actual algorithm. We propose a very simple cost predictor which can be used to measure the average performance of any ray shooting method based on traversing a bounded-degree space decomposition.We experimentally show that this predictor is accurate for octree-induced decompositions, irrespective of whether or not the bounded-degree requirement is enforced. The predictor has been tested on octrees constructed using a variety of criteria.This establishes a sound basis for comparison and optimization of octrees. It also raises a number of interesting and challenging questions such as how to construct an optimal octree for a given scene using our cost predictor.Since the distribution of rays in a ray-tracing process may differ from the rigid-motion invariant distribution of lines and the corresponding distribution of rays assumed by our cost predictor, we also experimentally confirm that the performance of an octree for an actual ray-tracing computation is well captured by our cost predictor. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1145/513400.513438 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
cost predictor,ray shooting,octree,cost prediction,cost model,corresponding distribution,bounded-degree requirement,different context,simple cost predictor,space decomposition,actual algorithm,average performance,bounded-degree space decomposition,rigid-motion invariant distribution,actual ray-tracing computation,ray tracing,computer graphic | Bottleneck,Mathematical optimization,Data set,Shooting method,Computer science,Algorithm,Invariant (mathematics),Computer graphics,Traverse,Octree,Computation | Conference |
ISBN | Citations | PageRank |
1-58113-504-1 | 5 | 0.78 |
References | Authors | |
16 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Boris Aronov | 1 | 1430 | 149.20 |
| Hervé Brönnimann | 2 | 866 | 69.61 |
| Allen Y. Chang | 3 | 33 | 6.34 |
| Yi-jen Chiang | 4 | 503 | 38.21 |