Paper Info
Title
Quadrilateral and tetrahedral mesh stripification using 2-factor partitioning of the dual graph
Abstract
Finding a 2-factor of a generic graph is a difficult problem and there are randomized algorithms proposed to solve this problem in O(n3) complexity (12). In this paper, we propose algorithms that find a 2-factor of a graph, if one exists, for a restricted class of graphs in which all vertices have degree four or less, in O(n2) complexity where n is the number of vertices of the graph. Such graphs are ac- tually dual graphs of quadrilateral and tetrahedral meshes that are widely used in graphics and visualization applications. We use the 2-factor of these graphs to find linear ordering of the primitives in the form of strips. Applications like compression, access and ren- dering of such data benefits a lot from such linear ordering. We use the similarity between the dual graphs of the quadrilateral and tetra- hedral meshes to introduce a novel, unified graph based algorithm to produce quad and tetrahedral strip representations respectively. Further, by introducing a few additional vertices, we can represent the entire quad-surface using a single quad-strip loop. We can use a similar technique to reduce the number of tetrahedral strips, to represent the entire tetrahedral mesh. CR Categories: I.3.5 (Computer Graphics): Geometric Algorithms—Quadrangulation, Tetrahedraliztion, Stripification; K.7.m (Graph Algorithms): k-factor—Perfect Matching, 2-factor; Figure 1: A cube and its dual graph. A 2-factor of the graph is a 2- regular spanning graph. Two possible 2-factors of the dual graph are shown. They define disjoint quadrilateral strip cycles on a manifold quadrangulation. Note that the edges that belong to the complement of 2-factor also define disjoint cycles in the dual of a quadrangulated manifold. by (21). In this context, there are also works on creating triangle strips specifically from a quadrilateral meshes (18, 20). In this paper, given a quad or tetrahedral mesh, we propose a graph based algorithm that performs a global analysis of the mesh to find quad and tetra strips. This algorithm takes advantage of the similarity in the dual graph structures of quad and tetrahedral meshes and presents a unified solution for the problem in meshes with either of these primitives. Our work is closely related to the triangle strip generation algorithm by Gopi and Eppstein (6) that finds strips using the 1-factor in the dual graph of a manifold trian- gulated mesh. We use the 2-factor in the dual graph of tetrahedral meshes and manifold quadrilateral meshes.
Year
DOI
Venue
2005
10.1007/s00371-005-0336-9
The Visual Computer
Keywords
Field
DocType
quadrilateral strips,2-factor,graph algorithms.,single-strip,tetrahedral strips,weighted perfect matching,generic algorithm,factor graph,randomized algorithm,computer graphic,linear order,global analysis
Geometric graph theory,Discrete mathematics,Mathematical optimization,Outerplanar graph,Combinatorics,Line graph,Dual graph,Symmetric graph,Lattice graph,Voltage graph,Mathematics,Complement graph
Journal
Volume
Issue
ISSN
21
8-10
1432-2315
Citations 
PageRank 
References 
4
0.43
17
Authors
2
Name
Order
Citations
PageRank
Pablo Diaz-gutierrez1514.54
M. Gopi2694.10