Please use this identifier to cite or link to this item:

Maintaining deforming surface meshes

Authors Cheng, S.W. View this author's profile
Dey, T.K.
Issue Date 2008
Source Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms , 2008, p. 112-121
Summary We present a method to maintain a mesh approximating a deforming surface, which is specified by a dense set of sample points. We identify a reasonable motion model for which a provably good surface mesh can be maintained. Our algorithm determines the appropriate times at which the mesh is updated to maintain a good approximation. The updates use simple primitives, and no costly computation such as line-surface intersection is necessary. Point insertions and deletions are allowed at the updates. Each update takes time linear in the size of the current sample set plus the new sample points inserted. We also construct examples for which, under the same model, no other algorithm makes asymptotically fewer changes to the mesh than our algorithm.
ISBN 978-0-898716-47-4
Rights © ACM, 2008. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, p. 112-121.
Language English
Format Conference paper
Access View full-text via Scopus
View full-text via Web of Science
Files in this item:
File Description Size Format
soda.pdf 216991 B Adobe PDF