Best practice for triangulating meshes


#1

So I just wanted to start a discussion about how everyone infers the order of vertex triangulation which is required in the ‘faces’ array when creating a speckle mesh…

I’ve never seen this triangulation order stored in any of the file types I’ve been creating speckle streams out of, which also makes me wonder how other software platforms deal with this issue… Is there just some convention that I’m missing?

To date I just hard code the case for 3 and 4 sided surfaces, and then use an ear cut algorithm to figure it out for the rest. This works fine, but I’m curious about what others do here. Surely there’s a better way.


#2

If i remember correctly, there’s not much magic behind this; the face array of a classical SpeckleMesh from CoreGeometry is just

[ {0 or 1}*, vertexIndex, vertexIndex, vertexIndex, {0 or 1}*, vertexIndex, vertexIndex, vertexIndex, ... ]

*0 = triangle, so there’s an expected three vertex indexes afterwards, 1 = quad, four indexes expected afterwards.


#3

yeah I understand what it’s for/how it works. But it requires that you come up with an order in which to create these triangles that make up the mesh


#4

Which can be a kinda tricky thing to do with 3D coordinates


#5

Are you asking now about triangulation algorithms from a set of points, from scratch, are you? That’s a completely different discussion, possibly subject to quite a few phds and cgi articles :slight_smile:

Speckle usually deals with meshes from other software. It’s not a geometry kernel. Could you describe your use case a bit more?


#6

Yeah, that’s more or less what I’m talking about.

So I’ve written a couple of parsers/uploaders to go from gbxml to speckle, .sim to speckle and .idf to speckle. In all cases, the vertices are just given in sequence around the outside of the surface. So every time I’ve had to do the step of triangulating them in order to create the mesh.

I figured this would be something you’re always dealing with, so you’d probably have some good ideas about how it’s best done.


#7

This is a bit of a tangential sidenote, but an adjustment I wouldn’t mind seeing is that instead of 1 and 0 to denote quads and tris, perhaps that could just be extended to general polygons/ngons by just indicating how many verts the polygon has. For quads and tris this wouldn’t make a difference in terms of data - just using 3 and 4 instead of 0 and 1 - but would also allow handling ngons.

For example, Blender directly uses ngons and triangulates them on the fly / for rendering.


#8

That’s a good shout! Generally speaking the speckle core geometry doesn’t prevent you from doing this already; blender to blender you can, most likely, ship n-gon meshes.

The problem will be implementation in things that do not support ngons - mainly threejs, dynamo, revit, grasshopper/rhino; herein probably we need the ToNative methods for all these host apps to triangulate on the fly the face.


#9

Yes, but as a “Speckle standard”, the 0 and 1 method is currently how things are passed around, so it just needs to be changed to 3 and 4. Platforms that cannot support ngons / polygons would just skip them.

Apologies, @tluther, for the digression…


#10

Gotcha. If you flag an issue on SpeckleCoreGeometry I’ll find a place for you to crash at the meetup, and have a dedicated drinks stand :sunglasses: It will take a while to implement and check, but at least we’ll remember this way.

Re the original thread of the topic from @tluther, i’m not familiar with those formats. The only thing i can say is that I have never had to deal with triangulating things myself as Speckle always relied on the host application’s mesh data structures to provide a face array too. Easy life :tropical_drink: Consequently, I’m no better than a google search…


#11

yeah fair enough. I just wasn’t sure if there was a simpler way which I was just missing… My current method of projecting the vertices to a 2D space and applying a 2D earcut triangulation seems to always get the right results as far as I’ve tested. But it just feels a bit hacky…


#12

A post was split to a new topic: STL parsing: face interpretation