1 /*************************************************************************/
2 /* triangle_mesh.cpp */
3 /*************************************************************************/
4 /* This file is part of: */
5 /* GODOT ENGINE */
6 /* https://godotengine.org */
7 /*************************************************************************/
8 /* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */
9 /* Copyright (c) 2014-2020 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
31 #include "triangle_mesh.h"
32
33 #include "core/sort_array.h"
34
_create_bvh(BVH * p_bvh,BVH ** p_bb,int p_from,int p_size,int p_depth,int & max_depth,int & max_alloc)35 int TriangleMesh::_create_bvh(BVH *p_bvh, BVH **p_bb, int p_from, int p_size, int p_depth, int &max_depth, int &max_alloc) {
36
37 if (p_depth > max_depth) {
38 max_depth = p_depth;
39 }
40
41 if (p_size == 1) {
42
43 return p_bb[p_from] - p_bvh;
44 } else if (p_size == 0) {
45
46 return -1;
47 }
48
49 AABB aabb;
50 aabb = p_bb[p_from]->aabb;
51 for (int i = 1; i < p_size; i++) {
52
53 aabb.merge_with(p_bb[p_from + i]->aabb);
54 }
55
56 int li = aabb.get_longest_axis_index();
57
58 switch (li) {
59
60 case Vector3::AXIS_X: {
61 SortArray<BVH *, BVHCmpX> sort_x;
62 sort_x.nth_element(0, p_size, p_size / 2, &p_bb[p_from]);
63 //sort_x.sort(&p_bb[p_from],p_size);
64 } break;
65 case Vector3::AXIS_Y: {
66 SortArray<BVH *, BVHCmpY> sort_y;
67 sort_y.nth_element(0, p_size, p_size / 2, &p_bb[p_from]);
68 //sort_y.sort(&p_bb[p_from],p_size);
69 } break;
70 case Vector3::AXIS_Z: {
71 SortArray<BVH *, BVHCmpZ> sort_z;
72 sort_z.nth_element(0, p_size, p_size / 2, &p_bb[p_from]);
73 //sort_z.sort(&p_bb[p_from],p_size);
74
75 } break;
76 }
77
78 int left = _create_bvh(p_bvh, p_bb, p_from, p_size / 2, p_depth + 1, max_depth, max_alloc);
79 int right = _create_bvh(p_bvh, p_bb, p_from + p_size / 2, p_size - p_size / 2, p_depth + 1, max_depth, max_alloc);
80
81 int index = max_alloc++;
82 BVH *_new = &p_bvh[index];
83 _new->aabb = aabb;
84 _new->center = aabb.position + aabb.size * 0.5;
85 _new->face_index = -1;
86 _new->left = left;
87 _new->right = right;
88
89 return index;
90 }
91
get_indices(PoolVector<int> * r_triangles_indices) const92 void TriangleMesh::get_indices(PoolVector<int> *r_triangles_indices) const {
93
94 if (!valid)
95 return;
96
97 const int triangles_num = triangles.size();
98
99 // Parse vertices indices
100 PoolVector<Triangle>::Read triangles_read = triangles.read();
101
102 r_triangles_indices->resize(triangles_num * 3);
103 PoolVector<int>::Write r_indices_write = r_triangles_indices->write();
104
105 for (int i = 0; i < triangles_num; ++i) {
106 r_indices_write[3 * i + 0] = triangles_read[i].indices[0];
107 r_indices_write[3 * i + 1] = triangles_read[i].indices[1];
108 r_indices_write[3 * i + 2] = triangles_read[i].indices[2];
109 }
110 }
111
create(const PoolVector<Vector3> & p_faces)112 void TriangleMesh::create(const PoolVector<Vector3> &p_faces) {
113
114 valid = false;
115
116 int fc = p_faces.size();
117 ERR_FAIL_COND(!fc || ((fc % 3) != 0));
118 fc /= 3;
119 triangles.resize(fc);
120
121 bvh.resize(fc * 3); //will never be larger than this (todo make better)
122 PoolVector<BVH>::Write bw = bvh.write();
123
124 {
125
126 //create faces and indices and base bvh
127 //except for the Set for repeated triangles, everything
128 //goes in-place.
129
130 PoolVector<Vector3>::Read r = p_faces.read();
131 PoolVector<Triangle>::Write w = triangles.write();
132 Map<Vector3, int> db;
133
134 for (int i = 0; i < fc; i++) {
135
136 Triangle &f = w[i];
137 const Vector3 *v = &r[i * 3];
138
139 for (int j = 0; j < 3; j++) {
140
141 int vidx = -1;
142 Vector3 vs = v[j].snapped(Vector3(0.0001, 0.0001, 0.0001));
143 Map<Vector3, int>::Element *E = db.find(vs);
144 if (E) {
145 vidx = E->get();
146 } else {
147 vidx = db.size();
148 db[vs] = vidx;
149 }
150
151 f.indices[j] = vidx;
152 if (j == 0)
153 bw[i].aabb.position = vs;
154 else
155 bw[i].aabb.expand_to(vs);
156 }
157
158 f.normal = Face3(r[i * 3 + 0], r[i * 3 + 1], r[i * 3 + 2]).get_plane().get_normal();
159
160 bw[i].left = -1;
161 bw[i].right = -1;
162 bw[i].face_index = i;
163 bw[i].center = bw[i].aabb.position + bw[i].aabb.size * 0.5;
164 }
165
166 vertices.resize(db.size());
167 PoolVector<Vector3>::Write vw = vertices.write();
168 for (Map<Vector3, int>::Element *E = db.front(); E; E = E->next()) {
169 vw[E->get()] = E->key();
170 }
171 }
172
173 PoolVector<BVH *> bwptrs;
174 bwptrs.resize(fc);
175 PoolVector<BVH *>::Write bwp = bwptrs.write();
176 for (int i = 0; i < fc; i++) {
177
178 bwp[i] = &bw[i];
179 }
180
181 max_depth = 0;
182 int max_alloc = fc;
183 _create_bvh(bw.ptr(), bwp.ptr(), 0, fc, 1, max_depth, max_alloc);
184
185 bw.release(); //clearup
186 bvh.resize(max_alloc); //resize back
187
188 valid = true;
189 }
190
get_area_normal(const AABB & p_aabb) const191 Vector3 TriangleMesh::get_area_normal(const AABB &p_aabb) const {
192
193 uint32_t *stack = (uint32_t *)alloca(sizeof(int) * max_depth);
194
195 enum {
196 TEST_AABB_BIT = 0,
197 VISIT_LEFT_BIT = 1,
198 VISIT_RIGHT_BIT = 2,
199 VISIT_DONE_BIT = 3,
200 VISITED_BIT_SHIFT = 29,
201 NODE_IDX_MASK = (1 << VISITED_BIT_SHIFT) - 1,
202 VISITED_BIT_MASK = ~NODE_IDX_MASK,
203
204 };
205
206 int n_count = 0;
207 Vector3 n;
208
209 int level = 0;
210
211 PoolVector<Triangle>::Read trianglesr = triangles.read();
212 PoolVector<Vector3>::Read verticesr = vertices.read();
213 PoolVector<BVH>::Read bvhr = bvh.read();
214
215 const Triangle *triangleptr = trianglesr.ptr();
216 int pos = bvh.size() - 1;
217 const BVH *bvhptr = bvhr.ptr();
218
219 stack[0] = pos;
220 while (true) {
221
222 uint32_t node = stack[level] & NODE_IDX_MASK;
223 const BVH &b = bvhptr[node];
224 bool done = false;
225
226 switch (stack[level] >> VISITED_BIT_SHIFT) {
227 case TEST_AABB_BIT: {
228
229 bool valid = b.aabb.intersects(p_aabb);
230 if (!valid) {
231
232 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
233
234 } else {
235
236 if (b.face_index >= 0) {
237
238 const Triangle &s = triangleptr[b.face_index];
239 n += s.normal;
240 n_count++;
241
242 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
243
244 } else {
245
246 stack[level] = (VISIT_LEFT_BIT << VISITED_BIT_SHIFT) | node;
247 }
248 }
249 continue;
250 }
251 case VISIT_LEFT_BIT: {
252
253 stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node;
254 stack[level + 1] = b.left | TEST_AABB_BIT;
255 level++;
256 continue;
257 }
258 case VISIT_RIGHT_BIT: {
259
260 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
261 stack[level + 1] = b.right | TEST_AABB_BIT;
262 level++;
263 continue;
264 }
265 case VISIT_DONE_BIT: {
266
267 if (level == 0) {
268 done = true;
269 break;
270 } else
271 level--;
272 continue;
273 }
274 }
275
276 if (done)
277 break;
278 }
279
280 if (n_count > 0)
281 n /= n_count;
282
283 return n;
284 }
285
intersect_segment(const Vector3 & p_begin,const Vector3 & p_end,Vector3 & r_point,Vector3 & r_normal) const286 bool TriangleMesh::intersect_segment(const Vector3 &p_begin, const Vector3 &p_end, Vector3 &r_point, Vector3 &r_normal) const {
287
288 uint32_t *stack = (uint32_t *)alloca(sizeof(int) * max_depth);
289
290 enum {
291 TEST_AABB_BIT = 0,
292 VISIT_LEFT_BIT = 1,
293 VISIT_RIGHT_BIT = 2,
294 VISIT_DONE_BIT = 3,
295 VISITED_BIT_SHIFT = 29,
296 NODE_IDX_MASK = (1 << VISITED_BIT_SHIFT) - 1,
297 VISITED_BIT_MASK = ~NODE_IDX_MASK,
298
299 };
300
301 Vector3 n = (p_end - p_begin).normalized();
302 real_t d = 1e10;
303 bool inters = false;
304
305 int level = 0;
306
307 PoolVector<Triangle>::Read trianglesr = triangles.read();
308 PoolVector<Vector3>::Read verticesr = vertices.read();
309 PoolVector<BVH>::Read bvhr = bvh.read();
310
311 const Triangle *triangleptr = trianglesr.ptr();
312 const Vector3 *vertexptr = verticesr.ptr();
313 int pos = bvh.size() - 1;
314 const BVH *bvhptr = bvhr.ptr();
315
316 stack[0] = pos;
317 while (true) {
318
319 uint32_t node = stack[level] & NODE_IDX_MASK;
320 const BVH &b = bvhptr[node];
321 bool done = false;
322
323 switch (stack[level] >> VISITED_BIT_SHIFT) {
324 case TEST_AABB_BIT: {
325
326 bool valid = b.aabb.intersects_segment(p_begin, p_end);
327 //bool valid = b.aabb.intersects(ray_aabb);
328
329 if (!valid) {
330
331 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
332
333 } else {
334
335 if (b.face_index >= 0) {
336
337 const Triangle &s = triangleptr[b.face_index];
338 Face3 f3(vertexptr[s.indices[0]], vertexptr[s.indices[1]], vertexptr[s.indices[2]]);
339
340 Vector3 res;
341
342 if (f3.intersects_segment(p_begin, p_end, &res)) {
343
344 real_t nd = n.dot(res);
345 if (nd < d) {
346
347 d = nd;
348 r_point = res;
349 r_normal = f3.get_plane().get_normal();
350 inters = true;
351 }
352 }
353
354 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
355
356 } else {
357
358 stack[level] = (VISIT_LEFT_BIT << VISITED_BIT_SHIFT) | node;
359 }
360 }
361 continue;
362 }
363 case VISIT_LEFT_BIT: {
364
365 stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node;
366 stack[level + 1] = b.left | TEST_AABB_BIT;
367 level++;
368 continue;
369 }
370 case VISIT_RIGHT_BIT: {
371
372 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
373 stack[level + 1] = b.right | TEST_AABB_BIT;
374 level++;
375 continue;
376 }
377 case VISIT_DONE_BIT: {
378
379 if (level == 0) {
380 done = true;
381 break;
382 } else
383 level--;
384 continue;
385 }
386 }
387
388 if (done)
389 break;
390 }
391
392 if (inters) {
393
394 if (n.dot(r_normal) > 0)
395 r_normal = -r_normal;
396 }
397
398 return inters;
399 }
400
intersect_ray(const Vector3 & p_begin,const Vector3 & p_dir,Vector3 & r_point,Vector3 & r_normal) const401 bool TriangleMesh::intersect_ray(const Vector3 &p_begin, const Vector3 &p_dir, Vector3 &r_point, Vector3 &r_normal) const {
402
403 uint32_t *stack = (uint32_t *)alloca(sizeof(int) * max_depth);
404
405 enum {
406 TEST_AABB_BIT = 0,
407 VISIT_LEFT_BIT = 1,
408 VISIT_RIGHT_BIT = 2,
409 VISIT_DONE_BIT = 3,
410 VISITED_BIT_SHIFT = 29,
411 NODE_IDX_MASK = (1 << VISITED_BIT_SHIFT) - 1,
412 VISITED_BIT_MASK = ~NODE_IDX_MASK,
413
414 };
415
416 Vector3 n = p_dir;
417 real_t d = 1e20;
418 bool inters = false;
419
420 int level = 0;
421
422 PoolVector<Triangle>::Read trianglesr = triangles.read();
423 PoolVector<Vector3>::Read verticesr = vertices.read();
424 PoolVector<BVH>::Read bvhr = bvh.read();
425
426 const Triangle *triangleptr = trianglesr.ptr();
427 const Vector3 *vertexptr = verticesr.ptr();
428 int pos = bvh.size() - 1;
429 const BVH *bvhptr = bvhr.ptr();
430
431 stack[0] = pos;
432 while (true) {
433
434 uint32_t node = stack[level] & NODE_IDX_MASK;
435 const BVH &b = bvhptr[node];
436 bool done = false;
437
438 switch (stack[level] >> VISITED_BIT_SHIFT) {
439 case TEST_AABB_BIT: {
440
441 bool valid = b.aabb.intersects_ray(p_begin, p_dir);
442 if (!valid) {
443
444 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
445
446 } else {
447
448 if (b.face_index >= 0) {
449
450 const Triangle &s = triangleptr[b.face_index];
451 Face3 f3(vertexptr[s.indices[0]], vertexptr[s.indices[1]], vertexptr[s.indices[2]]);
452
453 Vector3 res;
454
455 if (f3.intersects_ray(p_begin, p_dir, &res)) {
456
457 real_t nd = n.dot(res);
458 if (nd < d) {
459
460 d = nd;
461 r_point = res;
462 r_normal = f3.get_plane().get_normal();
463 inters = true;
464 }
465 }
466
467 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
468
469 } else {
470
471 stack[level] = (VISIT_LEFT_BIT << VISITED_BIT_SHIFT) | node;
472 }
473 }
474 continue;
475 }
476 case VISIT_LEFT_BIT: {
477
478 stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node;
479 stack[level + 1] = b.left | TEST_AABB_BIT;
480 level++;
481 continue;
482 }
483 case VISIT_RIGHT_BIT: {
484
485 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
486 stack[level + 1] = b.right | TEST_AABB_BIT;
487 level++;
488 continue;
489 }
490 case VISIT_DONE_BIT: {
491
492 if (level == 0) {
493 done = true;
494 break;
495 } else
496 level--;
497 continue;
498 }
499 }
500
501 if (done)
502 break;
503 }
504
505 if (inters) {
506
507 if (n.dot(r_normal) > 0)
508 r_normal = -r_normal;
509 }
510
511 return inters;
512 }
513
intersect_convex_shape(const Plane * p_planes,int p_plane_count,const Vector3 * p_points,int p_point_count) const514 bool TriangleMesh::intersect_convex_shape(const Plane *p_planes, int p_plane_count, const Vector3 *p_points, int p_point_count) const {
515 uint32_t *stack = (uint32_t *)alloca(sizeof(int) * max_depth);
516
517 //p_fully_inside = true;
518
519 enum {
520 TEST_AABB_BIT = 0,
521 VISIT_LEFT_BIT = 1,
522 VISIT_RIGHT_BIT = 2,
523 VISIT_DONE_BIT = 3,
524 VISITED_BIT_SHIFT = 29,
525 NODE_IDX_MASK = (1 << VISITED_BIT_SHIFT) - 1,
526 VISITED_BIT_MASK = ~NODE_IDX_MASK,
527
528 };
529
530 int level = 0;
531
532 PoolVector<Triangle>::Read trianglesr = triangles.read();
533 PoolVector<Vector3>::Read verticesr = vertices.read();
534 PoolVector<BVH>::Read bvhr = bvh.read();
535
536 const Triangle *triangleptr = trianglesr.ptr();
537 const Vector3 *vertexptr = verticesr.ptr();
538 int pos = bvh.size() - 1;
539 const BVH *bvhptr = bvhr.ptr();
540
541 stack[0] = pos;
542 while (true) {
543
544 uint32_t node = stack[level] & NODE_IDX_MASK;
545 const BVH &b = bvhptr[node];
546 bool done = false;
547
548 switch (stack[level] >> VISITED_BIT_SHIFT) {
549 case TEST_AABB_BIT: {
550
551 bool valid = b.aabb.intersects_convex_shape(p_planes, p_plane_count, p_points, p_point_count);
552 if (!valid) {
553
554 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
555
556 } else {
557
558 if (b.face_index >= 0) {
559
560 const Triangle &s = triangleptr[b.face_index];
561
562 for (int j = 0; j < 3; ++j) {
563 const Vector3 &point = vertexptr[s.indices[j]];
564 const Vector3 &next_point = vertexptr[s.indices[(j + 1) % 3]];
565 Vector3 res;
566 bool over = true;
567 for (int i = 0; i < p_plane_count; i++) {
568 const Plane &p = p_planes[i];
569
570 if (p.intersects_segment(point, next_point, &res)) {
571 bool inisde = true;
572 for (int k = 0; k < p_plane_count; k++) {
573 if (k == i) continue;
574 const Plane &pp = p_planes[k];
575 if (pp.is_point_over(res)) {
576 inisde = false;
577 break;
578 }
579 }
580 if (inisde) return true;
581 }
582
583 if (p.is_point_over(point)) {
584 over = false;
585 break;
586 }
587 }
588 if (over) return true;
589 }
590
591 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
592
593 } else {
594
595 stack[level] = (VISIT_LEFT_BIT << VISITED_BIT_SHIFT) | node;
596 }
597 }
598 continue;
599 }
600 case VISIT_LEFT_BIT: {
601
602 stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node;
603 stack[level + 1] = b.left | TEST_AABB_BIT;
604 level++;
605 continue;
606 }
607 case VISIT_RIGHT_BIT: {
608
609 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
610 stack[level + 1] = b.right | TEST_AABB_BIT;
611 level++;
612 continue;
613 }
614 case VISIT_DONE_BIT: {
615
616 if (level == 0) {
617 done = true;
618 break;
619 } else
620 level--;
621 continue;
622 }
623 }
624
625 if (done)
626 break;
627 }
628
629 return false;
630 }
631
inside_convex_shape(const Plane * p_planes,int p_plane_count,const Vector3 * p_points,int p_point_count,Vector3 p_scale) const632 bool TriangleMesh::inside_convex_shape(const Plane *p_planes, int p_plane_count, const Vector3 *p_points, int p_point_count, Vector3 p_scale) const {
633 uint32_t *stack = (uint32_t *)alloca(sizeof(int) * max_depth);
634
635 enum {
636 TEST_AABB_BIT = 0,
637 VISIT_LEFT_BIT = 1,
638 VISIT_RIGHT_BIT = 2,
639 VISIT_DONE_BIT = 3,
640 VISITED_BIT_SHIFT = 29,
641 NODE_IDX_MASK = (1 << VISITED_BIT_SHIFT) - 1,
642 VISITED_BIT_MASK = ~NODE_IDX_MASK,
643
644 };
645
646 int level = 0;
647
648 PoolVector<Triangle>::Read trianglesr = triangles.read();
649 PoolVector<Vector3>::Read verticesr = vertices.read();
650 PoolVector<BVH>::Read bvhr = bvh.read();
651
652 Transform scale(Basis().scaled(p_scale));
653
654 const Triangle *triangleptr = trianglesr.ptr();
655 const Vector3 *vertexptr = verticesr.ptr();
656 int pos = bvh.size() - 1;
657 const BVH *bvhptr = bvhr.ptr();
658
659 stack[0] = pos;
660 while (true) {
661
662 uint32_t node = stack[level] & NODE_IDX_MASK;
663 const BVH &b = bvhptr[node];
664 bool done = false;
665
666 switch (stack[level] >> VISITED_BIT_SHIFT) {
667 case TEST_AABB_BIT: {
668
669 bool intersects = scale.xform(b.aabb).intersects_convex_shape(p_planes, p_plane_count, p_points, p_point_count);
670 if (!intersects) return false;
671
672 bool inside = scale.xform(b.aabb).inside_convex_shape(p_planes, p_plane_count);
673 if (inside) {
674
675 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
676
677 } else {
678
679 if (b.face_index >= 0) {
680 const Triangle &s = triangleptr[b.face_index];
681 for (int j = 0; j < 3; ++j) {
682 Vector3 point = scale.xform(vertexptr[s.indices[j]]);
683 for (int i = 0; i < p_plane_count; i++) {
684 const Plane &p = p_planes[i];
685 if (p.is_point_over(point)) return false;
686 }
687 }
688
689 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
690
691 } else {
692
693 stack[level] = (VISIT_LEFT_BIT << VISITED_BIT_SHIFT) | node;
694 }
695 }
696 continue;
697 }
698 case VISIT_LEFT_BIT: {
699
700 stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node;
701 stack[level + 1] = b.left | TEST_AABB_BIT;
702 level++;
703 continue;
704 }
705 case VISIT_RIGHT_BIT: {
706
707 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
708 stack[level + 1] = b.right | TEST_AABB_BIT;
709 level++;
710 continue;
711 }
712 case VISIT_DONE_BIT: {
713
714 if (level == 0) {
715 done = true;
716 break;
717 } else
718 level--;
719 continue;
720 }
721 }
722
723 if (done)
724 break;
725 }
726
727 return true;
728 }
729
is_valid() const730 bool TriangleMesh::is_valid() const {
731
732 return valid;
733 }
734
get_faces() const735 PoolVector<Face3> TriangleMesh::get_faces() const {
736
737 if (!valid)
738 return PoolVector<Face3>();
739
740 PoolVector<Face3> faces;
741 int ts = triangles.size();
742 faces.resize(triangles.size());
743
744 PoolVector<Face3>::Write w = faces.write();
745 PoolVector<Triangle>::Read r = triangles.read();
746 PoolVector<Vector3>::Read rv = vertices.read();
747
748 for (int i = 0; i < ts; i++) {
749 for (int j = 0; j < 3; j++) {
750 w[i].vertex[j] = rv[r[i].indices[j]];
751 }
752 }
753
754 w.release();
755 return faces;
756 }
757
TriangleMesh()758 TriangleMesh::TriangleMesh() {
759
760 valid = false;
761 max_depth = 0;
762 }
763