Supervisors: Pierre Alliez (TITANE) and Laurent Busé (GALAAD)
NURBS (Non-Uniform Rational Basis Spline) is a mathematical model that has become a standard in the modeling community for generating and representing curves and surfaces. It offers flexibility, precision and intuitive human interaction through control points [1]. NURBS surfaces are nowadays widely used in computer graphics, computer-aided design, manufacturing and engineering. Nevertheless, for some specific applications such as computational engineering or real-time rendering, the NURBS surfaces must be converted into isotropic triangle surface meshes. Such conversion is still a scientific challenge and current mesh generators suffer from a lack of control on the shape and size of the mesh elements, as well as of topological guarantees. The goal of this internship is to devise a reliable algorithm for meshing NURBS surfaces, within the generic meshing framework of the CGAL library [2]. Some experiments and comparisons with the Workbench software from Ansys will be carried out.
In order to control the quality of the output surface triangle mesh, notably in terms of shape and size of the triangles, we will investigate an approach based on Delaunay refinement that uses the notion of restricted Delaunay triangulations. This approach consists of sampling a point set on the NURBS surface to initialize the restricted Delaunay triangulation, then refining it until all mesh elements meet some user-specified criteria [2]. The refinement process inserts new points that are computed as intersections between the NURBS surface and line segments that are dual Voronoi edges of Delaunay triangles.
The first objective is to devise a reliable and efficient line/NURBS intersection oracle. For this purpose, we will investigate a new matrix-based representation of NURBS surfaces relying upon recent advances on algebraic techniques for eliminating variables in polynomial systems [3]. This representation, adapted to trimmed NURBS, i.e., NURBS that contain holes, gives the ability to compute intersections by means of state-of-the-art methods in numerical linear algebra (matrix kernel, singular value decompo- sition, eigen-computation). The second objective is to specialize the initialization of the mesh generation process to NURBS surfaces. The third objective, more prospective, is to assess the common defect of NURBS surfaces (e.g., cracks, islands, self-intersections) in order to devise an algorithm with resilience to defect-laden inputs.
References
1 L. Piegl and W. Tiller, The NURBS book. Springer, Monographs in Visual Communication, 2nd edition, 1997.
2 C. Jamin, P. Alliez, M. Yvinec and J.-D. Boissonnat. CGALmesh: a Generic Framework for Delaunay Mesh Generation. Inria Technical report 8256. Available at http://hal.inria.fr/ hal-00796052/en/.
3 L. Busé, Implicit matrix representations of rational B ́ezier curves and surfaces. To appear in Computer-Aided Design, preprint available at http://hal.inria.fr/hal-00847802/en/.
