## 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.

Original language | English (US) |
---|---|

Pages | 293-302 |

Number of pages | 10 |

DOIs | |

State | Published - 2002 |

Event | Proceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) - Barcelona, Spain Duration: Jun 5 2002 → Jun 7 2002 |

### Other

Other | Proceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) |
---|---|

Country/Territory | Spain |

City | Barcelona |

Period | 6/5/02 → 6/7/02 |

## Keywords

- Average performance
- Cost model
- Cost prediction
- Octree
- Ray shooting
- Space decomposition

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics