Data Structures for Computer Graphics

Vztahy:

Předmět BE4M39DPG může při kontrole studijních plánů nahradit předmět B4M39DPG

Předmět BE4M39DPG nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět B4M39DPG (vztah je symetrický)

Předmět BE4M39DPG nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět B4M39DPG (vztah je symetrický)

Garant předmětu:

Vlastimil Havran

Přednášející:

Vlastimil Havran

Cvičící:

Vlastimil Havran

Předmět zajišťuje:

katedra počítačové grafiky a interakce

Anotace:

This course provides you with the fundamentals of data structures commonly used in computer graphics. In contrast to standard binary search trees used in one dimension, the presented theory focuses on multidimensional data used to describe 3D scenes. In addition to the theory, the course emphasizes individual and team projects, where the importance and advantages of multidimensional data are demonstrated on practical examples. The students will gain practical experience through their own individual projects.

Požadavky:

Space and runtime complexity of algorithms, binary trees and heaps, tree balancing, search algorithms, priority queues, fundamentals of von Neumann architecture, good knowledge of C++.

Osnova přednášek:

1. Lectures overview, review of sorting and searching, review of computer graphics algorithms, questions to the course, rules of the game. Introduction to hierarchical and regular data structures used in CG

2. Incidence operations used in computer graphics

3. Point based representations and data structures

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

5. Proximity search and its applications I.

6. Proximity search and its application II.

7. Proximity search in high-dimensional spaces.

8. Ray shooting and its applications I.

9. Ray shooting and its applications II.

10. Ray shooting and its applications III.

11. Visibility algorithms based on z-buffer

12. Static collision detection

13. Advanced collision detection

14. Reserved.

Osnova cvičení:

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. Project presentations (4 participants)

6. Project presentations (4 participants)

7. Project presentations (4 participants)

8. Consultations to term projects

9. Written test for 60 minutes (plus some presentations, if possible)

10. Project presentation (4 participants)

11. Project presentations (4 participants)

12. Consultations to the term projects

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

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

Cíle studia:

Students will acquire credits on the basis of term project and it consists of achieved results, the source code documentation, project presentation and the project functionality. There will be a written test in the term. The extent of the exam is given by contents of lectures.

Studijní materiály:

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

Poznámka:

https://cw.fel.cvut.cz/wiki/courses/a4m39dpg/start

Další informace:

https://cw.fel.cvut.cz/wiki/courses/b4m39dpg/start

Rozvrh na zimní semestr 2024/2025:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po	místnost KN:E-127 Havran V. 11:00–12:30 (přednášková par. 1) Karlovo nám. Kotkova cvičebna K4místnost KN:E-127 Havran V. 14:30–16:00 (přednášková par. 1 paralelka 101) Karlovo nám. Kotkova cvičebna K4
Út
St
Čt
Pá

Rozvrh na letní semestr 2024/2025:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Open Informatics - Computer Graphics (povinný předmět oboru)