
Voronoi diagramy koulí v E3
Maňák, Martin ; Zemek, Josef (referee) ; Kolingerová, Ivana (advisor)
Voronoi diagrams (VD) describe spatial relationships among a given set of input sites. The family of VD for a set of points is a wellexplored domain and e ective algorithms for their construction exist. Although the family of VD for a set of spheres has been known for many years, properties of these diagrams and algorithms for their construction are a relatively new thing. Their importance grows with the development in the area of molecular biology. The goal of this work is to survey the theory behind VD of spheres, implement one of the existing algorithms for their construction as a library and use the library on a real data, such as proteins.


Modelling of terrain and its modifications
Danihelka, Jiří ; Vaněček, Pavel (referee) ; Kolingerová, Ivana (advisor)
This thesis is about intuitive terrain modeling for needs of computer games. The thesis is searching for a method of terrain modeling that will be easy for people with lack of experience. The method also should be able to allow powerful modeling techniques for professionals game creators. The thesis debate about choosing appropriate method and compare different methods between each other. Selected is the method of moving control points of Bezier patches. The thesis presents a program Terrain Editor that was created as part of the thesis. The program implements selected method and demonstrates its use in practice.


Rekonštrukcie povrchov z neparalelných rezov s použitím interpolačných metód
Ilavský, Ján ; Kolingerová, Ivana (referee) ; Felkel, Petr (advisor)
Reconstruction from nonparallel crosssections is not very well studied problem. This work provides overview of methods used to solve it. Step by step there are described all the algorithms from obtaining input data to visualize reconstructed surface. Main focus is put on methods which create distance function interpolating data from crosssections. The closest point, average normal and discguided interpolation are described in details. Out of visualization techniques there are mentioned straight methods and defined in detail marching cubes, marching tetrahedra and regularized marching tetrahedra. All this methods are implemented and used in windows application to compare their results in reconstruction of models saved in ASE format. First of all this model is cut into several crosssections inside this application. These are used to create distance function using one of the interpolation methods. At the end, distance function is visualized. To compare results, there is used volume computing algorithm based on raycasting and subjective user opinion based on graphical output.

 

Tetrahedrization as an alternative to volume data
Varga, Martin ; Kohout, Josef (referee) ; Kolingerová, Ivana (advisor)
Main goal of the thesis was to research or propose a suitable method for substitution of volume data including volume data derived from motion pictures by irregular tetrahedronbased grids. The method should minimize the loss of information and the size of the data. The thesis proposes a method for finding a suitable tetrahedron grid that substitutes the volume data without assuming anything about its inner structure. The proposed method can be applied on both volume data and volume data from motion pictures. The method consists of two steps. First a basic grid is generated by a simple incremental algorithm and then it is improved by a process of simulated annealing. The thesis proposes an unbiased measure for measuring the loss of information and evaluates the suitability of the proposed method for both types of data based on experiments. The thesis includes an implementation of the proposed method which demonstrates its use. The thesis also includes sample volume data and motion picture volume data which were used to test the suitability of the method.


Modelling of deformations of geometric objects
Kratochvíl, Erik ; Pelikán, Josef (referee) ; Kolingerová, Ivana (advisor)
Deformable models have been widely studied by the CG community for more than two decades. Many issues had to be addressed and many problems had to be solved before the quality of the deformable models reached an acceptable level. The aim of the work is to simulate interactions of several deformable bodies in realtime. First, we unveil the basic ideas behind several deformable models created for solids represented by a surface or volumetric mesh. We prefer the physicallybased approaches as they tend to yield more convincing results. We consider elastic materials only. We also briefly discuss the topic of collision detection for deformable models with its speci c aspects. A special attention is paid to contact resolution because it greatly influences the final impression. The result of this thesis is an overview of the proposed algorithm, detailed description of its parts, and its implementation. We also perform several benchmarks to prove its applicability in virtual environments and its capability to run in realtime.


Pseudotriangulations and their use in applied computational geometry
Trčka, Jan ; Kolcun, Alexej (referee) ; Kolingerová, Ivana (advisor)
This thesis shows fundamental properties of pseudotriangulation, its use as a planar tesselation and implementation of minimal pseudotriangulation algorithm, which has triangulation as its input. Furthermore, this thesis examines usability of a walking algorithm and two versions of algorithm are proposed. The walking algorithm is also used in an incremental algorithm for a pseudotriangulation construction. All proposed algorithms have been verified with implementation and experiments.

 

Minimum Weight Triangulation (MWT)
Charvát, Pavel ; Kolingerová, Ivana (advisor) ; Ferko, Andrej (referee)
For a long time, it has been neither known whether MWT is solvable in a polynomial time nor whether it belongs to NP. As we now, its status still remain unknown. We present severalknown approaches to MWT such as modifications of the problem with known time complexity or various heuristics and approximations which allow us to find an exact or at least an approximate solution in a reasonable time. We compare the approximations in some particular situations. The main part of the work is devoted to a description and implementation of an efficient heuristic with (almost?) linear expected complexity for points uniformly distributed in some convex shape. The algorithm is a modification of Drysdale's algorithm for finding GT candidates and Beurouti's computation of the modified LMTskeleton, where we add some proofs of the correctness. We are able to complete MWT from the graph of candidate edges in O(n · d3 + n · d2+k), where d is the the maximum degree and k is the maximum number of inner components of some skeleton face. Further, we suggest a new approximation of MWT with polynomial complexity in the worst case and (almost?) linear expected complexity, which only rarely differs from the optimal triangulation and has O(1) approximation factor in the worst case. This approximation combines the LMTskeleton...
