Wiki

Clone wiki

Core / triangulate

Back to Beyond the Codea in-app reference


FunctionIconFunction-Small.png triangulate() function

Introduction

The 'Shaders & Mesh' chapter of Codea's in-app reference documents most of the triangulate(points) function. The function takes an array of vec2 values representing the vertices of a polygon (points) and returns a table (an array) of vec2 values representing the vertices of triangles which together comprise the polygon.

Order of the vertices

From Codea version 1.5, the array of vec2 values representing the vertices of the polygon can be in a clockwise or anti-clockwise order. Before version 1.5, the order of the vertices was important. For example:

-- 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

function setup()
    local pCW = {             -- A 100 x 100 'C', in clockwise order:
    vec2(0, 0),               -- 2--------------3
    vec2(0, 100),             -- |              |
    vec2(100, 100),           -- |  5-----------4
    vec2(100,75),             -- |  |
    vec2(25,75),              -- |  |
    vec2(25,25),              -- |  |
    vec2(100,25),             -- |  6-----------7
    vec2(100, 0)              -- |              | 
    }                         -- 1--------------8

    local pCCW = reverse(pCW) -- Counter-clockwise
    
    print("-- Clockwise --")
    local tCW = triangulate(pCW)
    for i = 1, #tCW, 3 do
        local p = {tCW[i], tCW[i+1], tCW[i+2]}
        print(unpack(p))      -- Outputs: six triangles
    end
    
    print("-- Counter-clockwise --")
    local tCCW = triangulate(pCCW)
    for i = 1, #tCCW, 3 do
        local p = {tCCW[i], tCCW[i+1], tCCW[i+2]}
        print(unpack(p))      -- Outputs: same six triangles
    end
end

Any triangles returned by the triangulate() function are themselves in a counter-clockwise order.

Detecting the order of polygon vertices

A polygon with vertices in a counter-clockwise order has a positive 'signed' area and a polygon with vertices in a clockwise order has a negative 'signed' area. The code below returns the 'signed' area of a polygon:

-- A helper function to calculate 'signed' area of a polygon
local function area(p)
    local a = 0                  -- will hold 'signed' area
    for i = 1, #p do             -- iterate through vertices
        local p1 = p[i]
        local p2 = p[i % #p + 1] -- if i < #p then i % #p + 1 is i + 1
                                 -- if i = #p then i % #p + 1 is 1
        a = a + p1:cross(p2)     -- p1:cross(p2) is x1y2 - x2y1
    end
    return a/2
end

Updated