# triangulate

Is there a particular sequence in the creation of the vertices for the mesh? For a triangle everything is nice, but how does it work for a polygon having N=6 vertices as defined by the user? I figured out that the triangulate() generates 3+(3*(N-3)) vertices in sum. But the sequence (order) is a bit a secret to me. In case I would like to get an interpolated color fill, I need to assign each vertex a dedicated color. But I need to assign those colors to the vertices generated by the triangulate() command, and in doing so I need to know the correct sequence beforehand … I am sure somebody can help me out here?!

@CrazyEd… John’s code doesn’t help?

http://twolivesleft.com/Codea/Talk/discussion/544/polygon-editing-example-with-physics

@Blanchot: partly. But John uses one unique color, and I know you can render also with same beautiful colors as for the triangle mesh example. Its just you need to assign the colors properly, and this is the tricky part. For four, five, six vertices specified, I can perform a trial and error, but for more this will become tedious. I guess I just need to know, in which order the additional vertices are created, so that the color asignment works properly …

I’ll compile a short example, that explains better the issue I do have.

``````function setup()
print("Hello Mesh!")
verts = {}
vertcolor = {}

verts[1] = vec2(600,400)
verts[2] = vec2(600,100)
verts[3] = vec2(100,100)
verts[4] = vec2(100,600)

-- the colors for the vertices need to be multiple of three. So if we do
-- have four vertices, we must specify 6. Two vertices are used twice ...
vertcolor[1] = color(255,0,0,255)
vertcolor[2] = color(255,255,0,255)
vertcolor[3] = color(0,255,255,255)
vertcolor[4] = color(0,225,255,255)
vertcolor[5] = color(255,225,0,255)
vertcolor[6] = color(225,0,0,255)

any = mesh()

any.vertices = triangulate(verts)
--any:setColors(255,0,0,255)
any.colors = vertcolor

-- number of created vertices is (user defined ==> created by command triangulate)
-- 3 vertices ==> 3 vertices
-- 4 vertices ==> 6 vertices
-- 5 vertices ==> 9 vertices
-- N vertices ==> 3 + 3*(N-3) vertices

