weldmesh.cpp

Go to the documentation of this file.

// Slightly modified version of weldmesh, by Wildfire Games, for 0 A.D.
// 
// Motivation for changes:
//  * Fix build on *BSD (including malloc.h produces an error)

#include "precompiled.h"

/**
 *  Copyright (C) 2011 by Morten S. Mikkelsen
 *
 *  This software is provided 'as-is', without any express or implied
 *  warranty.  In no event will the authors be held liable for any damages
 *  arising from the use of this software.
 *
 *  Permission is granted to anyone to use this software for any purpose,
 *  including commercial applications, and to alter it and redistribute it
 *  freely, subject to the following restrictions:
 *
 *  1. The origin of this software must not be misrepresented; you must not
 *     claim that you wrote the original software. If you use this software
 *     in a product, an acknowledgment in the product documentation would be
 *     appreciated but is not required.
 *  2. Altered source versions must be plainly marked as such, and must not be
 *     misrepresented as being the original software.
 *  3. This notice may not be removed or altered from any source distribution.
 */


#include "weldmesh.h"
#include <string.h>
#include <assert.h>

#if defined(__APPLE__) || defined(__FreeBSD__) || defined(__OpenBSD__)
#include <stdlib.h>  /* BSD-based OSes get their malloc stuff through here */
#else
#include <malloc.h> 
#endif

static void MergeVertsFast(int * piCurNrUniqueVertices, int * piRemapTable, float * pfVertexDataOut, int * piVertexIDs,
              const float pfVertexDataIn[], const int iNrVerticesIn, const int iFloatsPerVert,
              const int iL_in, const int iR_in, const int iChannelNum);

int WeldMesh(int * piRemapTable, float * pfVertexDataOut,
              const float pfVertexDataIn[], const int iNrVerticesIn, const int iFloatsPerVert)
{
    int iUniqueVertices = 0, i=0;
    int * piVertexIDs = NULL;
    if(iNrVerticesIn<=0) return 0;


    iUniqueVertices = 0;
    piVertexIDs = (int *) malloc(sizeof(int)*iNrVerticesIn);
    if(piVertexIDs!=NULL)
    {
        for(i=0; i<iNrVerticesIn; i++)
        {
            piRemapTable[i] = -1;
            piVertexIDs[i] = i;
        }

        MergeVertsFast(&iUniqueVertices, piRemapTable, pfVertexDataOut, piVertexIDs,
                                         pfVertexDataIn, iNrVerticesIn, iFloatsPerVert, 0, iNrVerticesIn-1, 0);

        free(piVertexIDs);

        // debug check
        for(i=0; i<iUniqueVertices; i++)
            assert(piRemapTable[i]>=0);
    }

    return iUniqueVertices;
}





