src/client/mesh.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>
   4
   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.
   9
  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.
  14
  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.
  18 */
  19
  20 #include "mesh.h"
  21 #include "debug.h"
  22 #include "log.h"
  23 #include "irrMap.h"
  24 #include <cmath>
  25 #include <iostream>
  26 #include <IAnimatedMesh.h>
  27 #include <SAnimatedMesh.h>
  28 #include <IAnimatedMeshSceneNode.h>
  29
  30 // In Irrlicht 1.8 the signature of ITexture::lock was changed from
  31 // (bool, u32) to (E_TEXTURE_LOCK_MODE, u32).
  32 #if IRRLICHT_VERSION_MAJOR == 1 && IRRLICHT_VERSION_MINOR <= 7
  33 #define MY_ETLM_READ_ONLY true
  34 #else
  35 #define MY_ETLM_READ_ONLY video::ETLM_READ_ONLY
  36 #endif
  37
  38 inline static void applyShadeFactor(video::SColor& color, float factor)
  39 {
  40         color.setRed(core::clamp(core::round32(color.getRed()*factor), 0, 255));
  41         color.setGreen(core::clamp(core::round32(color.getGreen()*factor), 0, 255));
  42         color.setBlue(core::clamp(core::round32(color.getBlue()*factor), 0, 255));
  43 }
  44
  45 void applyFacesShading(video::SColor &color, const v3f &normal)
  46 {
  47         /*
  48                 Some drawtypes have normals set to (0, 0, 0), this must result in
  49                 maximum brightness: shade factor 1.0.
  50                 Shade factors for aligned cube faces are:
  51                 +Y 1.000000 sqrt(1.0)
  52                 -Y 0.447213 sqrt(0.2)
  53                 +-X 0.670820 sqrt(0.45)
  54                 +-Z 0.836660 sqrt(0.7)
  55         */
  56         float x2 = normal.X * normal.X;
  57         float y2 = normal.Y * normal.Y;
  58         float z2 = normal.Z * normal.Z;
  59         if (normal.Y < 0)
  60                 applyShadeFactor(color, 0.670820f * x2 + 0.447213f * y2 + 0.836660f * z2);
  61         else if ((x2 > 1e-3) || (z2 > 1e-3))
  62                 applyShadeFactor(color, 0.670820f * x2 + 1.000000f * y2 + 0.836660f * z2);
  63 }
  64
  65 scene::IAnimatedMesh* createCubeMesh(v3f scale)
  66 {
  67         video::SColor c(255,255,255,255);
  68         video::S3DVertex vertices[24] =
  69         {
  70                 // Up
  71                 video::S3DVertex(-0.5,+0.5,-0.5, 0,1,0, c, 0,1),
  72                 video::S3DVertex(-0.5,+0.5,+0.5, 0,1,0, c, 0,0),
  73                 video::S3DVertex(+0.5,+0.5,+0.5, 0,1,0, c, 1,0),
  74                 video::S3DVertex(+0.5,+0.5,-0.5, 0,1,0, c, 1,1),
  75                 // Down
  76                 video::S3DVertex(-0.5,-0.5,-0.5, 0,-1,0, c, 0,0),
  77                 video::S3DVertex(+0.5,-0.5,-0.5, 0,-1,0, c, 1,0),
  78                 video::S3DVertex(+0.5,-0.5,+0.5, 0,-1,0, c, 1,1),
  79                 video::S3DVertex(-0.5,-0.5,+0.5, 0,-1,0, c, 0,1),
  80                 // Right
  81                 video::S3DVertex(+0.5,-0.5,-0.5, 1,0,0, c, 0,1),
  82                 video::S3DVertex(+0.5,+0.5,-0.5, 1,0,0, c, 0,0),
  83                 video::S3DVertex(+0.5,+0.5,+0.5, 1,0,0, c, 1,0),
  84                 video::S3DVertex(+0.5,-0.5,+0.5, 1,0,0, c, 1,1),
  85                 // Left
  86                 video::S3DVertex(-0.5,-0.5,-0.5, -1,0,0, c, 1,1),
  87                 video::S3DVertex(-0.5,-0.5,+0.5, -1,0,0, c, 0,1),
  88                 video::S3DVertex(-0.5,+0.5,+0.5, -1,0,0, c, 0,0),
  89                 video::S3DVertex(-0.5,+0.5,-0.5, -1,0,0, c, 1,0),
  90                 // Back
  91                 video::S3DVertex(-0.5,-0.5,+0.5, 0,0,1, c, 1,1),
  92                 video::S3DVertex(+0.5,-0.5,+0.5, 0,0,1, c, 0,1),
  93                 video::S3DVertex(+0.5,+0.5,+0.5, 0,0,1, c, 0,0),
  94                 video::S3DVertex(-0.5,+0.5,+0.5, 0,0,1, c, 1,0),
  95                 // Front
  96                 video::S3DVertex(-0.5,-0.5,-0.5, 0,0,-1, c, 0,1),
  97                 video::S3DVertex(-0.5,+0.5,-0.5, 0,0,-1, c, 0,0),
  98                 video::S3DVertex(+0.5,+0.5,-0.5, 0,0,-1, c, 1,0),
  99                 video::S3DVertex(+0.5,-0.5,-0.5, 0,0,-1, c, 1,1),
 100         };
 101
 102         u16 indices[6] = {0,1,2,2,3,0};
 103
 104         scene::SMesh *mesh = new scene::SMesh();
 105         for (u32 i=0; i<6; ++i)
 106         {
 107                 scene::IMeshBuffer *buf = new scene::SMeshBuffer();
 108                 buf->append(vertices + 4 * i, 4, indices, 6);
 109                 // Set default material
 110                 buf->getMaterial().setFlag(video::EMF_LIGHTING, false);
 111                 buf->getMaterial().setFlag(video::EMF_BILINEAR_FILTER, false);
 112                 buf->getMaterial().MaterialType = video::EMT_TRANSPARENT_ALPHA_CHANNEL_REF;
 113                 // Add mesh buffer to mesh
 114                 mesh->addMeshBuffer(buf);
 115                 buf->drop();
 116         }
 117
 118         scene::SAnimatedMesh *anim_mesh = new scene::SAnimatedMesh(mesh);
 119         mesh->drop();
 120         scaleMesh(anim_mesh, scale);  // also recalculates bounding box
 121         return anim_mesh;
 122 }
 123
 124 void scaleMesh(scene::IMesh *mesh, v3f scale)
 125 {
 126         if (mesh == NULL)
 127                 return;
 128
 129         aabb3f bbox;
 130         bbox.reset(0, 0, 0);
 131
 132         u32 mc = mesh->getMeshBufferCount();
 133         for (u32 j = 0; j < mc; j++) {
 134                 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
 135                 const u32 stride = getVertexPitchFromType(buf->getVertexType());
 136                 u32 vertex_count = buf->getVertexCount();
 137                 u8 *vertices = (u8 *)buf->getVertices();
 138                 for (u32 i = 0; i < vertex_count; i++)
 139                         ((video::S3DVertex *)(vertices + i * stride))->Pos *= scale;
 140
 141                 buf->recalculateBoundingBox();
 142
 143                 // calculate total bounding box
 144                 if (j == 0)
 145                         bbox = buf->getBoundingBox();
 146                 else
 147                         bbox.addInternalBox(buf->getBoundingBox());
 148         }
 149         mesh->setBoundingBox(bbox);
 150 }
 151
 152 void translateMesh(scene::IMesh *mesh, v3f vec)
 153 {
 154         if (mesh == NULL)
 155                 return;
 156
 157         aabb3f bbox;
 158         bbox.reset(0, 0, 0);
 159
 160         u32 mc = mesh->getMeshBufferCount();
 161         for (u32 j = 0; j < mc; j++) {
 162                 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
 163                 const u32 stride = getVertexPitchFromType(buf->getVertexType());
 164                 u32 vertex_count = buf->getVertexCount();
 165                 u8 *vertices = (u8 *)buf->getVertices();
 166                 for (u32 i = 0; i < vertex_count; i++)
 167                         ((video::S3DVertex *)(vertices + i * stride))->Pos += vec;
 168
 169                 buf->recalculateBoundingBox();
 170
 171                 // calculate total bounding box
 172                 if (j == 0)
 173                         bbox = buf->getBoundingBox();
 174                 else
 175                         bbox.addInternalBox(buf->getBoundingBox());
 176         }
 177         mesh->setBoundingBox(bbox);
 178 }
 179
 180 void setMeshBufferColor(scene::IMeshBuffer *buf, const video::SColor &color)
 181 {
 182         const u32 stride = getVertexPitchFromType(buf->getVertexType());
 183         u32 vertex_count = buf->getVertexCount();
 184         u8 *vertices = (u8 *) buf->getVertices();
 185         for (u32 i = 0; i < vertex_count; i++)
 186                 ((video::S3DVertex *) (vertices + i * stride))->Color = color;
 187 }
 188
 189 void setAnimatedMeshColor(scene::IAnimatedMeshSceneNode *node, const video::SColor &color)
 190 {
 191         for (u32 i = 0; i < node->getMaterialCount(); ++i) {
 192                 node->getMaterial(i).EmissiveColor = color;
 193         }
 194 }
 195
 196 void setMeshColor(scene::IMesh *mesh, const video::SColor &color)
 197 {
 198         if (mesh == NULL)
 199                 return;
 200
 201         u32 mc = mesh->getMeshBufferCount();
 202         for (u32 j = 0; j < mc; j++)
 203                 setMeshBufferColor(mesh->getMeshBuffer(j), color);
 204 }
 205
 206 void setMeshBufferTextureCoords(scene::IMeshBuffer *buf, const v2f *uv, u32 count)
 207 {
 208         const u32 stride = getVertexPitchFromType(buf->getVertexType());
 209         assert(buf->getVertexCount() >= count);
 210         u8 *vertices = (u8 *) buf->getVertices();
 211         for (u32 i = 0; i < count; i++)
 212                 ((video::S3DVertex*) (vertices + i * stride))->TCoords = uv[i];
 213 }
 214
 215 template <typename F>
 216 static void applyToMesh(scene::IMesh *mesh, const F &fn)
 217 {
 218         u16 mc = mesh->getMeshBufferCount();
 219         for (u16 j = 0; j < mc; j++) {
 220                 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
 221                 const u32 stride = getVertexPitchFromType(buf->getVertexType());
 222                 u32 vertex_count = buf->getVertexCount();
 223                 char *vertices = reinterpret_cast<char *>(buf->getVertices());
 224                 for (u32 i = 0; i < vertex_count; i++)
 225                         fn(reinterpret_cast<video::S3DVertex *>(vertices + i * stride));
 226         }
 227 }
 228
 229 void colorizeMeshBuffer(scene::IMeshBuffer *buf, const video::SColor *buffercolor)
 230 {
 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                 video::SColor *vc = &(vertex->Color);
 237                 // Reset color
 238                 *vc = *buffercolor;
 239                 // Apply shading
 240                 applyFacesShading(*vc, vertex->Normal);
 241         }
 242 }
 243
 244 void setMeshColorByNormalXYZ(scene::IMesh *mesh,
 245                 const video::SColor &colorX,
 246                 const video::SColor &colorY,
 247                 const video::SColor &colorZ)
 248 {
 249         if (!mesh)
 250                 return;
 251         auto colorizator = [=] (video::S3DVertex *vertex) {
 252                 f32 x = fabs(vertex->Normal.X);
 253                 f32 y = fabs(vertex->Normal.Y);
 254                 f32 z = fabs(vertex->Normal.Z);
 255                 if (x >= y && x >= z)
 256                         vertex->Color = colorX;
 257                 else if (y >= z)
 258                         vertex->Color = colorY;
 259                 else
 260                         vertex->Color = colorZ;
 261         };
 262         applyToMesh(mesh, colorizator);
 263 }
 264
 265 void setMeshColorByNormal(scene::IMesh *mesh, const v3f &normal,
 266                 const video::SColor &color)
 267 {
 268         if (!mesh)
 269                 return;
 270         auto colorizator = [normal, color] (video::S3DVertex *vertex) {
 271                 if (vertex->Normal == normal)
 272                         vertex->Color = color;
 273         };
 274         applyToMesh(mesh, colorizator);
 275 }
 276
 277 template <float v3f::*U, float v3f::*V>
 278 static void rotateMesh(scene::IMesh *mesh, float degrees)
 279 {
 280         degrees *= M_PI / 180.0f;
 281         float c = std::cos(degrees);
 282         float s = std::sin(degrees);
 283         auto rotator = [c, s] (video::S3DVertex *vertex) {
 284                 float u = vertex->Pos.*U;
 285                 float v = vertex->Pos.*V;
 286                 vertex->Pos.*U = c * u - s * v;
 287                 vertex->Pos.*V = s * u + c * v;
 288         };
 289         applyToMesh(mesh, rotator);
 290 }
 291
 292 void rotateMeshXYby(scene::IMesh *mesh, f64 degrees)
 293 {
 294         rotateMesh<&v3f::X, &v3f::Y>(mesh, degrees);
 295 }
 296
 297 void rotateMeshXZby(scene::IMesh *mesh, f64 degrees)
 298 {
 299         rotateMesh<&v3f::X, &v3f::Z>(mesh, degrees);
 300 }
 301
 302 void rotateMeshYZby(scene::IMesh *mesh, f64 degrees)
 303 {
 304         rotateMesh<&v3f::Y, &v3f::Z>(mesh, degrees);
 305 }
 306
 307 void rotateMeshBy6dFacedir(scene::IMesh *mesh, int facedir)
 308 {
 309         int axisdir = facedir >> 2;
 310         facedir &= 0x03;
 311         switch (facedir) {
 312                 case 1: rotateMeshXZby(mesh, -90); break;
 313                 case 2: rotateMeshXZby(mesh, 180); break;
 314                 case 3: rotateMeshXZby(mesh, 90); break;
 315         }
 316         switch (axisdir) {
 317                 case 1: rotateMeshYZby(mesh, 90); break; // z+
 318                 case 2: rotateMeshYZby(mesh, -90); break; // z-
 319                 case 3: rotateMeshXYby(mesh, -90); break; // x+
 320                 case 4: rotateMeshXYby(mesh, 90); break; // x-
 321                 case 5: rotateMeshXYby(mesh, -180); break;
 322         }
 323 }
 324
 325 void recalculateBoundingBox(scene::IMesh *src_mesh)
 326 {
 327         aabb3f bbox;
 328         bbox.reset(0,0,0);
 329         for (u16 j = 0; j < src_mesh->getMeshBufferCount(); j++) {
 330                 scene::IMeshBuffer *buf = src_mesh->getMeshBuffer(j);
 331                 buf->recalculateBoundingBox();
 332                 if (j == 0)
 333                         bbox = buf->getBoundingBox();
 334                 else
 335                         bbox.addInternalBox(buf->getBoundingBox());
 336         }
 337         src_mesh->setBoundingBox(bbox);
 338 }
 339
 340 bool checkMeshNormals(scene::IMesh *mesh)
 341 {
 342         u32 buffer_count = mesh->getMeshBufferCount();
 343
 344         for (u32 i = 0; i < buffer_count; i++) {
 345                 scene::IMeshBuffer *buffer = mesh->getMeshBuffer(i);
 346
 347                 // Here we intentionally check only first normal, assuming that if buffer
 348                 // has it valid, then most likely all other ones are fine too. We can
 349                 // check all of the normals to have length, but it seems like an overkill
 350                 // hurting the performance and covering only really weird broken models.
 351                 f32 length = buffer->getNormal(0).getLength();
 352
 353                 if (!std::isfinite(length) || length < 1e-10f)
 354                         return false;
 355         }
 356
 357         return true;
 358 }
 359
 360 scene::IMeshBuffer* cloneMeshBuffer(scene::IMeshBuffer *mesh_buffer)
 361 {
 362         switch (mesh_buffer->getVertexType()) {
 363         case video::EVT_STANDARD: {
 364                 video::S3DVertex *v = (video::S3DVertex *) mesh_buffer->getVertices();
 365                 u16 *indices = mesh_buffer->getIndices();
 366                 scene::SMeshBuffer *cloned_buffer = new scene::SMeshBuffer();
 367                 cloned_buffer->append(v, mesh_buffer->getVertexCount(), indices,
 368                         mesh_buffer->getIndexCount());
 369                 return cloned_buffer;
 370         }
 371         case video::EVT_2TCOORDS: {
 372                 video::S3DVertex2TCoords *v =
 373                         (video::S3DVertex2TCoords *) mesh_buffer->getVertices();
 374                 u16 *indices = mesh_buffer->getIndices();
 375                 scene::SMeshBufferLightMap *cloned_buffer =
 376                         new scene::SMeshBufferLightMap();
 377                 cloned_buffer->append(v, mesh_buffer->getVertexCount(), indices,
 378                         mesh_buffer->getIndexCount());
 379                 return cloned_buffer;
 380         }
 381         case video::EVT_TANGENTS: {
 382                 video::S3DVertexTangents *v =
 383                         (video::S3DVertexTangents *) mesh_buffer->getVertices();
 384                 u16 *indices = mesh_buffer->getIndices();
 385                 scene::SMeshBufferTangents *cloned_buffer =
 386                         new scene::SMeshBufferTangents();
 387                 cloned_buffer->append(v, mesh_buffer->getVertexCount(), indices,
 388                         mesh_buffer->getIndexCount());
 389                 return cloned_buffer;
 390         }
 391         }
 392         // This should not happen.
 393         sanity_check(false);
 394         return NULL;
 395 }
 396
 397 scene::SMesh* cloneMesh(scene::IMesh *src_mesh)
 398 {
 399         scene::SMesh* dst_mesh = new scene::SMesh();
 400         for (u16 j = 0; j < src_mesh->getMeshBufferCount(); j++) {
 401                 scene::IMeshBuffer *temp_buf = cloneMeshBuffer(
 402                         src_mesh->getMeshBuffer(j));
 403                 dst_mesh->addMeshBuffer(temp_buf);
 404                 temp_buf->drop();
 405
 406         }
 407         return dst_mesh;
 408 }
 409
 410 scene::IMesh* convertNodeboxesToMesh(const std::vector<aabb3f> &boxes,
 411                 const f32 *uv_coords, float expand)
 412 {
 413         scene::SMesh* dst_mesh = new scene::SMesh();
 414
 415         for (u16 j = 0; j < 6; j++)
 416         {
 417                 scene::IMeshBuffer *buf = new scene::SMeshBuffer();
 418                 buf->getMaterial().setFlag(video::EMF_LIGHTING, false);
 419                 buf->getMaterial().setFlag(video::EMF_BILINEAR_FILTER, false);
 420                 dst_mesh->addMeshBuffer(buf);
 421                 buf->drop();
 422         }
 423
 424         video::SColor c(255,255,255,255);
 425
 426         for (aabb3f box : boxes) {
 427                 box.repair();
 428
 429                 box.MinEdge.X -= expand;
 430                 box.MinEdge.Y -= expand;
 431                 box.MinEdge.Z -= expand;
 432                 box.MaxEdge.X += expand;
 433                 box.MaxEdge.Y += expand;
 434                 box.MaxEdge.Z += expand;
 435
 436                 // Compute texture UV coords
 437                 f32 tx1 = (box.MinEdge.X / BS) + 0.5;
 438                 f32 ty1 = (box.MinEdge.Y / BS) + 0.5;
 439                 f32 tz1 = (box.MinEdge.Z / BS) + 0.5;
 440                 f32 tx2 = (box.MaxEdge.X / BS) + 0.5;
 441                 f32 ty2 = (box.MaxEdge.Y / BS) + 0.5;
 442                 f32 tz2 = (box.MaxEdge.Z / BS) + 0.5;
 443
 444                 f32 txc_default[24] = {
 445                         // up
 446                         tx1, 1 - tz2, tx2, 1 - tz1,
 447                         // down
 448                         tx1, tz1, tx2, tz2,
 449                         // right
 450                         tz1, 1 - ty2, tz2, 1 - ty1,
 451                         // left
 452                         1 - tz2, 1 - ty2, 1 - tz1, 1 - ty1,
 453                         // back
 454                         1 - tx2, 1 - ty2, 1 - tx1, 1 - ty1,
 455                         // front
 456                         tx1, 1 - ty2, tx2, 1 - ty1,
 457                 };
 458
 459                 // use default texture UV mapping if not provided
 460                 const f32 *txc = uv_coords ? uv_coords : txc_default;
 461
 462                 v3f min = box.MinEdge;
 463                 v3f max = box.MaxEdge;
 464
 465                 video::S3DVertex vertices[24] =
 466                 {
 467                         // up
 468                         video::S3DVertex(min.X,max.Y,max.Z, 0,1,0, c, txc[0],txc[1]),
 469                         video::S3DVertex(max.X,max.Y,max.Z, 0,1,0, c, txc[2],txc[1]),
 470                         video::S3DVertex(max.X,max.Y,min.Z, 0,1,0, c, txc[2],txc[3]),
 471                         video::S3DVertex(min.X,max.Y,min.Z, 0,1,0, c, txc[0],txc[3]),
 472                         // down
 473                         video::S3DVertex(min.X,min.Y,min.Z, 0,-1,0, c, txc[4],txc[5]),
 474                         video::S3DVertex(max.X,min.Y,min.Z, 0,-1,0, c, txc[6],txc[5]),
 475                         video::S3DVertex(max.X,min.Y,max.Z, 0,-1,0, c, txc[6],txc[7]),
 476                         video::S3DVertex(min.X,min.Y,max.Z, 0,-1,0, c, txc[4],txc[7]),
 477                         // right
 478                         video::S3DVertex(max.X,max.Y,min.Z, 1,0,0, c, txc[ 8],txc[9]),
 479                         video::S3DVertex(max.X,max.Y,max.Z, 1,0,0, c, txc[10],txc[9]),
 480                         video::S3DVertex(max.X,min.Y,max.Z, 1,0,0, c, txc[10],txc[11]),
 481                         video::S3DVertex(max.X,min.Y,min.Z, 1,0,0, c, txc[ 8],txc[11]),
 482                         // left
 483                         video::S3DVertex(min.X,max.Y,max.Z, -1,0,0, c, txc[12],txc[13]),
 484                         video::S3DVertex(min.X,max.Y,min.Z, -1,0,0, c, txc[14],txc[13]),
 485                         video::S3DVertex(min.X,min.Y,min.Z, -1,0,0, c, txc[14],txc[15]),
 486                         video::S3DVertex(min.X,min.Y,max.Z, -1,0,0, c, txc[12],txc[15]),
 487                         // back
 488                         video::S3DVertex(max.X,max.Y,max.Z, 0,0,1, c, txc[16],txc[17]),
 489                         video::S3DVertex(min.X,max.Y,max.Z, 0,0,1, c, txc[18],txc[17]),
 490                         video::S3DVertex(min.X,min.Y,max.Z, 0,0,1, c, txc[18],txc[19]),
 491                         video::S3DVertex(max.X,min.Y,max.Z, 0,0,1, c, txc[16],txc[19]),
 492                         // front
 493                         video::S3DVertex(min.X,max.Y,min.Z, 0,0,-1, c, txc[20],txc[21]),
 494                         video::S3DVertex(max.X,max.Y,min.Z, 0,0,-1, c, txc[22],txc[21]),
 495                         video::S3DVertex(max.X,min.Y,min.Z, 0,0,-1, c, txc[22],txc[23]),
 496                         video::S3DVertex(min.X,min.Y,min.Z, 0,0,-1, c, txc[20],txc[23]),
 497                 };
 498
 499                 u16 indices[] = {0,1,2,2,3,0};
 500
 501                 for(u16 j = 0; j < 24; j += 4)
 502                 {
 503                         scene::IMeshBuffer *buf = dst_mesh->getMeshBuffer(j / 4);
 504                         buf->append(vertices + j, 4, indices, 6);
 505                 }
 506         }
 507         return dst_mesh;
 508 }
 509
 510 struct vcache
 511 {
 512         core::array<u32> tris;
 513         float score;
 514         s16 cachepos;
 515         u16 NumActiveTris;
 516 };
 517
 518 struct tcache
 519 {
 520         u16 ind[3];
 521         float score;
 522         bool drawn;
 523 };
 524
 525 const u16 cachesize = 32;
 526
 527 float FindVertexScore(vcache *v)
 528 {
 529         const float CacheDecayPower = 1.5f;
 530         const float LastTriScore = 0.75f;
 531         const float ValenceBoostScale = 2.0f;
 532         const float ValenceBoostPower = 0.5f;
 533         const float MaxSizeVertexCache = 32.0f;
 534
 535         if (v->NumActiveTris == 0)
 536         {
 537                 // No tri needs this vertex!
 538                 return -1.0f;
 539         }
 540
 541         float Score = 0.0f;
 542         int CachePosition = v->cachepos;
 543         if (CachePosition < 0)
 544         {
 545                 // Vertex is not in FIFO cache - no score.
 546         }
 547         else
 548         {
 549                 if (CachePosition < 3)
 550                 {
 551                         // This vertex was used in the last triangle,
 552                         // so it has a fixed score.
 553                         Score = LastTriScore;
 554                 }
 555                 else
 556                 {
 557                         // Points for being high in the cache.
 558                         const float Scaler = 1.0f / (MaxSizeVertexCache - 3);
 559                         Score = 1.0f - (CachePosition - 3) * Scaler;
 560                         Score = powf(Score, CacheDecayPower);
 561                 }
 562         }
 563
 564         // Bonus points for having a low number of tris still to
 565         // use the vert, so we get rid of lone verts quickly.
 566         float ValenceBoost = powf(v->NumActiveTris,
 567                                 -ValenceBoostPower);
 568         Score += ValenceBoostScale * ValenceBoost;
 569
 570         return Score;
 571 }
 572
 573 /*
 574         A specialized LRU cache for the Forsyth algorithm.
 575 */
 576
 577 class f_lru
 578 {
 579
 580 public:
 581         f_lru(vcache *v, tcache *t): vc(v), tc(t)
 582         {
 583                 for (int &i : cache) {
 584                         i = -1;
 585                 }
 586         }
 587
 588         // Adds this vertex index and returns the highest-scoring triangle index
 589         u32 add(u16 vert, bool updatetris = false)
 590         {
 591                 bool found = false;
 592
 593                 // Mark existing pos as empty
 594                 for (u16 i = 0; i < cachesize; i++)
 595                 {
 596                         if (cache[i] == vert)
 597                         {
 598                                 // Move everything down
 599                                 for (u16 j = i; j; j--)
 600                                 {
 601                                         cache[j] = cache[j - 1];
 602                                 }
 603
 604                                 found = true;
 605                                 break;
 606                         }
 607                 }
 608
 609                 if (!found)
 610                 {
 611                         if (cache[cachesize-1] != -1)
 612                                 vc[cache[cachesize-1]].cachepos = -1;
 613
 614                         // Move everything down
 615                         for (u16 i = cachesize - 1; i; i--)
 616                         {
 617                                 cache[i] = cache[i - 1];
 618                         }
 619                 }
 620
 621                 cache[0] = vert;
 622
 623                 u32 highest = 0;
 624                 float hiscore = 0;
 625
 626                 if (updatetris)
 627                 {
 628                         // Update cache positions
 629                         for (u16 i = 0; i < cachesize; i++)
 630                         {
 631                                 if (cache[i] == -1)
 632                                         break;
 633
 634                                 vc[cache[i]].cachepos = i;
 635                                 vc[cache[i]].score = FindVertexScore(&vc[cache[i]]);
 636                         }
 637
 638                         // Update triangle scores
 639                         for (int i : cache) {
 640                                 if (i == -1)
 641                                         break;
 642
 643                                 const u16 trisize = vc[i].tris.size();
 644                                 for (u16 t = 0; t < trisize; t++)
 645                                 {
 646                                         tcache *tri = &tc[vc[i].tris[t]];
 647
 648                                         tri->score =
 649                                                 vc[tri->ind[0]].score +
 650                                                 vc[tri->ind[1]].score +
 651                                                 vc[tri->ind[2]].score;
 652
 653                                         if (tri->score > hiscore)
 654                                         {
 655                                                 hiscore = tri->score;
 656                                                 highest = vc[i].tris[t];
 657                                         }
 658                                 }
 659                         }
 660                 }
 661
 662                 return highest;
 663         }
 664
 665 private:
 666         s32 cache[cachesize];
 667         vcache *vc;
 668         tcache *tc;
 669 };
 670
 671 /**
 672 Vertex cache optimization according to the Forsyth paper:
 673 http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html
 674
 675 The function is thread-safe (read: you can optimize several meshes in different threads)
 676
 677 \param mesh Source mesh for the operation.  */
 678 scene::IMesh* createForsythOptimizedMesh(const scene::IMesh *mesh)
 679 {
 680         if (!mesh)
 681                 return 0;
 682
 683         scene::SMesh *newmesh = new scene::SMesh();
 684         newmesh->BoundingBox = mesh->getBoundingBox();
 685
 686         const u32 mbcount = mesh->getMeshBufferCount();
 687
 688         for (u32 b = 0; b < mbcount; ++b)
 689         {
 690                 const scene::IMeshBuffer *mb = mesh->getMeshBuffer(b);
 691
 692                 if (mb->getIndexType() != video::EIT_16BIT)
 693                 {
 694                         //os::Printer::log("Cannot optimize a mesh with 32bit indices", ELL_ERROR);
 695                         newmesh->drop();
 696                         return 0;
 697                 }
 698
 699                 const u32 icount = mb->getIndexCount();
 700                 const u32 tcount = icount / 3;
 701                 const u32 vcount = mb->getVertexCount();
 702                 const u16 *ind = mb->getIndices();
 703
 704                 vcache *vc = new vcache[vcount];
 705                 tcache *tc = new tcache[tcount];
 706
 707                 f_lru lru(vc, tc);
 708
 709                 // init
 710                 for (u16 i = 0; i < vcount; i++)
 711                 {
 712                         vc[i].score = 0;
 713                         vc[i].cachepos = -1;
 714                         vc[i].NumActiveTris = 0;
 715                 }
 716
 717                 // First pass: count how many times a vert is used
 718                 for (u32 i = 0; i < icount; i += 3)
 719                 {
 720                         vc[ind[i]].NumActiveTris++;
 721                         vc[ind[i + 1]].NumActiveTris++;
 722                         vc[ind[i + 2]].NumActiveTris++;
 723
 724                         const u32 tri_ind = i/3;
 725                         tc[tri_ind].ind[0] = ind[i];
 726                         tc[tri_ind].ind[1] = ind[i + 1];
 727                         tc[tri_ind].ind[2] = ind[i + 2];
 728                 }
 729
 730                 // Second pass: list of each triangle
 731                 for (u32 i = 0; i < tcount; i++)
 732                 {
 733                         vc[tc[i].ind[0]].tris.push_back(i);
 734                         vc[tc[i].ind[1]].tris.push_back(i);
 735                         vc[tc[i].ind[2]].tris.push_back(i);
 736
 737                         tc[i].drawn = false;
 738                 }
 739
 740                 // Give initial scores
 741                 for (u16 i = 0; i < vcount; i++)
 742                 {
 743                         vc[i].score = FindVertexScore(&vc[i]);
 744                 }
 745                 for (u32 i = 0; i < tcount; i++)
 746                 {
 747                         tc[i].score =
 748                                         vc[tc[i].ind[0]].score +
 749                                         vc[tc[i].ind[1]].score +
 750                                         vc[tc[i].ind[2]].score;
 751                 }
 752
 753                 switch(mb->getVertexType())
 754                 {
 755                         case video::EVT_STANDARD:
 756                         {
 757                                 video::S3DVertex *v = (video::S3DVertex *) mb->getVertices();
 758
 759                                 scene::SMeshBuffer *buf = new scene::SMeshBuffer();
 760                                 buf->Material = mb->getMaterial();
 761
 762                                 buf->Vertices.reallocate(vcount);
 763                                 buf->Indices.reallocate(icount);
 764
 765                                 core::map<const video::S3DVertex, const u16> sind; // search index for fast operation
 766                                 typedef core::map<const video::S3DVertex, const u16>::Node snode;
 767
 768                                 // Main algorithm
 769                                 u32 highest = 0;
 770                                 u32 drawcalls = 0;
 771                                 for (;;)
 772                                 {
 773                                         if (tc[highest].drawn)
 774                                         {
 775                                                 bool found = false;
 776                                                 float hiscore = 0;
 777                                                 for (u32 t = 0; t < tcount; t++)
 778                                                 {
 779                                                         if (!tc[t].drawn)
 780                                                         {
 781                                                                 if (tc[t].score > hiscore)
 782                                                                 {
 783                                                                         highest = t;
 784                                                                         hiscore = tc[t].score;
 785                                                                         found = true;
 786                                                                 }
 787                                                         }
 788                                                 }
 789                                                 if (!found)
 790                                                         break;
 791                                         }
 792
 793                                         // Output the best triangle
 794                                         u16 newind = buf->Vertices.size();
 795
 796                                         snode *s = sind.find(v[tc[highest].ind[0]]);
 797
 798                                         if (!s)
 799                                         {
 800                                                 buf->Vertices.push_back(v[tc[highest].ind[0]]);
 801                                                 buf->Indices.push_back(newind);
 802                                                 sind.insert(v[tc[highest].ind[0]], newind);
 803                                                 newind++;
 804                                         }
 805                                         else
 806                                         {
 807                                                 buf->Indices.push_back(s->getValue());
 808                                         }
 809
 810                                         s = sind.find(v[tc[highest].ind[1]]);
 811
 812                                         if (!s)
 813                                         {
 814                                                 buf->Vertices.push_back(v[tc[highest].ind[1]]);
 815                                                 buf->Indices.push_back(newind);
 816                                                 sind.insert(v[tc[highest].ind[1]], newind);
 817                                                 newind++;
 818                                         }
 819                                         else
 820                                         {
 821                                                 buf->Indices.push_back(s->getValue());
 822                                         }
 823
 824                                         s = sind.find(v[tc[highest].ind[2]]);
 825
 826                                         if (!s)
 827                                         {
 828                                                 buf->Vertices.push_back(v[tc[highest].ind[2]]);
 829                                                 buf->Indices.push_back(newind);
 830                                                 sind.insert(v[tc[highest].ind[2]], newind);
 831                                         }
 832                                         else
 833                                         {
 834                                                 buf->Indices.push_back(s->getValue());
 835                                         }
 836
 837                                         vc[tc[highest].ind[0]].NumActiveTris--;
 838                                         vc[tc[highest].ind[1]].NumActiveTris--;
 839                                         vc[tc[highest].ind[2]].NumActiveTris--;
 840
 841                                         tc[highest].drawn = true;
 842
 843                                         for (u16 j : tc[highest].ind) {
 844                                                 vcache *vert = &vc[j];
 845                                                 for (u16 t = 0; t < vert->tris.size(); t++)
 846                                                 {
 847                                                         if (highest == vert->tris[t])
 848                                                         {
 849                                                                 vert->tris.erase(t);
 850                                                                 break;
 851                                                         }
 852                                                 }
 853                                         }
 854
 855                                         lru.add(tc[highest].ind[0]);
 856                                         lru.add(tc[highest].ind[1]);
 857                                         highest = lru.add(tc[highest].ind[2], true);
 858                                         drawcalls++;
 859                                 }
 860
 861                                 buf->setBoundingBox(mb->getBoundingBox());
 862                                 newmesh->addMeshBuffer(buf);
 863                                 buf->drop();
 864                         }
 865                         break;
 866                         case video::EVT_2TCOORDS:
 867                         {
 868                                 video::S3DVertex2TCoords *v = (video::S3DVertex2TCoords *) mb->getVertices();
 869
 870                                 scene::SMeshBufferLightMap *buf = new scene::SMeshBufferLightMap();
 871                                 buf->Material = mb->getMaterial();
 872
 873                                 buf->Vertices.reallocate(vcount);
 874                                 buf->Indices.reallocate(icount);
 875
 876                                 core::map<const video::S3DVertex2TCoords, const u16> sind; // search index for fast operation
 877                                 typedef core::map<const video::S3DVertex2TCoords, const u16>::Node snode;
 878
 879                                 // Main algorithm
 880                                 u32 highest = 0;
 881                                 u32 drawcalls = 0;
 882                                 for (;;)
 883                                 {
 884                                         if (tc[highest].drawn)
 885                                         {
 886                                                 bool found = false;
 887                                                 float hiscore = 0;
 888                                                 for (u32 t = 0; t < tcount; t++)
 889                                                 {
 890                                                         if (!tc[t].drawn)
 891                                                         {
 892                                                                 if (tc[t].score > hiscore)
 893                                                                 {
 894                                                                         highest = t;
 895                                                                         hiscore = tc[t].score;
 896                                                                         found = true;
 897                                                                 }
 898                                                         }
 899                                                 }
 900                                                 if (!found)
 901                                                         break;
 902                                         }
 903
 904                                         // Output the best triangle
 905                                         u16 newind = buf->Vertices.size();
 906
 907                                         snode *s = sind.find(v[tc[highest].ind[0]]);
 908
 909                                         if (!s)
 910                                         {
 911                                                 buf->Vertices.push_back(v[tc[highest].ind[0]]);
 912                                                 buf->Indices.push_back(newind);
 913                                                 sind.insert(v[tc[highest].ind[0]], newind);
 914                                                 newind++;
 915                                         }
 916                                         else
 917                                         {
 918                                                 buf->Indices.push_back(s->getValue());
 919                                         }
 920
 921                                         s = sind.find(v[tc[highest].ind[1]]);
 922
 923                                         if (!s)
 924                                         {
 925                                                 buf->Vertices.push_back(v[tc[highest].ind[1]]);
 926                                                 buf->Indices.push_back(newind);
 927                                                 sind.insert(v[tc[highest].ind[1]], newind);
 928                                                 newind++;
 929                                         }
 930                                         else
 931                                         {
 932                                                 buf->Indices.push_back(s->getValue());
 933                                         }
 934
 935                                         s = sind.find(v[tc[highest].ind[2]]);
 936
 937                                         if (!s)
 938                                         {
 939                                                 buf->Vertices.push_back(v[tc[highest].ind[2]]);
 940                                                 buf->Indices.push_back(newind);
 941                                                 sind.insert(v[tc[highest].ind[2]], newind);
 942                                         }
 943                                         else
 944                                         {
 945                                                 buf->Indices.push_back(s->getValue());
 946                                         }
 947
 948                                         vc[tc[highest].ind[0]].NumActiveTris--;
 949                                         vc[tc[highest].ind[1]].NumActiveTris--;
 950                                         vc[tc[highest].ind[2]].NumActiveTris--;
 951
 952                                         tc[highest].drawn = true;
 953
 954                                         for (u16 j : tc[highest].ind) {
 955                                                 vcache *vert = &vc[j];
 956                                                 for (u16 t = 0; t < vert->tris.size(); t++)
 957                                                 {
 958                                                         if (highest == vert->tris[t])
 959                                                         {
 960                                                                 vert->tris.erase(t);
 961                                                                 break;
 962                                                         }
 963                                                 }
 964                                         }
 965
 966                                         lru.add(tc[highest].ind[0]);
 967                                         lru.add(tc[highest].ind[1]);
 968                                         highest = lru.add(tc[highest].ind[2]);
 969                                         drawcalls++;
 970                                 }
 971
 972                                 buf->setBoundingBox(mb->getBoundingBox());
 973                                 newmesh->addMeshBuffer(buf);
 974                                 buf->drop();
 975
 976                         }
 977                         break;
 978                         case video::EVT_TANGENTS:
 979                         {
 980                                 video::S3DVertexTangents *v = (video::S3DVertexTangents *) mb->getVertices();
 981
 982                                 scene::SMeshBufferTangents *buf = new scene::SMeshBufferTangents();
 983                                 buf->Material = mb->getMaterial();
 984
 985                                 buf->Vertices.reallocate(vcount);
 986                                 buf->Indices.reallocate(icount);
 987
 988                                 core::map<const video::S3DVertexTangents, const u16> sind; // search index for fast operation
 989                                 typedef core::map<const video::S3DVertexTangents, const u16>::Node snode;
 990
 991                                 // Main algorithm
 992                                 u32 highest = 0;
 993                                 u32 drawcalls = 0;
 994                                 for (;;)
 995                                 {
 996                                         if (tc[highest].drawn)
 997                                         {
 998                                                 bool found = false;
 999                                                 float hiscore = 0;
1000                                                 for (u32 t = 0; t < tcount; t++)
1001                                                 {
1002                                                         if (!tc[t].drawn)
1003                                                         {
1004                                                                 if (tc[t].score > hiscore)
1005                                                                 {
1006                                                                         highest = t;
1007                                                                         hiscore = tc[t].score;
1008                                                                         found = true;
1009                                                                 }
1010                                                         }
1011                                                 }
1012                                                 if (!found)
1013                                                         break;
1014                                         }
1015
1016                                         // Output the best triangle
1017                                         u16 newind = buf->Vertices.size();
1018
1019                                         snode *s = sind.find(v[tc[highest].ind[0]]);
1020
1021                                         if (!s)
1022                                         {
1023                                                 buf->Vertices.push_back(v[tc[highest].ind[0]]);
1024                                                 buf->Indices.push_back(newind);
1025                                                 sind.insert(v[tc[highest].ind[0]], newind);
1026                                                 newind++;
1027                                         }
1028                                         else
1029                                         {
1030                                                 buf->Indices.push_back(s->getValue());
1031                                         }
1032
1033                                         s = sind.find(v[tc[highest].ind[1]]);
1034
1035                                         if (!s)
1036                                         {
1037                                                 buf->Vertices.push_back(v[tc[highest].ind[1]]);
1038                                                 buf->Indices.push_back(newind);
1039                                                 sind.insert(v[tc[highest].ind[1]], newind);
1040                                                 newind++;
1041                                         }
1042                                         else
1043                                         {
1044                                                 buf->Indices.push_back(s->getValue());
1045                                         }
1046
1047                                         s = sind.find(v[tc[highest].ind[2]]);
1048
1049                                         if (!s)
1050                                         {
1051                                                 buf->Vertices.push_back(v[tc[highest].ind[2]]);
1052                                                 buf->Indices.push_back(newind);
1053                                                 sind.insert(v[tc[highest].ind[2]], newind);
1054                                         }
1055                                         else
1056                                         {
1057                                                 buf->Indices.push_back(s->getValue());
1058                                         }
1059
1060                                         vc[tc[highest].ind[0]].NumActiveTris--;
1061                                         vc[tc[highest].ind[1]].NumActiveTris--;
1062                                         vc[tc[highest].ind[2]].NumActiveTris--;
1063
1064                                         tc[highest].drawn = true;
1065
1066                                         for (u16 j : tc[highest].ind) {
1067                                                 vcache *vert = &vc[j];
1068                                                 for (u16 t = 0; t < vert->tris.size(); t++)
1069                                                 {
1070                                                         if (highest == vert->tris[t])
1071                                                         {
1072                                                                 vert->tris.erase(t);
1073                                                                 break;
1074                                                         }
1075                                                 }
1076                                         }
1077
1078                                         lru.add(tc[highest].ind[0]);
1079                                         lru.add(tc[highest].ind[1]);
1080                                         highest = lru.add(tc[highest].ind[2]);
1081                                         drawcalls++;
1082                                 }
1083
1084                                 buf->setBoundingBox(mb->getBoundingBox());
1085                                 newmesh->addMeshBuffer(buf);
1086                                 buf->drop();
1087                         }
1088                         break;
1089                 }
1090
1091                 delete [] vc;
1092                 delete [] tc;
1093
1094         } // for each meshbuffer
1095
1096         return newmesh;
1097 }