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