LR: Compact connectivity representation for triangle meshes Page: 4 of 10
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to Digital Library by the UNT Libraries Government Documents Department.
The following text was automatically extracted from the image on this page using optical character recognition software:
Ring-based ordering: We build a nearly-Hamiltonian cycle of pri-
mal mesh edges that we call the ring. It divides the mesh in two
parts (Fig. 1) that form triangle strip corridors with bifurcations. To
reduce storage, we classify triangles by the number of edges they
have on the ring (bifurcation To, normal T1, dead-end T2). We
store the ring vertices and the T1 and T2 triangles in the order in
which they are visited by the ring. The isolated vertices not part
of the ring are stored last. The To triangles are stored using the
standard CT data structure.
Omitted V entries for T1 and T2 triangles: Most triangles are
of type T1 or T2. Two of their vertex references (V entries of the
CT) are defined implicitly and need not be stored. Thus, we store
two references, L [v] and R[v], per ring vertex and assume that tri-
angle 2v has vertices (n, L[v], v.n) and triangle 2n+ 1 has vertices
(v.n, R[v], v), where v.n - (v + 1) mod mr is the next vertex af-
ter v on the ring, and where mr denotes the number of ring vertices.
Although this data structure has two entries for each T2 triangle, the
cost of this redundancy is amortized, because typically there are far
fewer T2 than T1 triangles.
Omitted O entries for cheap T1 and T2 triangles: We do not
store O table entries for the "cheap" T1 and T2 triangles that are
not adjacent to a To, because we can access the opposite corners
directly from neighboring ring vertices in constant time.
RING-EXPANDER construction of the ring: We propose a simple
(linear time and space) greedy approach for computing a ring that,
in all tested cases, either produces a Hamiltonian cycle or leaves a
small proportion of isolated vertices. Our RING-EXPANDER algo-
rithm tends to minimize the number of To and T2 triangles.
Wart skipping: To further reduce storage, we conceptually modify
the ring to exclude warts T2 triangles adjacent to To triangles
which allows the expensive To triangles adjacent to warts to be rep-
resented as cheap T1 triangles (Fig. 1).
Short offsets: When differences L [v] - v and R [v] - v are suf-
ficiently small, we choose to store L[v] and R[v] as short 2-byte
relative offsets. We provide a compact data structure for accommo-
dating exceptions, when the offset is too large.
HYBRID-RING-EXPANDER for increased locality: For large
meshes, LR provides the option of either minimizing the number
of references or the number of bits stored. For the latter option, we
provide a modified RING-EXPANDER that attempts to reduce the
average magnitude of offsets.
2 Terminology and Notation
We assume a mesh with m vertices and n triangles. The vertices,
which are numbered between 0 and m - 1, are stored in a geom-
etry table (array of points). The connectivity captures: (1) trian-
gle/vertex incidence, (2) its reverse (star), (3) triangle/triangle and
vertex/vertex adjacency (access to neighbors), and (4) ordering of
vertices around triangles and of triangles around vertices.
Numerous data structures have been proposed for connectivity so
as to support constant-time operators for traversing the mesh from
one element (triangle or vertex) to adjacent ones in an orderly man-
ner [Guibas and Stolfi 1985; Brisson 1989; Rossignac 1994].
When conventional data structures are used, the storage cost of the
connectivity exceeds the storage cost of the geometry. Indeed, the
triangle/vertex incidence alone amounts to 3 rpt and thus requires
twice the storage of geometry, because in a manifold mesh with
relatively low genus the number of triangles is roughly 2m. Popu-
lar data structures use several additional references per triangle to
encode adjacency, order, and other connectivity relationships.
vertex of corner c
triangle of corner c
next corner around c.t
previous corner around c.t
next corner around c.v
corner opposite of c
left neighbor c.n.o of c
right neighbor c.p.o of c
a corner of vertex v
a corner of triangle t
c.l c.s7, cr7
Figure 2: Standard set of corner operators.
2.1 Corner Table
We present our work in terms of corners [Rossignac 2001], which
each associate a triangle with a bounding vertex. To facilitate com-
parison with prior art that manipulates half-edges (also called edge-
uses or directed-edges) [Mantyla 1988; Campagna et al. 1998], we
observe that each half-edge h corresponds to a unique facing cor-
ner c and that the next and opposite half-edge operators, h.n and
h.o, map to equivalent corner operators c.n and c.o.
Fig. 2 shows the standard corner operators. Although corner and
vertex references are stored in the LR data structure as integers, we
use an object-oriented notation that interprets the operator based
on the type of the operand. For example, if c is a corner, c.n.v.n.c
means: start with c, go to the next corner c.n around the triangle c.t,
obtain the reference c.n.v to its vertex, go to the next vertex c.n.v.n
around the ring, and retrieve a corner c.n.v.n.c of that vertex.
3 Prior Art
A customization of the popular Winged-Edge (WE) data struc-
ture [Baumgart 1972] to triangles stores connectivity using 3 ref-
erences for each half-edge h: to its starting vertex h.v, to the oppo-
site half-edge h.o, and to the next half-edge h.n around the same
triangle, resulting in a total of 9 rpt.
As suggested by Campagna et al. , the Corner Table (CT)
data structure [Rossignac 2001] sorts the half-edge entries so that
the three entries of a triangle are consecutive and listed in clockwise
order (with respect to the outward pointing normal). This makes
storing c.n unnecessary, since it can be derived trivially using mod-
ular arithmetic. Hence, CT stores only two references per corner c:
its vertex c.v and its opposite corner c.o; see Fig. 2. CT uses two
arrays V and O of integers so that c.v = V[c] and c.o = O[c].
WE and CT do not store any vertex-to-triangle references. One may
add these by storing, for each vertex v, a reference v.c = C[v] to
one of its corners in the C table. Since there are three corners (and
half-edges) per triangle and about twice as many triangles as ver-
tices, with this addition, WE stores 9.5 rpt, while CT stores 6.5 rpt.
The mesh connectivity is completely captured in the V array of per-
triangle vertex references and may be compressed to less than two
bits per triangle [Rossignac 1999; Khodakovsky et al. 2002]. How-
ever, compressed formats produced through sequential encoding
cannot be used for random access mesh traversal, and V alone does
not provide constant-time access to neighboring elements. Some
formats support local decompression [Yoon and Lindstrom 2007;
Courbet and Hudelot 2009], but restrict the access pattern to a hier-
archical or contiguous traversal and execute a complex decompres-
sion code each time a new portion of the mesh is accessed.
Castelli-Aleardi et al. [2006b] prove that a succinct representation
of the connectivity of planar triangulations of n triangles can be
Here’s what’s next.
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Gurung, T; Luffel, M; Lindstrom, P & Rossignac, J. LR: Compact connectivity representation for triangle meshes, article, January 28, 2011; Livermore, California. (https://digital.library.unt.edu/ark:/67531/metadc830751/m1/4/: accessed June 25, 2019), University of North Texas Libraries, Digital Library, https://digital.library.unt.edu; crediting UNT Libraries Government Documents Department.