1 /*************************************************************************/
2 /* geometry.cpp */
3 /*************************************************************************/
4 /* This file is part of: */
5 /* GODOT ENGINE */
6 /* https://godotengine.org */
7 /*************************************************************************/
8 /* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */
9 /* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */
10 /* */
11 /* Permission is hereby granted, free of charge, to any person obtaining */
12 /* a copy of this software and associated documentation files (the */
13 /* "Software"), to deal in the Software without restriction, including */
14 /* without limitation the rights to use, copy, modify, merge, publish, */
15 /* distribute, sublicense, and/or sell copies of the Software, and to */
16 /* permit persons to whom the Software is furnished to do so, subject to */
17 /* the following conditions: */
18 /* */
19 /* The above copyright notice and this permission notice shall be */
20 /* included in all copies or substantial portions of the Software. */
21 /* */
22 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24 /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
25 /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26 /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27 /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28 /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29 /*************************************************************************/
30 #include "geometry.h"
31 #include "print_string.h"
32
optimize_vertices()33 void Geometry::MeshData::optimize_vertices() {
34
35 Map<int, int> vtx_remap;
36
37 for (int i = 0; i < faces.size(); i++) {
38
39 for (int j = 0; j < faces[i].indices.size(); j++) {
40
41 int idx = faces[i].indices[j];
42 if (!vtx_remap.has(idx)) {
43 int ni = vtx_remap.size();
44 vtx_remap[idx] = ni;
45 }
46
47 faces[i].indices[j] = vtx_remap[idx];
48 }
49 }
50
51 for (int i = 0; i < edges.size(); i++) {
52
53 int a = edges[i].a;
54 int b = edges[i].b;
55
56 if (!vtx_remap.has(a)) {
57 int ni = vtx_remap.size();
58 vtx_remap[a] = ni;
59 }
60 if (!vtx_remap.has(b)) {
61 int ni = vtx_remap.size();
62 vtx_remap[b] = ni;
63 }
64
65 edges[i].a = vtx_remap[a];
66 edges[i].b = vtx_remap[b];
67 }
68
69 Vector<Vector3> new_vertices;
70 new_vertices.resize(vtx_remap.size());
71
72 for (int i = 0; i < vertices.size(); i++) {
73
74 if (vtx_remap.has(i))
75 new_vertices[vtx_remap[i]] = vertices[i];
76 }
77 vertices = new_vertices;
78 }
79
80 Vector<Vector<Vector2> > (*Geometry::_decompose_func)(const Vector<Vector2> &p_polygon) = NULL;
81
82 struct _FaceClassify {
83
84 struct _Link {
85
86 int face;
87 int edge;
clear_FaceClassify::_Link88 void clear() {
89 face = -1;
90 edge = -1;
91 }
_Link_FaceClassify::_Link92 _Link() {
93 face = -1;
94 edge = -1;
95 }
96 };
97 bool valid;
98 int group;
99 _Link links[3];
100 Face3 face;
_FaceClassify_FaceClassify101 _FaceClassify() {
102 group = -1;
103 valid = false;
104 };
105 };
106
_connect_faces(_FaceClassify * p_faces,int len,int p_group)107 static bool _connect_faces(_FaceClassify *p_faces, int len, int p_group) {
108 /* connect faces, error will occur if an edge is shared between more than 2 faces */
109 /* clear connections */
110
111 bool error = false;
112
113 for (int i = 0; i < len; i++) {
114
115 for (int j = 0; j < 3; j++) {
116
117 p_faces[i].links[j].clear();
118 }
119 }
120
121 for (int i = 0; i < len; i++) {
122
123 if (p_faces[i].group != p_group)
124 continue;
125 for (int j = i + 1; j < len; j++) {
126
127 if (p_faces[j].group != p_group)
128 continue;
129
130 for (int k = 0; k < 3; k++) {
131
132 Vector3 vi1 = p_faces[i].face.vertex[k];
133 Vector3 vi2 = p_faces[i].face.vertex[(k + 1) % 3];
134
135 for (int l = 0; l < 3; l++) {
136
137 Vector3 vj2 = p_faces[j].face.vertex[l];
138 Vector3 vj1 = p_faces[j].face.vertex[(l + 1) % 3];
139
140 if (vi1.distance_to(vj1) < 0.00001 &&
141 vi2.distance_to(vj2) < 0.00001) {
142 if (p_faces[i].links[k].face != -1) {
143
144 ERR_PRINT("already linked\n");
145 error = true;
146 break;
147 }
148 if (p_faces[j].links[l].face != -1) {
149
150 ERR_PRINT("already linked\n");
151 error = true;
152 break;
153 }
154
155 p_faces[i].links[k].face = j;
156 p_faces[i].links[k].edge = l;
157 p_faces[j].links[l].face = i;
158 p_faces[j].links[l].edge = k;
159 }
160 }
161 if (error)
162 break;
163 }
164 if (error)
165 break;
166 }
167 if (error)
168 break;
169 }
170
171 for (int i = 0; i < len; i++) {
172
173 p_faces[i].valid = true;
174 for (int j = 0; j < 3; j++) {
175
176 if (p_faces[i].links[j].face == -1)
177 p_faces[i].valid = false;
178 }
179 /*printf("face %i is valid: %i, group %i. connected to %i:%i,%i:%i,%i:%i\n",i,p_faces[i].valid,p_faces[i].group,
180 p_faces[i].links[0].face,
181 p_faces[i].links[0].edge,
182 p_faces[i].links[1].face,
183 p_faces[i].links[1].edge,
184 p_faces[i].links[2].face,
185 p_faces[i].links[2].edge);*/
186 }
187 return error;
188 }
189
_group_face(_FaceClassify * p_faces,int len,int p_index,int p_group)190 static bool _group_face(_FaceClassify *p_faces, int len, int p_index, int p_group) {
191
192 if (p_faces[p_index].group >= 0)
193 return false;
194
195 p_faces[p_index].group = p_group;
196
197 for (int i = 0; i < 3; i++) {
198
199 ERR_FAIL_INDEX_V(p_faces[p_index].links[i].face, len, true);
200 _group_face(p_faces, len, p_faces[p_index].links[i].face, p_group);
201 }
202
203 return true;
204 }
205
separate_objects(DVector<Face3> p_array)206 DVector<DVector<Face3> > Geometry::separate_objects(DVector<Face3> p_array) {
207
208 DVector<DVector<Face3> > objects;
209
210 int len = p_array.size();
211
212 DVector<Face3>::Read r = p_array.read();
213
214 const Face3 *arrayptr = r.ptr();
215
216 DVector<_FaceClassify> fc;
217
218 fc.resize(len);
219
220 DVector<_FaceClassify>::Write fcw = fc.write();
221
222 _FaceClassify *_fcptr = fcw.ptr();
223
224 for (int i = 0; i < len; i++) {
225
226 _fcptr[i].face = arrayptr[i];
227 }
228
229 bool error = _connect_faces(_fcptr, len, -1);
230
231 if (error) {
232
233 ERR_FAIL_COND_V(error, DVector<DVector<Face3> >()); // invalid geometry
234 }
235
236 /* group connected faces in separate objects */
237
238 int group = 0;
239 for (int i = 0; i < len; i++) {
240
241 if (!_fcptr[i].valid)
242 continue;
243 if (_group_face(_fcptr, len, i, group)) {
244 group++;
245 }
246 }
247
248 /* group connected faces in separate objects */
249
250 for (int i = 0; i < len; i++) {
251
252 _fcptr[i].face = arrayptr[i];
253 }
254
255 if (group >= 0) {
256
257 objects.resize(group);
258 DVector<DVector<Face3> >::Write obw = objects.write();
259 DVector<Face3> *group_faces = obw.ptr();
260
261 for (int i = 0; i < len; i++) {
262 if (!_fcptr[i].valid)
263 continue;
264 if (_fcptr[i].group >= 0 && _fcptr[i].group < group) {
265
266 group_faces[_fcptr[i].group].push_back(_fcptr[i].face);
267 }
268 }
269 }
270
271 return objects;
272 }
273
274 /*** GEOMETRY WRAPPER ***/
275
276 enum _CellFlags {
277
278 _CELL_SOLID = 1,
279 _CELL_EXTERIOR = 2,
280 _CELL_STEP_MASK = 0x1C,
281 _CELL_STEP_NONE = 0 << 2,
282 _CELL_STEP_Y_POS = 1 << 2,
283 _CELL_STEP_Y_NEG = 2 << 2,
284 _CELL_STEP_X_POS = 3 << 2,
285 _CELL_STEP_X_NEG = 4 << 2,
286 _CELL_STEP_Z_POS = 5 << 2,
287 _CELL_STEP_Z_NEG = 6 << 2,
288 _CELL_STEP_DONE = 7 << 2,
289 _CELL_PREV_MASK = 0xE0,
290 _CELL_PREV_NONE = 0 << 5,
291 _CELL_PREV_Y_POS = 1 << 5,
292 _CELL_PREV_Y_NEG = 2 << 5,
293 _CELL_PREV_X_POS = 3 << 5,
294 _CELL_PREV_X_NEG = 4 << 5,
295 _CELL_PREV_Z_POS = 5 << 5,
296 _CELL_PREV_Z_NEG = 6 << 5,
297 _CELL_PREV_FIRST = 7 << 5,
298
299 };
300
_plot_face(uint8_t *** p_cell_status,int x,int y,int z,int len_x,int len_y,int len_z,const Vector3 & voxelsize,const Face3 & p_face)301 static inline void _plot_face(uint8_t ***p_cell_status, int x, int y, int z, int len_x, int len_y, int len_z, const Vector3 &voxelsize, const Face3 &p_face) {
302
303 AABB aabb(Vector3(x, y, z), Vector3(len_x, len_y, len_z));
304 aabb.pos = aabb.pos * voxelsize;
305 aabb.size = aabb.size * voxelsize;
306
307 if (!p_face.intersects_aabb(aabb))
308 return;
309
310 if (len_x == 1 && len_y == 1 && len_z == 1) {
311
312 p_cell_status[x][y][z] = _CELL_SOLID;
313 return;
314 }
315
316 int div_x = len_x > 1 ? 2 : 1;
317 int div_y = len_y > 1 ? 2 : 1;
318 int div_z = len_z > 1 ? 2 : 1;
319
320 #define _SPLIT(m_i, m_div, m_v, m_len_v, m_new_v, m_new_len_v) \
321 if (m_div == 1) { \
322 m_new_v = m_v; \
323 m_new_len_v = 1; \
324 } else if (m_i == 0) { \
325 m_new_v = m_v; \
326 m_new_len_v = m_len_v / 2; \
327 } else { \
328 m_new_v = m_v + m_len_v / 2; \
329 m_new_len_v = m_len_v - m_len_v / 2; \
330 }
331
332 int new_x;
333 int new_len_x;
334 int new_y;
335 int new_len_y;
336 int new_z;
337 int new_len_z;
338
339 for (int i = 0; i < div_x; i++) {
340
341 _SPLIT(i, div_x, x, len_x, new_x, new_len_x);
342
343 for (int j = 0; j < div_y; j++) {
344
345 _SPLIT(j, div_y, y, len_y, new_y, new_len_y);
346
347 for (int k = 0; k < div_z; k++) {
348
349 _SPLIT(k, div_z, z, len_z, new_z, new_len_z);
350
351 _plot_face(p_cell_status, new_x, new_y, new_z, new_len_x, new_len_y, new_len_z, voxelsize, p_face);
352 }
353 }
354 }
355 }
356
_mark_outside(uint8_t *** p_cell_status,int x,int y,int z,int len_x,int len_y,int len_z)357 static inline void _mark_outside(uint8_t ***p_cell_status, int x, int y, int z, int len_x, int len_y, int len_z) {
358
359 if (p_cell_status[x][y][z] & 3)
360 return; // nothing to do, already used and/or visited
361
362 p_cell_status[x][y][z] = _CELL_PREV_FIRST;
363
364 while (true) {
365
366 uint8_t &c = p_cell_status[x][y][z];
367
368 //printf("at %i,%i,%i\n",x,y,z);
369
370 if ((c & _CELL_STEP_MASK) == _CELL_STEP_NONE) {
371 /* Haven't been in here, mark as outside */
372 p_cell_status[x][y][z] |= _CELL_EXTERIOR;
373 //printf("not marked as anything, marking exterior\n");
374 }
375
376 //printf("cell step is %i\n",(c&_CELL_STEP_MASK));
377
378 if ((c & _CELL_STEP_MASK) != _CELL_STEP_DONE) {
379 /* if not done, increase step */
380 c += 1 << 2;
381 //printf("incrementing cell step\n");
382 }
383
384 if ((c & _CELL_STEP_MASK) == _CELL_STEP_DONE) {
385 /* Go back */
386 //printf("done, going back a cell\n");
387
388 switch (c & _CELL_PREV_MASK) {
389 case _CELL_PREV_FIRST: {
390 //printf("at end, finished marking\n");
391 return;
392 } break;
393 case _CELL_PREV_Y_POS: {
394 y++;
395 ERR_FAIL_COND(y >= len_y);
396 } break;
397 case _CELL_PREV_Y_NEG: {
398 y--;
399 ERR_FAIL_COND(y < 0);
400 } break;
401 case _CELL_PREV_X_POS: {
402 x++;
403 ERR_FAIL_COND(x >= len_x);
404 } break;
405 case _CELL_PREV_X_NEG: {
406 x--;
407 ERR_FAIL_COND(x < 0);
408 } break;
409 case _CELL_PREV_Z_POS: {
410 z++;
411 ERR_FAIL_COND(z >= len_z);
412 } break;
413 case _CELL_PREV_Z_NEG: {
414 z--;
415 ERR_FAIL_COND(z < 0);
416 } break;
417 default: {
418 ERR_FAIL();
419 }
420 }
421 continue;
422 }
423
424 //printf("attempting new cell!\n");
425
426 int next_x = x, next_y = y, next_z = z;
427 uint8_t prev = 0;
428
429 switch (c & _CELL_STEP_MASK) {
430
431 case _CELL_STEP_Y_POS: {
432
433 next_y++;
434 prev = _CELL_PREV_Y_NEG;
435 } break;
436 case _CELL_STEP_Y_NEG: {
437 next_y--;
438 prev = _CELL_PREV_Y_POS;
439 } break;
440 case _CELL_STEP_X_POS: {
441 next_x++;
442 prev = _CELL_PREV_X_NEG;
443 } break;
444 case _CELL_STEP_X_NEG: {
445 next_x--;
446 prev = _CELL_PREV_X_POS;
447 } break;
448 case _CELL_STEP_Z_POS: {
449 next_z++;
450 prev = _CELL_PREV_Z_NEG;
451 } break;
452 case _CELL_STEP_Z_NEG: {
453 next_z--;
454 prev = _CELL_PREV_Z_POS;
455 } break;
456 default: ERR_FAIL();
457 }
458
459 //printf("testing if new cell will be ok...!\n");
460
461 if (next_x < 0 || next_x >= len_x)
462 continue;
463 if (next_y < 0 || next_y >= len_y)
464 continue;
465 if (next_z < 0 || next_z >= len_z)
466 continue;
467
468 //printf("testing if new cell is traversable\n");
469
470 if (p_cell_status[next_x][next_y][next_z] & 3)
471 continue;
472
473 //printf("move to it\n");
474
475 x = next_x;
476 y = next_y;
477 z = next_z;
478 p_cell_status[x][y][z] |= prev;
479 }
480 }
481
_build_faces(uint8_t *** p_cell_status,int x,int y,int z,int len_x,int len_y,int len_z,DVector<Face3> & p_faces)482 static inline void _build_faces(uint8_t ***p_cell_status, int x, int y, int z, int len_x, int len_y, int len_z, DVector<Face3> &p_faces) {
483
484 ERR_FAIL_INDEX(x, len_x);
485 ERR_FAIL_INDEX(y, len_y);
486 ERR_FAIL_INDEX(z, len_z);
487
488 if (p_cell_status[x][y][z] & _CELL_EXTERIOR)
489 return;
490
491 /* static const Vector3 vertices[8]={
492 Vector3(0,0,0),
493 Vector3(0,0,1),
494 Vector3(0,1,0),
495 Vector3(0,1,1),
496 Vector3(1,0,0),
497 Vector3(1,0,1),
498 Vector3(1,1,0),
499 Vector3(1,1,1),
500 };
501 */
502 #define vert(m_idx) Vector3((m_idx & 4) >> 2, (m_idx & 2) >> 1, m_idx & 1)
503
504 static const uint8_t indices[6][4] = {
505 { 7, 6, 4, 5 },
506 { 7, 3, 2, 6 },
507 { 7, 5, 1, 3 },
508 { 0, 2, 3, 1 },
509 { 0, 1, 5, 4 },
510 { 0, 4, 6, 2 },
511
512 };
513 /*
514
515 {0,1,2,3},
516 {0,1,4,5},
517 {0,2,4,6},
518 {4,5,6,7},
519 {2,3,7,6},
520 {1,3,5,7},
521
522 {0,2,3,1},
523 {0,1,5,4},
524 {0,4,6,2},
525 {7,6,4,5},
526 {7,3,2,6},
527 {7,5,1,3},
528 */
529
530 for (int i = 0; i < 6; i++) {
531
532 Vector3 face_points[4];
533 int disp_x = x + ((i % 3) == 0 ? ((i < 3) ? 1 : -1) : 0);
534 int disp_y = y + (((i - 1) % 3) == 0 ? ((i < 3) ? 1 : -1) : 0);
535 int disp_z = z + (((i - 2) % 3) == 0 ? ((i < 3) ? 1 : -1) : 0);
536
537 bool plot = false;
538
539 if (disp_x < 0 || disp_x >= len_x)
540 plot = true;
541 if (disp_y < 0 || disp_y >= len_y)
542 plot = true;
543 if (disp_z < 0 || disp_z >= len_z)
544 plot = true;
545
546 if (!plot && (p_cell_status[disp_x][disp_y][disp_z] & _CELL_EXTERIOR))
547 plot = true;
548
549 if (!plot)
550 continue;
551
552 for (int j = 0; j < 4; j++)
553 face_points[j] = vert(indices[i][j]) + Vector3(x, y, z);
554
555 p_faces.push_back(
556 Face3(
557 face_points[0],
558 face_points[1],
559 face_points[2]));
560
561 p_faces.push_back(
562 Face3(
563 face_points[2],
564 face_points[3],
565 face_points[0]));
566 }
567 }
568
wrap_geometry(DVector<Face3> p_array,float * p_error)569 DVector<Face3> Geometry::wrap_geometry(DVector<Face3> p_array, float *p_error) {
570
571 #define _MIN_SIZE 1.0
572 #define _MAX_LENGTH 20
573
574 int face_count = p_array.size();
575 DVector<Face3>::Read facesr = p_array.read();
576 const Face3 *faces = facesr.ptr();
577
578 AABB global_aabb;
579
580 for (int i = 0; i < face_count; i++) {
581
582 if (i == 0) {
583
584 global_aabb = faces[i].get_aabb();
585 } else {
586
587 global_aabb.merge_with(faces[i].get_aabb());
588 }
589 }
590
591 global_aabb.grow_by(0.01); // avoid numerical error
592
593 // determine amount of cells in grid axis
594 int div_x, div_y, div_z;
595
596 if (global_aabb.size.x / _MIN_SIZE < _MAX_LENGTH)
597 div_x = (int)(global_aabb.size.x / _MIN_SIZE) + 1;
598 else
599 div_x = _MAX_LENGTH;
600
601 if (global_aabb.size.y / _MIN_SIZE < _MAX_LENGTH)
602 div_y = (int)(global_aabb.size.y / _MIN_SIZE) + 1;
603 else
604 div_y = _MAX_LENGTH;
605
606 if (global_aabb.size.z / _MIN_SIZE < _MAX_LENGTH)
607 div_z = (int)(global_aabb.size.z / _MIN_SIZE) + 1;
608 else
609 div_z = _MAX_LENGTH;
610
611 Vector3 voxelsize = global_aabb.size;
612 voxelsize.x /= div_x;
613 voxelsize.y /= div_y;
614 voxelsize.z /= div_z;
615
616 // create and initialize cells to zero
617 //print_line("Wrapper: Initializing Cells");
618
619 uint8_t ***cell_status = memnew_arr(uint8_t **, div_x);
620 for (int i = 0; i < div_x; i++) {
621
622 cell_status[i] = memnew_arr(uint8_t *, div_y);
623
624 for (int j = 0; j < div_y; j++) {
625
626 cell_status[i][j] = memnew_arr(uint8_t, div_z);
627
628 for (int k = 0; k < div_z; k++) {
629
630 cell_status[i][j][k] = 0;
631 }
632 }
633 }
634
635 // plot faces into cells
636 //print_line("Wrapper (1/6): Plotting Faces");
637
638 for (int i = 0; i < face_count; i++) {
639
640 Face3 f = faces[i];
641 for (int j = 0; j < 3; j++) {
642
643 f.vertex[j] -= global_aabb.pos;
644 }
645 _plot_face(cell_status, 0, 0, 0, div_x, div_y, div_z, voxelsize, f);
646 }
647
648 // determine which cells connect to the outside by traversing the outside and recursively flood-fill marking
649
650 //print_line("Wrapper (2/6): Flood Filling");
651
652 for (int i = 0; i < div_x; i++) {
653
654 for (int j = 0; j < div_y; j++) {
655
656 _mark_outside(cell_status, i, j, 0, div_x, div_y, div_z);
657 _mark_outside(cell_status, i, j, div_z - 1, div_x, div_y, div_z);
658 }
659 }
660
661 for (int i = 0; i < div_z; i++) {
662
663 for (int j = 0; j < div_y; j++) {
664
665 _mark_outside(cell_status, 0, j, i, div_x, div_y, div_z);
666 _mark_outside(cell_status, div_x - 1, j, i, div_x, div_y, div_z);
667 }
668 }
669
670 for (int i = 0; i < div_x; i++) {
671
672 for (int j = 0; j < div_z; j++) {
673
674 _mark_outside(cell_status, i, 0, j, div_x, div_y, div_z);
675 _mark_outside(cell_status, i, div_y - 1, j, div_x, div_y, div_z);
676 }
677 }
678
679 // build faces for the inside-outside cell divisors
680
681 //print_line("Wrapper (3/6): Building Faces");
682
683 DVector<Face3> wrapped_faces;
684
685 for (int i = 0; i < div_x; i++) {
686
687 for (int j = 0; j < div_y; j++) {
688
689 for (int k = 0; k < div_z; k++) {
690
691 _build_faces(cell_status, i, j, k, div_x, div_y, div_z, wrapped_faces);
692 }
693 }
694 }
695
696 //print_line("Wrapper (4/6): Transforming Back Vertices");
697
698 // transform face vertices to global coords
699
700 int wrapped_faces_count = wrapped_faces.size();
701 DVector<Face3>::Write wrapped_facesw = wrapped_faces.write();
702 Face3 *wrapped_faces_ptr = wrapped_facesw.ptr();
703
704 for (int i = 0; i < wrapped_faces_count; i++) {
705
706 for (int j = 0; j < 3; j++) {
707
708 Vector3 &v = wrapped_faces_ptr[i].vertex[j];
709 v = v * voxelsize;
710 v += global_aabb.pos;
711 }
712 }
713
714 // clean up grid
715 //print_line("Wrapper (5/6): Grid Cleanup");
716
717 for (int i = 0; i < div_x; i++) {
718
719 for (int j = 0; j < div_y; j++) {
720
721 memdelete_arr(cell_status[i][j]);
722 }
723
724 memdelete_arr(cell_status[i]);
725 }
726
727 memdelete_arr(cell_status);
728 if (p_error)
729 *p_error = voxelsize.length();
730
731 //print_line("Wrapper (6/6): Finished.");
732 return wrapped_faces;
733 }
734
build_convex_mesh(const DVector<Plane> & p_planes)735 Geometry::MeshData Geometry::build_convex_mesh(const DVector<Plane> &p_planes) {
736
737 MeshData mesh;
738
739 #define SUBPLANE_SIZE 1024.0
740
741 float subplane_size = 1024.0; // should compute this from the actual plane
742 for (int i = 0; i < p_planes.size(); i++) {
743
744 Plane p = p_planes[i];
745
746 Vector3 ref = Vector3(0.0, 1.0, 0.0);
747
748 if (ABS(p.normal.dot(ref)) > 0.95)
749 ref = Vector3(0.0, 0.0, 1.0); // change axis
750
751 Vector3 right = p.normal.cross(ref).normalized();
752 Vector3 up = p.normal.cross(right).normalized();
753
754 Vector<Vector3> vertices;
755
756 Vector3 center = p.get_any_point();
757 // make a quad clockwise
758 vertices.push_back(center - up * subplane_size + right * subplane_size);
759 vertices.push_back(center - up * subplane_size - right * subplane_size);
760 vertices.push_back(center + up * subplane_size - right * subplane_size);
761 vertices.push_back(center + up * subplane_size + right * subplane_size);
762
763 for (int j = 0; j < p_planes.size(); j++) {
764
765 if (j == i)
766 continue;
767
768 Vector<Vector3> new_vertices;
769 Plane clip = p_planes[j];
770
771 if (clip.normal.dot(p.normal) > 0.95)
772 continue;
773
774 if (vertices.size() < 3)
775 break;
776
777 for (int k = 0; k < vertices.size(); k++) {
778
779 int k_n = (k + 1) % vertices.size();
780
781 Vector3 edge0_A = vertices[k];
782 Vector3 edge1_A = vertices[k_n];
783
784 real_t dist0 = clip.distance_to(edge0_A);
785 real_t dist1 = clip.distance_to(edge1_A);
786
787 if (dist0 <= 0) { // behind plane
788
789 new_vertices.push_back(vertices[k]);
790 }
791
792 // check for different sides and non coplanar
793 if ((dist0 * dist1) < 0) {
794
795 // calculate intersection
796 Vector3 rel = edge1_A - edge0_A;
797
798 real_t den = clip.normal.dot(rel);
799 if (Math::abs(den) < CMP_EPSILON)
800 continue; // point too short
801
802 real_t dist = -(clip.normal.dot(edge0_A) - clip.d) / den;
803 Vector3 inters = edge0_A + rel * dist;
804 new_vertices.push_back(inters);
805 }
806 }
807
808 vertices = new_vertices;
809 }
810
811 if (vertices.size() < 3)
812 continue;
813
814 //result is a clockwise face
815
816 MeshData::Face face;
817
818 // add face indices
819 for (int j = 0; j < vertices.size(); j++) {
820
821 int idx = -1;
822 for (int k = 0; k < mesh.vertices.size(); k++) {
823
824 if (mesh.vertices[k].distance_to(vertices[j]) < 0.001) {
825
826 idx = k;
827 break;
828 }
829 }
830
831 if (idx == -1) {
832
833 idx = mesh.vertices.size();
834 mesh.vertices.push_back(vertices[j]);
835 }
836
837 face.indices.push_back(idx);
838 }
839 face.plane = p;
840 mesh.faces.push_back(face);
841
842 //add edge
843
844 for (int j = 0; j < face.indices.size(); j++) {
845
846 int a = face.indices[j];
847 int b = face.indices[(j + 1) % face.indices.size()];
848
849 bool found = false;
850 for (int k = 0; k < mesh.edges.size(); k++) {
851
852 if (mesh.edges[k].a == a && mesh.edges[k].b == b) {
853 found = true;
854 break;
855 }
856 if (mesh.edges[k].b == a && mesh.edges[k].a == b) {
857 found = true;
858 break;
859 }
860 }
861
862 if (found)
863 continue;
864 MeshData::Edge edge;
865 edge.a = a;
866 edge.b = b;
867 mesh.edges.push_back(edge);
868 }
869 }
870
871 return mesh;
872 }
873
build_box_planes(const Vector3 & p_extents)874 DVector<Plane> Geometry::build_box_planes(const Vector3 &p_extents) {
875
876 DVector<Plane> planes;
877
878 planes.push_back(Plane(Vector3(1, 0, 0), p_extents.x));
879 planes.push_back(Plane(Vector3(-1, 0, 0), p_extents.x));
880 planes.push_back(Plane(Vector3(0, 1, 0), p_extents.y));
881 planes.push_back(Plane(Vector3(0, -1, 0), p_extents.y));
882 planes.push_back(Plane(Vector3(0, 0, 1), p_extents.z));
883 planes.push_back(Plane(Vector3(0, 0, -1), p_extents.z));
884
885 return planes;
886 }
887
build_cylinder_planes(float p_radius,float p_height,int p_sides,Vector3::Axis p_axis)888 DVector<Plane> Geometry::build_cylinder_planes(float p_radius, float p_height, int p_sides, Vector3::Axis p_axis) {
889
890 DVector<Plane> planes;
891
892 for (int i = 0; i < p_sides; i++) {
893
894 Vector3 normal;
895 normal[(p_axis + 1) % 3] = Math::cos(i * (2.0 * Math_PI) / p_sides);
896 normal[(p_axis + 2) % 3] = Math::sin(i * (2.0 * Math_PI) / p_sides);
897
898 planes.push_back(Plane(normal, p_radius));
899 }
900
901 Vector3 axis;
902 axis[p_axis] = 1.0;
903
904 planes.push_back(Plane(axis, p_height * 0.5));
905 planes.push_back(Plane(-axis, p_height * 0.5));
906
907 return planes;
908 }
909
build_sphere_planes(float p_radius,int p_lats,int p_lons,Vector3::Axis p_axis)910 DVector<Plane> Geometry::build_sphere_planes(float p_radius, int p_lats, int p_lons, Vector3::Axis p_axis) {
911
912 DVector<Plane> planes;
913
914 Vector3 axis;
915 axis[p_axis] = 1.0;
916
917 Vector3 axis_neg;
918 axis_neg[(p_axis + 1) % 3] = 1.0;
919 axis_neg[(p_axis + 2) % 3] = 1.0;
920 axis_neg[p_axis] = -1.0;
921
922 for (int i = 0; i < p_lons; i++) {
923
924 Vector3 normal;
925 normal[(p_axis + 1) % 3] = Math::cos(i * (2.0 * Math_PI) / p_lons);
926 normal[(p_axis + 2) % 3] = Math::sin(i * (2.0 * Math_PI) / p_lons);
927
928 planes.push_back(Plane(normal, p_radius));
929
930 for (int j = 1; j <= p_lats; j++) {
931
932 //todo this is stupid, fix
933 Vector3 angle = normal.linear_interpolate(axis, j / (float)p_lats).normalized();
934 Vector3 pos = angle * p_radius;
935 planes.push_back(Plane(pos, angle));
936 planes.push_back(Plane(pos * axis_neg, angle * axis_neg));
937 }
938 }
939
940 return planes;
941 }
942
build_capsule_planes(float p_radius,float p_height,int p_sides,int p_lats,Vector3::Axis p_axis)943 DVector<Plane> Geometry::build_capsule_planes(float p_radius, float p_height, int p_sides, int p_lats, Vector3::Axis p_axis) {
944
945 DVector<Plane> planes;
946
947 Vector3 axis;
948 axis[p_axis] = 1.0;
949
950 Vector3 axis_neg;
951 axis_neg[(p_axis + 1) % 3] = 1.0;
952 axis_neg[(p_axis + 2) % 3] = 1.0;
953 axis_neg[p_axis] = -1.0;
954
955 for (int i = 0; i < p_sides; i++) {
956
957 Vector3 normal;
958 normal[(p_axis + 1) % 3] = Math::cos(i * (2.0 * Math_PI) / p_sides);
959 normal[(p_axis + 2) % 3] = Math::sin(i * (2.0 * Math_PI) / p_sides);
960
961 planes.push_back(Plane(normal, p_radius));
962
963 for (int j = 1; j <= p_lats; j++) {
964
965 Vector3 angle = normal.linear_interpolate(axis, j / (float)p_lats).normalized();
966 Vector3 pos = axis * p_height * 0.5 + angle * p_radius;
967 planes.push_back(Plane(pos, angle));
968 planes.push_back(Plane(pos * axis_neg, angle * axis_neg));
969 }
970 }
971
972 return planes;
973 }
974
975 struct _AtlasWorkRect {
976
977 Size2i s;
978 Point2i p;
979 int idx;
operator <_AtlasWorkRect980 _FORCE_INLINE_ bool operator<(const _AtlasWorkRect &p_r) const { return s.width > p_r.s.width; };
981 };
982
983 struct _AtlasWorkRectResult {
984
985 Vector<_AtlasWorkRect> result;
986 int max_w;
987 int max_h;
988 };
989
make_atlas(const Vector<Size2i> & p_rects,Vector<Point2i> & r_result,Size2i & r_size)990 void Geometry::make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_result, Size2i &r_size) {
991
992 //super simple, almost brute force scanline stacking fitter
993 //it's pretty basic for now, but it tries to make sure that the aspect ratio of the
994 //resulting atlas is somehow square. This is necesary because video cards have limits
995 //on texture size (usually 2048 or 4096), so the more square a texture, the more chances
996 //it will work in every hardware.
997 // for example, it will prioritize a 1024x1024 atlas (works everywhere) instead of a
998 // 256x8192 atlas (won't work anywhere).
999
1000 ERR_FAIL_COND(p_rects.size() == 0);
1001
1002 Vector<_AtlasWorkRect> wrects;
1003 wrects.resize(p_rects.size());
1004 for (int i = 0; i < p_rects.size(); i++) {
1005 wrects[i].s = p_rects[i];
1006 wrects[i].idx = i;
1007 }
1008 wrects.sort();
1009 int widest = wrects[0].s.width;
1010
1011 Vector<_AtlasWorkRectResult> results;
1012
1013 for (int i = 0; i <= 12; i++) {
1014
1015 int w = 1 << i;
1016 int max_h = 0;
1017 int max_w = 0;
1018 if (w < widest)
1019 continue;
1020
1021 Vector<int> hmax;
1022 hmax.resize(w);
1023 for (int j = 0; j < w; j++)
1024 hmax[j] = 0;
1025
1026 //place them
1027 int ofs = 0;
1028 int limit_h = 0;
1029 for (int j = 0; j < wrects.size(); j++) {
1030
1031 if (ofs + wrects[j].s.width > w) {
1032
1033 ofs = 0;
1034 }
1035
1036 int from_y = 0;
1037 for (int k = 0; k < wrects[j].s.width; k++) {
1038
1039 if (hmax[ofs + k] > from_y)
1040 from_y = hmax[ofs + k];
1041 }
1042
1043 wrects[j].p.x = ofs;
1044 wrects[j].p.y = from_y;
1045 int end_h = from_y + wrects[j].s.height;
1046 int end_w = ofs + wrects[j].s.width;
1047 if (ofs == 0)
1048 limit_h = end_h;
1049
1050 for (int k = 0; k < wrects[j].s.width; k++) {
1051
1052 hmax[ofs + k] = end_h;
1053 }
1054
1055 if (end_h > max_h)
1056 max_h = end_h;
1057
1058 if (end_w > max_w)
1059 max_w = end_w;
1060
1061 if (ofs == 0 || end_h > limit_h) //while h limit not reched, keep stacking
1062 ofs += wrects[j].s.width;
1063 }
1064
1065 _AtlasWorkRectResult result;
1066 result.result = wrects;
1067 result.max_h = max_h;
1068 result.max_w = max_w;
1069 results.push_back(result);
1070 }
1071
1072 //find the result with the best aspect ratio
1073
1074 int best = -1;
1075 float best_aspect = 1e20;
1076
1077 for (int i = 0; i < results.size(); i++) {
1078
1079 float h = next_power_of_2(results[i].max_h);
1080 float w = next_power_of_2(results[i].max_w);
1081 float aspect = h > w ? h / w : w / h;
1082 if (aspect < best_aspect) {
1083 best = i;
1084 best_aspect = aspect;
1085 }
1086 }
1087
1088 r_result.resize(p_rects.size());
1089
1090 for (int i = 0; i < p_rects.size(); i++) {
1091
1092 r_result[results[best].result[i].idx] = results[best].result[i].p;
1093 }
1094
1095 r_size = Size2(results[best].max_w, results[best].max_h);
1096 }
1097