Faster Mesh Welding (Patch)

[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 ), 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.)

[REDDemon]

Pretty cool, STL going to be even more needed with advent of 3d printing

[devsh]

I have something even faster

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]

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]

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