Triangulating N-Gons?

jonathon · 13 July 2022 08:08

I’m being lazy but do any of the connectors or libraries already have efficient routines for triangulating n-gons that we might find in Speckle Meshes?

It’s not important, but I’ll be implementing it in c++.

izzylys · 13 July 2022 10:02

heya!

I don’t think we’re necessarily wedded to these, but we do have triangulation implemented in both sharp and web:

here it is in sharp:

github.com

specklesystems/speckle-sharp/blob/main/Objects/Objects/Utils/MeshTriangulationHelper.cs

using System;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using Objects.Geometry;

namespace Objects.Utils
{
    /// <summary>
    /// Set of functions to triangulate n-gon faces (i.e. polygon faces with an arbitrary (n) number of vertices) in <see cref="Mesh"/>es.
    /// </summary>
    public static class MeshTriangulationHelper
    {
       
        /// <summary>
        /// Triangulates all faces in <paramref name="Mesh"/>.
        /// </summary>
        /// <param name="mesh">The mesh to triangulate.</param>
        /// <param name="preserveQuads">If <see langword="true"/>, will not triangulate quad faces.</param>
        public static void TriangulateMesh(this Mesh mesh, bool preserveQuads = false)
        {

This file has been truncated. show original

and here it is in web:

github.com

specklesystems/speckle-server/blob/main/packages/viewer/src/modules/converter/MeshTriangulationHelper.js

/**
 * Set of functions to triangulate n-gon faces (i.e. polygon faces with an arbitrary (n) number of vertices).
 * This class is a JavaScript port of https://github.com/specklesystems/speckle-sharp/blob/main/Objects/Objects/Utils/MeshTriangulationHelper.cs
 */
export default class MeshTriangulationHelper {
  /**
   * Calculates the triangulation of the face at given faceIndex.
   * @remarks This implementation is based the ear clipping method proposed by "Christer Ericson (2005) <i>Real-Time Collision Detection</i>.
   * @param {Number}   faceIndex      The index of the face's cardinality indicator `n`
   * @param {Number[]}   faces      The list of faces in the mesh
   * @param {Number[]}   vertices   The list of vertices in the mesh
   * @return {Number[]} flat list of triangle faces (without cardinality indicators)
   */
  static triangulateFace(faceIndex, faces, vertices) {
    let n = faces[faceIndex]
    if (n < 3) n += 3 // 0 -> 3, 1 -> 4

    //Converts from relative to absolute index (returns index in mesh.vertices list)
    function asIndex(v) {
      return faceIndex + v + 1

This file has been truncated. show original

note that I don’t think we’d call these “done” or perfect (found a bug somewhat recently that was promptly fixed ), but they are totally functional and useful

jonathon · 13 July 2022 10:16

Perfect! Wow, I was, even so lazy not to have found these.

Now all I have to do is remember all the c++ I haven’t touched since highschool

Jedd · 13 July 2022 14:01

Those triangulation functions are based on a textbook.

Christer Ericson (2005) - Real-Time Collision Detection
see page section 12.5.1 (pp. 498 - 500).

There are faster triangulation functions out there, but this one seems to serve our needs quite well for the applications that don’t support n-gons natively (unity, autocad, three.js)

If you decide to re-write this in C++, let me know if you need a hand!