“Direct visibility of point sets” by Katz, Tal and Basri

  • ©Sagi Katz, Ayellet Tal, and Ronen Basri




    Direct visibility of point sets



    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.


    1. Abam, M., and de Berg, M. 2005. Kinetic sorting and kinetic convex hulls. In Twenty-First Annual Symposium on Computational geometry, 190–197. Google ScholarDigital Library
    2. Adamson, A., and Alexa, M. 2003. Approximating and intersecting surfaces from points. In Eurographics/ACM SIGGRAPH symposium on Geometry processing, 230–239. Google ScholarDigital Library
    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. Google ScholarDigital Library
    4. Alexa, M., Gross, M., Pauly, M., Pfister, H., Stamminger, M., and Zwicker, M. 2004. Point-based computer graphics. In SIGGRAPH course notes. Google ScholarDigital Library
    5. Amenta, N., and Kil, Y. 2004. Defining point-set surfaces. ACM Trans. Graph. 23, 3, 264–270. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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.Google ScholarCross Ref
    8. Appel, A. 1968. Some techniques for shading machine renderings of solids. In AFIPS Spring Joint Computer Conf., vol. 32, 37–45. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    11. Bittner, J., and Wonka, P. 2003. Visibility in computer graphics. Environment and Planning B: Planning and Design 30, 5, 729–756.Google ScholarCross Ref
    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. Google ScholarDigital Library
    13. Co, C. 2006. Meshless Methods for Volume Visualization. PhD thesis, University of California, Davis. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    16. Dachsbacher, C., Vogelgsang, C., and Stamminger, M. 2003. Sequential point trees. ACM Trans. Graph. 22, 3, 657–662. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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.Google Scholar
    19. Fleishman, S., Cohen-Or, D., Alexa, M., and Silva, C. 2003. Progressive point set surfaces. ACM Trans. Graph. 22, 4, 997–1011. Google ScholarDigital Library
    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. Google ScholarDigital Library
    21. Forsythe, G., Malcolm, M., and Moler, C. 1977. Computer Methods for Mathematical Computations. Prentice Hall. Google ScholarDigital Library
    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. Google ScholarDigital Library
    23. Greene, N., Kass, M., and Miller, G. 1993. Hierarchical z-buffer visibility. In SIGGRAPH, 231–238. Google ScholarDigital Library
    24. Guennebaud, G., Barthe, L., and Paulin, M. 2004. Deferred splatting. Comput. Graph. Forum 23, 3, 653–660.Google ScholarCross Ref
    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.Google Scholar
    26. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. Computer Graphics 26, 2, 71–78. Google ScholarDigital Library
    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.Google ScholarCross Ref
    28. Kobbelt, L., and Botsch, M. 2004. A survey of point-based techniques in computer graphics. Computers & Graphics 28, 6 (December), 801–814. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    32. Pauly, M., and Gross, M. 2001. Spectral processing of point-sampled geometry. In SIGGRAPH, 379–386. Google ScholarDigital Library
    33. Rusinkiewicz, S., and Levoy, M. 2000. Qsplat: A multiresolution point rendering system for large meshes. In SIGGRAPH, 343–352. Google ScholarDigital Library
    34. Sainz, M., and Pajarola, R. 2004. Point-based rendering techniques. Computers & Graphics 28, 6, 869–879. Google ScholarDigital Library
    35. Sainz, M., Pajarola, R., and Lario, R. 2004. Points reloaded: Point-based rendering revisited. In Symposium on Point-Based Graphics, 121–128. Google ScholarCross Ref
    36. Schaufler, G., and Jensen, H. 2000. Ray tracing point sampled geometry. In Eurographics Workshop on Rendering Techniques, 319–328. Google ScholarDigital Library
    37. Sutherland, E., Sproull, R., and Schumacker, R. 1974. A characterization of ten hidden-surface algorithms. ACM Comput. Surv. 6, 1, 1–55. Google ScholarDigital Library
    38. Wald, I., and Seidel, H.-P. 2005. Interactive ray tracing of point-based models. In Eurographics Symposium on Point-Based Graphics, 1–8. Google ScholarCross Ref
    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. Google ScholarCross Ref
    40. Woo, A., Poulin, P., and Fournier, A. 1990. A survey of shadow algorithms. IEEE Comput. Graph. Appl. 10, 6, 13–32. Google ScholarDigital Library
    41. Wu, J., and Kobbelt, L. 2004. Optimized sub-sampling of point sets for surface splatting. Computer Graphics Forum 23, 643–652.Google ScholarCross Ref
    42. Zwicker, M., Pfister, H., van Baar, J., and Gross, M. 2001. Surface splatting. In SIGGRAPH, 371–378. Google ScholarDigital Library
    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. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: