VEGAS VEGAS VEGAS

The Vegas research group was created in 2005 and is part of LORIA (Lorraine Laboratory for Research in Information Technology and its Applications), a combined Research Unit (UMR 7503) common to CNRS (Centre National de la Recherche Scientifique), INPL (Institut National Polytechnique de Lorraine), INRIA (Institut National de Recherche en Informatique et en Automatique), Université Henri Poincaré Nancy 1, Université Nancy 2.

The main scientific focus of our group is the design and implementation of technology-independent, robust and efficient geometric algorithms for 3D visibility and low-degree algebraic surfaces.

By technology-independent we mean usable solutions to geometric problems that will be relevant long after current hardware is obsolete. By robust we mean algorithms that do not crash on degenerate inputs and always output topologically consistent data. By efficient we mean algorithms that run reasonably quickly on realistic data where performance is ascertained both experimentally and theoretically.

Meeting our computational objectives requires mathematical tools that are both geometric and algebraic. In particular, we need further knowledge of the basic geometry of lines and surfaces in a variety of spaces and dimensions as well as to adapt sophisticated algebraic methods, often computationally prohibitive in the most general setting, for use in solving seemingly simple geometric problems.

3D Visibility Our research project is centered around two themes. First, we focus on the theory and applications of three-dimensional visibility problems. Visibility computations are central in computer graphics applications. Computing the limit of the umbra and penumbra cast by an area light source, identifying the set of blockers between any two polygons and determining the view from a given point are examples of visibility queries that are essential for the realistic rendering of 3D scenes. Our research objectives include the design and implementation of algorithmic solutions for 3D visibility. In particular we work on designing and producing a full robust implementation of the visibility skeleton in 3D for polyhedra, a structure that encodes visibility information. Then, our goal is to apply our results to the graphics problems that motivated our studies, namely to computing shadows using discontinuity meshes in radiosity algorithms. To design algorithmic solutions for 3D visibility, we first need a better understanding of the properties of lines in space. To that purpose, we work on predicates, degeneracies, and combinatorics for lines. In parallel, we work on improving and implementing the algorithmic tools for global 3D visibility data structures. It should be noted that the theoretical study of the properties of lines in three-dimensional space is a fundamental line of research that is of interest independent of any direct application.

Quadrics Our second center of interest concerns low-degree real algebraic surfaces such as quadrics. Such surfaces allow for a good compromise between simplicity, flexibility and modeling power. They play a leading role in the construction of accurate computer models of physical environments for simulation and prototyping purposes, especially in the fields of industrial design, architecture and manufacturing. Our goal is to contribute to the development of an effective geometric computing dedicated to curved geometric objects. In particular, we work on the design and implementation of algorithms for computing intersections of quadratic surfaces and for computing quadratic complexes, i.e., piecewise quadratic surfaces. It should be stressed that the curved objects that we consider are not necessarily everyday three-dimensional objects, but also abstract mathematical objects that are not linear, that may live in high-dimensional space, and whose geometry we do not control. For instance, the set of lines in 3D (at the core of visibility issues) that are tangent to three polyhedra span a ruled quadratic complex and the lines tangent to a sphere correspond, in projective five-dimensional space, to the intersection of two quadratic hypersurfaces.

Vegas is one of the four offsprings of the project Isa (created in 1995). In 2002, several members left Isa to form the new project, Qgar, on the topic of document recognition. In 2005, Isa was split into three new groups, Alice centered on digital geometry, Magritte focused on augmented reality and medical imaging, and Vegas.