Header

UZH-Logo

Maintenance Infos

Hierarchyless simplification, stripification and compression of triangulated two-manifolds - Zurich Open Repository and Archive


Diaz-Gutierrez, P; Gopi, M; Pajarola, R (2005). Hierarchyless simplification, stripification and compression of triangulated two-manifolds. Computer Graphics Forum, 24(3):457-467.

Abstract

In this paper we explore the algorithmic space in which stripification, simplification and geometric compression of
triangulated 2-manifolds overlap. Edge-collapse/uncollapse based geometric simplification algorithms develop a
hierarchy of collapses such that during uncollapse the reverse order has to be maintained. We show that restricting
the simplification and refinement operations only to, what we call, the collapsible edges creates hierarchyless
simplification in which the operations on one edge can be performed independent of those on another. Although
only a restricted set of edges is used for simplification operations, we prove topological results to show that, with
minor retriangulation, any triangulated 2-manifold can be reduced to either a single vertex or a single edge using
the hierarchyless simplification, resulting in extreme simplification.
The set of collapsible edges helps us analyze and relate the similarities between simplification, stripification and
geometric compression algorithms. We show that the maximal set of collapsible edges implicitly describes a triangle
strip representation of the original model. Further, these strips can be effortlessly maintained on multiresolution
models obtained through any sequence of hierarchyless simplifications on these collapsible edges. Due
to natural relationship between stripification and geometric compression, these multi-resolution models can also be efficiently compressed using traditional compression algorithms.
We present algorithms to find the maximal set of collapsible edges and to reorganize these edges to get the minimum number of connected components of these edges. An order-independent simplification and refinement of these
edges is achieved by our novel data structure and we show the results of our implementation of view-dependent,
dynamic, hierarchyless simplification. We maintain a single triangle strip across all multi-resolution models created
by the view-dependent simplification process. We present a new algorithm to compress the models using the
triangle strips implicitly defined by the collapsible edges.

Abstract

In this paper we explore the algorithmic space in which stripification, simplification and geometric compression of
triangulated 2-manifolds overlap. Edge-collapse/uncollapse based geometric simplification algorithms develop a
hierarchy of collapses such that during uncollapse the reverse order has to be maintained. We show that restricting
the simplification and refinement operations only to, what we call, the collapsible edges creates hierarchyless
simplification in which the operations on one edge can be performed independent of those on another. Although
only a restricted set of edges is used for simplification operations, we prove topological results to show that, with
minor retriangulation, any triangulated 2-manifold can be reduced to either a single vertex or a single edge using
the hierarchyless simplification, resulting in extreme simplification.
The set of collapsible edges helps us analyze and relate the similarities between simplification, stripification and
geometric compression algorithms. We show that the maximal set of collapsible edges implicitly describes a triangle
strip representation of the original model. Further, these strips can be effortlessly maintained on multiresolution
models obtained through any sequence of hierarchyless simplifications on these collapsible edges. Due
to natural relationship between stripification and geometric compression, these multi-resolution models can also be efficiently compressed using traditional compression algorithms.
We present algorithms to find the maximal set of collapsible edges and to reorganize these edges to get the minimum number of connected components of these edges. An order-independent simplification and refinement of these
edges is achieved by our novel data structure and we show the results of our implementation of view-dependent,
dynamic, hierarchyless simplification. We maintain a single triangle strip across all multi-resolution models created
by the view-dependent simplification process. We present a new algorithm to compress the models using the
triangle strips implicitly defined by the collapsible edges.

Statistics

Citations

5 citations in Web of Science®
8 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

1 download since deposited on 24 Mar 2011
0 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Date:2005
Deposited On:24 Mar 2011 15:45
Last Modified:05 Apr 2016 14:53
Publisher:Wiley-Blackwell
ISSN:0167-7055
Publisher DOI:https://doi.org/10.1111/j.1467-8659.2005.00871.x

Download

Preview Icon on Download
Filetype: PDF - Registered users only
Size: 5MB
View at publisher

TrendTerms

TrendTerms displays relevant terms of the abstract of this publication and related documents on a map. The terms and their relations were extracted from ZORA using word statistics. Their timelines are taken from ZORA as well. The bubble size of a term is proportional to the number of documents where the term occurs. Red, orange, yellow and green colors are used for terms that occur in the current document; red indicates high interlinkedness of a term with other terms, orange, yellow and green decreasing interlinkedness. Blue is used for terms that have a relation with the terms in this document, but occur in other documents.
You can navigate and zoom the map. Mouse-hovering a term displays its timeline, clicking it yields the associated documents.

Author Collaborations