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 (std::vector<aabb3f>::const_iterator
 457                         i = boxes.begin();
 458                         i != boxes.end(); ++i)
 459         {
 460                 aabb3f box = *i;
 461                 box.repair();
 462
 463                 box.MinEdge.X -= expand;
 464                 box.MinEdge.Y -= expand;
 465                 box.MinEdge.Z -= expand;
 466                 box.MaxEdge.X += expand;
 467                 box.MaxEdge.Y += expand;
 468                 box.MaxEdge.Z += expand;
 469
 470                 // Compute texture UV coords
 471                 f32 tx1 = (box.MinEdge.X / BS) + 0.5;
 472                 f32 ty1 = (box.MinEdge.Y / BS) + 0.5;
 473                 f32 tz1 = (box.MinEdge.Z / BS) + 0.5;
 474                 f32 tx2 = (box.MaxEdge.X / BS) + 0.5;
 475                 f32 ty2 = (box.MaxEdge.Y / BS) + 0.5;
 476                 f32 tz2 = (box.MaxEdge.Z / BS) + 0.5;
 477
 478                 f32 txc_default[24] = {
 479                         // up
 480                         tx1, 1 - tz2, tx2, 1 - tz1,
 481                         // down
 482                         tx1, tz1, tx2, tz2,
 483                         // right
 484                         tz1, 1 - ty2, tz2, 1 - ty1,
 485                         // left
 486                         1 - tz2, 1 - ty2, 1 - tz1, 1 - ty1,
 487                         // back
 488                         1 - tx2, 1 - ty2, 1 - tx1, 1 - ty1,
 489                         // front
 490                         tx1, 1 - ty2, tx2, 1 - ty1,
 491                 };
 492
 493                 // use default texture UV mapping if not provided
 494                 const f32 *txc = uv_coords ? uv_coords : txc_default;
 495
 496                 v3f min = box.MinEdge;
 497                 v3f max = box.MaxEdge;
 498
 499                 video::S3DVertex vertices[24] =
 500                 {
 501                         // up
 502                         video::S3DVertex(min.X,max.Y,max.Z, 0,1,0, c, txc[0],txc[1]),
 503                         video::S3DVertex(max.X,max.Y,max.Z, 0,1,0, c, txc[2],txc[1]),
 504                         video::S3DVertex(max.X,max.Y,min.Z, 0,1,0, c, txc[2],txc[3]),
 505                         video::S3DVertex(min.X,max.Y,min.Z, 0,1,0, c, txc[0],txc[3]),
 506                         // down
 507                         video::S3DVertex(min.X,min.Y,min.Z, 0,-1,0, c, txc[4],txc[5]),
 508                         video::S3DVertex(max.X,min.Y,min.Z, 0,-1,0, c, txc[6],txc[5]),
 509                         video::S3DVertex(max.X,min.Y,max.Z, 0,-1,0, c, txc[6],txc[7]),
 510                         video::S3DVertex(min.X,min.Y,max.Z, 0,-1,0, c, txc[4],txc[7]),
 511                         // right
 512                         video::S3DVertex(max.X,max.Y,min.Z, 1,0,0, c, txc[ 8],txc[9]),
 513                         video::S3DVertex(max.X,max.Y,max.Z, 1,0,0, c, txc[10],txc[9]),
 514                         video::S3DVertex(max.X,min.Y,max.Z, 1,0,0, c, txc[10],txc[11]),
 515                         video::S3DVertex(max.X,min.Y,min.Z, 1,0,0, c, txc[ 8],txc[11]),
 516                         // left
 517                         video::S3DVertex(min.X,max.Y,max.Z, -1,0,0, c, txc[12],txc[13]),
 518                         video::S3DVertex(min.X,max.Y,min.Z, -1,0,0, c, txc[14],txc[13]),
 519                         video::S3DVertex(min.X,min.Y,min.Z, -1,0,0, c, txc[14],txc[15]),
 520                         video::S3DVertex(min.X,min.Y,max.Z, -1,0,0, c, txc[12],txc[15]),
 521                         // back
 522                         video::S3DVertex(max.X,max.Y,max.Z, 0,0,1, c, txc[16],txc[17]),
 523                         video::S3DVertex(min.X,max.Y,max.Z, 0,0,1, c, txc[18],txc[17]),
 524                         video::S3DVertex(min.X,min.Y,max.Z, 0,0,1, c, txc[18],txc[19]),
 525                         video::S3DVertex(max.X,min.Y,max.Z, 0,0,1, c, txc[16],txc[19]),
 526                         // front
 527                         video::S3DVertex(min.X,max.Y,min.Z, 0,0,-1, c, txc[20],txc[21]),
 528                         video::S3DVertex(max.X,max.Y,min.Z, 0,0,-1, c, txc[22],txc[21]),
 529                         video::S3DVertex(max.X,min.Y,min.Z, 0,0,-1, c, txc[22],txc[23]),
 530                         video::S3DVertex(min.X,min.Y,min.Z, 0,0,-1, c, txc[20],txc[23]),
 531                 };
 532
 533                 u16 indices[] = {0,1,2,2,3,0};
 534
 535                 for(u16 j = 0; j < 24; j += 4)
 536                 {
 537                         scene::IMeshBuffer *buf = dst_mesh->getMeshBuffer(j / 4);
 538                         buf->append(vertices + j, 4, indices, 6);
 539                 }
 540         }
 541         return dst_mesh;
 542 }
 543
 544 struct vcache
 545 {
 546         core::array<u32> tris;
 547         float score;
 548         s16 cachepos;
 549         u16 NumActiveTris;
 550 };
 551
 552 struct tcache
 553 {
 554         u16 ind[3];
 555         float score;
 556         bool drawn;
 557 };
 558
 559 const u16 cachesize = 32;
 560
 561 float FindVertexScore(vcache *v)
 562 {
 563         const float CacheDecayPower = 1.5f;
 564         const float LastTriScore = 0.75f;
 565         const float ValenceBoostScale = 2.0f;
 566         const float ValenceBoostPower = 0.5f;
 567         const float MaxSizeVertexCache = 32.0f;
 568
 569         if (v->NumActiveTris == 0)
 570         {
 571                 // No tri needs this vertex!
 572                 return -1.0f;
 573         }
 574
 575         float Score = 0.0f;
 576         int CachePosition = v->cachepos;
 577         if (CachePosition < 0)
 578         {
 579                 // Vertex is not in FIFO cache - no score.
 580         }
 581         else
 582         {
 583                 if (CachePosition < 3)
 584                 {
 585                         // This vertex was used in the last triangle,
 586                         // so it has a fixed score.
 587                         Score = LastTriScore;
 588                 }
 589                 else
 590                 {
 591                         // Points for being high in the cache.
 592                         const float Scaler = 1.0f / (MaxSizeVertexCache - 3);
 593                         Score = 1.0f - (CachePosition - 3) * Scaler;
 594                         Score = powf(Score, CacheDecayPower);
 595                 }
 596         }
 597
 598         // Bonus points for having a low number of tris still to
 599         // use the vert, so we get rid of lone verts quickly.
 600         float ValenceBoost = powf(v->NumActiveTris,
 601                                 -ValenceBoostPower);
 602         Score += ValenceBoostScale * ValenceBoost;
 603
 604         return Score;
 605 }
 606
 607 /*
 608         A specialized LRU cache for the Forsyth algorithm.
 609 */
 610
 611 class f_lru
 612 {
 613
 614 public:
 615         f_lru(vcache *v, tcache *t): vc(v), tc(t)
 616         {
 617                 for (u16 i = 0; i < cachesize; i++)
 618                 {
 619                         cache[i] = -1;
 620                 }
 621         }
 622
 623         // Adds this vertex index and returns the highest-scoring triangle index
 624         u32 add(u16 vert, bool updatetris = false)
 625         {
 626                 bool found = false;
 627
 628                 // Mark existing pos as empty
 629                 for (u16 i = 0; i < cachesize; i++)
 630                 {
 631                         if (cache[i] == vert)
 632                         {
 633                                 // Move everything down
 634                                 for (u16 j = i; j; j--)
 635                                 {
 636                                         cache[j] = cache[j - 1];
 637                                 }
 638
 639                                 found = true;
 640                                 break;
 641                         }
 642                 }
 643
 644                 if (!found)
 645                 {
 646                         if (cache[cachesize-1] != -1)
 647                                 vc[cache[cachesize-1]].cachepos = -1;
 648
 649                         // Move everything down
 650                         for (u16 i = cachesize - 1; i; i--)
 651                         {
 652                                 cache[i] = cache[i - 1];
 653                         }
 654                 }
 655
 656                 cache[0] = vert;
 657
 658                 u32 highest = 0;
 659                 float hiscore = 0;
 660
 661                 if (updatetris)
 662                 {
 663                         // Update cache positions
 664                         for (u16 i = 0; i < cachesize; i++)
 665                         {
 666                                 if (cache[i] == -1)
 667                                         break;
 668
 669                                 vc[cache[i]].cachepos = i;
 670                                 vc[cache[i]].score = FindVertexScore(&vc[cache[i]]);
 671                         }
 672
 673                         // Update triangle scores
 674                         for (u16 i = 0; i < cachesize; i++)
 675                         {
 676                                 if (cache[i] == -1)
 677                                         break;
 678
 679                                 const u16 trisize = vc[cache[i]].tris.size();
 680                                 for (u16 t = 0; t < trisize; t++)
 681                                 {
 682                                         tcache *tri = &tc[vc[cache[i]].tris[t]];
 683
 684                                         tri->score =
 685                                                 vc[tri->ind[0]].score +
 686                                                 vc[tri->ind[1]].score +
 687                                                 vc[tri->ind[2]].score;
 688
 689                                         if (tri->score > hiscore)
 690                                         {
 691                                                 hiscore = tri->score;
 692                                                 highest = vc[cache[i]].tris[t];
 693                                         }
 694                                 }
 695                         }
 696                 }
 697
 698                 return highest;
 699         }
 700
 701 private:
 702         s32 cache[cachesize];
 703         vcache *vc;
 704         tcache *tc;
 705 };
 706
 707 /**
 708 Vertex cache optimization according to the Forsyth paper:
 709 http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html
 710
 711 The function is thread-safe (read: you can optimize several meshes in different threads)
 712
 713 \param mesh Source mesh for the operation.  */
 714 scene::IMesh* createForsythOptimizedMesh(const scene::IMesh *mesh)
 715 {
 716         if (!mesh)
 717                 return 0;
 718
 719         scene::SMesh *newmesh = new scene::SMesh();
 720         newmesh->BoundingBox = mesh->getBoundingBox();
 721
 722         const u32 mbcount = mesh->getMeshBufferCount();
 723
 724         for (u32 b = 0; b < mbcount; ++b)
 725         {
 726                 const scene::IMeshBuffer *mb = mesh->getMeshBuffer(b);
 727
 728                 if (mb->getIndexType() != video::EIT_16BIT)
 729                 {
 730                         //os::Printer::log("Cannot optimize a mesh with 32bit indices", ELL_ERROR);
 731                         newmesh->drop();
 732                         return 0;
 733                 }
 734
 735                 const u32 icount = mb->getIndexCount();
 736                 const u32 tcount = icount / 3;
 737                 const u32 vcount = mb->getVertexCount();
 738                 const u16 *ind = mb->getIndices();
 739
 740                 vcache *vc = new vcache[vcount];
 741                 tcache *tc = new tcache[tcount];
 742
 743                 f_lru lru(vc, tc);
 744
 745                 // init
 746                 for (u16 i = 0; i < vcount; i++)
 747                 {
 748                         vc[i].score = 0;
 749                         vc[i].cachepos = -1;
 750                         vc[i].NumActiveTris = 0;
 751                 }
 752
 753                 // First pass: count how many times a vert is used
 754                 for (u32 i = 0; i < icount; i += 3)
 755                 {
 756                         vc[ind[i]].NumActiveTris++;
 757                         vc[ind[i + 1]].NumActiveTris++;
 758                         vc[ind[i + 2]].NumActiveTris++;
 759
 760                         const u32 tri_ind = i/3;
 761                         tc[tri_ind].ind[0] = ind[i];
 762                         tc[tri_ind].ind[1] = ind[i + 1];
 763                         tc[tri_ind].ind[2] = ind[i + 2];
 764                 }
 765
 766                 // Second pass: list of each triangle
 767                 for (u32 i = 0; i < tcount; i++)
 768                 {
 769                         vc[tc[i].ind[0]].tris.push_back(i);
 770                         vc[tc[i].ind[1]].tris.push_back(i);
 771                         vc[tc[i].ind[2]].tris.push_back(i);
 772
 773                         tc[i].drawn = false;
 774                 }
 775
 776                 // Give initial scores
 777                 for (u16 i = 0; i < vcount; i++)
 778                 {
 779                         vc[i].score = FindVertexScore(&vc[i]);
 780                 }
 781                 for (u32 i = 0; i < tcount; i++)
 782                 {
 783                         tc[i].score =
 784                                         vc[tc[i].ind[0]].score +
 785                                         vc[tc[i].ind[1]].score +
 786                                         vc[tc[i].ind[2]].score;
 787                 }
 788
 789                 switch(mb->getVertexType())
 790                 {
 791                         case video::EVT_STANDARD:
 792                         {
 793                                 video::S3DVertex *v = (video::S3DVertex *) mb->getVertices();
 794
 795                                 scene::SMeshBuffer *buf = new scene::SMeshBuffer();
 796                                 buf->Material = mb->getMaterial();
 797
 798                                 buf->Vertices.reallocate(vcount);
 799                                 buf->Indices.reallocate(icount);
 800
 801                                 core::map<const video::S3DVertex, const u16> sind; // search index for fast operation
 802                                 typedef core::map<const video::S3DVertex, const u16>::Node snode;
 803
 804                                 // Main algorithm
 805                                 u32 highest = 0;
 806                                 u32 drawcalls = 0;
 807                                 for (;;)
 808                                 {
 809                                         if (tc[highest].drawn)
 810                                         {
 811                                                 bool found = false;
 812                                                 float hiscore = 0;
 813                                                 for (u32 t = 0; t < tcount; t++)
 814                                                 {
 815                                                         if (!tc[t].drawn)
 816                                                         {
 817                                                                 if (tc[t].score > hiscore)
 818                                                                 {
 819                                                                         highest = t;
 820                                                                         hiscore = tc[t].score;
 821                                                                         found = true;
 822                                                                 }
 823                                                         }
 824                                                 }
 825                                                 if (!found)
 826                                                         break;
 827                                         }
 828
 829                                         // Output the best triangle
 830                                         u16 newind = buf->Vertices.size();
 831
 832                                         snode *s = sind.find(v[tc[highest].ind[0]]);
 833
 834                                         if (!s)
 835                                         {
 836                                                 buf->Vertices.push_back(v[tc[highest].ind[0]]);
 837                                                 buf->Indices.push_back(newind);
 838                                                 sind.insert(v[tc[highest].ind[0]], newind);
 839                                                 newind++;
 840                                         }
 841                                         else
 842                                         {
 843                                                 buf->Indices.push_back(s->getValue());
 844                                         }
 845
 846                                         s = sind.find(v[tc[highest].ind[1]]);
 847
 848                                         if (!s)
 849                                         {
 850                                                 buf->Vertices.push_back(v[tc[highest].ind[1]]);
 851                                                 buf->Indices.push_back(newind);
 852                                                 sind.insert(v[tc[highest].ind[1]], newind);
 853                                                 newind++;
 854                                         }
 855                                         else
 856                                         {
 857                                                 buf->Indices.push_back(s->getValue());
 858                                         }
 859
 860                                         s = sind.find(v[tc[highest].ind[2]]);
 861
 862                                         if (!s)
 863                                         {
 864                                                 buf->Vertices.push_back(v[tc[highest].ind[2]]);
 865                                                 buf->Indices.push_back(newind);
 866                                                 sind.insert(v[tc[highest].ind[2]], newind);
 867                                         }
 868                                         else
 869                                         {
 870                                                 buf->Indices.push_back(s->getValue());
 871                                         }
 872
 873                                         vc[tc[highest].ind[0]].NumActiveTris--;
 874                                         vc[tc[highest].ind[1]].NumActiveTris--;
 875                                         vc[tc[highest].ind[2]].NumActiveTris--;
 876
 877                                         tc[highest].drawn = true;
 878
 879                                         for (u16 j = 0; j < 3; j++)
 880                                         {
 881                                                 vcache *vert = &vc[tc[highest].ind[j]];
 882                                                 for (u16 t = 0; t < vert->tris.size(); t++)
 883                                                 {
 884                                                         if (highest == vert->tris[t])
 885                                                         {
 886                                                                 vert->tris.erase(t);
 887                                                                 break;
 888                                                         }
 889                                                 }
 890                                         }
 891
 892                                         lru.add(tc[highest].ind[0]);
 893                                         lru.add(tc[highest].ind[1]);
 894                                         highest = lru.add(tc[highest].ind[2], true);
 895                                         drawcalls++;
 896                                 }
 897
 898                                 buf->setBoundingBox(mb->getBoundingBox());
 899                                 newmesh->addMeshBuffer(buf);
 900                                 buf->drop();
 901                         }
 902                         break;
 903                         case video::EVT_2TCOORDS:
 904                         {
 905                                 video::S3DVertex2TCoords *v = (video::S3DVertex2TCoords *) mb->getVertices();
 906
 907                                 scene::SMeshBufferLightMap *buf = new scene::SMeshBufferLightMap();
 908                                 buf->Material = mb->getMaterial();
 909
 910                                 buf->Vertices.reallocate(vcount);
 911                                 buf->Indices.reallocate(icount);
 912
 913                                 core::map<const video::S3DVertex2TCoords, const u16> sind; // search index for fast operation
 914                                 typedef core::map<const video::S3DVertex2TCoords, const u16>::Node snode;
 915
 916                                 // Main algorithm
 917                                 u32 highest = 0;
 918                                 u32 drawcalls = 0;
 919                                 for (;;)
 920                                 {
 921                                         if (tc[highest].drawn)
 922                                         {
 923                                                 bool found = false;
 924                                                 float hiscore = 0;
 925                                                 for (u32 t = 0; t < tcount; t++)
 926                                                 {
 927                                                         if (!tc[t].drawn)
 928                                                         {
 929                                                                 if (tc[t].score > hiscore)
 930                                                                 {
 931                                                                         highest = t;
 932                                                                         hiscore = tc[t].score;
 933                                                                         found = true;
 934                                                                 }
 935                                                         }
 936                                                 }
 937                                                 if (!found)
 938                                                         break;
 939                                         }
 940
 941                                         // Output the best triangle
 942                                         u16 newind = buf->Vertices.size();
 943
 944                                         snode *s = sind.find(v[tc[highest].ind[0]]);
 945
 946                                         if (!s)
 947                                         {
 948                                                 buf->Vertices.push_back(v[tc[highest].ind[0]]);
 949                                                 buf->Indices.push_back(newind);
 950                                                 sind.insert(v[tc[highest].ind[0]], newind);
 951                                                 newind++;
 952                                         }
 953                                         else
 954                                         {
 955                                                 buf->Indices.push_back(s->getValue());
 956                                         }
 957
 958                                         s = sind.find(v[tc[highest].ind[1]]);
 959
 960                                         if (!s)
 961                                         {
 962                                                 buf->Vertices.push_back(v[tc[highest].ind[1]]);
 963                                                 buf->Indices.push_back(newind);
 964                                                 sind.insert(v[tc[highest].ind[1]], newind);
 965                                                 newind++;
 966                                         }
 967                                         else
 968                                         {
 969                                                 buf->Indices.push_back(s->getValue());
 970                                         }
 971
 972                                         s = sind.find(v[tc[highest].ind[2]]);
 973
 974                                         if (!s)
 975                                         {
 976                                                 buf->Vertices.push_back(v[tc[highest].ind[2]]);
 977                                                 buf->Indices.push_back(newind);
 978                                                 sind.insert(v[tc[highest].ind[2]], newind);
 979                                         }
 980                                         else
 981                                         {
 982                                                 buf->Indices.push_back(s->getValue());
 983                                         }
 984
 985                                         vc[tc[highest].ind[0]].NumActiveTris--;
 986                                         vc[tc[highest].ind[1]].NumActiveTris--;
 987                                         vc[tc[highest].ind[2]].NumActiveTris--;
 988
 989                                         tc[highest].drawn = true;
 990
 991                                         for (u16 j = 0; j < 3; j++)
 992                                         {
 993                                                 vcache *vert = &vc[tc[highest].ind[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 = 0; j < 3; j++)
1105                                         {
1106                                                 vcache *vert = &vc[tc[highest].ind[j]];
1107                                                 for (u16 t = 0; t < vert->tris.size(); t++)
1108                                                 {
1109                                                         if (highest == vert->tris[t])
1110                                                         {
1111                                                                 vert->tris.erase(t);
1112                                                                 break;
1113                                                         }
1114                                                 }
1115                                         }
1116
1117                                         lru.add(tc[highest].ind[0]);
1118                                         lru.add(tc[highest].ind[1]);
1119                                         highest = lru.add(tc[highest].ind[2]);
1120                                         drawcalls++;
1121                                 }
1122
1123                                 buf->setBoundingBox(mb->getBoundingBox());
1124                                 newmesh->addMeshBuffer(buf);
1125                                 buf->drop();
1126                         }
1127                         break;
1128                 }
1129
1130                 delete [] vc;
1131                 delete [] tc;
1132
1133         } // for each meshbuffer
1134
1135         return newmesh;
1136 }