On the three-dimensional visibility skeleton: implementation and analysis

Squelette de visibilité en trois dimensions: implantation et analyse

Linqiao Zhang (1, 2)

1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
2 Computational Geometry Lab

The visibility skeleton is a data structure that encodes global visibility information of a given scene in either 2D or 3D. While this data structure is in principle very useful in answering global visibility queries, its high order worst-case complexity, especially in 3D scene, appears to be prohibitive. However, previous theoretical research has indicated that the expected size of this data structure can be linear under some restricted conditions. This thesis advances the study of the size of the visibility skeleton, namely, using an experimental approach. We first show that, both theoretically and experimentally, the expected size of the visibility skeleton in 2D is linear, and present a linear asymptote that facilitates estimation of the size of the 2D visibility skeleton. We then study the 3D visibility skeleton defined by visual events, which is a subset of the full skeleton defined by Durand et al.. We first present an implementation to compute the vertices of that skeleton for convex disjoint polytopes in general position. This implementation makes it possible to carry on our empirical study in 3D. We consider input scenes that consist of disjoint convex polytopes that approximate randomly distributed unit spheres. We found that, in our setting, the size of the 3D visibility skeleton is quadratically related to the number of the input polytopes and linearly related to the expected silhouette size of the input polytopes. This estimate is much lower than the worst-case complexity, but higher than the expected linear complexity that we had initially hoped for. We also provide arguments that could explain the obtained complexity. We finally prove that, using the 3D visibility skeleton defined by visual events, we can compute the remaining vertices of the full skeleton in almost linear time in the size of their output.

Le squelette de visibilité est une structure de donnée qui encode l'information de visibilité globale pour une scène donnée en 2D ou 3D. Cette structure de donnée est en principe très utile pour répondre à des requêtes de visiblité globale, mais elle est, en particulier en 3D, d'une complexité de haut degré dans le pire des cas qui semble prohibitive. Cependant, les recherches théoriques précédentes ont indiqué que l'espérance de la taille de cette structure de donnée peut être linéaire sous certaines conditions restreintes. Cette thèse approfondit l'étude de la taille du squelette de visibilité, au moyen d'une approche expérimentale. Nous montrons d'abord qu'aussi bien théoriquement qu'empiriquement, l'espérance de la taille du squelette de visibilité en 2D est linéaire, et présentons une asymptote affine qui facilite l'estimation de la taille du squelette de visibilité en 2D. Nous étudions ensuite le squelette de visibilité 3D défini par événement visuels, qui est un sous-ensemble du squelette complet défini par Durand et al. . Nous présen- tons tout d'abord une implantation calculant les sommets de ce squelette pour des polytopes convexes disjoints en position générale. Cette implantation nous permet de continuer notre étude empirique en 3D. Nous considérons des scènes données consis- tant en des polytopes convexes disjoints qui sont une approximation de sphères unités distribuées aléatoirement. Nous avons découvert que, dans ces conditions, la taille du squelette de visibilité 3D a une relation quadratique en le nombre de polytopes donnés, et linéaire en l'espérance de la taille de la silhouette des polytopes donnés. Cette estimation est bien plus basse que la complexité dans le pire des cas, mais plus haute que la complexité linéaire que nous espérions initialement. Nous présentons aussi des arguments qui pourraient expliquer la complexité obtenue. Nous prouvons finalement qu'en utilisant le squelette de visibilité 3D défini par événement visuels, nous pouvons calculer les sommets restants du squelette complet en temps presque linéaire en la taille du résultat.

Mots clés: visibilite 3D

Mots clés: 3D visibility

Domaines: Informatique [cs]

Linqiao Zhang. On the three-dimensional visibility skeleton: implementation and analysis. Computer Science [cs]. Université McGill, 2009. English. ⟨NNT : ⟩. ⟨tel-00431464⟩