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, efficiencywise, 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
Transversals to line segments in R^{3}
Lines tangent to triangles in R^{3}
Common tangents to spheres and quadrics in R^{3}
Line transversals and their discrete properties
Geometric permutations of disjoint unit spheres
Hellytype theorems for line transversals to disjoint unit balls
Line transversals to disjoint balls
Lower bounds for Helly numbers
Isolated line transversals to polytopes
Asymptotic complexity of 3D visibility structures
Visibility Complex of Random Scenes
On the Number of Lines Tangent to Four Polytopes
Average Complexity of Silhouettes of a Polyhedron
Complexity of Shadow Boundaries
Computing the Visibility Skeleton by Plane Sweeps
Other visibilityrelated results
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint
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...
We completely describe the structure of the connected components of transversals to a collection of n line segments in R^{3}. Generically, the set of transversal to four segments consist of zero or two lines. We catalog the nongeneric cases and show that n>2 arbitrary line segments in R^{3} admit at most n connected components of line transversals, and that this bound can be achieved in certain configurations when the segments are coplanar, or they all lie on a hyperboloid of one sheet. This implies a tight upper bound of n on the number of geometric permutations of line segments in R^{3}. 

We establish upper and lower bounds on the number of connected components of lines tangent to four triangles in R^{3}. We show by a construction that four triangles may admit as many as 62 common tangents. We prove that there are at most 162 connected components of tangents, and at most 156 if the triangles are disjoint. In addition, if the triangles are in (algebraic) general position, then the number of tangents is finite and it is always even. Finally we provide an experimental study on the number of tangents to four random triangles. 

We completely characterize the quadruples of spheres R^{3} with infinitely many common tangent lines. Specifically, we show that four spheres admit infinitely many common tangents if they intersect in a circle (possibly degenerating to a point) or have aligned centers and each sphere has a circle of tangency with one and the same quadric of revolution with symmetry axis the line passing through all centers. This quadric can be a cone, a cylinder or a hyperboloid of one sheet. 

When an observer moves in a 3D scene, his view of the scene changes qualitatively when he goes through certain critical positions. This idea underlies many approaches to visibility questions in Computer Vision, Computer Graphics and Computational Geometry. The locus of critical points, or visualevent surfaces, depends on the precise meaning attached to ``view'' and ``qualitative change''. The two traditional approaches to these questions consider objects that are either smooth manifolds or polyhedra, and capture different phenomena; in particular, the visualevent surfaces of a smooth manifold cannot be easily retrieved from the visualevent surfaces of a sequence of polyhedral approximations of this manifold. We studied the visualevent surfaces associated with the topological changes in the apparent contour of an object, a notion that is welldefined both in the smooth and discrete setting. For scenes consisting of disjoint convex sets, we characterized these visualevent surfaces and showed that this notion captures the essential properties of the previous smooth and discrete approaches, while being simpler to analyze. In the case of polyhedral manifolds, we gave a partial characterization of these visualevent surfaces. 

We show that any family of n disjoint balls of equal radius in finite dimension has at most 2 geometric permutations (pairs of orderings induced by a line that intersect every ball) if n>8 and at most 3 otherwise. That this bound is asymptotically independant of both n and the dimension of the space is remarquable, as this is not the case for other nontrivial shapes (arbitrary radii balls, unitlength line segments, disjoint translates of a convex set...). 

Helly's theorem, from 1913, asserts that finitely many convex sets in R^{d} have nonempty intersection if and only if every d+1 of them intersect. Danzer, in 1957, showed that a similar statement holds for lines intersecting disjoint disks with equal radii in the plane: if for every 5 disks there exists a line that intersect them, then there exists a line that intersects the whole family. He also conjectured that a similar result holds in higher dimension. We settle this conjecture. 

We prove that the set of directions of lines intersecting three disjoint balls in R^{3} in a given order is a strictly convex subset of S^{2}. We then generalize this result to n disjoint balls in R^{d}. As a consequence, we can improve upon several old and new results on line transversals to disjoint balls in arbitrary dimension, such as bounds on the number of connected components and Hellytype theorems. 

We proved that our bound of 2d1 on certificates for isolated line transversals to disjoint balls in R^{d} is best possible for any d. This result is based on (i) the construction of isolated line transversals that are stable in the sense that they remain isolated transversals when the balls are subject to small (independent) translations along or rotations around the line, and (ii) a proof that any isolated line transversal to 2d2 or fewer disjoint balls must be instable. As a consequence we can bound from below the maximum size of a certificate for the nonexistence of a line transversal by 2d1, improving on the previous bound of 5 going back to 1957. 
We presented two new fundamental lower bounds on the worstcase
combinatorial complexity of sets of free lines and sets of
maximal free line segments in the presence of balls in three
dimensions. The main one proves that the visibility complex of n
disjoint unit balls, or equivalently the set of maximal
nonoccluded line segments among n disjoint unit balls, has
complexity Ω(n^{4}), which matches the trivial O(n^{4}) upper bound.
This result settled, negatively, the conjecture that this set of
line segments, or, equivalently, the visibility complex, has smaller
worstcase complexity for disjoint fat objects than for skinny triangles.
We also proved an Ω(n^{3}) lower bound on the complexity of the set
of nonoccluded lines among n balls of arbitrary radii, improving on
the trivial Ω(n^{2}) bound. This new bound almost matches the 2010
O(n^{3+ε}) upper bound by Rubin.

