Generate mesh faces for vertices in THREE.js

Question

I'm not sure if the answer is supposed to be blindingly obvious but it eludes me. I'm doing the 3D Graphics class on Udacity that uses three.js. I'm at a point where I'm required to generate a 3d mesh.

I've got the vertices all generating correctly, but I'm stuck at generating faces for them. I can't think of an obvious way to auto generate faces that don't overlap. I've searched and searched around the web but I can't find any information about it. I'm not sure if it's something stupidly obvious or just not very documented. Here's the code:

function PolygonGeometry(sides) {
    var geo = new THREE.Geometry();

    // generate vertices
    for ( var pt = 0 ; pt < sides; pt++ )
    {
        // Add 90 degrees so we start at +Y axis, rotate counterclockwise around
        var angle = (Math.PI/2) + (pt / sides) * 2 * Math.PI;

        var x = Math.cos( angle );
        var y = Math.sin( angle );

        // YOUR CODE HERE
        //Save the vertex location - fill in the code
        geo.vertices.push( new THREE.Vector3(x, y, 0) );
    }
    // YOUR CODE HERE
    // Write the code to generate minimum number of faces for the polygon.


    // Return the geometry object
    return geo;
}

I know the basic formula for the minimum number of faces is n-2. But I just can't think of a way to do this without faces overlapping. I don't want anyone to do my work for me, I want to figure it out myself as much as I can. But is there anyone who can point me in the right direction or give me a formula or something?

Answer 1

Assuming you are generating your vertices in a concave fashion and in a counterclockwise manner then if you have 3 sides (triangle) you connect vertex 0 with 1 with 2. If you have 4 sides (quad) you connect vertex 0 with 1 with 2 (first triangle) and then vertex 0 with 2 with 3. If you have 5 sides (pentagon) you connect vertex 0 with 1 with 2 (first triangle) then vertex 0 with 2 with 3 (second triangle and then vertex 0 with 3 with 4. I think you get the pattern.

Answer 2

You can automate your triangulation

For big polygons it can be quite a job to manually add the faces. You can automate the process of adding faces to the Mesh using the triangulateShape method in THREE.Shape.Utils like this:

var vertices = [your vertices array]
var holes = [];
var triangles, mesh;
var geometry = new THREE.Geometry();
var material = new THREE.MeshBasicMaterial();

geometry.vertices = vertices;

triangles = THREE.Shape.Utils.triangulateShape ( vertices, holes );

for( var i = 0; i < triangles.length; i++ ){

    geometry.faces.push( new THREE.Face3( triangles[i][0], triangles[i][1], triangles[i][2] ));

}

mesh = new THREE.Mesh( geometry, material );

Where vertices is your array of vertices and with holes you can define holes in your polygon.

Note: Be careful, if your polygon is self intersecting it will throw an error. Make sure your vertices array is representing a valid (non intersecting) polygon.