Subject description - A4M39DPG

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
A4M39DPG Data Structures for Computer Graphics
Roles:PO, V Extent of teaching:2P+2S
Department:13139 Language of teaching:CS
Guarantors:  Completion:Z,ZK
Lecturers:  Credits:6
Tutors:  Semester:L


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.

Study targets:

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.

Course outlines:

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. High-dimensional search algorithms.
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. Reserved.

Exercises outline:

1. Introduction to the exercises, description of homework projects
2. Selection of term projects + consultations
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 homework projects
9. Written test for 60 minutes (plus perhaps some presentations)
10. Project presentation (4 participants)
11. Project presentations (4 participants)
12. Consultation to the term projects.
13. Demonstration and evaluation of the projects (10x)
14. Demonstration and evaluation of the projects (10x)


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


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++.


Couse pages:



sorting, searching, multidimensional data structures, objects representations, ray shooting, ray tracing, visibility computations, visibility culling, collision detection.

Subject is included into these academic programs:

Program Branch Role Recommended semester
MPIB Common courses V
MPKME1 Wireless Communication V 2
MPKME5 Systems of Communication V 2
MPKME4 Networks of Electronic Communication V 2
MPKME3 Electronics V 2
MPKME2 Multimedia Technology V 2
MPEEM1 Technological Systems V 2
MPEEM5 Economy and Management of Electrical Engineering V 2
MPEEM4 Economy and Management of Power Engineering V 2
MPEEM3 Electrical Power Engineering V 2
MPEEM2 Electrical Machines, Apparatus and Drives V 2
MPOI4NEW Computer Graphics and Interaction PO 2
MPOI4 Computer Graphics and Interaction PO 2
MPKYR4 Aerospace Systems V 2
MPKYR1 Robotics V 2
MPKYR3 Systems and Control V 2
MPKYR2 Sensors and Instrumentation V 2

Page updated 10.8.2020 12:51:48, semester: Z,L/2020-1, L/2019-20, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)