The Expected Number of 3D Visibility Events Is Linear
Authors:
- Olivier DevillersODOlivier Devillers
- Vida DujmovicVDVida Dujmovic
- Hazel EverettHEHazel Everett
- Xavier GoaocXGXavier Goaoc
- Sylvain LazardSLSylvain Lazard
- Hyeon-Suk NaHNHyeon-Suk Na
- Sylvain PetitjeanSPSylvain Petitjean
- 1 January 2003
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 32 (6) , 1586-1620
Abstract
In this paper, we show that, amongst n uniformly distributed unit balls in $\mathbb{R}^3$, the expected number of maximal nonoccluded line segments tangent to four balls is linear. Using our techniques we show a linear bound on the expected size of the visibility complex, a data structure encoding the visibility information of a scene, providing evidence that the storage requirement for this data structure is not necessarily prohibitive. These results significantly improve the best previously known bounds of $O(n^{8/3})$ [F. Durand, G. Drettakis, and C. Puech, {ACM Transactions on Graphics}, 21 (2002), pp. 176-206]. Our results generalize in various directions. We show that the linear bound on the expected number of maximal nonoccluded line segments that are not too close to the boundary of the scene and tangent to four unit balls extends to balls of various but bounded radii, to polyhedra of bounded aspect ratio, and even to nonfat three-dimensional objects such as polygons of bounded aspect ratio. We also prove that our results extend to other distributions such as the Poisson distribution. Finally, we indicate how our probabilistic analysis provides new insight on the expected size of other global visibility data structures, notably the aspect graph.
Keywords
This publication has 16 references indexed in Scilit:
- The 3D visibility complexACM Transactions on Graphics, 2002
- Common Tangents to Four Unit Balls in R 3Discrete & Computational Geometry, 2001
- Interactive ray tracing with the visibility complexComputers & Graphics, 1999
- A qualitative and quantitative visibility analysis in urban scenesComputers & Graphics, 1999
- Line Transversals of Balls and Smallest Enclosing Cylinders in Three DimensionsDiscrete & Computational Geometry, 1999
- The union of moving polygonal pseudodiscs — Combinatorial bounds and applicationsComputational Geometry, 1998
- THE VISIBILITY COMPLEXInternational Journal of Computational Geometry & Applications, 1996
- The visual hull concept for silhouette-based image understandingIEEE Transactions on Pattern Analysis and Machine Intelligence, 1994
- Ray shooting on triangles in 3-spaceAlgorithmica, 1993
- Visibility, occlusion, and the aspect graphInternational Journal of Computer Vision, 1990