3D Polygonal Mesh Fracture Plugin: A Tetrahedra Clustering Approach

Abstract

Nowadays GPUs and CPUs are getting faster and faster, it is reasonable to assume that many algorithms that used to take long times to complete and were impossible to contemplate in games like water simulations, dynamic lighting, etc. Now, due to the improvements in current technologies and new technologies in general, they could be a standard in the industry, which is what has happened for many of those algorithms. However, this seems not to be the case of fracture effects, since it is rarely seen as a feature in video games or in video games development tools. Algorithms exist that have the potential to create a dynamic fracture in real time. This project emerges from the need to create an extension of a commercial game engine to help new game developers incorporate a fast, robust and aesthetic fracture that is customizable in their games so that better game play sensation is achieved. For this purpose, an extensive research on different methodologies to achieve the fracture effect has been carried on, among all the techniques studied the Delaunay triangulation in 3D, that fills the inside of a model with tetrahedra, was chosen because of its potential. Our fracture simulation approach consists in, given an impact point, grouping the tetrahedra according to how much of the impact they receive. The tetrahedra that receive the greatest impact are grouped into a new object and other groups are formed with the rest of the tetrahedra according to whether they are left disconnected or not after withdrawing the tetrahedra that received the greatest impact. After creating the groups the physics engine is in charge of simulating their behavior as rigid bodies. To create the triangulation, a state of the art library that uses an hybrid CPU GPU approach to the problem is modified and integrated with the game engine. For the sake of the speed of the fracture process new methodologies are developed in order to perform fast queries to know whether a point is outside or inside a polygonal model. This queries help to quickly create the constrained Delaunay Triangulation of the existing Delaunay Triangulation. In order to perform our fracture effect in a way that can be handled by the CPU, different ways of grouping the existing tetrahedra into chunks were implemented: one fast but less precise algorithm and a slower but more appealing algorithm. Those chunks are then configured to be simulated by the physics engine. The final result is a plugin for a commercial game engine that creates the fractured version of a model in a real time fashion that is customizable and has great potential and implications in the video game development field.