Tesis programa Software

Tesi: APROXIMACIÓ FACETADA DE SUPERF%CDCIES PARAMÈTRIQUES RELATTADES

Doctorant:
Director/s: Pere Brunet i Núria Pla
Data de defensa: 30/11/1998
Programa: software
Tribunal:

President: Alvar Vinacua

Secretari: Robert joan-Arinyo

Vocals: Manuel Abellanas, Gabriel Bugeda, Hans-Peter Seidel
Resum:
First, a summary of the models used in Computer Graphics to model solids and to describe curves and surfaces is presented. Special emphasis is done on the case of the models used in the thesis, i.e. boundary representations able for modelling closed solids and trimmed surfaces. Input data is stored as a B-rep of a closed solid with non-planar faces. Edges of the solid are Bézier curves which trim the surfaces, represented as parametric Bézier patches.
Second, a review of previous methods that solve the problem of triangulating parametric surfaces is included, and areas where triangulations are used in the scope of ComputeGraphics are identified. The requirements of these areas leads to the aim of the thesis, which is to study algorithms to triangulate the surface of a solid such that the triangulation must be admissible (i.e., the distance to the original surface must not exceed a given tolerance), conformal (without cracks between neighbour triangles) and adaptive to the curvature, and the number of resulting triangles must be minimized. A secondary requirement is that triangles must be as well shaped as possible.
Third, the algorithmic scheme which ensures our requirements, the solid model used and the main data structure are presented. Two preprocesses of the input data are developed, a first one that converts degenerate triangular patches into trimmed patches, and a second one that reparameterizes the patches trying to improve the correspondence between parametric and image spaces, and therefore improving the shape of the resulting triangles.
Fourth, the isotropic algorithm is developed. This is a new algorithm to triangulate a solid bounded by trimmed surfaces. Bounds for the length of the resulting edges are obtained that depend on the curvature in each parametric point, therefore the resulting algorithm is adaptive. The kernel of the algorithm is the refining edges method, which inserts points on the interior of a face until an admissible triangulation is obtained.
Fifth, the directional algorithm is presented. This is a second new method proposed to obtain a triangulation of a closed set of trimmed patches that takes into account the parametric directions, in such a way that the edges of the resulting triangulation are aligned according to curvature directions. This requires obtaining new bounds and adapting the steps of the isotropic algorithm to work with directional information.
Finally, the results, conclusions and future research are presented. A set of test cases is described, and several comparisons of the resulting triangulations applying both algorithms and preprocessing steps are done. A shape improving postprocess which works in image space is also developed to show that the minimum angles can be improved in some cases.
An appendix of the thesis presents an incremental algorithm to obtain a constrained Delaunay triangulation (CDT) of a generic graph, which has been developed to be used by the isotropic and directional algorithms. The appendix also includes two generalizations of the CDT algorithm that work with elliptical distances or even with different directional information associated to each point of the plane.
First, a summary of the models used in Computer Graphics to model solids and to describe curves and surfaces is presented. Special emphasis is done on the case of the models used in the thesis, i.e. boundary representations able for modelling closed solids and trimmed surfaces. Input data is stored as a B-rep of a closed solid with non-planar faces. Edges of the solid are Bézier curves which trim the surfaces, represented as parametric Bézier patches.
Second, a review of previous methods that solve the problem of triangulating parametric surfaces is included, and areas where triangulations are used in the scope of Computer Graphics are identified. The requirements of these areas leads to the aim of the thesis, which is to study algorithms to triangulate the surface of a solid such that the triangulation must be admissible (i.e., the distance to the original surface must not exceed a given tolerance), conformal (without cracks between neighbour triangles) and adaptive to the curvature, and the number of resulting triangles must be minimized. A secondary requirement is that triangles must be as well shaped as possible.
Third, the algorithmic scheme which ensures our requirements, the solid model used and the main data structure are presented. Two preprocesses of the input data are developed, a first one that converts degenerate triangular patches into trimmed patches, and a second one that reparameterizes the patches trying to improve the correspondence between parametric and image spaces, and therefore improving the shape of the resulting triangles.
Fourth, the isotropic algorithm is developed. This is a new algorithm to triangulate a solid bounded by trimmed surfaces. Bounds for the length of the resulting edges are obtained that depend on the curvature in each parametric point, therefore the resulting algorithm is adaptive. The kernel of the algorithm is the refining edges method, which inserts points on the interior of a face until an admissible triangulation is obtained.
Fifth, the directional algorithm is presented. This is a second new method proposed to obtain a triangulation of a closed set of trimmed patches that takes into account the parametric directions, in such a way that the edges of the resulting triangulation are aligned according to curvature directions. This requires obtaining new bounds and adapting the steps of the isotropic algorithm to work with directional information.
Finally, the results, conclusions and future research are presented. A set of test cases is described, and several comparisons of the resulting triangulations applying both algorithms and preprocessing steps are done. A shape improving postprocess which works in image space is also developed to show that the minimum angles can be improved in some cases.
An appendix of the thesis presents an incremental algorithm to obtain a constrained Delaunay triangulation (CDT) of a generic graph, which has been developed to be used by the isotropic and directional algorithms. The appendix also includes two generalizations of the CDT algorithm that work with elliptical distances or even with different directional information associated to each point of the plane.

Link: http://www.lsi.upc.es/~marc

Darrera modificació:26-Jun-2003

Informació General | Programa de software | Programa d'Intel·ligència Artificial (en anglès)
Admissió | Beques i ajuts | Informació pels estudiants dels programes

Dept. Llenguatges i Sistemes Informàtics - Universitat Politècnica de Catalunya
c/ Jordi Girona, 31
08034 Barcelona
Tel. : 93 413 xxxx. Fax: 93 413 78 33

¨ 2000 - Copyright Dept. Llenguatges i Sistemes Informàtics