src/mesh.cpp

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