Please wait a minute...
Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering)  0, Vol. 6 Issue (100): 137-143    DOI: 10.1631/jzus.2005.AS0137
Computer & Information Science     
Surface reconstruction by offset surface filtering
DONG Chen-shi, WANG Guo-zhao
Department Mathematics, Zhejiang University, Hangzhou 310027, China
Download:   PDF(0KB)
Export: BibTeX | EndNote (RIS)      

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.

Key wordsCloud points      Surface reconstruction      Delaunay triangulation      Offset surface     
Received: 20 January 2005     
CLC:  TP391.72  
Cite this article:

DONG Chen-shi, WANG Guo-zhao. Surface reconstruction by offset surface filtering. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 0, 6(100): 137-143.

URL:

http://www.zjujournals.com/xueshu/zjus-a/10.1631/jzus.2005.AS0137     OR     http://www.zjujournals.com/xueshu/zjus-a/Y0/V6/I100/137

[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.
[1] Zhen-fei Zhan, Jie Hu, Yan Fu, Ren-Jye Yang, Ying-hong Peng, Jin Qi. Multivariate error assessment of response time histories method for dynamic systems[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2012, 13(2): 121-131.
[2] Nur Saaidah Abu Bakar, Mohd Rizal Alkahari, Hambali Boejang. Analysis on fused deposition modelling performance[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2010, 11(12): 972-977.
[3] Zhi-long LI, Jun-jie CAO, Xiu-ping LIU, Zhi-xun SU. A code-based approach for labeling in complex irregular regions[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2009, 10(10): 1450-1460.
[4] Ping ZHU, Guo-zhao WANG. Optimal approximate merging of a pair of Bézier curves with G2-continuity[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2009, 10(4): 554-561.
[5] Jorge CARAVANTES, Laureano GONZALEZ-VEGA. Computing the topology of an arrangement of implicitly defined real algebraic plane curves[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(12): 1685-1693.
[6] Ya-juan LI, Li-zheng LU, Guo-zhao WANG. Paths of algebraic hyperbolic curves[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(6): 816-821.
[7] CAI Hong-jie, WANG Guo-jin. Constrained multi-degree reduction of rational Bézier curves using reparameterization[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(10): 1650-1656.
[8] ZOU Wan-hong, DING Zhan, YE Xiu-zi, CHEN Zhi-yang. Interactive point cloud blending by drag-and-drop[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(10): 1633-1641.
[9] WANG Jin, LU Guo-dong, LI Ji-tuo, CHEN Long, ZHANG Dong-liang. Pattern design on 3D triangular garment surfaces[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(10): 1642-1649.
[10] CAO Juan, WANG Guo-zhao. Relation among C-curve characterization diagrams[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(10): 1663-1670.
[11] LU Li-zheng, WANG Guo-zhao. A quadratic programming method for optimal degree reduction of Bézier curves with G1-continuity[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(10): 1657-1662.
[12] JUHÁSZ Imre. Vanishing torsion of parametric curves[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(4): 593-595.
[13] MO Guo-liang, ZHAO Ya-nan. A new extension algorithm for cubic B-splines based on minimal strain energy[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(12): 13-.
[14] ZHANG Xing-wang, WANG Guo-jin. A new algorithm for designing developable Bézier surfaces[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(12): 14-.
[15] CAO Yan-long, LIU Yu-sheng, MAO Jian, YANG Jiang-xin. 3DTS: A 3D tolerancing system based on mathematical definition[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(11): 4-.