?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Change Encyclo button name and macros icon
[ryzomcore.git] / nel / src / 3d / stripifier.cpp
blob6453cbd1b4e5b03ae15f39cd9e5a768a729ecb26
1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
2 // Copyright (C) 2010 Winch Gate Property Limited
3 //
4 // This program is free software: you can redistribute it and/or modify
5 // it under the terms of the GNU Affero General Public License as
6 // published by the Free Software Foundation, either version 3 of the
7 // License, or (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU Affero General Public License for more details.
13 //
14 // You should have received a copy of the GNU Affero General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16
17 #include "std3d.h"
18
19 #include "nel/3d/stripifier.h"
20 // For now, don't use NVidia stripifier.
21 //#include "nv_tri_strip_objects.h"
22 #include <vector>
23 #include <deque>
24
25
26 using namespace std;
27
28 #ifdef DEBUG_NEW
29 #define new DEBUG_NEW
30 #endif
31
32 namespace NL3D
33 {
34
35
36 // ***************************************************************************
37 CStripifier::CStripifier()
38 {
39 }
40
41
42 // ***************************************************************************
43 /*
44 NVidia(tm) 's method get better performance (8ms on 50K faces meshe, instead of 8.9ms), but
45 precomputing is much slower (1'40 instead of 0'?? :) ).
46 */
47 /*void CStripifier::optimizeTriangles(const CIndexBuffer &in, CIndexBuffer &out, uint cacheSize)
48 {
49 NvStripifier stripifier;
50 WordVec inIndices;
51 NvStripInfoVec outStrips;
52 sint i;
53
54 // prepare inIndices.
55 inIndices.resize(in.getNumTri()*3);
56 for(i=0;i< (sint)inIndices.size(); i++)
57 {
58 inIndices[i]= in.getPtr()[i];
59 }
60
61 // build strips.
62 stripifier.Stripify(inIndices, cacheSize, outStrips);
63
64 // build triangles from strips, and release memory
65 out.setNumTri(0);
66 out.reserveTri(in.getNumTri());
67 for(i= 0;i< (sint)outStrips.size(); i++)
68 {
69 NvStripInfo *stripInfo= outStrips[i];
70
71 // build triangle from the strip.
72 for(uint j= 0;j< stripInfo->m_faces.size(); j++)
73 {
74 NvFaceInfo *face= stripInfo->m_faces[j];
75 out.addTri(face->m_v0, face->m_v1, face->m_v2);
76 // delete this face.
77 delete face;
78 }
79
80 // delete this strip.
81 // Unref first the edges touched by this strip.
82 NvEdgeInfo *edgeInfo = stripInfo->m_startInfo.m_startEdge;
83 while(edgeInfo)
84 {
85 NvEdgeInfo *edgeInfoNext= edgeInfo->m_nextV1;
86 edgeInfo->Unref();
87 edgeInfo= edgeInfoNext;
88 }
89 // delete
90 delete stripInfo;
91 }
92
93 }*/
94
95 // ***************************************************************************
96 struct CVertexCache
97 {
98 CVertexCache(sint cacheSize, sint nbVerts)
99 {
100 _VertexInCache.resize(nbVerts, 0);
101 _Cache.resize(cacheSize, 0xFFFFFFFF);
102 }
103
104 void touchVertex(uint vert)
105 {
106 if(isVertexInCache(vert))
107 {
108 // do nothing ?????? depends of vcache implementation
109 }
110 else
111 {
112 // pop front
113 uint removed= _Cache.front();
114 if(removed!=0xFFFFFFFF)
115 _VertexInCache[removed]= 0;
116 _Cache.pop_front();
117 // push_back
118 _VertexInCache[vert]= 3;
119 _Cache.push_back(vert);
120 }
121 }
122
123 bool isVertexInCache(uint vert)
124 {
125 return _VertexInCache[vert]==3;
126 }
127
128 // return which vertex is at which place in the cache. 0xFFFFFFFF if the entry is empty
129 uint getVertexInCache(uint vertIdInCache)
130 {
131 return _Cache[vertIdInCache];
132 }
133
134 void tempTouchVertex(uint vert, bool inCache)
135 {
136 if( _VertexInCache[vert]&1 )
137 {
138 if(inCache)
139 _VertexInCache[vert]|= 2;
140 else
141 _VertexInCache[vert]&= 1;
142 }
143 }
144
145 private:
146 // 0 if not in the cache
147 vector<uint8> _VertexInCache;
148 deque<uint32> _Cache;
149
150 };
151
152
153 // ***************************************************************************
154 struct COrderFace
155 {
156 sint v[3];
157 bool Inserted;
158
159 void insertInPB(CIndexBuffer &out, CVertexCache &vertexCache)
160 {
161 uint index = out.getNumIndexes ();
162 out.setNumIndexes (index+3);
163 CIndexBufferReadWrite ibaWrite;
164 out.lock (ibaWrite);
165 ibaWrite.setTri(index, v[0], v[1], v[2]);
166 vertexCache.touchVertex(v[0]);
167 vertexCache.touchVertex(v[1]);
168 vertexCache.touchVertex(v[2]);
169 Inserted= true;
170 }
171
172 sint countCacheMiss(CVertexCache &vertexCache)
173 {
174 sint ret=0 ;
175 if(!vertexCache.isVertexInCache(v[0])) ret++;
176 if(!vertexCache.isVertexInCache(v[1])) ret++;
177 if(!vertexCache.isVertexInCache(v[2])) ret++;
178 return ret;
179 }
180 };
181
182
183 // ***************************************************************************
184 struct CCornerNode
185 {
186 // next in the list
187 CCornerNode *Next;
188 // corner == tuple face/vertex.
189 uint FaceId;
190 uint VertexId;
191 };
192
193
194 // ***************************************************************************
195 void CStripifier::optimizeTriangles(const CIndexBuffer &in, CIndexBuffer &out, uint cacheSize)
196 {
197 vector<COrderFace> inFaces;
198 sint i;
199 sint numTris= in.getNumIndexes()/3;
200
201 // TestYoyo: All the same tri => perfect vertex caching...
202 /*out.setNumTri(numTris);
203 for(i=0;i< numTris; i++)
204 {
205 uint32 v0= *(in.getPtr()+0);
206 uint32 v1= *(in.getPtr()+1);
207 uint32 v2= *(in.getPtr()+2);
208 out.setTri(i, v0, v1, v2);
209 }
210 return;*/
211
212
213 // prepare inIndices.
214 //--------------------
215 {
216 CIndexBufferRead ibaRead;
217 in.lock (ibaRead);
218 inFaces.resize(numTris);
219 if (ibaRead.getFormat() == CIndexBuffer::Indices32)
220 {
221 for(i=0;i< numTris; i++)
222 {
223 const uint32 *ibaPtr = (const uint32 *) ibaRead.getPtr();
224 inFaces[i].v[0]= ibaPtr[i*3 + 0];
225 inFaces[i].v[1]= ibaPtr[i*3 + 1];
226 inFaces[i].v[2]= ibaPtr[i*3 + 2];
227 inFaces[i].Inserted= false;
228 }
229 }
230 else
231 {
232 nlassert(ibaRead.getFormat() == CIndexBuffer::Indices16);
233 for(i=0;i< numTris; i++)
234 {
235 const uint16 *ibaPtr = (const uint16 *) ibaRead.getPtr();
236 inFaces[i].v[0]= ibaPtr[i*3 + 0];
237 inFaces[i].v[1]= ibaPtr[i*3 + 1];
238 inFaces[i].v[2]= ibaPtr[i*3 + 2];
239 inFaces[i].Inserted= false;
240 }
241 }
242 }
243
244
245 // build our cache, and compute max number of vertices.
246 //--------------------
247 int numVerts=0;
248 for (i = 0; i < numTris; i++)
249 {
250 numVerts= max(numVerts, (int)inFaces[i].v[0]);
251 numVerts= max(numVerts, (int)inFaces[i].v[1]);
252 numVerts= max(numVerts, (int)inFaces[i].v[2]);
253 }
254 numVerts++;
255 CVertexCache vertexCache(cacheSize, numVerts);
256
257
258 // Compute vertex connectivity.
259 //--------------------
260 vector<CCornerNode*> vertexConnectivity;
261 vector<CCornerNode> cornerAllocator;
262 cornerAllocator.resize(numTris * 3);
263 vertexConnectivity.resize(numVerts, NULL);
264 // For all triangles.
265 for (i = 0; i < numTris; i++)
266 {
267 COrderFace *ordFace= &inFaces[i];
268 // For each corner, allocate and fill
269 for(sint j=0; j<3;j++)
270 {
271 sint vertexId= ordFace->v[j];
272
273 // allocate a corner
274 CCornerNode *corner= &cornerAllocator[i*3 + j];
275
276 // fill it.
277 corner->FaceId= i;
278 corner->VertexId= vertexId;
279 // Link it to the vertex list of faces.
280 corner->Next= vertexConnectivity[vertexId];
281 vertexConnectivity[vertexId]= corner;
282 }
283 }
284
285
286 // build output optimized triangles
287 //--------------------
288 out.setFormat(in.getFormat());
289 out.setNumIndexes(0);
290 out.reserve(3*numTris);
291
292 for(i=0; i<numTris; i++)
293 {
294 // force insertion of the ith face.
295 sint nextToInsert= i;
296 bool nextToInsertFound= true;
297 while( nextToInsertFound )
298 {
299 nextToInsertFound= false;
300
301 // if the face is not yet inserted.
302 if(!inFaces[nextToInsert].Inserted)
303 {
304 // must insert this face.
305 inFaces[nextToInsert].insertInPB(out, vertexCache);
306
307 sint minC= 3;
308
309 // look only for faces which use vertices in VertexCache, to get a face with at least one vertex.
310 for(uint j=0; j<cacheSize; j++)
311 {
312 // get a vertex from the vertex cache.
313 uint vertexId= vertexCache.getVertexInCache(j);
314 // if empty entry
315 if(vertexId==0xFFFFFFFF)
316 continue;
317
318 // parse list of faces which use this vertex.
319 CCornerNode *corner= vertexConnectivity[vertexId];
320 while(corner)
321 {
322 uint faceId= corner->FaceId;
323
324 // if the face is not yet inserted.
325 if(!inFaces[faceId].Inserted)
326 {
327 sint c= inFaces[faceId].countCacheMiss(vertexCache);
328 // insert first any face which don't add any vertex in the cache.
329 if(c==0)
330 {
331 inFaces[faceId].insertInPB(out, vertexCache);
332 }
333 // else the one which add the minimum of vertex possible: nextToInsert
334 else
335 {
336 // Add cost of faces that use vertices pushed out (better results...)
337 uint numVOut= c;
338 uint k;
339 for(k=cacheSize-numVOut; k<cacheSize; k++)
340 {
341 uint vertexOutId= vertexCache.getVertexInCache(k);
342 if(vertexOutId==0xFFFFFFFF)
343 continue;
344 // TempRemove the vertex from the cache
345 vertexCache.tempTouchVertex(vertexOutId, false);
346 }
347 // parse all faces that still use those out vertices.
348 for(k=cacheSize-numVOut; k<cacheSize; k++)
349 {
350 uint vertexOutId= vertexCache.getVertexInCache(k);
351 if(vertexOutId==0xFFFFFFFF)
352 continue;
353 CCornerNode *cornerOut= vertexConnectivity[vertexOutId];
354 while(cornerOut)
355 {
356 uint faceOutId= cornerOut->FaceId;
357
358 // if the face is not yet inserted AND not the one treated
359 if(!inFaces[faceOutId].Inserted && faceOutId!=faceId)
360 {
361 // Add cache miss of this face
362 c+= inFaces[faceOutId].countCacheMiss(vertexCache);
363 }
364
365 // next corner
366 cornerOut= cornerOut->Next;
367 }
368 }
369 // reset touch
370 for(k=cacheSize-numVOut; k<cacheSize; k++)
371 {
372 uint vertexOutId= vertexCache.getVertexInCache(k);
373 if(vertexOutId==0xFFFFFFFF)
374 continue;
375 // restore TempTouch the vertex from the cache
376 vertexCache.tempTouchVertex(vertexOutId, true);
377 }
378
379
380 // take the minimum cost
381 if(c<minC)
382 {
383 nextToInsert= faceId;
384 nextToInsertFound= true;
385 minC= c;
386 }
387 }
388 }
389
390 // next corner
391 corner= corner->Next;
392 }
393
394 }
395
396 // if nextToInsertFound, then nextToInsert has the face which add the minimum of vertex possible in the cache
397 }
398 }
399
400 }
401
402 }
403
404
405 } // NL3D