PhD fellowship - Effective computational geometry
Sylvain Petitjean
Sylvain.Petitjean at loria.fr
Wed Jun 16 19:31:46 PDT 2004
(Please pass to interested parties.)
Applications are invited for a PhD fellowship in the field of effective
computational geometry and geometric computing. The PhD topic is on
robust and
efficient calculation of arrangements of quadrics (degree 2 surfaces) --
see below
for more details.
Research will take place at the LORIA laboratory, Nancy, France, in the ISA
project-team (Models, algorithms and geometry for computer graphics and
artificial
vision). See the web pages for further info: http://www.loria.fr and
http://www.loria.fr/isa
The PhD grant is slightly above 1300 euros per month over 36 months. The
thesis is
scheduled to start in October 2004.
The ideal candidate will have working knowledge of computational
geometry and a
solid background in mathematics.
The exact conditions to be allowed to apply for this fellowship are
stated on the
following page (in French):
http://dr.education.fr/Alloc_doc/alloc_2.html
Roughly: to be under 25, to have or be about to have a Master's degree,
to be a
citizen of a member state of the European Union. There are also special
conditions
for citizens of Bulgaria, Russia, Iceland, Norway, Roumania, Switzerland and
Turkey, so feel free to send e-mail to enquire.
To apply, please send a fairly complete vitae by e-mail to
Sylvain.Petitjean at loria.fr
The schedule is very tight: deadline for application is set to July 5th,
2004.
Contact person:
Sylvain Petitjean
LORIA
Campus scientifique
BP 239
54506 Vandoeuvre cedex
FRANCE
-----------------
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 (but see [1,2,3]). A major reason is
that outside
the linear realm exact arithmetic computations require algebraic numbers
which
cannot in general be represented 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 PhD 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 [4,5]. 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 doctoral
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] E. Schömer and N. Wolpert, An Exact and Efficient Approach for
Computing a
Cell in an Arrangement of Quadrics, Computational Geometry: Theory and
Applications, 2004.
[3] B. Mourrain, J.-P. Técourt and Monique Teillaud, Predicates for the
Sweeping
of an Arrangement of Quadrics in 3D, Computational Geometry: Theory and
Applications, 2004.
[4] 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, 2003.
[5] S. Lazard, L. M. Peñaranda and S. Petitjean, Intersecting Quadrics: An
Efficient and Exact Implementation, Proc. of the ACM Symposium on
Computational
Geometry, 2004
--
- 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.
More information about the Compgeom-announce
mailing list