We study the size of the visibility complex of random distributions, in 2 and 3 dimensions, and show that its asymptotic behavior is essentially linear. This shows that the worstcase complexity of the visibility complex, n^{2} in the plane and n^{4} in 3 dimensions, is attained by pathological scenes and need not reflect its practical size. This analysis also provides new insight on the expected size of other global visibility data structures, notably the aspect graph. 

A family of convex polyhedra with n edges in total may have up to order n^{4} lines tangent to any four of them. We prove that if the number k of polytopes is taken into account in the analysis, this bound becomes O(n^{2}k^{2}). Moreover, this bound is asymptotically tight and holds for possibly intersecting polytopes in arbitrary degenerate position (counting connected components of tangents rather than tangents). This confirms the intuition that the classical order n^{4} bound is very pessimistic when the triangles admit some structure. 

We give theoretical evidence of a widely observed phenomenon in computer graphics: the size of the silhouette of a polyhedron is much smaller than the size of the whole polyhedron. Our results pertain to the worstcase complexity of the silhouette of convex polyhedra and the average asymptotic complexity of "reasonable" polyhedral approximations of smooth manifolds. 

We give lower and upper bounds on the complexity of the boundary between the umbra and penumbra regions cast on a plane by extended lightsources (segments, polygons...) in the presence of polygon or polytope obstacles. For example, we show that a segment light source can cast, in the presence of two triangular obstacles, four connected components of umbra. 

With the insight obtained on visualevent surfaces we developed a new method for computing the exact boundaries between the full light, penumbra and umbra regions of firstorder shadows cast by area lightsources; the associated prototype software is, up to our knowledge, the first implementation that computes exactly such shadow boundaries of polygonal light sources in the presence of polyhedral obstacles for nontrivial scenes. This implementation was first developed by J. Demouth in his Ph.D, and later improved by J.H. Jang whom joined the group for a sixmonth internship for his Master thesis. 
We presented an efficient sweepplane algorithm for computing the set of free line segments tangent to (possibly intersecting) arbitrary convex polytopes. We produced an implementation of this algorithm (called Visqueux) that computes robustly the vertices of the visibility skeleton (a substructure of the visibility complex) of a set of convex polyhedra in generic position. This implementation is a key element of the prototype Shadows for computing limits of umbra; it also allowed us to study experimentally the size of the 3D visibility skeleton (a data structures that encodes visibility information) in a random setting and, in particular, to show that the constant involved in the asymptotic complexity is small. We also presented a substructure of the visibility skeleton data structure that provides a tradeoff between size and information. 
We propose an algorithm for computing the visibility skeleton of a collection of polyhedra in arbitrary position with worstcase complexity O(n^{2}k^{2}), improving over the bruteforce approach with complexity order n^{5}. Our technique is to sweep a plane around each edge and maintain the visibility skeleton of that planar section. We implemented our algorithm, so far for disjoint convex polyhedra in generic position, and analyze its practical behavior. 

In geometric computing, combinatorial decisions often rely on numerical computations. This dependence is encapsulated in the notion of predicates, that is decisions made by an algorithm to choose which branch to follow in its computation tree. Naive formulations of the classical predicates arising in 3D visibility computations easily lead to evaluation of polynomials of degree 100 or higher. We analyze these predicates and devise formulations of the same decisions using substantially lower degree polynomials. 

Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves. We prove that after an O(n log n) preprocessing time and using O(n) space, moving viewpoint queries along a specified line segment L can be answered in O(k log n+s) amortized or O(k log^{2} n+s) worstcase time where k is the number of different views seen from L and s is the size of the output. 

We show that for any t>0, any covering of a unit disk U by unit disks contains a subset whose size is bounded by a function of t that covers U up to an area at most t. We present generalizations to various other shapes, including sets of lines arising in visibility problems, as well as asymptotic upper and lower bounds on C(t). 

We obtained a complete analytical characterization of a large class of central and noncentral imaging devices, unifying two earlier approaches of Ponce in 2009 and Pajdla in 2002. Specifically, we showed that any linear line congruence, i.e. twodimensional section of the Grassmannian manifold by a projective subspace, corresponds to the set of integral lines of some 4 x 4 linear map. This allows to extend classical techniques developed for the pinhole camera, e.g. stereoreconstruction, to any pair of cameras whose projections are governed by such linear line congruences: pinhole, twoslits, pushbroom, pencil and oblique cameras.  