Point-sampled cell complexes

ABSTRACT

A piecewise smooth surface, possibly with boundaries, sharp edges, corners, or other features is defined by a set of samples. The basic idea is to model surface patches, curve segments and points explicitly, and then to glue them together based on explicit connectivity information. The geometry is defined as the set of stationary points of a projection operator, which is generalized to allow modeling curves with samples, and extended to account for the connectivity information. Additional tangent constraints can be used to model shapes with continuous tangents across edges and corners.

REFERENCES

• 1: Adams, B., Keiser, R., Pauly, M., Guibas, L. J., Gross, M., & Dutréé, P. 2005. Efficient raytracing of deforming point-sampled surfaces. Computer Graphics Forum 24, 3, 677--684.
• 2: Approximating Bounded, Non-Orientable Surfaces from Points, Proceedings of the Shape Modeling International 2004 (SMI'04), p.243-252, June 07-09, 2004 [doi>10.1109/SMI.2004.13]
• 3: Alexa, M., & Adamson, A. 2004. On normals and projection operators for surfaces defined by point sets. In Proceedings of Eurographics Symposium on Point-based Graphics, Eurographics, M. Alexa, M. Gross, H. Pfister, & S. Rusinkiewicz, Eds., 149--156.
• 4: Marc Alexa , Johannes Behr , Daniel Cohen-Or , Shachar Fleishman , David Levin , Claudio T. Silva, Point set surfaces, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 5: Alexa, M., 2006. Hermite point set surfaces. manuscript.
• 6: Nina Amenta , Yong Joo Kil, Defining point-set surfaces, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 7: Nina Amenta , Marshall Bern , Manolis Kamvysselis, A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.415-421, July 1998 [doi>10.1145/280814.280947]
• 8: Henning Biermann , Adi Levin , Denis Zorin, Piecewise smooth subdivision surfaces with normal control, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.113-120, July 2000 [doi>10.1145/344779.344841]
• 9: Henning Biermann , Ioana Martin , Fausto Bernardini , Denis Zorin, Cut-and-paste editing of multiresolution surfaces, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 10: Henning Biermann , Ioana M. Martin , Denis Zorin , Fausto Bernardini, Sharp features on multiresolution subdivision surfaces, Graphical Models, v.64 n.2, p.61-77, March 2002 [doi>10.1006/gmod.2002.0570]
• 11: Bremer, P.-T., & Hart, J. C. 2005. A sampling theorem for mls surfaces. In Symposium on Point - Based Graphics 2005, 47--54.
• 12: Tamal K. Dey , Piyush Kumar, A simple provable algorithm for curve reconstruction, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.893-894, January 17-19, 1999, Baltimore, Maryland, United States
• 13: Dey, T. K., & Sun, J. 2005. An adaptive mls surface for reconstruction with guarantees. In ACM Symposium on Geometry Processing, 43--52.
• 14: Dey, T. K., Goswami, S., & Sun, J., 2005. Extremal surface based projections converge and reconstruct with isotopy. manuscript.
• 15: Shachar Fleishman , Daniel Cohen-Or , Cláudio T. Silva, Robust moving least-squares fitting with sharp features, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 16: Cindy M. Grimm , John F. Hughes, Modeling surfaces of arbitrary topology using manifolds, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.359-368, September 1995 [doi>10.1145/218380.218475]
• 17: Gumhold, S., Wang, X., & McLeod, R. 2001. Feature extraction from point clouds. In Proc. 10th International Meshing Roundtable, 293--305.
• 18: Hart, J. C. 1996. Sphere tracing: a geometric method for the antialiased ray tracing of implicit surfaces. The Visual Computer 12, 9, 527--545.
• 19: Hart, J. C. 1999. Using the CW-complex to represent the topological structure of implicit surfaces and solids. In Proc. Implicit Surfaces '99, 107--112.
• 20: Hatcher, A. 2002. Algebraic Topology. Cambridge University Press, Cambridge, UK.
• 21: Masaki Hilaga , Yoshihisa Shinagawa , Taku Kohmura , Tosiyasu L. Kunii, Topology matching for fully automatic similarity estimation of 3D shapes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.203-212, August 2001 [doi>10.1145/383259.383282]
• 22: Hugues Hoppe , Tony DeRose , Tom Duchamp , Mark Halstead , Hubert Jin , John McDonald , Jean Schweitzer , Werner Stuetzle, Piecewise smooth surface reconstruction, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.295-302, July 1994 [doi>10.1145/192161.192233]
• 23: Hugues Hoppe, Progressive meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.99-108, August 1996 [doi>10.1145/237170.237216]
• 24: Kobbelt, L., & Botsch, M. 2004. A survey of point-based techniques in computer graphics. Computers & Graphics 28, 6, 801--814.
• 25: Leif Kobbelt , Swen Campagna , Jens Vorsatz , Hans-Peter Seidel, Interactive multi-resolution modeling on arbitrary meshes, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.105-114, July 1998 [doi>10.1145/280814.280831]
• 26: Ravikrishna Kolluri, Provably good moving least squares, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 27: Henning Biermann , Daniel Kristjansson , Denis Zorin, Approximate Boolean operations on free-form solids, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.185-194, August 2001 [doi>10.1145/383259.383280]
• 28: David Levin, The approximation power of moving least-squares, Mathematics of Computation, v.67 n.224, p.1517-1531, Oct. 1998 [doi>10.1090/S0025-5718-98-00974-0 ]
• 29: Adi Levin, Combined subdivision schemes for the design of surfaces satisfying boundary conditions, Computer Aided Geometric Design, v.16 n.5, p.345-354, June 1999 [doi>10.1016/S0167-8396(98)00051-X ]
• 30: Levin, D. 2003. Mesh-independent surface interpolation. In Geometric Modeling for Data Visualization, Springer.
• 31: Nathan Litke , Adi Levin , Peter Schröder, Fitting subdivision surfaces, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 32: Nasri, A. H., & Sabin, M. A. 2002. Taxonomy of interpolation constraints on recursive subdivision surfaces. The Visual Computer 18, 5/6, 382--403.
• 33: Xinlai Ni , Michael Garland , John C. Hart, Fair morse functions for extracting the topological structure of a surface mesh, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 34: Yutaka Ohtake , Alexander Belyaev , Marc Alexa , Greg Turk , Hans-Peter Seidel, Multi-level partition of unity implicits, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 35: Mark Pauly , Richard Keiser , Leif P. Kobbelt , Markus Gross, Shape modeling with point-sampled geometry, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 36: Pauly, M., Keiser, R., & Gross, M. 2003. Multi-scale feature extraction on point-sampled surfaces. Computer Graphics Forum 22, 3 (Sept.), 281--290.
• 37: Jarek Rossignac, Structured topological complexes: a feature-based API for non-manifold topologies, Proceedings of the fourth ACM symposium on Solid modeling and applications, p.1-9, May 14-16, 1997, Atlanta, Georgia, United States [doi>10.1145/267734.267742]
• 38: Thomas W. Sederberg , Jianmin Zheng , Almaz Bakenov , Ahmad Nasri, T-splines and T-NURCCs, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 39: Thomas W. Sederberg , David L. Cardon , G. Thomas Finnigan , Nicholas S. North , Jianmin Zheng , Tom Lyche, T-spline simplification and local refinement, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 40: Chen Shen , James F. O'Brien , Jonathan R. Shewchuk, Interpolating and approximating implicit surfaces from polygon soup, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 41: Yoshihisa Shinagawa , Tosiyasu L. Kunii , Yannick L. Kergosien, Surface Coding Based on Morse Theory, IEEE Computer Graphics and Applications, v.11 n.5, p.66-78, September 1991 [doi>10.1109/38.90568 ]
• 42: Wald, I., & Seidel, H.-P. 2005. Interactive ray tracing of point based models. In Proceedings of 2005 Symposium on Point Based Graphics, 9--16.
• 43: Wendland, H. 1995. Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree. Adv. Comput. Math. 4, 4, 389--396.
• 44: Lexing Ying , Denis Zorin, Nonmanifold subdivision, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 45: Lexing Ying , Denis Zorin, A simple manifold-based construction of surfaces of arbitrary smoothness, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 46: Denis Zorin , Peter Schröder , Wim Sweldens, Interactive multiresolution mesh editing, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.259-268, August 1997 [doi>10.1145/258734.258863]
• 47: Matthias Zwicker , Mark Pauly , Oliver Knoll , Markus Gross, Pointshop 3D: an interactive system for point-based surface editing, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Keywords:
cell complex, continuity constraints, point-based modeling, sharp edges and corners