aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/src/others/irrlicht-1.8.1/source/Irrlicht/CMeshManipulator.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/others/irrlicht-1.8.1/source/Irrlicht/CMeshManipulator.cpp')
-rw-r--r--src/others/irrlicht-1.8.1/source/Irrlicht/CMeshManipulator.cpp1820
1 files changed, 1820 insertions, 0 deletions
diff --git a/src/others/irrlicht-1.8.1/source/Irrlicht/CMeshManipulator.cpp b/src/others/irrlicht-1.8.1/source/Irrlicht/CMeshManipulator.cpp
new file mode 100644
index 0000000..823c4e3
--- /dev/null
+++ b/src/others/irrlicht-1.8.1/source/Irrlicht/CMeshManipulator.cpp
@@ -0,0 +1,1820 @@
1// Copyright (C) 2002-2012 Nikolaus Gebhardt
2// This file is part of the "Irrlicht Engine".
3// For conditions of distribution and use, see copyright notice in irrlicht.h
4
5#include "CMeshManipulator.h"
6#include "SMesh.h"
7#include "CMeshBuffer.h"
8#include "SAnimatedMesh.h"
9#include "os.h"
10#include "irrMap.h"
11
12namespace irr
13{
14namespace scene
15{
16
17static inline core::vector3df getAngleWeight(const core::vector3df& v1,
18 const core::vector3df& v2,
19 const core::vector3df& v3)
20{
21 // Calculate this triangle's weight for each of its three vertices
22 // start by calculating the lengths of its sides
23 const f32 a = v2.getDistanceFromSQ(v3);
24 const f32 asqrt = sqrtf(a);
25 const f32 b = v1.getDistanceFromSQ(v3);
26 const f32 bsqrt = sqrtf(b);
27 const f32 c = v1.getDistanceFromSQ(v2);
28 const f32 csqrt = sqrtf(c);
29
30 // use them to find the angle at each vertex
31 return core::vector3df(
32 acosf((b + c - a) / (2.f * bsqrt * csqrt)),
33 acosf((-b + c + a) / (2.f * asqrt * csqrt)),
34 acosf((b - c + a) / (2.f * bsqrt * asqrt)));
35}
36
37
38//! Flips the direction of surfaces. Changes backfacing triangles to frontfacing
39//! triangles and vice versa.
40//! \param mesh: Mesh on which the operation is performed.
41void CMeshManipulator::flipSurfaces(scene::IMesh* mesh) const
42{
43 if (!mesh)
44 return;
45
46 const u32 bcount = mesh->getMeshBufferCount();
47 for (u32 b=0; b<bcount; ++b)
48 {
49 IMeshBuffer* buffer = mesh->getMeshBuffer(b);
50 const u32 idxcnt = buffer->getIndexCount();
51 if (buffer->getIndexType() == video::EIT_16BIT)
52 {
53 u16* idx = buffer->getIndices();
54 for (u32 i=0; i<idxcnt; i+=3)
55 {
56 const u16 tmp = idx[i+1];
57 idx[i+1] = idx[i+2];
58 idx[i+2] = tmp;
59 }
60 }
61 else
62 {
63 u32* idx = reinterpret_cast<u32*>(buffer->getIndices());
64 for (u32 i=0; i<idxcnt; i+=3)
65 {
66 const u32 tmp = idx[i+1];
67 idx[i+1] = idx[i+2];
68 idx[i+2] = tmp;
69 }
70 }
71 }
72}
73
74
75namespace
76{
77template <typename T>
78void recalculateNormalsT(IMeshBuffer* buffer, bool smooth, bool angleWeighted)
79{
80 const u32 vtxcnt = buffer->getVertexCount();
81 const u32 idxcnt = buffer->getIndexCount();
82 const T* idx = reinterpret_cast<T*>(buffer->getIndices());
83
84 if (!smooth)
85 {
86 for (u32 i=0; i<idxcnt; i+=3)
87 {
88 const core::vector3df& v1 = buffer->getPosition(idx[i+0]);
89 const core::vector3df& v2 = buffer->getPosition(idx[i+1]);
90 const core::vector3df& v3 = buffer->getPosition(idx[i+2]);
91 const core::vector3df normal = core::plane3d<f32>(v1, v2, v3).Normal;
92 buffer->getNormal(idx[i+0]) = normal;
93 buffer->getNormal(idx[i+1]) = normal;
94 buffer->getNormal(idx[i+2]) = normal;
95 }
96 }
97 else
98 {
99 u32 i;
100
101 for ( i = 0; i!= vtxcnt; ++i )
102 buffer->getNormal(i).set(0.f, 0.f, 0.f);
103
104 for ( i=0; i<idxcnt; i+=3)
105 {
106 const core::vector3df& v1 = buffer->getPosition(idx[i+0]);
107 const core::vector3df& v2 = buffer->getPosition(idx[i+1]);
108 const core::vector3df& v3 = buffer->getPosition(idx[i+2]);
109 const core::vector3df normal = core::plane3d<f32>(v1, v2, v3).Normal;
110
111 core::vector3df weight(1.f,1.f,1.f);
112 if (angleWeighted)
113 weight = irr::scene::getAngleWeight(v1,v2,v3); // writing irr::scene:: necessary for borland
114
115 buffer->getNormal(idx[i+0]) += weight.X*normal;
116 buffer->getNormal(idx[i+1]) += weight.Y*normal;
117 buffer->getNormal(idx[i+2]) += weight.Z*normal;
118 }
119
120 for ( i = 0; i!= vtxcnt; ++i )
121 buffer->getNormal(i).normalize();
122 }
123}
124}
125
126
127//! Recalculates all normals of the mesh buffer.
128/** \param buffer: Mesh buffer on which the operation is performed. */
129void CMeshManipulator::recalculateNormals(IMeshBuffer* buffer, bool smooth, bool angleWeighted) const
130{
131 if (!buffer)
132 return;
133
134 if (buffer->getIndexType()==video::EIT_16BIT)
135 recalculateNormalsT<u16>(buffer, smooth, angleWeighted);
136 else
137 recalculateNormalsT<u32>(buffer, smooth, angleWeighted);
138}
139
140
141//! Recalculates all normals of the mesh.
142//! \param mesh: Mesh on which the operation is performed.
143void CMeshManipulator::recalculateNormals(scene::IMesh* mesh, bool smooth, bool angleWeighted) const
144{
145 if (!mesh)
146 return;
147
148 const u32 bcount = mesh->getMeshBufferCount();
149 for ( u32 b=0; b<bcount; ++b)
150 recalculateNormals(mesh->getMeshBuffer(b), smooth, angleWeighted);
151}
152
153
154namespace
155{
156void calculateTangents(
157 core::vector3df& normal,
158 core::vector3df& tangent,
159 core::vector3df& binormal,
160 const core::vector3df& vt1, const core::vector3df& vt2, const core::vector3df& vt3, // vertices
161 const core::vector2df& tc1, const core::vector2df& tc2, const core::vector2df& tc3) // texture coords
162{
163 // choose one of them:
164 //#define USE_NVIDIA_GLH_VERSION // use version used by nvidia in glh headers
165 #define USE_IRR_VERSION
166
167#ifdef USE_IRR_VERSION
168
169 core::vector3df v1 = vt1 - vt2;
170 core::vector3df v2 = vt3 - vt1;
171 normal = v2.crossProduct(v1);
172 normal.normalize();
173
174 // binormal
175
176 f32 deltaX1 = tc1.X - tc2.X;
177 f32 deltaX2 = tc3.X - tc1.X;
178 binormal = (v1 * deltaX2) - (v2 * deltaX1);
179 binormal.normalize();
180
181 // tangent
182
183 f32 deltaY1 = tc1.Y - tc2.Y;
184 f32 deltaY2 = tc3.Y - tc1.Y;
185 tangent = (v1 * deltaY2) - (v2 * deltaY1);
186 tangent.normalize();
187
188 // adjust
189
190 core::vector3df txb = tangent.crossProduct(binormal);
191 if (txb.dotProduct(normal) < 0.0f)
192 {
193 tangent *= -1.0f;
194 binormal *= -1.0f;
195 }
196
197#endif // USE_IRR_VERSION
198
199#ifdef USE_NVIDIA_GLH_VERSION
200
201 tangent.set(0,0,0);
202 binormal.set(0,0,0);
203
204 core::vector3df v1(vt2.X - vt1.X, tc2.X - tc1.X, tc2.Y - tc1.Y);
205 core::vector3df v2(vt3.X - vt1.X, tc3.X - tc1.X, tc3.Y - tc1.Y);
206
207 core::vector3df txb = v1.crossProduct(v2);
208 if ( !core::iszero ( txb.X ) )
209 {
210 tangent.X = -txb.Y / txb.X;
211 binormal.X = -txb.Z / txb.X;
212 }
213
214 v1.X = vt2.Y - vt1.Y;
215 v2.X = vt3.Y - vt1.Y;
216 txb = v1.crossProduct(v2);
217
218 if ( !core::iszero ( txb.X ) )
219 {
220 tangent.Y = -txb.Y / txb.X;
221 binormal.Y = -txb.Z / txb.X;
222 }
223
224 v1.X = vt2.Z - vt1.Z;
225 v2.X = vt3.Z - vt1.Z;
226 txb = v1.crossProduct(v2);
227
228 if ( !core::iszero ( txb.X ) )
229 {
230 tangent.Z = -txb.Y / txb.X;
231 binormal.Z = -txb.Z / txb.X;
232 }
233
234 tangent.normalize();
235 binormal.normalize();
236
237 normal = tangent.crossProduct(binormal);
238 normal.normalize();
239
240 binormal = tangent.crossProduct(normal);
241 binormal.normalize();
242
243 core::plane3d<f32> pl(vt1, vt2, vt3);
244
245 if(normal.dotProduct(pl.Normal) < 0.0f )
246 normal *= -1.0f;
247
248#endif // USE_NVIDIA_GLH_VERSION
249}
250
251
252//! Recalculates tangents for a tangent mesh buffer
253template <typename T>
254void recalculateTangentsT(IMeshBuffer* buffer, bool recalculateNormals, bool smooth, bool angleWeighted)
255{
256 if (!buffer || (buffer->getVertexType()!= video::EVT_TANGENTS))
257 return;
258
259 const u32 vtxCnt = buffer->getVertexCount();
260 const u32 idxCnt = buffer->getIndexCount();
261
262 T* idx = reinterpret_cast<T*>(buffer->getIndices());
263 video::S3DVertexTangents* v =
264 (video::S3DVertexTangents*)buffer->getVertices();
265
266 if (smooth)
267 {
268 u32 i;
269
270 for ( i = 0; i!= vtxCnt; ++i )
271 {
272 if (recalculateNormals)
273 v[i].Normal.set( 0.f, 0.f, 0.f );
274 v[i].Tangent.set( 0.f, 0.f, 0.f );
275 v[i].Binormal.set( 0.f, 0.f, 0.f );
276 }
277
278 //Each vertex gets the sum of the tangents and binormals from the faces around it
279 for ( i=0; i<idxCnt; i+=3)
280 {
281 // if this triangle is degenerate, skip it!
282 if (v[idx[i+0]].Pos == v[idx[i+1]].Pos ||
283 v[idx[i+0]].Pos == v[idx[i+2]].Pos ||
284 v[idx[i+1]].Pos == v[idx[i+2]].Pos
285 /*||
286 v[idx[i+0]].TCoords == v[idx[i+1]].TCoords ||
287 v[idx[i+0]].TCoords == v[idx[i+2]].TCoords ||
288 v[idx[i+1]].TCoords == v[idx[i+2]].TCoords */
289 )
290 continue;
291
292 //Angle-weighted normals look better, but are slightly more CPU intensive to calculate
293 core::vector3df weight(1.f,1.f,1.f);
294 if (angleWeighted)
295 weight = irr::scene::getAngleWeight(v[i+0].Pos,v[i+1].Pos,v[i+2].Pos); // writing irr::scene:: necessary for borland
296 core::vector3df localNormal;
297 core::vector3df localTangent;
298 core::vector3df localBinormal;
299
300 calculateTangents(
301 localNormal,
302 localTangent,
303 localBinormal,
304 v[idx[i+0]].Pos,
305 v[idx[i+1]].Pos,
306 v[idx[i+2]].Pos,
307 v[idx[i+0]].TCoords,
308 v[idx[i+1]].TCoords,
309 v[idx[i+2]].TCoords);
310
311 if (recalculateNormals)
312 v[idx[i+0]].Normal += localNormal * weight.X;
313 v[idx[i+0]].Tangent += localTangent * weight.X;
314 v[idx[i+0]].Binormal += localBinormal * weight.X;
315
316 calculateTangents(
317 localNormal,
318 localTangent,
319 localBinormal,
320 v[idx[i+1]].Pos,
321 v[idx[i+2]].Pos,
322 v[idx[i+0]].Pos,
323 v[idx[i+1]].TCoords,
324 v[idx[i+2]].TCoords,
325 v[idx[i+0]].TCoords);
326
327 if (recalculateNormals)
328 v[idx[i+1]].Normal += localNormal * weight.Y;
329 v[idx[i+1]].Tangent += localTangent * weight.Y;
330 v[idx[i+1]].Binormal += localBinormal * weight.Y;
331
332 calculateTangents(
333 localNormal,
334 localTangent,
335 localBinormal,
336 v[idx[i+2]].Pos,
337 v[idx[i+0]].Pos,
338 v[idx[i+1]].Pos,
339 v[idx[i+2]].TCoords,
340 v[idx[i+0]].TCoords,
341 v[idx[i+1]].TCoords);
342
343 if (recalculateNormals)
344 v[idx[i+2]].Normal += localNormal * weight.Z;
345 v[idx[i+2]].Tangent += localTangent * weight.Z;
346 v[idx[i+2]].Binormal += localBinormal * weight.Z;
347 }
348
349 // Normalize the tangents and binormals
350 if (recalculateNormals)
351 {
352 for ( i = 0; i!= vtxCnt; ++i )
353 v[i].Normal.normalize();
354 }
355 for ( i = 0; i!= vtxCnt; ++i )
356 {
357 v[i].Tangent.normalize();
358 v[i].Binormal.normalize();
359 }
360 }
361 else
362 {
363 core::vector3df localNormal;
364 for (u32 i=0; i<idxCnt; i+=3)
365 {
366 calculateTangents(
367 localNormal,
368 v[idx[i+0]].Tangent,
369 v[idx[i+0]].Binormal,
370 v[idx[i+0]].Pos,
371 v[idx[i+1]].Pos,
372 v[idx[i+2]].Pos,
373 v[idx[i+0]].TCoords,
374 v[idx[i+1]].TCoords,
375 v[idx[i+2]].TCoords);
376 if (recalculateNormals)
377 v[idx[i+0]].Normal=localNormal;
378
379 calculateTangents(
380 localNormal,
381 v[idx[i+1]].Tangent,
382 v[idx[i+1]].Binormal,
383 v[idx[i+1]].Pos,
384 v[idx[i+2]].Pos,
385 v[idx[i+0]].Pos,
386 v[idx[i+1]].TCoords,
387 v[idx[i+2]].TCoords,
388 v[idx[i+0]].TCoords);
389 if (recalculateNormals)
390 v[idx[i+1]].Normal=localNormal;
391
392 calculateTangents(
393 localNormal,
394 v[idx[i+2]].Tangent,
395 v[idx[i+2]].Binormal,
396 v[idx[i+2]].Pos,
397 v[idx[i+0]].Pos,
398 v[idx[i+1]].Pos,
399 v[idx[i+2]].TCoords,
400 v[idx[i+0]].TCoords,
401 v[idx[i+1]].TCoords);
402 if (recalculateNormals)
403 v[idx[i+2]].Normal=localNormal;
404 }
405 }
406}
407}
408
409
410//! Recalculates tangents for a tangent mesh buffer
411void CMeshManipulator::recalculateTangents(IMeshBuffer* buffer, bool recalculateNormals, bool smooth, bool angleWeighted) const
412{
413 if (buffer && (buffer->getVertexType() == video::EVT_TANGENTS))
414 {
415 if (buffer->getIndexType() == video::EIT_16BIT)
416 recalculateTangentsT<u16>(buffer, recalculateNormals, smooth, angleWeighted);
417 else
418 recalculateTangentsT<u32>(buffer, recalculateNormals, smooth, angleWeighted);
419 }
420}
421
422
423//! Recalculates tangents for all tangent mesh buffers
424void CMeshManipulator::recalculateTangents(IMesh* mesh, bool recalculateNormals, bool smooth, bool angleWeighted) const
425{
426 if (!mesh)
427 return;
428
429 const u32 meshBufferCount = mesh->getMeshBufferCount();
430 for (u32 b=0; b<meshBufferCount; ++b)
431 {
432 recalculateTangents(mesh->getMeshBuffer(b), recalculateNormals, smooth, angleWeighted);
433 }
434}
435
436
437namespace
438{
439//! Creates a planar texture mapping on the meshbuffer
440template<typename T>
441void makePlanarTextureMappingT(scene::IMeshBuffer* buffer, f32 resolution)
442{
443 u32 idxcnt = buffer->getIndexCount();
444 T* idx = reinterpret_cast<T*>(buffer->getIndices());
445
446 for (u32 i=0; i<idxcnt; i+=3)
447 {
448 core::plane3df p(buffer->getPosition(idx[i+0]), buffer->getPosition(idx[i+1]), buffer->getPosition(idx[i+2]));
449 p.Normal.X = fabsf(p.Normal.X);
450 p.Normal.Y = fabsf(p.Normal.Y);
451 p.Normal.Z = fabsf(p.Normal.Z);
452 // calculate planar mapping worldspace coordinates
453
454 if (p.Normal.X > p.Normal.Y && p.Normal.X > p.Normal.Z)
455 {
456 for (u32 o=0; o!=3; ++o)
457 {
458 buffer->getTCoords(idx[i+o]).X = buffer->getPosition(idx[i+o]).Y * resolution;
459 buffer->getTCoords(idx[i+o]).Y = buffer->getPosition(idx[i+o]).Z * resolution;
460 }
461 }
462 else
463 if (p.Normal.Y > p.Normal.X && p.Normal.Y > p.Normal.Z)
464 {
465 for (u32 o=0; o!=3; ++o)
466 {
467 buffer->getTCoords(idx[i+o]).X = buffer->getPosition(idx[i+o]).X * resolution;
468 buffer->getTCoords(idx[i+o]).Y = buffer->getPosition(idx[i+o]).Z * resolution;
469 }
470 }
471 else
472 {
473 for (u32 o=0; o!=3; ++o)
474 {
475 buffer->getTCoords(idx[i+o]).X = buffer->getPosition(idx[i+o]).X * resolution;
476 buffer->getTCoords(idx[i+o]).Y = buffer->getPosition(idx[i+o]).Y * resolution;
477 }
478 }
479 }
480}
481}
482
483
484//! Creates a planar texture mapping on the meshbuffer
485void CMeshManipulator::makePlanarTextureMapping(scene::IMeshBuffer* buffer, f32 resolution) const
486{
487 if (!buffer)
488 return;
489
490 if (buffer->getIndexType()==video::EIT_16BIT)
491 makePlanarTextureMappingT<u16>(buffer, resolution);
492 else
493 makePlanarTextureMappingT<u32>(buffer, resolution);
494}
495
496
497//! Creates a planar texture mapping on the mesh
498void CMeshManipulator::makePlanarTextureMapping(scene::IMesh* mesh, f32 resolution) const
499{
500 if (!mesh)
501 return;
502
503 const u32 bcount = mesh->getMeshBufferCount();
504 for ( u32 b=0; b<bcount; ++b)
505 {
506 makePlanarTextureMapping(mesh->getMeshBuffer(b), resolution);
507 }
508}
509
510
511namespace
512{
513//! Creates a planar texture mapping on the meshbuffer
514template <typename T>
515void makePlanarTextureMappingT(scene::IMeshBuffer* buffer, f32 resolutionS, f32 resolutionT, u8 axis, const core::vector3df& offset)
516{
517 u32 idxcnt = buffer->getIndexCount();
518 T* idx = reinterpret_cast<T*>(buffer->getIndices());
519
520 for (u32 i=0; i<idxcnt; i+=3)
521 {
522 // calculate planar mapping worldspace coordinates
523 if (axis==0)
524 {
525 for (u32 o=0; o!=3; ++o)
526 {
527 buffer->getTCoords(idx[i+o]).X = 0.5f+(buffer->getPosition(idx[i+o]).Z + offset.Z) * resolutionS;
528 buffer->getTCoords(idx[i+o]).Y = 0.5f-(buffer->getPosition(idx[i+o]).Y + offset.Y) * resolutionT;
529 }
530 }
531 else if (axis==1)
532 {
533 for (u32 o=0; o!=3; ++o)
534 {
535 buffer->getTCoords(idx[i+o]).X = 0.5f+(buffer->getPosition(idx[i+o]).X + offset.X) * resolutionS;
536 buffer->getTCoords(idx[i+o]).Y = 1.f-(buffer->getPosition(idx[i+o]).Z + offset.Z) * resolutionT;
537 }
538 }
539 else if (axis==2)
540 {
541 for (u32 o=0; o!=3; ++o)
542 {
543 buffer->getTCoords(idx[i+o]).X = 0.5f+(buffer->getPosition(idx[i+o]).X + offset.X) * resolutionS;
544 buffer->getTCoords(idx[i+o]).Y = 0.5f-(buffer->getPosition(idx[i+o]).Y + offset.Y) * resolutionT;
545 }
546 }
547 }
548}
549}
550
551
552//! Creates a planar texture mapping on the meshbuffer
553void CMeshManipulator::makePlanarTextureMapping(scene::IMeshBuffer* buffer, f32 resolutionS, f32 resolutionT, u8 axis, const core::vector3df& offset) const
554{
555 if (!buffer)
556 return;
557
558 if (buffer->getIndexType()==video::EIT_16BIT)
559 makePlanarTextureMappingT<u16>(buffer, resolutionS, resolutionT, axis, offset);
560 else
561 makePlanarTextureMappingT<u32>(buffer, resolutionS, resolutionT, axis, offset);
562}
563
564
565//! Creates a planar texture mapping on the mesh
566void CMeshManipulator::makePlanarTextureMapping(scene::IMesh* mesh, f32 resolutionS, f32 resolutionT, u8 axis, const core::vector3df& offset) const
567{
568 if (!mesh)
569 return;
570
571 const u32 bcount = mesh->getMeshBufferCount();
572 for ( u32 b=0; b<bcount; ++b)
573 {
574 makePlanarTextureMapping(mesh->getMeshBuffer(b), resolutionS, resolutionT, axis, offset);
575 }
576}
577
578
579//! Clones a static IMesh into a modifyable SMesh.
580// not yet 32bit
581SMesh* CMeshManipulator::createMeshCopy(scene::IMesh* mesh) const
582{
583 if (!mesh)
584 return 0;
585
586 SMesh* clone = new SMesh();
587
588 const u32 meshBufferCount = mesh->getMeshBufferCount();
589
590 for ( u32 b=0; b<meshBufferCount; ++b)
591 {
592 const IMeshBuffer* const mb = mesh->getMeshBuffer(b);
593 switch(mb->getVertexType())
594 {
595 case video::EVT_STANDARD:
596 {
597 SMeshBuffer* buffer = new SMeshBuffer();
598 buffer->Material = mb->getMaterial();
599 const u32 vcount = mb->getVertexCount();
600 buffer->Vertices.reallocate(vcount);
601 video::S3DVertex* vertices = (video::S3DVertex*)mb->getVertices();
602 for (u32 i=0; i < vcount; ++i)
603 buffer->Vertices.push_back(vertices[i]);
604 const u32 icount = mb->getIndexCount();
605 buffer->Indices.reallocate(icount);
606 const u16* indices = mb->getIndices();
607 for (u32 i=0; i < icount; ++i)
608 buffer->Indices.push_back(indices[i]);
609 clone->addMeshBuffer(buffer);
610 buffer->drop();
611 }
612 break;
613 case video::EVT_2TCOORDS:
614 {
615 SMeshBufferLightMap* buffer = new SMeshBufferLightMap();
616 buffer->Material = mb->getMaterial();
617 const u32 vcount = mb->getVertexCount();
618 buffer->Vertices.reallocate(vcount);
619 video::S3DVertex2TCoords* vertices = (video::S3DVertex2TCoords*)mb->getVertices();
620 for (u32 i=0; i < vcount; ++i)
621 buffer->Vertices.push_back(vertices[i]);
622 const u32 icount = mb->getIndexCount();
623 buffer->Indices.reallocate(icount);
624 const u16* indices = mb->getIndices();
625 for (u32 i=0; i < icount; ++i)
626 buffer->Indices.push_back(indices[i]);
627 clone->addMeshBuffer(buffer);
628 buffer->drop();
629 }
630 break;
631 case video::EVT_TANGENTS:
632 {
633 SMeshBufferTangents* buffer = new SMeshBufferTangents();
634 buffer->Material = mb->getMaterial();
635 const u32 vcount = mb->getVertexCount();
636 buffer->Vertices.reallocate(vcount);
637 video::S3DVertexTangents* vertices = (video::S3DVertexTangents*)mb->getVertices();
638 for (u32 i=0; i < vcount; ++i)
639 buffer->Vertices.push_back(vertices[i]);
640 const u32 icount = mb->getIndexCount();
641 buffer->Indices.reallocate(icount);
642 const u16* indices = mb->getIndices();
643 for (u32 i=0; i < icount; ++i)
644 buffer->Indices.push_back(indices[i]);
645 clone->addMeshBuffer(buffer);
646 buffer->drop();
647 }
648 break;
649 }// end switch
650
651 }// end for all mesh buffers
652
653 clone->BoundingBox = mesh->getBoundingBox();
654 return clone;
655}
656
657
658//! Creates a copy of the mesh, which will only consist of unique primitives
659// not yet 32bit
660IMesh* CMeshManipulator::createMeshUniquePrimitives(IMesh* mesh) const
661{
662 if (!mesh)
663 return 0;
664
665 SMesh* clone = new SMesh();
666
667 const u32 meshBufferCount = mesh->getMeshBufferCount();
668
669 for ( u32 b=0; b<meshBufferCount; ++b)
670 {
671 const IMeshBuffer* const mb = mesh->getMeshBuffer(b);
672 const s32 idxCnt = mb->getIndexCount();
673 const u16* idx = mb->getIndices();
674
675 switch(mb->getVertexType())
676 {
677 case video::EVT_STANDARD:
678 {
679 SMeshBuffer* buffer = new SMeshBuffer();
680 buffer->Material = mb->getMaterial();
681
682 video::S3DVertex* v =
683 (video::S3DVertex*)mb->getVertices();
684
685 buffer->Vertices.reallocate(idxCnt);
686 buffer->Indices.reallocate(idxCnt);
687 for (s32 i=0; i<idxCnt; i += 3)
688 {
689 buffer->Vertices.push_back( v[idx[i + 0 ]] );
690 buffer->Vertices.push_back( v[idx[i + 1 ]] );
691 buffer->Vertices.push_back( v[idx[i + 2 ]] );
692
693 buffer->Indices.push_back( i + 0 );
694 buffer->Indices.push_back( i + 1 );
695 buffer->Indices.push_back( i + 2 );
696 }
697
698 buffer->setBoundingBox(mb->getBoundingBox());
699 clone->addMeshBuffer(buffer);
700 buffer->drop();
701 }
702 break;
703 case video::EVT_2TCOORDS:
704 {
705 SMeshBufferLightMap* buffer = new SMeshBufferLightMap();
706 buffer->Material = mb->getMaterial();
707
708 video::S3DVertex2TCoords* v =
709 (video::S3DVertex2TCoords*)mb->getVertices();
710
711 buffer->Vertices.reallocate(idxCnt);
712 buffer->Indices.reallocate(idxCnt);
713 for (s32 i=0; i<idxCnt; i += 3)
714 {
715 buffer->Vertices.push_back( v[idx[i + 0 ]] );
716 buffer->Vertices.push_back( v[idx[i + 1 ]] );
717 buffer->Vertices.push_back( v[idx[i + 2 ]] );
718
719 buffer->Indices.push_back( i + 0 );
720 buffer->Indices.push_back( i + 1 );
721 buffer->Indices.push_back( i + 2 );
722 }
723 buffer->setBoundingBox(mb->getBoundingBox());
724 clone->addMeshBuffer(buffer);
725 buffer->drop();
726 }
727 break;
728 case video::EVT_TANGENTS:
729 {
730 SMeshBufferTangents* buffer = new SMeshBufferTangents();
731 buffer->Material = mb->getMaterial();
732
733 video::S3DVertexTangents* v =
734 (video::S3DVertexTangents*)mb->getVertices();
735
736 buffer->Vertices.reallocate(idxCnt);
737 buffer->Indices.reallocate(idxCnt);
738 for (s32 i=0; i<idxCnt; i += 3)
739 {
740 buffer->Vertices.push_back( v[idx[i + 0 ]] );
741 buffer->Vertices.push_back( v[idx[i + 1 ]] );
742 buffer->Vertices.push_back( v[idx[i + 2 ]] );
743
744 buffer->Indices.push_back( i + 0 );
745 buffer->Indices.push_back( i + 1 );
746 buffer->Indices.push_back( i + 2 );
747 }
748
749 buffer->setBoundingBox(mb->getBoundingBox());
750 clone->addMeshBuffer(buffer);
751 buffer->drop();
752 }
753 break;
754 }// end switch
755
756 }// end for all mesh buffers
757
758 clone->BoundingBox = mesh->getBoundingBox();
759 return clone;
760}
761
762
763//! Creates a copy of a mesh, which will have identical vertices welded together
764// not yet 32bit
765IMesh* CMeshManipulator::createMeshWelded(IMesh *mesh, f32 tolerance) const
766{
767 SMesh* clone = new SMesh();
768 clone->BoundingBox = mesh->getBoundingBox();
769
770 core::array<u16> redirects;
771
772 for (u32 b=0; b<mesh->getMeshBufferCount(); ++b)
773 {
774 const IMeshBuffer* const mb = mesh->getMeshBuffer(b);
775 // reset redirect list
776 redirects.set_used(mb->getVertexCount());
777
778 const u16* indices = 0;
779 u32 indexCount = 0;
780 core::array<u16>* outIdx = 0;
781
782 switch(mb->getVertexType())
783 {
784 case video::EVT_STANDARD:
785 {
786 SMeshBuffer* buffer = new SMeshBuffer();
787 buffer->BoundingBox = mb->getBoundingBox();
788 buffer->Material = mb->getMaterial();
789 clone->addMeshBuffer(buffer);
790 buffer->drop();
791
792 video::S3DVertex* v =
793 (video::S3DVertex*)mb->getVertices();
794
795 u32 vertexCount = mb->getVertexCount();
796
797 indices = mb->getIndices();
798 indexCount = mb->getIndexCount();
799 outIdx = &buffer->Indices;
800
801 buffer->Vertices.reallocate(vertexCount);
802
803 for (u32 i=0; i < vertexCount; ++i)
804 {
805 bool found = false;
806 for (u32 j=0; j < i; ++j)
807 {
808 if ( v[i].Pos.equals( v[j].Pos, tolerance) &&
809 v[i].Normal.equals( v[j].Normal, tolerance) &&
810 v[i].TCoords.equals( v[j].TCoords ) &&
811 (v[i].Color == v[j].Color) )
812 {
813 redirects[i] = redirects[j];
814 found = true;
815 break;
816 }
817 }
818 if (!found)
819 {
820 redirects[i] = buffer->Vertices.size();
821 buffer->Vertices.push_back(v[i]);
822 }
823 }
824
825 break;
826 }
827 case video::EVT_2TCOORDS:
828 {
829 SMeshBufferLightMap* buffer = new SMeshBufferLightMap();
830 buffer->BoundingBox = mb->getBoundingBox();
831 buffer->Material = mb->getMaterial();
832 clone->addMeshBuffer(buffer);
833 buffer->drop();
834
835 video::S3DVertex2TCoords* v =
836 (video::S3DVertex2TCoords*)mb->getVertices();
837
838 u32 vertexCount = mb->getVertexCount();
839
840 indices = mb->getIndices();
841 indexCount = mb->getIndexCount();
842 outIdx = &buffer->Indices;
843
844 buffer->Vertices.reallocate(vertexCount);
845
846 for (u32 i=0; i < vertexCount; ++i)
847 {
848 bool found = false;
849 for (u32 j=0; j < i; ++j)
850 {
851 if ( v[i].Pos.equals( v[j].Pos, tolerance) &&
852 v[i].Normal.equals( v[j].Normal, tolerance) &&
853 v[i].TCoords.equals( v[j].TCoords ) &&
854 v[i].TCoords2.equals( v[j].TCoords2 ) &&
855 (v[i].Color == v[j].Color) )
856 {
857 redirects[i] = redirects[j];
858 found = true;
859 break;
860 }
861 }
862 if (!found)
863 {
864 redirects[i] = buffer->Vertices.size();
865 buffer->Vertices.push_back(v[i]);
866 }
867 }
868 break;
869 }
870 case video::EVT_TANGENTS:
871 {
872 SMeshBufferTangents* buffer = new SMeshBufferTangents();
873 buffer->BoundingBox = mb->getBoundingBox();
874 buffer->Material = mb->getMaterial();
875 clone->addMeshBuffer(buffer);
876 buffer->drop();
877
878 video::S3DVertexTangents* v =
879 (video::S3DVertexTangents*)mb->getVertices();
880
881 u32 vertexCount = mb->getVertexCount();
882
883 indices = mb->getIndices();
884 indexCount = mb->getIndexCount();
885 outIdx = &buffer->Indices;
886
887 buffer->Vertices.reallocate(vertexCount);
888
889 for (u32 i=0; i < vertexCount; ++i)
890 {
891 bool found = false;
892 for (u32 j=0; j < i; ++j)
893 {
894 if ( v[i].Pos.equals( v[j].Pos, tolerance) &&
895 v[i].Normal.equals( v[j].Normal, tolerance) &&
896 v[i].TCoords.equals( v[j].TCoords ) &&
897 v[i].Tangent.equals( v[j].Tangent, tolerance ) &&
898 v[i].Binormal.equals( v[j].Binormal, tolerance ) &&
899 (v[i].Color == v[j].Color) )
900 {
901 redirects[i] = redirects[j];
902 found = true;
903 break;
904 }
905 }
906 if (!found)
907 {
908 redirects[i] = buffer->Vertices.size();
909 buffer->Vertices.push_back(v[i]);
910 }
911 }
912 break;
913 }
914 default:
915 os::Printer::log("Cannot create welded mesh, vertex type unsupported", ELL_ERROR);
916 break;
917 }
918
919 // write the buffer's index list
920 core::array<u16> &Indices = *outIdx;
921
922 Indices.set_used(indexCount);
923 for (u32 i=0; i<indexCount; ++i)
924 {
925 Indices[i] = redirects[ indices[i] ];
926 }
927 }
928 return clone;
929}
930
931
932//! Creates a copy of the mesh, which will only consist of S3DVertexTangents vertices.
933// not yet 32bit
934IMesh* CMeshManipulator::createMeshWithTangents(IMesh* mesh, bool recalculateNormals, bool smooth, bool angleWeighted, bool calculateTangents) const
935{
936 if (!mesh)
937 return 0;
938
939 // copy mesh and fill data into SMeshBufferTangents
940
941 SMesh* clone = new SMesh();
942 const u32 meshBufferCount = mesh->getMeshBufferCount();
943
944 for (u32 b=0; b<meshBufferCount; ++b)
945 {
946 const IMeshBuffer* const original = mesh->getMeshBuffer(b);
947 const u32 idxCnt = original->getIndexCount();
948 const u16* idx = original->getIndices();
949
950 SMeshBufferTangents* buffer = new SMeshBufferTangents();
951
952 buffer->Material = original->getMaterial();
953 buffer->Vertices.reallocate(idxCnt);
954 buffer->Indices.reallocate(idxCnt);
955
956 core::map<video::S3DVertexTangents, int> vertMap;
957 int vertLocation;
958
959 // copy vertices
960
961 const video::E_VERTEX_TYPE vType = original->getVertexType();
962 video::S3DVertexTangents vNew;
963 for (u32 i=0; i<idxCnt; ++i)
964 {
965 switch(vType)
966 {
967 case video::EVT_STANDARD:
968 {
969 const video::S3DVertex* v =
970 (const video::S3DVertex*)original->getVertices();
971 vNew = video::S3DVertexTangents(
972 v[idx[i]].Pos, v[idx[i]].Normal, v[idx[i]].Color, v[idx[i]].TCoords);
973 }
974 break;
975 case video::EVT_2TCOORDS:
976 {
977 const video::S3DVertex2TCoords* v =
978 (const video::S3DVertex2TCoords*)original->getVertices();
979 vNew = video::S3DVertexTangents(
980 v[idx[i]].Pos, v[idx[i]].Normal, v[idx[i]].Color, v[idx[i]].TCoords);
981 }
982 break;
983 case video::EVT_TANGENTS:
984 {
985 const video::S3DVertexTangents* v =
986 (const video::S3DVertexTangents*)original->getVertices();
987 vNew = v[idx[i]];
988 }
989 break;
990 }
991 core::map<video::S3DVertexTangents, int>::Node* n = vertMap.find(vNew);
992 if (n)
993 {
994 vertLocation = n->getValue();
995 }
996 else
997 {
998 vertLocation = buffer->Vertices.size();
999 buffer->Vertices.push_back(vNew);
1000 vertMap.insert(vNew, vertLocation);
1001 }
1002
1003 // create new indices
1004 buffer->Indices.push_back(vertLocation);
1005 }
1006 buffer->recalculateBoundingBox();
1007
1008 // add new buffer
1009 clone->addMeshBuffer(buffer);
1010 buffer->drop();
1011 }
1012
1013 clone->recalculateBoundingBox();
1014 if (calculateTangents)
1015 recalculateTangents(clone, recalculateNormals, smooth, angleWeighted);
1016
1017 return clone;
1018}
1019
1020
1021//! Creates a copy of the mesh, which will only consist of S3DVertex2TCoords vertices.
1022// not yet 32bit
1023IMesh* CMeshManipulator::createMeshWith2TCoords(IMesh* mesh) const
1024{
1025 if (!mesh)
1026 return 0;
1027
1028 // copy mesh and fill data into SMeshBufferLightMap
1029
1030 SMesh* clone = new SMesh();
1031 const u32 meshBufferCount = mesh->getMeshBufferCount();
1032
1033 for (u32 b=0; b<meshBufferCount; ++b)
1034 {
1035 const IMeshBuffer* const original = mesh->getMeshBuffer(b);
1036 const u32 idxCnt = original->getIndexCount();
1037 const u16* idx = original->getIndices();
1038
1039 SMeshBufferLightMap* buffer = new SMeshBufferLightMap();
1040 buffer->Material = original->getMaterial();
1041 buffer->Vertices.reallocate(idxCnt);
1042 buffer->Indices.reallocate(idxCnt);
1043
1044 core::map<video::S3DVertex2TCoords, int> vertMap;
1045 int vertLocation;
1046
1047 // copy vertices
1048
1049 const video::E_VERTEX_TYPE vType = original->getVertexType();
1050 video::S3DVertex2TCoords vNew;
1051 for (u32 i=0; i<idxCnt; ++i)
1052 {
1053 switch(vType)
1054 {
1055 case video::EVT_STANDARD:
1056 {
1057 const video::S3DVertex* v =
1058 (const video::S3DVertex*)original->getVertices();
1059 vNew = video::S3DVertex2TCoords(
1060 v[idx[i]].Pos, v[idx[i]].Normal, v[idx[i]].Color, v[idx[i]].TCoords, v[idx[i]].TCoords);
1061 }
1062 break;
1063 case video::EVT_2TCOORDS:
1064 {
1065 const video::S3DVertex2TCoords* v =
1066 (const video::S3DVertex2TCoords*)original->getVertices();
1067 vNew = v[idx[i]];
1068 }
1069 break;
1070 case video::EVT_TANGENTS:
1071 {
1072 const video::S3DVertexTangents* v =
1073 (const video::S3DVertexTangents*)original->getVertices();
1074 vNew = video::S3DVertex2TCoords(
1075 v[idx[i]].Pos, v[idx[i]].Normal, v[idx[i]].Color, v[idx[i]].TCoords, v[idx[i]].TCoords);
1076 }
1077 break;
1078 }
1079 core::map<video::S3DVertex2TCoords, int>::Node* n = vertMap.find(vNew);
1080 if (n)
1081 {
1082 vertLocation = n->getValue();
1083 }
1084 else
1085 {
1086 vertLocation = buffer->Vertices.size();
1087 buffer->Vertices.push_back(vNew);
1088 vertMap.insert(vNew, vertLocation);
1089 }
1090
1091 // create new indices
1092 buffer->Indices.push_back(vertLocation);
1093 }
1094 buffer->recalculateBoundingBox();
1095
1096 // add new buffer
1097 clone->addMeshBuffer(buffer);
1098 buffer->drop();
1099 }
1100
1101 clone->recalculateBoundingBox();
1102 return clone;
1103}
1104
1105
1106//! Creates a copy of the mesh, which will only consist of S3DVertex vertices.
1107// not yet 32bit
1108IMesh* CMeshManipulator::createMeshWith1TCoords(IMesh* mesh) const
1109{
1110 if (!mesh)
1111 return 0;
1112
1113 // copy mesh and fill data into SMeshBuffer
1114 SMesh* clone = new SMesh();
1115 const u32 meshBufferCount = mesh->getMeshBufferCount();
1116
1117 for (u32 b=0; b<meshBufferCount; ++b)
1118 {
1119 IMeshBuffer* original = mesh->getMeshBuffer(b);
1120 const u32 idxCnt = original->getIndexCount();
1121 const u16* idx = original->getIndices();
1122
1123 SMeshBuffer* buffer = new SMeshBuffer();
1124 buffer->Material = original->getMaterial();
1125 buffer->Vertices.reallocate(idxCnt);
1126 buffer->Indices.reallocate(idxCnt);
1127
1128 core::map<video::S3DVertex, int> vertMap;
1129 int vertLocation;
1130
1131 // copy vertices
1132 const video::E_VERTEX_TYPE vType = original->getVertexType();
1133 video::S3DVertex vNew;
1134 for (u32 i=0; i<idxCnt; ++i)
1135 {
1136 switch(vType)
1137 {
1138 case video::EVT_STANDARD:
1139 {
1140 video::S3DVertex* v =
1141 (video::S3DVertex*)original->getVertices();
1142 vNew = v[idx[i]];
1143 }
1144 break;
1145 case video::EVT_2TCOORDS:
1146 {
1147 video::S3DVertex2TCoords* v =
1148 (video::S3DVertex2TCoords*)original->getVertices();
1149 vNew = video::S3DVertex(
1150 v[idx[i]].Pos, v[idx[i]].Normal, v[idx[i]].Color, v[idx[i]].TCoords);
1151 }
1152 break;
1153 case video::EVT_TANGENTS:
1154 {
1155 video::S3DVertexTangents* v =
1156 (video::S3DVertexTangents*)original->getVertices();
1157 vNew = video::S3DVertex(
1158 v[idx[i]].Pos, v[idx[i]].Normal, v[idx[i]].Color, v[idx[i]].TCoords);
1159 }
1160 break;
1161 }
1162 core::map<video::S3DVertex, int>::Node* n = vertMap.find(vNew);
1163 if (n)
1164 {
1165 vertLocation = n->getValue();
1166 }
1167 else
1168 {
1169 vertLocation = buffer->Vertices.size();
1170 buffer->Vertices.push_back(vNew);
1171 vertMap.insert(vNew, vertLocation);
1172 }
1173
1174 // create new indices
1175 buffer->Indices.push_back(vertLocation);
1176 }
1177 buffer->recalculateBoundingBox();
1178 // add new buffer
1179 clone->addMeshBuffer(buffer);
1180 buffer->drop();
1181 }
1182
1183 clone->recalculateBoundingBox();
1184 return clone;
1185}
1186
1187
1188//! Returns amount of polygons in mesh.
1189s32 CMeshManipulator::getPolyCount(scene::IMesh* mesh) const
1190{
1191 if (!mesh)
1192 return 0;
1193
1194 s32 trianglecount = 0;
1195
1196 for (u32 g=0; g<mesh->getMeshBufferCount(); ++g)
1197 trianglecount += mesh->getMeshBuffer(g)->getIndexCount() / 3;
1198
1199 return trianglecount;
1200}
1201
1202
1203//! Returns amount of polygons in mesh.
1204s32 CMeshManipulator::getPolyCount(scene::IAnimatedMesh* mesh) const
1205{
1206 if (mesh && mesh->getFrameCount() != 0)
1207 return getPolyCount(mesh->getMesh(0));
1208
1209 return 0;
1210}
1211
1212
1213//! create a new AnimatedMesh and adds the mesh to it
1214IAnimatedMesh * CMeshManipulator::createAnimatedMesh(scene::IMesh* mesh, scene::E_ANIMATED_MESH_TYPE type) const
1215{
1216 return new SAnimatedMesh(mesh, type);
1217}
1218
1219namespace
1220{
1221
1222struct vcache
1223{
1224 core::array<u32> tris;
1225 float score;
1226 s16 cachepos;
1227 u16 NumActiveTris;
1228};
1229
1230struct tcache
1231{
1232 u16 ind[3];
1233 float score;
1234 bool drawn;
1235};
1236
1237const u16 cachesize = 32;
1238
1239float FindVertexScore(vcache *v)
1240{
1241 const float CacheDecayPower = 1.5f;
1242 const float LastTriScore = 0.75f;
1243 const float ValenceBoostScale = 2.0f;
1244 const float ValenceBoostPower = 0.5f;
1245 const float MaxSizeVertexCache = 32.0f;
1246
1247 if (v->NumActiveTris == 0)
1248 {
1249 // No tri needs this vertex!
1250 return -1.0f;
1251 }
1252
1253 float Score = 0.0f;
1254 int CachePosition = v->cachepos;
1255 if (CachePosition < 0)
1256 {
1257 // Vertex is not in FIFO cache - no score.
1258 }
1259 else
1260 {
1261 if (CachePosition < 3)
1262 {
1263 // This vertex was used in the last triangle,
1264 // so it has a fixed score.
1265 Score = LastTriScore;
1266 }
1267 else
1268 {
1269 // Points for being high in the cache.
1270 const float Scaler = 1.0f / (MaxSizeVertexCache - 3);
1271 Score = 1.0f - (CachePosition - 3) * Scaler;
1272 Score = powf(Score, CacheDecayPower);
1273 }
1274 }
1275
1276 // Bonus points for having a low number of tris still to
1277 // use the vert, so we get rid of lone verts quickly.
1278 float ValenceBoost = powf(v->NumActiveTris,
1279 -ValenceBoostPower);
1280 Score += ValenceBoostScale * ValenceBoost;
1281
1282 return Score;
1283}
1284
1285/*
1286 A specialized LRU cache for the Forsyth algorithm.
1287*/
1288
1289class f_lru
1290{
1291
1292public:
1293 f_lru(vcache *v, tcache *t): vc(v), tc(t)
1294 {
1295 for (u16 i = 0; i < cachesize; i++)
1296 {
1297 cache[i] = -1;
1298 }
1299 }
1300
1301 // Adds this vertex index and returns the highest-scoring triangle index
1302 u32 add(u16 vert, bool updatetris = false)
1303 {
1304 bool found = false;
1305
1306 // Mark existing pos as empty
1307 for (u16 i = 0; i < cachesize; i++)
1308 {
1309 if (cache[i] == vert)
1310 {
1311 // Move everything down
1312 for (u16 j = i; j; j--)
1313 {
1314 cache[j] = cache[j - 1];
1315 }
1316
1317 found = true;
1318 break;
1319 }
1320 }
1321
1322 if (!found)
1323 {
1324 if (cache[cachesize-1] != -1)
1325 vc[cache[cachesize-1]].cachepos = -1;
1326
1327 // Move everything down
1328 for (u16 i = cachesize - 1; i; i--)
1329 {
1330 cache[i] = cache[i - 1];
1331 }
1332 }
1333
1334 cache[0] = vert;
1335
1336 u32 highest = 0;
1337 float hiscore = 0;
1338
1339 if (updatetris)
1340 {
1341 // Update cache positions
1342 for (u16 i = 0; i < cachesize; i++)
1343 {
1344 if (cache[i] == -1)
1345 break;
1346
1347 vc[cache[i]].cachepos = i;
1348 vc[cache[i]].score = FindVertexScore(&vc[cache[i]]);
1349 }
1350
1351 // Update triangle scores
1352 for (u16 i = 0; i < cachesize; i++)
1353 {
1354 if (cache[i] == -1)
1355 break;
1356
1357 const u16 trisize = vc[cache[i]].tris.size();
1358 for (u16 t = 0; t < trisize; t++)
1359 {
1360 tcache *tri = &tc[vc[cache[i]].tris[t]];
1361
1362 tri->score =
1363 vc[tri->ind[0]].score +
1364 vc[tri->ind[1]].score +
1365 vc[tri->ind[2]].score;
1366
1367 if (tri->score > hiscore)
1368 {
1369 hiscore = tri->score;
1370 highest = vc[cache[i]].tris[t];
1371 }
1372 }
1373 }
1374 }
1375
1376 return highest;
1377 }
1378
1379private:
1380 s32 cache[cachesize];
1381 vcache *vc;
1382 tcache *tc;
1383};
1384
1385} // end anonymous namespace
1386
1387/**
1388Vertex cache optimization according to the Forsyth paper:
1389http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html
1390
1391The function is thread-safe (read: you can optimize several meshes in different threads)
1392
1393\param mesh Source mesh for the operation. */
1394IMesh* CMeshManipulator::createForsythOptimizedMesh(const IMesh *mesh) const
1395{
1396 if (!mesh)
1397 return 0;
1398
1399 SMesh *newmesh = new SMesh();
1400 newmesh->BoundingBox = mesh->getBoundingBox();
1401
1402 const u32 mbcount = mesh->getMeshBufferCount();
1403
1404 for (u32 b = 0; b < mbcount; ++b)
1405 {
1406 const IMeshBuffer *mb = mesh->getMeshBuffer(b);
1407
1408 if (mb->getIndexType() != video::EIT_16BIT)
1409 {
1410 os::Printer::log("Cannot optimize a mesh with 32bit indices", ELL_ERROR);
1411 newmesh->drop();
1412 return 0;
1413 }
1414
1415 const u32 icount = mb->getIndexCount();
1416 const u32 tcount = icount / 3;
1417 const u32 vcount = mb->getVertexCount();
1418 const u16 *ind = mb->getIndices();
1419
1420 vcache *vc = new vcache[vcount];
1421 tcache *tc = new tcache[tcount];
1422
1423 f_lru lru(vc, tc);
1424
1425 // init
1426 for (u16 i = 0; i < vcount; i++)
1427 {
1428 vc[i].score = 0;
1429 vc[i].cachepos = -1;
1430 vc[i].NumActiveTris = 0;
1431 }
1432
1433 // First pass: count how many times a vert is used
1434 for (u32 i = 0; i < icount; i += 3)
1435 {
1436 vc[ind[i]].NumActiveTris++;
1437 vc[ind[i + 1]].NumActiveTris++;
1438 vc[ind[i + 2]].NumActiveTris++;
1439
1440 const u32 tri_ind = i/3;
1441 tc[tri_ind].ind[0] = ind[i];
1442 tc[tri_ind].ind[1] = ind[i + 1];
1443 tc[tri_ind].ind[2] = ind[i + 2];
1444 }
1445
1446 // Second pass: list of each triangle
1447 for (u32 i = 0; i < tcount; i++)
1448 {
1449 vc[tc[i].ind[0]].tris.push_back(i);
1450 vc[tc[i].ind[1]].tris.push_back(i);
1451 vc[tc[i].ind[2]].tris.push_back(i);
1452
1453 tc[i].drawn = false;
1454 }
1455
1456 // Give initial scores
1457 for (u16 i = 0; i < vcount; i++)
1458 {
1459 vc[i].score = FindVertexScore(&vc[i]);
1460 }
1461 for (u32 i = 0; i < tcount; i++)
1462 {
1463 tc[i].score =
1464 vc[tc[i].ind[0]].score +
1465 vc[tc[i].ind[1]].score +
1466 vc[tc[i].ind[2]].score;
1467 }
1468
1469 switch(mb->getVertexType())
1470 {
1471 case video::EVT_STANDARD:
1472 {
1473 video::S3DVertex *v = (video::S3DVertex *) mb->getVertices();
1474
1475 SMeshBuffer *buf = new SMeshBuffer();
1476 buf->Material = mb->getMaterial();
1477
1478 buf->Vertices.reallocate(vcount);
1479 buf->Indices.reallocate(icount);
1480
1481 core::map<const video::S3DVertex, const u16> sind; // search index for fast operation
1482 typedef core::map<const video::S3DVertex, const u16>::Node snode;
1483
1484 // Main algorithm
1485 u32 highest = 0;
1486 u32 drawcalls = 0;
1487 for (;;)
1488 {
1489 if (tc[highest].drawn)
1490 {
1491 bool found = false;
1492 float hiscore = 0;
1493 for (u32 t = 0; t < tcount; t++)
1494 {
1495 if (!tc[t].drawn)
1496 {
1497 if (tc[t].score > hiscore)
1498 {
1499 highest = t;
1500 hiscore = tc[t].score;
1501 found = true;
1502 }
1503 }
1504 }
1505 if (!found)
1506 break;
1507 }
1508
1509 // Output the best triangle
1510 u16 newind = buf->Vertices.size();
1511
1512 snode *s = sind.find(v[tc[highest].ind[0]]);
1513
1514 if (!s)
1515 {
1516 buf->Vertices.push_back(v[tc[highest].ind[0]]);
1517 buf->Indices.push_back(newind);
1518 sind.insert(v[tc[highest].ind[0]], newind);
1519 newind++;
1520 }
1521 else
1522 {
1523 buf->Indices.push_back(s->getValue());
1524 }
1525
1526 s = sind.find(v[tc[highest].ind[1]]);
1527
1528 if (!s)
1529 {
1530 buf->Vertices.push_back(v[tc[highest].ind[1]]);
1531 buf->Indices.push_back(newind);
1532 sind.insert(v[tc[highest].ind[1]], newind);
1533 newind++;
1534 }
1535 else
1536 {
1537 buf->Indices.push_back(s->getValue());
1538 }
1539
1540 s = sind.find(v[tc[highest].ind[2]]);
1541
1542 if (!s)
1543 {
1544 buf->Vertices.push_back(v[tc[highest].ind[2]]);
1545 buf->Indices.push_back(newind);
1546 sind.insert(v[tc[highest].ind[2]], newind);
1547 }
1548 else
1549 {
1550 buf->Indices.push_back(s->getValue());
1551 }
1552
1553 vc[tc[highest].ind[0]].NumActiveTris--;
1554 vc[tc[highest].ind[1]].NumActiveTris--;
1555 vc[tc[highest].ind[2]].NumActiveTris--;
1556
1557 tc[highest].drawn = true;
1558
1559 for (u16 j = 0; j < 3; j++)
1560 {
1561 vcache *vert = &vc[tc[highest].ind[j]];
1562 for (u16 t = 0; t < vert->tris.size(); t++)
1563 {
1564 if (highest == vert->tris[t])
1565 {
1566 vert->tris.erase(t);
1567 break;
1568 }
1569 }
1570 }
1571
1572 lru.add(tc[highest].ind[0]);
1573 lru.add(tc[highest].ind[1]);
1574 highest = lru.add(tc[highest].ind[2], true);
1575 drawcalls++;
1576 }
1577
1578 buf->setBoundingBox(mb->getBoundingBox());
1579 newmesh->addMeshBuffer(buf);
1580 buf->drop();
1581 }
1582 break;
1583 case video::EVT_2TCOORDS:
1584 {
1585 video::S3DVertex2TCoords *v = (video::S3DVertex2TCoords *) mb->getVertices();
1586
1587 SMeshBufferLightMap *buf = new SMeshBufferLightMap();
1588 buf->Material = mb->getMaterial();
1589
1590 buf->Vertices.reallocate(vcount);
1591 buf->Indices.reallocate(icount);
1592
1593 core::map<const video::S3DVertex2TCoords, const u16> sind; // search index for fast operation
1594 typedef core::map<const video::S3DVertex2TCoords, const u16>::Node snode;
1595
1596 // Main algorithm
1597 u32 highest = 0;
1598 u32 drawcalls = 0;
1599 for (;;)
1600 {
1601 if (tc[highest].drawn)
1602 {
1603 bool found = false;
1604 float hiscore = 0;
1605 for (u32 t = 0; t < tcount; t++)
1606 {
1607 if (!tc[t].drawn)
1608 {
1609 if (tc[t].score > hiscore)
1610 {
1611 highest = t;
1612 hiscore = tc[t].score;
1613 found = true;
1614 }
1615 }
1616 }
1617 if (!found)
1618 break;
1619 }
1620
1621 // Output the best triangle
1622 u16 newind = buf->Vertices.size();
1623
1624 snode *s = sind.find(v[tc[highest].ind[0]]);
1625
1626 if (!s)
1627 {
1628 buf->Vertices.push_back(v[tc[highest].ind[0]]);
1629 buf->Indices.push_back(newind);
1630 sind.insert(v[tc[highest].ind[0]], newind);
1631 newind++;
1632 }
1633 else
1634 {
1635 buf->Indices.push_back(s->getValue());
1636 }
1637
1638 s = sind.find(v[tc[highest].ind[1]]);
1639
1640 if (!s)
1641 {
1642 buf->Vertices.push_back(v[tc[highest].ind[1]]);
1643 buf->Indices.push_back(newind);
1644 sind.insert(v[tc[highest].ind[1]], newind);
1645 newind++;
1646 }
1647 else
1648 {
1649 buf->Indices.push_back(s->getValue());
1650 }
1651
1652 s = sind.find(v[tc[highest].ind[2]]);
1653
1654 if (!s)
1655 {
1656 buf->Vertices.push_back(v[tc[highest].ind[2]]);
1657 buf->Indices.push_back(newind);
1658 sind.insert(v[tc[highest].ind[2]], newind);
1659 }
1660 else
1661 {
1662 buf->Indices.push_back(s->getValue());
1663 }
1664
1665 vc[tc[highest].ind[0]].NumActiveTris--;
1666 vc[tc[highest].ind[1]].NumActiveTris--;
1667 vc[tc[highest].ind[2]].NumActiveTris--;
1668
1669 tc[highest].drawn = true;
1670
1671 for (u16 j = 0; j < 3; j++)
1672 {
1673 vcache *vert = &vc[tc[highest].ind[j]];
1674 for (u16 t = 0; t < vert->tris.size(); t++)
1675 {
1676 if (highest == vert->tris[t])
1677 {
1678 vert->tris.erase(t);
1679 break;
1680 }
1681 }
1682 }
1683
1684 lru.add(tc[highest].ind[0]);
1685 lru.add(tc[highest].ind[1]);
1686 highest = lru.add(tc[highest].ind[2]);
1687 drawcalls++;
1688 }
1689
1690 buf->setBoundingBox(mb->getBoundingBox());
1691 newmesh->addMeshBuffer(buf);
1692 buf->drop();
1693
1694 }
1695 break;
1696 case video::EVT_TANGENTS:
1697 {
1698 video::S3DVertexTangents *v = (video::S3DVertexTangents *) mb->getVertices();
1699
1700 SMeshBufferTangents *buf = new SMeshBufferTangents();
1701 buf->Material = mb->getMaterial();
1702
1703 buf->Vertices.reallocate(vcount);
1704 buf->Indices.reallocate(icount);
1705
1706 core::map<const video::S3DVertexTangents, const u16> sind; // search index for fast operation
1707 typedef core::map<const video::S3DVertexTangents, const u16>::Node snode;
1708
1709 // Main algorithm
1710 u32 highest = 0;
1711 u32 drawcalls = 0;
1712 for (;;)
1713 {
1714 if (tc[highest].drawn)
1715 {
1716 bool found = false;
1717 float hiscore = 0;
1718 for (u32 t = 0; t < tcount; t++)
1719 {
1720 if (!tc[t].drawn)
1721 {
1722 if (tc[t].score > hiscore)
1723 {
1724 highest = t;
1725 hiscore = tc[t].score;
1726 found = true;
1727 }
1728 }
1729 }
1730 if (!found)
1731 break;
1732 }
1733
1734 // Output the best triangle
1735 u16 newind = buf->Vertices.size();
1736
1737 snode *s = sind.find(v[tc[highest].ind[0]]);
1738
1739 if (!s)
1740 {
1741 buf->Vertices.push_back(v[tc[highest].ind[0]]);
1742 buf->Indices.push_back(newind);
1743 sind.insert(v[tc[highest].ind[0]], newind);
1744 newind++;
1745 }
1746 else
1747 {
1748 buf->Indices.push_back(s->getValue());
1749 }
1750
1751 s = sind.find(v[tc[highest].ind[1]]);
1752
1753 if (!s)
1754 {
1755 buf->Vertices.push_back(v[tc[highest].ind[1]]);
1756 buf->Indices.push_back(newind);
1757 sind.insert(v[tc[highest].ind[1]], newind);
1758 newind++;
1759 }
1760 else
1761 {
1762 buf->Indices.push_back(s->getValue());
1763 }
1764
1765 s = sind.find(v[tc[highest].ind[2]]);
1766
1767 if (!s)
1768 {
1769 buf->Vertices.push_back(v[tc[highest].ind[2]]);
1770 buf->Indices.push_back(newind);
1771 sind.insert(v[tc[highest].ind[2]], newind);
1772 }
1773 else
1774 {
1775 buf->Indices.push_back(s->getValue());
1776 }
1777
1778 vc[tc[highest].ind[0]].NumActiveTris--;
1779 vc[tc[highest].ind[1]].NumActiveTris--;
1780 vc[tc[highest].ind[2]].NumActiveTris--;
1781
1782 tc[highest].drawn = true;
1783
1784 for (u16 j = 0; j < 3; j++)
1785 {
1786 vcache *vert = &vc[tc[highest].ind[j]];
1787 for (u16 t = 0; t < vert->tris.size(); t++)
1788 {
1789 if (highest == vert->tris[t])
1790 {
1791 vert->tris.erase(t);
1792 break;
1793 }
1794 }
1795 }
1796
1797 lru.add(tc[highest].ind[0]);
1798 lru.add(tc[highest].ind[1]);
1799 highest = lru.add(tc[highest].ind[2]);
1800 drawcalls++;
1801 }
1802
1803 buf->setBoundingBox(mb->getBoundingBox());
1804 newmesh->addMeshBuffer(buf);
1805 buf->drop();
1806 }
1807 break;
1808 }
1809
1810 delete [] vc;
1811 delete [] tc;
1812
1813 } // for each meshbuffer
1814
1815 return newmesh;
1816}
1817
1818} // end namespace scene
1819} // end namespace irr
1820
generated by cgit v1.1 at 2024-06-27 09:34:38 +0000