An Efficient Ray-Quadrilateral Intersection Test

Ares Lagae and Philip Dutré
Katholieke Universiteit Leuven

This paper appears in issue Volume 10, Number 4.
An electronic version of this article is available.

Abstract

We present a new and efficient method to compute the intersection point between a convex planar quadrilateral and a ray. Contrary to the Schlick-Subrenat intersection test, the bilinear coordinates of the intersection point are computed only for rays that hit the quadrilateral. Rays that do not hit the quadrilateral are rejected early. Our method is up to 40% faster compared to the algorithm presented by Schlick and Subrenat. The intersection test we present is based on the Möller-Trumbore ray-triangle intersection algorithm. The new test is at least as fast as two ray-triangle intersection tests, and yields bilinear coordinates with no discontinuities in the isoparametrics. Source code implementing the intersection test is available online.

Author Information

Ares Lagae, Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200 AB-3001 Heverlee, Belgium ares.lagae@cs.kuleuven.be

Philip Dutré, Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200 AB-3001 Heverlee, Belgium philip.dutre@cs.kuleuven.be

Source Code

The file erqit.cpp (12k html) contains C++ source code implementing a minimal ray tracer that ray traces a single quadrilateral covered with a checkerboard texture. The intersection test described in this paper is implemented in the function intersect_quadrilateral_ray().

BibTeX Entry

@article{LagaeDutre05,
  author = "Ares Lagae and Philip Dutré",
  title = "An Efficient Ray-Quadrilateral Intersection Test",
  journal = "journal of graphics, gpu, and game tools",
  volume = "10",
  number = "4",
  pages = "23-32",
  year = "2005",
}