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