Postdoc position at INRIA (France)

[Sylvain Petitjean]

In 2003, INRIA, the French national institute for research in computer
science and control, will be recruiting approximately 70 post-doctorates,
23 of whom will be part of a recruitment program which deadline is April
15, 2003. The other 50 will be recruited over the course of time.  For more
information and a list of proposed postdoctoral topics, please consult:

http://www.inria.fr/travailler/opportunites/postdoc.en.html

You can also contact  a research team whose work is of interest	to you and
propose a research program.


We, the geometric computing group at INRIA Lorraine (Nancy), one of the
research units of the institute, proposed a postdoctoral subject on the
efficient and robust computation of arrangements of quadrics (see below).

If you recently obtained your PhD and are interested in working as a
postdoc on this topic, please contact

  Sylvain Lazard (lazard at loria.fr) and Sylvain Petitjean (petitjea at loria.fr) 

(Please distribute to interested parties.)

-------

Efficient and Robust Computation of Arrangements of Quadrics
------------------------------------------------------------

The two most widely used types of object representation in solid modeling
are constructive solid geometry (CSG) and boundary representation
(BRep). Both representations having their own respective advantages, solid
modeling kernels often need an efficient and reliable way to convert one
type of representation into the other. CSG-to-BRep conversion is a well
understood problem, but past approaches have often put more emphasis on
efficiency than on robustness and accuracy. If only finite-precision
arithmetic is assumed, the topological consistency of the compute BRep can
easily be jeopardized by small amounts of error introduced in the data. For
many applications in design and automated manufacturing, this may be
unacceptable.

Designing reliable and robust algorithms is currently a major interest of
the computational geometry and geometric computing research communities. A
number of successful approaches have been proposed for the robust and
accurate CSG-to-BRep conversion of polyhedral models. Computing the
topological structure of a BRep involves accurately evaluating signs of
arithmetic expressions, which can be achieved for piecewise-linear models
assuming the necessary bit length is allowed for number representation.

By contrast, there has been much less work on robust CSG-to-BRep conversion
algorithms for curved primitives (with the notable exception of [1]). A
major reason is that outside the linear realm exact arithmetic computations
require algebraic numbers which cannot in general be representated
explicitly with a finite number of bits. In addition, computation with
algebraic numbers is extremely slow.

In the algebraic domain, the most simple surfaces, outside piecewise-linear
meshes, are degree 2 surfaces, i.e. quadrics. Quadrics represent a fairly
good compromise between complexity, flexibility and modeling power. With
respect to the CSG-to-BRep conversion problem, and more generally to the
computation of arrangements of quadrics, they also have undeniable
advantages. Indeed, the quadratic nature of their defining equations
permits an explicit representation of intersection curves. Thus, it is
theoretically possible to compute a fully parametric representation of the
boundary of second-order CSG solids.

The goal of this postdoc is to make strides towards this goal. Recently, we
have proposed and implemented a robust algorithm for the near-optimal
parameterization of the intersection of two quadrics [2]. The complexity of
the output is minimal in terms of the number and depth of the radicals
involved. Using this algorithm (and the accompanying theoretical results)
as a building block, the postdoctoral candidate will propose solutions for
the robust and efficient computation of arrangements of quadrics. Depending
on his/her background, he/she will focus more specifically on one or
several of the many different aspects of the problem: handling degenerate
cases, mixing finite-precision and exact arithmetic, ensuring the
geometrical-topological consistency, using filters, designing proper
geometric predicates, managing complexity, solving polynomial equations
with algebraic coefficients, sorting algebraic points along a curve, ...

[1] J. Keyser, S. Krishnan and D. Manocha, Efficient and Accurate BRep
Generation of Low Degree Sculptured Solids Using Exact Arithmetic, Computer
Aided Geometric Design, 16 (9), 1999.

[2] L. Dupont, D. Lazard, S. Lazard and S. Petitjean, Near-Optimal
Parameterization of the Intersection of Quadrics, Proc. of the ACM
Symposium on Computational Geometry (SoCG), 2003, to appear.


-- 
	- Sylvain



-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.