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