McGill - INRIA Workshop on Computational Geometry in Computer Graphics

Bellairs Research Institute of McGill University
February 9 - 15, 2002

Previous workshops

List of Participants

  • Helmut Alt, Freie Universität Berlin
  • Hervé Brönnimann, Polytechnic University, New York
  • Vida Dujmovic, McGill University
  • Hazel Everett, LORIA
  • Marc Glisse, Polytechnic University, New York
  • Xavier Goaoc, LORIA
  • Sylvain Lazard, LORIA
  • Hyeon-Suk Na, LORIA
  • Sue Whitesides, McGill University
  • David Wood, Carleton University, Ottawa


The problems examined at the workshop concerned 3D visibility questions, with a focus on analyzing the average cost of computations rather than the usual worst-case cost. Two families of problems were studied, one having to do with lines tangent to four objects in R3, the other with minimizing the expected cost of ray shooting.

Visibility queries account for more than half of the overall computation time routinely spent by global illumination algorithms. One approach to speeding up rendering is to store global visibility information in a data structure, the visibility complex of Pocchiola and Vegter, for example, that can then be efficiently queried. The study of lines tangent to four objects is essential for the design and implementation of such data structures.

An alternative data structure, one which is widely used for answering geometric queries such as ray shooting, is the octree. It is not known how to construct an octree for the purpose of minimizing the average cost of ray shooting. Indeed to design an optimal octree a cost measure is needed. Recently Aronov, Bronnimann, Chang and Chiang proposed a simple and promising cost measure (based on preliminary work by Aronov and Fortune). The workshop examined the problem of constructing an optimal octree with respect to this cost measure.

Concerning line tangents, we looked at extending a result previously obtained by some of the participants: among n unit balls uniformly distributed with constant density in a universe modeled by a large ball, the expected number of line segments tangent to four balls and not occluded by the others is O(n). Problems 1, 2, 3 and 4 deal with related questions on tangents to unit balls. Problem 5 also considers unit balls, but looks at the expected complexity of a different quantity: visibility events create shadow curves on the boundaries of the unit balls, and we want to know the expected total complexity of their arrangements.

Problems 6, 7, and 8 address the case where unit balls are replaced by more complex objects (mainly polytopes). One basic problem is to establish the worst-case number of non-occluded tangents among four objects. Another deals with the expected number of occlusions when more than four objects are considered. Finally, the bound for four objects may be strengthened with further assumptions having to do with the shape of the polytopes. One solution to problem 7, shows that an upper bound on the size of the silhouette of a polytope with some assumptions is relevant for counting common tangents.

The last problem listed below arose from another paper by participants which dealt with the expected cost of ray shooting in a scene. Here, the goal is to build a data structure that minimizes the expected cost of ray shooting for a uniform distribution of rays. Problem 9 raises the question of whether constructing the optimal space decomposition (or even within a constant factor thereof) is inherently hard, and this even for a quadtree containing points in the plane. Similar questions also remain unanswered in 3D. The same problems need to be studied for non-uniform distributions of rays that depend on the scene.

Problems & Solutions

Annotated bibliography

References on lines tangent to four unit balls in R3

The basic result is reference [2], which shows that any four unit balls in R3 whose centers are not collinear, have at most twelve common tangent lines, and that this bound is tight. (If the centers are collinear, there is an infinity of common tangent lines.) When the centers are coplanar, there can be at most eight tangent lines [3], and this number is again tight. There are configurations that have k tangent lines, for any kÎ{0,...,12} [9], and these configurations can be realized in R3. The high-degree (12) brought about by spheres makes the analysis of degenerate situations much more intricate. This contrasts with the situation for lines, for which there are either an infinity (if all lines lie on a ruled surface of degree two), or 0, 1,or 2 lines tangent to a set of four lines. In an attempt at mixing unit balls and lines in the same model, Theobald [8] shows that the common tangents to k unit balls and 4-k lines is 2, 4, 8, 12, 12, 12 for k=0,1,2,3,4 respectively. If the unit ball restriction is removed, reference [6] shows that there at most 3· 2d-1 real tangent lines to 2d-2 general spheres in Rd (in non-degenerate positions) and that this bound is tight.

On the algorithmic front, the question of computing the common tangent lines to four unit balls boils down to solving a system of equations with variables the position and orientation of the line; most equations are linear, except for one equation of degree 3 and another of degree 4 in three variables. The same situation arises if the variables are in Plücker coordinates, another way to assign coordinates for lines in R3 [5]. For computing a common tangent to four lines, reference [7] explains how to use Plücker coordinates to cast the problem into a null-space computation in R5, and singular value decomposition to efficiently and robustly compute them. It also details the input degeneracies, how to detect and handle each case, and the solution set of common tangents that arises.

