Mesh merge by distance

[cingelmarekmt]

Hi

I am trying to remove duplicate vertices. Unfortunately, after removing the duplicate vertices, I don't know how to correctly calculate the normals. Is there support for a feature like Blender : Edit Mode : Mesh : Merge : By Distance

Here is a piece of my code:

    MyMesh m;

    auto vi = vcg::tri::Allocator<MyMesh>::AddVertices(m, g.vertices.size());
    for (int i = 0; i < g.vertices.size(); ++i, ++vi)
    {
        auto const & p = g.vertices[i];
        auto const & n = g.normals[i];

        (&*vi)->P() = Point3f(p.x, p.y, p.z);
        (&*vi)->N() = MyVertex::NormalType(n.x, n.y, n.z);
    }

    auto fi = tri::Allocator<MyMesh>::AddFaces(m, g.indices.size() / 3);
    for (int i = 0; i < g.indices.size() / 3; ++i, ++fi)
    {
        auto const & i0 = g.indices[i * 3 + 0];
        auto const & i1 = g.indices[i * 3 + 1];
        auto const & i2 = g.indices[i * 3 + 2];

        (&*fi)->V(0) = &m.vert[i0];
        (&*fi)->V(1) = &m.vert[i1];
        (&*fi)->V(2) = &m.vert[i2];
    }

    tri::UpdateBounding<MyMesh>::Box(m);
    tri::Clean<MyMesh>::MergeCloseVertex(m, m.bbox.Diag() * 0.0001);

    tri::UpdateNormal<MyMesh>::PerVertexNormalizedPerFace(m);
    tri::UpdateNormal<MyMesh>::PerFaceNormalized(m);

    g.vertices.clear();
    g.normals.clear();
    int numvert = 0;
    std::vector<int> vertexId(m.vert.size(), -1);
    for (auto vi = m.vert.begin(); vi != m.vert.end(); ++vi)
    {
        if (vi->IsD())
        {
            continue;
        }
        vertexId[vi - m.vert.begin()] = numvert;
        g.vertices.emplace_back(vi->P()[0], vi->P()[1], vi->P()[2]);
        g.normals.emplace_back(vi->N()[0], vi->N()[1], vi->N()[2]);
        ++numvert;
    }

    g.indices.clear();
    for (auto fi = m.face.begin(); fi != m.face.end(); ++fi)
    {
        if (fi->IsD())
        {
            continue;
        }

        for(int k = 0; k < (*fi).VN(); ++k)
        {
            auto vInd = vertexId[tri::Index(m, fi->V(k))];
            if (vInd >= 0)
            {
                g.indices.push_back(vInd);
            }
        }
    }

Thank you for your response.

[cingelmarekmt]

Hi

I managed to do it as follows:

