preface.tex

\chapter*{Introduction}
\addcontentsline{toc}{chapter}{Introduction}
Destructible environment has been an amusing part of computer games since their beginning, from shooting through the simple bricks in Space invaders to blowing up buildings in the Battlefield series. Current development is trying to achieve highly realistic destruction effects by inventing and improving various simulation approaches of 2D and 3D destructible game worlds.

Despite the advances in the field, the excessive complexity of accurate physical simulation introduces a trade-off: To achieve sufficient performance required to satisfy real-time constraints of the game environment (most notably acceptable and consistent frame rate), the game developers are forced to relax their demands on realism, usually by simplifying the game environment and neglecting less-important aspects of physical simulation.

The goal of this thesis is to review current techniques used to simulate such environments, implement a simple game environment to test some of the approaches, and design and measure an approach applicable in the game environment that is based on a combination of the reviewed techniques.

\paragraph{Related work}
A large part of the research on the destructible environment is done commercially to be deployed in game titles; the thesis reviews a selection of those approaches. The commercial research is usually based on rigorous academic research of the basic algorithms required for the task, including various tessellations, convex decompositions, methods of physical simulation and geometric representation of solid objects. We specially refer to the work on dynamically destructible rigid-bodies (treated in detail in \cref{sec:methods}), boolean operations on meshes using Nef polyhedra \citet{nefpoly}, an approach based on discrete particle method focused on inner body stress simulation~\cite{edem}, and one based on Voronoi tessellation~\cite{nvidia}.

\paragraph{Approach}
As a main result of the thesis, we present an algorithm that computes a fracture of a 3D solid object using boolean operations on 3D objects and Voronoi tessellation. The algorithm is set into the environment of a simple physical simulation of objects of arbitrary shape and used to modify the objects in the case when a critical force is applied to them, \ie when they are shot by the player or when the simulation detects collisions with other objects.

The algorithm is similar to one described by \citet{nvidia}, with some improvements:
\begin{itemize}
\item We try to reuse currently available open-source libraries to implement primitive operations on 3D solids, which has influenced the internal representation of the objects (\eg the mesh representation used for rendering and model storage is different than the one required to run tessellations) and exact steps of the algorithms (\eg we use mesh subtraction instead of object reconstruction).
\item To hide the latency caused by fracturing-related computation, we offload it to other program threads and insert the result to the main simulation only as soon as the computation finishes. Without the drop in frame rate, the introduced delay is almost negligible from the user perspective.
\end{itemize}

Finally, the performance of the algorithm is measured on objects with varying complexity.

\paragraph{Thesis structure}
The thesis is organized as follows: \Cref{chapt:over} describes the techniques used in computer games and simulations, and focuses on several results of recent research. \Cref{chapt:technology} introduces open-source libraries and implementations of the 3D geometric algorithms that are required for the simulation. \Cref{chapt:Implementation} illustrates the design of our implementation and presents measurements of its performance. After conclusion we continue with two appendices: \Cref{app:guide} is a user guide for running the testing program, and \cref{app:implementation} provides some insight into the inner structure of the program.