Line data Source code
1 : // Slightly modified version of weldmesh, by Wildfire Games, for 0 A.D.
2 : //
3 : // Motivation for changes:
4 : // * Fix build on *BSD (including malloc.h produces an error)
5 :
6 : #include "precompiled.h"
7 :
8 : #ifdef _MSC_VER
9 : # pragma warning(disable:4456) // hides previous local declaration
10 : #endif
11 :
12 : /**
13 : * Copyright (C) 2011 by Morten S. Mikkelsen
14 : *
15 : * This software is provided 'as-is', without any express or implied
16 : * warranty. In no event will the authors be held liable for any damages
17 : * arising from the use of this software.
18 : *
19 : * Permission is granted to anyone to use this software for any purpose,
20 : * including commercial applications, and to alter it and redistribute it
21 : * freely, subject to the following restrictions:
22 : *
23 : * 1. The origin of this software must not be misrepresented; you must not
24 : * claim that you wrote the original software. If you use this software
25 : * in a product, an acknowledgment in the product documentation would be
26 : * appreciated but is not required.
27 : * 2. Altered source versions must be plainly marked as such, and must not be
28 : * misrepresented as being the original software.
29 : * 3. This notice may not be removed or altered from any source distribution.
30 : */
31 :
32 :
33 : #include "weldmesh.h"
34 : #include <string.h>
35 : #include <assert.h>
36 :
37 : #if defined(__APPLE__) || defined(__FreeBSD__) || defined(__OpenBSD__)
38 : #include <stdlib.h> /* BSD-based OSes get their malloc stuff through here */
39 : #else
40 : #include <malloc.h>
41 : #endif
42 :
43 : static void MergeVertsFast(int * piCurNrUniqueVertices, int * piRemapTable, float * pfVertexDataOut, int * piVertexIDs,
44 : const float pfVertexDataIn[], const int iNrVerticesIn, const int iFloatsPerVert,
45 : const int iL_in, const int iR_in, const int iChannelNum);
46 :
47 0 : int WeldMesh(int * piRemapTable, float * pfVertexDataOut,
48 : const float pfVertexDataIn[], const int iNrVerticesIn, const int iFloatsPerVert)
49 : {
50 0 : int iUniqueVertices = 0, i=0;
51 0 : int * piVertexIDs = NULL;
52 0 : if(iNrVerticesIn<=0) return 0;
53 :
54 :
55 0 : iUniqueVertices = 0;
56 0 : piVertexIDs = (int *) malloc(sizeof(int)*iNrVerticesIn);
57 0 : if(piVertexIDs!=NULL)
58 : {
59 0 : for(i=0; i<iNrVerticesIn; i++)
60 : {
61 0 : piRemapTable[i] = -1;
62 0 : piVertexIDs[i] = i;
63 : }
64 :
65 0 : MergeVertsFast(&iUniqueVertices, piRemapTable, pfVertexDataOut, piVertexIDs,
66 : pfVertexDataIn, iNrVerticesIn, iFloatsPerVert, 0, iNrVerticesIn-1, 0);
67 :
68 0 : free(piVertexIDs);
69 :
70 : // debug check
71 0 : for(i=0; i<iUniqueVertices; i++)
72 0 : assert(piRemapTable[i]>=0);
73 : }
74 :
75 0 : return iUniqueVertices;
76 : }
77 :
78 :
79 :
80 :
81 :
82 0 : static void MergeVertsFast(int * piCurNrUniqueVertices, int * piRemapTable, float * pfVertexDataOut, int * piVertexIDs,
83 : const float pfVertexDataIn[], const int iNrVerticesIn, const int iFloatsPerVert,
84 : const int iL_in, const int iR_in, const int iChannelNum)
85 : {
86 0 : const int iCount = iR_in-iL_in+1;
87 0 : int l=0;
88 : float fMin, fMax, fAvg;
89 0 : assert(iCount>0);
90 : // make bbox
91 0 : fMin = pfVertexDataIn[ piVertexIDs[iL_in]*iFloatsPerVert + iChannelNum]; fMax = fMin;
92 0 : for(l=(iL_in+1); l<=iR_in; l++)
93 : {
94 0 : const int index = piVertexIDs[l]*iFloatsPerVert + iChannelNum;
95 0 : const float fVal = pfVertexDataIn[index];
96 0 : if(fMin>fVal) fMin=fVal;
97 0 : else if(fMax<fVal) fMax=fVal;
98 : }
99 :
100 : // terminate recursion when the separation/average value
101 : // is no longer strictly between fMin and fMax values.
102 0 : fAvg = 0.5f*(fMax + fMin);
103 0 : if(fAvg<=fMin || fAvg>=fMax || iCount==1)
104 : {
105 0 : if((iChannelNum+1) == iFloatsPerVert || iCount==1) // we are done, weld by hand
106 : {
107 0 : int iUniqueNewVertices = 0;
108 0 : float * pfNewUniVertsOut = &pfVertexDataOut[ piCurNrUniqueVertices[0]*iFloatsPerVert ];
109 :
110 0 : for(l=iL_in; l<=iR_in; l++)
111 : {
112 0 : const int index = piVertexIDs[l]*iFloatsPerVert;
113 :
114 0 : int iFound = 0; // didn't find copy yet.
115 0 : int l2=0;
116 0 : while(l2<iUniqueNewVertices && iFound==0)
117 : {
118 0 : const int index2 = l2*iFloatsPerVert;
119 :
120 0 : int iAllSame = 1;
121 0 : int c=0;
122 0 : while(iAllSame!=0 && c<iFloatsPerVert)
123 : {
124 0 : iAllSame &= (pfVertexDataIn[index+c] == pfNewUniVertsOut[index2+c] ? 1 : 0);
125 0 : ++c;
126 : }
127 :
128 0 : iFound = iAllSame;
129 0 : if(iFound==0) ++l2;
130 : }
131 :
132 : // generate new entry
133 0 : if(iFound==0)
134 : {
135 0 : memcpy(pfNewUniVertsOut+iUniqueNewVertices*iFloatsPerVert, pfVertexDataIn+index, sizeof(float)*iFloatsPerVert);
136 0 : ++iUniqueNewVertices;
137 : }
138 :
139 0 : assert(piRemapTable[piVertexIDs[l]] == -1); // has not yet been assigned
140 0 : piRemapTable[piVertexIDs[l]] = piCurNrUniqueVertices[0] + l2;
141 : }
142 :
143 0 : piCurNrUniqueVertices[0] += iUniqueNewVertices;
144 : }
145 : else
146 : {
147 0 : MergeVertsFast(piCurNrUniqueVertices, piRemapTable, pfVertexDataOut, piVertexIDs,
148 : pfVertexDataIn, iNrVerticesIn, iFloatsPerVert,
149 : iL_in, iR_in, iChannelNum+1);
150 0 : }
151 : }
152 : else
153 : {
154 0 : int iL=iL_in, iR=iR_in, index;
155 :
156 : // seperate (by fSep) all points between iL_in and iR_in in pTmpVert[]
157 0 : while(iL < iR)
158 : {
159 0 : int iReadyLeftSwap = 0;
160 0 : int iReadyRightSwap = 0;
161 0 : while(iReadyLeftSwap==0 && iL<iR)
162 : {
163 0 : assert(iL>=iL_in && iL<=iR_in);
164 0 : index = piVertexIDs[iL]*iFloatsPerVert+iChannelNum;
165 0 : iReadyLeftSwap = !(pfVertexDataIn[index]<fAvg) ? 1 : 0;
166 0 : if(iReadyLeftSwap==0) ++iL;
167 : }
168 0 : while(iReadyRightSwap==0 && iL<iR)
169 : {
170 0 : assert(iR>=iL_in && iR<=iR_in);
171 0 : index = piVertexIDs[iR]*iFloatsPerVert+iChannelNum;
172 0 : iReadyRightSwap = pfVertexDataIn[index]<fAvg ? 1 : 0;
173 0 : if(iReadyRightSwap==0) --iR;
174 : }
175 0 : assert( (iL<iR) || (iReadyLeftSwap==0 || iReadyRightSwap==0));
176 :
177 0 : if(iReadyLeftSwap!=0 && iReadyRightSwap!=0)
178 : {
179 0 : int iID=0;
180 0 : assert(iL<iR);
181 0 : iID = piVertexIDs[iL];
182 0 : piVertexIDs[iL] = piVertexIDs[iR];
183 0 : piVertexIDs[iR] = iID;
184 0 : ++iL; --iR;
185 : }
186 : }
187 :
188 0 : assert(iL==(iR+1) || (iL==iR));
189 0 : if(iL==iR)
190 : {
191 0 : const int index = piVertexIDs[iR]*iFloatsPerVert+iChannelNum;
192 0 : const int iReadyRightSwap = pfVertexDataIn[index]<fAvg ? 1 : 0;
193 0 : if(iReadyRightSwap!=0) ++iL;
194 0 : else --iR;
195 : }
196 :
197 : // recurse
198 0 : if(iL_in <= iR)
199 0 : MergeVertsFast(piCurNrUniqueVertices, piRemapTable, pfVertexDataOut, piVertexIDs,
200 : pfVertexDataIn, iNrVerticesIn, iFloatsPerVert, iL_in, iR, iChannelNum); // weld all left of fSep
201 0 : if(iL <= iR_in)
202 0 : MergeVertsFast(piCurNrUniqueVertices, piRemapTable, pfVertexDataOut, piVertexIDs,
203 : pfVertexDataIn, iNrVerticesIn, iFloatsPerVert, iL, iR_in, iChannelNum); // weld all right of (or equal to) fSep
204 : }
205 3 : }
206 :
|
