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.

We present the first complete, exact and efficient C++ implementation of a method for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the near-optimal algorithm recently introduced by Dupont et al., [2]. Unlike existing implementations, it correctly identifies and parameterizes all the connected components of the intersection in all cases, returning parameterizations with rational functions whenever such parameterizations exist. In addition, the coefficient fields of the parameterizations are either minimal or involve one possibly unneeded square root. We prove upper bounds on the size of the coefficients of the output parameterization and compare these bounds to observed values. We give other experimental results and present some examples.

In this paper, we present the first exact, robust and practical method for computing an explicit representation of the intersection of two arbitrary quadrics whose coefficients are rational. Combining results from the theory of quadratic forms, linear algebra and number theory, we show how to obtain parametric intersection curves that are near-optimal in the number and depth of radicals involved.

In this paper, we show that, amongst n uniformly distributed unit balls in $\mathbb{R}^3$, the expected number of maximal nonoccluded line segments tangent to four balls is linear. Using our techniques we show a linear bound on the expected size of the visibility complex, a data structure encoding the visibility information of a scene, providing evidence that the storage requirement for this data structure is not necessarily prohibitive. These results significantly improve the best previously known bounds of $O(n^{8/3})$ [F. Durand, G. Drettakis, and C. Puech, {ACM Transactions on Graphics}, 21 (2002), pp. 176-206]. Our results generalize in various directions. We show that the linear bound on the expected number of maximal nonoccluded line segments that are not too close to the boundary of the scene and tangent to four unit balls extends to balls of various but bounded radii, to polyhedra of bounded aspect ratio, and even to nonfat three-dimensional objects such as polygons of bounded aspect ratio. We also prove that our results extend to other distributions such as the Poisson distribution. Finally, we indicate how our probabilistic analysis provides new insight on the expected size of other global visibility data structures, notably the aspect graph.

A Texture Atlas is an efficient color representation for 3D Paint Systems. The model to be textured is decomposed into charts homeomorphic to discs, each chart is parameterized, and the unfolded charts are packed in texture space. Existing texture atlas methods for triangulated surfaces suffer from several limitations, requiring them to generate a large number of small charts with simple borders. The discontinuities between the charts cause artifacts, and make it difficult to paint large areas with regular patterns.In this paper, our main contribution is a new quasi-conformal parameterization method, based on a least-squares approximation of the Cauchy-Riemann equations. The so-defined objective function minimizes angle deformations, and we prove the following properties: the minimum is unique, independent of a similarity in texture space, independent of the resolution of the mesh and cannot generate triangle flips. The function is numerically well behaved and can therefore be very efficiently minimized. Our approach is robust, and can parameterize large charts with complex borders.We also introduce segmentation methods to decompose the model into charts with natural shapes, and a new packing algorithm to gather them in texture space. We demonstrate our approach applied to paint both scanned and modeled data sets.

In this article, we introduce a general-purpose method for computing radiosity on scenes made of parametric surfaces with arbitrary trimming curves. In contrast with past approaches that require a tessellation of the input surfaces (be it made up of triangles or patches with simple trimming curves) or some form of geometric approximation, our method takes full advantage of the rich and compact mathematical representation of objects. At its core lies the virtual mesh , an abstraction of the input geometry that allows complex shapes to be illuminated as if they were simple primitives. The virtual mesh is a collection of normalized square domains to which the input surfaces are mapped while preserving their energy properties. Radiosity values are then computed on these supports before being lifted back to the original surfaces. To demonstrate the power of our method, we describe a high-order wavelet radiosity implementation that uses the virtual mesh. Examples of objects and environments, designed for interactive applications or virtual reality, are presented. They prove that, by exactly integrating curved surfaces in the resolution process, the virtual mesh allows complex scenes to be rendered more quickly, more accurately, and much more naturally than with previously known methods.

In this paper, we address the problem of curve and surface reconstruction from sets of points. We introduce regular interpolants which are polygonal approximations of planar curves and surfaces verifying a local sampling criterion. Properties of regular interpolants lead to new polygonal reconstruction methods from sets of organized and unorganized points. These methods do not need any parameter of additional information apart from the original points and allow unorganized sets of points to be easily handled.

Augmented reality is the technique by which real images can be enhanced by addition of computer-generated information. Augmented reality shows great promises in fields where a simulation in situ would be either impossible, not realistic enough or too expensive. We present in this paper an augmented reality loop that uses vision tools (perspective inversion, tracking) and show how it was used to fully enrich a sequence of the bridge of Paris with a model illuminated synthetically.

In this paper, we describe an algorithm to compute arbitrary stationary multiple-point formulas. We report its full implementation in Maple and show some examples matching formulas found by hand computation. We also present an application to the enumeration of lines having specified contact with a projective surface.