Header

UZH-Logo

Maintenance Infos

Hierarchyless simplification, stripification and compression of triangulated two-manifolds


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

Dimensions.ai Metrics
6 citations in Web of Science®
10 citations in Scopus®
10 citations in Microsoft Academic
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:19 Feb 2018 20:03
Publisher:Wiley-Blackwell
ISSN:0167-7055
OA Status:Closed
Publisher DOI:https://doi.org/10.1111/j.1467-8659.2005.00871.x

Download