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

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