# 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.

#### Extracted Text

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.c.v

c.t

c. n

c.p

c.s

c.o

c.l

c.r

v.c

t. cvertex 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 tco.

c.l c.s7, cr7

t

Ocp cen

c.0Figure 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. [1998], 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

## Upcoming Pages

Here’s what’s next.

## Search Inside

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.