23# define dc_printf printf
26# define dc_printf(...) \
60 alloc_output(alloc_output_func),
61 add_vert(add_vert_func),
62 add_quad(add_quad_func)
101 clock_t start, finish;
112 (
double)(finish - start) / CLOCKS_PER_SEC);
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",
128 (
float)totRingLengths / (
float)numRings,
134 int tnumRings = numRings;
136#ifdef IN_VERBOSE_MODE
137 dc_printf(
"Holes after patching: %d \n", numRings);
139 numRings = tnumRings;
148 dc_printf(
"Time taken: %f seconds \n", (
double)(finish - start) / CLOCKS_PER_SEC);
174 dc_printf(
"Time taken: %f seconds \n", (
double)(finish - start) / CLOCKS_PER_SEC);
189#ifdef IN_VERBOSE_MODE
194void Octree::initMemory()
212void Octree::freeMemory()
214 for (
int i = 0; i < 9; i++) {
219 for (
int i = 0; i < 4; i++) {
225void Octree::printMemUsage()
228 dc_printf(
"********* Internal nodes: \n");
229 for (
int i = 0; i < 9; i++) {
236 for (
int i = 0; i < 4; i++) {
243 dc_printf(
"Total allocated bytes on disk: %d \n", totalbytes);
244 dc_printf(
"Total leaf nodes: %d\n", totalLeafs);
251void Octree::resetMinimalEdges()
256void Octree::addAllTriangles()
263 int unitcount = 1000;
272 addTriangle(trian, count);
279 if (count % unitcount == 0) {
282 switch ((count / unitcount) % 4) {
297 float percent = (
float)count / total;
311 dc_printf(
" %f%% complete.", 100 * percent);
320void Octree::addTriangle(
Triangle *trian,
int triind)
325 for (i = 0; i < 3; i++) {
326 for (j = 0; j < 3; j++) {
334 for (i = 0; i < 3; i++) {
335 for (j = 0; j < 3; j++) {
350static void print_depth(
int height,
int maxDepth)
352 for (
int i = 0; i < maxDepth - height; 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}};
367 int tempdiff[3] = {0, 0, 0};
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];
376 if (boxmask & (1 << i)) {
377 subp->
shift(tempdiff);
378 tempdiff[0] = tempdiff[1] = tempdiff[2] = 0;
382 if (!
node->has_child(i)) {
384 node = addLeafChild(
node, i, count, createLeaf(0));
387 node = addInternalChild(
node, i, count, createInternal(0));
390 Node *chd =
node->get_child(count);
392 if (
node->is_child_leaf(i)) {
393 node->set_child(count, (Node *)updateCell(&chd->
leaf, subp));
396 node->set_child(count, (Node *)addTriangle(&chd->
internal, subp, height - 1));
401 if (
node->has_child(i)) {
416 int mask[3] = {0, 4, 8};
417 int oldc = 0, newc = 0;
419 float a[3],
b[3], c[3];
421 for (i = 0; i < 3; i++) {
422 if (!getEdgeParity(
node,
mask[i])) {
434 offs[newc] = getEdgeOffsetNormal(
node, oldc, a[newc],
b[newc], c[newc]);
443 node = updateEdgeOffsetsNormals(
node, oldc, newc, offs, a,
b, c);
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);
458 preparePrimalEdgesMask(&
node->get_child(count)->internal);
477 PathList *chdpath =
nullptr;
480 if (chdpath !=
nullptr) {
481 dc_printf(
"there are incomplete rings.\n");
489 PathList *chdpaths[8];
499 for (i = 0; i < 8; i++) {
500 for (j = 0; j < 3; j++) {
505 chdpaths[i] =
nullptr;
508 trace(chd[i], nst[i],
len, depth - 1, chdpaths[i]);
516 int df[2] = {depth - 1, depth - 1};
521 for (i = 0; i < 12; i++) {
524 for (
int j = 0; j < 2; j++) {
525 lf[j] = chdleaf[c[j]];
532 findPaths((Node **)nf, lf, df, nstf, depth - 1,
cellProcFaceMask[i][2], conn[i]);
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);
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);
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);
565 PathList *trings = rings;
568 totRingLengths += trings->
length;
569 maxRingLength = std::max(trings->
length, maxRingLength);
570 trings = trings->
next;
574 newnode = patch(newnode, st, (
len << 1), rings);
582void Octree::findPaths(
Node *
node[2],
594 if (!(leaf[0] && leaf[1])) {
603 for (j = 0; j < 2; j++) {
605 node[j]->internal.fill_children(chd[j], chdleaf[j]);
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];
621 for (i = 0; i < 4; i++) {
623 for (
int j = 0; j < 2; j++) {
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]];
637 findPaths(nf, lf, df, nstf, maxdep - 1,
faceProcFaceMask[dir][i][2], paths);
642 int ind = (depth[0] == maxdep ? 0 : 1);
643 int fcind = 2 * dir + (1 - ind);
644 if (getFaceParity((LeafNode *)
node[ind], fcind)) {
646 PathElement *ele1 =
new PathElement;
647 PathElement *ele2 =
new PathElement;
649 ele1->
pos[0] = st[0][0];
650 ele1->
pos[1] = st[0][1];
651 ele1->
pos[2] = st[0][2];
653 ele2->
pos[0] = st[1][0];
654 ele2->
pos[1] = st[1][1];
655 ele2->
pos[2] = st[1][2];
658 ele2->
next =
nullptr;
660 PathList *lst =
new PathList;
675 PathList *nlist =
nullptr;
678 PathList *tpaths = paths;
679 PathList *tlist, *pre;
681 PathList *singlist = tpaths;
683 tpaths = tpaths->
next;
684 singlist->
next =
nullptr;
690 if ((templist = combineSinglePath(list1, pre, tlist, singlist,
nullptr, singlist)) !=
704 if ((templist = combineSinglePath(list2, pre, tlist, singlist,
nullptr, singlist)) !=
718 if ((templist = combineSinglePath(nlist, pre, tlist, singlist,
nullptr, singlist)) !=
729 if (isEqual(singlist->
head, singlist->
tail)) {
730 PathElement *temp = singlist->
head;
736 singlist->
next = rings;
740 singlist->
next = nlist;
747 if (tlist !=
nullptr) {
748 while (tlist->
next !=
nullptr) {
758 if (tlist !=
nullptr) {
759 while (tlist->
next !=
nullptr) {
777 if (isEqual(list1->
head, list2->
head) || isEqual(list1->
tail, list2->
tail)) {
782 PathElement *next =
prev->next;
783 prev->next =
nullptr;
784 while (next !=
nullptr) {
785 PathElement *tnext = next->
next;
798 PathElement *next =
prev->next;
799 prev->next =
nullptr;
800 while (next !=
nullptr) {
801 PathElement *tnext = next->
next;
813 if (isEqual(list1->
head, list2->
tail)) {
816 PathElement *temp = list1->
head->
next;
820 PathList *nlist =
new PathList;
824 nlist->
next =
nullptr;
826 deletePath(head1, pre1, list1);
827 deletePath(head2, pre2, list2);
831 if (isEqual(list1->
tail, list2->
head)) {
833 PathElement *temp = list2->
head->
next;
837 PathList *nlist =
new PathList;
841 nlist->
next =
nullptr;
843 deletePath(head1, pre1, list1);
844 deletePath(head2, pre2, list2);
854 PathList *temp = curr;
858 if (pre ==
nullptr) {
868 if (ele !=
nullptr) {
873void Octree::printPath(
PathList *path)
875 PathElement *n = path->
head;
881 while (n && (same == 0 || n != path->
head)) {
887 if (n == path->
head) {
897 PathElement *n = path;
902 while (n && (same == 0 || n != path)) {
916void Octree::printPaths(
PathList *path)
918 PathList *iter = path;
919 while (iter !=
nullptr) {
929 dc_printf(
"Call to PATCH with rings: \n");
952 dc_printf(
"Error! should have no list by now.\n");
958 newnode = patchSplit(newnode, st,
len, rings, 0, xlists[0], xlists[1]);
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]);
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]);
975 for (
int i = 0; i < 8; i++) {
976 if (zlists[i] !=
nullptr) {
992Node *Octree::patchSplit(
Node *newnode,
1001 dc_printf(
"Call to PATCHSPLIT with direction %d and rings: \n", dir);
1008 while (rings !=
nullptr) {
1010 newnode = patchSplitSingle(newnode, st,
len, rings->
head, dir, nrings1, nrings2);
1014 rings = rings->
next;
1019 dc_printf(
"Return from PATCHSPLIT with \n");
1021 printPaths(nrings1);
1023 printPaths(nrings2);
1029Node *Octree::patchSplitSingle(
Node *newnode,
1038 dc_printf(
"Call to PATCHSPLITSINGLE with direction %d and path: \n", dir);
1042 if (head ==
nullptr) {
1044 dc_printf(
"Return from PATCHSPLITSINGLE with head==nullptr.\n");
1052 PathElement *pre1 =
nullptr;
1053 PathElement *pre2 =
nullptr;
1054 int side = findPair(head, st[dir] +
len / 2, dir, pre1, pre2);
1059 dc_printf(
"Location: %d %d %d Direction: %d Reso: %d\n",
1072 PathList *nring =
new PathList();
1076 nring->
next = nrings1;
1080 nring->
next = nrings2;
1086 PathElement *nxt1 = pre1->
next;
1087 PathElement *nxt2 = pre2->
next;
1091 newnode = connectFace(newnode, st,
len, dir, pre1, pre2);
1093 if (isEqual(pre1, pre1->
next)) {
1094 if (pre1 == pre1->
next) {
1099 PathElement *temp = pre1->
next;
1104 if (isEqual(pre2, pre2->
next)) {
1105 if (pre2 == pre2->
next) {
1110 PathElement *temp = pre2->
next;
1120 newnode = patchSplitSingle(newnode, st,
len, pre1, dir, nrings1, nrings2);
1121 newnode = patchSplitSingle(newnode, st,
len, pre2, dir, nrings1, nrings2);
1125 dc_printf(
"Return from PATCHSPLITSINGLE with \n");
1127 printPaths(nrings1);
1129 printPaths(nrings2);
1135Node *Octree::connectFace(
1139 dc_printf(
"Call to CONNECTFACE with direction %d and length %d path: \n", dir,
len);
1149 int pos = st[dir] +
len / 2;
1150 int xdir = (dir + 1) % 3;
1151 int ydir = (dir + 2) % 3;
1155 float p1, q1, p2, q2;
1157 getFacePoint(f2->
next, dir, x1, y1, p1, q1);
1158 getFacePoint(f2, dir, x2, y2, p2, q2);
1160 float dx = x2 + p2 - x1 - p1;
1161 float dy = y2 + q2 - y1 - q1;
1164 float rx = p1, ry = q1;
1165 int incx = 1, incy = 1;
1166 int lx = x1, ly = y1;
1167 int hx = x2, hy = y2;
1182 float sx = dx * incx;
1183 float sy = dy * incy;
1193 PathElement *curEleN = f1;
1194 PathElement *curEleP = f2->
next;
1195 Node *nodeN =
nullptr, *nodeP =
nullptr;
1198 if (curN ==
nullptr || curP ==
nullptr) {
1213 while (ori[xdir] != x2 || ori[ydir] != y2) {
1215 if (sy * (1 - rx) > sx * (1 - ry)) {
1217 next = ori[ydir] + incy;
1218 if (next < ly || next > hy) {
1220 next = ori[xdir] + incx;
1225 next = ori[xdir] + incx;
1226 if (next < lx || next > hx) {
1228 next = ori[ydir] + incy;
1235 rx += (sy == 0 ? 0 : (1 - ry) * sx / sy);
1241 alpha = x2 < x1 ? 1 - rx : rx;
1246 ry += (sx == 0 ? 0 : (1 - rx) * sy / sx);
1252 alpha = y2 < y1 ? 1 - ry : ry;
1257 float spt[3] = {(
float)nori[0], (
float)nori[1], (
float)nori[2]};
1258 spt[(dir + (3 - walkdir)) % 3] += alpha *
mindimen;
1260 spt[(dir + walkdir) % 3] +=
mindimen;
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]);
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);
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])
1281 newEleN =
new PathElement;
1283 newEleN->
pos[0] = stN[0];
1284 newEleN->
pos[1] = stN[1];
1285 newEleN->
pos[2] = stN[2];
1287 curEleN->
next = newEleN;
1290 newEleN = curEleN->
next;
1292 curN = patchAdjacent(&newnode->
internal,
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];
1321 curP = patchAdjacent(&newnode->
internal,
1344 dc_printf(
"Return from CONNECTFACE with \n");
1373 "-----------------%d %d %d; %d %d %d\n", st1[0], st2[1], st1[2], st2[0], st2[1], st2[2]);
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);
1382 int eind1 = ((edgedir << 2) | (side << ind1) | ((inc > 0 ? 1 : 0) << ind2));
1383 int eind2 = ((edgedir << 2) | (side << ind1) | ((inc > 0 ? 0 : 1) << ind2));
1386 dc_printf(
"Index 1: %d Alpha 1: %f Index 2: %d Alpha 2: %f\n", eind1, alpha, eind2, alpha);
1397 LeafNode *nleaf1 = flipEdge(leaf1, eind1, alpha);
1398 LeafNode *nleaf2 = flipEdge(leaf2, eind2, alpha);
1401 updateParent(
node,
len, st1, nleaf1);
1402 updateParent(
node,
len, st2, nleaf2);
1441 for (i = 0; i < 3; i++) {
1443 if (i == dir && side == 1) {
1444 ind |= (ori[i] <= (st[i] +
len) ? 0 : 1);
1447 ind |= (ori[i] < (st[i] +
len) ? 0 : 1);
1454 "In LOCATECELL index of ori(%d %d %d) with dir %d side %d in st(%d %d %d, %d) is: %d\n",
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)) {
1481 node->set_child(count,
1482 locateCell(&chd->
internal, rst,
len, ori, dir, side, rleaf, rst, rlen));
1488 LeafNode *chd = createLeaf(0);
1489 node = addChild(
node, ind, (Node *)chd, 1);
1490 rleaf = (Node *)chd;
1495 InternalNode *chd = createInternal(0);
1496 node = addChild(
node, ind, locateCell(chd, rst,
len, ori, dir, side, rleaf, rst, rlen), 0);
1504 return (Node *)
node;
1510 if (ele !=
nullptr && locateLeafCheck(ele->
pos) != ele->node) {
1511 dc_printf(
"Screwed! at pos: %d %d %d\n",
1522 PathElement *n = path;
1524 while (n && (same == 0 || n != path)) {
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]) {
1550 getFacePoint(e, i,
x,
y, p, q);
1553void Octree::getFacePoint(
PathElement *leaf,
int dir,
int &
x,
int &
y,
float &p,
float &q)
1556 float avg[3] = {0, 0, 0};
1558 int num = 0, num2 = 0;
1562 LeafNode *leafnode = locateLeaf(leaf->
pos);
1563 for (
int i = 0; i < 4; i++) {
1564 int edgeind =
faceMap[dir * 2][i];
1566 for (
int j = 0; j < 3; j++) {
1570 if (getEdgeIntersectionByIndex(nst, edgeind / 4, off, 1)) {
1576 if (getEdgeParity(leafnode, edgeind)) {
1581 dc_printf(
"Wrong! dir: %d pos: %d %d %d num: %d\n",
1602 int xdir = (dir + 1) % 3;
1603 int ydir = (dir + 2) % 3;
1605 float xf = avg[xdir];
1606 float yf = avg[ydir];
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",
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",
1650 dc_printf(
"Face point at dir %d pos %d: %f %f\n", dir, pos, xf, yf);
1663 dc_printf(
"Face point at dir %d : %f %f\n", dir, xf, yf);
1669 int side = getSide(head, pos, dir);
1670 PathElement *cur = head;
1671 PathElement *anchor;
1672 PathElement *ppre1, *ppre2;
1678 while (cur != anchor && (getSide(cur, pos, dir) == side)) {
1682 if (cur == anchor) {
1687 side = getSide(cur, pos, dir);
1690 while (getSide(cur, pos, dir) == side) {
1708int Octree::getSide(
PathElement *e,
int pos,
int dir)
1710 return (
e->pos[dir] < pos ? -1 : 1);
1715 return (e1->
pos[0] == e2->
pos[0] && e1->
pos[1] == e2->
pos[1] && e1->
pos[2] == e2->
pos[2]);
1720 if (ring ==
nullptr) {
1724 dc_printf(
"Call to COMPRESSRING with path: \n");
1728 PathElement *cur = ring->
next->
next;
1729 PathElement *pre = ring->
next;
1730 PathElement *prepre = ring;
1731 PathElement *anchor = prepre;
1734 while (isEqual(cur, prepre)) {
1736 if (cur == prepre) {
1751 if (anchor ==
nullptr) {
1758 }
while (prepre != anchor);
1763 dc_printf(
"Return from COMPRESSRING with path: \n");
1768void Octree::buildSigns()
1773 unsigned char table[1 << 12];
1774 for (
int i = 0; i <
size; i++) {
1777 for (
int i = 0; i < 256; i++) {
1779 for (
int j = 11; j >= 0; j--) {
1792 buildSigns(table,
root, 0, sg, cube);
1795void Octree::buildSigns(
unsigned char table[],
Node *
node,
int isLeaf,
int sg,
int rvalue[8])
1797 if (
node ==
nullptr) {
1798 for (
int i = 0; i < 8; i++) {
1808 node->internal.fill_children(chd, leaf);
1813 buildSigns(table, chd[0], leaf[0], sg, oris);
1817 for (
int i = 1; i < 8; i++) {
1818 buildSigns(table, chd[i], leaf[i], oris[i], cube);
1819 rvalue[i] =
cube[i];
1824 generateSigns(&
node->leaf, table, sg);
1826 for (
int i = 0; i < 8; i++) {
1827 rvalue[i] = getSign(&
node->leaf, i);
1832void Octree::floodFill()
1835 int st[3] = {0, 0, 0};
1843 dc_printf(
"Largest component: %d\n", threshold);
1845 dc_printf(
"Removing all components smaller than %d\n", threshold);
1847 int st2[3] = {0, 0, 0};
1852void Octree::clearProcessBits(
Node *
node,
int height)
1858 for (i = 0; i < 12; i++) {
1859 setOutProcess(&
node->leaf, i);
1865 for (i = 0; i < 8; i++) {
1866 if (
node->internal.has_child(i)) {
1867 clearProcessBits(
node->internal.get_child(count), height - 1);
1874int Octree::floodFill(
LeafNode *leaf,
const int st[3],
int len,
int ,
int threshold)
1883 for (i = 0; i < 12; i++) {
1884 par = getEdgeParity(leaf, i);
1885 inp = isInProcess(leaf, i);
1887 if (par == 1 && inp == 0) {
1899 setInProcessAll(mst, mdir);
1906 while (queue->
popQueue(nst, dir) == 1) {
1915 int stMask[3][3] = {{0, 0 -
len, 0 -
len}, {0 -
len, 0, 0 -
len}, {0 -
len, 0 -
len, 0}};
1917 for (j = 0; j < 3; j++) {
1919 cst[1][j] = nst[j] + stMask[dir][j];
1924 for (j = 0; j < 2; j++) {
1925 cs[j] = locateLeaf(cst[j]);
1929 int s = getSign(cs[0], 0);
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}}};
1938 for (
int find = 0;
find < 4;
find++) {
1939 int cind = fcCells[
find];
1943 for (eind = 0; eind < 3; eind++) {
1944 edge = fcEdges[dir][
find][eind];
1945 if (getEdgeParity(cs[cind], edge) == 1) {
1952 for (eind = 2; eind >= 0; eind--) {
1953 edge = fcEdges[dir][
find][eind];
1954 if (getEdgeParity(cs[cind], edge) == 1) {
1960 if (eind == 3 || eind == -1) {
1961 dc_printf(
"Wrong! this is not a consistent sign. %d\n", eind);
1968 int edir = edge / 4;
1970 if (isInProcess(cs[cind], edge) == 0) {
1971 setInProcessAll(est, edir);
1974 dc_printf(
"Pushed: est: %d %d %d, edir: %d\n",
1986 dc_printf(
"Size of component: %d ", total);
1988 if (threshold == 0) {
1990 maxtotal = std::max(total, maxtotal);
1996 if (total >= threshold) {
2001 dc_printf(
"Less than %d, removing...\n", threshold);
2007 flipParityAll(mst, mdir);
2013 while (queue->
popQueue(nst, dir) == 1) {
2022 int stMask[3][3] = {{0, 0 -
len, 0 -
len}, {0 -
len, 0, 0 -
len}, {0 -
len, 0 -
len, 0}};
2024 for (j = 0; j < 3; j++) {
2026 cst[1][j] = nst[j] + stMask[dir][j];
2031 for (j = 0; j < 2; j++) {
2032 cs[j] = locateLeaf(cst[j]);
2036 int s = getSign(cs[0], 0);
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}}};
2045 for (
int find = 0;
find < 4;
find++) {
2046 int cind = fcCells[
find];
2050 for (eind = 0; eind < 3; eind++) {
2051 edge = fcEdges[dir][
find][eind];
2052 if (isInProcess(cs[cind], edge) == 1) {
2059 for (eind = 2; eind >= 0; eind--) {
2060 edge = fcEdges[dir][
find][eind];
2061 if (isInProcess(cs[cind], edge) == 1) {
2067 if (eind == 3 || eind == -1) {
2068 dc_printf(
"Wrong! this is not a consistent sign. %d\n", eind);
2075 int edir = edge / 4;
2077 if (getEdgeParity(cs[cind], edge) == 1) {
2078 flipParityAll(est, edir);
2081 dc_printf(
"Pushed: est: %d %d %d, edir: %d\n",
2100int Octree::floodFill(
Node *
node,
int st[3],
int len,
int height,
int threshold)
2106 maxtotal = floodFill(&
node->leaf, st,
len, height, threshold);
2112 for (i = 0; i < 8; i++) {
2113 if (
node->internal.has_child(i)) {
2119 int d = floodFill(
node->internal.get_child(count), nst,
len, height - 1, threshold);
2120 maxtotal = std::max(d, maxtotal);
2129void Octree::writeOut()
2138 output_mesh = alloc_output(
numVertices, numQuads);
2140 int st[3] = {0, 0, 0};
2152void Octree::countIntersection(
Node *
node,
int height,
int &nedge,
int &ncell,
int &nface)
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);
2161 nedge += getNumEdges2(&
node->leaf);
2163 int smask = getSignMask(&
node->leaf);
2170 if (smask > 0 && smask < 255) {
2175 for (
int i = 0; i < 3; i++) {
2176 if (getFaceEdgeNum(&
node->leaf, i * 2)) {
2184static void pseudoInverse(
const Eigen::Matrix3f &a, Eigen::Matrix3f &result,
float tolerance)
2186 const int Options = Eigen::ComputeFullU | Eigen::ComputeFullV;
2187 Eigen::JacobiSVD<Eigen::Matrix3f, Options> svd = a.jacobiSvd<
Options>();
2189 result = svd.matrixV() *
2190 Eigen::Vector3f((svd.singularValues().array().abs() > tolerance)
2191 .select(svd.singularValues().array().inverse(), 0))
2193 svd.matrixU().adjoint();
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];
2206 Eigen::Vector3f b2(
b), mp(
midpoint), result;
2208 result = pinv * b2 + mp;
2210 for (
int i = 0; i < 3; i++) {
2211 rvalue[i] = result(i);
2215static void mass_point(
float mp[3],
const float pts[12][3],
const int parity[12])
2219 for (
int i = 0; i < 12; i++) {
2221 const float *p = pts[i];
2241 const float pts[12][3],
2242 const float norms[12][3],
2243 const int parity[12])
2245 float ata[6] = {0, 0, 0, 0, 0, 0};
2246 float atb[3] = {0, 0, 0};
2249 for (
int i = 0; i < 12; i++) {
2252 const float *
norm = norms[i];
2253 const float *p = pts[i];
2263 const float pn = p[0] *
norm[0] + p[1] *
norm[1] + p[2] *
norm[2];
2289void Octree::computeMinimizer(
const LeafNode *leaf,
int st[3],
int len,
float rvalue[3])
const
2292 float pts[12][3], norms[12][3];
2294 fillEdgeIntersections(leaf, st,
len, pts, norms, parity);
2298 rvalue[0] = (
float)st[0] +
len / 2;
2299 rvalue[1] = (
float)st[1] +
len / 2;
2300 rvalue[2] = (
float)st[2] +
len / 2;
2304 rvalue[0] = rvalue[1] = rvalue[2] = 0;
2312 float mp[3] = {0, 0, 0};
2313 minimize(rvalue, mp, pts, norms, parity);
2319 if (rvalue[0] < st[0] - nh1 || rvalue[1] < st[1] - nh1 || rvalue[2] < st[2] - nh1 ||
2321 rvalue[0] > st[0] + nh2 || rvalue[1] > st[1] + nh2 || rvalue[2] > st[2] + nh2)
2333void Octree::generateMinimizer(
Node *
node,
int st[3],
int len,
int height,
int &offset)
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);
2349 for (j = 0; j < 3; j++) {
2354 int mult = 0, smask = getSignMask(&
node->leaf);
2360 if (smask > 0 && smask < 255) {
2365 for (j = 0; j <
mult; j++) {
2366 add_vert(output_mesh, rvalue);
2370 setMinimizerIndex(&
node->leaf, offset);
2378 for (i = 0; i < 8; i++) {
2379 if (
node->internal.has_child(i)) {
2385 generateMinimizer(
node->internal.get_child(count), nst,
len, height - 1, offset);
2392void Octree::processEdgeWrite(
Node *
node[4],
int [4],
int ,
int dir)
2401 if (getSign((LeafNode *)
node[i],
edgemap[edgeind][1]) > 0) {
2410 int seq[4] = {0, 1, 3, 2};
2411 for (
int k = 0; k < 4; k++) {
2416 if (vind[1] != -1) {
2420 ind[
num - 1] = vind[0];
2421 ind[
num - 2] = vind[1];
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]));
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]));
2444 add_quad(output_mesh, ind);
2453void Octree::edgeProcContour(
Node *
node[4],
const int leaf[4],
int depth[4],
int maxdep,
int dir)
2458 if (leaf[0] && leaf[1] && leaf[2] && leaf[3]) {
2459 processEdgeWrite(
node, depth, maxdep, dir);
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)) ?
2476 for (i = 0; i < 2; i++) {
2482 for (
int j = 0; j < 4; j++) {
2489 le[j] =
node[j]->internal.is_child_leaf(c[j]);
2490 ne[j] = chd[j][c[j]];
2491 de[j] = depth[j] - 1;
2500void Octree::faceProcContour(
2501 Node *
node[2],
const int leaf[2],
const int depth[2],
int maxdep,
int dir)
2507 if (!(leaf[0] && leaf[1])) {
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)) ?
2523 for (i = 0; i < 4; i++) {
2525 for (
int j = 0; j < 2; j++) {
2532 lf[j] =
node[j]->internal.is_child_leaf(c[j]);
2533 nf[j] = chd[j][c[j]];
2534 df[j] = depth[j] - 1;
2541 int orders[2][4] = {{0, 0, 1, 1}, {0, 1, 0, 1}};
2546 for (i = 0; i < 4; i++) {
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]];
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;
2571void Octree::cellProcContour(
Node *
node,
int leaf,
int depth)
2573 if (
node ==
nullptr) {
2582 for (i = 0; i < 8; i++) {
2583 chd[i] = ((!leaf) &&
node->internal.has_child(i)) ?
2589 for (i = 0; i < 8; i++) {
2590 cellProcContour(chd[i],
node->internal.is_child_leaf(i), depth - 1);
2596 int df[2] = {depth - 1, depth - 1};
2597 for (i = 0; i < 12; i++) {
2600 lf[0] =
node->internal.is_child_leaf(c[0]);
2601 lf[1] =
node->internal.is_child_leaf(c[1]);
2612 int de[4] = {depth - 1, depth - 1, depth - 1, depth - 1};
2613 for (i = 0; i < 6; i++) {
2619 for (
int j = 0; j < 4; j++) {
2620 le[j] =
node->internal.is_child_leaf(c[j]);
2629void Octree::processEdgeParity(
LeafNode *
node[4],
const int [4],
int ,
int dir)
2632 for (
int i = 0; i < 4; i++) {
2644 for (
int i = 0; i < 4; i++) {
2650void Octree::edgeProcParity(
2651 Node *
node[4],
const int leaf[4],
const int depth[4],
int maxdep,
int dir)
2656 if (leaf[0] && leaf[1] && leaf[2] && leaf[3]) {
2657 processEdgeParity((LeafNode **)
node, depth, maxdep, dir);
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)) ?
2674 for (i = 0; i < 2; i++) {
2681 for (
int j = 0; j < 4; j++) {
2689 le[j] =
node[j]->internal.is_child_leaf(c[j]);
2690 ne[j] = chd[j][c[j]];
2691 de[j] = depth[j] - 1;
2700void Octree::faceProcParity(
2701 Node *
node[2],
const int leaf[2],
const int depth[2],
int maxdep,
int dir)
2707 if (!(leaf[0] && leaf[1])) {
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)) ?
2723 for (i = 0; i < 4; i++) {
2725 for (
int j = 0; j < 2; j++) {
2732 lf[j] =
node[j]->internal.is_child_leaf(c[j]);
2733 nf[j] = chd[j][c[j]];
2734 df[j] = depth[j] - 1;
2741 int orders[2][4] = {{0, 0, 1, 1}, {0, 1, 0, 1}};
2746 for (i = 0; i < 4; i++) {
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]];
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;
2771void Octree::cellProcParity(
Node *
node,
int leaf,
int depth)
2773 if (
node ==
nullptr) {
2782 for (i = 0; i < 8; i++) {
2783 chd[i] = ((!leaf) &&
node->internal.has_child(i)) ?
2789 for (i = 0; i < 8; i++) {
2790 cellProcParity(chd[i],
node->internal.is_child_leaf(i), depth - 1);
2796 int df[2] = {depth - 1, depth - 1};
2797 for (i = 0; i < 12; i++) {
2800 lf[0] =
node->internal.is_child_leaf(c[0]);
2801 lf[1] =
node->internal.is_child_leaf(c[1]);
2812 int de[4] = {depth - 1, depth - 1, depth - 1, depth - 1};
2813 for (i = 0; i < 6; i++) {
2819 for (
int j = 0; j < 4; j++) {
2820 le[j] =
node->internal.is_child_leaf(c[j]);
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}}};
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}}};
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}},
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}}};
SIMD_FORCE_INLINE btScalar norm() const
Return the norm (length) of the vector.
CubeTriangleIsect()=default
void shift(const int off[3])
int isIntersecting() const
int isIntersectingPrimary(int edgeInd) const
unsigned char getBoxMask()
TriangleProjection * inherit
Inheritable portion.
float getIntersectionPrimary(int edgeInd) const
void pushQueue(const int st[3], int dir)
int popQueue(int st[3], int &dir)
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.
VirtualMemoryAllocator * alloc[9]
VirtualMemoryAllocator * leafalloc[4]
Octree(const BoundBox &bbox)
virtual int getAllocated()=0
virtual void printInfo()=0
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 faceProcEdgeMask[3][4][6]
const int cellProcEdgeMask[6][5]
static void mass_point(float mp[3], const float pts[12][3], const int parity[12])
const int dirCell[3][4][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 faceProcEdgeMask[3][4][6]
const int cellProcEdgeMask[6][5]
void *(*) DualConAllocOutput(int totvert, int totquad)
void(*) DualConAddQuad(void *output, const int vert_indices[4])
void(*) DualConAddVert(void *output, const float co[3])
int midpoint(int a, int b)
const ManifoldIndices manifold_table[256]
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
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)
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
double norm[3]
Normal of the triangle.