Skip to content
Permalink
master
Switch branches/tags
Go to file
 
 
Cannot retrieve contributors at this time
/**
* 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>
#ifdef __APPLE__
#include <stdlib.h> /* OSX gets its 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
}
}