Triangulation of 3D points with K vertices per face

Question

I'm working with Three.js. I have a collection of 3D points (x, y, z) and a collection of faces. One face is composed of K points. It can be as well convex as concave. I found nothing that could help me in the Three.js documentation. One solution could be to triangulate those shapes, but so far I haven't found any simple 3D triangulation algorithm.

The other solution would be doing something like that :

var pointsGeometry = new THREE.Geometry();

pointsGeometry.vertices.push(new THREE.Vector3(10, 0, 0));
pointsGeometry.vertices.push(new THREE.Vector3(10, 10, 0));
pointsGeometry.vertices.push(new THREE.Vector3(0, 10, 0));
pointsGeometry.vertices.push(new THREE.Vector3(1, 3, 0));
pointsGeometry.vertices.push(new THREE.Vector3(-1, 3, 0));
pointsGeometry.vertices.push(new THREE.Vector3(10, 0, 0));

var material = new THREE.MeshBasicMaterial({color: 0x00ff00});

var mesh = new THREE.Shape/ShapeGeometry/Something(pointsGeometry, material);
group.add(mesh);

scene.add(group);

I have a lot of these shapes that build together a closed surface.

Any suggestion?

Thank you for your attention. Have a nice day.

Answer 1

As you pointed out, there are 2 ways to achieve that :

• use a 3D triangulation algorithm (not provided by Three.js) ;
• use the 2D triangulation algorithm normally used for Three.js Shape objects with some transformation applied upon each face of the geometry.

The last one seems cool but unfortunately, as I tried out I realized it's not that trivial. I came up with something similar to what Paul-Jan said :

For each face of your geometry :

1. Compute the centroid the face ;
2. Compute the face normal ;
3. Compute the matrix of the face ;
4. Project the 3D points onto the 2D plane of the face ;
5. Create the geometry (triangulated with the Shape triangulation algorithm) ;
6. Apply the face matrix to the newly created geometry
7. Create a Mesh and add it to an Object3D (I tried to merged all the geometries into 1, but it fails with the ShapeBufferGeometry)

Check this fiddle.

Be careful to the winding order of your vertices or put the THREE.Material.side to THREE.DoubleSide to prevent faces from being culled.