Game Development Reference
In-Depth Information
Chapter 4
Building Procedural Geometry Using
MAXScript (Voronoi Polygons)
Alessandro Ardolino
Procedural geometry modeling is a smart solution for some tasks that are tedious from an artist's perspective, or as
sometimes happens, for a task that simply cannot be accomplished within a given production schedule. For example,
consider the task of building a complex set of shapes such as broken glass. For an artist, this modeling task would
be very time-consuming. A better solution might be to automate the process of building all the glass pieces while
retaining the old shape.
This chapter explains how to do just that using a technique that can be adapted to solve a wide variety of
problems. I will illustrate a way to create a complex polygon pattern using the powerful scripting tools provided
by 3ds Max. This versatile pattern is known as a Voronoi diagram
1
, named after Georgy Voronoy
2
, the Ukrainian
mathematician who defined it.
Please refer to the Wikipedia article for the formal definition of the diagram. For our purpose it will be defined as
Let P represent a set of sites p(x, y) in a 2D space: for each p in P, the Voronoi cell V(p) (or the Voronoi polygon) is
the region that contains all the points closer to p than all the other sites in P.
Using terms more common in the CG world, given a set of vertices in a 2D space, a Voronoi polygon is the one
built around a vertex including all of the 2D space closer to it than the other vertices. Figure
4-1
shows a common
Voronoi diagram.
