Selecting Independent Chains on a Triangulated 2-Manifold.
Siu-Wing Cheng, Sheung-Hung Poon · 2000
We prove that there exists linearly many independent edge chains of length k in a connected orientable triangulated 2-manifold (possibly with boundary) of genus zero, for any positive integer parameter k. Such an independent set of chains can be identified by a simple linear-time algorithm. Our motivation is to simplify a surface by repeatedly contracting a large set of independent chains. Preliminary experimental verification of the effectiveness of this approach in surface simplification has been conducted. 1 Introduction Many graphics softwares, animation applications, computer games and virtual reality applications nowadays use 3D object models extensively. Realistic models often have high complexity, which slow down computation and rendering in applications. Sometimes, not all details are needed, for example, when the object is far away. Therefore, providing levels of details of a model will speed up its manipulation when the resolution needed is low. Our motivation is to combi...