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