Keywords: free-form surfaces, CAD, FE mesh generation, mesh adaptation, edge collapse, mesh simplification.

Nowadays, polyhedrons are more and more used as a reference model in many applications: virtual environments, virtual reality, virtual prototyping, virtual assembly, design, simulation, etc. are more and more used and developed in the industry. These environments require polyhedral models obtained by a tessellation of objects resulting from CAD or laser scanning, etc. In order to meet the needs for handling easily and optimizing polyhedrons, some simplification methods of polyhedral models are necessary.

The subject addressed is based on a simplification approach of polyhedral models. The method used was developed for the adaptation of a mesh resulting from a patch independent triangulation process. This simplification technique is based on an algorithm of edge collapse at the purely topological level, at the opposite to the current ones, which embeds geometric criteria. Geometric criteria look after elements shapes to check the validity of an operation while topologic operators only care about the connections between nodes, edges and faces. The topologic approach proved its robustness because no floating-point operations are involved. Nevertheless, each topologic operator remains to be well defined to treat every configuration. The collapsing operator, which simply deletes an edge, is a good example of this complexity because the impact of connectivity is not reduced to the closed shell around the collapsed edge.

In this paper we summarize a patch independent meshing method, which takes benefit of the purely topological algorithm of edge collapse. The main topics for the method are:

• The description of an algorithm to relocate nodes in a patch independent method,
• The description of various possibilities for the edge collapse operator where an exhaustive list of cases is presented and discussed,
• The discussion of the interest of a purely topological edge collapse algorithm compared to a purely geometrical edge collapse algorithm,
• The presentation of various complex configurations for a purely topological edge collapse,
• The presentation of an algorithm for a purely topological edge collapse method.

1

P-J. Frey, P-L. George, "Maillages, applications aux éléments-finis", Hermès Science Publications, Paris, 1999.

2

L. Fine, "Processus et méthodes d'adaptation et d'idéalisation de modèles dz'ediés à l'analyse de structures mécaniques", PhD. Thesis, Institut National Polytechnique de Grenoble, 2001.

3

F. Noël, "Global parameterization of a topological surface defined as a collection of trimmed bi-parametric patches - application to automatic mesh construction", Int. J. for Num. Met. in Eng., Vol. 54, pp 965-986, 2002. doi:10.1002/nme.454

4

F. Noël, "Adaptation of cad surface meshes to a map of sizes through the Igatom concept", Int. J. for Num. Meth. in Eng., Vol. 49, pp 313-326, 2000. doi:10.1002/1097-0207(20000910/20)49:1/2<313::AID-NME935>3.0.CO;2-3

5

F. Noël, "Mailleur auto-adaptatif pour des surfaces gauches en vue de la conception intégrée", PhD Thesis, National Polytechnic Institute of Grenoble, 1994.

6

H. Hoppe. "New quadric metric for simplifying meshes with appearance attributes", In David Ebert, Markus Gross, and Bernd Hamann editors, IEEE Visualization-99, pp 59-67, November, 1999. doi:10.1109/VISUAL.1999.809869

7

H. Hoppe, T. DeRose, J. MacDonald, W. Stuetzle, "Mesh Optimization", Computer Graphics, ACM SIGGRAPH'93, pp 71-78, 1993.

8

H. Hoppe, "Progressive meshes.", Computer Graphics, ACM SIGGRAPH 96, pp 99-108, 1996.

9

J. Xia, A. Varshney, "Dynamic view-dependent simplification for polygonal models", IEEE Visualization '96 Proceedings, pp. 327-334, 1996. doi:10.1109/VISUAL.1996.568126

10

M. Bern, D. Eppstein, and S.-H. Teng, "Parallel construction of quadtrees and quality triangulations", In Proc. 3rd Workshop on Algorithms and Data Structures, Springer-Verlag, LNCS 709, pp 188-199, 1993.

11

M.W. Bern, D. Eppstein, S. Teng, "Parallel Construction of Quadtrees and Quality Triangulations", Int. J. Comput. Geometry Appl., Vol. 9, no6, pp 517-532, 1999. doi:10.1142/S0218195999000303

12

H. Samet, "The quadtree and related hierarchical data structures", Computing Surveys, Vol. 16, pp 188-260, 1984. doi:10.1145/356924.356930

13

H.J. Scheck, "The force density method for form finding and computation of general networks", Computer Methods in Applied Mechanics and Engineering. Vol 3, pp. 115-134, 1974. doi:10.1016/0045-7825(74)90045-0

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)