Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
Webová stránka:
https://cw.fel.cvut.cz/wiki/courses/b4m39dpg/start
Anotace:
The course is designed to familiarize students with the data structures used in algorithms applied in computer graphics, particularly for search operations. Emphasis is placed on basic and hierarchical data structures for point and object data in 2D and 3D for the representation of spatial data, nearest neighbor search, and ray tracing. In the lab sessions, students work individually on a project to implement an algorithm in C++, gaining insight and experience in addressing a specific problem.
Cíle studia:
The aim of the course is to familiarize students with data structures used in computer graphics for 2D and 3D data, typically for search problems, and to gain both theoretical and practical experience in implementing a non-trivial algorithm—typically one that implements a hierarchical data structure—as well as in carrying out a project involving the study of the algorithm, its implementation, execution, debugging, testing, presentation, and documentation.
Obsah:
Students earn credits based on a semester-long project consisting of a theoretical presentation of an algorithm, implementation of the algorithm—including testing and debugging—documentation of the algorithm’s source code, a technical report, and a final presentation on their project. The written portion of the exam covers the material presented in the lectures.
Osnovy 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. | | Simple geometric entities and their representations |
| 4. | | Advanced geometric entities and their representations |
| 5. | | Incidence operations between entities used in computer graphics; the cost model. |
| 6. | | Point based representations and data structures |
| 7. | | Object based and image based representations in 2D and 3D |
| 8. | | Proximity search and its applications I. |
| 9. | | Approximate algorithms for nearest neighbor search, computer graphics usage |
| 10. | | Ray shooting and its applications I. |
| 11. | | Ray shooting and its applications II. |
| 12. | | Ray shooting and its applications III. |
| 13. | | High-dimensional search algorithms. |
| 14. | | Reserved. |
Osnovy cvičení:
| 1. | | Introduction to the lab, placement test. |
| 2. | | Overview of semester assignments. |
| 3. | | Students select homework assignments, consultation on homework assignments. |
| 4. | | Introduction to the C++ programming environment. |
| 5. | | Examples of incidence operations. |
| 6. | | Examples of incidence operations. |
| 7. | | Presentation of homework assignments (10 students) |
| 8. | | Presentation of homework assignments (10 students) |
| 9. | | Presentation of homework assignments, reserve time, consultation on semester projects. |
| 10. | | 60-minute written test. |
| 11. | | Consultations on semester projects. |
| 12. | | Demonstration presentations of homework assignments. (10 students) |
| 13. | | Demonstration presentations of homework assignments. (10 students) |
| 14. | | Reserve |
Literatura:
| 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 |
Požadavky:
Space and runtime complexity of algorithms, binary trees and heaps, tree balancing, search algorithms, priority queues, fundamentals of von Neumann architecture, and good knowledge of C++ basics. The knowledge of C++ will be checked during the first exercise.
Poznámka:
Klíčová slova:
sorting, searching, multidimensional data structures, objects representations, ray shooting, ray tracing, visibility computations, visibility culling
Předmět je zahrnut do těchto studijních plánů:
| Stránka vytvořena 12.7.2026 17:49:57, semestry: L/2029-30, Z,L/2027-8, L/2025-6, Z,L/2028-9, Z,L/2026-7, připomínky k informační náplni zasílejte správci studijních plánů |
Návrh a realizace: I. Halaška (K336), J. Novák (K336) |