Game Development Reference
In-Depth Information
t = triangle ee.p1 ee.p2 p
append delunayTriangles t
)
)
--remove the supertriangle and its vertices
for i=delunayTriangles.count to 1 by -1 do
(
t = delunayTriangles[i]
if (t.p1 == superTriangle.p1 or t.p2 == superTriangle.p2 or t.p3 == superTriangle.p3 or
t.p1 == superTriangle.p1 or t.p2 == superTriangle.p3 or t.p3 == superTriangle.p2 or
t.p1 == superTriangle.p2 or t.p2 == superTriangle.p3 or t.p3 == superTriangle.p1 or
t.p1 == superTriangle.p2 or t.p2 == superTriangle.p1 or t.p3 == superTriangle.p3 or
t.p1 == superTriangle.p3 or t.p2 == superTriangle.p1 or t.p3 == superTriangle.p2 or
t.p1 == superTriangle.p3 or t.p2 == superTriangle.p2 or t.p3 == superTriangle.p1
) then
deleteItem delunayTriangles i
)
-------------------
-- continue below
-------------------
Using the
compare
utility function, the vertex array is sorted along the X axis. Next, the bounding box of all the
vertices is computed and a super-triangle surrounding the set of all the vertices is generated. One by one, all the
vertices are compared to the triangles currently inside the triangulation set, and based on the inside-circumcircle
check, new triangles are added or the existing ones are modified. At the end of this process, the super-triangle is
deleted from the Delaunay set (see Listing 4-3).
Listing 4-3.
The Final Delaunay Mesh
-------------------
-- continue above
-------------------
--create a mesh to see the results
for t in delunayTriangles do
(
v=#()
append v t.p1
append v t.p2
append v t.p3
f=#([1,2,3])
mm = mesh vertices:v faces:f
mm.name = uniqueName "tri_000"
)
--select all the tri meshes and attach them to a void mesh
delaunayMesh = editable_mesh()
delaunayMesh.name = uniqueName "delaunayMesh_"
deselect $*
for i in $*tri_* do
meshop.attach delaunayMesh i
