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