Tesselator triangle soup to shared vertices representation

[tpaviot]

In the current tesselator implementation, the Tesselate() method (see https://github.com/tpaviot/pythonocc-core/blob/master/src/Visualization/Tesselator.cpp#L139) generates a list of vertices as following (pseudo-code):

vertices = [
vertex1, # triangle 1
vertex2, # triangle 1
vertex3, # triangle 1
vertex4, # triangle 2
vertex5, # triangle 2
vertex6, # triangle 2
vertex7, # triangle 3
etc.
]

As a consequence, the vertex indices list is:

indices = [0, 1, 2,
                3, 4, 5,
                6, 7, 8, etc.]

With this representation, vertex4 and vertex1 maybe the same vertex (i.e. the thee coords X, Y and Z are equal).

I would like to get a shared vertices representation, where all vertices are different. This would become, for instance:

vertices = [
vertex1, # in this list, all vertices are different
vertex2,
vertex3,
vertex4,
vertex5,
etc.
]

With a slightly changed index list:

indices = [0, 1, 2,
        2, 1, 3,,
        4, 0, 2, etc.]

Generate the second representation (Shared vertices) from the first (triangle soup) is highly costly : traverse the vertices list, try to find identical vertices, replace the related index into thze indices list. It's an o(n!) algorithm.

So my question here : has anyone generated a "Shared Vertices Representation" directly from a BRepMesh_IncrementalMesh and BRep_Tool::Triangulation ?

@rainman110 @aothms @sfotis any advice ?

FYI it would allows much lighter meshes (I especially thinnk about x3d files for instance).

[rainman110]

@tpaviot Yes, i have done it already. Actually, the mentioned OpenCASCADE classes directly provide a shared representation . I' ll post the code later.

The vertex sharing is limited to single faces though. If you also want to share vertices between faces, things are getting more complicated. One also has to keep in mind, that some vertices might be identical but their normal vector not !

[tpaviot]

@rainman110 I know about that, the visualization may be modified. Great if you can share some code. FYI I've been working on some webgl changes, I will request a review from you as soon as the PR is created.

[sfotis]

@tpaviot I have since then implemented a class that keeps an ordered c++ set of 3d data (efficient enough for our needs), from any soup of 3d data (we use it internally to compose a mesh from sketch up data (which usually is a mess and not a mesh ...)). Class provides also VBO ready arrays, and some handy routines for merging, scaling, translating and splitting to contiguous objects. I could, time willing, integrate it to the current tesselator.

[tpaviot]

@sfotis It would be cool, although the only thing I need so far is the Shared Vertices representation. What I'd like to do after that is to perform a mesh reduction algorithm to be able to generate lower triangles representations fo any TopoDS_Shape. I'd like to include into the Tesselator class a method able to reduce the mesh, something very simple and efficient, doable in c++, and that would not require any additional big dependency like numpy, scipy, meshlab etc. So far I've found https://github.com/melax/sandbox/tree/master/bunnylod and https://github.com/sp4cerat/Fast-Quadric-Mesh-Simplification The final goal is to implement LOD management in order to enable large scale visualizations. I already experimented some nice stuff.

[rainman110]

Heres our triangulation code:

int TriangulationImpl::triangularizeFace(const TopoDS_Face& face)
{
    TopLoc_Location location;

    const Handle(Poly_Triangulation) triangulation = BRep_Tool::Triangulation(face,
            location);

    if (triangulation.IsNull())
    {
        return 0;
    }

    gp_Trsf nodeTransformation = location;

    unsigned long startIndex = _vertices.size();
    assert(_vertices.size() == _normals.size());

    unsigned long ilower = 0;

    if (triangulation->HasUVNodes())
    {
        // we use the uv nodes to compute normal vectors for each point

        BRepGProp_Face prop(face);

        const TColgp_Array1OfPnt2d& uvnodes =
            triangulation->UVNodes(); // get (face-local) list of nodes
        ilower = uvnodes.Lower();

        for (int inode = uvnodes.Lower(); inode <= uvnodes.Upper(); ++inode)
        {
            const gp_Pnt2d& uv_pnt = uvnodes(inode);
            gp_Pnt p;
            gp_Vec n;
            prop.Normal(uv_pnt.X(), uv_pnt.Y(), p, n);

            if (n.SquareMagnitude() > 0.)
            {
                n.Normalize();
            }

            if (face.Orientation() == TopAbs_INTERNAL)
            {
                n.Reverse();
            }

            _vertices.append(Point3d(p.X(), p.Y(), p.Z()));
            _normals.append(Point3d(n.X(), n.Y(), n.Z()));
        }
    }
    else
    {
        // we cannot compute normals

        const TColgp_Array1OfPnt& nodes =
            triangulation->Nodes(); // get (face-local) list of nodes
        ilower = nodes.Lower();

        for (int inode = nodes.Lower(); inode <= nodes.Upper(); inode++)
        {
            const gp_Pnt& p = nodes(inode).Transformed(nodeTransformation);
            _vertices.append(Point3d(p.X(), p.Y(), p.Z()));
            _normals.append(Point3d(1, 0, 0));
        }
    }

    const Poly_Array1OfTriangle& triangles = triangulation->Triangles();

    // iterate over triangles in the array
    for (int j = triangles.Lower(); j <= triangles.Upper(); j++)
    {
        const Poly_Triangle& triangle = triangles(j);
        int occindex1, occindex2, occindex3;
        triangle.Get(occindex1, occindex2, occindex3); // get indices into index1..3
        unsigned long index1, index2, index3;
        index1 = occindex1 - ilower + startIndex;
        index2 = occindex2 - ilower + startIndex;
        index3 = occindex3 - ilower + startIndex;

        if (face.Orientation() != TopAbs_REVERSED &&
                face.Orientation() != TopAbs_INTERNAL)
        {
            _triangles.push_back(Triangle(index1, index2, index3));
        }
        else
        {
            _triangles.push_back(Triangle(index1, index3, index2));
        }
    } // for triangles

    return 0;
}

[rainman110]

@tpaviot I just looked at Tesselator::Tesselate(). It should actually share vertices. It is very similar to our tesselation code.

[jf---]

@tpaviot is the idea to generate meshes of different resoltions by a range setting of the Deviation parameters for the BRepMesh? Perhaps that might be interesting to explore, since creating dense meshes and then reducing them can in some cases be avoided?

what's tricky with reducing density of CAD meshes, is that often edges cannot be further reduced... by that I mean that the mesh looks like the 1st image, which cant really be reduced meaninfully, where the 2nd case ( not typical ) can...

so that's the basis for the hunch that using the Deviation parameters might be practical

---

little potential for mesh reduction, this is the type of mesh OCC's ( and most CAD meshers ) produce

---

plenty of potential for mesh reduction, but more typical of FEM output, where you prefer that the angles of the triangles are evenly distributed

[tpaviot]

@jf--- I disagree with "weak or strong potential" argument. If I remove 50% of triangles in case 1, and if I remove 50% f triangles in case 2, in both cased I reduced the mesh size by a factor 2. This is exactly what I want: reducing the number of triangles.

I already played wth deflection parameters from the BRepMesh_IncrementalMesh class, but I always get "almost" the same mesh quality.

I'm not sure about what's the most interesting in terms of computing time : use n times the occ mesher, or use it once and run (n-1) times a reduction algorithm.

Well, all of that must be tested, intuition is not enough.

[aothms]

IfcOpenShell has a function to merge vertices belonging to different faces [1]. It uses a std::map so performance should scale fine. If you also want to account for geometrical proximity I guess you can use some of the spatial acceleration structures provided in OCC.

Indeed, in the case of IfcOpenShell enabling this setting implies that normal vectors are discarded (they could have been averaged as well). Some modelling tools don't care about normals, at least as far as the interface to the user is concerned. Hence this option.

In general I am quite interested in a more hybrid approach of BRep and polyhedral modelling approach. While maybe not the scope of your effort, I think a coupling with e.g CGAL would be quite interesting.

[1] https://github.com/IfcOpenShell/IfcOpenShell/blob/master/src/ifcgeom/IfcGeomRepresentation.h#L365

@rainman110 since you use BRepGProp_Face which operates on face and not surface, is it still necessary to reverse the normal? Also, is a face orientation ever INTERNAL, I typically only check for FORWARD and REVERSED, is that misguided on my behalf?

            if (face.Orientation() == TopAbs_INTERNAL)
            {
                n.Reverse();
            }

[rainman110]

@aothms It quite a while ago, when I implemented this. I am not sure aynmore if was is really necessary to invert the normal for internal faces. Probably best, to test it in more detail.

[jf---]

coupling CGAL would be brilliant 👍 ( though quite a different beast in itself )