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