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)
45 // Many special drawtypes have normals set to 0,0,0 and this
46 // must result in maximum brightness (no face shadng).
48 applyShadeFactor (color, 0.447213f);
49 else if (normal.X > 0.5f || normal.X < -0.5f)
50 applyShadeFactor (color, 0.670820f);
51 else if (normal.Z > 0.5f || normal.Z < -0.5f)
52 applyShadeFactor (color, 0.836660f);
55 scene::IAnimatedMesh* createCubeMesh(v3f scale)
57 video::SColor c(255,255,255,255);
58 video::S3DVertex vertices[24] =
61 video::S3DVertex(-0.5,+0.5,-0.5, 0,1,0, c, 0,1),
62 video::S3DVertex(-0.5,+0.5,+0.5, 0,1,0, c, 0,0),
63 video::S3DVertex(+0.5,+0.5,+0.5, 0,1,0, c, 1,0),
64 video::S3DVertex(+0.5,+0.5,-0.5, 0,1,0, c, 1,1),
66 video::S3DVertex(-0.5,-0.5,-0.5, 0,-1,0, c, 0,0),
67 video::S3DVertex(+0.5,-0.5,-0.5, 0,-1,0, c, 1,0),
68 video::S3DVertex(+0.5,-0.5,+0.5, 0,-1,0, c, 1,1),
69 video::S3DVertex(-0.5,-0.5,+0.5, 0,-1,0, c, 0,1),
71 video::S3DVertex(+0.5,-0.5,-0.5, 1,0,0, c, 0,1),
72 video::S3DVertex(+0.5,+0.5,-0.5, 1,0,0, c, 0,0),
73 video::S3DVertex(+0.5,+0.5,+0.5, 1,0,0, c, 1,0),
74 video::S3DVertex(+0.5,-0.5,+0.5, 1,0,0, c, 1,1),
76 video::S3DVertex(-0.5,-0.5,-0.5, -1,0,0, c, 1,1),
77 video::S3DVertex(-0.5,-0.5,+0.5, -1,0,0, c, 0,1),
78 video::S3DVertex(-0.5,+0.5,+0.5, -1,0,0, c, 0,0),
79 video::S3DVertex(-0.5,+0.5,-0.5, -1,0,0, c, 1,0),
81 video::S3DVertex(-0.5,-0.5,+0.5, 0,0,1, c, 1,1),
82 video::S3DVertex(+0.5,-0.5,+0.5, 0,0,1, c, 0,1),
83 video::S3DVertex(+0.5,+0.5,+0.5, 0,0,1, c, 0,0),
84 video::S3DVertex(-0.5,+0.5,+0.5, 0,0,1, c, 1,0),
86 video::S3DVertex(-0.5,-0.5,-0.5, 0,0,-1, c, 0,1),
87 video::S3DVertex(-0.5,+0.5,-0.5, 0,0,-1, c, 0,0),
88 video::S3DVertex(+0.5,+0.5,-0.5, 0,0,-1, c, 1,0),
89 video::S3DVertex(+0.5,-0.5,-0.5, 0,0,-1, c, 1,1),
92 u16 indices[6] = {0,1,2,2,3,0};
94 scene::SMesh *mesh = new scene::SMesh();
95 for (u32 i=0; i<6; ++i)
97 scene::IMeshBuffer *buf = new scene::SMeshBuffer();
98 buf->append(vertices + 4 * i, 4, indices, 6);
99 // Set default material
100 buf->getMaterial().setFlag(video::EMF_LIGHTING, false);
101 buf->getMaterial().setFlag(video::EMF_BILINEAR_FILTER, false);
102 buf->getMaterial().MaterialType = video::EMT_TRANSPARENT_ALPHA_CHANNEL_REF;
103 // Add mesh buffer to mesh
104 mesh->addMeshBuffer(buf);
108 scene::SAnimatedMesh *anim_mesh = new scene::SAnimatedMesh(mesh);
110 scaleMesh(anim_mesh, scale); // also recalculates bounding box
114 void scaleMesh(scene::IMesh *mesh, v3f scale)
122 u32 mc = mesh->getMeshBufferCount();
123 for (u32 j = 0; j < mc; j++) {
124 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
125 const u32 stride = getVertexPitchFromType(buf->getVertexType());
126 u32 vertex_count = buf->getVertexCount();
127 u8 *vertices = (u8 *)buf->getVertices();
128 for (u32 i = 0; i < vertex_count; i++)
129 ((video::S3DVertex *)(vertices + i * stride))->Pos *= scale;
131 buf->recalculateBoundingBox();
133 // calculate total bounding box
135 bbox = buf->getBoundingBox();
137 bbox.addInternalBox(buf->getBoundingBox());
139 mesh->setBoundingBox(bbox);
142 void translateMesh(scene::IMesh *mesh, v3f vec)
150 u32 mc = mesh->getMeshBufferCount();
151 for (u32 j = 0; j < mc; j++) {
152 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
153 const u32 stride = getVertexPitchFromType(buf->getVertexType());
154 u32 vertex_count = buf->getVertexCount();
155 u8 *vertices = (u8 *)buf->getVertices();
156 for (u32 i = 0; i < vertex_count; i++)
157 ((video::S3DVertex *)(vertices + i * stride))->Pos += vec;
159 buf->recalculateBoundingBox();
161 // calculate total bounding box
163 bbox = buf->getBoundingBox();
165 bbox.addInternalBox(buf->getBoundingBox());
167 mesh->setBoundingBox(bbox);
171 void setMeshColor(scene::IMesh *mesh, const video::SColor &color)
176 u32 mc = mesh->getMeshBufferCount();
177 for (u32 j = 0; j < mc; j++) {
178 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
179 const u32 stride = getVertexPitchFromType(buf->getVertexType());
180 u32 vertex_count = buf->getVertexCount();
181 u8 *vertices = (u8 *)buf->getVertices();
182 for (u32 i = 0; i < vertex_count; i++)
183 ((video::S3DVertex *)(vertices + i * stride))->Color = color;
187 void colorizeMeshBuffer(scene::IMeshBuffer *buf, const video::SColor *buffercolor)
189 const u32 stride = getVertexPitchFromType(buf->getVertexType());
190 u32 vertex_count = buf->getVertexCount();
191 u8 *vertices = (u8 *) buf->getVertices();
192 for (u32 i = 0; i < vertex_count; i++) {
193 video::S3DVertex *vertex = (video::S3DVertex *) (vertices + i * stride);
194 video::SColor *vc = &(vertex->Color);
198 applyFacesShading(*vc, vertex->Normal);
202 void setMeshColorByNormalXYZ(scene::IMesh *mesh,
203 const video::SColor &colorX,
204 const video::SColor &colorY,
205 const video::SColor &colorZ)
210 u16 mc = mesh->getMeshBufferCount();
211 for (u16 j = 0; j < mc; j++) {
212 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
213 const u32 stride = getVertexPitchFromType(buf->getVertexType());
214 u32 vertex_count = buf->getVertexCount();
215 u8 *vertices = (u8 *)buf->getVertices();
216 for (u32 i = 0; i < vertex_count; i++) {
217 video::S3DVertex *vertex = (video::S3DVertex *)(vertices + i * stride);
218 f32 x = fabs(vertex->Normal.X);
219 f32 y = fabs(vertex->Normal.Y);
220 f32 z = fabs(vertex->Normal.Z);
221 if (x >= y && x >= z)
222 vertex->Color = colorX;
224 vertex->Color = colorY;
226 vertex->Color = colorZ;
231 void setMeshColorByNormal(scene::IMesh *mesh, const v3f &normal,
232 const video::SColor &color)
237 u16 mc = mesh->getMeshBufferCount();
238 for (u16 j = 0; j < mc; j++) {
239 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
240 const u32 stride = getVertexPitchFromType(buf->getVertexType());
241 u32 vertex_count = buf->getVertexCount();
242 u8 *vertices = (u8 *)buf->getVertices();
243 for (u32 i = 0; i < vertex_count; i++) {
244 video::S3DVertex *vertex = (video::S3DVertex *)(vertices + i * stride);
245 if (normal == vertex->Normal) {
246 vertex->Color = color;
252 void rotateMeshXYby(scene::IMesh *mesh, f64 degrees)
254 u16 mc = mesh->getMeshBufferCount();
255 for (u16 j = 0; j < mc; j++) {
256 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
257 const u32 stride = getVertexPitchFromType(buf->getVertexType());
258 u32 vertex_count = buf->getVertexCount();
259 u8 *vertices = (u8 *)buf->getVertices();
260 for (u32 i = 0; i < vertex_count; i++)
261 ((video::S3DVertex *)(vertices + i * stride))->Pos.rotateXYBy(degrees);
265 void rotateMeshXZby(scene::IMesh *mesh, f64 degrees)
267 u16 mc = mesh->getMeshBufferCount();
268 for (u16 j = 0; j < mc; j++) {
269 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
270 const u32 stride = getVertexPitchFromType(buf->getVertexType());
271 u32 vertex_count = buf->getVertexCount();
272 u8 *vertices = (u8 *)buf->getVertices();
273 for (u32 i = 0; i < vertex_count; i++)
274 ((video::S3DVertex *)(vertices + i * stride))->Pos.rotateXZBy(degrees);
278 void rotateMeshYZby(scene::IMesh *mesh, f64 degrees)
280 u16 mc = mesh->getMeshBufferCount();
281 for (u16 j = 0; j < mc; j++) {
282 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
283 const u32 stride = getVertexPitchFromType(buf->getVertexType());
284 u32 vertex_count = buf->getVertexCount();
285 u8 *vertices = (u8 *)buf->getVertices();
286 for (u32 i = 0; i < vertex_count; i++)
287 ((video::S3DVertex *)(vertices + i * stride))->Pos.rotateYZBy(degrees);
291 void rotateMeshBy6dFacedir(scene::IMesh *mesh, int facedir)
293 int axisdir = facedir >> 2;
296 u16 mc = mesh->getMeshBufferCount();
297 for (u16 j = 0; j < mc; j++) {
298 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
299 const u32 stride = getVertexPitchFromType(buf->getVertexType());
300 u32 vertex_count = buf->getVertexCount();
301 u8 *vertices = (u8 *)buf->getVertices();
302 for (u32 i = 0; i < vertex_count; i++) {
303 video::S3DVertex *vertex = (video::S3DVertex *)(vertices + i * stride);
307 vertex->Pos.rotateXZBy(-90);
308 else if (facedir == 2)
309 vertex->Pos.rotateXZBy(180);
310 else if (facedir == 3)
311 vertex->Pos.rotateXZBy(90);
314 vertex->Pos.rotateYZBy(90);
316 vertex->Pos.rotateXYBy(90);
317 else if (facedir == 2)
318 vertex->Pos.rotateXYBy(180);
319 else if (facedir == 3)
320 vertex->Pos.rotateXYBy(-90);
323 vertex->Pos.rotateYZBy(-90);
325 vertex->Pos.rotateXYBy(-90);
326 else if (facedir == 2)
327 vertex->Pos.rotateXYBy(180);
328 else if (facedir == 3)
329 vertex->Pos.rotateXYBy(90);
332 vertex->Pos.rotateXYBy(-90);
334 vertex->Pos.rotateYZBy(90);
335 else if (facedir == 2)
336 vertex->Pos.rotateYZBy(180);
337 else if (facedir == 3)
338 vertex->Pos.rotateYZBy(-90);
341 vertex->Pos.rotateXYBy(90);
343 vertex->Pos.rotateYZBy(-90);
344 else if (facedir == 2)
345 vertex->Pos.rotateYZBy(180);
346 else if (facedir == 3)
347 vertex->Pos.rotateYZBy(90);
350 vertex->Pos.rotateXYBy(-180);
352 vertex->Pos.rotateXZBy(90);
353 else if (facedir == 2)
354 vertex->Pos.rotateXZBy(180);
355 else if (facedir == 3)
356 vertex->Pos.rotateXZBy(-90);
365 void recalculateBoundingBox(scene::IMesh *src_mesh)
369 for (u16 j = 0; j < src_mesh->getMeshBufferCount(); j++) {
370 scene::IMeshBuffer *buf = src_mesh->getMeshBuffer(j);
371 buf->recalculateBoundingBox();
373 bbox = buf->getBoundingBox();
375 bbox.addInternalBox(buf->getBoundingBox());
377 src_mesh->setBoundingBox(bbox);
380 scene::IMesh* cloneMesh(scene::IMesh *src_mesh)
382 scene::SMesh* dst_mesh = new scene::SMesh();
383 for (u16 j = 0; j < src_mesh->getMeshBufferCount(); j++) {
384 scene::IMeshBuffer *buf = src_mesh->getMeshBuffer(j);
385 switch (buf->getVertexType()) {
386 case video::EVT_STANDARD: {
387 video::S3DVertex *v =
388 (video::S3DVertex *) buf->getVertices();
389 u16 *indices = (u16*)buf->getIndices();
390 scene::SMeshBuffer *temp_buf = new scene::SMeshBuffer();
391 temp_buf->append(v, buf->getVertexCount(),
392 indices, buf->getIndexCount());
393 dst_mesh->addMeshBuffer(temp_buf);
397 case video::EVT_2TCOORDS: {
398 video::S3DVertex2TCoords *v =
399 (video::S3DVertex2TCoords *) buf->getVertices();
400 u16 *indices = (u16*)buf->getIndices();
401 scene::SMeshBufferTangents *temp_buf =
402 new scene::SMeshBufferTangents();
403 temp_buf->append(v, buf->getVertexCount(),
404 indices, buf->getIndexCount());
405 dst_mesh->addMeshBuffer(temp_buf);
409 case video::EVT_TANGENTS: {
410 video::S3DVertexTangents *v =
411 (video::S3DVertexTangents *) buf->getVertices();
412 u16 *indices = (u16*)buf->getIndices();
413 scene::SMeshBufferTangents *temp_buf =
414 new scene::SMeshBufferTangents();
415 temp_buf->append(v, buf->getVertexCount(),
416 indices, buf->getIndexCount());
417 dst_mesh->addMeshBuffer(temp_buf);
426 scene::IMesh* convertNodeboxesToMesh(const std::vector<aabb3f> &boxes,
427 const f32 *uv_coords, float expand)
429 scene::SMesh* dst_mesh = new scene::SMesh();
431 for (u16 j = 0; j < 6; j++)
433 scene::IMeshBuffer *buf = new scene::SMeshBuffer();
434 buf->getMaterial().setFlag(video::EMF_LIGHTING, false);
435 buf->getMaterial().setFlag(video::EMF_BILINEAR_FILTER, false);
436 dst_mesh->addMeshBuffer(buf);
440 video::SColor c(255,255,255,255);
442 for (std::vector<aabb3f>::const_iterator
444 i != boxes.end(); ++i)
449 box.MinEdge.X -= expand;
450 box.MinEdge.Y -= expand;
451 box.MinEdge.Z -= expand;
452 box.MaxEdge.X += expand;
453 box.MaxEdge.Y += expand;
454 box.MaxEdge.Z += expand;
456 // Compute texture UV coords
457 f32 tx1 = (box.MinEdge.X / BS) + 0.5;
458 f32 ty1 = (box.MinEdge.Y / BS) + 0.5;
459 f32 tz1 = (box.MinEdge.Z / BS) + 0.5;
460 f32 tx2 = (box.MaxEdge.X / BS) + 0.5;
461 f32 ty2 = (box.MaxEdge.Y / BS) + 0.5;
462 f32 tz2 = (box.MaxEdge.Z / BS) + 0.5;
464 f32 txc_default[24] = {
466 tx1, 1 - tz2, tx2, 1 - tz1,
470 tz1, 1 - ty2, tz2, 1 - ty1,
472 1 - tz2, 1 - ty2, 1 - tz1, 1 - ty1,
474 1 - tx2, 1 - ty2, 1 - tx1, 1 - ty1,
476 tx1, 1 - ty2, tx2, 1 - ty1,
479 // use default texture UV mapping if not provided
480 const f32 *txc = uv_coords ? uv_coords : txc_default;
482 v3f min = box.MinEdge;
483 v3f max = box.MaxEdge;
485 video::S3DVertex vertices[24] =
488 video::S3DVertex(min.X,max.Y,max.Z, 0,1,0, c, txc[0],txc[1]),
489 video::S3DVertex(max.X,max.Y,max.Z, 0,1,0, c, txc[2],txc[1]),
490 video::S3DVertex(max.X,max.Y,min.Z, 0,1,0, c, txc[2],txc[3]),
491 video::S3DVertex(min.X,max.Y,min.Z, 0,1,0, c, txc[0],txc[3]),
493 video::S3DVertex(min.X,min.Y,min.Z, 0,-1,0, c, txc[4],txc[5]),
494 video::S3DVertex(max.X,min.Y,min.Z, 0,-1,0, c, txc[6],txc[5]),
495 video::S3DVertex(max.X,min.Y,max.Z, 0,-1,0, c, txc[6],txc[7]),
496 video::S3DVertex(min.X,min.Y,max.Z, 0,-1,0, c, txc[4],txc[7]),
498 video::S3DVertex(max.X,max.Y,min.Z, 1,0,0, c, txc[ 8],txc[9]),
499 video::S3DVertex(max.X,max.Y,max.Z, 1,0,0, c, txc[10],txc[9]),
500 video::S3DVertex(max.X,min.Y,max.Z, 1,0,0, c, txc[10],txc[11]),
501 video::S3DVertex(max.X,min.Y,min.Z, 1,0,0, c, txc[ 8],txc[11]),
503 video::S3DVertex(min.X,max.Y,max.Z, -1,0,0, c, txc[12],txc[13]),
504 video::S3DVertex(min.X,max.Y,min.Z, -1,0,0, c, txc[14],txc[13]),
505 video::S3DVertex(min.X,min.Y,min.Z, -1,0,0, c, txc[14],txc[15]),
506 video::S3DVertex(min.X,min.Y,max.Z, -1,0,0, c, txc[12],txc[15]),
508 video::S3DVertex(max.X,max.Y,max.Z, 0,0,1, c, txc[16],txc[17]),
509 video::S3DVertex(min.X,max.Y,max.Z, 0,0,1, c, txc[18],txc[17]),
510 video::S3DVertex(min.X,min.Y,max.Z, 0,0,1, c, txc[18],txc[19]),
511 video::S3DVertex(max.X,min.Y,max.Z, 0,0,1, c, txc[16],txc[19]),
513 video::S3DVertex(min.X,max.Y,min.Z, 0,0,-1, c, txc[20],txc[21]),
514 video::S3DVertex(max.X,max.Y,min.Z, 0,0,-1, c, txc[22],txc[21]),
515 video::S3DVertex(max.X,min.Y,min.Z, 0,0,-1, c, txc[22],txc[23]),
516 video::S3DVertex(min.X,min.Y,min.Z, 0,0,-1, c, txc[20],txc[23]),
519 u16 indices[] = {0,1,2,2,3,0};
521 for(u16 j = 0; j < 24; j += 4)
523 scene::IMeshBuffer *buf = dst_mesh->getMeshBuffer(j / 4);
524 buf->append(vertices + j, 4, indices, 6);
532 core::array<u32> tris;
545 const u16 cachesize = 32;
547 float FindVertexScore(vcache *v)
549 const float CacheDecayPower = 1.5f;
550 const float LastTriScore = 0.75f;
551 const float ValenceBoostScale = 2.0f;
552 const float ValenceBoostPower = 0.5f;
553 const float MaxSizeVertexCache = 32.0f;
555 if (v->NumActiveTris == 0)
557 // No tri needs this vertex!
562 int CachePosition = v->cachepos;
563 if (CachePosition < 0)
565 // Vertex is not in FIFO cache - no score.
569 if (CachePosition < 3)
571 // This vertex was used in the last triangle,
572 // so it has a fixed score.
573 Score = LastTriScore;
577 // Points for being high in the cache.
578 const float Scaler = 1.0f / (MaxSizeVertexCache - 3);
579 Score = 1.0f - (CachePosition - 3) * Scaler;
580 Score = powf(Score, CacheDecayPower);
584 // Bonus points for having a low number of tris still to
585 // use the vert, so we get rid of lone verts quickly.
586 float ValenceBoost = powf(v->NumActiveTris,
588 Score += ValenceBoostScale * ValenceBoost;
594 A specialized LRU cache for the Forsyth algorithm.
601 f_lru(vcache *v, tcache *t): vc(v), tc(t)
603 for (u16 i = 0; i < cachesize; i++)
609 // Adds this vertex index and returns the highest-scoring triangle index
610 u32 add(u16 vert, bool updatetris = false)
614 // Mark existing pos as empty
615 for (u16 i = 0; i < cachesize; i++)
617 if (cache[i] == vert)
619 // Move everything down
620 for (u16 j = i; j; j--)
622 cache[j] = cache[j - 1];
632 if (cache[cachesize-1] != -1)
633 vc[cache[cachesize-1]].cachepos = -1;
635 // Move everything down
636 for (u16 i = cachesize - 1; i; i--)
638 cache[i] = cache[i - 1];
649 // Update cache positions
650 for (u16 i = 0; i < cachesize; i++)
655 vc[cache[i]].cachepos = i;
656 vc[cache[i]].score = FindVertexScore(&vc[cache[i]]);
659 // Update triangle scores
660 for (u16 i = 0; i < cachesize; i++)
665 const u16 trisize = vc[cache[i]].tris.size();
666 for (u16 t = 0; t < trisize; t++)
668 tcache *tri = &tc[vc[cache[i]].tris[t]];
671 vc[tri->ind[0]].score +
672 vc[tri->ind[1]].score +
673 vc[tri->ind[2]].score;
675 if (tri->score > hiscore)
677 hiscore = tri->score;
678 highest = vc[cache[i]].tris[t];
688 s32 cache[cachesize];
694 Vertex cache optimization according to the Forsyth paper:
695 http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html
697 The function is thread-safe (read: you can optimize several meshes in different threads)
699 \param mesh Source mesh for the operation. */
700 scene::IMesh* createForsythOptimizedMesh(const scene::IMesh *mesh)
705 scene::SMesh *newmesh = new scene::SMesh();
706 newmesh->BoundingBox = mesh->getBoundingBox();
708 const u32 mbcount = mesh->getMeshBufferCount();
710 for (u32 b = 0; b < mbcount; ++b)
712 const scene::IMeshBuffer *mb = mesh->getMeshBuffer(b);
714 if (mb->getIndexType() != video::EIT_16BIT)
716 //os::Printer::log("Cannot optimize a mesh with 32bit indices", ELL_ERROR);
721 const u32 icount = mb->getIndexCount();
722 const u32 tcount = icount / 3;
723 const u32 vcount = mb->getVertexCount();
724 const u16 *ind = mb->getIndices();
726 vcache *vc = new vcache[vcount];
727 tcache *tc = new tcache[tcount];
732 for (u16 i = 0; i < vcount; i++)
736 vc[i].NumActiveTris = 0;
739 // First pass: count how many times a vert is used
740 for (u32 i = 0; i < icount; i += 3)
742 vc[ind[i]].NumActiveTris++;
743 vc[ind[i + 1]].NumActiveTris++;
744 vc[ind[i + 2]].NumActiveTris++;
746 const u32 tri_ind = i/3;
747 tc[tri_ind].ind[0] = ind[i];
748 tc[tri_ind].ind[1] = ind[i + 1];
749 tc[tri_ind].ind[2] = ind[i + 2];
752 // Second pass: list of each triangle
753 for (u32 i = 0; i < tcount; i++)
755 vc[tc[i].ind[0]].tris.push_back(i);
756 vc[tc[i].ind[1]].tris.push_back(i);
757 vc[tc[i].ind[2]].tris.push_back(i);
762 // Give initial scores
763 for (u16 i = 0; i < vcount; i++)
765 vc[i].score = FindVertexScore(&vc[i]);
767 for (u32 i = 0; i < tcount; i++)
770 vc[tc[i].ind[0]].score +
771 vc[tc[i].ind[1]].score +
772 vc[tc[i].ind[2]].score;
775 switch(mb->getVertexType())
777 case video::EVT_STANDARD:
779 video::S3DVertex *v = (video::S3DVertex *) mb->getVertices();
781 scene::SMeshBuffer *buf = new scene::SMeshBuffer();
782 buf->Material = mb->getMaterial();
784 buf->Vertices.reallocate(vcount);
785 buf->Indices.reallocate(icount);
787 core::map<const video::S3DVertex, const u16> sind; // search index for fast operation
788 typedef core::map<const video::S3DVertex, const u16>::Node snode;
795 if (tc[highest].drawn)
799 for (u32 t = 0; t < tcount; t++)
803 if (tc[t].score > hiscore)
806 hiscore = tc[t].score;
815 // Output the best triangle
816 u16 newind = buf->Vertices.size();
818 snode *s = sind.find(v[tc[highest].ind[0]]);
822 buf->Vertices.push_back(v[tc[highest].ind[0]]);
823 buf->Indices.push_back(newind);
824 sind.insert(v[tc[highest].ind[0]], newind);
829 buf->Indices.push_back(s->getValue());
832 s = sind.find(v[tc[highest].ind[1]]);
836 buf->Vertices.push_back(v[tc[highest].ind[1]]);
837 buf->Indices.push_back(newind);
838 sind.insert(v[tc[highest].ind[1]], newind);
843 buf->Indices.push_back(s->getValue());
846 s = sind.find(v[tc[highest].ind[2]]);
850 buf->Vertices.push_back(v[tc[highest].ind[2]]);
851 buf->Indices.push_back(newind);
852 sind.insert(v[tc[highest].ind[2]], newind);
856 buf->Indices.push_back(s->getValue());
859 vc[tc[highest].ind[0]].NumActiveTris--;
860 vc[tc[highest].ind[1]].NumActiveTris--;
861 vc[tc[highest].ind[2]].NumActiveTris--;
863 tc[highest].drawn = true;
865 for (u16 j = 0; j < 3; j++)
867 vcache *vert = &vc[tc[highest].ind[j]];
868 for (u16 t = 0; t < vert->tris.size(); t++)
870 if (highest == vert->tris[t])
878 lru.add(tc[highest].ind[0]);
879 lru.add(tc[highest].ind[1]);
880 highest = lru.add(tc[highest].ind[2], true);
884 buf->setBoundingBox(mb->getBoundingBox());
885 newmesh->addMeshBuffer(buf);
889 case video::EVT_2TCOORDS:
891 video::S3DVertex2TCoords *v = (video::S3DVertex2TCoords *) mb->getVertices();
893 scene::SMeshBufferLightMap *buf = new scene::SMeshBufferLightMap();
894 buf->Material = mb->getMaterial();
896 buf->Vertices.reallocate(vcount);
897 buf->Indices.reallocate(icount);
899 core::map<const video::S3DVertex2TCoords, const u16> sind; // search index for fast operation
900 typedef core::map<const video::S3DVertex2TCoords, const u16>::Node snode;
907 if (tc[highest].drawn)
911 for (u32 t = 0; t < tcount; t++)
915 if (tc[t].score > hiscore)
918 hiscore = tc[t].score;
927 // Output the best triangle
928 u16 newind = buf->Vertices.size();
930 snode *s = sind.find(v[tc[highest].ind[0]]);
934 buf->Vertices.push_back(v[tc[highest].ind[0]]);
935 buf->Indices.push_back(newind);
936 sind.insert(v[tc[highest].ind[0]], newind);
941 buf->Indices.push_back(s->getValue());
944 s = sind.find(v[tc[highest].ind[1]]);
948 buf->Vertices.push_back(v[tc[highest].ind[1]]);
949 buf->Indices.push_back(newind);
950 sind.insert(v[tc[highest].ind[1]], newind);
955 buf->Indices.push_back(s->getValue());
958 s = sind.find(v[tc[highest].ind[2]]);
962 buf->Vertices.push_back(v[tc[highest].ind[2]]);
963 buf->Indices.push_back(newind);
964 sind.insert(v[tc[highest].ind[2]], newind);
968 buf->Indices.push_back(s->getValue());
971 vc[tc[highest].ind[0]].NumActiveTris--;
972 vc[tc[highest].ind[1]].NumActiveTris--;
973 vc[tc[highest].ind[2]].NumActiveTris--;
975 tc[highest].drawn = true;
977 for (u16 j = 0; j < 3; j++)
979 vcache *vert = &vc[tc[highest].ind[j]];
980 for (u16 t = 0; t < vert->tris.size(); t++)
982 if (highest == vert->tris[t])
990 lru.add(tc[highest].ind[0]);
991 lru.add(tc[highest].ind[1]);
992 highest = lru.add(tc[highest].ind[2]);
996 buf->setBoundingBox(mb->getBoundingBox());
997 newmesh->addMeshBuffer(buf);
1002 case video::EVT_TANGENTS:
1004 video::S3DVertexTangents *v = (video::S3DVertexTangents *) mb->getVertices();
1006 scene::SMeshBufferTangents *buf = new scene::SMeshBufferTangents();
1007 buf->Material = mb->getMaterial();
1009 buf->Vertices.reallocate(vcount);
1010 buf->Indices.reallocate(icount);
1012 core::map<const video::S3DVertexTangents, const u16> sind; // search index for fast operation
1013 typedef core::map<const video::S3DVertexTangents, const u16>::Node snode;
1020 if (tc[highest].drawn)
1024 for (u32 t = 0; t < tcount; t++)
1028 if (tc[t].score > hiscore)
1031 hiscore = tc[t].score;
1040 // Output the best triangle
1041 u16 newind = buf->Vertices.size();
1043 snode *s = sind.find(v[tc[highest].ind[0]]);
1047 buf->Vertices.push_back(v[tc[highest].ind[0]]);
1048 buf->Indices.push_back(newind);
1049 sind.insert(v[tc[highest].ind[0]], newind);
1054 buf->Indices.push_back(s->getValue());
1057 s = sind.find(v[tc[highest].ind[1]]);
1061 buf->Vertices.push_back(v[tc[highest].ind[1]]);
1062 buf->Indices.push_back(newind);
1063 sind.insert(v[tc[highest].ind[1]], newind);
1068 buf->Indices.push_back(s->getValue());
1071 s = sind.find(v[tc[highest].ind[2]]);
1075 buf->Vertices.push_back(v[tc[highest].ind[2]]);
1076 buf->Indices.push_back(newind);
1077 sind.insert(v[tc[highest].ind[2]], newind);
1081 buf->Indices.push_back(s->getValue());
1084 vc[tc[highest].ind[0]].NumActiveTris--;
1085 vc[tc[highest].ind[1]].NumActiveTris--;
1086 vc[tc[highest].ind[2]].NumActiveTris--;
1088 tc[highest].drawn = true;
1090 for (u16 j = 0; j < 3; j++)
1092 vcache *vert = &vc[tc[highest].ind[j]];
1093 for (u16 t = 0; t < vert->tris.size(); t++)
1095 if (highest == vert->tris[t])
1097 vert->tris.erase(t);
1103 lru.add(tc[highest].ind[0]);
1104 lru.add(tc[highest].ind[1]);
1105 highest = lru.add(tc[highest].ind[2]);
1109 buf->setBoundingBox(mb->getBoundingBox());
1110 newmesh->addMeshBuffer(buf);
1119 } // for each meshbuffer