Restricted mesh simplification using edge contractions
(2009) In International Journal of Computational Geometry and Applications 19(3). p.247265 Abstract
 We consider the problem of simplifying a planar triangle mesh using edge contractions, under the restriction that the resulting vertices must be a subset of the input set. That is, contraction of an edge must be made on to one of its adjacent vertices, which results in removing the other adjacent vertex. We show that if the perimeter of the mesh consists of at most five vertices, then we can always find a vertex not on the perimeter which can be removed in this way. If the perimeter consists of more than five vertices such a vertex may not exist. In order to maintain a higher number of removable vertices under the above restriction, we study edge flips which can be performed in a visually smooth way. A removal of a vertex which is preceded... (More)
 We consider the problem of simplifying a planar triangle mesh using edge contractions, under the restriction that the resulting vertices must be a subset of the input set. That is, contraction of an edge must be made on to one of its adjacent vertices, which results in removing the other adjacent vertex. We show that if the perimeter of the mesh consists of at most five vertices, then we can always find a vertex not on the perimeter which can be removed in this way. If the perimeter consists of more than five vertices such a vertex may not exist. In order to maintain a higher number of removable vertices under the above restriction, we study edge flips which can be performed in a visually smooth way. A removal of a vertex which is preceded by one such smooth operation is called a 2step removal. Moreover, we introduce the possibility that the user defines "important" vertices (or edges) which have to remain intact. Given m such important vertices, or edges, we show that a simplification hierarchy of size O(n) and depth O(log(n/m))can be constructed by 2step removals in O(n) time, such that the simplified graph contains the m important vertices and edges, and at most O(m) other vertices from the input graph. In some triangulations, many vertices may not even be 2step removable. In order to provide the option to remove such vertices, we also define and examine kstep removals. This increases the lower bound on the number of removable vertices. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1463174
 author
 Andersson, Mattias ^{LU} ; Gudmundsson, Joachim and Levcopoulos, Christos ^{LU}
 organization
 publishing date
 2009
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 edge contractions, Computational geometry, computer graphics
 in
 International Journal of Computational Geometry and Applications
 volume
 19
 issue
 3
 pages
 247  265
 publisher
 World Scientific
 external identifiers

 wos:000267510600004
 scopus:68049144811
 ISSN
 02181959
 DOI
 10.1142/S0218195909002940
 project
 VR 20084649
 language
 English
 LU publication?
 yes
 id
 f6883800e7754f11991b15d18d04aea7 (old id 1463174)
 date added to LUP
 20090818 14:24:34
 date last changed
 20170101 05:21:06
@article{f6883800e7754f11991b15d18d04aea7, abstract = {We consider the problem of simplifying a planar triangle mesh using edge contractions, under the restriction that the resulting vertices must be a subset of the input set. That is, contraction of an edge must be made on to one of its adjacent vertices, which results in removing the other adjacent vertex. We show that if the perimeter of the mesh consists of at most five vertices, then we can always find a vertex not on the perimeter which can be removed in this way. If the perimeter consists of more than five vertices such a vertex may not exist. In order to maintain a higher number of removable vertices under the above restriction, we study edge flips which can be performed in a visually smooth way. A removal of a vertex which is preceded by one such smooth operation is called a 2step removal. Moreover, we introduce the possibility that the user defines "important" vertices (or edges) which have to remain intact. Given m such important vertices, or edges, we show that a simplification hierarchy of size O(n) and depth O(log(n/m))can be constructed by 2step removals in O(n) time, such that the simplified graph contains the m important vertices and edges, and at most O(m) other vertices from the input graph. In some triangulations, many vertices may not even be 2step removable. In order to provide the option to remove such vertices, we also define and examine kstep removals. This increases the lower bound on the number of removable vertices.}, author = {Andersson, Mattias and Gudmundsson, Joachim and Levcopoulos, Christos}, issn = {02181959}, keyword = {edge contractions,Computational geometry,computer graphics}, language = {eng}, number = {3}, pages = {247265}, publisher = {World Scientific}, series = {International Journal of Computational Geometry and Applications}, title = {Restricted mesh simplification using edge contractions}, url = {http://dx.doi.org/10.1142/S0218195909002940}, volume = {19}, year = {2009}, }