EFSAT - An Exact and Efficient Triangle Intersection Test Hardware

Andreas Raabe, Jan Tietjen, Joachim K. Anlauf

2009

Abstract

Software implementations that test two triangles for intersection often favour speed over exact calculation. They leave it to the user to choose an exact or a fast test depending on the domain of application. Hardware implementations can not opt to make this distinction since users will always expect an accelerator hardware to be applicable in all possible settings. This paper introduces a novel approach towards exact intersection testing of triangles. It is based on the separating axes test and lends itself well to hardware implementation. To be integrable into a hierarchical collision detection design this test needs to be extremely resource efficient. Thus, it does not iterate until an exact solution is found, but instead categorises results as correct and possibly incorrect. It is implemented using 18-bit fixed-point numbers, while still maintaining resolutions that can keep up with double-precision floating-point implementations. The proposed test is integrated into a hierarchical collision detection FPGA-design accelerating collision queries by an order of magnitude. In a realistic benchmark less than 0:9% of possibly incorrect results are reported without impairing system performance.

Paper Citation

in Harvard Style

Raabe A., Tietjen J. and K. Anlauf J. (2009). EFSAT - An Exact and Efficient Triangle Intersection Test Hardware . In Proceedings of the Fourth International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2009) ISBN 978-989-8111-67-8, pages 355-360. DOI: 10.5220/0001775203550360

in Bibtex Style

@conference{grapp09,
author={Andreas Raabe and Jan Tietjen and Joachim K. Anlauf},
title={EFSAT - An Exact and Efficient Triangle Intersection Test Hardware},
booktitle={Proceedings of the Fourth International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2009)},
year={2009},
pages={355-360},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001775203550360},
isbn={978-989-8111-67-8},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Fourth International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2009)
TI - EFSAT - An Exact and Efficient Triangle Intersection Test Hardware
SN - 978-989-8111-67-8
AU - Raabe A.
AU - Tietjen J.
AU - K. Anlauf J.
PY - 2009
SP - 355
EP - 360
DO - 10.5220/0001775203550360