VEGAS Research team

Effective Geometric Algorithms for Surfaces and Visibility

Team presentation

The main scientific focus of the VEGAS team 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.

Research themes

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.

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.

International and industrial relations

Scientific partnerships: McGill University, Canada; University of Illinois at Urbana-Champaign, USA; KAIST university, South Korea; University of Athens, Greece; INRIA Sophia-Antipolis, France.

Industrial relationships: CIRTES St Dié, France; SGDL inc. Canada; VSP-Technology, France.

Keywords: Computational geometry Three-dimensional visibility Quadric surfaces Robustness

Research teams of the same theme :

Inria Headquarters and research centres

Direct links

Social