42014 - Complex and Hierarchical Models (MJC)

Type: Elective
Semester: S3
Teaching Points: 12
Offer: Annual
Responsible Unit: LSI
Responsible: Pere Brunet
Language: English
Requirements:Students should have previous knowledge of:
  • Algorithmics and data structures
  • Lineal algebra
  • Geometrical models
The requirements for the first two subjects can be reached at any degree in Informatics. As for the latter, it is required to know about fundamental representation schemes of solids (borders, CSG, triangle nets, octrees) and of surfaces (Bèzier, Splines, Fractals, Subdivision).

The goal of the course is to introduce the students in the existing methods for achieving an efficient inspection and manipulation of complex objects and scenes. The aim is that the student has a global view of the problem and a wide knowledge of the current solutions. The course will focus on hierarchical representation of scenes and on model's simplification and visibility culling algorithms.

1. Hierarchical models
  • Models based on the space subdivision.
  • Models based on the scene subdivision.
  • Out-of-core representations.
2. Simplification of triangular meshes
  • Theoretical principles.
  • Geometry and Topologic-preserving simplifications.
  • Visual-preserving simplification
  • Out-of-core simplification.
3. Visibility Computation
  • The visibility problem.
  • Portal culling.
  • Point and region visibility algorithms
  • GPU visibility computation.
4. Interactive navigation.
  • Scene representation.
  • Level of Detail selection factors.
  • View-depended rendering.
  • Collision detection.

Students’ work will be divided into:
  • Theoretical lessons: students will be presented with the master lines for each topic, the most relevant ideas, and the connection between them and other speciality topics. The complementary materials will be specified, and will usually be from magazine publications.
  • Personal work: studying, deepening in the covered topics with complementary materials and meetings with the teacher.
  • Practical projects: done in labs, supervised during some time, but mainly consisting of the implementation of diverse algorithms

Students will be evaluated on their practical exercises and projects, solving of problems and presentations of complementary materials.

D. Luebke, M. Reddy, J. Cohen, A. Varshney, B. Watson, R. Huebner
Level of Detail for 3D Graphics
Morgan Kaufmann Publishers, 2003

Recent articles and tutorials presented in Eurographics and SIGGRAPH as:
Visibility, Problems, Techniques and Applications
Daniel Cohen-Or et alt.
Siggraph Course Notes #30, 2001
Geometric Data Structures for Computer Graphics
G. Zachmann, E. Langetepe
Eurographic Tutorial, 2002

As there are no books that gather the state of the question, the basic resources will be articles published in magazines, which teachers will provide the students with. Access to the magazines in the library will be fundamental.