src/mesh.cpp

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