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