A new Voronoi-based surface reconstruction algorithm
Nina Amenta, Marshall W. Bern, Manolis Kamvysselis · ACM SIGGRAPH Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH) · 1998
We describe our experience with a new algorithm for the reconstruction of surfaces from unorganized sample points in IR 3 .The al- gorithm is the first for this problem with provable guarantees.Given a "good sample" from a smooth surface, the output is guaranteed to be topologically correct and convergent to the original surface as the sampling density increases.The definition of a good sample is itself interesting: the required sampling density varies locally, rigorously capturing the intuitive notion that featureless areas can be reconstructed from fewer samples.The output mesh interpolates, rather than approximates, the input points.Our algorithm is based on the three-dimensional Voronoi diagram.Given a good program for this fundamental subroutine, the algorithm is quite easy to implement.
Cited by 901 works. doi:10.1145/280814.280947 Open-access PDF
Authors
References
- Basic Local Alignment Search Tool
- Elements of Information Theory
- CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice
- Controlling the False Discovery Rate: A Practical and Powerful Approach to Multiple Testing
- Neural Networks: A Comprehensive Foundation
- Exploring the Metabolic and Genetic Control of Gene Expression on a Genomic Scale
- Comprehensive Identification of Cell Cycle–regulated Genes of the YeastSaccharomyces cerevisiaeby Microarray Hybridization
- CLUSTAL: a package for performing multiple sequence alignment on a microcomputer
- Prediction of complete gene structures in human genomic DNA
- Life with 6000 Genes