Visibility and lines in space

Computing whether two points or two surfaces are mutually visible is a common task in application fields in computer science such as image synthesis. Since opaque 3D objects can produce complex occlusion phenomenas, existing methods to solve 3D visibility problems are commonly approximate and are often, efficiency-wise, the bottleneck of applications. Typical examples are global illumination methods such as radiosity.

Why not compute, for a given scene, all visibility informations and preprocess it to solve visibility problems more efficiently? This approach raises various questions such as estimating the amount of visibility information contained in a typical scene, computing efficiently all this visibility information or dealing with degenerate input.

Line geometry has been a classical subject since the 19th century and provides the foundation for the resolution of several algorithmic problems in 3D visibility. These foundations are, however, incomplete and a number of results need to be refined. We work in particular on the combinatorics and discrete properties of certain sets of lines.

Structure and degeneracies of lines tangent to objects

Lines and segments tangent to 3 or 4 objects in 3D are the building blocks of global visibility data structures. To design robust and efficient algorithms for these data structure, one usually has to answer the two typical questions: "what is the maximum number of lines tangent to four objects of a given type?" and "what are the configurations of four objects with infinitely many common tangents?". Perhaps surprisingly, little is known beyond the classical case where the objects are lines...

Line transversals and their discrete properties

Lines intersecting or tangent to prescribed objects are central to various geometric problems. In three dimensions, one reason why efficient algorithms for these problems are scarce is that the geometry of these sets of lines is still not well understood. One of our goal is to contribute to filling this gap by studying the combinatorial properties of sets of lines. In particular, we try to understand how the geometry of 3D objects constrains the structure of the set of lines that intersect them (their line transversals).

Asymptotic complexity of 3D visibility structures

The worst-case asymptotic complexity of a geometric (data) structure is usually not a satisfiable estimate of its practical size. While realistic input models for geometric data are notoriously hard to come by, the worst-case analysis can still be refined, for instance by injecting additional parameters in the analysis. In this direction, our work focus on analyzing the complexity of visibility-related structures.

Algorithms and implementation

The design and implementation of robust and efficient algorithms for global visibility raises many problems, both algorithmic and algebraic

Other visibility-related results

Results with a visibility flavor that do not relate to one of the above directions.