VEGAS VEGAS VEGAS

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

Transversals to line segments in R3

Lines tangent to triangles in R3

Common tangents to spheres and quadrics in R3

Visuals events

Line transversals and their discrete properties

Geometric permutations of disjoint unit spheres

Helly-type 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

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

Algorithms and implementation

Shadows

Visibility skeleton

Computing the Visibility Skeleton by Plane Sweeps

Predicates for 3D visibility

Other visibility-related results

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint

Helly-Type Theorems for Approximate Covering

Models for non-standard cameras


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

Transversals to line segments in R3

We completely describe the structure of the connected components of transversals to a collection of n line segments in R3. Generically, the set of transversal to four segments consist of zero or two lines. We catalog the non-generic cases and show that n>2 arbitrary line segments in R3 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 R3.

Lines tangent to triangles in R3

We establish upper and lower bounds on the number of connected components of lines tangent to four triangles in R3. 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.

Common tangents to spheres and quadrics in R3

We completely characterize the quadruples of spheres R3 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.
basket1

Visuals events

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 visual-event 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 visual-event surfaces of a smooth manifold cannot be easily retrieved from the visual-event surfaces of a sequence of polyhedral approximations of this manifold. We studied the visual-event surfaces associated with the topological changes in the apparent contour of an object, a notion that is well-defined both in the smooth and discrete setting. For scenes consisting of disjoint convex sets, we characterized these visual-event 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 visual-event surfaces.

Line transversals and their discrete properties

Geometric permutations of disjoint unit spheres

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 non-trivial shapes (arbitrary radii balls, unit-length line segments, disjoint translates of a convex set...).

Helly-type theorems for line transversals to disjoint unit balls

Helly's theorem, from 1913, asserts that finitely many convex sets in Rd have non-empty 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.

Line transversals to disjoint balls

We prove that the set of directions of lines intersecting three disjoint balls in R3 in a given order is a strictly convex subset of S2. We then generalize this result to n disjoint balls in Rd. 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 Helly-type theorems.

Lower bounds for Helly numbers

We proved that our bound of 2d-1 on certificates for isolated line transversals to disjoint balls in Rd 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 2d-2 or fewer disjoint balls must be instable. As a consequence we can bound from below the maximum size of a certificate for the non-existence of a line transversal by 2d-1, improving on the previous bound of 5 going back to 1957.

Isolated line transversals to polytopes

Asymptotic complexity of visibility structures

Visibility complex

We presented two new fundamental lower bounds on the worst-case 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 non-occluded line segments among n disjoint unit balls, has complexity Ω(n4), which matches the trivial O(n4) upper bound. This result settled, negatively, the conjecture that this set of line segments, or, equivalently, the visibility complex, has smaller worst-case complexity for disjoint fat objects than for skinny triangles. We also proved an Ω(n3) lower bound on the complexity of the set of non-occluded lines among n balls of arbitrary radii, improving on the trivial Ω(n2) bound. This new bound almost matches the 2010 O(n3+ε) upper bound by Rubin.

Visibility Complex of Random Scenes

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 worst-case complexity of the visibility complex, n2 in the plane and n4 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.

On the Number of Lines Tangent to Four Polytopes

A family of convex polyhedra with n edges in total may have up to order n4 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(n2k2). 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 n4 bound is very pessimistic when the triangles admit some structure.

Average Complexity of Silhouettes of a Polyhedron

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 worst-case complexity of the silhouette of convex polyhedra and the average asymptotic complexity of "reasonable" polyhedral approximations of smooth manifolds.

Complexity of Shadow Boundaries

We give lower and upper bounds on the complexity of the boundary between the umbra and penumbra regions cast on a plane by extended light-sources (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.

Algorithms and Implementation

Shadows

With the insight obtained on visual-event surfaces we developed a new method for computing the exact boundaries between the full light, penumbra and umbra regions of first-order shadows cast by area light-sources; 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 six-month internship for his Master thesis.

Visibility skeleton


We presented an efficient sweep-plane 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.

Computing the Visibility Skeleton by Plane Sweeps

We propose an algorithm for computing the visibility skeleton of a collection of polyhedra in arbitrary position with worst-case complexity O(n2k2), improving over the brute-force approach with complexity order n5. 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.

Predicates for 3D visibility

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.

Other Visibility-Related Results

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint

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 log2 n+s) worst-case time where k is the number of different views seen from L and s is the size of the output.

Helly-Type Theorems for Approximate Covering

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).
  • Helly-Type Theorems for Approximate Covering.
    J. Demouth, O. Devillers, M. Glisse and X. Goaoc.
    • In Proc. 24th ACM Symposium on Computational Geometry (SoCG), Washington, 2008.

Models for non-standard cameras

We obtained a complete analytical characterization of a large class of central and non-central imaging devices, unifying two earlier approaches of Ponce in 2009 and Pajdla in 2002. Specifically, we showed that any linear line congruence, i.e. two-dimensional 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, two-slits, pushbroom, pencil and oblique cameras.