Maintenance de la visibilité d'un point mobile, et applications
Maintenance of a mobile point's visibility, and applications

PhD thesis, Samuel Hornus

This webpage is in english but the thesis is written in french.
You can find a brief english summary of my thesis below.
I have defended my PhD thesis on May 22.

The manuscript as of July, 16th 2006 (A4 paper, almost final): [PDF] and the defense slides: [PDF]
What can you find in the thesis ?
What else have I done since the beginings ?

What can you find in the thesis ?

Here is a brief summary of my thesis.


The notion of visibility is central in computer graphics and computational geometry. A visibility computation amounts to determining the shape, or merely the existence of the set of segments in space linking two specified objects without crossing any other. We examine the problem of maintaining the visibility of a moving viewpoint with the aid of a complex describing all the visibility relationships in a scene, at once: the visibility complex.
We take two different approaches to this problem. In one, we show how one can maintain the so-called visibility polyhedron of the moving point, in an exact fashion. We apply a variant of the algorithm to the construction of the visibility complex of a set of disjoint polytopes.
The second approach is motivated by the need to render complex 3D scenes at interactive rates. We propose an algorithm that decomposes a 3D scene into simple cells related together with simple visibility relationships represented as a graph. The scene is drawn as the graph is traversed, allowing pruning to speed up rendering. We also provide an efficient algorithm for real-time rendering of hard shadows.

Chapter 1

Chapter 1 gives a few basic definitions regarding visibility and related notions.

Chapter 2

Chapter 2 is a brief summary of results about visibility computations and maintenance, in the computational geometry and computer graphics fields.

Chapter 3

Chapters 3, 4, 5 and 6 form our contributions to the problem of exact maintenance of the visibility of a moving viewpoint. In Chapter 3, we drastically simplify many assumptions about the scene, as we deal with a finite point set in the plane. In this case, the problem is that of maintaining the radial order of the points around the moving viewpoint. Two events can take place: We give an algorithm that handles this two type of events in O(log n) time, while keeping a linear space usage [1].

Chapter 4

Chapter 4 is a rather pedagogical contribution, since the algorithm that is presented is due to Olaf Hall-Holt: The visible zone algorithm. Here, the scene consists of a finite set of disjoint convex objects in the plane. The correctness of Hall-Holt's algorithm is based on several properties of certain curves in the visibility complex of the scene. Unfortunately, the exposition of these properties---in the Appendix A of Hall-Holt's thesis--- are complex to follow. In this chapter, we re-explain them (with Figures!) and shorten the exposition by providing a new and simpler proof of a technical lemma.

Chapter 5

Chapter 5 is devoted to the study of an algorithm for maintaining the visibility of a viewpoint moving among a set of disjoint polytopes (convex polyhedra) in 3-space. On of the main characteristic of our algorithm is its ability to handle arbitrary pseudo-algebaric motion plan for the viewpoint, ie, it is not specialized for a predefined type of trajectory such as a line segment. While the space requirement are roughly the same as the space needed to store a visibility map, our algorithm however is not optimal in that a change in the viewpoint trajectory may yield an update operation with quadratic cost in time. As a good point, we note that our algorithm allows the polytopes to deform arbitrarily (provided they stay convex!). Early report on this work were published in [2].

Chapter 6

Chapter 6 shows how we handle a data structure used in the initialization of the algorithm of Chapter 5: a kinetic radial decomposition of a set of segments in the plane, both of which (?) endpoints are allowed to move freely, with the ability to perform efficient point location queries.

Chapter 7

Here, we demonstrate an interesting property of the 3D visibility complex of a set of disjoint polytopes: if C is a 4-cell of the visibility complex, then its boundary is connected (in the topological sense). We use this property to design an simple algorithm for the construction of the 3D visibility complex. This algorithm seems to be the first for which an implementation looks feasible (!). Actually coding it, is therefore one of my our future goal.

Chapter 8

The two remaining chapters deal with practical concerns, ie, that of rendering a 3D scene quicky on the computer screen. In Chapter 8, ... shadow volumes [3].

Chapter 9

Automatic cell-and-portal decomposition [4].

Some related publications:

[1] Maintaining visibility information of planar point sets with a moving viewpoint
Olivier Devillers, Vida Dujmović, Hazel Everett, Samuel Hornus, Sue Whitesides, and Steve Wismath
Canadian Conference on Computational Geometry - August 2005. [www]
Return to Chapter 3, Return to top.

[2] 3D radial decomposition and their kinetic maintenance
Samuel Hornus and Claude Puech
DIMACS workshop on Algorithmic Issues in Modeling Motion, November 2002, Rutgers University. [www]
Return to Chapter 5, Return to top.

[3] ZP+: correct Z-pass stencil shadows
Samuel Hornus, Jared Hoberock, Sylvain Lefebvre and John C. Hart
ACM Symposium on Interactive 3D Graphics and Games (I3D'05) - April 2005. [www] [video]
Return to Chapter 8, Return to top.

[4] Automatic cell-and-portal decomposition
Sylvain Lefebvre and Samuel Hornus
INRIA Research Report 4898, July 2003. [www] [video]
Return to Chapter 9, Return to top.

What else have I done since the beginings ?

During my PhD, I have done a few more things on different topics, please visit my publications list.

Return to top

Last modified: