Game Development Reference
In-Depth Information
Figure 4-5.
From left to right, the base mesh, the Delaunay triangulation mesh, and the resulting Voronoi diagram
What the Script Does
The script you are going to build will be composed of three main procedures and some utility functions:
fn_delaunayTriangulation
is the procedure used to create a random point distribution over
the XY plane, or, if a mesh is passed as an argument, inside its triangles using barycentric
coordinates. This function will return a triangulated mesh.
•
fn_voronoiDiagram
is the procedure used to derive the Voronoi diagram using the
triangulated Delaunay mesh.
•
ut_compareAngle
is a utility procedure used to find the right order in which to build each
Voronoi polygon.
•
ut_compareVx
is used to order the vertex array along the X axis.
•
ut_isTriangleContained
checks to see if a triangle is inside the Delaunay triangle array yet or
needs to be added.
•
ut_isInsideCircumcircle
checks to see if a vertex is inside a triangle's circumcircle.
•
Two simple data structures will be defined to help the computation:
struct triangle(p1,p2,p3)
to store triangle data
•
struct tEdge(p1,p2)
to store edge data during the swapping stage in the Delaunay
triangulation
•
The Code: Utility Functions and Data Structures
The Voronoi diagram computation code is based on two main procedures, one for the Delaunay triangulation and
one to achieve your diagram. But to get more readable and practical code, you need some utility procedures and
data structures. Two very simple data structures are used in the code, one storing a single triangle and one for the
triangle's edges:
struct triangle (p1,p2,p3)
defines a triangle
•
struct tEdge (p1,p2)
defines an edge, used to mark the triangle's edge to split
•