TitleSimpifications of Closed Triangulated Surfaces Using Simulated Annealing (In Book)
inMathematical Methods in CAGD: Oslo 2000
Author(s) Peer Timo Bremer, Bernd Hamann, Oliver Kreylos, F.-E. Wolter
Editor(s) T. Lyche, L. L. Schumaker
Year 2001
PublisherVanderbilt University Press
AddressNashville, Tennessee
Abstract We describe a method to approximate a closed surface tri- angulation using simulated annealing. Our approach guarantees that all vertices and triangles in an approximating surface triangulation are within a user-defined distance of the original surface triangulation. We introduce the idea of atomic envelopes to guarantee error bounds that are independent of the surface geometry. Atomic envelopes also allow approximation distance to be di erent for di erent parts of the surface. We start with the original triangulation and perturb it randomly and improve an approximating triangulation by locally changing the triangulation, using a simulated annealing algorithm. Our algorithm is not restricted to using only original vertices; the algorithm considers every point inside the envelope triangulation as a possible position. The algorithm attempts to minimize the total number of vertices needed to approximate the original surface triangulation within the prescribed error bound.