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):
and the defense slides:
What can you find in the thesis ?
What else have I done since the beginings ?
Here is a brief summary of my thesis.
Abstract
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:
- a change in the radial
ordering,
- or a change in the observer motion
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.
During my PhD, I have done a few more things on different topics, please visit
my
publications list.
Return to top
Last modified: