Data Structures in Computer Graphics

The course is a substitute for:

Data Structures for Computer Graphics (X39DPG)

Lecturer:

Tutor:

Supervisor:

Department of Computer Science and Engineering

Synopsis:

The main topic of the lectures are the data structures used in computer graphics. The basic and hierarchical data structures over point and object data will be addressed. The focus of the lectures and exercises is nearest and k-nearest neighbor search, ray shooting, z-buffer based visibility algorithms and collision detection. The students will have their own projects.

Requirements:

Students will acquire credits on the basis of semestral project. The extent of the exam is given by contents of lectures.

Syllabus of lectures:

1. Lectures overview, review of sorting and searching, review of computer graphics algorithms, questions to the course, rules of the game

2. Introduction to hierarchical and regular data structures used in CG

3. Incidence operations used in computer graphics

4. Point based representations and data structures

5. Object based and image based representations in 2D and 3D

6. Proximity search and its applications I.

7. Proximity search and its application II

8. Ray shooting and its applications I

9. Ray shooting and its applications II

10. Visibility algorithms based on z-buffer I

11. Visibility algorithms based on z-buffer II

12. Static collision detection

13. Advanced collision detection

14. Reserve

Syllabus of tutorials:

1. Introduction to the exercises, description of homework projects

2. Selection of homework projects + consultation

3. Examples of incidence operations

4. Consultation to homework projects

5. Consultation to homework projects

6. Project presentation (4 participants)

7. Project presentation (4 participants)

8. Presentations (4 participants)

9. Consultations to homework projects

10. Written test for 60 minutes (plus perhaps some presentations)

11. Project presentation (4 participants)

12. Project presentations (4 participants)

13. Demonstration and evaluation of the projects (10x)

14. Demonstration and evaluation of the projects (10x)

Study Objective:

Study materials:

1. Samet, H: The Design and Analysis of Spatial Data Structures, Addison Wesley 1994.

2. Samet, H: Applications of Spatial Data Structures, Addison Wesley, 1990.

3. Laurini, R. and Thompson D.: Fundamentals of Spatial Information Systems, Academic Press 1992.

4. Samet, H: Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann Publishers, 2006.

5. E. Langetepe and G. Zachmann: Geometric Data Structures for Computer Graphics, 2006.

6. C. Ericson: Real Time Collision Detection, Morgan Kauffman Publishers, 2005.

7. G. van den Bergen: Collision Detection in Interactive 3D Environments, Elsevier, 2004.

8. D. P. Mehta and S. Sahni: Handbook of Data Structures and Applications, Chapman and Hall/CRC, 2004

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans: