Blender V5.3
dualcon/intern/octree.cpp
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2011-2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#include "octree.h"
6#include "Queue.h"
7
8#include <Eigen/Dense>
9#include <algorithm>
10#include <ctime>
11
17
18/* set to non-zero value to enable debugging output */
19#define DC_DEBUG 0
20
21#if DC_DEBUG
22/* enable debug printfs */
23# define dc_printf printf
24#else
25/* disable debug printfs */
26# define dc_printf(...) \
27 do { \
28 } while (0)
29#endif
30
32 DualConAllocOutput alloc_output_func,
33 DualConAddVert add_vert_func,
34 DualConAddQuad add_quad_func,
35 DualConFlags flags,
36 DualConMode dualcon_mode,
37 int depth,
38 float threshold,
39 float sharpness)
41 /* note on `use_manifold':
42
43 After playing around with this option, the only case I could
44 find where this option gives different results is on
45 relatively thin corners. Sometimes along these corners two
46 vertices from separate sides will be placed in the same
47 position, so hole gets filled with a 5-sided face, where two
48 of those vertices are in the same 3D location. If
49 `use_manifold' is disabled, then the modifier doesn't
50 generate two separate vertices so the results end up as all
51 quads.
52
53 Since the results are just as good with all quads, there
54 doesn't seem any reason to allow this to be toggled in
55 Blender. -nicholasbishop
56 */
57 use_manifold(false),
58 hermite_num(sharpness),
59 mode(dualcon_mode),
60 alloc_output(alloc_output_func),
61 add_vert(add_vert_func),
62 add_quad(add_quad_func)
63{
64 thresh = threshold;
65 reader = mr;
66 dimen = 1 << GRID_DIMENSION;
68 nodeCount = nodeSpace = 0;
69 maxDepth = depth;
70 mindimen = (dimen >> maxDepth);
72 buildTable();
73
75
76 // Initialize memory
77#ifdef IN_VERBOSE_MODE
78 dc_printf("Range: %f origin: %f, %f,%f \n", range, origin[0], origin[1], origin[2]);
79 dc_printf("Initialize memory...\n");
80#endif
81 initMemory();
82 root = (Node *)createInternal(0);
83
84 // Read MC table
85#ifdef IN_VERBOSE_MODE
86 dc_printf("Reading contour table...\n");
87#endif
88 cubes = new Cubes();
89}
90
92{
93 delete cubes;
94 freeMemory();
95}
96
98{
99 // Scan triangles
100#if DC_DEBUG
101 clock_t start, finish;
102 start = clock();
103#endif
104
105 addAllTriangles();
106 resetMinimalEdges();
107 preparePrimalEdgesMask(&root->internal);
108
109#if DC_DEBUG
110 finish = clock();
111 dc_printf("Time taken: %f seconds \n",
112 (double)(finish - start) / CLOCKS_PER_SEC);
113#endif
114
115 // Generate signs
116 // Find holes
117#if DC_DEBUG
118 dc_printf("Patching...\n");
119 start = clock();
120#endif
121 trace();
122#if DC_DEBUG
123 finish = clock();
124 dc_printf("Time taken: %f seconds \n", (double)(finish - start) / CLOCKS_PER_SEC);
125# ifdef IN_VERBOSE_MODE
126 dc_printf("Holes: %d Average Length: %f Max Length: %d \n",
127 numRings,
128 (float)totRingLengths / (float)numRings,
129 maxRingLength);
130# endif
131#endif
132
133 // Check again
134 int tnumRings = numRings;
135 trace();
136#ifdef IN_VERBOSE_MODE
137 dc_printf("Holes after patching: %d \n", numRings);
138#endif
139 numRings = tnumRings;
140
141#if DC_DEBUG
142 dc_printf("Building signs...\n");
143 start = clock();
144#endif
145 buildSigns();
146#if DC_DEBUG
147 finish = clock();
148 dc_printf("Time taken: %f seconds \n", (double)(finish - start) / CLOCKS_PER_SEC);
149#endif
150
151 if (use_flood_fill) {
152 /*
153 start = clock();
154 floodFill();
155 // Check again
156 tnumRings = numRings;
157 trace();
158 dc_printf("Holes after filling: %d \n", numRings);
159 numRings = tnumRings;
160 buildSigns();
161 finish = clock();
162 dc_printf("Time taken: %f seconds \n", (double)(finish - start) / CLOCKS_PER_SEC);
163 */
164#if DC_DEBUG
165 start = clock();
166 dc_printf("Removing components...\n");
167#endif
168 floodFill();
169 buildSigns();
170 // dc_printf("Checking...\n");
171 // floodFill();
172#if DC_DEBUG
173 finish = clock();
174 dc_printf("Time taken: %f seconds \n", (double)(finish - start) / CLOCKS_PER_SEC);
175#endif
176 }
177
178 // Output
179#if DC_DEBUG
180 start = clock();
181#endif
182 writeOut();
183#if DC_DEBUG
184 finish = clock();
185#endif
186 // dc_printf("Time taken: %f seconds \n", (double)(finish - start) / CLOCKS_PER_SEC);
187
188 // Print info
189#ifdef IN_VERBOSE_MODE
190 printMemUsage();
191#endif
192}
193
194void Octree::initMemory()
195{
200
210}
211
212void Octree::freeMemory()
213{
214 for (int i = 0; i < 9; i++) {
215 alloc[i]->destroy();
216 delete alloc[i];
217 }
218
219 for (int i = 0; i < 4; i++) {
220 leafalloc[i]->destroy();
221 delete leafalloc[i];
222 }
223}
224
225void Octree::printMemUsage()
226{
227 int totalbytes = 0;
228 dc_printf("********* Internal nodes: \n");
229 for (int i = 0; i < 9; i++) {
230 alloc[i]->printInfo();
231
232 totalbytes += alloc[i]->getAll() * alloc[i]->getBytes();
233 }
234 dc_printf("********* Leaf nodes: \n");
235 int totalLeafs = 0;
236 for (int i = 0; i < 4; i++) {
237 leafalloc[i]->printInfo();
238
239 totalbytes += leafalloc[i]->getAll() * leafalloc[i]->getBytes();
240 totalLeafs += leafalloc[i]->getAllocated();
241 }
242
243 dc_printf("Total allocated bytes on disk: %d \n", totalbytes);
244 dc_printf("Total leaf nodes: %d\n", totalLeafs);
245
246 /* Unused when not debuggining. */
247 (void)totalbytes;
248 (void)totalLeafs;
249}
250
251void Octree::resetMinimalEdges()
252{
253 cellProcParity(root, 0, maxDepth);
254}
255
256void Octree::addAllTriangles()
257{
258 Triangle *trian;
259 int count = 0;
260
261#if DC_DEBUG
262 int total = reader->getNumTriangles();
263 int unitcount = 1000;
264 dc_printf("\nScan converting to depth %d...\n", maxDepth);
265#endif
266
267 srand(0);
268
269 while ((trian = reader->getNextTriangle()) != nullptr) {
270 // Drop triangles
271 {
272 addTriangle(trian, count);
273 }
274 delete trian;
275
276 count++;
277
278#if DC_DEBUG
279 if (count % unitcount == 0) {
280 putchar(13);
281
282 switch ((count / unitcount) % 4) {
283 case 0:
284 dc_printf("-");
285 break;
286 case 1:
287 dc_printf("/");
288 break;
289 case 2:
290 dc_printf("|");
291 break;
292 case 3:
293 dc_printf("\\");
294 break;
295 }
296
297 float percent = (float)count / total;
298
299 /*
300 int totbars = 50;
301 int bars =(int)(percent * totbars);
302 for(int i = 0; i < bars; i ++) {
303 putchar(219);
304 }
305 for(i = bars; i < totbars; i ++) {
306 putchar(176);
307 }
308 */
309
310 dc_printf(" %d triangles: ", count);
311 dc_printf(" %f%% complete.", 100 * percent);
312 }
313#endif
314 }
315 putchar(13);
316}
317
318/* Prepare a triangle for insertion into the octree; call the other
319 addTriangle() to (recursively) build the octree */
320void Octree::addTriangle(Triangle *trian, int triind)
321{
322 int i, j;
323
324 /* Project the triangle's coordinates into the grid */
325 for (i = 0; i < 3; i++) {
326 for (j = 0; j < 3; j++) {
327 trian->vt[i][j] = dimen * (trian->vt[i][j] - origin[j]) / range;
328 }
329 }
330
331 /* Generate projections */
332 int64_t cube[2][3] = {{0, 0, 0}, {dimen, dimen, dimen}};
333 int64_t trig[3][3];
334 for (i = 0; i < 3; i++) {
335 for (j = 0; j < 3; j++) {
336 trig[i][j] = (int64_t)(trian->vt[i][j]);
337 }
338 }
339
340 /* Add triangle to the octree */
341 int64_t errorvec = (int64_t)(0);
342 CubeTriangleIsect *proj = new CubeTriangleIsect(cube, trig, errorvec, triind);
343 root = (Node *)addTriangle(&root->internal, proj, maxDepth);
344
345 delete proj->inherit;
346 delete proj;
347}
348
349#if 0
350static void print_depth(int height, int maxDepth)
351{
352 for (int i = 0; i < maxDepth - height; i++) {
353 printf(" ");
354 }
355}
356#endif
357
358InternalNode *Octree::addTriangle(InternalNode *node, CubeTriangleIsect *p, int height)
359{
360 int i;
361 const int vertdiff[8][3] = {
362 {0, 0, 0}, {0, 0, 1}, {0, 1, -1}, {0, 0, 1}, {1, -1, -1}, {0, 0, 1}, {0, 1, -1}, {0, 0, 1}};
363 unsigned char boxmask = p->getBoxMask();
364 CubeTriangleIsect *subp = new CubeTriangleIsect(p);
365
366 int count = 0;
367 int tempdiff[3] = {0, 0, 0};
368
369 /* Check triangle against each of the input node's children */
370 for (i = 0; i < 8; i++) {
371 tempdiff[0] += vertdiff[i][0];
372 tempdiff[1] += vertdiff[i][1];
373 tempdiff[2] += vertdiff[i][2];
374
375 /* Quick pruning using bounding box */
376 if (boxmask & (1 << i)) {
377 subp->shift(tempdiff);
378 tempdiff[0] = tempdiff[1] = tempdiff[2] = 0;
379
380 /* Pruning using intersection test */
381 if (subp->isIntersecting()) {
382 if (!node->has_child(i)) {
383 if (height == 1) {
384 node = addLeafChild(node, i, count, createLeaf(0));
385 }
386 else {
387 node = addInternalChild(node, i, count, createInternal(0));
388 }
389 }
390 Node *chd = node->get_child(count);
391
392 if (node->is_child_leaf(i)) {
393 node->set_child(count, (Node *)updateCell(&chd->leaf, subp));
394 }
395 else {
396 node->set_child(count, (Node *)addTriangle(&chd->internal, subp, height - 1));
397 }
398 }
399 }
400
401 if (node->has_child(i)) {
402 count++;
403 }
404 }
405
406 delete subp;
407
408 return node;
409}
410
411LeafNode *Octree::updateCell(LeafNode *node, CubeTriangleIsect *p)
412{
413 int i;
414
415 // Edge connectivity
416 int mask[3] = {0, 4, 8};
417 int oldc = 0, newc = 0;
418 float offs[3];
419 float a[3], b[3], c[3];
420
421 for (i = 0; i < 3; i++) {
422 if (!getEdgeParity(node, mask[i])) {
423 if (p->isIntersectingPrimary(i)) {
424 // actualQuads ++;
425 setEdge(node, mask[i]);
426 offs[newc] = p->getIntersectionPrimary(i);
427 a[newc] = (float)p->inherit->norm[0];
428 b[newc] = (float)p->inherit->norm[1];
429 c[newc] = (float)p->inherit->norm[2];
430 newc++;
431 }
432 }
433 else {
434 offs[newc] = getEdgeOffsetNormal(node, oldc, a[newc], b[newc], c[newc]);
435
436 oldc++;
437 newc++;
438 }
439 }
440
441 if (newc > oldc) {
442 // New offsets added, update this node
443 node = updateEdgeOffsetsNormals(node, oldc, newc, offs, a, b, c);
444 }
445
446 return node;
447}
448
449void Octree::preparePrimalEdgesMask(InternalNode *node)
450{
451 int count = 0;
452 for (int i = 0; i < 8; i++) {
453 if (node->has_child(i)) {
454 if (node->is_child_leaf(i)) {
455 createPrimalEdgesMask(&node->get_child(count)->leaf);
456 }
457 else {
458 preparePrimalEdgesMask(&node->get_child(count)->internal);
459 }
460
461 count++;
462 }
463 }
464}
465
466void Octree::trace()
467{
468 int st[3] = {
469 0,
470 0,
471 0,
472 };
473 numRings = 0;
474 totRingLengths = 0;
475 maxRingLength = 0;
476
477 PathList *chdpath = nullptr;
478 root = trace(root, st, dimen, maxDepth, chdpath);
479
480 if (chdpath != nullptr) {
481 dc_printf("there are incomplete rings.\n");
482 printPaths(chdpath);
483 }
484}
485
486Node *Octree::trace(Node *newnode, int *st, int len, int depth, PathList *&paths)
487{
488 len >>= 1;
489 PathList *chdpaths[8];
490 Node *chd[8];
491 int nst[8][3];
492 int i, j;
493
494 // Get children paths
495 int chdleaf[8];
496 newnode->internal.fill_children(chd, chdleaf);
497
498 // int count = 0;
499 for (i = 0; i < 8; i++) {
500 for (j = 0; j < 3; j++) {
501 nst[i][j] = st[j] + len * vertmap[i][j];
502 }
503
504 if (chd[i] == nullptr || newnode->internal.is_child_leaf(i)) {
505 chdpaths[i] = nullptr;
506 }
507 else {
508 trace(chd[i], nst[i], len, depth - 1, chdpaths[i]);
509 }
510 }
511
512 // Get connectors on the faces
513 PathList *conn[12];
514 Node *nf[2];
515 int lf[2];
516 int df[2] = {depth - 1, depth - 1};
517 int *nstf[2];
518
519 newnode->internal.fill_children(chd, chdleaf);
520
521 for (i = 0; i < 12; i++) {
522 int c[2] = {cellProcFaceMask[i][0], cellProcFaceMask[i][1]};
523
524 for (int j = 0; j < 2; j++) {
525 lf[j] = chdleaf[c[j]];
526 nf[j] = chd[c[j]];
527 nstf[j] = nst[c[j]];
528 }
529
530 conn[i] = nullptr;
531
532 findPaths((Node **)nf, lf, df, nstf, depth - 1, cellProcFaceMask[i][2], conn[i]);
533
534#if 0
535 if (conn[i]) {
536 printPath(conn[i]);
537 }
538#endif
539 }
540
541 // Connect paths
542 PathList *rings = nullptr;
543 combinePaths(chdpaths[0], chdpaths[1], conn[8], rings);
544 combinePaths(chdpaths[2], chdpaths[3], conn[9], rings);
545 combinePaths(chdpaths[4], chdpaths[5], conn[10], rings);
546 combinePaths(chdpaths[6], chdpaths[7], conn[11], rings);
547
548 combinePaths(chdpaths[0], chdpaths[2], conn[4], rings);
549 combinePaths(chdpaths[4], chdpaths[6], conn[5], rings);
550 combinePaths(chdpaths[0], nullptr, conn[6], rings);
551 combinePaths(chdpaths[4], nullptr, conn[7], rings);
552
553 combinePaths(chdpaths[0], chdpaths[4], conn[0], rings);
554 combinePaths(chdpaths[0], nullptr, conn[1], rings);
555 combinePaths(chdpaths[0], nullptr, conn[2], rings);
556 combinePaths(chdpaths[0], nullptr, conn[3], rings);
557
558 // By now, only chdpaths[0] and rings have contents
559
560 // Process rings
561 if (rings) {
562 // printPath(rings);
563
564 /* Let's count first */
565 PathList *trings = rings;
566 while (trings) {
567 numRings++;
568 totRingLengths += trings->length;
569 maxRingLength = std::max(trings->length, maxRingLength);
570 trings = trings->next;
571 }
572
573 // printPath(rings);
574 newnode = patch(newnode, st, (len << 1), rings);
575 }
576
577 // Return incomplete paths
578 paths = chdpaths[0];
579 return newnode;
580}
581
582void Octree::findPaths(Node *node[2],
583 const int leaf[2],
584 const int depth[2],
585 int *st[2],
586 int maxdep,
587 int dir,
588 PathList *&paths)
589{
590 if (!(node[0] && node[1])) {
591 return;
592 }
593
594 if (!(leaf[0] && leaf[1])) {
595 // Not at the bottom, recur
596
597 // Fill children nodes
598 int i, j;
599 Node *chd[2][8];
600 int chdleaf[2][8];
601 int nst[2][8][3];
602
603 for (j = 0; j < 2; j++) {
604 if (!leaf[j]) {
605 node[j]->internal.fill_children(chd[j], chdleaf[j]);
606
607 int len = (dimen >> (maxDepth - depth[j] + 1));
608 for (i = 0; i < 8; i++) {
609 for (int k = 0; k < 3; k++) {
610 nst[j][i][k] = st[j][k] + len * vertmap[i][k];
611 }
612 }
613 }
614 }
615
616 // 4 face calls
617 Node *nf[2];
618 int df[2];
619 int lf[2];
620 int *nstf[2];
621 for (i = 0; i < 4; i++) {
622 int c[2] = {faceProcFaceMask[dir][i][0], faceProcFaceMask[dir][i][1]};
623 for (int j = 0; j < 2; j++) {
624 if (leaf[j]) {
625 lf[j] = leaf[j];
626 nf[j] = node[j];
627 df[j] = depth[j];
628 nstf[j] = st[j];
629 }
630 else {
631 lf[j] = chdleaf[j][c[j]];
632 nf[j] = chd[j][c[j]];
633 df[j] = depth[j] - 1;
634 nstf[j] = nst[j][c[j]];
635 }
636 }
637 findPaths(nf, lf, df, nstf, maxdep - 1, faceProcFaceMask[dir][i][2], paths);
638 }
639 }
640 else {
641 // At the bottom, check this face
642 int ind = (depth[0] == maxdep ? 0 : 1);
643 int fcind = 2 * dir + (1 - ind);
644 if (getFaceParity((LeafNode *)node[ind], fcind)) {
645 // Add into path
646 PathElement *ele1 = new PathElement;
647 PathElement *ele2 = new PathElement;
648
649 ele1->pos[0] = st[0][0];
650 ele1->pos[1] = st[0][1];
651 ele1->pos[2] = st[0][2];
652
653 ele2->pos[0] = st[1][0];
654 ele2->pos[1] = st[1][1];
655 ele2->pos[2] = st[1][2];
656
657 ele1->next = ele2;
658 ele2->next = nullptr;
659
660 PathList *lst = new PathList;
661 lst->head = ele1;
662 lst->tail = ele2;
663 lst->length = 2;
664 lst->next = paths;
665 paths = lst;
666
667 // int l =(dimen >> maxDepth);
668 }
669 }
670}
671
672void Octree::combinePaths(PathList *&list1, PathList *list2, PathList *paths, PathList *&rings)
673{
674 // Make new list of paths
675 PathList *nlist = nullptr;
676
677 // Search for each connectors in paths
678 PathList *tpaths = paths;
679 PathList *tlist, *pre;
680 while (tpaths) {
681 PathList *singlist = tpaths;
682 PathList *templist;
683 tpaths = tpaths->next;
684 singlist->next = nullptr;
685
686 // Look for hookup in list1
687 tlist = list1;
688 pre = nullptr;
689 while (tlist) {
690 if ((templist = combineSinglePath(list1, pre, tlist, singlist, nullptr, singlist)) !=
691 nullptr)
692 {
693 singlist = templist;
694 continue;
695 }
696 pre = tlist;
697 tlist = tlist->next;
698 }
699
700 // Look for hookup in list2
701 tlist = list2;
702 pre = nullptr;
703 while (tlist) {
704 if ((templist = combineSinglePath(list2, pre, tlist, singlist, nullptr, singlist)) !=
705 nullptr)
706 {
707 singlist = templist;
708 continue;
709 }
710 pre = tlist;
711 tlist = tlist->next;
712 }
713
714 // Look for hookup in nlist
715 tlist = nlist;
716 pre = nullptr;
717 while (tlist) {
718 if ((templist = combineSinglePath(nlist, pre, tlist, singlist, nullptr, singlist)) !=
719 nullptr)
720 {
721 singlist = templist;
722 continue;
723 }
724 pre = tlist;
725 tlist = tlist->next;
726 }
727
728 // Add to nlist or rings
729 if (isEqual(singlist->head, singlist->tail)) {
730 PathElement *temp = singlist->head;
731 singlist->head = temp->next;
732 delete temp;
733 singlist->length--;
734 singlist->tail->next = singlist->head;
735
736 singlist->next = rings;
737 rings = singlist;
738 }
739 else {
740 singlist->next = nlist;
741 nlist = singlist;
742 }
743 }
744
745 // Append list2 and nlist to the end of list1
746 tlist = list1;
747 if (tlist != nullptr) {
748 while (tlist->next != nullptr) {
749 tlist = tlist->next;
750 }
751 tlist->next = list2;
752 }
753 else {
754 tlist = list2;
755 list1 = list2;
756 }
757
758 if (tlist != nullptr) {
759 while (tlist->next != nullptr) {
760 tlist = tlist->next;
761 }
762 tlist->next = nlist;
763 }
764 else {
765 tlist = nlist;
766 list1 = nlist;
767 }
768}
769
770PathList *Octree::combineSinglePath(PathList *&head1,
771 PathList *pre1,
772 PathList *&list1,
773 PathList *&head2,
774 PathList *pre2,
775 PathList *&list2)
776{
777 if (isEqual(list1->head, list2->head) || isEqual(list1->tail, list2->tail)) {
778 // Reverse the list
779 if (list1->length < list2->length) {
780 // Reverse list1
781 PathElement *prev = list1->head;
782 PathElement *next = prev->next;
783 prev->next = nullptr;
784 while (next != nullptr) {
785 PathElement *tnext = next->next;
786 next->next = prev;
787
788 prev = next;
789 next = tnext;
790 }
791
792 list1->tail = list1->head;
793 list1->head = prev;
794 }
795 else {
796 // Reverse list2
797 PathElement *prev = list2->head;
798 PathElement *next = prev->next;
799 prev->next = nullptr;
800 while (next != nullptr) {
801 PathElement *tnext = next->next;
802 next->next = prev;
803
804 prev = next;
805 next = tnext;
806 }
807
808 list2->tail = list2->head;
809 list2->head = prev;
810 }
811 }
812
813 if (isEqual(list1->head, list2->tail)) {
814
815 // Easy case
816 PathElement *temp = list1->head->next;
817 delete list1->head;
818 list2->tail->next = temp;
819
820 PathList *nlist = new PathList;
821 nlist->length = list1->length + list2->length - 1;
822 nlist->head = list2->head;
823 nlist->tail = list1->tail;
824 nlist->next = nullptr;
825
826 deletePath(head1, pre1, list1);
827 deletePath(head2, pre2, list2);
828
829 return nlist;
830 }
831 if (isEqual(list1->tail, list2->head)) {
832 // Easy case
833 PathElement *temp = list2->head->next;
834 delete list2->head;
835 list1->tail->next = temp;
836
837 PathList *nlist = new PathList;
838 nlist->length = list1->length + list2->length - 1;
839 nlist->head = list1->head;
840 nlist->tail = list2->tail;
841 nlist->next = nullptr;
842
843 deletePath(head1, pre1, list1);
844 deletePath(head2, pre2, list2);
845
846 return nlist;
847 }
848
849 return nullptr;
850}
851
852void Octree::deletePath(PathList *&head, PathList *pre, PathList *&curr)
853{
854 PathList *temp = curr;
855 curr = temp->next;
856 delete temp;
857
858 if (pre == nullptr) {
859 head = curr;
860 }
861 else {
862 pre->next = curr;
863 }
864}
865
866void Octree::printElement(PathElement *ele)
867{
868 if (ele != nullptr) {
869 dc_printf("(%d %d %d)", ele->pos[0], ele->pos[1], ele->pos[2]);
870 }
871}
872
873void Octree::printPath(PathList *path)
874{
875 PathElement *n = path->head;
876 int same = 0;
877
878#if DC_DEBUG
879 int len = (dimen >> maxDepth);
880#endif
881 while (n && (same == 0 || n != path->head)) {
882 same++;
883 dc_printf("(%d %d %d)", n->pos[0] / len, n->pos[1] / len, n->pos[2] / len);
884 n = n->next;
885 }
886
887 if (n == path->head) {
888 dc_printf(" Ring!\n");
889 }
890 else {
891 dc_printf(" %p end!\n", n);
892 }
893}
894
895void Octree::printPath(PathElement *path)
896{
897 PathElement *n = path;
898 int same = 0;
899#if DC_DEBUG
900 int len = (dimen >> maxDepth);
901#endif
902 while (n && (same == 0 || n != path)) {
903 same++;
904 dc_printf("(%d %d %d)", n->pos[0] / len, n->pos[1] / len, n->pos[2] / len);
905 n = n->next;
906 }
907
908 if (n == path) {
909 dc_printf(" Ring!\n");
910 }
911 else {
912 dc_printf(" %p end!\n", n);
913 }
914}
915
916void Octree::printPaths(PathList *path)
917{
918 PathList *iter = path;
919 while (iter != nullptr) {
920 dc_printf("Path %d:\n", i);
921 printPath(iter);
922 iter = iter->next;
923 }
924}
925
926Node *Octree::patch(Node *newnode, int st[3], int len, PathList *rings)
927{
928#ifdef IN_DEBUG_MODE
929 dc_printf("Call to PATCH with rings: \n");
930 printPaths(rings);
931#endif
932
933 /* Do nothing but couting
934 PathList* tlist = rings;
935 PathList* ttlist;
936 PathElement* telem, * ttelem;
937 while(tlist!= nullptr) {
938 // printPath(tlist);
939 numRings ++;
940 totRingLengths += tlist->length;
941 if(tlist->length > maxRingLength) {
942 maxRingLength = tlist->length;
943 }
944 ttlist = tlist;
945 tlist = tlist->next;
946 }
947 return node;
948 */
949
950 /* Pass onto separate calls in each direction */
951 if (len == mindimen) {
952 dc_printf("Error! should have no list by now.\n");
953 exit(0);
954 }
955
956 // YZ plane
957 PathList *xlists[2];
958 newnode = patchSplit(newnode, st, len, rings, 0, xlists[0], xlists[1]);
959
960 // XZ plane
961 PathList *ylists[4];
962 newnode = patchSplit(newnode, st, len, xlists[0], 1, ylists[0], ylists[1]);
963 newnode = patchSplit(newnode, st, len, xlists[1], 1, ylists[2], ylists[3]);
964
965 // XY plane
966 PathList *zlists[8];
967 newnode = patchSplit(newnode, st, len, ylists[0], 2, zlists[0], zlists[1]);
968 newnode = patchSplit(newnode, st, len, ylists[1], 2, zlists[2], zlists[3]);
969 newnode = patchSplit(newnode, st, len, ylists[2], 2, zlists[4], zlists[5]);
970 newnode = patchSplit(newnode, st, len, ylists[3], 2, zlists[6], zlists[7]);
971
972 // Recur
973 len >>= 1;
974 int count = 0;
975 for (int i = 0; i < 8; i++) {
976 if (zlists[i] != nullptr) {
977 int nori[3] = {
978 st[0] + len * vertmap[i][0], st[1] + len * vertmap[i][1], st[2] + len * vertmap[i][2]};
979 patch(newnode->internal.get_child(count), nori, len, zlists[i]);
980 }
981
982 if (newnode->internal.has_child(i)) {
983 count++;
984 }
985 }
986#ifdef IN_DEBUG_MODE
987 dc_printf("Return from PATCH\n");
988#endif
989 return newnode;
990}
991
992Node *Octree::patchSplit(Node *newnode,
993 int st[3],
994 int len,
995 PathList *rings,
996 int dir,
997 PathList *&nrings1,
998 PathList *&nrings2)
999{
1000#ifdef IN_DEBUG_MODE
1001 dc_printf("Call to PATCHSPLIT with direction %d and rings: \n", dir);
1002 printPaths(rings);
1003#endif
1004
1005 nrings1 = nullptr;
1006 nrings2 = nullptr;
1007 PathList *tmp;
1008 while (rings != nullptr) {
1009 // Process this ring
1010 newnode = patchSplitSingle(newnode, st, len, rings->head, dir, nrings1, nrings2);
1011
1012 // Delete this ring from the group
1013 tmp = rings;
1014 rings = rings->next;
1015 delete tmp;
1016 }
1017
1018#ifdef IN_DEBUG_MODE
1019 dc_printf("Return from PATCHSPLIT with \n");
1020 dc_printf("Rings group 1:\n");
1021 printPaths(nrings1);
1022 dc_printf("Rings group 2:\n");
1023 printPaths(nrings2);
1024#endif
1025
1026 return newnode;
1027}
1028
1029Node *Octree::patchSplitSingle(Node *newnode,
1030 int st[3],
1031 int len,
1032 PathElement *head,
1033 int dir,
1034 PathList *&nrings1,
1035 PathList *&nrings2)
1036{
1037#ifdef IN_DEBUG_MODE
1038 dc_printf("Call to PATCHSPLITSINGLE with direction %d and path: \n", dir);
1039 printPath(head);
1040#endif
1041
1042 if (head == nullptr) {
1043#ifdef IN_DEBUG_MODE
1044 dc_printf("Return from PATCHSPLITSINGLE with head==nullptr.\n");
1045#endif
1046 return newnode;
1047 }
1048
1049 // printPath(head);
1050
1051 // Walk along the ring to find pair of intersections
1052 PathElement *pre1 = nullptr;
1053 PathElement *pre2 = nullptr;
1054 int side = findPair(head, st[dir] + len / 2, dir, pre1, pre2);
1055
1056#if 0
1057 if (pre1 == pre2) {
1058 int edgelen = (dimen >> maxDepth);
1059 dc_printf("Location: %d %d %d Direction: %d Reso: %d\n",
1060 st[0] / edgelen,
1061 st[1] / edgelen,
1062 st[2] / edgelen,
1063 dir,
1064 len / edgelen);
1065 printPath(head);
1066 exit(0);
1067 }
1068#endif
1069
1070 if (side) {
1071 // Entirely on one side
1072 PathList *nring = new PathList();
1073 nring->head = head;
1074
1075 if (side == -1) {
1076 nring->next = nrings1;
1077 nrings1 = nring;
1078 }
1079 else {
1080 nring->next = nrings2;
1081 nrings2 = nring;
1082 }
1083 }
1084 else {
1085 // Break into two parts
1086 PathElement *nxt1 = pre1->next;
1087 PathElement *nxt2 = pre2->next;
1088 pre1->next = nxt2;
1089 pre2->next = nxt1;
1090
1091 newnode = connectFace(newnode, st, len, dir, pre1, pre2);
1092
1093 if (isEqual(pre1, pre1->next)) {
1094 if (pre1 == pre1->next) {
1095 delete pre1;
1096 pre1 = nullptr;
1097 }
1098 else {
1099 PathElement *temp = pre1->next;
1100 pre1->next = temp->next;
1101 delete temp;
1102 }
1103 }
1104 if (isEqual(pre2, pre2->next)) {
1105 if (pre2 == pre2->next) {
1106 delete pre2;
1107 pre2 = nullptr;
1108 }
1109 else {
1110 PathElement *temp = pre2->next;
1111 pre2->next = temp->next;
1112 delete temp;
1113 }
1114 }
1115
1116 compressRing(pre1);
1117 compressRing(pre2);
1118
1119 // Recur
1120 newnode = patchSplitSingle(newnode, st, len, pre1, dir, nrings1, nrings2);
1121 newnode = patchSplitSingle(newnode, st, len, pre2, dir, nrings1, nrings2);
1122 }
1123
1124#ifdef IN_DEBUG_MODE
1125 dc_printf("Return from PATCHSPLITSINGLE with \n");
1126 dc_printf("Rings group 1:\n");
1127 printPaths(nrings1);
1128 dc_printf("Rings group 2:\n");
1129 printPaths(nrings2);
1130#endif
1131
1132 return newnode;
1133}
1134
1135Node *Octree::connectFace(
1136 Node *newnode, int st[3], int len, int dir, PathElement *f1, PathElement *f2)
1137{
1138#ifdef IN_DEBUG_MODE
1139 dc_printf("Call to CONNECTFACE with direction %d and length %d path: \n", dir, len);
1140 dc_printf("Path(low side): \n");
1141 printPath(f1);
1142 // checkPath(f1);
1143 dc_printf("Path(high side): \n");
1144 printPath(f2);
1145// checkPath(f2);
1146#endif
1147
1148 // Setup 2D
1149 int pos = st[dir] + len / 2;
1150 int xdir = (dir + 1) % 3;
1151 int ydir = (dir + 2) % 3;
1152
1153 // Use existing intersections on f1 and f2
1154 int x1, y1, x2, y2;
1155 float p1, q1, p2, q2;
1156
1157 getFacePoint(f2->next, dir, x1, y1, p1, q1);
1158 getFacePoint(f2, dir, x2, y2, p2, q2);
1159
1160 float dx = x2 + p2 - x1 - p1;
1161 float dy = y2 + q2 - y1 - q1;
1162
1163 // Do adapted Bresenham line drawing
1164 float rx = p1, ry = q1;
1165 int incx = 1, incy = 1;
1166 int lx = x1, ly = y1;
1167 int hx = x2, hy = y2;
1168 int choice;
1169 if (x2 < x1) {
1170 incx = -1;
1171 rx = 1 - rx;
1172 lx = x2;
1173 hx = x1;
1174 }
1175 if (y2 < y1) {
1176 incy = -1;
1177 ry = 1 - ry;
1178 ly = y2;
1179 hy = y1;
1180 }
1181
1182 float sx = dx * incx;
1183 float sy = dy * incy;
1184
1185 int ori[3];
1186 ori[dir] = pos / mindimen;
1187 ori[xdir] = x1;
1188 ori[ydir] = y1;
1189 int walkdir;
1190 int inc;
1191 float alpha;
1192
1193 PathElement *curEleN = f1;
1194 PathElement *curEleP = f2->next;
1195 Node *nodeN = nullptr, *nodeP = nullptr;
1196 LeafNode *curN = locateLeaf(&newnode->internal, len, f1->pos);
1197 LeafNode *curP = locateLeaf(&newnode->internal, len, f2->next->pos);
1198 if (curN == nullptr || curP == nullptr) {
1199 exit(0);
1200 }
1201 int stN[3], stP[3];
1202 int lenN, lenP;
1203
1204 /* Unused code, leaving for posterity
1205
1206 float stpt[3], edpt[3];
1207 stpt[dir] = edpt[dir] =(float) pos;
1208 stpt[xdir] =(x1 + p1) * mindimen;
1209 stpt[ydir] =(y1 + q1) * mindimen;
1210 edpt[xdir] =(x2 + p2) * mindimen;
1211 edpt[ydir] =(y2 + q2) * mindimen;
1212 */
1213 while (ori[xdir] != x2 || ori[ydir] != y2) {
1214 int next;
1215 if (sy * (1 - rx) > sx * (1 - ry)) {
1216 choice = 1;
1217 next = ori[ydir] + incy;
1218 if (next < ly || next > hy) {
1219 choice = 4;
1220 next = ori[xdir] + incx;
1221 }
1222 }
1223 else {
1224 choice = 2;
1225 next = ori[xdir] + incx;
1226 if (next < lx || next > hx) {
1227 choice = 3;
1228 next = ori[ydir] + incy;
1229 }
1230 }
1231
1232 if (choice & 1) {
1233 ori[ydir] = next;
1234 if (choice == 1) {
1235 rx += (sy == 0 ? 0 : (1 - ry) * sx / sy);
1236 ry = 0;
1237 }
1238
1239 walkdir = 2;
1240 inc = incy;
1241 alpha = x2 < x1 ? 1 - rx : rx;
1242 }
1243 else {
1244 ori[xdir] = next;
1245 if (choice == 2) {
1246 ry += (sx == 0 ? 0 : (1 - rx) * sy / sx);
1247 rx = 0;
1248 }
1249
1250 walkdir = 1;
1251 inc = incx;
1252 alpha = y2 < y1 ? 1 - ry : ry;
1253 }
1254
1255 // Get the exact location of the marcher
1256 int nori[3] = {ori[0] * mindimen, ori[1] * mindimen, ori[2] * mindimen};
1257 float spt[3] = {(float)nori[0], (float)nori[1], (float)nori[2]};
1258 spt[(dir + (3 - walkdir)) % 3] += alpha * mindimen;
1259 if (inc < 0) {
1260 spt[(dir + walkdir) % 3] += mindimen;
1261 }
1262
1263#if 0
1264 dc_printf("new x,y: %d %d\n", ori[xdir] / edgelen, ori[ydir] / edgelen);
1265 dc_printf("nori: %d %d %d alpha: %f walkdir: %d\n", nori[0], nori[1], nori[2], alpha, walkdir);
1266 dc_printf("%f %f %f\n", spt[0], spt[1], spt[2]);
1267#endif
1268
1269 // Locate the current cells on both sides
1270 newnode = locateCell(&newnode->internal, st, len, nori, dir, 1, nodeN, stN, lenN);
1271 newnode = locateCell(&newnode->internal, st, len, nori, dir, 0, nodeP, stP, lenP);
1272
1273 updateParent(&newnode->internal, len, st);
1274
1275 // Add the cells to the rings and fill in the patch
1276 PathElement *newEleN;
1277 if (curEleN->pos[0] != stN[0] || curEleN->pos[1] != stN[1] || curEleN->pos[2] != stN[2]) {
1278 if (curEleN->next->pos[0] != stN[0] || curEleN->next->pos[1] != stN[1] ||
1279 curEleN->next->pos[2] != stN[2])
1280 {
1281 newEleN = new PathElement;
1282 newEleN->next = curEleN->next;
1283 newEleN->pos[0] = stN[0];
1284 newEleN->pos[1] = stN[1];
1285 newEleN->pos[2] = stN[2];
1286
1287 curEleN->next = newEleN;
1288 }
1289 else {
1290 newEleN = curEleN->next;
1291 }
1292 curN = patchAdjacent(&newnode->internal,
1293 len,
1294 curEleN->pos,
1295 curN,
1296 newEleN->pos,
1297 (LeafNode *)nodeN,
1298 walkdir,
1299 inc,
1300 dir,
1301 1,
1302 alpha);
1303
1304 curEleN = newEleN;
1305 }
1306
1307 PathElement *newEleP;
1308 if (curEleP->pos[0] != stP[0] || curEleP->pos[1] != stP[1] || curEleP->pos[2] != stP[2]) {
1309 if (f2->pos[0] != stP[0] || f2->pos[1] != stP[1] || f2->pos[2] != stP[2]) {
1310 newEleP = new PathElement;
1311 newEleP->next = curEleP;
1312 newEleP->pos[0] = stP[0];
1313 newEleP->pos[1] = stP[1];
1314 newEleP->pos[2] = stP[2];
1315
1316 f2->next = newEleP;
1317 }
1318 else {
1319 newEleP = f2;
1320 }
1321 curP = patchAdjacent(&newnode->internal,
1322 len,
1323 curEleP->pos,
1324 curP,
1325 newEleP->pos,
1326 (LeafNode *)nodeP,
1327 walkdir,
1328 inc,
1329 dir,
1330 0,
1331 alpha);
1332
1333 curEleP = newEleP;
1334 }
1335
1336 /*
1337 if(flag == 0) {
1338 dc_printf("error: non-synchronized patching! at \n");
1339 }
1340 */
1341 }
1342
1343#ifdef IN_DEBUG_MODE
1344 dc_printf("Return from CONNECTFACE with \n");
1345 dc_printf("Path(low side):\n");
1346 printPath(f1);
1347 checkPath(f1);
1348 dc_printf("Path(high side):\n");
1349 printPath(f2);
1350 checkPath(f2);
1351#endif
1352
1353 return newnode;
1354}
1355
1356LeafNode *Octree::patchAdjacent(InternalNode *node,
1357 int len,
1358 int st1[3],
1359 LeafNode *leaf1,
1360 int st2[3],
1361 LeafNode *leaf2,
1362 int walkdir,
1363 int inc,
1364 int dir,
1365 int side,
1366 float alpha)
1367{
1368#ifdef IN_DEBUG_MODE
1369 dc_printf("Before patching.\n");
1370 printInfo(st1);
1371 printInfo(st2);
1372 dc_printf(
1373 "-----------------%d %d %d; %d %d %d\n", st1[0], st2[1], st1[2], st2[0], st2[1], st2[2]);
1374#endif
1375
1376 // Get edge index on each leaf
1377 int edgedir = (dir + (3 - walkdir)) % 3;
1378 int incdir = (dir + walkdir) % 3;
1379 int ind1 = (edgedir == 1 ? (dir + 3 - edgedir) % 3 - 1 : 2 - (dir + 3 - edgedir) % 3);
1380 int ind2 = (edgedir == 1 ? (incdir + 3 - edgedir) % 3 - 1 : 2 - (incdir + 3 - edgedir) % 3);
1381
1382 int eind1 = ((edgedir << 2) | (side << ind1) | ((inc > 0 ? 1 : 0) << ind2));
1383 int eind2 = ((edgedir << 2) | (side << ind1) | ((inc > 0 ? 0 : 1) << ind2));
1384
1385#ifdef IN_DEBUG_MODE
1386 dc_printf("Index 1: %d Alpha 1: %f Index 2: %d Alpha 2: %f\n", eind1, alpha, eind2, alpha);
1387 /*
1388 if(alpha < 0 || alpha > 1) {
1389 dc_printf("Index 1: %d Alpha 1: %f Index 2: %d Alpha 2: %f\n", eind1, alpha, eind2, alpha);
1390 printInfo(st1);
1391 printInfo(st2);
1392 }
1393 */
1394#endif
1395
1396 // Flip edge parity
1397 LeafNode *nleaf1 = flipEdge(leaf1, eind1, alpha);
1398 LeafNode *nleaf2 = flipEdge(leaf2, eind2, alpha);
1399
1400 // Update parent link
1401 updateParent(node, len, st1, nleaf1);
1402 updateParent(node, len, st2, nleaf2);
1403 // updateParent(nleaf1, mindimen, st1);
1404 // updateParent(nleaf2, mindimen, st2);
1405
1406 /*
1407 float m[3];
1408 dc_printf("Adding new point: %f %f %f\n", spt[0], spt[1], spt[2]);
1409 getMinimizer(leaf1, m);
1410 dc_printf("Cell %d now has minimizer %f %f %f\n", leaf1, m[0], m[1], m[2]);
1411 getMinimizer(leaf2, m);
1412 dc_printf("Cell %d now has minimizer %f %f %f\n", leaf2, m[0], m[1], m[2]);
1413 */
1414
1415#ifdef IN_DEBUG_MODE
1416 dc_printf("After patching.\n");
1417 printInfo(st1);
1418 printInfo(st2);
1419#endif
1420 return nleaf2;
1421}
1422
1423Node *Octree::locateCell(InternalNode *node,
1424 const int st[3],
1425 int len,
1426 int ori[3],
1427 int dir,
1428 int side,
1429 Node *&rleaf,
1430 int rst[3],
1431 int &rlen)
1432{
1433#ifdef IN_DEBUG_MODE
1434 // dc_printf("Call to LOCATECELL with node ");
1435 // printNode(node);
1436#endif
1437
1438 int i;
1439 len >>= 1;
1440 int ind = 0;
1441 for (i = 0; i < 3; i++) {
1442 ind <<= 1;
1443 if (i == dir && side == 1) {
1444 ind |= (ori[i] <= (st[i] + len) ? 0 : 1);
1445 }
1446 else {
1447 ind |= (ori[i] < (st[i] + len) ? 0 : 1);
1448 }
1449 }
1450
1451#ifdef IN_DEBUG_MODE
1452# if 0
1453 dc_printf(
1454 "In LOCATECELL index of ori(%d %d %d) with dir %d side %d in st(%d %d %d, %d) is: %d\n",
1455 ori[0],
1456 ori[1],
1457 ori[2],
1458 dir,
1459 side,
1460 st[0],
1461 st[1],
1462 st[2],
1463 len,
1464 ind);
1465# endif
1466#endif
1467
1468 rst[0] = st[0] + vertmap[ind][0] * len;
1469 rst[1] = st[1] + vertmap[ind][1] * len;
1470 rst[2] = st[2] + vertmap[ind][2] * len;
1471
1472 if (node->has_child(ind)) {
1473 int count = node->get_child_count(ind);
1474 Node *chd = node->get_child(count);
1475 if (node->is_child_leaf(ind)) {
1476 rleaf = chd;
1477 rlen = len;
1478 }
1479 else {
1480 // Recur
1481 node->set_child(count,
1482 locateCell(&chd->internal, rst, len, ori, dir, side, rleaf, rst, rlen));
1483 }
1484 }
1485 else {
1486 // Create a new child here
1487 if (len == mindimen) {
1488 LeafNode *chd = createLeaf(0);
1489 node = addChild(node, ind, (Node *)chd, 1);
1490 rleaf = (Node *)chd;
1491 rlen = len;
1492 }
1493 else {
1494 // Subdivide the empty cube
1495 InternalNode *chd = createInternal(0);
1496 node = addChild(node, ind, locateCell(chd, rst, len, ori, dir, side, rleaf, rst, rlen), 0);
1497 }
1498 }
1499
1500#ifdef IN_DEBUG_MODE
1501 // dc_printf("Return from LOCATECELL with node ");
1502 // printNode(newnode);
1503#endif
1504 return (Node *)node;
1505}
1506
1507void Octree::checkElement(PathElement * /*ele*/)
1508{
1509#if 0
1510 if (ele != nullptr && locateLeafCheck(ele->pos) != ele->node) {
1511 dc_printf("Screwed! at pos: %d %d %d\n",
1512 ele->pos[0] >> minshift,
1513 ele->pos[1] >> minshift,
1514 ele->pos[2] >> minshift);
1515 exit(0);
1516 }
1517#endif
1518}
1519
1520void Octree::checkPath(PathElement *path)
1521{
1522 PathElement *n = path;
1523 int same = 0;
1524 while (n && (same == 0 || n != path)) {
1525 same++;
1526 checkElement(n);
1527 n = n->next;
1528 }
1529}
1530
1531void Octree::testFacePoint(PathElement *e1, PathElement *e2)
1532{
1533 int i;
1534 PathElement *e = nullptr;
1535 for (i = 0; i < 3; i++) {
1536 if (e1->pos[i] != e2->pos[i]) {
1537 if (e1->pos[i] < e2->pos[i]) {
1538 e = e2;
1539 }
1540 else {
1541 e = e1;
1542 }
1543 break;
1544 }
1545 }
1546
1547 int x, y;
1548 float p, q;
1549 dc_printf("Test.");
1550 getFacePoint(e, i, x, y, p, q);
1551}
1552
1553void Octree::getFacePoint(PathElement *leaf, int dir, int &x, int &y, float &p, float &q)
1554{
1555 // Find average intersections
1556 float avg[3] = {0, 0, 0};
1557 float off[3];
1558 int num = 0, num2 = 0;
1559
1560 (void)num2; // Unused in release builds.
1561
1562 LeafNode *leafnode = locateLeaf(leaf->pos);
1563 for (int i = 0; i < 4; i++) {
1564 int edgeind = faceMap[dir * 2][i];
1565 int nst[3];
1566 for (int j = 0; j < 3; j++) {
1567 nst[j] = leaf->pos[j] + mindimen * vertmap[edgemap[edgeind][0]][j];
1568 }
1569
1570 if (getEdgeIntersectionByIndex(nst, edgeind / 4, off, 1)) {
1571 avg[0] += off[0];
1572 avg[1] += off[1];
1573 avg[2] += off[2];
1574 num++;
1575 }
1576 if (getEdgeParity(leafnode, edgeind)) {
1577 num2++;
1578 }
1579 }
1580 if (num == 0) {
1581 dc_printf("Wrong! dir: %d pos: %d %d %d num: %d\n",
1582 dir,
1583 leaf->pos[0] >> minshift,
1584 leaf->pos[1] >> minshift,
1585 leaf->pos[2] >> minshift,
1586 num2);
1587 avg[0] = (float)leaf->pos[0];
1588 avg[1] = (float)leaf->pos[1];
1589 avg[2] = (float)leaf->pos[2];
1590 }
1591 else {
1592
1593 avg[0] /= num;
1594 avg[1] /= num;
1595 avg[2] /= num;
1596
1597 // avg[0] =(float) leaf->pos[0];
1598 // avg[1] =(float) leaf->pos[1];
1599 // avg[2] =(float) leaf->pos[2];
1600 }
1601
1602 int xdir = (dir + 1) % 3;
1603 int ydir = (dir + 2) % 3;
1604
1605 float xf = avg[xdir];
1606 float yf = avg[ydir];
1607
1608#ifdef IN_DEBUG_MODE
1609 // Is it outside?
1610 // PathElement* leaf = leaf1->len < leaf2->len ? leaf1 : leaf2;
1611# if 0
1612 float *m = (leaf == leaf1 ? m1 : m2);
1613 if (xf < leaf->pos[xdir] || yf < leaf->pos[ydir] || xf > leaf->pos[xdir] + leaf->len ||
1614 yf > leaf->pos[ydir] + leaf->len) {
1615 dc_printf("Outside cube(%d %d %d), %d : %d %d %f %f\n",
1616 leaf->pos[0],
1617 leaf->pos[1],
1618 leaf->pos[2],
1619 leaf->len,
1620 pos,
1621 dir,
1622 xf,
1623 yf);
1624
1625 // For now, snap to cell
1626 xf = m[xdir];
1627 yf = m[ydir];
1628 }
1629# endif
1630
1631# if 0
1632 if (alpha < 0 || alpha > 1 || xf < leaf->pos[xdir] || xf > leaf->pos[xdir] + leaf->len ||
1633 yf < leaf->pos[ydir] || yf > leaf->pos[ydir] + leaf->len) {
1634 dc_printf("Alpha: %f Address: %d and %d\n", alpha, leaf1->node, leaf2->node);
1635 dc_printf("GETFACEPOINT result:(%d %d %d) %d min:(%f %f %f);(%d %d %d) %d min:(%f %f %f).\n",
1636 leaf1->pos[0],
1637 leaf1->pos[1],
1638 leaf1->pos[2],
1639 leaf1->len,
1640 m1[0],
1641 m1[1],
1642 m1[2],
1643 leaf2->pos[0],
1644 leaf2->pos[1],
1645 leaf2->pos[2],
1646 leaf2->len,
1647 m2[0],
1648 m2[1],
1649 m2[2]);
1650 dc_printf("Face point at dir %d pos %d: %f %f\n", dir, pos, xf, yf);
1651 }
1652# endif
1653#endif
1654
1655 // Get the integer and float part
1656 x = ((leaf->pos[xdir]) >> minshift);
1657 y = ((leaf->pos[ydir]) >> minshift);
1658
1659 p = (xf - leaf->pos[xdir]) / mindimen;
1660 q = (yf - leaf->pos[ydir]) / mindimen;
1661
1662#ifdef IN_DEBUG_MODE
1663 dc_printf("Face point at dir %d : %f %f\n", dir, xf, yf);
1664#endif
1665}
1666
1667int Octree::findPair(PathElement *head, int pos, int dir, PathElement *&pre1, PathElement *&pre2)
1668{
1669 int side = getSide(head, pos, dir);
1670 PathElement *cur = head;
1671 PathElement *anchor;
1672 PathElement *ppre1, *ppre2;
1673
1674 // Start from this face, find a pair
1675 anchor = cur;
1676 ppre1 = cur;
1677 cur = cur->next;
1678 while (cur != anchor && (getSide(cur, pos, dir) == side)) {
1679 ppre1 = cur;
1680 cur = cur->next;
1681 }
1682 if (cur == anchor) {
1683 // No pair found
1684 return side;
1685 }
1686
1687 side = getSide(cur, pos, dir);
1688 ppre2 = cur;
1689 cur = cur->next;
1690 while (getSide(cur, pos, dir) == side) {
1691 ppre2 = cur;
1692 cur = cur->next;
1693 }
1694
1695 // Switch pre1 and pre2 if we start from the higher side
1696 if (side == -1) {
1697 cur = ppre1;
1698 ppre1 = ppre2;
1699 ppre2 = cur;
1700 }
1701
1702 pre1 = ppre1;
1703 pre2 = ppre2;
1704
1705 return 0;
1706}
1707
1708int Octree::getSide(PathElement *e, int pos, int dir)
1709{
1710 return (e->pos[dir] < pos ? -1 : 1);
1711}
1712
1713int Octree::isEqual(PathElement *e1, PathElement *e2)
1714{
1715 return (e1->pos[0] == e2->pos[0] && e1->pos[1] == e2->pos[1] && e1->pos[2] == e2->pos[2]);
1716}
1717
1718void Octree::compressRing(PathElement *&ring)
1719{
1720 if (ring == nullptr) {
1721 return;
1722 }
1723#ifdef IN_DEBUG_MODE
1724 dc_printf("Call to COMPRESSRING with path: \n");
1725 printPath(ring);
1726#endif
1727
1728 PathElement *cur = ring->next->next;
1729 PathElement *pre = ring->next;
1730 PathElement *prepre = ring;
1731 PathElement *anchor = prepre;
1732
1733 do {
1734 while (isEqual(cur, prepre)) {
1735 // Delete
1736 if (cur == prepre) {
1737 // The ring has shrinked to a point
1738 delete pre;
1739 delete cur;
1740 anchor = nullptr;
1741 break;
1742 }
1743 prepre->next = cur->next;
1744 delete pre;
1745 delete cur;
1746 pre = prepre->next;
1747 cur = pre->next;
1748 anchor = prepre;
1749 }
1750
1751 if (anchor == nullptr) {
1752 break;
1753 }
1754
1755 prepre = pre;
1756 pre = cur;
1757 cur = cur->next;
1758 } while (prepre != anchor);
1759
1760 ring = anchor;
1761
1762#ifdef IN_DEBUG_MODE
1763 dc_printf("Return from COMPRESSRING with path: \n");
1764 printPath(ring);
1765#endif
1766}
1767
1768void Octree::buildSigns()
1769{
1770 // First build a lookup table
1771 // dc_printf("Building up look up table...\n");
1772 int size = 1 << 12;
1773 unsigned char table[1 << 12];
1774 for (int i = 0; i < size; i++) {
1775 table[i] = 0;
1776 }
1777 for (int i = 0; i < 256; i++) {
1778 int ind = 0;
1779 for (int j = 11; j >= 0; j--) {
1780 ind <<= 1;
1781 if (((i >> edgemap[j][0]) & 1) ^ ((i >> edgemap[j][1]) & 1)) {
1782 ind |= 1;
1783 }
1784 }
1785
1786 table[ind] = i;
1787 }
1788
1789 // Next, traverse the grid
1790 int sg = 1;
1791 int cube[8];
1792 buildSigns(table, root, 0, sg, cube);
1793}
1794
1795void Octree::buildSigns(unsigned char table[], Node *node, int isLeaf, int sg, int rvalue[8])
1796{
1797 if (node == nullptr) {
1798 for (int i = 0; i < 8; i++) {
1799 rvalue[i] = sg;
1800 }
1801 return;
1802 }
1803
1804 if (isLeaf == 0) {
1805 // Internal node
1806 Node *chd[8];
1807 int leaf[8];
1808 node->internal.fill_children(chd, leaf);
1809
1810 // Get the signs at the corners of the first cube
1811 rvalue[0] = sg;
1812 int oris[8];
1813 buildSigns(table, chd[0], leaf[0], sg, oris);
1814
1815 // Get the rest
1816 int cube[8];
1817 for (int i = 1; i < 8; i++) {
1818 buildSigns(table, chd[i], leaf[i], oris[i], cube);
1819 rvalue[i] = cube[i];
1820 }
1821 }
1822 else {
1823 // Leaf node
1824 generateSigns(&node->leaf, table, sg);
1825
1826 for (int i = 0; i < 8; i++) {
1827 rvalue[i] = getSign(&node->leaf, i);
1828 }
1829 }
1830}
1831
1832void Octree::floodFill()
1833{
1834 // int threshold =(int)((dimen/mindimen) *(dimen/mindimen) * 0.5f);
1835 int st[3] = {0, 0, 0};
1836
1837 // First, check for largest component
1838 // size stored in -threshold
1839 clearProcessBits(root, maxDepth);
1840 int threshold = floodFill(root, st, dimen, maxDepth, 0);
1841
1842 // Next remove
1843 dc_printf("Largest component: %d\n", threshold);
1844 threshold *= thresh;
1845 dc_printf("Removing all components smaller than %d\n", threshold);
1846
1847 int st2[3] = {0, 0, 0};
1848 clearProcessBits(root, maxDepth);
1849 floodFill(root, st2, dimen, maxDepth, threshold);
1850}
1851
1852void Octree::clearProcessBits(Node *node, int height)
1853{
1854 int i;
1855
1856 if (height == 0) {
1857 // Leaf cell,
1858 for (i = 0; i < 12; i++) {
1859 setOutProcess(&node->leaf, i);
1860 }
1861 }
1862 else {
1863 // Internal cell, recur
1864 int count = 0;
1865 for (i = 0; i < 8; i++) {
1866 if (node->internal.has_child(i)) {
1867 clearProcessBits(node->internal.get_child(count), height - 1);
1868 count++;
1869 }
1870 }
1871 }
1872}
1873
1874int Octree::floodFill(LeafNode *leaf, const int st[3], int len, int /*height*/, int threshold)
1875{
1876 int i, j;
1877 int maxtotal = 0;
1878
1879 // Leaf cell,
1880 int par, inp;
1881
1882 // Test if the leaf has intersection edges
1883 for (i = 0; i < 12; i++) {
1884 par = getEdgeParity(leaf, i);
1885 inp = isInProcess(leaf, i);
1886
1887 if (par == 1 && inp == 0) {
1888 // Intersection edge, hasn't been processed
1889 // Let's start filling
1890 GridQueue *queue = new GridQueue();
1891 int total = 1;
1892
1893 // Set to in process
1894 int mst[3];
1895 mst[0] = st[0] + vertmap[edgemap[i][0]][0] * len;
1896 mst[1] = st[1] + vertmap[edgemap[i][0]][1] * len;
1897 mst[2] = st[2] + vertmap[edgemap[i][0]][2] * len;
1898 int mdir = i / 4;
1899 setInProcessAll(mst, mdir);
1900
1901 // Put this edge into queue
1902 queue->pushQueue(mst, mdir);
1903
1904 // Queue processing
1905 int nst[3], dir;
1906 while (queue->popQueue(nst, dir) == 1) {
1907#if 0
1908 dc_printf("nst: %d %d %d, dir: %d\n",
1909 nst[0] / mindimen,
1910 nst[1] / mindimen,
1911 nst[2] / mindimen,
1912 dir);
1913#endif
1914 // locations
1915 int stMask[3][3] = {{0, 0 - len, 0 - len}, {0 - len, 0, 0 - len}, {0 - len, 0 - len, 0}};
1916 int cst[2][3];
1917 for (j = 0; j < 3; j++) {
1918 cst[0][j] = nst[j];
1919 cst[1][j] = nst[j] + stMask[dir][j];
1920 }
1921
1922 // cells
1923 LeafNode *cs[2];
1924 for (j = 0; j < 2; j++) {
1925 cs[j] = locateLeaf(cst[j]);
1926 }
1927
1928 // Middle sign
1929 int s = getSign(cs[0], 0);
1930
1931 // Masks
1932 int fcCells[4] = {1, 0, 1, 0};
1933 int fcEdges[3][4][3] = {{{9, 2, 11}, {8, 1, 10}, {5, 1, 7}, {4, 2, 6}},
1934 {{10, 6, 11}, {8, 5, 9}, {1, 5, 3}, {0, 6, 2}},
1935 {{6, 10, 7}, {4, 9, 5}, {2, 9, 3}, {0, 10, 1}}};
1936
1937 // Search for neighboring connected intersection edges
1938 for (int find = 0; find < 4; find++) {
1939 int cind = fcCells[find];
1940 int eind, edge;
1941 if (s == 0) {
1942 // Original order
1943 for (eind = 0; eind < 3; eind++) {
1944 edge = fcEdges[dir][find][eind];
1945 if (getEdgeParity(cs[cind], edge) == 1) {
1946 break;
1947 }
1948 }
1949 }
1950 else {
1951 // Inverse order
1952 for (eind = 2; eind >= 0; eind--) {
1953 edge = fcEdges[dir][find][eind];
1954 if (getEdgeParity(cs[cind], edge) == 1) {
1955 break;
1956 }
1957 }
1958 }
1959
1960 if (eind == 3 || eind == -1) {
1961 dc_printf("Wrong! this is not a consistent sign. %d\n", eind);
1962 }
1963 else {
1964 int est[3];
1965 est[0] = cst[cind][0] + vertmap[edgemap[edge][0]][0] * len;
1966 est[1] = cst[cind][1] + vertmap[edgemap[edge][0]][1] * len;
1967 est[2] = cst[cind][2] + vertmap[edgemap[edge][0]][2] * len;
1968 int edir = edge / 4;
1969
1970 if (isInProcess(cs[cind], edge) == 0) {
1971 setInProcessAll(est, edir);
1972 queue->pushQueue(est, edir);
1973#if 0
1974 dc_printf("Pushed: est: %d %d %d, edir: %d\n",
1975 est[0] / len,
1976 est[1] / len,
1977 est[2] / len,
1978 edir);
1979#endif
1980 total++;
1981 }
1982 }
1983 }
1984 }
1985
1986 dc_printf("Size of component: %d ", total);
1987
1988 if (threshold == 0) {
1989 // Measuring stage
1990 maxtotal = std::max(total, maxtotal);
1991 dc_printf(".\n");
1992 delete queue;
1993 continue;
1994 }
1995
1996 if (total >= threshold) {
1997 dc_printf("Maintained.\n");
1998 delete queue;
1999 continue;
2000 }
2001 dc_printf("Less than %d, removing...\n", threshold);
2002
2003 // We have to remove this noise
2004
2005 // Flip parity
2006 // setOutProcessAll(mst, mdir);
2007 flipParityAll(mst, mdir);
2008
2009 // Put this edge into queue
2010 queue->pushQueue(mst, mdir);
2011
2012 // Queue processing
2013 while (queue->popQueue(nst, dir) == 1) {
2014#if 0
2015 dc_printf("nst: %d %d %d, dir: %d\n",
2016 nst[0] / mindimen,
2017 nst[1] / mindimen,
2018 nst[2] / mindimen,
2019 dir);
2020#endif
2021 // locations
2022 int stMask[3][3] = {{0, 0 - len, 0 - len}, {0 - len, 0, 0 - len}, {0 - len, 0 - len, 0}};
2023 int cst[2][3];
2024 for (j = 0; j < 3; j++) {
2025 cst[0][j] = nst[j];
2026 cst[1][j] = nst[j] + stMask[dir][j];
2027 }
2028
2029 // cells
2030 LeafNode *cs[2];
2031 for (j = 0; j < 2; j++) {
2032 cs[j] = locateLeaf(cst[j]);
2033 }
2034
2035 // Middle sign
2036 int s = getSign(cs[0], 0);
2037
2038 // Masks
2039 int fcCells[4] = {1, 0, 1, 0};
2040 int fcEdges[3][4][3] = {{{9, 2, 11}, {8, 1, 10}, {5, 1, 7}, {4, 2, 6}},
2041 {{10, 6, 11}, {8, 5, 9}, {1, 5, 3}, {0, 6, 2}},
2042 {{6, 10, 7}, {4, 9, 5}, {2, 9, 3}, {0, 10, 1}}};
2043
2044 // Search for neighboring connected intersection edges
2045 for (int find = 0; find < 4; find++) {
2046 int cind = fcCells[find];
2047 int eind, edge;
2048 if (s == 0) {
2049 // Original order
2050 for (eind = 0; eind < 3; eind++) {
2051 edge = fcEdges[dir][find][eind];
2052 if (isInProcess(cs[cind], edge) == 1) {
2053 break;
2054 }
2055 }
2056 }
2057 else {
2058 // Inverse order
2059 for (eind = 2; eind >= 0; eind--) {
2060 edge = fcEdges[dir][find][eind];
2061 if (isInProcess(cs[cind], edge) == 1) {
2062 break;
2063 }
2064 }
2065 }
2066
2067 if (eind == 3 || eind == -1) {
2068 dc_printf("Wrong! this is not a consistent sign. %d\n", eind);
2069 }
2070 else {
2071 int est[3];
2072 est[0] = cst[cind][0] + vertmap[edgemap[edge][0]][0] * len;
2073 est[1] = cst[cind][1] + vertmap[edgemap[edge][0]][1] * len;
2074 est[2] = cst[cind][2] + vertmap[edgemap[edge][0]][2] * len;
2075 int edir = edge / 4;
2076
2077 if (getEdgeParity(cs[cind], edge) == 1) {
2078 flipParityAll(est, edir);
2079 queue->pushQueue(est, edir);
2080#if 0
2081 dc_printf("Pushed: est: %d %d %d, edir: %d\n",
2082 est[0] / len,
2083 est[1] / len,
2084 est[2] / len,
2085 edir);
2086#endif
2087 total++;
2088 }
2089 }
2090 }
2091 }
2092
2093 delete queue;
2094 }
2095 }
2096
2097 return maxtotal;
2098}
2099
2100int Octree::floodFill(Node *node, int st[3], int len, int height, int threshold)
2101{
2102 int i;
2103 int maxtotal = 0;
2104
2105 if (height == 0) {
2106 maxtotal = floodFill(&node->leaf, st, len, height, threshold);
2107 }
2108 else {
2109 // Internal cell, recur
2110 int count = 0;
2111 len >>= 1;
2112 for (i = 0; i < 8; i++) {
2113 if (node->internal.has_child(i)) {
2114 int nst[3];
2115 nst[0] = st[0] + vertmap[i][0] * len;
2116 nst[1] = st[1] + vertmap[i][1] * len;
2117 nst[2] = st[2] + vertmap[i][2] * len;
2118
2119 int d = floodFill(node->internal.get_child(count), nst, len, height - 1, threshold);
2120 maxtotal = std::max(d, maxtotal);
2121 count++;
2122 }
2123 }
2124 }
2125
2126 return maxtotal;
2127}
2128
2129void Octree::writeOut()
2130{
2131 int numQuads = 0;
2132 int numVertices = 0;
2133 int numEdges = 0;
2134
2135 countIntersection(root, maxDepth, numQuads, numVertices, numEdges);
2136
2137 dc_printf("Vertices counted: %d Polys counted: %d \n", numVertices, numQuads);
2138 output_mesh = alloc_output(numVertices, numQuads);
2139 int offset = 0;
2140 int st[3] = {0, 0, 0};
2141
2142 // First, output vertices
2143 offset = 0;
2144 actualVerts = 0;
2145 actualQuads = 0;
2146
2147 generateMinimizer(root, st, dimen, maxDepth, offset);
2148 cellProcContour(root, 0, maxDepth);
2149 dc_printf("Vertices written: %d Quads written: %d \n", offset, actualQuads);
2150}
2151
2152void Octree::countIntersection(Node *node, int height, int &nedge, int &ncell, int &nface)
2153{
2154 if (height > 0) {
2155 int total = node->internal.get_num_children();
2156 for (int i = 0; i < total; i++) {
2157 countIntersection(node->internal.get_child(i), height - 1, nedge, ncell, nface);
2158 }
2159 }
2160 else {
2161 nedge += getNumEdges2(&node->leaf);
2162
2163 int smask = getSignMask(&node->leaf);
2164
2165 if (use_manifold) {
2166 int comps = manifold_table[smask].comps;
2167 ncell += comps;
2168 }
2169 else {
2170 if (smask > 0 && smask < 255) {
2171 ncell++;
2172 }
2173 }
2174
2175 for (int i = 0; i < 3; i++) {
2176 if (getFaceEdgeNum(&node->leaf, i * 2)) {
2177 nface++;
2178 }
2179 }
2180 }
2181}
2182
2183/* from http://eigen.tuxfamily.org/bz/show_bug.cgi?id=257 */
2184static void pseudoInverse(const Eigen::Matrix3f &a, Eigen::Matrix3f &result, float tolerance)
2185{
2186 const int Options = Eigen::ComputeFullU | Eigen::ComputeFullV;
2187 Eigen::JacobiSVD<Eigen::Matrix3f, Options> svd = a.jacobiSvd<Options>();
2188
2189 result = svd.matrixV() *
2190 Eigen::Vector3f((svd.singularValues().array().abs() > tolerance)
2191 .select(svd.singularValues().array().inverse(), 0))
2192 .asDiagonal() *
2193 svd.matrixU().adjoint();
2194}
2195
2196static void solve_least_squares(const float halfA[],
2197 const float b[],
2198 const float midpoint[],
2199 float rvalue[])
2200{
2201 /* calculate pseudo-inverse */
2202 Eigen::Matrix3f A, pinv;
2203 A << halfA[0], halfA[1], halfA[2], halfA[1], halfA[3], halfA[4], halfA[2], halfA[4], halfA[5];
2204 pseudoInverse(A, pinv, 0.1f);
2205
2206 Eigen::Vector3f b2(b), mp(midpoint), result;
2207 b2 = b2 + A * -mp;
2208 result = pinv * b2 + mp;
2209
2210 for (int i = 0; i < 3; i++) {
2211 rvalue[i] = result(i);
2212 }
2213}
2214
2215static void mass_point(float mp[3], const float pts[12][3], const int parity[12])
2216{
2217 int ec = 0;
2218
2219 for (int i = 0; i < 12; i++) {
2220 if (parity[i]) {
2221 const float *p = pts[i];
2222
2223 mp[0] += p[0];
2224 mp[1] += p[1];
2225 mp[2] += p[2];
2226
2227 ec++;
2228 }
2229 }
2230
2231 if (ec == 0) {
2232 return;
2233 }
2234 mp[0] /= ec;
2235 mp[1] /= ec;
2236 mp[2] /= ec;
2237}
2238
2239static void minimize(float rvalue[3],
2240 float mp[3],
2241 const float pts[12][3],
2242 const float norms[12][3],
2243 const int parity[12])
2244{
2245 float ata[6] = {0, 0, 0, 0, 0, 0};
2246 float atb[3] = {0, 0, 0};
2247 int ec = 0;
2248
2249 for (int i = 0; i < 12; i++) {
2250 // if(getEdgeParity(leaf, i))
2251 if (parity[i]) {
2252 const float *norm = norms[i];
2253 const float *p = pts[i];
2254
2255 // QEF
2256 ata[0] += (float)(norm[0] * norm[0]);
2257 ata[1] += (float)(norm[0] * norm[1]);
2258 ata[2] += (float)(norm[0] * norm[2]);
2259 ata[3] += (float)(norm[1] * norm[1]);
2260 ata[4] += (float)(norm[1] * norm[2]);
2261 ata[5] += (float)(norm[2] * norm[2]);
2262
2263 const float pn = p[0] * norm[0] + p[1] * norm[1] + p[2] * norm[2];
2264
2265 atb[0] += (float)(norm[0] * pn);
2266 atb[1] += (float)(norm[1] * pn);
2267 atb[2] += (float)(norm[2] * pn);
2268
2269 // Minimizer
2270 mp[0] += p[0];
2271 mp[1] += p[1];
2272 mp[2] += p[2];
2273
2274 ec++;
2275 }
2276 }
2277
2278 if (ec == 0) {
2279 return;
2280 }
2281 mp[0] /= ec;
2282 mp[1] /= ec;
2283 mp[2] /= ec;
2284
2285 // Solve least squares
2286 solve_least_squares(ata, atb, mp, rvalue);
2287}
2288
2289void Octree::computeMinimizer(const LeafNode *leaf, int st[3], int len, float rvalue[3]) const
2290{
2291 // First, gather all edge intersections
2292 float pts[12][3], norms[12][3];
2293 int parity[12];
2294 fillEdgeIntersections(leaf, st, len, pts, norms, parity);
2295
2296 switch (mode) {
2297 case DUALCON_CENTROID:
2298 rvalue[0] = (float)st[0] + len / 2;
2299 rvalue[1] = (float)st[1] + len / 2;
2300 rvalue[2] = (float)st[2] + len / 2;
2301 break;
2302
2303 case DUALCON_MASS_POINT:
2304 rvalue[0] = rvalue[1] = rvalue[2] = 0;
2305 mass_point(rvalue, pts, parity);
2306 break;
2307
2308 default: {
2309 // Sharp features */
2310
2311 // construct QEF and minimizer
2312 float mp[3] = {0, 0, 0};
2313 minimize(rvalue, mp, pts, norms, parity);
2314
2315 /* Restraining the location of the minimizer */
2316 float nh1 = hermite_num * len;
2317 float nh2 = (1 + hermite_num) * len;
2318
2319 if (rvalue[0] < st[0] - nh1 || rvalue[1] < st[1] - nh1 || rvalue[2] < st[2] - nh1 ||
2320
2321 rvalue[0] > st[0] + nh2 || rvalue[1] > st[1] + nh2 || rvalue[2] > st[2] + nh2)
2322 {
2323 // Use mass point instead
2324 rvalue[0] = mp[0];
2325 rvalue[1] = mp[1];
2326 rvalue[2] = mp[2];
2327 }
2328 break;
2329 }
2330 }
2331}
2332
2333void Octree::generateMinimizer(Node *node, int st[3], int len, int height, int &offset)
2334{
2335 int i, j;
2336
2337 if (height == 0) {
2338 // Leaf cell, generate
2339
2340 // First, find minimizer
2341 float rvalue[3];
2342 rvalue[0] = (float)st[0] + len / 2;
2343 rvalue[1] = (float)st[1] + len / 2;
2344 rvalue[2] = (float)st[2] + len / 2;
2345 computeMinimizer(&node->leaf, st, len, rvalue);
2346
2347 // Update
2348 // float fnst[3];
2349 for (j = 0; j < 3; j++) {
2350 rvalue[j] = rvalue[j] * range / dimen + origin[j];
2351 // fnst[j] = st[j] * range / dimen + origin[j];
2352 }
2353
2354 int mult = 0, smask = getSignMask(&node->leaf);
2355
2356 if (use_manifold) {
2357 mult = manifold_table[smask].comps;
2358 }
2359 else {
2360 if (smask > 0 && smask < 255) {
2361 mult = 1;
2362 }
2363 }
2364
2365 for (j = 0; j < mult; j++) {
2366 add_vert(output_mesh, rvalue);
2367 }
2368
2369 // Store the index
2370 setMinimizerIndex(&node->leaf, offset);
2371
2372 offset += mult;
2373 }
2374 else {
2375 // Internal cell, recur
2376 int count = 0;
2377 len >>= 1;
2378 for (i = 0; i < 8; i++) {
2379 if (node->internal.has_child(i)) {
2380 int nst[3];
2381 nst[0] = st[0] + vertmap[i][0] * len;
2382 nst[1] = st[1] + vertmap[i][1] * len;
2383 nst[2] = st[2] + vertmap[i][2] * len;
2384
2385 generateMinimizer(node->internal.get_child(count), nst, len, height - 1, offset);
2386 count++;
2387 }
2388 }
2389 }
2390}
2391
2392void Octree::processEdgeWrite(Node *node[4], int /*depth*/[4], int /*maxdep*/, int dir)
2393{
2394 // int color = 0;
2395
2396 int i = 3;
2397 {
2398 if (getEdgeParity((LeafNode *)(node[i]), processEdgeMask[dir][i])) {
2399 int flip = 0;
2400 int edgeind = processEdgeMask[dir][i];
2401 if (getSign((LeafNode *)node[i], edgemap[edgeind][1]) > 0) {
2402 flip = 1;
2403 }
2404
2405 int num = 0;
2406 {
2407 int ind[8];
2408 if (use_manifold) {
2409 int vind[2];
2410 int seq[4] = {0, 1, 3, 2};
2411 for (int k = 0; k < 4; k++) {
2412 getMinimizerIndices((LeafNode *)(node[seq[k]]), processEdgeMask[dir][seq[k]], vind);
2413 ind[num] = vind[0];
2414 num++;
2415
2416 if (vind[1] != -1) {
2417 ind[num] = vind[1];
2418 num++;
2419 if (flip == 0) {
2420 ind[num - 1] = vind[0];
2421 ind[num - 2] = vind[1];
2422 }
2423 }
2424 }
2425
2426 /* we don't use the manifold option, but if it is
2427 ever enabled again note that it can output
2428 non-quads */
2429 }
2430 else {
2431 if (flip) {
2432 ind[0] = getMinimizerIndex((LeafNode *)(node[2]));
2433 ind[1] = getMinimizerIndex((LeafNode *)(node[3]));
2434 ind[2] = getMinimizerIndex((LeafNode *)(node[1]));
2435 ind[3] = getMinimizerIndex((LeafNode *)(node[0]));
2436 }
2437 else {
2438 ind[0] = getMinimizerIndex((LeafNode *)(node[0]));
2439 ind[1] = getMinimizerIndex((LeafNode *)(node[1]));
2440 ind[2] = getMinimizerIndex((LeafNode *)(node[3]));
2441 ind[3] = getMinimizerIndex((LeafNode *)(node[2]));
2442 }
2443
2444 add_quad(output_mesh, ind);
2445 }
2446 }
2447 return;
2448 }
2449 return;
2450 }
2451}
2452
2453void Octree::edgeProcContour(Node *node[4], const int leaf[4], int depth[4], int maxdep, int dir)
2454{
2455 if (!(node[0] && node[1] && node[2] && node[3])) {
2456 return;
2457 }
2458 if (leaf[0] && leaf[1] && leaf[2] && leaf[3]) {
2459 processEdgeWrite(node, depth, maxdep, dir);
2460 }
2461 else {
2462 int i, j;
2463 Node *chd[4][8];
2464 for (j = 0; j < 4; j++) {
2465 for (i = 0; i < 8; i++) {
2466 chd[j][i] = ((!leaf[j]) && node[j]->internal.has_child(i)) ?
2467 node[j]->internal.get_child(node[j]->internal.get_child_count(i)) :
2468 nullptr;
2469 }
2470 }
2471
2472 // 2 edge calls
2473 Node *ne[4];
2474 int le[4];
2475 int de[4];
2476 for (i = 0; i < 2; i++) {
2477 int c[4] = {edgeProcEdgeMask[dir][i][0],
2478 edgeProcEdgeMask[dir][i][1],
2479 edgeProcEdgeMask[dir][i][2],
2480 edgeProcEdgeMask[dir][i][3]};
2481
2482 for (int j = 0; j < 4; j++) {
2483 if (leaf[j]) {
2484 le[j] = leaf[j];
2485 ne[j] = node[j];
2486 de[j] = depth[j];
2487 }
2488 else {
2489 le[j] = node[j]->internal.is_child_leaf(c[j]);
2490 ne[j] = chd[j][c[j]];
2491 de[j] = depth[j] - 1;
2492 }
2493 }
2494
2495 edgeProcContour(ne, le, de, maxdep - 1, edgeProcEdgeMask[dir][i][4]);
2496 }
2497 }
2498}
2499
2500void Octree::faceProcContour(
2501 Node *node[2], const int leaf[2], const int depth[2], int maxdep, int dir)
2502{
2503 if (!(node[0] && node[1])) {
2504 return;
2505 }
2506
2507 if (!(leaf[0] && leaf[1])) {
2508 int i, j;
2509 // Fill children nodes
2510 Node *chd[2][8];
2511 for (j = 0; j < 2; j++) {
2512 for (i = 0; i < 8; i++) {
2513 chd[j][i] = ((!leaf[j]) && node[j]->internal.has_child(i)) ?
2514 node[j]->internal.get_child(node[j]->internal.get_child_count(i)) :
2515 nullptr;
2516 }
2517 }
2518
2519 // 4 face calls
2520 Node *nf[2];
2521 int df[2];
2522 int lf[2];
2523 for (i = 0; i < 4; i++) {
2524 int c[2] = {faceProcFaceMask[dir][i][0], faceProcFaceMask[dir][i][1]};
2525 for (int j = 0; j < 2; j++) {
2526 if (leaf[j]) {
2527 lf[j] = leaf[j];
2528 nf[j] = node[j];
2529 df[j] = depth[j];
2530 }
2531 else {
2532 lf[j] = node[j]->internal.is_child_leaf(c[j]);
2533 nf[j] = chd[j][c[j]];
2534 df[j] = depth[j] - 1;
2535 }
2536 }
2537 faceProcContour(nf, lf, df, maxdep - 1, faceProcFaceMask[dir][i][2]);
2538 }
2539
2540 // 4 edge calls
2541 int orders[2][4] = {{0, 0, 1, 1}, {0, 1, 0, 1}};
2542 Node *ne[4];
2543 int le[4];
2544 int de[4];
2545
2546 for (i = 0; i < 4; i++) {
2547 int c[4] = {faceProcEdgeMask[dir][i][1],
2548 faceProcEdgeMask[dir][i][2],
2549 faceProcEdgeMask[dir][i][3],
2550 faceProcEdgeMask[dir][i][4]};
2551 int *order = orders[faceProcEdgeMask[dir][i][0]];
2552
2553 for (int j = 0; j < 4; j++) {
2554 if (leaf[order[j]]) {
2555 le[j] = leaf[order[j]];
2556 ne[j] = node[order[j]];
2557 de[j] = depth[order[j]];
2558 }
2559 else {
2560 le[j] = node[order[j]]->internal.is_child_leaf(c[j]);
2561 ne[j] = chd[order[j]][c[j]];
2562 de[j] = depth[order[j]] - 1;
2563 }
2564 }
2565
2566 edgeProcContour(ne, le, de, maxdep - 1, faceProcEdgeMask[dir][i][5]);
2567 }
2568 }
2569}
2570
2571void Octree::cellProcContour(Node *node, int leaf, int depth)
2572{
2573 if (node == nullptr) {
2574 return;
2575 }
2576
2577 if (!leaf) {
2578 int i;
2579
2580 // Fill children nodes
2581 Node *chd[8];
2582 for (i = 0; i < 8; i++) {
2583 chd[i] = ((!leaf) && node->internal.has_child(i)) ?
2584 node->internal.get_child(node->internal.get_child_count(i)) :
2585 nullptr;
2586 }
2587
2588 // 8 Cell calls
2589 for (i = 0; i < 8; i++) {
2590 cellProcContour(chd[i], node->internal.is_child_leaf(i), depth - 1);
2591 }
2592
2593 // 12 face calls
2594 Node *nf[2];
2595 int lf[2];
2596 int df[2] = {depth - 1, depth - 1};
2597 for (i = 0; i < 12; i++) {
2598 int c[2] = {cellProcFaceMask[i][0], cellProcFaceMask[i][1]};
2599
2600 lf[0] = node->internal.is_child_leaf(c[0]);
2601 lf[1] = node->internal.is_child_leaf(c[1]);
2602
2603 nf[0] = chd[c[0]];
2604 nf[1] = chd[c[1]];
2605
2606 faceProcContour(nf, lf, df, depth - 1, cellProcFaceMask[i][2]);
2607 }
2608
2609 // 6 edge calls
2610 Node *ne[4];
2611 int le[4];
2612 int de[4] = {depth - 1, depth - 1, depth - 1, depth - 1};
2613 for (i = 0; i < 6; i++) {
2614 int c[4] = {cellProcEdgeMask[i][0],
2615 cellProcEdgeMask[i][1],
2616 cellProcEdgeMask[i][2],
2617 cellProcEdgeMask[i][3]};
2618
2619 for (int j = 0; j < 4; j++) {
2620 le[j] = node->internal.is_child_leaf(c[j]);
2621 ne[j] = chd[c[j]];
2622 }
2623
2624 edgeProcContour(ne, le, de, depth - 1, cellProcEdgeMask[i][4]);
2625 }
2626 }
2627}
2628
2629void Octree::processEdgeParity(LeafNode *node[4], const int /*depth*/[4], int /*maxdep*/, int dir)
2630{
2631 int con = 0;
2632 for (int i = 0; i < 4; i++) {
2633 // Minimal cell
2634 // if(op == 0)
2635 {
2636 if (getEdgeParity(node[i], processEdgeMask[dir][i])) {
2637 con = 1;
2638 break;
2639 }
2640 }
2641 }
2642
2643 if (con == 1) {
2644 for (int i = 0; i < 4; i++) {
2645 setEdge(node[i], processEdgeMask[dir][i]);
2646 }
2647 }
2648}
2649
2650void Octree::edgeProcParity(
2651 Node *node[4], const int leaf[4], const int depth[4], int maxdep, int dir)
2652{
2653 if (!(node[0] && node[1] && node[2] && node[3])) {
2654 return;
2655 }
2656 if (leaf[0] && leaf[1] && leaf[2] && leaf[3]) {
2657 processEdgeParity((LeafNode **)node, depth, maxdep, dir);
2658 }
2659 else {
2660 int i, j;
2661 Node *chd[4][8];
2662 for (j = 0; j < 4; j++) {
2663 for (i = 0; i < 8; i++) {
2664 chd[j][i] = ((!leaf[j]) && node[j]->internal.has_child(i)) ?
2665 node[j]->internal.get_child(node[j]->internal.get_child_count(i)) :
2666 nullptr;
2667 }
2668 }
2669
2670 // 2 edge calls
2671 Node *ne[4];
2672 int le[4];
2673 int de[4];
2674 for (i = 0; i < 2; i++) {
2675 int c[4] = {edgeProcEdgeMask[dir][i][0],
2676 edgeProcEdgeMask[dir][i][1],
2677 edgeProcEdgeMask[dir][i][2],
2678 edgeProcEdgeMask[dir][i][3]};
2679
2680 // int allleaf = 1;
2681 for (int j = 0; j < 4; j++) {
2682
2683 if (leaf[j]) {
2684 le[j] = leaf[j];
2685 ne[j] = node[j];
2686 de[j] = depth[j];
2687 }
2688 else {
2689 le[j] = node[j]->internal.is_child_leaf(c[j]);
2690 ne[j] = chd[j][c[j]];
2691 de[j] = depth[j] - 1;
2692 }
2693 }
2694
2695 edgeProcParity(ne, le, de, maxdep - 1, edgeProcEdgeMask[dir][i][4]);
2696 }
2697 }
2698}
2699
2700void Octree::faceProcParity(
2701 Node *node[2], const int leaf[2], const int depth[2], int maxdep, int dir)
2702{
2703 if (!(node[0] && node[1])) {
2704 return;
2705 }
2706
2707 if (!(leaf[0] && leaf[1])) {
2708 int i, j;
2709 // Fill children nodes
2710 Node *chd[2][8];
2711 for (j = 0; j < 2; j++) {
2712 for (i = 0; i < 8; i++) {
2713 chd[j][i] = ((!leaf[j]) && node[j]->internal.has_child(i)) ?
2714 node[j]->internal.get_child(node[j]->internal.get_child_count(i)) :
2715 nullptr;
2716 }
2717 }
2718
2719 // 4 face calls
2720 Node *nf[2];
2721 int df[2];
2722 int lf[2];
2723 for (i = 0; i < 4; i++) {
2724 int c[2] = {faceProcFaceMask[dir][i][0], faceProcFaceMask[dir][i][1]};
2725 for (int j = 0; j < 2; j++) {
2726 if (leaf[j]) {
2727 lf[j] = leaf[j];
2728 nf[j] = node[j];
2729 df[j] = depth[j];
2730 }
2731 else {
2732 lf[j] = node[j]->internal.is_child_leaf(c[j]);
2733 nf[j] = chd[j][c[j]];
2734 df[j] = depth[j] - 1;
2735 }
2736 }
2737 faceProcParity(nf, lf, df, maxdep - 1, faceProcFaceMask[dir][i][2]);
2738 }
2739
2740 // 4 edge calls
2741 int orders[2][4] = {{0, 0, 1, 1}, {0, 1, 0, 1}};
2742 Node *ne[4];
2743 int le[4];
2744 int de[4];
2745
2746 for (i = 0; i < 4; i++) {
2747 int c[4] = {faceProcEdgeMask[dir][i][1],
2748 faceProcEdgeMask[dir][i][2],
2749 faceProcEdgeMask[dir][i][3],
2750 faceProcEdgeMask[dir][i][4]};
2751 int *order = orders[faceProcEdgeMask[dir][i][0]];
2752
2753 for (int j = 0; j < 4; j++) {
2754 if (leaf[order[j]]) {
2755 le[j] = leaf[order[j]];
2756 ne[j] = node[order[j]];
2757 de[j] = depth[order[j]];
2758 }
2759 else {
2760 le[j] = node[order[j]]->internal.is_child_leaf(c[j]);
2761 ne[j] = chd[order[j]][c[j]];
2762 de[j] = depth[order[j]] - 1;
2763 }
2764 }
2765
2766 edgeProcParity(ne, le, de, maxdep - 1, faceProcEdgeMask[dir][i][5]);
2767 }
2768 }
2769}
2770
2771void Octree::cellProcParity(Node *node, int leaf, int depth)
2772{
2773 if (node == nullptr) {
2774 return;
2775 }
2776
2777 if (!leaf) {
2778 int i;
2779
2780 // Fill children nodes
2781 Node *chd[8];
2782 for (i = 0; i < 8; i++) {
2783 chd[i] = ((!leaf) && node->internal.has_child(i)) ?
2784 node->internal.get_child(node->internal.get_child_count(i)) :
2785 nullptr;
2786 }
2787
2788 // 8 Cell calls
2789 for (i = 0; i < 8; i++) {
2790 cellProcParity(chd[i], node->internal.is_child_leaf(i), depth - 1);
2791 }
2792
2793 // 12 face calls
2794 Node *nf[2];
2795 int lf[2];
2796 int df[2] = {depth - 1, depth - 1};
2797 for (i = 0; i < 12; i++) {
2798 int c[2] = {cellProcFaceMask[i][0], cellProcFaceMask[i][1]};
2799
2800 lf[0] = node->internal.is_child_leaf(c[0]);
2801 lf[1] = node->internal.is_child_leaf(c[1]);
2802
2803 nf[0] = chd[c[0]];
2804 nf[1] = chd[c[1]];
2805
2806 faceProcParity(nf, lf, df, depth - 1, cellProcFaceMask[i][2]);
2807 }
2808
2809 // 6 edge calls
2810 Node *ne[4];
2811 int le[4];
2812 int de[4] = {depth - 1, depth - 1, depth - 1, depth - 1};
2813 for (i = 0; i < 6; i++) {
2814 int c[4] = {cellProcEdgeMask[i][0],
2815 cellProcEdgeMask[i][1],
2816 cellProcEdgeMask[i][2],
2817 cellProcEdgeMask[i][3]};
2818
2819 for (int j = 0; j < 4; j++) {
2820 le[j] = node->internal.is_child_leaf(c[j]);
2821 ne[j] = chd[c[j]];
2822 }
2823
2824 edgeProcParity(ne, le, de, depth - 1, cellProcEdgeMask[i][4]);
2825 }
2826 }
2827}
2828
2829/* definitions for global arrays */
2830const int edgemask[3] = {5, 3, 6};
2831
2832const int faceMap[6][4] = {
2833 {4, 8, 5, 9},
2834 {6, 10, 7, 11},
2835 {0, 8, 1, 10},
2836 {2, 9, 3, 11},
2837 {0, 4, 2, 6},
2838 {1, 5, 3, 7},
2839};
2840
2841const int cellProcFaceMask[12][3] = {
2842 {0, 4, 0},
2843 {1, 5, 0},
2844 {2, 6, 0},
2845 {3, 7, 0},
2846 {0, 2, 1},
2847 {4, 6, 1},
2848 {1, 3, 1},
2849 {5, 7, 1},
2850 {0, 1, 2},
2851 {2, 3, 2},
2852 {4, 5, 2},
2853 {6, 7, 2},
2854};
2855
2856const int cellProcEdgeMask[6][5] = {
2857 {0, 1, 2, 3, 0},
2858 {4, 5, 6, 7, 0},
2859 {0, 4, 1, 5, 1},
2860 {2, 6, 3, 7, 1},
2861 {0, 2, 4, 6, 2},
2862 {1, 3, 5, 7, 2},
2863};
2864
2865const int faceProcFaceMask[3][4][3] = {{{4, 0, 0}, {5, 1, 0}, {6, 2, 0}, {7, 3, 0}},
2866 {{2, 0, 1}, {6, 4, 1}, {3, 1, 1}, {7, 5, 1}},
2867 {{1, 0, 2}, {3, 2, 2}, {5, 4, 2}, {7, 6, 2}}};
2868
2869const int faceProcEdgeMask[3][4][6] = {
2870 {{1, 4, 0, 5, 1, 1}, {1, 6, 2, 7, 3, 1}, {0, 4, 6, 0, 2, 2}, {0, 5, 7, 1, 3, 2}},
2871 {{0, 2, 3, 0, 1, 0}, {0, 6, 7, 4, 5, 0}, {1, 2, 0, 6, 4, 2}, {1, 3, 1, 7, 5, 2}},
2872 {{1, 1, 0, 3, 2, 0}, {1, 5, 4, 7, 6, 0}, {0, 1, 5, 0, 4, 1}, {0, 3, 7, 2, 6, 1}}};
2873
2874const int edgeProcEdgeMask[3][2][5] = {
2875 {{3, 2, 1, 0, 0}, {7, 6, 5, 4, 0}},
2876 {{5, 1, 4, 0, 1}, {7, 3, 6, 2, 1}},
2877 {{6, 4, 2, 0, 2}, {7, 5, 3, 1, 2}},
2878};
2879
2880const int processEdgeMask[3][4] = {
2881 {3, 2, 1, 0},
2882 {7, 5, 6, 4},
2883 {11, 10, 9, 8},
2884};
2885
2886const int dirCell[3][4][3] = {{{0, -1, -1}, {0, -1, 0}, {0, 0, -1}, {0, 0, 0}},
2887 {{-1, 0, -1}, {-1, 0, 0}, {0, 0, -1}, {0, 0, 0}},
2888 {{-1, -1, 0}, {-1, 0, 0}, {0, -1, 0}, {0, 0, 0}}};
2889
2890const int dirEdge[3][4] = {
2891 {3, 2, 1, 0},
2892 {7, 6, 5, 4},
2893 {11, 10, 9, 8},
2894};
2895
const int edgemap[12][2]
const int vertmap[8][3]
#define GRID_DIMENSION
Definition Projections.h:13
#define A
long long int int64_t
int numVertices() const
SIMD_FORCE_INLINE void mult(const btTransform &t1, const btTransform &t2)
Set the current transform as the value of the product of two transforms.
Definition btTransform.h:76
SIMD_FORCE_INLINE btScalar norm() const
Return the norm (length) of the vector.
Definition btVector3.h:263
CubeTriangleIsect()=default
void shift(const int off[3])
int isIntersecting() const
int isIntersectingPrimary(int edgeInd) const
unsigned char getBoxMask()
TriangleProjection * inherit
Inheritable portion.
Definition Projections.h:75
float getIntersectionPrimary(int edgeInd) const
Definition cubes.h:13
void pushQueue(const int st[3], int dir)
Definition Queue.h:39
int popQueue(int st[3], int &dir)
Definition Queue.h:57
GridQueue()
Definition Queue.h:22
virtual float getBoundingBox(float origin[3])=0
Get bounding box.
virtual Triangle * getNextTriangle()=0
Get next triangle.
virtual int getNumTriangles()=0
Get number of triangles.
ModelReader * reader
VirtualMemoryAllocator * alloc[9]
VirtualMemoryAllocator * leafalloc[4]
DualConMode mode
Octree(const BoundBox &bbox)
virtual int getBytes()=0
virtual int getAllocated()=0
virtual int getAll()=0
virtual void destroy()=0
virtual void printInfo()=0
#define printf
const int processEdgeMask[3][4]
const int edgeProcEdgeMask[3][2][5]
static void pseudoInverse(const Eigen::Matrix3f &a, Eigen::Matrix3f &result, float tolerance)
const int faceProcFaceMask[3][4][3]
static void minimize(float rvalue[3], float mp[3], const float pts[12][3], const float norms[12][3], const int parity[12])
static void solve_least_squares(const float halfA[], const float b[], const float midpoint[], float rvalue[])
const int cellProcFaceMask[12][3]
const int faceMap[6][4]
const int faceProcEdgeMask[3][4][6]
#define dc_printf(...)
const int cellProcEdgeMask[6][5]
const int dirEdge[3][4]
static void mass_point(float mp[3], const float pts[12][3], const int parity[12])
const int dirCell[3][4][3]
const int edgemask[3]
const int processEdgeMask[3][4]
const int edgeProcEdgeMask[3][2][5]
const int faceProcFaceMask[3][4][3]
const int cellProcFaceMask[12][3]
const int faceMap[6][4]
const int faceProcEdgeMask[3][4][6]
const int cellProcEdgeMask[6][5]
DualConMode
Definition dualcon.h:45
@ DUALCON_CENTROID
Definition dualcon.h:47
@ DUALCON_MASS_POINT
Definition dualcon.h:49
void *(*) DualConAllocOutput(int totvert, int totquad)
Definition dualcon.h:35
void(*) DualConAddQuad(void *output, const int vert_indices[4])
Definition dualcon.h:39
void(*) DualConAddVert(void *output, const float co[3])
Definition dualcon.h:37
DualConFlags
Definition dualcon.h:41
@ DUALCON_FLOOD_FILL
Definition dualcon.h:42
int midpoint(int a, int b)
const ManifoldIndices manifold_table[256]
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
ccl_device_inline float2 mask(const MaskType mask, const float2 a)
int size(const AssetLibraryReference *library_reference)
const std::any * find(const AnyDictionary &dictionary, const std::string &key)
T cube(const T &a)
SymEdge< T > * prev(const SymEdge< T > *se)
ATTR_WARN_UNUSED_RESULT const size_t num
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
Node * get_child(int count)
static int childrenCountTable[256][8]
static int numChildrenTable[256]
int has_child(int index) const
static int childrenIndexTable[256][8]
void fill_children(Node *children[8], int leaf[8])
int is_child_leaf(int index) const
InternalNode internal
PathElement * tail
PathElement * head
double norm[3]
Normal of the triangle.
Definition Projections.h:55
float vt[3][3]
Definition GeoCommon.h:31