Surface reconstruction using umbrella filters. (English) Zbl 0991.68125
Summary: We present a new approach to surface reconstruction in arbitrary dimensions based on the Delaunay complex. Basically, our algorithm picks locally a surface at each vertex. In the case of two dimensions we prove that this method gives indeed a reconstruction scheme. In three dimensions we show that for smooth regions of the surface this method works well and at difficult parts of the surface yields an output well-suited for postprocessing. As a postprocessing step we propose a topological clean up and a new technique based on linear programming in order to establish a topologically correct surface. These techniques should be useful also for many other reconstruction algorithms.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | U. Adamy, J. Giesen, M. John, New techniques for topologically correct surface reconstruction, in: Proceedings of the 11th Annual IEEE Visualization Conference (VIS ’00), 2000, pp. 373-380; U. Adamy, J. Giesen, M. John, New techniques for topologically correct surface reconstruction, in: Proceedings of the 11th Annual IEEE Visualization Conference (VIS ’00), 2000, pp. 373-380 |
| [2] | Althaus, E.; Mehlhorn, K., TSP-based curve reconstruction in polynomial time, (Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’00) (2000)), 686-695 · Zbl 0954.65011 |
| [3] | Amenta, N.; Bern, M., Surface reconstruction by Voronoi filtering, Discrete Comput. Geom., 22, 4, 481-504 (1999) · Zbl 0939.68138 |
| [4] | Amenta, N.; Bern, M.; Eppstein, D., The crust and the \(β\)-skeleton: Combinatorial curve reconstruction, Graphical Models Image Process., 60, 2, 125-135 (1998) |
| [5] | Amenta, N.; Bern, M.; Kamvysselis, M., A new Voronoi-based surface reconstruction algorithm, (Proceedings of ACM SIGGRAPH 98 (1998)), 412-415 |
| [6] | Amenta, N.; Choi, S.; Dey, T. K.; Leekha, N., A simple algorithm for homeomorphic surface reconstruction, (Proceedings of the 16th Annual ACM Symposium on Computational Geometry (SCG ’00) (2000)), 213-222 · Zbl 1374.68636 |
| [7] | Attali, D., \(r\)-regular shape reconstruction from unorganized points, Computational Geometry, 10, 239-247 (1998) · Zbl 0904.68172 |
| [8] | Bajaj, C. L.; Bernardini, E.; Xu, G., Automatic reconstruction of surfaces and scalar fields from 3D scans, (Proceedings of ACM SIGGRAPH 95 (1995)), 109-118 |
| [9] | Boissonnat, J.-D., Geometric structures for three-dimensional shape representation, ACM Trans. Graphics, 3, 4, 266-286 (1984) |
| [10] | Computational Geometry Algorithms Library (CGAL), http://www.cgal.org; Computational Geometry Algorithms Library (CGAL), http://www.cgal.org · Zbl 1365.68441 |
| [11] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), MIT Press: MIT Press Cambridge, MA · Zbl 1158.68538 |
| [12] | CPLEX, http://www.cplex.com; CPLEX, http://www.cplex.com |
| [13] | Curless, B.; Levoy, M., A volumetric method for building complex models from range images, (Proceedings of ACM SIGGRAPH 96 (1996)), 303-312 |
| [14] | Dey, T. K.; Kumar, P., A simple provable algorithm for curve reconstruction, (Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’99) (1999)), 893-894 · Zbl 1052.65509 |
| [15] | Edelsbrunner, H.; Kirkpatrick, D. G.; Seidel, R., On the shape of a set of points in the plane, IEEE Trans. Inform. Theory, 29, 551-559 (1983) · Zbl 0512.52001 |
| [16] | Edelsbrunner, H.; Mücke, E. P., Three-dimensional alpha shapes, ACM Trans. Graphics, 13, 1, 43-72 (1994) · Zbl 0806.68107 |
| [17] | Falconer, K. J., The Geometry of Fractal Sets (1985), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0587.28004 |
| [18] | Geomview, http://www.geom.umn.edu/software/geomview; Geomview, http://www.geom.umn.edu/software/geomview |
| [19] | Giesen, J., Curve reconstruction, the Traveling Salesman Problem, and Menger’s Theorem on length, (Proceedings of the 15th Annual ACM Symposium on Computational Geometry (SCG ’99) (1999)), 207-216 · Zbl 0984.65012 |
| [20] | Hoppe, H.; DeRose, T.; Duchamp, T.; McDonald, J.; Stuetzle, W., Surface reconstruction from unorganized points, Computer Graphics (Proceedings of SIGGRAPH92), 26, 2, 71-78 (1992) |
| [21] | Kirkpatrick, D. G.; Radke, J. D., A framework for computational morphology, Computational Geometry, 217-248 (1985) |
| [22] | Teichmann, M.; Capps, M., Surface reconstruction with anisotropic density-scaled alpha shapes, (Proceedings of the 9th Annual IEEE Conference on Visualization (VIS ’98) (1998)), 67-72 |
| [23] | tom Dieck, T., Topologie (1991), DeGruyter: DeGruyter Berlin · Zbl 0731.55001 |
| [24] | Veltkamp, R. C., The gamma-neighborhood graph, Computational Geometry, 1, 227-246 (1992) · Zbl 0748.68089 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
