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 template <typename F>
 207 static void applyToMesh(scene::IMesh *mesh, const F &fn)
 208 {
 209         u16 mc = mesh->getMeshBufferCount();
 210         for (u16 j = 0; j < mc; j++) {
 211                 scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
 212                 const u32 stride = getVertexPitchFromType(buf->getVertexType());
 213                 u32 vertex_count = buf->getVertexCount();
 214                 char *vertices = reinterpret_cast<char *>(buf->getVertices());
 215                 for (u32 i = 0; i < vertex_count; i++)
 216                         fn(reinterpret_cast<video::S3DVertex *>(vertices + i * stride));
 217         }
 218 }
 219
 220 void colorizeMeshBuffer(scene::IMeshBuffer *buf, const video::SColor *buffercolor)
 221 {
 222         const u32 stride = getVertexPitchFromType(buf->getVertexType());
 223         u32 vertex_count = buf->getVertexCount();
 224         u8 *vertices = (u8 *) buf->getVertices();
 225         for (u32 i = 0; i < vertex_count; i++) {
 226                 video::S3DVertex *vertex = (video::S3DVertex *) (vertices + i * stride);
 227                 video::SColor *vc = &(vertex->Color);
 228                 // Reset color
 229                 *vc = *buffercolor;
 230                 // Apply shading
 231                 applyFacesShading(*vc, vertex->Normal);
 232         }
 233 }
 234
 235 void setMeshColorByNormalXYZ(scene::IMesh *mesh,
 236                 const video::SColor &colorX,
 237                 const video::SColor &colorY,
 238                 const video::SColor &colorZ)
 239 {
 240         if (!mesh)
 241                 return;
 242         auto colorizator = [=] (video::S3DVertex *vertex) {
 243                 f32 x = fabs(vertex->Normal.X);
 244                 f32 y = fabs(vertex->Normal.Y);
 245                 f32 z = fabs(vertex->Normal.Z);
 246                 if (x >= y && x >= z)
 247                         vertex->Color = colorX;
 248                 else if (y >= z)
 249                         vertex->Color = colorY;
 250                 else
 251                         vertex->Color = colorZ;
 252         };
 253         applyToMesh(mesh, colorizator);
 254 }
 255
 256 void setMeshColorByNormal(scene::IMesh *mesh, const v3f &normal,
 257                 const video::SColor &color)
 258 {
 259         if (!mesh)
 260                 return;
 261         auto colorizator = [normal, color] (video::S3DVertex *vertex) {
 262                 if (vertex->Normal == normal)
 263                         vertex->Color = color;
 264         };
 265         applyToMesh(mesh, colorizator);
 266 }
 267
 268 template <float v3f::*U, float v3f::*V>
 269 static void rotateMesh(scene::IMesh *mesh, float degrees)
 270 {
 271         degrees *= M_PI / 180.0f;
 272         float c = std::cos(degrees);
 273         float s = std::sin(degrees);
 274         auto rotator = [c, s] (video::S3DVertex *vertex) {
 275                 float u = vertex->Pos.*U;
 276                 float v = vertex->Pos.*V;
 277                 vertex->Pos.*U = c * u - s * v;
 278                 vertex->Pos.*V = s * u + c * v;
 279         };
 280         applyToMesh(mesh, rotator);
 281 }
 282
 283 void rotateMeshXYby(scene::IMesh *mesh, f64 degrees)
 284 {
 285         rotateMesh<&v3f::X, &v3f::Y>(mesh, degrees);
 286 }
 287
 288 void rotateMeshXZby(scene::IMesh *mesh, f64 degrees)
 289 {
 290         rotateMesh<&v3f::X, &v3f::Z>(mesh, degrees);
 291 }
 292
 293 void rotateMeshYZby(scene::IMesh *mesh, f64 degrees)
 294 {
 295         rotateMesh<&v3f::Y, &v3f::Z>(mesh, degrees);
 296 }
 297
 298 void rotateMeshBy6dFacedir(scene::IMesh *mesh, int facedir)
 299 {
 300         int axisdir = facedir >> 2;
 301         facedir &= 0x03;
 302         switch (facedir) {
 303                 case 1: rotateMeshXZby(mesh, -90); break;
 304                 case 2: rotateMeshXZby(mesh, 180); break;
 305                 case 3: rotateMeshXZby(mesh, 90); break;
 306         }
 307         switch (axisdir) {
 308                 case 1: rotateMeshYZby(mesh, 90); break; // z+
 309                 case 2: rotateMeshYZby(mesh, -90); break; // z-
 310                 case 3: rotateMeshXYby(mesh, -90); break; // x+
 311                 case 4: rotateMeshXYby(mesh, 90); break; // x-
 312                 case 5: rotateMeshXYby(mesh, -180); break;
 313         }
 314 }
 315
 316 void recalculateBoundingBox(scene::IMesh *src_mesh)
 317 {
 318         aabb3f bbox;
 319         bbox.reset(0,0,0);
 320         for (u16 j = 0; j < src_mesh->getMeshBufferCount(); j++) {
 321                 scene::IMeshBuffer *buf = src_mesh->getMeshBuffer(j);
 322                 buf->recalculateBoundingBox();
 323                 if (j == 0)
 324                         bbox = buf->getBoundingBox();
 325                 else
 326                         bbox.addInternalBox(buf->getBoundingBox());
 327         }
 328         src_mesh->setBoundingBox(bbox);
 329 }
 330
 331 scene::IMeshBuffer* cloneMeshBuffer(scene::IMeshBuffer *mesh_buffer)
 332 {
 333         switch (mesh_buffer->getVertexType()) {
 334         case video::EVT_STANDARD: {
 335                 video::S3DVertex *v = (video::S3DVertex *) mesh_buffer->getVertices();
 336                 u16 *indices = mesh_buffer->getIndices();
 337                 scene::SMeshBuffer *cloned_buffer = new scene::SMeshBuffer();
 338                 cloned_buffer->append(v, mesh_buffer->getVertexCount(), indices,
 339                         mesh_buffer->getIndexCount());
 340                 return cloned_buffer;
 341         }
 342         case video::EVT_2TCOORDS: {
 343                 video::S3DVertex2TCoords *v =
 344                         (video::S3DVertex2TCoords *) mesh_buffer->getVertices();
 345                 u16 *indices = mesh_buffer->getIndices();
 346                 scene::SMeshBufferLightMap *cloned_buffer =
 347                         new scene::SMeshBufferLightMap();
 348                 cloned_buffer->append(v, mesh_buffer->getVertexCount(), indices,
 349                         mesh_buffer->getIndexCount());
 350                 return cloned_buffer;
 351         }
 352         case video::EVT_TANGENTS: {
 353                 video::S3DVertexTangents *v =
 354                         (video::S3DVertexTangents *) mesh_buffer->getVertices();
 355                 u16 *indices = mesh_buffer->getIndices();
 356                 scene::SMeshBufferTangents *cloned_buffer =
 357                         new scene::SMeshBufferTangents();
 358                 cloned_buffer->append(v, mesh_buffer->getVertexCount(), indices,
 359                         mesh_buffer->getIndexCount());
 360                 return cloned_buffer;
 361         }
 362         }
 363         // This should not happen.
 364         sanity_check(false);
 365         return NULL;
 366 }
 367
 368 scene::SMesh* cloneMesh(scene::IMesh *src_mesh)
 369 {
 370         scene::SMesh* dst_mesh = new scene::SMesh();
 371         for (u16 j = 0; j < src_mesh->getMeshBufferCount(); j++) {
 372                 scene::IMeshBuffer *temp_buf = cloneMeshBuffer(
 373                         src_mesh->getMeshBuffer(j));
 374                 dst_mesh->addMeshBuffer(temp_buf);
 375                 temp_buf->drop();
 376
 377         }
 378         return dst_mesh;
 379 }
 380
 381 scene::IMesh* convertNodeboxesToMesh(const std::vector<aabb3f> &boxes,
 382                 const f32 *uv_coords, float expand)
 383 {
 384         scene::SMesh* dst_mesh = new scene::SMesh();
 385
 386         for (u16 j = 0; j < 6; j++)
 387         {
 388                 scene::IMeshBuffer *buf = new scene::SMeshBuffer();
 389                 buf->getMaterial().setFlag(video::EMF_LIGHTING, false);
 390                 buf->getMaterial().setFlag(video::EMF_BILINEAR_FILTER, false);
 391                 dst_mesh->addMeshBuffer(buf);
 392                 buf->drop();
 393         }
 394
 395         video::SColor c(255,255,255,255);
 396
 397         for (aabb3f box : boxes) {
 398                 box.repair();
 399
 400                 box.MinEdge.X -= expand;
 401                 box.MinEdge.Y -= expand;
 402                 box.MinEdge.Z -= expand;
 403                 box.MaxEdge.X += expand;
 404                 box.MaxEdge.Y += expand;
 405                 box.MaxEdge.Z += expand;
 406
 407                 // Compute texture UV coords
 408                 f32 tx1 = (box.MinEdge.X / BS) + 0.5;
 409                 f32 ty1 = (box.MinEdge.Y / BS) + 0.5;
 410                 f32 tz1 = (box.MinEdge.Z / BS) + 0.5;
 411                 f32 tx2 = (box.MaxEdge.X / BS) + 0.5;
 412                 f32 ty2 = (box.MaxEdge.Y / BS) + 0.5;
 413                 f32 tz2 = (box.MaxEdge.Z / BS) + 0.5;
 414
 415                 f32 txc_default[24] = {
 416                         // up
 417                         tx1, 1 - tz2, tx2, 1 - tz1,
 418                         // down
 419                         tx1, tz1, tx2, tz2,
 420                         // right
 421                         tz1, 1 - ty2, tz2, 1 - ty1,
 422                         // left
 423                         1 - tz2, 1 - ty2, 1 - tz1, 1 - ty1,
 424                         // back
 425                         1 - tx2, 1 - ty2, 1 - tx1, 1 - ty1,
 426                         // front
 427                         tx1, 1 - ty2, tx2, 1 - ty1,
 428                 };
 429
 430                 // use default texture UV mapping if not provided
 431                 const f32 *txc = uv_coords ? uv_coords : txc_default;
 432
 433                 v3f min = box.MinEdge;
 434                 v3f max = box.MaxEdge;
 435
 436                 video::S3DVertex vertices[24] =
 437                 {
 438                         // up
 439                         video::S3DVertex(min.X,max.Y,max.Z, 0,1,0, c, txc[0],txc[1]),
 440                         video::S3DVertex(max.X,max.Y,max.Z, 0,1,0, c, txc[2],txc[1]),
 441                         video::S3DVertex(max.X,max.Y,min.Z, 0,1,0, c, txc[2],txc[3]),
 442                         video::S3DVertex(min.X,max.Y,min.Z, 0,1,0, c, txc[0],txc[3]),
 443                         // down
 444                         video::S3DVertex(min.X,min.Y,min.Z, 0,-1,0, c, txc[4],txc[5]),
 445                         video::S3DVertex(max.X,min.Y,min.Z, 0,-1,0, c, txc[6],txc[5]),
 446                         video::S3DVertex(max.X,min.Y,max.Z, 0,-1,0, c, txc[6],txc[7]),
 447                         video::S3DVertex(min.X,min.Y,max.Z, 0,-1,0, c, txc[4],txc[7]),
 448                         // right
 449                         video::S3DVertex(max.X,max.Y,min.Z, 1,0,0, c, txc[ 8],txc[9]),
 450                         video::S3DVertex(max.X,max.Y,max.Z, 1,0,0, c, txc[10],txc[9]),
 451                         video::S3DVertex(max.X,min.Y,max.Z, 1,0,0, c, txc[10],txc[11]),
 452                         video::S3DVertex(max.X,min.Y,min.Z, 1,0,0, c, txc[ 8],txc[11]),
 453                         // left
 454                         video::S3DVertex(min.X,max.Y,max.Z, -1,0,0, c, txc[12],txc[13]),
 455                         video::S3DVertex(min.X,max.Y,min.Z, -1,0,0, c, txc[14],txc[13]),
 456                         video::S3DVertex(min.X,min.Y,min.Z, -1,0,0, c, txc[14],txc[15]),
 457                         video::S3DVertex(min.X,min.Y,max.Z, -1,0,0, c, txc[12],txc[15]),
 458                         // back
 459                         video::S3DVertex(max.X,max.Y,max.Z, 0,0,1, c, txc[16],txc[17]),
 460                         video::S3DVertex(min.X,max.Y,max.Z, 0,0,1, c, txc[18],txc[17]),
 461                         video::S3DVertex(min.X,min.Y,max.Z, 0,0,1, c, txc[18],txc[19]),
 462                         video::S3DVertex(max.X,min.Y,max.Z, 0,0,1, c, txc[16],txc[19]),
 463                         // front
 464                         video::S3DVertex(min.X,max.Y,min.Z, 0,0,-1, c, txc[20],txc[21]),
 465                         video::S3DVertex(max.X,max.Y,min.Z, 0,0,-1, c, txc[22],txc[21]),
 466                         video::S3DVertex(max.X,min.Y,min.Z, 0,0,-1, c, txc[22],txc[23]),
 467                         video::S3DVertex(min.X,min.Y,min.Z, 0,0,-1, c, txc[20],txc[23]),
 468                 };
 469
 470                 u16 indices[] = {0,1,2,2,3,0};
 471
 472                 for(u16 j = 0; j < 24; j += 4)
 473                 {
 474                         scene::IMeshBuffer *buf = dst_mesh->getMeshBuffer(j / 4);
 475                         buf->append(vertices + j, 4, indices, 6);
 476                 }
 477         }
 478         return dst_mesh;
 479 }
 480
 481 struct vcache
 482 {
 483         core::array<u32> tris;
 484         float score;
 485         s16 cachepos;
 486         u16 NumActiveTris;
 487 };
 488
 489 struct tcache
 490 {
 491         u16 ind[3];
 492         float score;
 493         bool drawn;
 494 };
 495
 496 const u16 cachesize = 32;
 497
 498 float FindVertexScore(vcache *v)
 499 {
 500         const float CacheDecayPower = 1.5f;
 501         const float LastTriScore = 0.75f;
 502         const float ValenceBoostScale = 2.0f;
 503         const float ValenceBoostPower = 0.5f;
 504         const float MaxSizeVertexCache = 32.0f;
 505
 506         if (v->NumActiveTris == 0)
 507         {
 508                 // No tri needs this vertex!
 509                 return -1.0f;
 510         }
 511
 512         float Score = 0.0f;
 513         int CachePosition = v->cachepos;
 514         if (CachePosition < 0)
 515         {
 516                 // Vertex is not in FIFO cache - no score.
 517         }
 518         else
 519         {
 520                 if (CachePosition < 3)
 521                 {
 522                         // This vertex was used in the last triangle,
 523                         // so it has a fixed score.
 524                         Score = LastTriScore;
 525                 }
 526                 else
 527                 {
 528                         // Points for being high in the cache.
 529                         const float Scaler = 1.0f / (MaxSizeVertexCache - 3);
 530                         Score = 1.0f - (CachePosition - 3) * Scaler;
 531                         Score = powf(Score, CacheDecayPower);
 532                 }
 533         }
 534
 535         // Bonus points for having a low number of tris still to
 536         // use the vert, so we get rid of lone verts quickly.
 537         float ValenceBoost = powf(v->NumActiveTris,
 538                                 -ValenceBoostPower);
 539         Score += ValenceBoostScale * ValenceBoost;
 540
 541         return Score;
 542 }
 543
 544 /*
 545         A specialized LRU cache for the Forsyth algorithm.
 546 */
 547
 548 class f_lru
 549 {
 550
 551 public:
 552         f_lru(vcache *v, tcache *t): vc(v), tc(t)
 553         {
 554                 for (int &i : cache) {
 555                         i = -1;
 556                 }
 557         }
 558
 559         // Adds this vertex index and returns the highest-scoring triangle index
 560         u32 add(u16 vert, bool updatetris = false)
 561         {
 562                 bool found = false;
 563
 564                 // Mark existing pos as empty
 565                 for (u16 i = 0; i < cachesize; i++)
 566                 {
 567                         if (cache[i] == vert)
 568                         {
 569                                 // Move everything down
 570                                 for (u16 j = i; j; j--)
 571                                 {
 572                                         cache[j] = cache[j - 1];
 573                                 }
 574
 575                                 found = true;
 576                                 break;
 577                         }
 578                 }
 579
 580                 if (!found)
 581                 {
 582                         if (cache[cachesize-1] != -1)
 583                                 vc[cache[cachesize-1]].cachepos = -1;
 584
 585                         // Move everything down
 586                         for (u16 i = cachesize - 1; i; i--)
 587                         {
 588                                 cache[i] = cache[i - 1];
 589                         }
 590                 }
 591
 592                 cache[0] = vert;
 593
 594                 u32 highest = 0;
 595                 float hiscore = 0;
 596
 597                 if (updatetris)
 598                 {
 599                         // Update cache positions
 600                         for (u16 i = 0; i < cachesize; i++)
 601                         {
 602                                 if (cache[i] == -1)
 603                                         break;
 604
 605                                 vc[cache[i]].cachepos = i;
 606                                 vc[cache[i]].score = FindVertexScore(&vc[cache[i]]);
 607                         }
 608
 609                         // Update triangle scores
 610                         for (int i : cache) {
 611                                 if (i == -1)
 612                                         break;
 613
 614                                 const u16 trisize = vc[i].tris.size();
 615                                 for (u16 t = 0; t < trisize; t++)
 616                                 {
 617                                         tcache *tri = &tc[vc[i].tris[t]];
 618
 619                                         tri->score =
 620                                                 vc[tri->ind[0]].score +
 621                                                 vc[tri->ind[1]].score +
 622                                                 vc[tri->ind[2]].score;
 623
 624                                         if (tri->score > hiscore)
 625                                         {
 626                                                 hiscore = tri->score;
 627                                                 highest = vc[i].tris[t];
 628                                         }
 629                                 }
 630                         }
 631                 }
 632
 633                 return highest;
 634         }
 635
 636 private:
 637         s32 cache[cachesize];
 638         vcache *vc;
 639         tcache *tc;
 640 };
 641
 642 /**
 643 Vertex cache optimization according to the Forsyth paper:
 644 http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html
 645
 646 The function is thread-safe (read: you can optimize several meshes in different threads)
 647
 648 \param mesh Source mesh for the operation.  */
 649 scene::IMesh* createForsythOptimizedMesh(const scene::IMesh *mesh)
 650 {
 651         if (!mesh)
 652                 return 0;
 653
 654         scene::SMesh *newmesh = new scene::SMesh();
 655         newmesh->BoundingBox = mesh->getBoundingBox();
 656
 657         const u32 mbcount = mesh->getMeshBufferCount();
 658
 659         for (u32 b = 0; b < mbcount; ++b)
 660         {
 661                 const scene::IMeshBuffer *mb = mesh->getMeshBuffer(b);
 662
 663                 if (mb->getIndexType() != video::EIT_16BIT)
 664                 {
 665                         //os::Printer::log("Cannot optimize a mesh with 32bit indices", ELL_ERROR);
 666                         newmesh->drop();
 667                         return 0;
 668                 }
 669
 670                 const u32 icount = mb->getIndexCount();
 671                 const u32 tcount = icount / 3;
 672                 const u32 vcount = mb->getVertexCount();
 673                 const u16 *ind = mb->getIndices();
 674
 675                 vcache *vc = new vcache[vcount];
 676                 tcache *tc = new tcache[tcount];
 677
 678                 f_lru lru(vc, tc);
 679
 680                 // init
 681                 for (u16 i = 0; i < vcount; i++)
 682                 {
 683                         vc[i].score = 0;
 684                         vc[i].cachepos = -1;
 685                         vc[i].NumActiveTris = 0;
 686                 }
 687
 688                 // First pass: count how many times a vert is used
 689                 for (u32 i = 0; i < icount; i += 3)
 690                 {
 691                         vc[ind[i]].NumActiveTris++;
 692                         vc[ind[i + 1]].NumActiveTris++;
 693                         vc[ind[i + 2]].NumActiveTris++;
 694
 695                         const u32 tri_ind = i/3;
 696                         tc[tri_ind].ind[0] = ind[i];
 697                         tc[tri_ind].ind[1] = ind[i + 1];
 698                         tc[tri_ind].ind[2] = ind[i + 2];
 699                 }
 700
 701                 // Second pass: list of each triangle
 702                 for (u32 i = 0; i < tcount; i++)
 703                 {
 704                         vc[tc[i].ind[0]].tris.push_back(i);
 705                         vc[tc[i].ind[1]].tris.push_back(i);
 706                         vc[tc[i].ind[2]].tris.push_back(i);
 707
 708                         tc[i].drawn = false;
 709                 }
 710
 711                 // Give initial scores
 712                 for (u16 i = 0; i < vcount; i++)
 713                 {
 714                         vc[i].score = FindVertexScore(&vc[i]);
 715                 }
 716                 for (u32 i = 0; i < tcount; i++)
 717                 {
 718                         tc[i].score =
 719                                         vc[tc[i].ind[0]].score +
 720                                         vc[tc[i].ind[1]].score +
 721                                         vc[tc[i].ind[2]].score;
 722                 }
 723
 724                 switch(mb->getVertexType())
 725                 {
 726                         case video::EVT_STANDARD:
 727                         {
 728                                 video::S3DVertex *v = (video::S3DVertex *) mb->getVertices();
 729
 730                                 scene::SMeshBuffer *buf = new scene::SMeshBuffer();
 731                                 buf->Material = mb->getMaterial();
 732
 733                                 buf->Vertices.reallocate(vcount);
 734                                 buf->Indices.reallocate(icount);
 735
 736                                 core::map<const video::S3DVertex, const u16> sind; // search index for fast operation
 737                                 typedef core::map<const video::S3DVertex, const u16>::Node snode;
 738
 739                                 // Main algorithm
 740                                 u32 highest = 0;
 741                                 u32 drawcalls = 0;
 742                                 for (;;)
 743                                 {
 744                                         if (tc[highest].drawn)
 745                                         {
 746                                                 bool found = false;
 747                                                 float hiscore = 0;
 748                                                 for (u32 t = 0; t < tcount; t++)
 749                                                 {
 750                                                         if (!tc[t].drawn)
 751                                                         {
 752                                                                 if (tc[t].score > hiscore)
 753                                                                 {
 754                                                                         highest = t;
 755                                                                         hiscore = tc[t].score;
 756                                                                         found = true;
 757                                                                 }
 758                                                         }
 759                                                 }
 760                                                 if (!found)
 761                                                         break;
 762                                         }
 763
 764                                         // Output the best triangle
 765                                         u16 newind = buf->Vertices.size();
 766
 767                                         snode *s = sind.find(v[tc[highest].ind[0]]);
 768
 769                                         if (!s)
 770                                         {
 771                                                 buf->Vertices.push_back(v[tc[highest].ind[0]]);
 772                                                 buf->Indices.push_back(newind);
 773                                                 sind.insert(v[tc[highest].ind[0]], newind);
 774                                                 newind++;
 775                                         }
 776                                         else
 777                                         {
 778                                                 buf->Indices.push_back(s->getValue());
 779                                         }
 780
 781                                         s = sind.find(v[tc[highest].ind[1]]);
 782
 783                                         if (!s)
 784                                         {
 785                                                 buf->Vertices.push_back(v[tc[highest].ind[1]]);
 786                                                 buf->Indices.push_back(newind);
 787                                                 sind.insert(v[tc[highest].ind[1]], newind);
 788                                                 newind++;
 789                                         }
 790                                         else
 791                                         {
 792                                                 buf->Indices.push_back(s->getValue());
 793                                         }
 794
 795                                         s = sind.find(v[tc[highest].ind[2]]);
 796
 797                                         if (!s)
 798                                         {
 799                                                 buf->Vertices.push_back(v[tc[highest].ind[2]]);
 800                                                 buf->Indices.push_back(newind);
 801                                                 sind.insert(v[tc[highest].ind[2]], newind);
 802                                         }
 803                                         else
 804                                         {
 805                                                 buf->Indices.push_back(s->getValue());
 806                                         }
 807
 808                                         vc[tc[highest].ind[0]].NumActiveTris--;
 809                                         vc[tc[highest].ind[1]].NumActiveTris--;
 810                                         vc[tc[highest].ind[2]].NumActiveTris--;
 811
 812                                         tc[highest].drawn = true;
 813
 814                                         for (u16 j : tc[highest].ind) {
 815                                                 vcache *vert = &vc[j];
 816                                                 for (u16 t = 0; t < vert->tris.size(); t++)
 817                                                 {
 818                                                         if (highest == vert->tris[t])
 819                                                         {
 820                                                                 vert->tris.erase(t);
 821                                                                 break;
 822                                                         }
 823                                                 }
 824                                         }
 825
 826                                         lru.add(tc[highest].ind[0]);
 827                                         lru.add(tc[highest].ind[1]);
 828                                         highest = lru.add(tc[highest].ind[2], true);
 829                                         drawcalls++;
 830                                 }
 831
 832                                 buf->setBoundingBox(mb->getBoundingBox());
 833                                 newmesh->addMeshBuffer(buf);
 834                                 buf->drop();
 835                         }
 836                         break;
 837                         case video::EVT_2TCOORDS:
 838                         {
 839                                 video::S3DVertex2TCoords *v = (video::S3DVertex2TCoords *) mb->getVertices();
 840
 841                                 scene::SMeshBufferLightMap *buf = new scene::SMeshBufferLightMap();
 842                                 buf->Material = mb->getMaterial();
 843
 844                                 buf->Vertices.reallocate(vcount);
 845                                 buf->Indices.reallocate(icount);
 846
 847                                 core::map<const video::S3DVertex2TCoords, const u16> sind; // search index for fast operation
 848                                 typedef core::map<const video::S3DVertex2TCoords, const u16>::Node snode;
 849
 850                                 // Main algorithm
 851                                 u32 highest = 0;
 852                                 u32 drawcalls = 0;
 853                                 for (;;)
 854                                 {
 855                                         if (tc[highest].drawn)
 856                                         {
 857                                                 bool found = false;
 858                                                 float hiscore = 0;
 859                                                 for (u32 t = 0; t < tcount; t++)
 860                                                 {
 861                                                         if (!tc[t].drawn)
 862                                                         {
 863                                                                 if (tc[t].score > hiscore)
 864                                                                 {
 865                                                                         highest = t;
 866                                                                         hiscore = tc[t].score;
 867                                                                         found = true;
 868                                                                 }
 869                                                         }
 870                                                 }
 871                                                 if (!found)
 872                                                         break;
 873                                         }
 874
 875                                         // Output the best triangle
 876                                         u16 newind = buf->Vertices.size();
 877
 878                                         snode *s = sind.find(v[tc[highest].ind[0]]);
 879
 880                                         if (!s)
 881                                         {
 882                                                 buf->Vertices.push_back(v[tc[highest].ind[0]]);
 883                                                 buf->Indices.push_back(newind);
 884                                                 sind.insert(v[tc[highest].ind[0]], newind);
 885                                                 newind++;
 886                                         }
 887                                         else
 888                                         {
 889                                                 buf->Indices.push_back(s->getValue());
 890                                         }
 891
 892                                         s = sind.find(v[tc[highest].ind[1]]);
 893
 894                                         if (!s)
 895                                         {
 896                                                 buf->Vertices.push_back(v[tc[highest].ind[1]]);
 897                                                 buf->Indices.push_back(newind);
 898                                                 sind.insert(v[tc[highest].ind[1]], newind);
 899                                                 newind++;
 900                                         }
 901                                         else
 902                                         {
 903                                                 buf->Indices.push_back(s->getValue());
 904                                         }
 905
 906                                         s = sind.find(v[tc[highest].ind[2]]);
 907
 908                                         if (!s)
 909                                         {
 910                                                 buf->Vertices.push_back(v[tc[highest].ind[2]]);
 911                                                 buf->Indices.push_back(newind);
 912                                                 sind.insert(v[tc[highest].ind[2]], newind);
 913                                         }
 914                                         else
 915                                         {
 916                                                 buf->Indices.push_back(s->getValue());
 917                                         }
 918
 919                                         vc[tc[highest].ind[0]].NumActiveTris--;
 920                                         vc[tc[highest].ind[1]].NumActiveTris--;
 921                                         vc[tc[highest].ind[2]].NumActiveTris--;
 922
 923                                         tc[highest].drawn = true;
 924
 925                                         for (u16 j : tc[highest].ind) {
 926                                                 vcache *vert = &vc[j];
 927                                                 for (u16 t = 0; t < vert->tris.size(); t++)
 928                                                 {
 929                                                         if (highest == vert->tris[t])
 930                                                         {
 931                                                                 vert->tris.erase(t);
 932                                                                 break;
 933                                                         }
 934                                                 }
 935                                         }
 936
 937                                         lru.add(tc[highest].ind[0]);
 938                                         lru.add(tc[highest].ind[1]);
 939                                         highest = lru.add(tc[highest].ind[2]);
 940                                         drawcalls++;
 941                                 }
 942
 943                                 buf->setBoundingBox(mb->getBoundingBox());
 944                                 newmesh->addMeshBuffer(buf);
 945                                 buf->drop();
 946
 947                         }
 948                         break;
 949                         case video::EVT_TANGENTS:
 950                         {
 951                                 video::S3DVertexTangents *v = (video::S3DVertexTangents *) mb->getVertices();
 952
 953                                 scene::SMeshBufferTangents *buf = new scene::SMeshBufferTangents();
 954                                 buf->Material = mb->getMaterial();
 955
 956                                 buf->Vertices.reallocate(vcount);
 957                                 buf->Indices.reallocate(icount);
 958
 959                                 core::map<const video::S3DVertexTangents, const u16> sind; // search index for fast operation
 960                                 typedef core::map<const video::S3DVertexTangents, const u16>::Node snode;
 961
 962                                 // Main algorithm
 963                                 u32 highest = 0;
 964                                 u32 drawcalls = 0;
 965                                 for (;;)
 966                                 {
 967                                         if (tc[highest].drawn)
 968                                         {
 969                                                 bool found = false;
 970                                                 float hiscore = 0;
 971                                                 for (u32 t = 0; t < tcount; t++)
 972                                                 {
 973                                                         if (!tc[t].drawn)
 974                                                         {
 975                                                                 if (tc[t].score > hiscore)
 976                                                                 {
 977                                                                         highest = t;
 978                                                                         hiscore = tc[t].score;
 979                                                                         found = true;
 980                                                                 }
 981                                                         }
 982                                                 }
 983                                                 if (!found)
 984                                                         break;
 985                                         }
 986
 987                                         // Output the best triangle
 988                                         u16 newind = buf->Vertices.size();
 989
 990                                         snode *s = sind.find(v[tc[highest].ind[0]]);
 991
 992                                         if (!s)
 993                                         {
 994                                                 buf->Vertices.push_back(v[tc[highest].ind[0]]);
 995                                                 buf->Indices.push_back(newind);
 996                                                 sind.insert(v[tc[highest].ind[0]], newind);
 997                                                 newind++;
 998                                         }
 999                                         else
1000                                         {
1001                                                 buf->Indices.push_back(s->getValue());
1002                                         }
1003
1004                                         s = sind.find(v[tc[highest].ind[1]]);
1005
1006                                         if (!s)
1007                                         {
1008                                                 buf->Vertices.push_back(v[tc[highest].ind[1]]);
1009                                                 buf->Indices.push_back(newind);
1010                                                 sind.insert(v[tc[highest].ind[1]], newind);
1011                                                 newind++;
1012                                         }
1013                                         else
1014                                         {
1015                                                 buf->Indices.push_back(s->getValue());
1016                                         }
1017
1018                                         s = sind.find(v[tc[highest].ind[2]]);
1019
1020                                         if (!s)
1021                                         {
1022                                                 buf->Vertices.push_back(v[tc[highest].ind[2]]);
1023                                                 buf->Indices.push_back(newind);
1024                                                 sind.insert(v[tc[highest].ind[2]], newind);
1025                                         }
1026                                         else
1027                                         {
1028                                                 buf->Indices.push_back(s->getValue());
1029                                         }
1030
1031                                         vc[tc[highest].ind[0]].NumActiveTris--;
1032                                         vc[tc[highest].ind[1]].NumActiveTris--;
1033                                         vc[tc[highest].ind[2]].NumActiveTris--;
1034
1035                                         tc[highest].drawn = true;
1036
1037                                         for (u16 j : tc[highest].ind) {
1038                                                 vcache *vert = &vc[j];
1039                                                 for (u16 t = 0; t < vert->tris.size(); t++)
1040                                                 {
1041                                                         if (highest == vert->tris[t])
1042                                                         {
1043                                                                 vert->tris.erase(t);
1044                                                                 break;
1045                                                         }
1046                                                 }
1047                                         }
1048
1049                                         lru.add(tc[highest].ind[0]);
1050                                         lru.add(tc[highest].ind[1]);
1051                                         highest = lru.add(tc[highest].ind[2]);
1052                                         drawcalls++;
1053                                 }
1054
1055                                 buf->setBoundingBox(mb->getBoundingBox());
1056                                 newmesh->addMeshBuffer(buf);
1057                                 buf->drop();
1058                         }
1059                         break;
1060                 }
1061
1062                 delete [] vc;
1063                 delete [] tc;
1064
1065         } // for each meshbuffer
1066
1067         return newmesh;
1068 }