3 Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as published by
7 the Free Software Foundation; either version 2.1 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public License along
16 with this program; if not, write to the Free Software Foundation, Inc.,
17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
25 #include <IAnimatedMesh.h>
26 #include <SAnimatedMesh.h>
28 // In Irrlicht 1.8 the signature of ITexture::lock was changed from
29 // (bool, u32) to (E_TEXTURE_LOCK_MODE, u32).
30 #if IRRLICHT_VERSION_MAJOR == 1 && IRRLICHT_VERSION_MINOR <= 7
31 #define MY_ETLM_READ_ONLY true
33 #define MY_ETLM_READ_ONLY video::ETLM_READ_ONLY
36 inline static void applyShadeFactor(video::SColor& color, float factor)
38 color.setRed(core::clamp(core::round32(color.getRed()*factor), 0, 255));
39 color.setGreen(core::clamp(core::round32(color.getGreen()*factor), 0, 255));
40 color.setBlue(core::clamp(core::round32(color.getBlue()*factor), 0, 255));
43 void applyFacesShading(video::SColor &color, const v3f &normal)
46 Some drawtypes have normals set to (0, 0, 0), this must result in
47 maximum brightness: shade factor 1.0.
48 Shade factors for aligned cube faces are:
51 +-X 0.670820 sqrt(0.45)
52 +-Z 0.836660 sqrt(0.7)
54 float x2 = normal.X * normal.X;
55 float y2 = normal.Y * normal.Y;
56 float z2 = normal.Z * normal.Z;
58 applyShadeFactor(color, 0.670820f * x2 + 0.447213f * y2 + 0.836660f * z2);
59 else if ((x2 > 1e-3) || (z2 > 1e-3))
60 applyShadeFactor(color, 0.670820f * x2 + 1.000000f * y2 + 0.836660f * z2);
63 scene::IAnimatedMesh* createCubeMesh(v3f scale)
65 video::SColor c(255,255,255,255);
66 video::S3DVertex vertices[24] =
69 video::S3DVertex(-0.5,+0.5,-0.5, 0,1,0, c, 0,1),
70 video::S3DVertex(-0.5,+0.5,+0.5, 0,1,0, c, 0,0),
71 video::S3DVertex(+0.5,+0.5,+0.5, 0,1,0, c, 1,0),
72 video::S3DVertex(+0.5,+0.5,-0.5, 0,1,0, c, 1,1),
74 video::S3DVertex(-0.5,-0.5,-0.5, 0,-1,0, c, 0,0),
75 video::S3DVertex(+0.5,-0.5,-0.5, 0,-1,0, c, 1,0),
76 video::S3DVertex(+0.5,-0.5,+0.5, 0,-1,0, c, 1,1),
77 video::S3DVertex(-0.5,-0.5,+0.5, 0,-1,0, c, 0,1),
79 video::S3DVertex(+0.5,-0.5,-0.5, 1,0,0, c, 0,1),
80 video::S3DVertex(+0.5,+0.5,-0.5, 1,0,0, c, 0,0),
81 video::S3DVertex(+0.5,+0.5,+0.5, 1,0,0, c, 1,0),
82 video::S3DVertex(+0.5,-0.5,+0.5, 1,0,0, c, 1,1),
84 video::S3DVertex(-0.5,-0.5,-0.5, -1,0,0, c, 1,1),
85 video::S3DVertex(-0.5,-0.5,+0.5, -1,0,0, c, 0,1),
86 video::S3DVertex(-0.5,+0.5,+0.5, -1,0,0, c, 0,0),
87 video::S3DVertex(-0.5,+0.5,-0.5, -1,0,0, c, 1,0),
89 video::S3DVertex(-0.5,-0.5,+0.5, 0,0,1, c, 1,1),
90 video::S3DVertex(+0.5,-0.5,+0.5, 0,0,1, c, 0,1),
91 video::S3DVertex(+0.5,+0.5,+0.5, 0,0,1, c, 0,0),
92 video::S3DVertex(-0.5,+0.5,+0.5, 0,0,1, c, 1,0),
94 video::S3DVertex(-0.5,-0.5,-0.5, 0,0,-1, c, 0,1),
95 video::S3DVertex(-0.5,+0.5,-0.5, 0,0,-1, c, 0,0),
96 video::S3DVertex(+0.5,+0.5,-0.5, 0,0,-1, c, 1,0),
97 video::S3DVertex(+0.5,-0.5,-0.5, 0,0,-1, c, 1,1),
100 u16 indices[6] = {0,1,2,2,3,0};
102 scene::SMesh *mesh = new scene::SMesh();
103 for (u32 i=0; i<6; ++i)
105 scene::IMeshBuffer *buf = new scene::SMeshBuffer();
106 buf->append(vertices + 4 * i, 4, indices, 6);
107 // Set default material
108 buf->getMaterial().setFlag(video::EMF_LIGHTING, false);
109 buf->getMaterial().setFlag(video::EMF_BILINEAR_FILTER, false);
110 buf->getMaterial().MaterialType = video::EMT_TRANSPARENT_ALPHA_CHANNEL_REF;
111 // Add mesh buffer to mesh
112 mesh->addMeshBuffer(buf);
116 scene::SAnimatedMesh *anim_mesh = new scene::SAnimatedMesh(mesh);
118 scaleMesh(anim_mesh, scale); // also recalculates bounding box
122 void scaleMesh(scene::IMesh *mesh, v3f scale)
130 u32 mc = mesh->getMeshBufferCount();
131 for (u32 j = 0; j < mc; j++) {
132 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
133 const u32 stride = getVertexPitchFromType(buf->getVertexType());
134 u32 vertex_count = buf->getVertexCount();
135 u8 *vertices = (u8 *)buf->getVertices();
136 for (u32 i = 0; i < vertex_count; i++)
137 ((video::S3DVertex *)(vertices + i * stride))->Pos *= scale;
139 buf->recalculateBoundingBox();
141 // calculate total bounding box
143 bbox = buf->getBoundingBox();
145 bbox.addInternalBox(buf->getBoundingBox());
147 mesh->setBoundingBox(bbox);
150 void translateMesh(scene::IMesh *mesh, v3f vec)
158 u32 mc = mesh->getMeshBufferCount();
159 for (u32 j = 0; j < mc; j++) {
160 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
161 const u32 stride = getVertexPitchFromType(buf->getVertexType());
162 u32 vertex_count = buf->getVertexCount();
163 u8 *vertices = (u8 *)buf->getVertices();
164 for (u32 i = 0; i < vertex_count; i++)
165 ((video::S3DVertex *)(vertices + i * stride))->Pos += vec;
167 buf->recalculateBoundingBox();
169 // calculate total bounding box
171 bbox = buf->getBoundingBox();
173 bbox.addInternalBox(buf->getBoundingBox());
175 mesh->setBoundingBox(bbox);
178 void setMeshBufferColor(scene::IMeshBuffer *buf, const video::SColor &color)
180 const u32 stride = getVertexPitchFromType(buf->getVertexType());
181 u32 vertex_count = buf->getVertexCount();
182 u8 *vertices = (u8 *) buf->getVertices();
183 for (u32 i = 0; i < vertex_count; i++)
184 ((video::S3DVertex *) (vertices + i * stride))->Color = color;
187 void setMeshColor(scene::IMesh *mesh, const video::SColor &color)
192 u32 mc = mesh->getMeshBufferCount();
193 for (u32 j = 0; j < mc; j++)
194 setMeshBufferColor(mesh->getMeshBuffer(j), color);
197 void colorizeMeshBuffer(scene::IMeshBuffer *buf, const video::SColor *buffercolor)
199 const u32 stride = getVertexPitchFromType(buf->getVertexType());
200 u32 vertex_count = buf->getVertexCount();
201 u8 *vertices = (u8 *) buf->getVertices();
202 for (u32 i = 0; i < vertex_count; i++) {
203 video::S3DVertex *vertex = (video::S3DVertex *) (vertices + i * stride);
204 video::SColor *vc = &(vertex->Color);
208 applyFacesShading(*vc, vertex->Normal);
212 void setMeshColorByNormalXYZ(scene::IMesh *mesh,
213 const video::SColor &colorX,
214 const video::SColor &colorY,
215 const video::SColor &colorZ)
220 u16 mc = mesh->getMeshBufferCount();
221 for (u16 j = 0; j < mc; j++) {
222 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
223 const u32 stride = getVertexPitchFromType(buf->getVertexType());
224 u32 vertex_count = buf->getVertexCount();
225 u8 *vertices = (u8 *)buf->getVertices();
226 for (u32 i = 0; i < vertex_count; i++) {
227 video::S3DVertex *vertex = (video::S3DVertex *)(vertices + i * stride);
228 f32 x = fabs(vertex->Normal.X);
229 f32 y = fabs(vertex->Normal.Y);
230 f32 z = fabs(vertex->Normal.Z);
231 if (x >= y && x >= z)
232 vertex->Color = colorX;
234 vertex->Color = colorY;
236 vertex->Color = colorZ;
241 void setMeshColorByNormal(scene::IMesh *mesh, const v3f &normal,
242 const video::SColor &color)
247 u16 mc = mesh->getMeshBufferCount();
248 for (u16 j = 0; j < mc; j++) {
249 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
250 const u32 stride = getVertexPitchFromType(buf->getVertexType());
251 u32 vertex_count = buf->getVertexCount();
252 u8 *vertices = (u8 *)buf->getVertices();
253 for (u32 i = 0; i < vertex_count; i++) {
254 video::S3DVertex *vertex = (video::S3DVertex *)(vertices + i * stride);
255 if (normal == vertex->Normal) {
256 vertex->Color = color;
262 void rotateMeshXYby(scene::IMesh *mesh, f64 degrees)
264 u16 mc = mesh->getMeshBufferCount();
265 for (u16 j = 0; j < mc; j++) {
266 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
267 const u32 stride = getVertexPitchFromType(buf->getVertexType());
268 u32 vertex_count = buf->getVertexCount();
269 u8 *vertices = (u8 *)buf->getVertices();
270 for (u32 i = 0; i < vertex_count; i++)
271 ((video::S3DVertex *)(vertices + i * stride))->Pos.rotateXYBy(degrees);
275 void rotateMeshXZby(scene::IMesh *mesh, f64 degrees)
277 u16 mc = mesh->getMeshBufferCount();
278 for (u16 j = 0; j < mc; j++) {
279 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
280 const u32 stride = getVertexPitchFromType(buf->getVertexType());
281 u32 vertex_count = buf->getVertexCount();
282 u8 *vertices = (u8 *)buf->getVertices();
283 for (u32 i = 0; i < vertex_count; i++)
284 ((video::S3DVertex *)(vertices + i * stride))->Pos.rotateXZBy(degrees);
288 void rotateMeshYZby(scene::IMesh *mesh, f64 degrees)
290 u16 mc = mesh->getMeshBufferCount();
291 for (u16 j = 0; j < mc; j++) {
292 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
293 const u32 stride = getVertexPitchFromType(buf->getVertexType());
294 u32 vertex_count = buf->getVertexCount();
295 u8 *vertices = (u8 *)buf->getVertices();
296 for (u32 i = 0; i < vertex_count; i++)
297 ((video::S3DVertex *)(vertices + i * stride))->Pos.rotateYZBy(degrees);
301 void rotateMeshBy6dFacedir(scene::IMesh *mesh, int facedir)
303 int axisdir = facedir >> 2;
306 u16 mc = mesh->getMeshBufferCount();
307 for (u16 j = 0; j < mc; j++) {
308 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
309 const u32 stride = getVertexPitchFromType(buf->getVertexType());
310 u32 vertex_count = buf->getVertexCount();
311 u8 *vertices = (u8 *)buf->getVertices();
312 for (u32 i = 0; i < vertex_count; i++) {
313 video::S3DVertex *vertex = (video::S3DVertex *)(vertices + i * stride);
317 vertex->Pos.rotateXZBy(-90);
318 else if (facedir == 2)
319 vertex->Pos.rotateXZBy(180);
320 else if (facedir == 3)
321 vertex->Pos.rotateXZBy(90);
324 vertex->Pos.rotateYZBy(90);
326 vertex->Pos.rotateXYBy(90);
327 else if (facedir == 2)
328 vertex->Pos.rotateXYBy(180);
329 else if (facedir == 3)
330 vertex->Pos.rotateXYBy(-90);
333 vertex->Pos.rotateYZBy(-90);
335 vertex->Pos.rotateXYBy(-90);
336 else if (facedir == 2)
337 vertex->Pos.rotateXYBy(180);
338 else if (facedir == 3)
339 vertex->Pos.rotateXYBy(90);
342 vertex->Pos.rotateXYBy(-90);
344 vertex->Pos.rotateYZBy(90);
345 else if (facedir == 2)
346 vertex->Pos.rotateYZBy(180);
347 else if (facedir == 3)
348 vertex->Pos.rotateYZBy(-90);
351 vertex->Pos.rotateXYBy(90);
353 vertex->Pos.rotateYZBy(-90);
354 else if (facedir == 2)
355 vertex->Pos.rotateYZBy(180);
356 else if (facedir == 3)
357 vertex->Pos.rotateYZBy(90);
360 vertex->Pos.rotateXYBy(-180);
362 vertex->Pos.rotateXZBy(90);
363 else if (facedir == 2)
364 vertex->Pos.rotateXZBy(180);
365 else if (facedir == 3)
366 vertex->Pos.rotateXZBy(-90);
375 void recalculateBoundingBox(scene::IMesh *src_mesh)
379 for (u16 j = 0; j < src_mesh->getMeshBufferCount(); j++) {
380 scene::IMeshBuffer *buf = src_mesh->getMeshBuffer(j);
381 buf->recalculateBoundingBox();
383 bbox = buf->getBoundingBox();
385 bbox.addInternalBox(buf->getBoundingBox());
387 src_mesh->setBoundingBox(bbox);
390 scene::IMeshBuffer* cloneMeshBuffer(scene::IMeshBuffer *mesh_buffer)
392 switch (mesh_buffer->getVertexType()) {
393 case video::EVT_STANDARD: {
394 video::S3DVertex *v = (video::S3DVertex *) mesh_buffer->getVertices();
395 u16 *indices = mesh_buffer->getIndices();
396 scene::SMeshBuffer *cloned_buffer = new scene::SMeshBuffer();
397 cloned_buffer->append(v, mesh_buffer->getVertexCount(), indices,
398 mesh_buffer->getIndexCount());
399 return cloned_buffer;
401 case video::EVT_2TCOORDS: {
402 video::S3DVertex2TCoords *v =
403 (video::S3DVertex2TCoords *) mesh_buffer->getVertices();
404 u16 *indices = mesh_buffer->getIndices();
405 scene::SMeshBufferTangents *cloned_buffer =
406 new scene::SMeshBufferTangents();
407 cloned_buffer->append(v, mesh_buffer->getVertexCount(), indices,
408 mesh_buffer->getIndexCount());
409 return cloned_buffer;
411 case video::EVT_TANGENTS: {
412 video::S3DVertexTangents *v =
413 (video::S3DVertexTangents *) mesh_buffer->getVertices();
414 u16 *indices = mesh_buffer->getIndices();
415 scene::SMeshBufferTangents *cloned_buffer =
416 new scene::SMeshBufferTangents();
417 cloned_buffer->append(v, mesh_buffer->getVertexCount(), indices,
418 mesh_buffer->getIndexCount());
419 return cloned_buffer;
422 // This should not happen.
427 scene::SMesh* cloneMesh(scene::IMesh *src_mesh)
429 scene::SMesh* dst_mesh = new scene::SMesh();
430 for (u16 j = 0; j < src_mesh->getMeshBufferCount(); j++) {
431 scene::IMeshBuffer *temp_buf = cloneMeshBuffer(
432 src_mesh->getMeshBuffer(j));
433 dst_mesh->addMeshBuffer(temp_buf);
440 scene::IMesh* convertNodeboxesToMesh(const std::vector<aabb3f> &boxes,
441 const f32 *uv_coords, float expand)
443 scene::SMesh* dst_mesh = new scene::SMesh();
445 for (u16 j = 0; j < 6; j++)
447 scene::IMeshBuffer *buf = new scene::SMeshBuffer();
448 buf->getMaterial().setFlag(video::EMF_LIGHTING, false);
449 buf->getMaterial().setFlag(video::EMF_BILINEAR_FILTER, false);
450 dst_mesh->addMeshBuffer(buf);
454 video::SColor c(255,255,255,255);
456 for (std::vector<aabb3f>::const_iterator
458 i != boxes.end(); ++i)
463 box.MinEdge.X -= expand;
464 box.MinEdge.Y -= expand;
465 box.MinEdge.Z -= expand;
466 box.MaxEdge.X += expand;
467 box.MaxEdge.Y += expand;
468 box.MaxEdge.Z += expand;
470 // Compute texture UV coords
471 f32 tx1 = (box.MinEdge.X / BS) + 0.5;
472 f32 ty1 = (box.MinEdge.Y / BS) + 0.5;
473 f32 tz1 = (box.MinEdge.Z / BS) + 0.5;
474 f32 tx2 = (box.MaxEdge.X / BS) + 0.5;
475 f32 ty2 = (box.MaxEdge.Y / BS) + 0.5;
476 f32 tz2 = (box.MaxEdge.Z / BS) + 0.5;
478 f32 txc_default[24] = {
480 tx1, 1 - tz2, tx2, 1 - tz1,
484 tz1, 1 - ty2, tz2, 1 - ty1,
486 1 - tz2, 1 - ty2, 1 - tz1, 1 - ty1,
488 1 - tx2, 1 - ty2, 1 - tx1, 1 - ty1,
490 tx1, 1 - ty2, tx2, 1 - ty1,
493 // use default texture UV mapping if not provided
494 const f32 *txc = uv_coords ? uv_coords : txc_default;
496 v3f min = box.MinEdge;
497 v3f max = box.MaxEdge;
499 video::S3DVertex vertices[24] =
502 video::S3DVertex(min.X,max.Y,max.Z, 0,1,0, c, txc[0],txc[1]),
503 video::S3DVertex(max.X,max.Y,max.Z, 0,1,0, c, txc[2],txc[1]),
504 video::S3DVertex(max.X,max.Y,min.Z, 0,1,0, c, txc[2],txc[3]),
505 video::S3DVertex(min.X,max.Y,min.Z, 0,1,0, c, txc[0],txc[3]),
507 video::S3DVertex(min.X,min.Y,min.Z, 0,-1,0, c, txc[4],txc[5]),
508 video::S3DVertex(max.X,min.Y,min.Z, 0,-1,0, c, txc[6],txc[5]),
509 video::S3DVertex(max.X,min.Y,max.Z, 0,-1,0, c, txc[6],txc[7]),
510 video::S3DVertex(min.X,min.Y,max.Z, 0,-1,0, c, txc[4],txc[7]),
512 video::S3DVertex(max.X,max.Y,min.Z, 1,0,0, c, txc[ 8],txc[9]),
513 video::S3DVertex(max.X,max.Y,max.Z, 1,0,0, c, txc[10],txc[9]),
514 video::S3DVertex(max.X,min.Y,max.Z, 1,0,0, c, txc[10],txc[11]),
515 video::S3DVertex(max.X,min.Y,min.Z, 1,0,0, c, txc[ 8],txc[11]),
517 video::S3DVertex(min.X,max.Y,max.Z, -1,0,0, c, txc[12],txc[13]),
518 video::S3DVertex(min.X,max.Y,min.Z, -1,0,0, c, txc[14],txc[13]),
519 video::S3DVertex(min.X,min.Y,min.Z, -1,0,0, c, txc[14],txc[15]),
520 video::S3DVertex(min.X,min.Y,max.Z, -1,0,0, c, txc[12],txc[15]),
522 video::S3DVertex(max.X,max.Y,max.Z, 0,0,1, c, txc[16],txc[17]),
523 video::S3DVertex(min.X,max.Y,max.Z, 0,0,1, c, txc[18],txc[17]),
524 video::S3DVertex(min.X,min.Y,max.Z, 0,0,1, c, txc[18],txc[19]),
525 video::S3DVertex(max.X,min.Y,max.Z, 0,0,1, c, txc[16],txc[19]),
527 video::S3DVertex(min.X,max.Y,min.Z, 0,0,-1, c, txc[20],txc[21]),
528 video::S3DVertex(max.X,max.Y,min.Z, 0,0,-1, c, txc[22],txc[21]),
529 video::S3DVertex(max.X,min.Y,min.Z, 0,0,-1, c, txc[22],txc[23]),
530 video::S3DVertex(min.X,min.Y,min.Z, 0,0,-1, c, txc[20],txc[23]),
533 u16 indices[] = {0,1,2,2,3,0};
535 for(u16 j = 0; j < 24; j += 4)
537 scene::IMeshBuffer *buf = dst_mesh->getMeshBuffer(j / 4);
538 buf->append(vertices + j, 4, indices, 6);
546 core::array<u32> tris;
559 const u16 cachesize = 32;
561 float FindVertexScore(vcache *v)
563 const float CacheDecayPower = 1.5f;
564 const float LastTriScore = 0.75f;
565 const float ValenceBoostScale = 2.0f;
566 const float ValenceBoostPower = 0.5f;
567 const float MaxSizeVertexCache = 32.0f;
569 if (v->NumActiveTris == 0)
571 // No tri needs this vertex!
576 int CachePosition = v->cachepos;
577 if (CachePosition < 0)
579 // Vertex is not in FIFO cache - no score.
583 if (CachePosition < 3)
585 // This vertex was used in the last triangle,
586 // so it has a fixed score.
587 Score = LastTriScore;
591 // Points for being high in the cache.
592 const float Scaler = 1.0f / (MaxSizeVertexCache - 3);
593 Score = 1.0f - (CachePosition - 3) * Scaler;
594 Score = powf(Score, CacheDecayPower);
598 // Bonus points for having a low number of tris still to
599 // use the vert, so we get rid of lone verts quickly.
600 float ValenceBoost = powf(v->NumActiveTris,
602 Score += ValenceBoostScale * ValenceBoost;
608 A specialized LRU cache for the Forsyth algorithm.
615 f_lru(vcache *v, tcache *t): vc(v), tc(t)
617 for (u16 i = 0; i < cachesize; i++)
623 // Adds this vertex index and returns the highest-scoring triangle index
624 u32 add(u16 vert, bool updatetris = false)
628 // Mark existing pos as empty
629 for (u16 i = 0; i < cachesize; i++)
631 if (cache[i] == vert)
633 // Move everything down
634 for (u16 j = i; j; j--)
636 cache[j] = cache[j - 1];
646 if (cache[cachesize-1] != -1)
647 vc[cache[cachesize-1]].cachepos = -1;
649 // Move everything down
650 for (u16 i = cachesize - 1; i; i--)
652 cache[i] = cache[i - 1];
663 // Update cache positions
664 for (u16 i = 0; i < cachesize; i++)
669 vc[cache[i]].cachepos = i;
670 vc[cache[i]].score = FindVertexScore(&vc[cache[i]]);
673 // Update triangle scores
674 for (u16 i = 0; i < cachesize; i++)
679 const u16 trisize = vc[cache[i]].tris.size();
680 for (u16 t = 0; t < trisize; t++)
682 tcache *tri = &tc[vc[cache[i]].tris[t]];
685 vc[tri->ind[0]].score +
686 vc[tri->ind[1]].score +
687 vc[tri->ind[2]].score;
689 if (tri->score > hiscore)
691 hiscore = tri->score;
692 highest = vc[cache[i]].tris[t];
702 s32 cache[cachesize];
708 Vertex cache optimization according to the Forsyth paper:
709 http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html
711 The function is thread-safe (read: you can optimize several meshes in different threads)
713 \param mesh Source mesh for the operation. */
714 scene::IMesh* createForsythOptimizedMesh(const scene::IMesh *mesh)
719 scene::SMesh *newmesh = new scene::SMesh();
720 newmesh->BoundingBox = mesh->getBoundingBox();
722 const u32 mbcount = mesh->getMeshBufferCount();
724 for (u32 b = 0; b < mbcount; ++b)
726 const scene::IMeshBuffer *mb = mesh->getMeshBuffer(b);
728 if (mb->getIndexType() != video::EIT_16BIT)
730 //os::Printer::log("Cannot optimize a mesh with 32bit indices", ELL_ERROR);
735 const u32 icount = mb->getIndexCount();
736 const u32 tcount = icount / 3;
737 const u32 vcount = mb->getVertexCount();
738 const u16 *ind = mb->getIndices();
740 vcache *vc = new vcache[vcount];
741 tcache *tc = new tcache[tcount];
746 for (u16 i = 0; i < vcount; i++)
750 vc[i].NumActiveTris = 0;
753 // First pass: count how many times a vert is used
754 for (u32 i = 0; i < icount; i += 3)
756 vc[ind[i]].NumActiveTris++;
757 vc[ind[i + 1]].NumActiveTris++;
758 vc[ind[i + 2]].NumActiveTris++;
760 const u32 tri_ind = i/3;
761 tc[tri_ind].ind[0] = ind[i];
762 tc[tri_ind].ind[1] = ind[i + 1];
763 tc[tri_ind].ind[2] = ind[i + 2];
766 // Second pass: list of each triangle
767 for (u32 i = 0; i < tcount; i++)
769 vc[tc[i].ind[0]].tris.push_back(i);
770 vc[tc[i].ind[1]].tris.push_back(i);
771 vc[tc[i].ind[2]].tris.push_back(i);
776 // Give initial scores
777 for (u16 i = 0; i < vcount; i++)
779 vc[i].score = FindVertexScore(&vc[i]);
781 for (u32 i = 0; i < tcount; i++)
784 vc[tc[i].ind[0]].score +
785 vc[tc[i].ind[1]].score +
786 vc[tc[i].ind[2]].score;
789 switch(mb->getVertexType())
791 case video::EVT_STANDARD:
793 video::S3DVertex *v = (video::S3DVertex *) mb->getVertices();
795 scene::SMeshBuffer *buf = new scene::SMeshBuffer();
796 buf->Material = mb->getMaterial();
798 buf->Vertices.reallocate(vcount);
799 buf->Indices.reallocate(icount);
801 core::map<const video::S3DVertex, const u16> sind; // search index for fast operation
802 typedef core::map<const video::S3DVertex, const u16>::Node snode;
809 if (tc[highest].drawn)
813 for (u32 t = 0; t < tcount; t++)
817 if (tc[t].score > hiscore)
820 hiscore = tc[t].score;
829 // Output the best triangle
830 u16 newind = buf->Vertices.size();
832 snode *s = sind.find(v[tc[highest].ind[0]]);
836 buf->Vertices.push_back(v[tc[highest].ind[0]]);
837 buf->Indices.push_back(newind);
838 sind.insert(v[tc[highest].ind[0]], newind);
843 buf->Indices.push_back(s->getValue());
846 s = sind.find(v[tc[highest].ind[1]]);
850 buf->Vertices.push_back(v[tc[highest].ind[1]]);
851 buf->Indices.push_back(newind);
852 sind.insert(v[tc[highest].ind[1]], newind);
857 buf->Indices.push_back(s->getValue());
860 s = sind.find(v[tc[highest].ind[2]]);
864 buf->Vertices.push_back(v[tc[highest].ind[2]]);
865 buf->Indices.push_back(newind);
866 sind.insert(v[tc[highest].ind[2]], newind);
870 buf->Indices.push_back(s->getValue());
873 vc[tc[highest].ind[0]].NumActiveTris--;
874 vc[tc[highest].ind[1]].NumActiveTris--;
875 vc[tc[highest].ind[2]].NumActiveTris--;
877 tc[highest].drawn = true;
879 for (u16 j = 0; j < 3; j++)
881 vcache *vert = &vc[tc[highest].ind[j]];
882 for (u16 t = 0; t < vert->tris.size(); t++)
884 if (highest == vert->tris[t])
892 lru.add(tc[highest].ind[0]);
893 lru.add(tc[highest].ind[1]);
894 highest = lru.add(tc[highest].ind[2], true);
898 buf->setBoundingBox(mb->getBoundingBox());
899 newmesh->addMeshBuffer(buf);
903 case video::EVT_2TCOORDS:
905 video::S3DVertex2TCoords *v = (video::S3DVertex2TCoords *) mb->getVertices();
907 scene::SMeshBufferLightMap *buf = new scene::SMeshBufferLightMap();
908 buf->Material = mb->getMaterial();
910 buf->Vertices.reallocate(vcount);
911 buf->Indices.reallocate(icount);
913 core::map<const video::S3DVertex2TCoords, const u16> sind; // search index for fast operation
914 typedef core::map<const video::S3DVertex2TCoords, const u16>::Node snode;
921 if (tc[highest].drawn)
925 for (u32 t = 0; t < tcount; t++)
929 if (tc[t].score > hiscore)
932 hiscore = tc[t].score;
941 // Output the best triangle
942 u16 newind = buf->Vertices.size();
944 snode *s = sind.find(v[tc[highest].ind[0]]);
948 buf->Vertices.push_back(v[tc[highest].ind[0]]);
949 buf->Indices.push_back(newind);
950 sind.insert(v[tc[highest].ind[0]], newind);
955 buf->Indices.push_back(s->getValue());
958 s = sind.find(v[tc[highest].ind[1]]);
962 buf->Vertices.push_back(v[tc[highest].ind[1]]);
963 buf->Indices.push_back(newind);
964 sind.insert(v[tc[highest].ind[1]], newind);
969 buf->Indices.push_back(s->getValue());
972 s = sind.find(v[tc[highest].ind[2]]);
976 buf->Vertices.push_back(v[tc[highest].ind[2]]);
977 buf->Indices.push_back(newind);
978 sind.insert(v[tc[highest].ind[2]], newind);
982 buf->Indices.push_back(s->getValue());
985 vc[tc[highest].ind[0]].NumActiveTris--;
986 vc[tc[highest].ind[1]].NumActiveTris--;
987 vc[tc[highest].ind[2]].NumActiveTris--;
989 tc[highest].drawn = true;
991 for (u16 j = 0; j < 3; j++)
993 vcache *vert = &vc[tc[highest].ind[j]];
994 for (u16 t = 0; t < vert->tris.size(); t++)
996 if (highest == vert->tris[t])
1004 lru.add(tc[highest].ind[0]);
1005 lru.add(tc[highest].ind[1]);
1006 highest = lru.add(tc[highest].ind[2]);
1010 buf->setBoundingBox(mb->getBoundingBox());
1011 newmesh->addMeshBuffer(buf);
1016 case video::EVT_TANGENTS:
1018 video::S3DVertexTangents *v = (video::S3DVertexTangents *) mb->getVertices();
1020 scene::SMeshBufferTangents *buf = new scene::SMeshBufferTangents();
1021 buf->Material = mb->getMaterial();
1023 buf->Vertices.reallocate(vcount);
1024 buf->Indices.reallocate(icount);
1026 core::map<const video::S3DVertexTangents, const u16> sind; // search index for fast operation
1027 typedef core::map<const video::S3DVertexTangents, const u16>::Node snode;
1034 if (tc[highest].drawn)
1038 for (u32 t = 0; t < tcount; t++)
1042 if (tc[t].score > hiscore)
1045 hiscore = tc[t].score;
1054 // Output the best triangle
1055 u16 newind = buf->Vertices.size();
1057 snode *s = sind.find(v[tc[highest].ind[0]]);
1061 buf->Vertices.push_back(v[tc[highest].ind[0]]);
1062 buf->Indices.push_back(newind);
1063 sind.insert(v[tc[highest].ind[0]], newind);
1068 buf->Indices.push_back(s->getValue());
1071 s = sind.find(v[tc[highest].ind[1]]);
1075 buf->Vertices.push_back(v[tc[highest].ind[1]]);
1076 buf->Indices.push_back(newind);
1077 sind.insert(v[tc[highest].ind[1]], newind);
1082 buf->Indices.push_back(s->getValue());
1085 s = sind.find(v[tc[highest].ind[2]]);
1089 buf->Vertices.push_back(v[tc[highest].ind[2]]);
1090 buf->Indices.push_back(newind);
1091 sind.insert(v[tc[highest].ind[2]], newind);
1095 buf->Indices.push_back(s->getValue());
1098 vc[tc[highest].ind[0]].NumActiveTris--;
1099 vc[tc[highest].ind[1]].NumActiveTris--;
1100 vc[tc[highest].ind[2]].NumActiveTris--;
1102 tc[highest].drawn = true;
1104 for (u16 j = 0; j < 3; j++)
1106 vcache *vert = &vc[tc[highest].ind[j]];
1107 for (u16 t = 0; t < vert->tris.size(); t++)
1109 if (highest == vert->tris[t])
1111 vert->tris.erase(t);
1117 lru.add(tc[highest].ind[0]);
1118 lru.add(tc[highest].ind[1]);
1119 highest = lru.add(tc[highest].ind[2]);
1123 buf->setBoundingBox(mb->getBoundingBox());
1124 newmesh->addMeshBuffer(buf);
1133 } // for each meshbuffer