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