Game Development Reference
In-Depth Information
else
(
m1 = - (t.p2.x-t.p1.x) / (t.p2.y-t.p1.y)
m2 = - (t.p3.x-t.p2.x) / (t.p3.y-t.p2.y)
mx1 = (t.p1.x + t.p2.x) / 2.0
mx2 = (t.p2.x + t.p3.x) / 2.0
my1 = (t.p1.y + t.p2.y) / 2.0
my2 = (t.p2.y + t.p3.y) / 2.0
circumCircle.x = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2)
circumCircle.y = m1 * (circumCircle.x - mx1) + my1
)
--check on distances and circumcircle radius
dx = t.p2.x - circumCircle.x
dy = t.p2.y - circumCircle.y
rsqr = dx*dx + dy*dy
circumCircle.z = sqrt(rsqr) --radius
dx = p.x - circumCircle.x
dy = p.y - circumCircle.y
drsqr = dx*dx + dy*dy --point distance
if(drsqr <= rsqr) then return true
)
The
ut_isInsideCircumcircle
procedure checks to see if point p is inside the t triangle and stores the
circumcircle attributes in the circumcircle variable. The & before a variable means that its value will be modified by
the function. After a check for a degenerate triangle, the function finds the circumcircle for the current triangle, and
using simple distance checks, discovers whether the passed vertex is inside or outside the circle. The circumcircle
variable is a simple vector using its x and y components to store circumcircle center 2D coordinates and the
z component to store the circumcircle radius. A degenerate triangle has collinear vertices; it is basically a segment.
The Code: the Delaunay Triangulation
This function starts from a mesh, and procedurally adding vertices inside its triangles (to get more interesting
Delaunay meshes from simple objects) finds the triangulation solution; it uses the barycentric coordinate system
to create more vertices inside a single triangle, expressing them based on an interpolation of the triangle's vertices
coordinates. After generating the right set of vertices, a big triangle surrounding all the vertices is created, and vertex
by vertex, a contain-check is performed. At this stage, new triangles are added to the Delaunay set and some are
deleted, too.
For readability, I will examine the Delaunay triangulation function code in sections, starting with Listing 4-1.
Listing 4-1.
The First Section of the Delaunay Triangulation Function Code
function fn_delaunayTriangulation vNumber baseMesh =
(
--the triangles created during the triangulation
local delunayTriangles = #()
--contains the vertices to triangulate
local vertices = #()
