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