template<class MeshType>
static int _MergeByDistance(MeshType & m, bool RemoveDegenerateFlag = true)
{
    typedef Clean<MeshType> CMT;

    if (m.vert.size() == 0 || m.vn == 0)
    {
        return 0;
    }

    std::map<MeshType::VertexPointer, MeshType::VertexPointer> mp;
    size_t i, j;
    MeshType::VertexIterator vi;
    int deleted = 0;
    int k = 0;
    size_t num_vert = m.vert.size();
    std::vector<MeshType::VertexPointer> perm(num_vert);
    for (vi = m.vert.begin(); vi != m.vert.end(); ++vi, ++k)
    {
        perm[k] = &(*vi);
    }

    CMT::RemoveDuplicateVert_Compare c_obj;
    std::sort(perm.begin(), perm.end(), c_obj);

    j = 0;
    i = j;
    mp[perm[i]] = perm[j];
    ++i;
    for (; i != num_vert;)
    {
        auto del = !perm[i]->IsD() && !perm[j]->IsD() && perm[i]->P() == perm[j]->cP();
        if (MeshType::VertexType::HasNormal())
        {
            auto dotProduct = perm[i]->N().dot(perm[j]->cN());
            auto shouldJoin = dotProduct > 0.8;
            del &= shouldJoin;
        }
        if (del)
        {
            MeshType::VertexPointer t = perm[i];
            mp[perm[i]] = perm[j];
            ++i;
            Allocator<MeshType>::DeleteVertex(m, *t);
            deleted++;
        }
        else
        {
            j = i;
            ++i;
        }
    }

    for (MeshType::FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
        if (!(*fi).IsD())
            for (k = 0; k < (*fi).VN(); ++k)
                if (mp.find((typename MeshType::VertexPointer)(*fi).V(k)) != mp.end())
                {
                    (*fi).V(k) = &*mp[(*fi).V(k)];
                }

    for (MeshType::EdgeIterator ei = m.edge.begin(); ei != m.edge.end(); ++ei)
        if (!(*ei).IsD())
            for (k = 0; k < 2; ++k)
                if (mp.find((typename MeshType::VertexPointer)(*ei).V(k)) != mp.end())
                {
                    (*ei).V(k) = &*mp[(*ei).V(k)];
                }

    for (MeshType::TetraIterator ti = m.tetra.begin(); ti != m.tetra.end(); ++ti)
        if (!(*ti).IsD())
            for (k = 0; k < 4; ++k)
                if (mp.find((typename MeshType::VertexPointer)(*ti).V(k)) != mp.end())
                    (*ti).V(k) = &*mp[(*ti).V(k)];

    if (RemoveDegenerateFlag)
    {
        CMT::RemoveDegenerateFace(m);
    }
    if (RemoveDegenerateFlag && m.en > 0)
    {
        CMT::RemoveDegenerateEdge(m);
        CMT::RemoveDuplicateEdge(m);
    }
    return deleted;
}

tri::UpdateBounding<MyMesh>::Box(mesh);
vcg::tri::UpdateNormal<MyMesh>::PerFaceNormalized(mesh);
vcg::tri::UpdateNormal<MyMesh>::PerVertexFromCurrentFaceNormal(mesh);

// int dup = tri::Clean<MyMesh>::MergeByDistance(mesh, mesh.bbox.Diag() * 0.0001);
int dup = tri::_MergeByDistance<MyMesh>(mesh);
// int dup = tri::Clean<MyMesh>::RemoveDuplicateVertex(mesh);
int unref = tri::Clean<MyMesh>::RemoveUnreferencedVertex(mesh);

vcg::tri::UpdateNormal<MyMesh>::PerVertexNormalized(mesh);

Wouldn't it be nice to call it a standard function in your SDK?

[cignoni]

Two ways of removing duplicated vertices in vcglib (both defined in clean.h):

• removing only exact duplicates (eg. vertexes that have exactly the same xyz coordinates) static int RemoveDuplicateVertex( MeshType & m, bool RemoveDegenerateFlag=true)
• merging vertices (e.g. unifying all the vertexes that are closer than a given radius) static int MergeCloseVertex(MeshType &m, const ScalarType radius)

[cingelmarekmt]

Yes, I tried them, but I needed the normal vector to be included in this process. Where can I make vertext normals for the same wall that are the classic area weighted average.

[cignoni]

Sorry if I do not understand, but what do you exactly mean with "normal vector to be included in this process"? That you want to unify the vertexes only if the they have the same normal? or that you want to preserve different normals for the same vertex (in order to correctly shade crease edges)?

[cingelmarekmt]

We do not remove the vertex if the face normal is within some tolerance. That's why I regenerate for mesh face normal, write them in vertex normal, then compare them and remove only those that are out of tolerance.

This will not reduce the vertices to a minimum, but for drawing the model this result is better.

Since the surface that is supposed to be smooth has averaged normals and the next plane out of tolerance has its own set of averaged normals.

The difference between RemoveDuplicateVertex is here:

        auto del = !perm[i]->IsD() && !perm[j]->IsD() && perm[i]->P() == perm[j]->cP();
        if (MeshType::VertexType::HasNormal())
        {
            auto dotProduct = perm[i]->N().dot(perm[j]->cN());
            auto shouldJoin = dotProduct > 0.8;
            del &= shouldJoin;
        }
        if (del)
        {

[cignoni]

O,k so you need the opposite: duplicating the vertices if they have sufficiently different normals. for that there is the generic AttributeSeam class inside (attribute_seam.h) that does exactly that. It splits vertexes when some attributes are more different than required (see its usage example inside meshlab) or the simpler void CreaseCut(MESH_TYPE &m, float angleRad) function that cut a mesh, duplicating vertices, if the face normals differ more than a given angle

[cingelmarekmt]

Thank you very much for the advice, I prefer to use the standard solution that you suggest.