Scaffolding skeletons using spherical Voronoi diagrams: Feasibility, regularity and symmetry. (September 2018)

• Record Type: Journal Article
• Authors: Fuentes Suárez, A.J.; Hubert, E.
• Is Part Of: Computer aided design. Volume 102(2018)
• Page Start: 83
• Page End: 93
• Publication Date: 2018-09
• Subjects: Quad mesh generation -- Skeleton based modeling -- Procedural modeling -- Scaffold; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2018.04.016
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: Given a skeleton made of line segments we describe how to obtain a coarse quad mesh of a surface that encloses tightly the skeleton and follows its structure — the scaffold . We formalize as an Integer Linear Program the problem of constructing an optimal scaffold that minimizes the total number of quads on the mesh. We prove the feasibility of the Integer Linear Program for any skeleton. In particular we can generate these scaffolds for skeletons with cycles. We additionally show how to obtain regular scaffolds, i.e. with the same number of quad patches around each line segment, and symmetric scaffolds that respect the symmetries of the skeleton. An application to polygonization of skeleton-based implicit surfaces is also presented. Graphical abstract: Highlights: Algorithmic generation of a quad mesh around a skeleton. No restriction on the topology of the skeleton: it can include cycles. Optimization in the number of quads. Preservation of symmetries.