Game Development Reference
In-Depth Information
Figure 4-1.
A Voronoi diagram
In nature, the Voronoi diagram can be seen on a turtle's carapace, a giraffe's skin, the cracks in dried mud,
and much more. There are many applications of this pattern in the CGI field, from procedural texture creations to
fracturing object simulations.
MAXScript and the Sample Code
MAXScript, the built-in scripting language for Autodesk 3ds Max, provides a number of methods to interact with mesh
nodes. These are contained in the
meshOp
struct, and in the sample code they are used to get/set information from/
to the meshes. The
snapshotAsMesh
command returns a mesh copy of the argument; in my example, it will be used
both for performance and for practical matters. MAXScript works faster with Editable Meshes than Editable Polys;
another advantage of Editable Meshes is that they provide access to the explicit triangles of the object. To improve
the performance of the script, the
suspendEditing()
and
resumeEditing()
methods, which disable the Modify
Panel interface during execution, will be used. In MAXScript, custom-generated meshes are created using the
mesh()
command with two arrays as its arguments: an array of vertices and an array of faces.
Voronoi and Delaunay
To generate a Voronoi diagram, the sample code uses a property of the Delaunay triangulation. Given a set of vertices,
P, it's a Delaunay triangulation, DT(P), if no point of this set is inside the circumcircle
3
of any triangle of DT(P).
Figures
4-2
through
4-4
illustrate this process (source:
en.wikipedia.org/wiki/Delaunay_triangulation
).
