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