February 9 - 15, 2002

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

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.

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

These problems bear relation to famous problems in enumerative geometry, such as the number of lines on a cubic surface in

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

- [2]
I.G. Macdonald, J. Pach, T. Theobald, Common tangents to four unit balls in
*R*^{3}, 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 2
*n*-2 spheres in*R*^{n}, 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
*R*^{3}, manuscript, 2001.

- [9] Thorsten Theobald, How to realize a given number of tangents to four unit balls in
*R*^{3},

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

- [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 L^{A}T_{E}X byH^{E}V^{E}A.