Description: In geometric modeling and more specifically in Computer Aided Geometric Design, parametric curves or surfaces based on bspline representations are playing an important role. They are the building blocks of many geometric operations such as offseting, blending, ... By composing such operations, new surfaces are produced which are in general easy to evaluate but which are not necessarily represented using bspline basis functions.

To describe complex shapes, additional operations such as intersection or trimming are usually performed on these models. This computation yields curves on the surfaces. Computing the arrangement of these curves yields the regions that should be kept in the description of the shape. The arrangement of curves and surfaces is a fundamental but delicate problem of geometric modeling. It consists in computing the connected components or regions cut out by curves on the surface or by surfaces in a given volume.

A typical problem is the analysis of regions defined by the self-intersection curve of an offset surface. An application that we will consider is the control of machine tools where the center of the tool is moving of a surface which is parallel at a given distance of the initial surface. The self-intersection curve of this offset surface defines regions which need to be analysed to determine the safe positions of the machining tool.

The main objective is to develop new methods to perform geometric computation on so called procedural surfaces represented as straight-line programs. In particular, we aim at efficient arrangement computation of curves defined by geometric constraints on these models. We assume that evaluation and derivatives up to some order are available at points of the surface.

The work contains three main components related to algorithmic, numeric and efficiency issues.

Regarding algorithmic issues, currently several techniques for computing with curves and surfaces assume that an explicit representation in a polynomial or a bspline basis is known. The first challenge is to develop new methods to compute with models for which only evaluation or some derivatives are available. One direction of investigation will be to combine this local information with subdivision techniques. We will consider in particular subdivision techniques for computing intersection curves or self-intersection curves of straight-line program surfaces. Techniques based on local tangential information will be studied for the treatment of singularities of these curves. The problem of computing the arrangement of such curves will be investigated along the same lines.

For the numeric aspect, we will consider with a special care the problem of certification of the computed results. This is critical in some applications such as for instance machining tool control. Methods based on interval or ball arithmetic and iterative methods such as Newton method using adapted convergence criteria will be investigated, including convergence criteria for singular solutions.

Finally the efficiency of the approach and its capacity to solve practical problems encountered in CAGD are issues that will be addressed. The potential improvement that can be gained from the use of GPU computation will be investigated in conjunction with the development of tuned algorithms exploiting the characteristics of CPU and GPU architectures.

Prerequisite: A good experience in geometric computation and a background in symbolic-numeric computation. Some expertise in software development (C, C++). An interest for practical applications in CAGD.

Period: October 2011 - October 2014.

Site: INRIA, team GALAAD, BP. 93, 06902 Sophia Antipolis, France. http://www-sop.inria.fr/galaad/

Contact: for application, send your CV to B. Mourrain ( This e-mail address is being protected from spambots. You need JavaScript enabled to view it )

Additional information: The work is related to the starting European project TERRIFIC. It will be done in close collaboration with the industrial partner MISSLER- TOPSOLID, producing CAGD software.