Similar articles

Abstract: The problem of computing a piecewise linear approximation to a surface from its sample has been a focus of research in geometry modeling and graphics due to its widespread applications in computer aided design. In this paper, we give a new algorithm, to be called offset surface filtering (OSF) algorithm, which computes a piecewise-linear approximation of a smooth surface from a finite set of cloud points. The algorithm has two main stages. First, the surface normal on every point is estimated by the least squares best fitting plane method. Second, we construct a restricted delaunay triangulation, which is a tubular neighborhood of the surface defined by two offset surfaces. The algorithm is simple and robust. We describe an implementation of it and show example outputs.

[1] Adamy, U., Giesen, J., John, M., 2002. Surface reconstruction using umbrella filters. Comput. Geom, 21(1-2):63-86.

[2] Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levein, D., Silva, C.T., 2001. Point Set Surfaces. IEEE Visualization 2001, p.21-28.

[3] Amenta, N., Bern, M., 1999. Surface reconstruction by Voronoi filtering. Discrete Comput. Geo., 22(4):481-504.

[4] Amenta, N., Bern, M., Kamvysselis, M., 1998. A New Voronoi-based Surface Reconstruction Algorithm. Proc. SIGGRAPH 1998, p.412-415.

[5] Amenta, N., Choi, S., Dey, T.K., Leekha, N., 2000. A Simple Algorithm for Homeomorphic Surface Reconstruction. Proceedings of the 16th Annual ACM Symposium on Computational Geometry (SCG

[6] Amenta, N., Choi, S., Kolluri, R.K., 2001. The power crust, unions of balls, and the medial axis transform. Comput. Geom. Theory Appl., 19:127-153.

[7] Attene, M., Spagnuolo, M., 2000. Automatic surface reconstruction from point sets in space. Computer Graphics Forum, 19(3):457-465.

[8] Bajaj, C., Bernardini, F., Xu, G., 1995. Automatic Reconstruction of Surfaces and Scalar Fields from 3D Scans. Proc. SIGGRAPH

[9] Bernardini, F., Mittleman, J., Rushmeier, H., Silva, C., Taubin, G., 1999. The ball-pivoting algorithm for surface reconstruction. IEEE Trans. Visualization Compute Graphics, 5(4):349-359.

[10] Bloomenthal, J.(Ed.), 1997. Introduction to Implicit Surfaces. Morgan Kaufmann, San Francisco, California. Bossonnat, J.D., 1984. Geometric structures of three-dimensional shape reconstruction. ACM Trans. Graphics, 3(4):266-286.

[11] Bossonnat, J.D., Cazals, F., 2000. Smooth Surface Reconstruction via Natural Neighbor Interpolation of Distance Functions. Proceedings of SCG

[12] Carr, J., Beatson, R.K., Cherrie, J.B., Mitchell, T.J., Fright, W.R., Mccallum, B.C., Evans, T.R., 2001. Reconstruction and Representation of 3D Objects with Radial Basis Functions. Proc. SIGGRAPH 2001, p.67-76.

[13] Chaine, R., 2003. A Geometric Convection Approach of 3-D Reconstruction. Proc. of Eurographics and ACM SIGGRAPH Symp. on Geometry Processing, p.218-229

[14] Curless, B., Levoy, M., 1996. A Volumetric Method for Building Complex Models from Range Images. Proc. SIGGRAPH

[15] Devillers, O., 1998. Improved Incremental Randomized Delaunay Triangulation. Proc. 14th Annual ACM Symp. Comput. Geom., p.106-115.

[16] Edelsbrunner, H., M

[17] Edelsbrunner, H., Shah, N., 1994. Triangulating Topological spaces. Proc. 10th ACM Symp. Comput. Geom., p.285-292.

[18] Floater, M.S., Reimers, M., 2001. Meshless parameterization and surface reconstruction. Computer Aided Geometry Design, 18(2):77-92.

[19] Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., Stuetzle, W., 1992. Surface reconstruction from unorganized points. Comput. Graphics, 26(2):71-78.

[20] Huang, J., Menq, C.H., 2002. Combinational manifold mesh reconstruction and optimization from unorganized points with arbitrary meshes. Computer-Aided Design, 34(2):149-165.

[21] Lorensen, W.E., Cline, H.E., 1987. Marching cubes: A high resolution 3D surface construction algorithm. Computer Graphics, 21(4):163-169.

[22] Lin, H.W., Tai, C.L., Wang, G.J., 2004. A mesh reconstruction algorithm driven by an intrinsic property of a point cloud. Computer-Aided Design, 36(1):1-9.

[23] Melkemi, M., 1997. A-shapes and Their Derivatives. Proc. 13th Annual ACM Symp. Comput. Geom., p.367-369.

[24] Mencl, R., 1995. Surface Reconstruction from Unorganized Points in Space. Abstracts 11th European Workshop Comput. Geom., p.67-70.

[25] Mencl, R., M

[26] Ohtake, Y., Belyaev, A., Alexa, M., Turk, G., Seidel, H.P., 2003. Multi-level Partition of Unity Implicits. Proc. SIGGRAPH 2003.

[27] Sakkalis, T., Peter, T.J., Bisceglio, J., 2004. Isotopic approximations and interval solids. Computer-Aided Design, 36:1089-1100.

[28] Turk, G., Brien, O.J., 2002. Modeling with implicit surfaces that interpolate. ACM Trans. on Graphics, 21(4):855-873.

[29] Veltkamp, R.C., 1991. The gamma-neighborhood graph. Comput. Geom., 1:227-246.

[30] Wallner, J., Sakkalis, T., Maekawa, T., Pottman, H., Yu, G., 2001. Selfintersections of offset curves and surfaces. Int. J. Shape Modeling, 7(1):1-21.

[31] Zhao, H., Osher, S., 2002. Visualization, Analysis and Shape Reconstruction of Unorganized Data Sets. In: Osher, S., Paragios, N.(Eds.), Geometric Level Set Methods in Imaging, Vision and Graphics. Springer.