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