Direct visibility of point sets

Abstract

This paper proposes a simple and fast operator, the "Hidden" Point Removal operator, which determines the visible points in a point cloud, as viewed from a given viewpoint. Visibility is determined without reconstructing a surface or estimating normals. It is shown that extracting the points that reside on the convex hull of a transformed point cloud, amounts to determining the visible points. This operator is general - it can be applied to point clouds at various dimensions, on both sparse and dense point clouds, and on viewpoints internal as well as external to the cloud. It is demonstrated that the operator is useful in visualizing point clouds, in view-dependent reconstruction and in shadow casting.

References

1. Abam, M., and de Berg, M. 2005. Kinetic sorting and kinetic convex hulls. In Twenty-First Annual Symposium on Computational geometry, 190--197.
2. Adamson, A., and Alexa, M. 2003. Approximating and intersecting surfaces from points. In Eurographics/ACM SIGGRAPH symposium on Geometry processing, 230--239.
3. Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., and Silva, C. 2003. Computing and rendering point set surfaces. IEEE Trans. on Vis. and Computer Graphics 9, 1, 3--15.
4. Alexa, M., Gross, M., Pauly, M., Pfister, H., Stamminger, M., and Zwicker, M. 2004. Point-based computer graphics. In SIGGRAPH course notes.
5. Amenta, N., and Kil, Y. 2004. Defining point-set surfaces. ACM Trans. Graph. 23, 3, 264--270.
6. Amenta, N., Choi, S., and Kolluri, R. 2001. The power crust, unions of balls, and the medial axis transform. Int. J. of Computational Geometry and its Applications 19, 2--3, 127--153.
7. Amenta, N., Choi, S., Dey, T. K., and Leekha, N. 2002. A simple algorithm for homeomorphic surface reconstruction. In Int. J. Comput. Geom. Appl., vol. 12, 125--141.
8. Appel, A. 1968. Some techniques for shading machine renderings of solids. In AFIPS Spring Joint Computer Conf., vol. 32, 37--45.
9. Barber, C. B., Dobkin, D. P., and Huhdanpaa, H. 1996. The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22, 4, 469--483.
10. Bernardini, F., Mittleman, J., Rushmeier, H., Silva, C., and Taubin, G. 1999. The ball-pivoting algorithm for surface reconstruction. IEEE Transactions on Visualization and Computer Graphics 5, 4.
11. Bittner, J., and Wonka, P. 2003. Visibility in computer graphics. Environment and Planning B: Planning and Design 30, 5, 729--756.
12. Carr, J. C., Beatson, R. K., Cherrie, J. B., Mitchell, T. J., Fright, W. R., McCallum, B. C., and Evans, T. R. 2001. Reconstruction and representation of 3D objects with radial basis functions. In SIGGRAPH, 67--76.
13. Co, C. 2006. Meshless Methods for Volume Visualization. PhD thesis, University of California, Davis.
14. Cohen-Or, D., Chrysanthou, Y., Silva, C., and Durand, F. 2003. A survey of visibility for walkthrough applications. IEEE Trans, on Vis. and Computer Graphics 9, 3, 412--431.
15. Curless, B., and Levoy, M. 1996. A volumetric method for building complex models from range images. In SIGGRAPH, ACM Press, New York, NY, USA, 303--312.
16. Dachsbacher, C., Vogelgsang, C., and Stamminger, M. 2003. Sequential point trees. ACM Trans. Graph. 22, 3, 657--662.
17. de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. 1997. Computational geometry: algorithms and applications. Springer-Verlag New York, Inc., NJ, USA.
18. Dutré, P., Tole, P., and Greenberg, D. 2000. Approximate visibility for illumination computations using point clouds. Tech. Rep. PCG-00-01, Cornell University, June.
19. Fleishman, S., Cohen-Or, D., Alexa, M., and Silva, C. 2003. Progressive point set surfaces. ACM Trans. Graph. 22, 4, 997--1011.
20. Fleishman, S., Cohen-Or, D., and Silva, C. 2005. Robust moving least-squares fitting with sharp features. ACM Trans. Graph. 24, 3, 544--552.
21. Forsythe, G., Malcolm, M., and Moler, C. 1977. Computer Methods for Mathematical Computations. Prentice Hall.
22. Funkhouser, T., Squin, C., and Teller, S. 1992. Management of large amounts of data in interactive building walkthroughs. Symposium on Interactive 3D Graphics 25, 2, 11--20.
23. Greene, N., Kass, M., and Miller, G. 1993. Hierarchical z-buffer visibility. In SIGGRAPH, 231--238.
24. Guennebaud, G., Barthe, L., and Paulin, M. 2004. Deferred splatting. Comput. Graph. Forum 23, 3, 653--660.
25. Hasenfratz, J.-M., Lapierre, M., Holzschuch, N., and Sillion, F. 2003. A survey of real-time soft shadows algorithms. In Eurographics State-of-the-Art Reports.
26. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. Computer Graphics 26, 2, 71--78.
27. Katz, S., Leifman, G., and Tal, A. 2005. Mesh segmentation using feature point and core extraction. The Visual Computer 21, 8--10, 865--875.
28. Kobbelt, L., and Botsch, M. 2004. A survey of point-based techniques in computer graphics. Computers & Graphics 28, 6 (December), 801--814.
29. Leyvand, T., Sorkine, O., and Cohen-Or, D. 2003. Ray space factorization for from-region visibility. ACM Transactions on Graphics (TOG) 22, 3, 595--604.
30. Mederos, B., Amenta, N., Vehlo, L., and de Figueiredo, L. 2005. Surface reconstruction from noisy point clouds. In Eurographics Symposium on Geometry Processing, 53--62.
31. Ohtake, Y., Belyaev, A., Alexa, M., Turk, G., and Seidel, H.-P. 2003. Multi-level partition of unity implicits. ACM Trans. Graph. 22, 3, 463--470.
32. Pauly, M., and Gross, M. 2001. Spectral processing of point-sampled geometry. In SIGGRAPH, 379--386.
33. Rusinkiewicz, S., and Levoy, M. 2000. Qsplat: A multiresolution point rendering system for large meshes. In SIGGRAPH, 343--352.
34. Sainz, M., and Pajarola, R. 2004. Point-based rendering techniques. Computers & Graphics 28, 6, 869--879.
35. Sainz, M., Pajarola, R., and Lario, R. 2004. Points reloaded: Point-based rendering revisited. In Symposium on Point-Based Graphics, 121--128.
36. Schaufler, G., and Jensen, H. 2000. Ray tracing point sampled geometry. In Eurographics Workshop on Rendering Techniques, 319--328.
37. Sutherland, E., Sproull, R., and Schumacker, R. 1974. A characterization of ten hidden-surface algorithms. ACM Comput. Surv. 6, 1, 1--55.
38. Wald, I., and Seidel, H.-P. 2005. Interactive ray tracing of point-based models. In Eurographics Symposium on Point-Based Graphics, 1--8.
39. Wimmer, M., and Scheiblauer, C. 2006. Instant points: Fast rendering of unprocessed point clouds. In Proceedings Symposium on Point-Based Graphics 2006, 129--136.
40. Woo, A., Poulin, P., and Fournier, A. 1990. A survey of shadow algorithms. IEEE Comput. Graph. Appl. 10, 6, 13--32.
41. Wu, J., and Kobbelt, L. 2004. Optimized sub-sampling of point sets for surface splatting. Computer Graphics Forum 23, 643--652.
42. Zwicker, M., Pfister, H., van Baar, J., and Gross, M. 2001. Surface splatting. In SIGGRAPH, 371--378.
43. Zwicker, M., Pauly, M., Knoll, O., and Gross, M. 2002. Pointshop 3D: an interactive system for point-based surface editing. ACM Trans. Graph. 21, 3, 322--329.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

      • Parametric curve and surface models

      • Volumetric models

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry