Provide indices

[promontis]

Hey @vpenades !

I'm currently porting some code from BabylonJS's polygonMesh class to C#, actually this piece of code here: https://github.com/BabylonJS/Babylon.js/blob/8aae1ec1c954c8e7a5dd5062dfabf33334db437b/src/Meshes/polygonMesh.ts#L245

It is extruding a polygon. They set positions, normals, uvs and indices.

From what I understand, the MeshBuilder allows us to use VertexPositionNormal (positions and normals), but that does not include indices. Is there any way to provide indices in the MeshBuilder? Or could you perhaps point me in the right direction?

Thnx,

Michel

[vpenades]

Hi @promontis

If you want to use positions, normals and uvs; var newMesh = new MeshBuilder<VertexPositionNormal,VertexTexture1,VertexEmpty>();

MeshBuilder does use indices internally, but it uses a dictionary to cache the vertices, so every vertex can only be used once.

Let's say you have source list of vertices, normals, and UVs, and another list with triangle indices... in order to add the triangles to a MeshBuilder you would do something like this:

List<Vector3> srcPositions;
List<Vector3> srcNormals;
List<Vector2> srcTexCoords;
List<int> srcIndices;

var dstMesh = new MeshBuilder<VertexPositionNormal,VertexTexture1,VertexEmpty>();

for(int i=2; i < srcIndices.count; i+=3)
{
    var idx0 = srcIndices[i-2];
    var idx1 = srcIndices[i-1];
    var idx2 = srcIndices[i-0];

    var a = new VertexBuilder<VertexPositionNormal,VertexTexture1,VertexEmpty>( ( srcPositions[idx0], srcNormals[idx0] ), srcTextures[idx0] );
    var b = new VertexBuilder<VertexPositionNormal,VertexTexture1,VertexEmpty>( ( srcPositions[idx1], srcNormals[idx1] ), srcTextures[idx1] );
    var c = new VertexBuilder<VertexPositionNormal,VertexTexture1,VertexEmpty>( ( srcPositions[idx2], srcNormals[idx2] ), srcTextures[idx2] );

    dstMesh.UsePrimitive(material).AddTriangle(a, b, c);
}

You'll notice it is quite verbose, that's why I use lots of usings in my examples... in fact you can do:

using VERTEX = VertexBuilder<VertexPositionNormal,VertexTexture1,VertexEmpty>;

var dstMesh = VERTEX.CreateCompatibleMesh();

var a = new VERTEX( ( srcPositions[idx0], srcNormals[idx0] ), srcTextures[idx0] );
var b = new VERTEX( ( srcPositions[idx1], srcNormals[idx1] ), srcTextures[idx1] );
var c = new VERTEX( ( srcPositions[idx2], srcNormals[idx2] ), srcTextures[idx2] );

dstMesh.UsePrimitive(material).AddTriangle(a, b, c);

Finally, if what you're trying to do is to be able to fill a mesh N-Vertex polygons, I would suggest you to look at Geometry/Triangulation.cs , so you can write your own implementation of IPolygonTriangulator so you could use MeshBuilder.AddPolygon instead.

[promontis]

Mmm... that IPolygonTriangulator sounds interesting! The BabylonJS code uses https://github.com/mapbox/earcut for triangulation and I've already found a port for c# here https://github.com/oberbichler/earcut.net/blob/master/src/Earcut.cs.

Is that something we could add to this library? Say EarcutPolygonTriangulator? You would need to add a holes parameter though.

Furthermore, I think those indices in the BabylonJS code are indeed triangle indices. Perhaps it's better to just port the code, and use AddTriangle() instead of AddPolygon().

[vpenades]

Yes, the idea is to have a EarcutPolygonTriangulator : IPolygonTriangulator

By default, AddPolygon uses a naive approach that only handles convex polygons, just because I didn't have time to implement a better algorythm.

The idea is to have several polygon triangulation methods, and set the best one by default. For example, even for convex polygons, there's interesting approaches like Minimum Cost Polygon Triangulation.

So, if you want to contribute an earcut triangulator implementation, I could replace the naive implementation with earcut implementation in the next release.

Holes are a bit more tricky to implement, they're an edge case, but worth to implement, I guess I would include another method called "AddPolygonWithHoles" or something like that.

Beware that it must work in three dimensions; most earcut implementations around work in a 2D plane... doing it in 3D is a bit trickier, specially when all the vertices are not coplanar.

[promontis]

Ah yes, this Earcut implementation is mainly for 2d planes :)

[vpenades]

@promontis In retrospect, the ear clipping algorythm is not that complex.... I gave it a try and I was able to work it out in a short time... I've just commited the changes.

[promontis]

Cool! Will give it a try!

I've just uploaded a gist of the PolygonMeshBuilder from BabylonJS here: https://gist.github.com/promontis/ca686732cfec04b4d9e38542dafd9468

If you can find the time, could you perhaps have a look if I'm using the MeshBuilder correctly?

The Build method is the part where I'm using MeshBuilder. Your example showed adding triangles based on a list of Vector3, however, I seem to result in a list of float after porting. Therefore, I've created the function CreateVertexFromIndex, which constructs Vector3 and such from the list of doubles.

Original BabylonJS code: https://github.com/BabylonJS/Babylon.js/blob/8aae1ec1c954c8e7a5dd5062dfabf33334db437b/src/Meshes/polygonMesh.ts#L245

Seems ok?

[vpenades]

Actually, after giving it a try, I'm seriously considering dropping support for AddPolygon altogether.

Even with Ear Clipping algorythm, in 3D, there's so many edge and non trivial cases that should require a considerable development time.

Given that this library is designed to be a gltf toolkit, and not a general geometry processing library, the AddTriangle method should be what everybody needs at the bottom to work with the library.

Polygon tessellation libraries can be built on top by third party libraries.

@promontis what do you think?

[promontis]

@vpenades I would agree for my specific case where I go from a (unioned) polygon to an extruded 3d mesh.

I'm trying to think of a case where you would like to have polygons. Or at least a simpler interface. What about converters from other 3d formats? Would it be easier to write one if we could add polygons? Or do those also just need AddTriangle()?

[vpenades]

@promontis There's several cases that could benefit from supporting polygons:

• Fonts tessellation
• Converting from models that support polygons (wavefront obj)

But in the end, any "AddPoygon" method ends calling AddTriangle... and I I want to support polygons, I need to support all the cases, not only the easy cases.... and there's a lot of really difficult cases, because it is not uncommon to have to deal with malformed polygons, for which I would have to check the malformation, and report it as an error.

So I am at a point in which I have to choose between keeping the feature (and dedicate time to mainain it)... or move to more gltf related features.

[promontis]

@vpenades ah yes... I would then remove support for it altogether, and focus on more gltf features.