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>
27 #include <IAnimatedMeshSceneNode.h>
29 // In Irrlicht 1.8 the signature of ITexture::lock was changed from
30 // (bool, u32) to (E_TEXTURE_LOCK_MODE, u32).
31 #if IRRLICHT_VERSION_MAJOR == 1 && IRRLICHT_VERSION_MINOR <= 7
32 #define MY_ETLM_READ_ONLY true
34 #define MY_ETLM_READ_ONLY video::ETLM_READ_ONLY
37 inline static void applyShadeFactor(video::SColor& color, float factor)
39 color.setRed(core::clamp(core::round32(color.getRed()*factor), 0, 255));
40 color.setGreen(core::clamp(core::round32(color.getGreen()*factor), 0, 255));
41 color.setBlue(core::clamp(core::round32(color.getBlue()*factor), 0, 255));
44 void applyFacesShading(video::SColor &color, const v3f &normal)
47 Some drawtypes have normals set to (0, 0, 0), this must result in
48 maximum brightness: shade factor 1.0.
49 Shade factors for aligned cube faces are:
52 +-X 0.670820 sqrt(0.45)
53 +-Z 0.836660 sqrt(0.7)
55 float x2 = normal.X * normal.X;
56 float y2 = normal.Y * normal.Y;
57 float z2 = normal.Z * normal.Z;
59 applyShadeFactor(color, 0.670820f * x2 + 0.447213f * y2 + 0.836660f * z2);
60 else if ((x2 > 1e-3) || (z2 > 1e-3))
61 applyShadeFactor(color, 0.670820f * x2 + 1.000000f * y2 + 0.836660f * z2);
64 scene::IAnimatedMesh* createCubeMesh(v3f scale)
66 video::SColor c(255,255,255,255);
67 video::S3DVertex vertices[24] =
70 video::S3DVertex(-0.5,+0.5,-0.5, 0,1,0, c, 0,1),
71 video::S3DVertex(-0.5,+0.5,+0.5, 0,1,0, c, 0,0),
72 video::S3DVertex(+0.5,+0.5,+0.5, 0,1,0, c, 1,0),
73 video::S3DVertex(+0.5,+0.5,-0.5, 0,1,0, c, 1,1),
75 video::S3DVertex(-0.5,-0.5,-0.5, 0,-1,0, c, 0,0),
76 video::S3DVertex(+0.5,-0.5,-0.5, 0,-1,0, c, 1,0),
77 video::S3DVertex(+0.5,-0.5,+0.5, 0,-1,0, c, 1,1),
78 video::S3DVertex(-0.5,-0.5,+0.5, 0,-1,0, c, 0,1),
80 video::S3DVertex(+0.5,-0.5,-0.5, 1,0,0, c, 0,1),
81 video::S3DVertex(+0.5,+0.5,-0.5, 1,0,0, c, 0,0),
82 video::S3DVertex(+0.5,+0.5,+0.5, 1,0,0, c, 1,0),
83 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, 1,1),
86 video::S3DVertex(-0.5,-0.5,+0.5, -1,0,0, c, 0,1),
87 video::S3DVertex(-0.5,+0.5,+0.5, -1,0,0, c, 0,0),
88 video::S3DVertex(-0.5,+0.5,-0.5, -1,0,0, c, 1,0),
90 video::S3DVertex(-0.5,-0.5,+0.5, 0,0,1, c, 1,1),
91 video::S3DVertex(+0.5,-0.5,+0.5, 0,0,1, c, 0,1),
92 video::S3DVertex(+0.5,+0.5,+0.5, 0,0,1, c, 0,0),
93 video::S3DVertex(-0.5,+0.5,+0.5, 0,0,1, c, 1,0),
95 video::S3DVertex(-0.5,-0.5,-0.5, 0,0,-1, c, 0,1),
96 video::S3DVertex(-0.5,+0.5,-0.5, 0,0,-1, c, 0,0),
97 video::S3DVertex(+0.5,+0.5,-0.5, 0,0,-1, c, 1,0),
98 video::S3DVertex(+0.5,-0.5,-0.5, 0,0,-1, c, 1,1),
101 u16 indices[6] = {0,1,2,2,3,0};
103 scene::SMesh *mesh = new scene::SMesh();
104 for (u32 i=0; i<6; ++i)
106 scene::IMeshBuffer *buf = new scene::SMeshBuffer();
107 buf->append(vertices + 4 * i, 4, indices, 6);
108 // Set default material
109 buf->getMaterial().setFlag(video::EMF_LIGHTING, false);
110 buf->getMaterial().setFlag(video::EMF_BILINEAR_FILTER, false);
111 buf->getMaterial().MaterialType = video::EMT_TRANSPARENT_ALPHA_CHANNEL_REF;
112 // Add mesh buffer to mesh
113 mesh->addMeshBuffer(buf);
117 scene::SAnimatedMesh *anim_mesh = new scene::SAnimatedMesh(mesh);
119 scaleMesh(anim_mesh, scale); // also recalculates bounding box
123 void scaleMesh(scene::IMesh *mesh, v3f scale)
131 u32 mc = mesh->getMeshBufferCount();
132 for (u32 j = 0; j < mc; j++) {
133 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
134 const u32 stride = getVertexPitchFromType(buf->getVertexType());
135 u32 vertex_count = buf->getVertexCount();
136 u8 *vertices = (u8 *)buf->getVertices();
137 for (u32 i = 0; i < vertex_count; i++)
138 ((video::S3DVertex *)(vertices + i * stride))->Pos *= scale;
140 buf->recalculateBoundingBox();
142 // calculate total bounding box
144 bbox = buf->getBoundingBox();
146 bbox.addInternalBox(buf->getBoundingBox());
148 mesh->setBoundingBox(bbox);
151 void translateMesh(scene::IMesh *mesh, v3f vec)
159 u32 mc = mesh->getMeshBufferCount();
160 for (u32 j = 0; j < mc; j++) {
161 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
162 const u32 stride = getVertexPitchFromType(buf->getVertexType());
163 u32 vertex_count = buf->getVertexCount();
164 u8 *vertices = (u8 *)buf->getVertices();
165 for (u32 i = 0; i < vertex_count; i++)
166 ((video::S3DVertex *)(vertices + i * stride))->Pos += vec;
168 buf->recalculateBoundingBox();
170 // calculate total bounding box
172 bbox = buf->getBoundingBox();
174 bbox.addInternalBox(buf->getBoundingBox());
176 mesh->setBoundingBox(bbox);
179 void setMeshBufferColor(scene::IMeshBuffer *buf, const video::SColor &color)
181 const u32 stride = getVertexPitchFromType(buf->getVertexType());
182 u32 vertex_count = buf->getVertexCount();
183 u8 *vertices = (u8 *) buf->getVertices();
184 for (u32 i = 0; i < vertex_count; i++)
185 ((video::S3DVertex *) (vertices + i * stride))->Color = color;
188 void setAnimatedMeshColor(scene::IAnimatedMeshSceneNode *node, const video::SColor &color)
190 for (u32 i = 0; i < node->getMaterialCount(); ++i) {
191 node->getMaterial(i).EmissiveColor = color;
195 void setMeshColor(scene::IMesh *mesh, const video::SColor &color)
200 u32 mc = mesh->getMeshBufferCount();
201 for (u32 j = 0; j < mc; j++)
202 setMeshBufferColor(mesh->getMeshBuffer(j), color);
205 void colorizeMeshBuffer(scene::IMeshBuffer *buf, const video::SColor *buffercolor)
207 const u32 stride = getVertexPitchFromType(buf->getVertexType());
208 u32 vertex_count = buf->getVertexCount();
209 u8 *vertices = (u8 *) buf->getVertices();
210 for (u32 i = 0; i < vertex_count; i++) {
211 video::S3DVertex *vertex = (video::S3DVertex *) (vertices + i * stride);
212 video::SColor *vc = &(vertex->Color);
216 applyFacesShading(*vc, vertex->Normal);
220 void setMeshColorByNormalXYZ(scene::IMesh *mesh,
221 const video::SColor &colorX,
222 const video::SColor &colorY,
223 const video::SColor &colorZ)
228 u16 mc = mesh->getMeshBufferCount();
229 for (u16 j = 0; j < mc; j++) {
230 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
231 const u32 stride = getVertexPitchFromType(buf->getVertexType());
232 u32 vertex_count = buf->getVertexCount();
233 u8 *vertices = (u8 *)buf->getVertices();
234 for (u32 i = 0; i < vertex_count; i++) {
235 video::S3DVertex *vertex = (video::S3DVertex *)(vertices + i * stride);
236 f32 x = fabs(vertex->Normal.X);
237 f32 y = fabs(vertex->Normal.Y);
238 f32 z = fabs(vertex->Normal.Z);
239 if (x >= y && x >= z)
240 vertex->Color = colorX;
242 vertex->Color = colorY;
244 vertex->Color = colorZ;
249 void setMeshColorByNormal(scene::IMesh *mesh, const v3f &normal,
250 const video::SColor &color)
255 u16 mc = mesh->getMeshBufferCount();
256 for (u16 j = 0; j < mc; j++) {
257 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
258 const u32 stride = getVertexPitchFromType(buf->getVertexType());
259 u32 vertex_count = buf->getVertexCount();
260 u8 *vertices = (u8 *)buf->getVertices();
261 for (u32 i = 0; i < vertex_count; i++) {
262 video::S3DVertex *vertex = (video::S3DVertex *)(vertices + i * stride);
263 if (normal == vertex->Normal) {
264 vertex->Color = color;
270 void rotateMeshXYby(scene::IMesh *mesh, f64 degrees)
272 u16 mc = mesh->getMeshBufferCount();
273 for (u16 j = 0; j < mc; j++) {
274 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
275 const u32 stride = getVertexPitchFromType(buf->getVertexType());
276 u32 vertex_count = buf->getVertexCount();
277 u8 *vertices = (u8 *)buf->getVertices();
278 for (u32 i = 0; i < vertex_count; i++)
279 ((video::S3DVertex *)(vertices + i * stride))->Pos.rotateXYBy(degrees);
283 void rotateMeshXZby(scene::IMesh *mesh, f64 degrees)
285 u16 mc = mesh->getMeshBufferCount();
286 for (u16 j = 0; j < mc; j++) {
287 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
288 const u32 stride = getVertexPitchFromType(buf->getVertexType());
289 u32 vertex_count = buf->getVertexCount();
290 u8 *vertices = (u8 *)buf->getVertices();
291 for (u32 i = 0; i < vertex_count; i++)
292 ((video::S3DVertex *)(vertices + i * stride))->Pos.rotateXZBy(degrees);
296 void rotateMeshYZby(scene::IMesh *mesh, f64 degrees)
298 u16 mc = mesh->getMeshBufferCount();
299 for (u16 j = 0; j < mc; j++) {
300 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
301 const u32 stride = getVertexPitchFromType(buf->getVertexType());
302 u32 vertex_count = buf->getVertexCount();
303 u8 *vertices = (u8 *)buf->getVertices();
304 for (u32 i = 0; i < vertex_count; i++)
305 ((video::S3DVertex *)(vertices + i * stride))->Pos.rotateYZBy(degrees);
309 void rotateMeshBy6dFacedir(scene::IMesh *mesh, int facedir)
311 int axisdir = facedir >> 2;
314 u16 mc = mesh->getMeshBufferCount();
315 for (u16 j = 0; j < mc; j++) {
316 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
317 const u32 stride = getVertexPitchFromType(buf->getVertexType());
318 u32 vertex_count = buf->getVertexCount();
319 u8 *vertices = (u8 *)buf->getVertices();
320 for (u32 i = 0; i < vertex_count; i++) {
321 video::S3DVertex *vertex = (video::S3DVertex *)(vertices + i * stride);
325 vertex->Pos.rotateXZBy(-90);
326 else if (facedir == 2)
327 vertex->Pos.rotateXZBy(180);
328 else if (facedir == 3)
329 vertex->Pos.rotateXZBy(90);
332 vertex->Pos.rotateYZBy(90);
334 vertex->Pos.rotateXYBy(90);
335 else if (facedir == 2)
336 vertex->Pos.rotateXYBy(180);
337 else if (facedir == 3)
338 vertex->Pos.rotateXYBy(-90);
341 vertex->Pos.rotateYZBy(-90);
343 vertex->Pos.rotateXYBy(-90);
344 else if (facedir == 2)
345 vertex->Pos.rotateXYBy(180);
346 else if (facedir == 3)
347 vertex->Pos.rotateXYBy(90);
350 vertex->Pos.rotateXYBy(-90);
352 vertex->Pos.rotateYZBy(90);
353 else if (facedir == 2)
354 vertex->Pos.rotateYZBy(180);
355 else if (facedir == 3)
356 vertex->Pos.rotateYZBy(-90);
359 vertex->Pos.rotateXYBy(90);
361 vertex->Pos.rotateYZBy(-90);
362 else if (facedir == 2)
363 vertex->Pos.rotateYZBy(180);
364 else if (facedir == 3)
365 vertex->Pos.rotateYZBy(90);
368 vertex->Pos.rotateXYBy(-180);
370 vertex->Pos.rotateXZBy(90);
371 else if (facedir == 2)
372 vertex->Pos.rotateXZBy(180);
373 else if (facedir == 3)
374 vertex->Pos.rotateXZBy(-90);
383 void recalculateBoundingBox(scene::IMesh *src_mesh)
387 for (u16 j = 0; j < src_mesh->getMeshBufferCount(); j++) {
388 scene::IMeshBuffer *buf = src_mesh->getMeshBuffer(j);
389 buf->recalculateBoundingBox();
391 bbox = buf->getBoundingBox();
393 bbox.addInternalBox(buf->getBoundingBox());
395 src_mesh->setBoundingBox(bbox);
398 scene::IMeshBuffer* cloneMeshBuffer(scene::IMeshBuffer *mesh_buffer)
400 switch (mesh_buffer->getVertexType()) {
401 case video::EVT_STANDARD: {
402 video::S3DVertex *v = (video::S3DVertex *) mesh_buffer->getVertices();
403 u16 *indices = mesh_buffer->getIndices();
404 scene::SMeshBuffer *cloned_buffer = new scene::SMeshBuffer();
405 cloned_buffer->append(v, mesh_buffer->getVertexCount(), indices,
406 mesh_buffer->getIndexCount());
407 return cloned_buffer;
409 case video::EVT_2TCOORDS: {
410 video::S3DVertex2TCoords *v =
411 (video::S3DVertex2TCoords *) mesh_buffer->getVertices();
412 u16 *indices = mesh_buffer->getIndices();
413 scene::SMeshBufferTangents *cloned_buffer =
414 new scene::SMeshBufferTangents();
415 cloned_buffer->append(v, mesh_buffer->getVertexCount(), indices,
416 mesh_buffer->getIndexCount());
417 return cloned_buffer;
419 case video::EVT_TANGENTS: {
420 video::S3DVertexTangents *v =
421 (video::S3DVertexTangents *) mesh_buffer->getVertices();
422 u16 *indices = mesh_buffer->getIndices();
423 scene::SMeshBufferTangents *cloned_buffer =
424 new scene::SMeshBufferTangents();
425 cloned_buffer->append(v, mesh_buffer->getVertexCount(), indices,
426 mesh_buffer->getIndexCount());
427 return cloned_buffer;
430 // This should not happen.
435 scene::SMesh* cloneMesh(scene::IMesh *src_mesh)
437 scene::SMesh* dst_mesh = new scene::SMesh();
438 for (u16 j = 0; j < src_mesh->getMeshBufferCount(); j++) {
439 scene::IMeshBuffer *temp_buf = cloneMeshBuffer(
440 src_mesh->getMeshBuffer(j));
441 dst_mesh->addMeshBuffer(temp_buf);
448 scene::IMesh* convertNodeboxesToMesh(const std::vector<aabb3f> &boxes,
449 const f32 *uv_coords, float expand)
451 scene::SMesh* dst_mesh = new scene::SMesh();
453 for (u16 j = 0; j < 6; j++)
455 scene::IMeshBuffer *buf = new scene::SMeshBuffer();
456 buf->getMaterial().setFlag(video::EMF_LIGHTING, false);
457 buf->getMaterial().setFlag(video::EMF_BILINEAR_FILTER, false);
458 dst_mesh->addMeshBuffer(buf);
462 video::SColor c(255,255,255,255);
464 for (aabb3f box : boxes) {
467 box.MinEdge.X -= expand;
468 box.MinEdge.Y -= expand;
469 box.MinEdge.Z -= expand;
470 box.MaxEdge.X += expand;
471 box.MaxEdge.Y += expand;
472 box.MaxEdge.Z += expand;
474 // Compute texture UV coords
475 f32 tx1 = (box.MinEdge.X / BS) + 0.5;
476 f32 ty1 = (box.MinEdge.Y / BS) + 0.5;
477 f32 tz1 = (box.MinEdge.Z / BS) + 0.5;
478 f32 tx2 = (box.MaxEdge.X / BS) + 0.5;
479 f32 ty2 = (box.MaxEdge.Y / BS) + 0.5;
480 f32 tz2 = (box.MaxEdge.Z / BS) + 0.5;
482 f32 txc_default[24] = {
484 tx1, 1 - tz2, tx2, 1 - tz1,
488 tz1, 1 - ty2, tz2, 1 - ty1,
490 1 - tz2, 1 - ty2, 1 - tz1, 1 - ty1,
492 1 - tx2, 1 - ty2, 1 - tx1, 1 - ty1,
494 tx1, 1 - ty2, tx2, 1 - ty1,
497 // use default texture UV mapping if not provided
498 const f32 *txc = uv_coords ? uv_coords : txc_default;
500 v3f min = box.MinEdge;
501 v3f max = box.MaxEdge;
503 video::S3DVertex vertices[24] =
506 video::S3DVertex(min.X,max.Y,max.Z, 0,1,0, c, txc[0],txc[1]),
507 video::S3DVertex(max.X,max.Y,max.Z, 0,1,0, c, txc[2],txc[1]),
508 video::S3DVertex(max.X,max.Y,min.Z, 0,1,0, c, txc[2],txc[3]),
509 video::S3DVertex(min.X,max.Y,min.Z, 0,1,0, c, txc[0],txc[3]),
511 video::S3DVertex(min.X,min.Y,min.Z, 0,-1,0, c, txc[4],txc[5]),
512 video::S3DVertex(max.X,min.Y,min.Z, 0,-1,0, c, txc[6],txc[5]),
513 video::S3DVertex(max.X,min.Y,max.Z, 0,-1,0, c, txc[6],txc[7]),
514 video::S3DVertex(min.X,min.Y,max.Z, 0,-1,0, c, txc[4],txc[7]),
516 video::S3DVertex(max.X,max.Y,min.Z, 1,0,0, c, txc[ 8],txc[9]),
517 video::S3DVertex(max.X,max.Y,max.Z, 1,0,0, c, txc[10],txc[9]),
518 video::S3DVertex(max.X,min.Y,max.Z, 1,0,0, c, txc[10],txc[11]),
519 video::S3DVertex(max.X,min.Y,min.Z, 1,0,0, c, txc[ 8],txc[11]),
521 video::S3DVertex(min.X,max.Y,max.Z, -1,0,0, c, txc[12],txc[13]),
522 video::S3DVertex(min.X,max.Y,min.Z, -1,0,0, c, txc[14],txc[13]),
523 video::S3DVertex(min.X,min.Y,min.Z, -1,0,0, c, txc[14],txc[15]),
524 video::S3DVertex(min.X,min.Y,max.Z, -1,0,0, c, txc[12],txc[15]),
526 video::S3DVertex(max.X,max.Y,max.Z, 0,0,1, c, txc[16],txc[17]),
527 video::S3DVertex(min.X,max.Y,max.Z, 0,0,1, c, txc[18],txc[17]),
528 video::S3DVertex(min.X,min.Y,max.Z, 0,0,1, c, txc[18],txc[19]),
529 video::S3DVertex(max.X,min.Y,max.Z, 0,0,1, c, txc[16],txc[19]),
531 video::S3DVertex(min.X,max.Y,min.Z, 0,0,-1, c, txc[20],txc[21]),
532 video::S3DVertex(max.X,max.Y,min.Z, 0,0,-1, c, txc[22],txc[21]),
533 video::S3DVertex(max.X,min.Y,min.Z, 0,0,-1, c, txc[22],txc[23]),
534 video::S3DVertex(min.X,min.Y,min.Z, 0,0,-1, c, txc[20],txc[23]),
537 u16 indices[] = {0,1,2,2,3,0};
539 for(u16 j = 0; j < 24; j += 4)
541 scene::IMeshBuffer *buf = dst_mesh->getMeshBuffer(j / 4);
542 buf->append(vertices + j, 4, indices, 6);
550 core::array<u32> tris;
563 const u16 cachesize = 32;
565 float FindVertexScore(vcache *v)
567 const float CacheDecayPower = 1.5f;
568 const float LastTriScore = 0.75f;
569 const float ValenceBoostScale = 2.0f;
570 const float ValenceBoostPower = 0.5f;
571 const float MaxSizeVertexCache = 32.0f;
573 if (v->NumActiveTris == 0)
575 // No tri needs this vertex!
580 int CachePosition = v->cachepos;
581 if (CachePosition < 0)
583 // Vertex is not in FIFO cache - no score.
587 if (CachePosition < 3)
589 // This vertex was used in the last triangle,
590 // so it has a fixed score.
591 Score = LastTriScore;
595 // Points for being high in the cache.
596 const float Scaler = 1.0f / (MaxSizeVertexCache - 3);
597 Score = 1.0f - (CachePosition - 3) * Scaler;
598 Score = powf(Score, CacheDecayPower);
602 // Bonus points for having a low number of tris still to
603 // use the vert, so we get rid of lone verts quickly.
604 float ValenceBoost = powf(v->NumActiveTris,
606 Score += ValenceBoostScale * ValenceBoost;
612 A specialized LRU cache for the Forsyth algorithm.
619 f_lru(vcache *v, tcache *t): vc(v), tc(t)
621 for (int &i : cache) {
626 // Adds this vertex index and returns the highest-scoring triangle index
627 u32 add(u16 vert, bool updatetris = false)
631 // Mark existing pos as empty
632 for (u16 i = 0; i < cachesize; i++)
634 if (cache[i] == vert)
636 // Move everything down
637 for (u16 j = i; j; j--)
639 cache[j] = cache[j - 1];
649 if (cache[cachesize-1] != -1)
650 vc[cache[cachesize-1]].cachepos = -1;
652 // Move everything down
653 for (u16 i = cachesize - 1; i; i--)
655 cache[i] = cache[i - 1];
666 // Update cache positions
667 for (u16 i = 0; i < cachesize; i++)
672 vc[cache[i]].cachepos = i;
673 vc[cache[i]].score = FindVertexScore(&vc[cache[i]]);
676 // Update triangle scores
677 for (int i : cache) {
681 const u16 trisize = vc[i].tris.size();
682 for (u16 t = 0; t < trisize; t++)
684 tcache *tri = &tc[vc[i].tris[t]];
687 vc[tri->ind[0]].score +
688 vc[tri->ind[1]].score +
689 vc[tri->ind[2]].score;
691 if (tri->score > hiscore)
693 hiscore = tri->score;
694 highest = vc[i].tris[t];
704 s32 cache[cachesize];
710 Vertex cache optimization according to the Forsyth paper:
711 http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html
713 The function is thread-safe (read: you can optimize several meshes in different threads)
715 \param mesh Source mesh for the operation. */
716 scene::IMesh* createForsythOptimizedMesh(const scene::IMesh *mesh)
721 scene::SMesh *newmesh = new scene::SMesh();
722 newmesh->BoundingBox = mesh->getBoundingBox();
724 const u32 mbcount = mesh->getMeshBufferCount();
726 for (u32 b = 0; b < mbcount; ++b)
728 const scene::IMeshBuffer *mb = mesh->getMeshBuffer(b);
730 if (mb->getIndexType() != video::EIT_16BIT)
732 //os::Printer::log("Cannot optimize a mesh with 32bit indices", ELL_ERROR);
737 const u32 icount = mb->getIndexCount();
738 const u32 tcount = icount / 3;
739 const u32 vcount = mb->getVertexCount();
740 const u16 *ind = mb->getIndices();
742 vcache *vc = new vcache[vcount];
743 tcache *tc = new tcache[tcount];
748 for (u16 i = 0; i < vcount; i++)
752 vc[i].NumActiveTris = 0;
755 // First pass: count how many times a vert is used
756 for (u32 i = 0; i < icount; i += 3)
758 vc[ind[i]].NumActiveTris++;
759 vc[ind[i + 1]].NumActiveTris++;
760 vc[ind[i + 2]].NumActiveTris++;
762 const u32 tri_ind = i/3;
763 tc[tri_ind].ind[0] = ind[i];
764 tc[tri_ind].ind[1] = ind[i + 1];
765 tc[tri_ind].ind[2] = ind[i + 2];
768 // Second pass: list of each triangle
769 for (u32 i = 0; i < tcount; i++)
771 vc[tc[i].ind[0]].tris.push_back(i);
772 vc[tc[i].ind[1]].tris.push_back(i);
773 vc[tc[i].ind[2]].tris.push_back(i);
778 // Give initial scores
779 for (u16 i = 0; i < vcount; i++)
781 vc[i].score = FindVertexScore(&vc[i]);
783 for (u32 i = 0; i < tcount; i++)
786 vc[tc[i].ind[0]].score +
787 vc[tc[i].ind[1]].score +
788 vc[tc[i].ind[2]].score;
791 switch(mb->getVertexType())
793 case video::EVT_STANDARD:
795 video::S3DVertex *v = (video::S3DVertex *) mb->getVertices();
797 scene::SMeshBuffer *buf = new scene::SMeshBuffer();
798 buf->Material = mb->getMaterial();
800 buf->Vertices.reallocate(vcount);
801 buf->Indices.reallocate(icount);
803 core::map<const video::S3DVertex, const u16> sind; // search index for fast operation
804 typedef core::map<const video::S3DVertex, const u16>::Node snode;
811 if (tc[highest].drawn)
815 for (u32 t = 0; t < tcount; t++)
819 if (tc[t].score > hiscore)
822 hiscore = tc[t].score;
831 // Output the best triangle
832 u16 newind = buf->Vertices.size();
834 snode *s = sind.find(v[tc[highest].ind[0]]);
838 buf->Vertices.push_back(v[tc[highest].ind[0]]);
839 buf->Indices.push_back(newind);
840 sind.insert(v[tc[highest].ind[0]], newind);
845 buf->Indices.push_back(s->getValue());
848 s = sind.find(v[tc[highest].ind[1]]);
852 buf->Vertices.push_back(v[tc[highest].ind[1]]);
853 buf->Indices.push_back(newind);
854 sind.insert(v[tc[highest].ind[1]], newind);
859 buf->Indices.push_back(s->getValue());
862 s = sind.find(v[tc[highest].ind[2]]);
866 buf->Vertices.push_back(v[tc[highest].ind[2]]);
867 buf->Indices.push_back(newind);
868 sind.insert(v[tc[highest].ind[2]], newind);
872 buf->Indices.push_back(s->getValue());
875 vc[tc[highest].ind[0]].NumActiveTris--;
876 vc[tc[highest].ind[1]].NumActiveTris--;
877 vc[tc[highest].ind[2]].NumActiveTris--;
879 tc[highest].drawn = true;
881 for (u16 j : tc[highest].ind) {
882 vcache *vert = &vc[j];
883 for (u16 t = 0; t < vert->tris.size(); t++)
885 if (highest == vert->tris[t])
893 lru.add(tc[highest].ind[0]);
894 lru.add(tc[highest].ind[1]);
895 highest = lru.add(tc[highest].ind[2], true);
899 buf->setBoundingBox(mb->getBoundingBox());
900 newmesh->addMeshBuffer(buf);
904 case video::EVT_2TCOORDS:
906 video::S3DVertex2TCoords *v = (video::S3DVertex2TCoords *) mb->getVertices();
908 scene::SMeshBufferLightMap *buf = new scene::SMeshBufferLightMap();
909 buf->Material = mb->getMaterial();
911 buf->Vertices.reallocate(vcount);
912 buf->Indices.reallocate(icount);
914 core::map<const video::S3DVertex2TCoords, const u16> sind; // search index for fast operation
915 typedef core::map<const video::S3DVertex2TCoords, const u16>::Node snode;
922 if (tc[highest].drawn)
926 for (u32 t = 0; t < tcount; t++)
930 if (tc[t].score > hiscore)
933 hiscore = tc[t].score;
942 // Output the best triangle
943 u16 newind = buf->Vertices.size();
945 snode *s = sind.find(v[tc[highest].ind[0]]);
949 buf->Vertices.push_back(v[tc[highest].ind[0]]);
950 buf->Indices.push_back(newind);
951 sind.insert(v[tc[highest].ind[0]], newind);
956 buf->Indices.push_back(s->getValue());
959 s = sind.find(v[tc[highest].ind[1]]);
963 buf->Vertices.push_back(v[tc[highest].ind[1]]);
964 buf->Indices.push_back(newind);
965 sind.insert(v[tc[highest].ind[1]], newind);
970 buf->Indices.push_back(s->getValue());
973 s = sind.find(v[tc[highest].ind[2]]);
977 buf->Vertices.push_back(v[tc[highest].ind[2]]);
978 buf->Indices.push_back(newind);
979 sind.insert(v[tc[highest].ind[2]], newind);
983 buf->Indices.push_back(s->getValue());
986 vc[tc[highest].ind[0]].NumActiveTris--;
987 vc[tc[highest].ind[1]].NumActiveTris--;
988 vc[tc[highest].ind[2]].NumActiveTris--;
990 tc[highest].drawn = true;
992 for (u16 j : tc[highest].ind) {
993 vcache *vert = &vc[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 : tc[highest].ind) {
1105 vcache *vert = &vc[j];
1106 for (u16 t = 0; t < vert->tris.size(); t++)
1108 if (highest == vert->tris[t])
1110 vert->tris.erase(t);
1116 lru.add(tc[highest].ind[0]);
1117 lru.add(tc[highest].ind[1]);
1118 highest = lru.add(tc[highest].ind[2]);
1122 buf->setBoundingBox(mb->getBoundingBox());
1123 newmesh->addMeshBuffer(buf);
1132 } // for each meshbuffer