These problems bear relation to famous problems in enumerative geometry, such as the number of lines on a cubic surface in R3 (there can be at most 27 of them, and only the numbers 3, 7, 15, and 27 can be realized by real lines). Also Appolonius' problem asks for the circles tangent to three given circles, for which every number of real tangent circles from 0 up to 8 can be realized, except for 7 [4]. Devillers et al. [1] show that the number of cylinders passing through 4 points and with unit radius is 12 (each cylinder correspond to a common tangent to four unit balls centered at those points). They also obtain tight bounds of 6 cylinders through five points in R3, of 186 cylindrical shells through six points, and 9 pairs of parallel cylinders through two sets of four points.

[1] Olivier Devillers, Bernard Mourrain, Franco P. Preparata, Philippe Trebuchet, On circular cylinders by four or five points in space, INRIA Technical Report No 4195, Juin 2001.

[2] I.G. Macdonald, J. Pach, T. Theobald, Common tangents to four unit balls in R3, Discrete and Computational Geometry, 26:1 (2001), 1--17.

[3] G. Megyesi, Lines tangent to four unit spheres with coplanar centers, Discrete Computational Geometry, 26 (2001), 493--497.

[4] D. Pedoe, The missing seventh circle, Elem. Math. 25:14--15, 1970.

[5] Marco Pellegrini, Ray shooting and lines in space, in Handbook of Discrete and Computational Geometry, chapter 32, pages 599--614. CRC Press LLC, Boca Raton, FL, 1997.

[6] Frank Sottile and Thorsten Theobald, Lines tangent to 2n-2 spheres in Rn, arXiv:math.AG/0105180 v1, 22 May 2001.

[7] Seth Teller and Michael Hohmeyer, Determining the lines through four lines, To appear in the Journal of Graphics Tools.

[8] Thorsten Theobald, An enumerative geometry framework for algorithmic line problems in R3, manuscript, 2001.

[9] Thorsten Theobald, How to realize a given number of tangents to four unit balls in R3,

References on tangent lines to many unit balls

Since tangent lines to four objects (lines, balls or polytopes) are essential to the study of 3D visibility, there is a lot of literature on the topic. Of these, we will mention the various families of related problems.

[10] Pankaj Agarwal, Boris Aronov, and Micha Sharir, Line transversals of balls and smallest enclosing cylinders in three dimensions, Disc. Comput. Geom. 21 (1999), 373--388.

[11] Olivier Devillers, Vida Dujmovic, Hazel Everett, Xavier Goaoc, Sylvain Lazard, Hyeon-Suk Na, Sylvain Petitjean, A linear bound on the expected number of visibility events, manuscript, 2002.

[12] F. Durand, G. Drettakis, C. Puech, The 3D visibility complex, manuscript, 2001.

[13] Michel Pocchiola, Gert Vegter, The visibility complex, International Journal of Computational Geometry and Applications, Vol 6, No 3 (1996) 279--308.

[14] Robert Schiffenbauer, A survey of aspect graphs, Technical Report TR-CIS-2001-01, Department of Computer and Information Science, Polytechnic University, 2001.

References for ray shooting

[15] B. Aronov, H. Brönnimann, A.Y. Chang, Y.-J. Chiang, Cost prediction for ray tracing, SoCG'02 (Barcelona).

[16] Franklin S. Cho, David Forsyth, Interactive ray tracing with the visibility complex, Computers and Graphics, Special issue on visibility, 1999.

[17] Olivier Devillers et al, On the size of the silhouette of a polyhedron, draft, 2001.

[18] Shai Mohaban and Micha Sharir, Ray shooting amidst spheres in three dimensions and related problems, manuscript, March 23, 1997.

[19] M. Pellegrini, Ray-shooting on triangles in 3-space, Algorithmica 9:471--494, 1993.

[20] M. Pellegrini and P. Shor, Finding stabbing lines in 3-space, Discrete and Computational Geometry 8:191--208, 1992.

[21] Marco Pellegrini, Ray shooting and lines in space, in Handbook of Discrete and Computational Geometry, chapter 32, pages 599--614. CRC Press LLC, Boca Raton, FL, 1997.

This document was translated from LATEX by HEVEA.