Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Restricted mesh simplification using edge contractions

In English

Författare

Summary, in English

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 2-step 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 2-step 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 2-step removable. In order to provide the option to remove such vertices, we also define and examine k-step removals. This increases the lower bound on the number of removable vertices.

Avdelning/ar

  • Computer Science

Publiceringsår

2009

Språk

Engelska

Sidor

247-265

Publikation/Tidskrift/Serie

International Journal of Computational Geometry and Applications

Volym

19

Issue

3

Dokumenttyp

Artikel i tidskrift

Förlag

World Scientific Publishing

Ämne

  • Computer Science

Nyckelord

  • edge contractions
  • Computational geometry
  • computer graphics

Status

Published

Projekt

  • VR 2008-4649

ISBN/ISSN/Övrigt

  • ISSN: 0218-1959