static void MergeVertsFast(int * piCurNrUniqueVertices, int * piRemapTable, float * pfVertexDataOut, int * piVertexIDs,
              const float pfVertexDataIn[], const int iNrVerticesIn, const int iFloatsPerVert,
              const int iL_in, const int iR_in, const int iChannelNum)
{
    const int iCount = iR_in-iL_in+1;
    int l=0;
    float fMin, fMax, fAvg;
    assert(iCount>0);
    // make bbox
    fMin = pfVertexDataIn[ piVertexIDs[iL_in]*iFloatsPerVert + iChannelNum]; fMax = fMin;
    for(l=(iL_in+1); l<=iR_in; l++)
    {
        const int index = piVertexIDs[l]*iFloatsPerVert + iChannelNum;
        const float fVal = pfVertexDataIn[index];
        if(fMin>fVal) fMin=fVal;
        else if(fMax<fVal) fMax=fVal;
    }

    // terminate recursion when the separation/average value
    // is no longer strictly between fMin and fMax values.
    fAvg = 0.5f*(fMax + fMin);
    if(fAvg<=fMin || fAvg>=fMax || iCount==1)
    {
        if((iChannelNum+1) == iFloatsPerVert || iCount==1)  // we are done, weld by hand
        {
            int iUniqueNewVertices = 0;
            float * pfNewUniVertsOut = &pfVertexDataOut[ piCurNrUniqueVertices[0]*iFloatsPerVert ];

            for(l=iL_in; l<=iR_in; l++)
            {
                const int index = piVertexIDs[l]*iFloatsPerVert;

                int iFound = 0; // didn't find copy yet.
                int l2=0;
                while(l2<iUniqueNewVertices && iFound==0)
                {
                    const int index2 = l2*iFloatsPerVert;

                    int iAllSame = 1;
                    int c=0;
                    while(iAllSame!=0 && c<iFloatsPerVert)
                    {
                        iAllSame &= (pfVertexDataIn[index+c] == pfNewUniVertsOut[index2+c] ? 1 : 0);
                        ++c;
                    }

                    iFound = iAllSame;
                    if(iFound==0) ++l2;
                }
                
                // generate new entry
                if(iFound==0)
                {
                    memcpy(pfNewUniVertsOut+iUniqueNewVertices*iFloatsPerVert, pfVertexDataIn+index, sizeof(float)*iFloatsPerVert);
                    ++iUniqueNewVertices;
                }

                assert(piRemapTable[piVertexIDs[l]] == -1); // has not yet been assigned
                piRemapTable[piVertexIDs[l]] = piCurNrUniqueVertices[0] + l2;
            }

            piCurNrUniqueVertices[0] += iUniqueNewVertices;
        }
        else
        {
            MergeVertsFast(piCurNrUniqueVertices, piRemapTable, pfVertexDataOut, piVertexIDs,
                           pfVertexDataIn, iNrVerticesIn, iFloatsPerVert,
                            iL_in, iR_in, iChannelNum+1);
        }
    }
    else
    {
        int iL=iL_in, iR=iR_in, index;

        // seperate (by fSep) all points between iL_in and iR_in in pTmpVert[]
        while(iL < iR)
        {
            int iReadyLeftSwap = 0;
            int iReadyRightSwap = 0;
            while(iReadyLeftSwap==0 && iL<iR)
            {
                assert(iL>=iL_in && iL<=iR_in);
                index = piVertexIDs[iL]*iFloatsPerVert+iChannelNum;
                iReadyLeftSwap = !(pfVertexDataIn[index]<fAvg) ? 1 : 0;
                if(iReadyLeftSwap==0) ++iL;
            }
            while(iReadyRightSwap==0 && iL<iR)
            {
                assert(iR>=iL_in && iR<=iR_in);
                index = piVertexIDs[iR]*iFloatsPerVert+iChannelNum;
                iReadyRightSwap = pfVertexDataIn[index]<fAvg ? 1 : 0;
                if(iReadyRightSwap==0) --iR;
            }
            assert( (iL<iR) || (iReadyLeftSwap==0 || iReadyRightSwap==0));

            if(iReadyLeftSwap!=0 && iReadyRightSwap!=0)
            {
                int iID=0;
                assert(iL<iR);
                iID = piVertexIDs[iL];
                piVertexIDs[iL] = piVertexIDs[iR];
                piVertexIDs[iR] = iID;
                ++iL; --iR;
            }
        }

        assert(iL==(iR+1) || (iL==iR));
        if(iL==iR)
        {
            const int index = piVertexIDs[iR]*iFloatsPerVert+iChannelNum;
            const int iReadyRightSwap = pfVertexDataIn[index]<fAvg ? 1 : 0;
            if(iReadyRightSwap!=0) ++iL;
            else --iR;
        }

        // recurse
        if(iL_in <= iR)
            MergeVertsFast(piCurNrUniqueVertices, piRemapTable, pfVertexDataOut, piVertexIDs,
                           pfVertexDataIn, iNrVerticesIn, iFloatsPerVert, iL_in, iR, iChannelNum);  // weld all left of fSep
        if(iL <= iR_in)
            MergeVertsFast(piCurNrUniqueVertices, piRemapTable, pfVertexDataOut, piVertexIDs,
                           pfVertexDataIn, iNrVerticesIn, iFloatsPerVert, iL, iR_in, iChannelNum);  // weld all right of (or equal to) fSep
    }
}