How to get 4 corners of a of a mesh's surface (or a plane) that consists of many triangles?

Question

After using CSG my mesh gets messed up with lots of more vertices and faces than needed. The data provides all vertices in a single array without differentiating wether they are real corners or somewhere in the middle of the surface / plane. I made a simple fiddle to show an example.

https://jsfiddle.net/apbln/k5ze30hr/82/

geometry.vertices.push(

      new THREE.Vector3(-1, -1,  0),  // 0
      new THREE.Vector3( 1, -1,  0),  // 1
      new THREE.Vector3(-1,  1,  0),  // 2
      new THREE.Vector3( 1,  1,  0),  // 3

      new THREE.Vector3(-0.5, -0.5,  0),  // 4
      new THREE.Vector3( 0,  1,  0),  // 5
      new THREE.Vector3( 1, -1,  0),  // 6
        );

    geometry.faces.push(

         new THREE.Face3(0, 5, 2),
         new THREE.Face3(0, 1, 5),
         new THREE.Face3(3, 5, 1),

      );

This is a simplified version of how my surfaces look like after using csg. How could I possibly know which vertices are real corners, so that I could repair the surface with 2 faces only?

Answer 1

You could try detecting adjacent faces. If two faces share an edge and they are coplanar then they can be merged. This would be a slightly more general algorithm.

Skecth of algorithm would be to first build adjacency graph where each edge is linked to the faces adjacent to it. Then loop through the list of edges and detect those where the two adjacent faces are coplaner, if so merge the faces and adjust adajacency lists.

Its a bit more complex if you require a triangular mesh. Best aproach might be to first construct the mesh with non triangular faces and then split them into triangles.

Its a pretty common problem and there are no doubt libraries which can do it for you. This answer may help: ThreeJS: is it possible to simplify an object / reduce the number of vertexes?