Faster Mesh Welding (Patch)

Post those lines of code you feel like sharing or find what you require for your project here; or simply use them as tutorials.
Post Reply
Foaly
Posts: 142
Joined: Tue Apr 15, 2014 8:45 am
Location: Germany

Faster Mesh Welding (Patch)

Post by Foaly »

On pastebin: http://pastebin.com/qPRTZVM4
As patch: https://www.dropbox.com/s/r98b56mp69c8k ... patch?dl=0

I used this model for testing (https://www.dropbox.com/s/bgykqgyqznytx ... tl.gz?dl=0, gzipped stl file, 279684 unique verts, 559366 unique indices), which I had created a while ago.
It is was meant for 3D printing (and I actually got it printed :D), and it's fan-art for the video game series "Ratchet & Clank".

This patch makes it possible to remove duplicate vertices A LOT faster.
As the STL loader generates unique normals for every triangle, you'll have to pass ignoreNormals = true, when welding (if you want to try it on this model.)
(This patch also makes the STL loader capable of 32 bit indices.)
Last edited by Foaly on Sun Feb 11, 2018 9:29 am, edited 1 time in total.
REDDemon
Developer
Posts: 1044
Joined: Tue Aug 31, 2010 8:06 pm
Location: Genova (Italy)

Re: Faster Mesh Welding (Patch)

Post by REDDemon »

Pretty cool, STL going to be even more needed with advent of 3d printing
Junior Irrlicht Developer.
Real value in social networks is not about "increasing" number of followers, but about getting in touch with Amazing people.
- by Me
devsh
Competition winner
Posts: 2057
Joined: Tue Dec 09, 2008 6:00 pm
Location: UK
Contact:

Re: Faster Mesh Welding (Patch)

Post by devsh »

I have something even faster :D

You need to use binary search, because finding duplicates for all vertices will take O(V*log(V)) where V is the number of vertices as opposed to yours and irrlicht's O(V^2).
Trust me, this makes a time difference with a 40k poly mesh and flexible vertex formats!


Written against BaW Irrlicht

Code: Select all

 
size_t cmpfunc_vertsz;
int cmpfunc (const void * a, const void * b)
{
   return memcmp((uint8_t*)a+4,(uint8_t*)b+4,cmpfunc_vertsz);
}
 
//! Creates a copy of a mesh, which will have identical vertices welded together
ICPUMeshBuffer* CMeshManipulator::createMeshBufferWelded(ICPUMeshBuffer *inbuffer, const bool& makeNewMesh, f32 tolerance) const
{
    if (!inbuffer)
        return 0;
    IMeshDataFormatDesc<core::ICPUBuffer>* oldDesc = inbuffer->getMeshDataAndFormat();
    if (!oldDesc)
        return 0;
 
    bool bufferPresent[EVAI_COUNT];
    ICPUMeshDataFormatDesc* desc = NULL;
    if (makeNewMesh)
    {
        desc = new ICPUMeshDataFormatDesc();
        if (!desc)
            return 0;
    }
 
    size_t vertexAttrSize[EVAI_COUNT];
    size_t vertexSize = 0;
    for (size_t i=0; i<EVAI_COUNT; i++)
    {
        const core::ICPUBuffer* buf = oldDesc->getMappedBuffer((E_VERTEX_ATTRIBUTE_ID)i);
        if (buf)
        {
            bufferPresent[i] = true;
            scene::E_COMPONENTS_PER_ATTRIBUTE componentCount = oldDesc->getAttribComponentCount((E_VERTEX_ATTRIBUTE_ID)i);
            scene::E_COMPONENT_TYPE componentType = oldDesc->getAttribType((E_VERTEX_ATTRIBUTE_ID)i);
            vertexAttrSize[i] = scene::vertexAttrSize[componentType][componentCount];
            vertexSize += vertexAttrSize[i];
            if (makeNewMesh)
            {
                desc->mapVertexAttrBuffer(  const_cast<core::ICPUBuffer*>(buf),(E_VERTEX_ATTRIBUTE_ID)i,
                                            componentCount,componentType,
                                            oldDesc->getMappedBufferStride((E_VERTEX_ATTRIBUTE_ID)i),oldDesc->getMappedBufferOffset((E_VERTEX_ATTRIBUTE_ID)i));
            }
        }
        else
            bufferPresent[i] = false;
    }
    cmpfunc_vertsz = vertexSize;
 
    size_t vertexCount = 0;
    video::E_INDEX_TYPE oldIndexType = video::EIT_UNKNOWN;
    if (oldDesc->getIndexBuffer())
    {
        if (inbuffer->getIndexType()==video::EIT_16BIT)
        {
            oldIndexType = video::EIT_16BIT;
            for (size_t i=0; i<inbuffer->getIndexCount(); i++)
            {
                size_t index = reinterpret_cast<const uint16_t*>(inbuffer->getIndices())[i];
                if (index>vertexCount)
                    vertexCount = index;
            }
            if (inbuffer->getIndexCount())
                vertexCount++;
        }
        else if (inbuffer->getIndexType()==video::EIT_32BIT)
        {
            oldIndexType = video::EIT_32BIT;
            for (size_t i=0; i<inbuffer->getIndexCount(); i++)
            {
                size_t index = reinterpret_cast<const uint32_t*>(inbuffer->getIndices())[i];
                if (index>vertexCount)
                    vertexCount = index;
            }
            if (inbuffer->getIndexCount())
                vertexCount++;
        }
        else
            vertexCount = inbuffer->getIndexCount();
    }
    else
        vertexCount = inbuffer->getIndexCount();
 
    if (vertexCount==0)
    {
        if (makeNewMesh)
            desc->drop();
        return 0;
    }
 
    // reset redirect list
    uint32_t* redirects = new uint32_t[vertexCount];
 
    uint32_t maxRedirect = 0;
 
    uint8_t* epicData = (uint8_t*)malloc((vertexSize+4)*vertexCount);
    for (size_t i=0; i < vertexCount; i++)
    {
        uint8_t* currentVertexPtr = epicData+i*(vertexSize+4);
        reinterpret_cast<uint32_t*>(currentVertexPtr)[0] = i;
        currentVertexPtr+=4;
        for (size_t k=0; k<EVAI_COUNT; k++)
        {
            if (!bufferPresent[k])
                continue;
 
            size_t stride = oldDesc->getMappedBufferStride((scene::E_VERTEX_ATTRIBUTE_ID)k);
            void* sourcePtr = inbuffer->getAttribPointer((scene::E_VERTEX_ATTRIBUTE_ID)k)+i*stride;
            memcpy(currentVertexPtr,sourcePtr,vertexAttrSize[k]);
            currentVertexPtr += vertexAttrSize[k];
        }
    }
    uint8_t* origData = (uint8_t*)malloc((vertexSize+4)*vertexCount);
    memcpy(origData,epicData,(vertexSize+4)*vertexCount);
    qsort(epicData, vertexCount, vertexSize+4, cmpfunc);
    for (size_t i=0; i<vertexCount; i++)
    {
        uint32_t redir;
 
        void* item = bsearch (origData+(vertexSize+4)*i, epicData, vertexCount, vertexSize+4, cmpfunc);
        if( item != NULL )
        {
            redir = *reinterpret_cast<uint32_t*>(item);
        }
 
        redirects[i] = redir;
        if (redir>maxRedirect)
            maxRedirect = redir;
    }
    free(origData);
    free(epicData);
 
    void* oldIndices = inbuffer->getIndices();
    ICPUMeshBuffer* clone = NULL;
    if (makeNewMesh)
    {
        clone = new ICPUMeshBuffer();
        if (!clone)
        {
            desc->drop();
            return 0;
        }
        clone->setBaseVertex(inbuffer->getBaseVertex());
        clone->setBoundingBox(inbuffer->getBoundingBox());
        clone->setIndexCount(inbuffer->getIndexCount());
        clone->setIndexType(maxRedirect>=0x10000u ? video::EIT_32BIT:video::EIT_16BIT);
        clone->setMeshDataAndFormat(desc);
        desc->drop();
        clone->setPrimitiveType(inbuffer->getPrimitiveType());
        clone->getMaterial() = inbuffer->getMaterial();
 
        core::ICPUBuffer* indexCpy = new core::ICPUBuffer((maxRedirect>=0x10000u ? 4:2)*inbuffer->getIndexCount());
        desc->mapIndexBuffer(indexCpy);
        indexCpy->drop();
    }
    else
    {
        if (!oldDesc->getIndexBuffer())
        {
            core::ICPUBuffer* indexCpy = new core::ICPUBuffer((maxRedirect>=0x10000u ? 4:2)*inbuffer->getIndexCount());
            oldDesc->mapIndexBuffer(indexCpy);
            indexCpy->drop();
        }
        inbuffer->setIndexType(maxRedirect>=0x10000u ? video::EIT_32BIT:video::EIT_16BIT);
    }
 
 
    if (oldIndexType==video::EIT_16BIT)
    {
        uint16_t* indicesIn = reinterpret_cast<uint16_t*>(oldIndices);
        if ((makeNewMesh ? clone:inbuffer)->getIndexType()==video::EIT_32BIT)
        {
            uint32_t* indicesOut = reinterpret_cast<uint32_t*>((makeNewMesh ? clone:inbuffer)->getIndices());
            for (size_t i=0; i<inbuffer->getIndexCount(); i++)
                indicesOut[i] = redirects[indicesIn[i]];
        }
        else if ((makeNewMesh ? clone:inbuffer)->getIndexType()==video::EIT_16BIT)
        {
            uint16_t* indicesOut = reinterpret_cast<uint16_t*>((makeNewMesh ? clone:inbuffer)->getIndices());
            for (size_t i=0; i<inbuffer->getIndexCount(); i++)
                indicesOut[i] = redirects[indicesIn[i]];
        }
    }
    else if (oldIndexType==video::EIT_32BIT)
    {
        uint32_t* indicesIn = reinterpret_cast<uint32_t*>(oldIndices);
        if ((makeNewMesh ? clone:inbuffer)->getIndexType()==video::EIT_32BIT)
        {
            uint32_t* indicesOut = reinterpret_cast<uint32_t*>((makeNewMesh ? clone:inbuffer)->getIndices());
            for (size_t i=0; i<inbuffer->getIndexCount(); i++)
                indicesOut[i] = redirects[indicesIn[i]];
        }
        else if ((makeNewMesh ? clone:inbuffer)->getIndexType()==video::EIT_16BIT)
        {
            uint16_t* indicesOut = reinterpret_cast<uint16_t*>((makeNewMesh ? clone:inbuffer)->getIndices());
            for (size_t i=0; i<inbuffer->getIndexCount(); i++)
                indicesOut[i] = redirects[indicesIn[i]];
        }
    }
    else if ((makeNewMesh ? clone:inbuffer)->getIndexType()==video::EIT_32BIT)
    {
        uint32_t* indicesOut = reinterpret_cast<uint32_t*>((makeNewMesh ? clone:inbuffer)->getIndices());
        for (size_t i=0; i<inbuffer->getIndexCount(); i++)
            indicesOut[i] = redirects[i];
    }
    else if ((makeNewMesh ? clone:inbuffer)->getIndexType()==video::EIT_16BIT)
    {
        uint16_t* indicesOut = reinterpret_cast<uint16_t*>((makeNewMesh ? clone:inbuffer)->getIndices());
        for (size_t i=0; i<inbuffer->getIndexCount(); i++)
            indicesOut[i] = redirects[i];
    }
    delete [] redirects;
 
    if (makeNewMesh)
        return clone;
    else
        return inbuffer;
}
 

P.S. STL is REALLY bad for 3D printing, because of simple geometry, lack of binary or compression representation

Try AMF, which supports XML (not all attributes need to be present) and ZIP compression (often beating STL or binary obj), Phong Tessellation (you use less triangles to make smooth surfaces with great precision), as well as Colors and Textures!
Foaly
Posts: 142
Joined: Tue Apr 15, 2014 8:45 am
Location: Germany

Re: Faster Mesh Welding (Patch)

Post by Foaly »

Mine uses a hash table, which takes O(1) if there are no collisions, and O(n) up to 400k vertices on average.
Yet it is does not support custom vertex formats.

I also tried using binary search earlier, but I used Irrlicht's map implementation and it turned out to be slower.

P.S. I know that STL is a horrible format, but it's supported everywhere.
devsh
Competition winner
Posts: 2057
Joined: Tue Dec 09, 2008 6:00 pm
Location: UK
Contact:

Re: Faster Mesh Welding (Patch)

Post by devsh »

Your algorithm buckets the vertices along the (1,1,1) line, if I have a mesh which has a lot of vertices in the plane with that normal your bucketing will die and become slower than a binary search approach
Post Reply