src/mesh.cpp

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