MULTI-LEVEL GRID STRATEGIES FOR RAY TRACING - Improving Render Time Performance for Row Displacement Compressed Grids

Vasco Costa, João Madeiras Pereira

2010

Abstract

Grids have some of the lowest ray tracing acceleration structure build times. This is because acceleration structure construction is analogous to a sorting algorithm. The ideal behavior for a sorting algorithm is to have O(N) time complexity regarding the number of elements. Grids also have O(N) construction time complexity regarding the number of primitives unlike other commonly used acceleration structures, such as kd-trees or bounding volume hierarchies, which have an O(N logN) lower bound. This trait makes grid ray tracing interesting for many applications including animation. Recent algorithmic developments have also made it possible to achieve one-level grid construction, with low memory requirements, by compressing empty grid cells. Unfortunately one-level grids achieve lower render time performance than recursive structures such as multi-level grids. We present a method for rapidly building a grid with similarly good render time performance and using less memory than classic multi-level grids. We demonstrate that this method is a remarkably effective solution for interactive ray tracing of large scanned models.

Paper Citation

in Harvard Style

Costa V. and Madeiras Pereira J. (2010). MULTI-LEVEL GRID STRATEGIES FOR RAY TRACING - Improving Render Time Performance for Row Displacement Compressed Grids . In Proceedings of the International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2010) ISBN 978-989-674-026-9, pages 219-224. DOI: 10.5220/0002815302190224

in Bibtex Style

@conference{grapp10,
author={Vasco Costa and João Madeiras Pereira},
title={MULTI-LEVEL GRID STRATEGIES FOR RAY TRACING - Improving Render Time Performance for Row Displacement Compressed Grids},
booktitle={Proceedings of the International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2010)},
year={2010},
pages={219-224},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002815302190224},
isbn={978-989-674-026-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2010)
TI - MULTI-LEVEL GRID STRATEGIES FOR RAY TRACING - Improving Render Time Performance for Row Displacement Compressed Grids
SN - 978-989-674-026-9
AU - Costa V.
AU - Madeiras Pereira J.
PY - 2010
SP - 219
EP - 224
DO - 10.5220/0002815302190224