print("Number of created vertices: " .. tostring(#any.vertices))
for i=1, #any.vertices do
print(tostring(i)..": ",any.vertices[i].x, any.vertices[i].y)
end

-- Here we create a second mesh, just a single triangle
triMesh = mesh()

-- This is an array of colours we'll assign to the triMesh vertices
triCol = { color(255, 0, 0, 255),
color(255, 0, 0, 255),
color(0, 100, 255, 255)}

-- Set the font for rendering instructions
fontSize(32)
end

-- This function gets called once every frame
function draw()
-- Dark background color
background(20, 20, 40)
fill(255)
text("Drawing Primitives", WIDTH/2, HEIGHT - 25)
noFill()

-- Draw the triMesh
-- Move to the middle of the screen
pushMatrix()
translate(WIDTH/2, HEIGHT/2)

triMesh.vertices = { vec2(-200,-200),
vec2(200,-200),
vec2(0,200) }
triMesh.colors = triCol
triMesh:draw()

popMatrix()
stroke(255,0,0,255)
--any.colors = vertcolors
any:draw()
end

``````

So part of the polygon consisting of four vertices is interpolated with respect to colors, but the colors do not match, since my color definition towards the vertices is wrong.

I think the only way to know is to loop over both and match the coordinates. In the following example I color the vertices of each triangle in the mesh with red, green and blue respectively, so you can see the triangulation in action. As the y-coordinate of one of the vertices changes you can see how the triangulation needs to change as well.

``````function setup()
print("Let's triangulate!")
verts = {}
vertcolor = {}

verts[1] = vec2(600,400)
verts[2] = vec2(600,100)
verts[3] = vec2(100,100)
verts[4] = vec2(100,600)
verts[5] = vec2(300,300)

for i=1,3*#verts - 6,3 do
vertcolor[i] = color(255, 0, 0, 255)
vertcolor[i+1] = color(0, 255, 0, 255)
vertcolor[i+2] = color(0, 0, 255, 255)
end

any = mesh()

any.vertices = triangulate(verts)
any.colors = vertcolor

fontSize(32)
h=0
end

function draw()
-- Dark background color
background(0, 0, 0, 255)
fill(255)
text("Triangulate in action", WIDTH/2, HEIGHT - 25)

verts[5]=vec2(300,200+math.abs(h-450))
any.vertices = triangulate(verts)
any:draw()
h=(h+1)%900
end

``````

@Herwig: thanks for this nice demo! I guess I still need to play around with it. Looping both seems to be one way to sort things out, but is this the only one? Just remembered that John was writing in his Physics2 example, the points need to be entered clockwise.

Edit: tried that, but I guess this gives no clear result. So sorting seems to be the only way. Thanks again, @Herwig, this example is really great for understanding the mesh family.

Maybe this is already a helpful hint to get the sequence correct? This rendering is really fast… Tried that with explicit functions before (colormap, combined with interpolation) and this was horrific slow.

@CrazyEd
The issue with triangulate is a bit of an oversight. I was originally going to have it return the indices for the triangle rather than the points directly but the functionality provided by Box2D’s triangulator was a bit limited. I’m going to be adding a better version of it that supports both clockwise and counter-clockwise as well as holes and constraint vertices. I’ll also add a version that returns indicies rather than points so you can use them for colors / texture coordinates and whatnot.

Looking forward to that @John!

Thanks a lot @John!

@John any news on this?

@Simeon do you know if there is any progress on improving the triangulate function, returning indices as well?

We can probably put in the indicies feature next release of the one after. Some other features have been taking priority.

Great! Thanks @John!

@John, may I ask you a question related to `triangulate()` and `physics.body(POLYGON, ...)`?

I’ve read on this forum that `triangulate` needs the input points to be in a clockwise order. (I’ve been working on some code that falls over with four points in a counter-clockwise order.)

There is also a comment in the Physics Lab example project code that reads: “-- polygons are defined by a series of points in counter-clockwise order”.

That appears to imply, in order to use the two together, I have to hold the points of a polygon in the two different orders. Is that right?

I think I’ve answered my question with the code below: if `triangulate` does not work in one direction, I call it again with the order of the points reversed. (Update) This does not work in every case; see my later comment.

``````
-- User the slider to set the number of sides of the polygon.
-- Tap the viewer to set the location of each vertex in turn,
-- clockwise or counter-clockwise. Tap the viewer one last time
-- to triangulate the polygon. It is over when all done.
--
supportedOrientations(LANDSCAPE_ANY)

CREATING = 0
BREAKING = 1

function setup()
points ={}
bodies = {}
iparameter("MaxNumber", 3, 12, 6)
state = CREATING
CCW = false
end

local m
function draw()
background(0)
if state == CREATING and #points > 0 then
fill(255, 0, 0)
for i = 1, #points do
local p = points[i]
local x = p.x
local y = p.y
ellipse(x, y, 10)
end
if #points > 2 then
local t
if not CCW then
t = triangulate(points)
else
t = triangulate(reverse(points))
end
if not t then -- Try the opposite direction...
CCW = true
t = triangulate(reverse(points))
end
if not m or m.size ~= #t then
m = mesh()
m.vertices = t
end
if m then
fill(127, 0, 127)
m:draw()
end
end
stroke(255)
strokeWidth(5)
for i = 2, #points do
local p1 = points[i - 1]
local p2 = points[i]
line(p1.x, p1.y, p2.x, p2.y)
end
if #points < maxNumber then
stroke(127)
end
if #points > 2 then
local p1 = points[#points]
local p2 = points[1]
line(p1.x, p1.y, p2.x, p2.y)
end

elseif state == BREAKING then
sleeping = true
for i = 1, #bodies do
if bodies[i] then
pushMatrix()
translate(bodies[i].x, bodies[i].y)
rotate(bodies[i].angle)
local m = mesh()
local p = bodies[i].points
m.vertices = p
fill(0, 192, 192)
m:draw()
stroke(255)
for j1 = 1, 3 do
local j2 = j1 % 3 + 1
local p1 = p[j1]
local p2 = p[j2]
line(p1.x, p1.y, p2.x, p2.y)
end
popMatrix()
sleeping = sleeping and not bodies[i].awake
if bodies[i].y < - HEIGHT then
bodies[i]:destroy()
table.remove(bodies, i)
end
end
end
if sleeping then
fill(255)
font("Inconsolata")
fontSize(72)
text("All Done", WIDTH/2, HEIGHT/2)
end
end
end

function touched(touch)
if touch.state == BEGAN and state ~= BREAKING then
if #points == 0 then
maxNumber = MaxNumber
end
if #points == maxNumber then
state = BREAKING
local t
if not CCW then
t = triangulate(points)
else
t = triangulate(reverse(points))
end
for i = 1, #t, 3 do
local c = (t[i] + t[i+1] + t[i+2])/3
local body = physics.body(POLYGON,
t[i] - c,
t[i+1] - c,
t[i+2] - c)
body.position = c
table.insert(bodies, body)
end
ground = physics.body(POLYGON,
vec2(0, 0),
vec2(0, -20),
vec2(WIDTH, -20),
vec2(WIDTH, 0))
ground.type = STATIC
return
end
local p = vec2(touch.x, touch.y)
table.insert(points, p)
end
end

function reverse(array)
local newarray = {}
local n = #array
for i = 1, n do
newarray[i] = array[n - i + 1]
end
return newarray
end

``````

The code in my comment above does not work in every case, because `triangulate()` can ‘fail’ without returning a `nil` value. The code below uses an over-written version of `triangulate()` that, I believe, avoids the problems. I have added a page to the wiki here that covers this.

``````
-- User the slider to set the number of sides of the polygon.
-- Tap the viewer to set the location of each vertex in turn,
-- clockwise or counter-clockwise. Tap the viewer one last time
-- to triangulate the polygon. It is over when all done.

-- A helper function to calculate the 'signed' area of a polygon
local function area(p)
local a = 0
for i = 1, #p do
local p1 = p[i]
local p2 = p[i % #p + 1]
a = a + p1:cross(p2)
end
return a/2
end

-- A helper function to reverse the order of an array
local function reverse(a)
local ra = {}
local n = #a
for i = 1, n do
ra[i] = a[n - i + 1]
end
return ra
end

-- Extend the triangulate() function
local oldtriangulate = triangulate -- Preserve original triangulate()
triangulate = function (points)
if area(points) > 0 then                   -- Counter-clockwise?
return oldtriangulate(reverse(points)) -- Reverse
else
return oldtriangulate(points)
end
end

supportedOrientations(LANDSCAPE_ANY)

CREATING = 0
BREAKING = 1

function setup()
points ={}
bodies = {}
iparameter("MaxNumber", 3, 12, 6)
state = CREATING
end

local m
function draw()
background(0)
if state == CREATING and #points > 0 then
fill(255, 0, 0)
for i = 1, #points do
local p = points[i]
local x = p.x
local y = p.y
ellipse(x, y, 10)
end
if #points > 2 then
local t = triangulate(points) -- Uses enhanced triangulate()
if not m or m.size ~= #t then
m = mesh()
m.vertices = t
end
if m then
fill(127, 0, 127)
m:draw()
end
end
stroke(255)
strokeWidth(5)
for i = 2, #points do
local p1 = points[i - 1]
local p2 = points[i]
line(p1.x, p1.y, p2.x, p2.y)
end
if #points < maxNumber then
stroke(127)
end
if #points > 2 then
local p1 = points[#points]
local p2 = points[1]
line(p1.x, p1.y, p2.x, p2.y)
end

elseif state == BREAKING then
sleeping = true
for i = 1, #bodies do
if bodies[i] then
pushMatrix()
translate(bodies[i].x, bodies[i].y)
rotate(bodies[i].angle)
local m = mesh()
local p = bodies[i].points
m.vertices = p
fill(0, 192, 192)
m:draw()
stroke(255)
for j1 = 1, 3 do
local j2 = j1 % 3 + 1
local p1 = p[j1]
local p2 = p[j2]
line(p1.x, p1.y, p2.x, p2.y)
end
popMatrix()
sleeping = sleeping and not bodies[i].awake
if bodies[i].y < - HEIGHT then
bodies[i]:destroy()
table.remove(bodies, i)
end
end
end
if sleeping then
fill(255)
font("Inconsolata")
fontSize(72)
text("All Done", WIDTH/2, HEIGHT/2)
end
end
end

function touched(touch)
if touch.state == BEGAN and state ~= BREAKING then
if #points == 0 then
maxNumber = MaxNumber
end
if #points == maxNumber then
state = BREAKING
local t = triangulate(points) -- Uses enhanced triangulate()
for i = 1, #t, 3 do
local c = (t[i] + t[i+1] + t[i+2])/3
local body = physics.body(POLYGON,
t[i] - c,
t[i+1] - c,
t[i+2] - c)
body.position = c
table.insert(bodies, body)
end
ground = physics.body(POLYGON,
vec2(0, 0),
vec2(0, -20),
vec2(WIDTH, -20),
vec2(WIDTH, 0))
ground.type = STATIC
return
end
local p = vec2(touch.x, touch.y)
table.insert(points, p)
end
end

``````