Multiresolution point-set surfaces

ABSTRACT

Multiresolution representations of 3D surfaces make it possible to concentrate the efforts of a modification at the appropriate level of detail. This paper introduces a multiresolution representation for point-set surfaces. At each level, the point set is smoothed and downsampled, and the geometric details are encoded along the smoothed surface normal. The resulting structure is only slightly larger than the original point set and allows to reconstruct it precisely. We demonstrate how it can be used for surface deformation and for frequency band scaling.

REFERENCES

• 1: Approximating Bounded, Non-Orientable Surfaces from Points, Proceedings of the Shape Modeling International 2004, p.243-252, June 07-09, 2004 [doi>10.1109/SMI.2004.13]
• 2: Anders Adamson , Marc Alexa, Anisotropic point set surfaces, Proceedings of the 4th international conference on Computer graphics, virtual reality, visualisation and interaction in Africa, January 25-27, 2006, Cape Town, South Africa [doi>10.1145/1108590.1108592]
• 3: Anders Adamson , Marc Alexa, Point-sampled cell complexes, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 4: M. Alexa and A. Adamson. Interpolatory point set surfaces --- convexity and hermite data. ACM Trans. on Graphics. To appear.
• 5: M. Alexa and A. Adamson. On normals and projection operators for surfaces defined by point sets. In Proc. Symp. on Point-based Graphics, pages 149--156, 2004.
• 6: Marc Alexa , Johannes Behr , Daniel Cohen-Or , Shachar Fleishman , David Levin , Claudio T. Silva, Computing and Rendering Point Set Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.9 n.1, p.3-15, January 2003 [doi>10.1109/TVCG.2003.1175093]
• 7: Nina Amenta , Yong Joo Kil, Defining point-set surfaces, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 8: Mario Botsch , Andreas Wiratanaya , Leif Kobbelt, Efficient high quality rendering of point sampled geometry, Proceedings of the 13th Eurographics workshop on Rendering, June 26-28, 2002, Pisa, Italy
• 9: T. Boubekeur, W. Heidrich, X. Granier, and C. Schlick. Volume-surface trees. Proc. Eurographics, 25(3):399--406, 2006.
• 10: T. Boubekeur, O. Sorkine, and C. Schlick. SIMOD: Making freeform deformation size-insensitive. In Proc. Symp. on Point-based Graphics, pages 47--56, 2007.
• 11: Matthias Eck , Tony DeRose , Tom Duchamp , Hugues Hoppe , Michael Lounsbery , Werner Stuetzle, Multiresolution analysis of arbitrary meshes, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.173-182, September 1995 [doi>10.1145/218380.218440]
• 12: Shachar Fleishman , Daniel Cohen-Or , Marc Alexa , Cláudio T. Silva, Progressive point set surfaces, ACM Transactions on Graphics (TOG), v.22 n.4, p.997-1011, October 2003 [doi>10.1145/944020.944023]
• 13: Markus Gross , Hanspeter Pfister, Point-Based Graphics (The Morgan Kaufmann Series in Computer Graphics), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2007
• 14: G. Guennebaud, L. Barthe, and M. Paulin. Dynamic surfel set refinement for high quality rendering. Computers & Graphics, 28(6):827--838, 2004.
• 15: G. Guennebaud, L. Barthe, and M. Paulin. Interpolatory refinement for real-time processing of point-based geometry. Proc. Eurographics), 24(3):657--667, 2005.
• 16: Gaël Guennebaud , Markus Gross, Algebraic point set surfaces, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 17: Igor Guskov , Wim Sweldens , Peter Schröder, Multiresolution signal processing for meshes, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.325-334, July 1999 [doi>10.1145/311535.311577]
• 18: Igor Guskov , Kiril Vidimče , Wim Sweldens , Peter Schröder, Normal meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.95-102, July 2000 [doi>10.1145/344779.344831]
• 19: Andreas Hubeli , Markus Gross, Multiresolution Methods for Nonmanifold Models, IEEE Transactions on Visualization and Computer Graphics, v.7 n.3, p.207-221, July 2001 [doi>10.1109/2945.942689]
• 20: L. Kobbelt and M. Botsch. A survey of point-based techniques in computer graphics. Computers & Graphics, 28(6):801--814, 2004.
• 21: 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]
• 22: 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
• 23: Carsten Lange , Konrad Polthier, Anisotropic smoothing of point sets, Computer Aided Geometric Design, v.22 n.7, p.680-692, October 2005 [doi>10.1016/j.cagd.2005.06.010]
• 24: Aaron Lee , Henry Moreton , Hugues Hoppe, Displaced subdivision surfaces, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.85-94, July 2000 [doi>10.1145/344779.344829]
• 25: 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]
• 26: D. Levin. Geometric Modeling for Scientific Visualization, chapter Mesh-Independent Surface Interpolation, pages 37--49. Springer-Verlag, 2003.
• 27: L. Linsen and H. Prautzsch. Fan clouds --- an alternative to meshes. In Theoretical Foundations of Computer Vision, pages 39--57, 2003.
• 28: Yaron Lipman , Daniel Cohen-Or , David Levin, Data-dependent MLS for faithful surface approximation, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
• 29: Yaron Lipman , Daniel Cohen-Or , David Levin , Hillel Tal-Ezer, Parameterization-free projection for geometry reconstruction, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 30: Michael Lounsbery , Tony D. DeRose , Joe Warren, Multiresolution analysis for surfaces of arbitrary topological type, ACM Transactions on Graphics (TOG), v.16 n.1, p.34-73, Jan. 1997 [doi>10.1145/237748.237750]
• 31: C. Moenning , F. Mémoli , G. Sapiro , N. Dyn , N. A. Dodgson, Meshless geometric subdivision, Graphical Models, v.69 n.3-4, p.160-179, May, 2007 [doi>10.1016/j.gmod.2006.11.001]
• 32: R. Pajarola. Efficient level-of-details for point based rendering. In Proc. IASTED Computer Graphics and Imaging, 2003.
• 33: R. Pajarola, M. Sainz, and R. Lario. XSplat: External memory multiresolution point visualization. In Proc. IASTED Visualization, Imaging and Image Processing, pages 628--633, 2005.
• 34: S.-B. Park, S.-U. Lee, and H. Choi. Multiscale surface representation and rendering for point clouds. In Proc. Intl. Conf. in Image Processing, volume 3, pages 1939--1942, 2004.
• 35: M. Pauly. Point Primitives for Interactive Modeling and Processing of 3D Geometry. PhD thesis, Eidgenössische Technische Hochschule Zürich, 2003.
• 36: Mark Pauly , Markus Gross, Spectral processing of point-sampled geometry, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.379-386, August 2001 [doi>10.1145/383259.383301]
• 37: Mark Pauly , Markus Gross , Leif P. Kobbelt, Efficient simplification of point-sampled surfaces, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 38: Mark Pauly , Leif P. Kobbelt , Markus Gross, Point-based multiscale surface representation, ACM Transactions on Graphics (TOG), v.25 n.2, p.177-193, April 2006 [doi>10.1145/1138450.1138451]
• 39: Hanspeter Pfister , Matthias Zwicker , Jeroen van Baar , Markus Gross, Surfels: surface elements as rendering primitives, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.335-342, July 2000 [doi>10.1145/344779.344936]
• 40: P. Reuter, P. Joyot, J. Trunzler, T. Boubekeur, and C. Schlick. Surface reconstruction with enriched reproducing kernel particle approximation. In Proc. Symp. on Point-based Graphics, pages 79--87, 2005.
• 41: Szymon Rusinkiewicz , Marc Levoy, QSplat: a multiresolution point rendering system for large meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.343-352, July 2000 [doi>10.1145/344779.344940]
• 42: J. M. Singh and P. J. Narayanan. Progressive decomposition of point clouds without local planes. In Indian Conf. on Computer Vision, Graphics and Image Processing, volume 4338 of Lecture Notes in Computer Science, pages 364--375, 2006.
• 43: Renfang Wang , Sanyuan Zhang , Xiuzi Ye, A novel simplification algorithm for point-sampled surfaces, Proceedings of the 2007 International Conference on Multimedia and Ubiquitous Engineering, p.573-578, April 26-28, 2007 [doi>10.1109/MUE.2007.39]
• 44: J. Wu, Z. Zhang, and L. Kobbelt. Progressive splatting. In Proc. Symp. on Point-based Graphics, pages 25--32, 2005.
• 45: Chunxia Xiao , Yongwei Miao , Shu Liu , Qunsheng Peng, A dynamic balanced flow for filtering point-sampled geometry, The Visual Computer: International Journal of Computer Graphics, v.22 n.3, p.210-219, March 2006 [doi>10.1007/s00371-006-0377-8]
• 46: Zhouwang Yang , Tae-wan Kim, Moving parabolic approximation of point clouds, Computer-Aided Design, v.39 n.12, p.1091-1112, December, 2007 [doi>10.1016/j.cad.2007.08.005]
• 47: Z. Yu and H.-S. Wong. An efficient local clustering approach for simplification of 3D point-based computer graphics models. In Intl. Conf. on Media & Expo, pages 2065--2068, 2006.
• 48: D.-H. Zhang, T. Yue, and Y.-H. Chen. Multi-scale surface representation of point-sampled geometry. In Intl. Symp. on Image and Signal Processing and Analysis, pages 371--376, 2005.
• 49: 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]

INDEX TERMS

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

Keywords:
deformation, multiresolution surface representations, point-sampled geometry, shape modeling