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