“Point-sampled cell complexes” by Adamson and Alexa

  • ©Anders Adamson and Marc Alexa




    Point-sampled cell complexes



    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.


    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.Google ScholarCross Ref
    2. Adamson, A., & Alexa, M. 2004. Approximating bounded, non-orientable surfaces from points. In Proceedings of Shape Modeling International 2004, IEEE Computer Society, F. Giannini & A. Pasko, Eds., 243–252. Google ScholarDigital Library
    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. Google ScholarDigital Library
    4. Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., & Silva, C. T. 2001. Point set surfaces. In IEEE Visualization 2001, 21–28. ISBN 0-7803-7200-x. Google ScholarDigital Library
    5. Alexa, M., 2006. Hermite point set surfaces. manuscript.Google Scholar
    6. Amenta, N., & Kil, Y. J. 2004. Defining point set surfaces. ACM Transactions on Graphics (SIGGRAPH 2004 issue) 23, 3, 264–270. Google ScholarDigital Library
    7. Amenta, N., Bern, M., & Kamvysselis, M. 1998. A new voronoi-based surface reconstruction algorithm. Proceedings of SIGGRAPH 98 (July), 415–422. Google ScholarDigital Library
    8. Biermann, H., Levin, A., & Zorin, D. 2000. Piecewise smooth subdivision surfaces with normal control. In Proceedings of ACM SIGGRAPH 2000, Computer Graphics Proceedings, Annual Conference Series, 113–120. Google ScholarDigital Library
    9. Biermann, H., Martin, I., Bernardini, F., & Zorin, D. 2002. Cut-and-paste editing of multiresolution surfaces. ACM Transactions on Graphics 21, 3 (July), 312–321. Google ScholarDigital Library
    10. Biermann, H., Martin, I. M., Zorin, D., & Bernardini, F. 2002. Sharp features on multiresolution subdivision surfaces. Graphical Models 64, 2 (Mar.), 61–77. Google ScholarDigital Library
    11. Bremer, P.-T., & Hart, J. C. 2005. A sampling theorem for mls surfaces. In Symposium on Point – Based Graphics 2005, 47–54. Google ScholarDigital Library
    12. Dey, T. K., & Kumar, P. 1999. A simple provable algorithm for curve reconstruction. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM-SIAM, N.Y., 893–894. Google ScholarDigital Library
    13. Dey, T. K., & Sun, J. 2005. An adaptive mls surface for reconstruction with guarantees. In ACM Symposium on Geometry Processing, 43–52. Google ScholarDigital Library
    14. Dey, T. K., Goswami, S., & Sun, J., 2005. Extremal surface based projections converge and reconstruct with isotopy. manuscript.Google Scholar
    15. Fleishman, S., Cohen-Or, D., & Silva, C. T. 2005. Robust moving least-squares fitting with sharp features. ACM Transactions on Graphics 24, 3 (Aug.), 544–552. Google ScholarDigital Library
    16. Grimm, C. M., & Hughes, J. F. 1995. Modeling surfaces of arbitrary topology using manifolds. In Proceedings of SIGGRAPH 95, Computer Graphics Proceedings, Annual Conference Series, 359–368. Google ScholarDigital Library
    17. Gumhold, S., Wang, X., & McLeod, R. 2001. Feature extraction from point clouds. In Proc. 10th International Meshing Roundtable, 293–305.Google Scholar
    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.Google ScholarCross Ref
    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.Google Scholar
    20. Hatcher, A. 2002. Algebraic Topology. Cambridge University Press, Cambridge, UK.Google Scholar
    21. Hilaga, M., Shinagawa, Y., Kohmura, T., & Kunii, T. L. 2001. Topology matching for fully automatic similarity estimation of 3d shapes. In Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, 203–212. Google ScholarDigital Library
    22. Hoppe, H., DeRose, T., Duchamp, T., Halstead, M., Jin, H., McDonald, J., Schweitzer, J., & Stuetzle, W. 1994. Piecewise smooth surface reconstruction. Proceedings of SIGGRAPH 94 (July), 295–302. Google ScholarDigital Library
    23. Hoppe, H. 1996. Progressive meshes. In Proceedings of SIGGRAPH 96, Computer Graphics Proceedings, Annual Conference Series, 99–108. Google ScholarDigital Library
    24. Kobbelt, L., & Botsch, M. 2004. A survey of point-based techniques in computer graphics. Computers & Graphics 28, 6, 801–814. Google ScholarDigital Library
    25. Kobbelt, L., Campagna, S., Vorsatz, J., & Seidel, H.-P. 1998. Interactive multi-resolution modeling on arbitrary meshes. In Proceedings of SIGGRAPH 98, Computer Graphics Proceedings, Annual Conference Series, 105–114. Google ScholarDigital Library
    26. Kolluri, R. 2005. Provably good moving least squares. In ACM-SIAM Symposium on Discrete Algorithms. to appear. Google ScholarDigital Library
    27. Kristjansson, D., Biermann, H., & Zorin, D. 2001. Approximate boolean operations on free-form solids. In Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, 185–194. Google ScholarDigital Library
    28. Levin, D. 1998. The approximation power of moving least-squares. Math. Comput. 67, 224, 1517–1531. Google ScholarDigital Library
    29. Levin, A. 1999. Combined subdivision schemes for the design of surfaces satisfying boundary conditions. Computer Aided Geometric Design 16, 5, 345–354. Google ScholarDigital Library
    30. Levin, D. 2003. Mesh-independent surface interpolation. In Geometric Modeling for Data Visualization, Springer.Google Scholar
    31. Litke, N., Levin, A., & Schrööder, P. 2001. Fitting subdivision surfaces. In IEEE Visualization 2001, 319–324. Google ScholarDigital Library
    32. Nasri, A. H., & Sabin, M. A. 2002. Taxonomy of interpolation constraints on recursive subdivision surfaces. The Visual Computer 18, 5/6, 382–403.Google Scholar
    33. Ni, X., Garland, M., & Hart, J. C. 2004. Fair morse functions for extracting the topological structure of a surface mesh. ACM Transactions on Graphics 23, 3 (Aug.), 613–622. Google ScholarDigital Library
    34. Ohtake, Y., Belyaev, A., Alexa, M., Turk, G., & Seidel, H.-P. 2003. Multi-level partition of unity implicits. ACM Transactions on Graphics 22, 3 (July), 463–470. Google ScholarDigital Library
    35. Pauly, M., Kaiser, R., Kobbelt, L., & Gross, M. 2003. Shape modeling with point-sampled geometry. ACM Transactions on Graphics (SIGGRAPH 2003 issue) 22, 3. to appear. Google ScholarDigital Library
    36. Pauly, M., Keiser, R., & Gross, M. 2003. Multi-scale feature extraction on point-sampled surfaces. Computer Graphics Forum 22, 3 (Sept.), 281–290.Google ScholarCross Ref
    37. Rossignac, J. 1997. Structured topological complexes: a feature-based api for non-manifold topologies. In SMA ’97: Proceedings of the Fourth Symposium on Solid Modeling and Applications, 1–9. Google ScholarDigital Library
    38. Sederberg, T. W., Zheng, J., Bakenov, A., & Nasri, A. 2003. T-splines and t-nurccs. ACM Transactions on Graphics 22, 3 (July), 477–484. Google ScholarDigital Library
    39. Sederberg, T. W., Cardon, D. L., Finnigan, G. T., North, N. S., Zheng, J., & Lyche, T. 2004. T-spline simplification and local refinement. ACM Transactions on Graphics 23, 3 (Aug.), 276–283. Google ScholarDigital Library
    40. Shen, C., O’Brien, J. F., & Shewchuk, J. R. 2004. Interpolating and approximating implicit surfaces from polygon soup. ACM Transactions on Graphics 23, 3 (Aug.), 896–904. Google ScholarDigital Library
    41. Shinagawa, Y., Kunii, T. L., & Kergosien, Y. L. 1991. Surface coding based on morse theory. IEEE Computer Graphics & Applications 11, 5 (Sept.), 66–78. Google ScholarDigital Library
    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. Google ScholarDigital Library
    43. Wendland, H. 1995. Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree. Adv. Comput. Math. 4, 4, 389–396.Google ScholarCross Ref
    44. Ying, L., & Zorin, D. 2001. Nonmanifold subdivision. In IEEE Visualization 2001, 325–331. Google ScholarDigital Library
    45. Ying, L., & Zorin, D. 2004. A simple manifold-based construction of surfaces of arbitrary smoothness. ACM Transactions on Graphics 23, 3 (Aug.), 271–275. Google ScholarDigital Library
    46. Zorin, D., Schröder, P., & Sweldens, W. 1997. Interactive multiresolution mesh editing. In Proceedings of SIGGRAPH 97, Computer Graphics Proceedings, Annual Conference Series, 259–268. Google ScholarDigital Library
    47. Zwicker, M., Pauly, M., Knoll, O., & Gross, M. 2002. Pointshop 3d: An interactive system for point-based surface editing. ACM Transactions on Graphics 21, 3 (July), 322–329. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: