Surfel Stripping

ABSTRACT

This paper presents an efficient combination of techniques for fast stripping and multiresolution rendering of Point-Based Surfaces (PBS) called Surfel Stripping. Surfel Strips are small triangle strips that interpolate the PBS. There are two major contributions. First, at loading time, we efficiently convert the PBS into triangle strips. This is done by first generating a set of overlapping small triangular meshes that interpolate the PBS, then removing redundant triangles and finally stripping the small triangular meshes by using a cache-friendly stripping method. All these operations are performed by using an octree data structure. Second, we reuse this data structure for providing a multiresolution interactive visualization of the surfel strips at rendering time. Since Surfel Stripping is local and very fast, it can be used in a lot of situations as an object-space alternative to the image-space surface splatting and thus be considered half way between point-based rendering and local polygonal generation. Rendering Surfel Strips is very efficient since it neither requires multi-pass rendering nor time-consuming vertex/fragment shaders compared to surface splatting. We show also how to exploit the locality of the surfel strips for maintaining compatibility with point-based modeling tools, such as local deformations of surfaces. We finally give some examples of well known visual enrichments developed for polygons, directly applied to PBS thanks to surfel strips.

REFERENCES

• 1: 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
• 2: Marc Alexa , Markus Gross , Mark Pauly , Hanspeter Pfister , Marc Stamminger , Matthias Zwicker, Point-based computer graphics, Proceedings of the conference on SIGGRAPH 2004 course notes, p.7-es, August 08-12, 2004, Los Angeles, CA [doi>10.1145/1103900.1103907]
• 3: Mario Botsch , Leif Kobbelt, High-Quality Point-Based Rendering on Modern GPUs, Proceedings of the 11th Pacific Conference on Computer Graphics and Applications, p.335, October 08-10, 2003
• 4: Botsch, M., Spernat, M., and Kobbelt, L. 2004. Phong splatting. Symposium on Point Based Graphics 2004.
• 5: Botsch, M., Spernat, M., and Kobbelt, L. 2005. High quality splatting on today's gpu. Symposium on Point Based Graphics 2005.
• 6: Tamy Boubekeur , Patrick Reuter , Christophe Schlick, Visualization of Point-Based Surfaces with Locally Reconstructed Subdivision Surfaces, Proceedings of the International Conference on Shape Modeling and Applications 2005 (SMI' 05), p.23-32, June 13-17, 2005 [doi>10.1109/SMI.2005.49]
• 7: Baoquan Chen , Minh Xuan Nguyen, POP: a hybrid point and polygon rendering system for large data, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 8: Paolo Cignoni , Fabio Ganovelli , Enrico Gobbetti , Fabio Marton , Federico Ponchio , Roberto Scopigno, Adaptive tetrapuzzles: efficient out-of-core construction and visualization of gigantic multiresolution polygonal models, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 9: Liviu Coconu , Hans-Christian Hege, Hardware-accelerated point-based rendering of complex scenes, Proceedings of the 13th Eurographics workshop on Rendering, June 26-28, 2002, Pisa, Italy
• 10: Jonathan D. Cohen , Daniel G. Aliaga , Weiqiang Zhang, Hybrid simplification: combining multi-resolution polygon and point rendering, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 11: Carsten Dachsbacher , Christian Vogelgsang , Marc Stamminger, Sequential point trees, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 12: Olivier Devillers, Improved incremental randomized Delaunay triangulation, Proceedings of the fourteenth annual symposium on Computational geometry, p.106-115, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276896]
• 13: Tamal K. Dey , James Hudson, PMR: point to mesh rendering, a feature-based approach, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 14: Francine Evans , Steven Skiena , Amitabh Varshney, Optimizing triangle strips for fast rendering, Proceedings of the 7th conference on Visualization '96, p.319-326, October 28-29, 1996, San Francisco, California, United States
• 15: Fortune, S. 1987. A sweepline algorithm for vorono diagrams. Algorithmica 2, 153--174.
• 16: Enrico Gobbetti , Fabio Marton, Far voxels: a multiresolution framework for interactive rendering of huge complex 3D models on commodity graphics platforms, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 17: Gopi, M., Krishnan, S., and Silva, C. 2000. Surface reconstruction based on lower dimensional localized delaunay triangulation. Eurographics 2000.
• 18: Grossman, J. P., and Dally, W. J. 1998. Point sample rendering. Eurographics Workshop on Rendering 1998.
• 19: Guennebaud, G., and Paulin, M. 2003. Efficient Screen Space Approach for Hardware Accelerated Surfel Rendering. Vision, Modeling and Visualization 2003.
• 20: Paul S Heckbert, Survey of texture mapping, IEEE Computer Graphics and Applications, v.6 n.11, p.56-67, November 1986 [doi>10.1109/MCG.1986.276672]
• 21: Kobbelt, L., and Botsch, M. 2004. A survey of point-based techniques in computer graphics. Computers & Graphics, v28, n6.
• 22: Levoy, M., and Whitted, T. 1985. The use of points as display primitive. TR 82-022, Univ. of North Carolina at Chapel Hill.
• 23: Marc Levoy , Kari Pulli , Brian Curless , Szymon Rusinkiewicz , David Koller , Lucas Pereira , Matt Ginzton , Sean Anderson , James Davis , Jeremy Ginsberg , Jonathan Shade , Duane Fulk, The digital Michelangelo project: 3D scanning of large statues, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.131-144, July 2000 [doi>10.1145/344779.344849]
• 24: Linsen, L., and Prautzsch, H. 2003. Fan clouds - an alternative to meshes. In Proceedings of 11th International Dagstuhl Workshop on Theoretical Foundations of Computer Vision, Springer-Verlag.
• 25: 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]
• 26: 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
• 27: 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
• 28: 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]
• 29: Ren, L., Pfister, H., and Zwicker, M. 2002. Object space ewa surface splatting: A hardware accelerated approach to high quality point rendering. Eurographics 2002.
• 30: Reuter, P., Behr, J., and Alexa, M. 2005. An improved adjacency data structure for fast triangle stripping. Journal of Graphics Tools 10, 2.
• 31: 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]
• 32: Wicke, M., Olibet, S., and Gross, M. 2005. Conversion of point-sampled models to textured meshes. In Proceedings of the Symposium on Point-Based Graphics.
• 33: Matthias Zwicker , Hanspeter Pfister , Jeroen van Baar , Markus Gross, Surface splatting, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.371-378, August 2001 [doi>10.1145/383259.383300]
• 34: Matthias Zwicker , Hanspeter Pfister , Jeroen van Baar , Markus Gross, EWA Splatting, IEEE Transactions on Visualization and Computer Graphics, v.8 n.3, p.223-238, July 2002 [doi>10.1109/TVCG.2002.1021576 ]

INDEX TERMS

Keywords:
fast surface conversion, graphics data structure, multiresolution rendering, point-based graphics, triangle stripping