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