101 for (
int i = 0; i < 8; i++) {
176extern const int dirCell[3][4][3];
300 void printMemUsage();
305 void resetMinimalEdges();
307 void cellProcParity(
Node *
node,
int leaf,
int depth);
308 void faceProcParity(
Node *
node[2],
const int leaf[2],
const int depth[2],
int maxdep,
int dir);
309 void edgeProcParity(
Node *
node[4],
const int leaf[4],
const int depth[4],
int maxdep,
int dir);
311 void processEdgeParity(
LeafNode *
node[4],
const int depths[4],
int maxdep,
int dir);
316 void addAllTriangles();
317 void addTriangle(
Triangle *trian,
int triind);
392 void getFacePoint(
PathElement *leaf,
int dir,
int &
x,
int &
y,
float &p,
float &q);
426 void buildSigns(
unsigned char table[],
Node *
node,
int isLeaf,
int sg,
int rvalue[8]);
432 void clearProcessBits(
Node *
node,
int height);
433 int floodFill(
LeafNode *leaf,
const int st[3],
int len,
int height,
int threshold);
434 int floodFill(
Node *
node,
int st[3],
int len,
int height,
int threshold);
441 void countIntersection(
Node *
node,
int height,
int &nedge,
int &ncell,
int &nface);
442 void generateMinimizer(
Node *
node,
int st[3],
int len,
int height,
int &offset);
443 void computeMinimizer(
const LeafNode *leaf,
int st[3],
int len,
float rvalue[3])
const;
448 void cellProcContour(
Node *
node,
int leaf,
int depth);
449 void faceProcContour(
Node *
node[2],
const int leaf[2],
const int depth[2],
int maxdep,
int dir);
450 void edgeProcContour(
Node *
node[4],
const int leaf[4],
int depth[4],
int maxdep,
int dir);
451 void processEdgeWrite(
Node *
node[4],
int depths[4],
int maxdep,
int dir);
463 int edgeCountTable[8][3];
468 for (
int i = 0; i < 256; i++) {
471 for (
int j = 0; j < 8; j++) {
475 count += ((i >> j) & 1);
479 for (
int i = 0; i < 8; i++) {
482 for (
int j = 0; j < 3; j++) {
483 numEdgeTable[i] += ((i >> j) & 1);
484 edgeCountTable[i][j] = count;
485 count += ((i >> j) & 1);
490 int getSign(Node *
node,
int height,
int index)
499 return getSign(
node->internal.get_child(0), height - 1, 7 -
node->internal.get_child_index(0));
504 void printInfo(
int st[3])
507 LeafNode *leaf = locateLeafCheck(st);
512 printf(
"Leaf not exists!\n");
516 void printInfo(
const LeafNode *leaf)
521 for (
int i = 0; i < 12; i++) {
522 printf(
"%d ", getEdgeParity(leaf, i));
525 printf(
"Stored edge mask: ");
526 for (
int i = 0; i < 3; i++) {
527 printf(
"%d ", getStoredEdgesParity(leaf, i));
533 for (
int i = 0; i < 8; i++) {
534 printf(
"%d ", getSign(leaf, i));
540 int getSign(
const LeafNode *leaf,
int index)
546 void setSign(LeafNode *leaf,
int index)
551 void setSign(LeafNode *leaf,
int index,
int sign)
557 int getSignMask(
const LeafNode *leaf)
const
562 void setInProcessAll(
const int st[3],
int dir)
565 for (
int i = 0; i < 4; i++) {
571 LeafNode *cell = locateLeafCheck(nst);
574 setInProcess(cell, eind);
578 void flipParityAll(
const int st[3],
int dir)
581 for (
int i = 0; i < 4; i++) {
587 LeafNode *cell = locateLeaf(nst);
588 flipEdge(cell, eind);
592 void setInProcess(LeafNode *leaf,
int eind)
594 assert(eind >= 0 && eind <= 11);
599 void setOutProcess(LeafNode *leaf,
int eind)
601 assert(eind >= 0 && eind <= 11);
606 int isInProcess(LeafNode *leaf,
int eind)
608 assert(eind >= 0 && eind <= 11);
614 void generateSigns(LeafNode *leaf,
const unsigned char table[],
int start)
618 if ((start ^ leaf->
signs) & 1) {
624 int getEdgeParity(
const LeafNode *leaf,
int index)
const
632 int getFaceParity(LeafNode *leaf,
int index)
638 int getFaceEdgeNum(LeafNode *leaf,
int index)
646 void flipEdge(LeafNode *leaf,
int index)
654 void setEdge(LeafNode *leaf,
int index)
662 void resetEdge(LeafNode *leaf,
int index)
670 void createPrimalEdgesMask(LeafNode *leaf)
675 void setStoredEdgesParity(LeafNode *leaf,
int pindex)
677 assert(pindex <= 2 && pindex >= 0);
682 int getStoredEdgesParity(
const LeafNode *leaf,
int pindex)
const
684 assert(pindex <= 2 && pindex >= 0);
689 LeafNode *flipEdge(LeafNode *leaf,
int index,
float alpha)
691 flipEdge(leaf,
index);
693 if ((
index & 3) == 0) {
695 if (getEdgeParity(leaf,
index) && !getStoredEdgesParity(leaf, ind)) {
697 int num = getNumEdges(leaf) + 1;
698 setStoredEdgesParity(leaf, ind);
699 int count = getEdgeCount(leaf, ind);
700 LeafNode *nleaf = createLeaf(num);
703 setEdgeOffset(nleaf, alpha, count);
708 for (
int i = 0; i < count; i++) {
713 for (
int i = count + 1; i <
num; i++) {
720 removeLeaf(num - 1, leaf);
729 void updateParent(InternalNode *
node,
int len,
int st[3], LeafNode *leaf)
733 InternalNode *parent = locateParent(
node,
len, st, count);
739 void updateParent(InternalNode *
node,
int len,
int st[3])
748 InternalNode *parent = locateParent(
len, st, count);
755 int getEdgeIntersectionByIndex(
int st[3],
int index,
float pt[3],
int check)
const
758 const LeafNode *leaf;
760 leaf = locateLeafCheck(st);
763 leaf = locateLeaf(st);
766 if (leaf && getStoredEdgesParity(leaf,
index)) {
767 float off = getEdgeOffset(leaf, getEdgeCount(leaf,
index));
768 pt[0] = (
float)st[0];
769 pt[1] = (
float)st[1];
770 pt[2] = (
float)st[2];
779 int getPrimalEdgesMask(
const LeafNode *leaf)
const
784 int getPrimalEdgesMask2(LeafNode *leaf)
791 int getEdgeCount(
const LeafNode *leaf,
int index)
const
793 return edgeCountTable[getPrimalEdgesMask(leaf)][
index];
795 int getNumEdges(LeafNode *leaf)
797 return numEdgeTable[getPrimalEdgesMask(leaf)];
800 int getNumEdges2(LeafNode *leaf)
802 return numEdgeTable[getPrimalEdgesMask2(leaf)];
806 void setEdgeOffset(LeafNode *leaf,
float pt,
int count)
816 void setEdgeOffsets(LeafNode *leaf,
const float pt[3],
int len)
819 for (
int i = 0; i <
len; i++) {
825 float getEdgeOffset(
const LeafNode *leaf,
int count)
const
831 LeafNode *updateEdgeOffsets(LeafNode *leaf,
int oldlen,
int newlen,
float offs[3])
834 LeafNode *nleaf = createLeaf(newlen);
838 setEdgeOffsets(nleaf, offs, newlen);
841 removeLeaf(oldlen, leaf);
847 void setMinimizerIndex(LeafNode *leaf,
int index)
853 int getMinimizerIndex(LeafNode *leaf)
858 int getMinimizerIndex(LeafNode *leaf,
int eind)
865 void getMinimizerIndices(LeafNode *leaf,
int eind,
int inds[2])
869 if (add[0] == add[1]) {
878 void setEdgeOffsetNormal(LeafNode *leaf,
float pt,
float a,
float b,
float c,
int count)
882 pts[4 * count + 1] = a;
883 pts[4 * count + 2] =
b;
884 pts[4 * count + 3] = c;
887 float getEdgeOffsetNormal(LeafNode *leaf,
int count,
float &a,
float &
b,
float &c)
890 a = pts[4 * count + 1];
891 b = pts[4 * count + 2];
892 c = pts[4 * count + 3];
893 return pts[4 * count];
897 void setEdgeOffsetsNormals(
898 LeafNode *leaf,
const float pt[],
const float a[],
const float b[],
const float c[],
int len)
901 for (
int i = 0; i <
len; i++) {
902 if (pt[i] > 1 || pt[i] < 0) {
903 printf(
"\noffset: %f\n", pt[i]);
906 pts[i * 4 + 1] = a[i];
907 pts[i * 4 + 2] =
b[i];
908 pts[i * 4 + 3] = c[i];
913 void getEdgeIntersectionByIndex(
914 const LeafNode *leaf,
int index,
const int st[3],
int len,
float pt[3],
float nm[3])
const
916 int count = getEdgeCount(leaf,
index);
919 float off = pts[4 * count];
921 pt[0] = (
float)st[0];
922 pt[1] = (
float)st[1];
923 pt[2] = (
float)st[2];
926 nm[0] = pts[4 * count + 1];
927 nm[1] = pts[4 * count + 2];
928 nm[2] = pts[4 * count + 3];
931 float getEdgeOffsetNormalByIndex(LeafNode *leaf,
int index,
float nm[3])
933 int count = getEdgeCount(leaf,
index);
936 float off = pts[4 * count];
938 nm[0] = pts[4 * count + 1];
939 nm[1] = pts[4 * count + 2];
940 nm[2] = pts[4 * count + 3];
945 void fillEdgeIntersections(
946 const LeafNode *leaf,
int st[3],
int len,
float pts[12][3],
float norms[12][3])
const
952 int pmask[3] = {0, 4, 8};
953 for (i = 0; i < 3; i++) {
954 if (getEdgeParity(leaf, pmask[i])) {
956 getEdgeIntersectionByIndex(leaf, i, st,
len, pts[pmask[i]], norms[pmask[i]]);
961 int fmask[3][2] = {{6, 10}, {2, 9}, {1, 5}};
962 int femask[3][2] = {{1, 2}, {0, 2}, {0, 1}};
963 for (i = 0; i < 3; i++) {
964 int e1 = getEdgeParity(leaf, fmask[i][0]);
965 int e2 = getEdgeParity(leaf, fmask[i][1]);
967 int nst[3] = {st[0], st[1], st[2]};
971 const LeafNode *
node = locateLeaf(nst);
976 getEdgeIntersectionByIndex(
977 node, femask[i][0], nst,
len, pts[fmask[i][0]], norms[fmask[i][0]]);
982 getEdgeIntersectionByIndex(
983 node, femask[i][1], nst,
len, pts[fmask[i][1]], norms[fmask[i][1]]);
989 int emask[3] = {3, 7, 11};
990 int eemask[3] = {0, 1, 2};
991 for (i = 0; i < 3; i++) {
992 if (getEdgeParity(leaf, emask[i])) {
993 int nst[3] = {st[0] +
len, st[1] +
len, st[2] +
len};
997 const LeafNode *
node = locateLeaf(nst);
1000 getEdgeIntersectionByIndex(
node, eemask[i], nst,
len, pts[emask[i]], norms[emask[i]]);
1005 void fillEdgeIntersections(
const LeafNode *leaf,
1010 int parity[12])
const
1013 for (i = 0; i < 12; i++) {
1019 int pmask[3] = {0, 4, 8};
1020 for (i = 0; i < 3; i++) {
1021 if (getStoredEdgesParity(leaf, i)) {
1023 getEdgeIntersectionByIndex(leaf, i, st,
len, pts[pmask[i]], norms[pmask[i]]);
1024 parity[pmask[i]] = 1;
1029 int fmask[3][2] = {{6, 10}, {2, 9}, {1, 5}};
1030 int femask[3][2] = {{1, 2}, {0, 2}, {0, 1}};
1031 for (i = 0; i < 3; i++) {
1033 int nst[3] = {st[0], st[1], st[2]};
1037 const LeafNode *
node = locateLeafCheck(nst);
1038 if (
node ==
nullptr) {
1042 int e1 = getStoredEdgesParity(
node, femask[i][0]);
1043 int e2 = getStoredEdgesParity(
node, femask[i][1]);
1048 getEdgeIntersectionByIndex(
1049 node, femask[i][0], nst,
len, pts[fmask[i][0]], norms[fmask[i][0]]);
1050 parity[fmask[i][0]] = 1;
1055 getEdgeIntersectionByIndex(
1056 node, femask[i][1], nst,
len, pts[fmask[i][1]], norms[fmask[i][1]]);
1057 parity[fmask[i][1]] = 1;
1063 int emask[3] = {3, 7, 11};
1064 int eemask[3] = {0, 1, 2};
1065 for (i = 0; i < 3; i++) {
1068 int nst[3] = {st[0] +
len, st[1] +
len, st[2] +
len};
1072 const LeafNode *
node = locateLeafCheck(nst);
1073 if (
node ==
nullptr) {
1077 if (getStoredEdgesParity(
node, eemask[i])) {
1079 getEdgeIntersectionByIndex(
node, eemask[i], nst,
len, pts[emask[i]], norms[emask[i]]);
1080 parity[emask[i]] = 1;
1086 void fillEdgeOffsetsNormals(
1087 LeafNode *leaf,
int st[3],
int len,
float pts[12],
float norms[12][3],
int parity[12])
1090 for (i = 0; i < 12; i++) {
1096 int pmask[3] = {0, 4, 8};
1097 for (i = 0; i < 3; i++) {
1098 if (getStoredEdgesParity(leaf, i)) {
1099 pts[pmask[i]] = getEdgeOffsetNormalByIndex(leaf, i, norms[pmask[i]]);
1100 parity[pmask[i]] = 1;
1105 int fmask[3][2] = {{6, 10}, {2, 9}, {1, 5}};
1106 int femask[3][2] = {{1, 2}, {0, 2}, {0, 1}};
1107 for (i = 0; i < 3; i++) {
1109 int nst[3] = {st[0], st[1], st[2]};
1113 LeafNode *
node = locateLeafCheck(nst);
1114 if (
node ==
nullptr) {
1118 int e1 = getStoredEdgesParity(
node, femask[i][0]);
1119 int e2 = getStoredEdgesParity(
node, femask[i][1]);
1122 pts[fmask[i][0]] = getEdgeOffsetNormalByIndex(
node, femask[i][0], norms[fmask[i][0]]);
1123 parity[fmask[i][0]] = 1;
1126 pts[fmask[i][1]] = getEdgeOffsetNormalByIndex(
node, femask[i][1], norms[fmask[i][1]]);
1127 parity[fmask[i][1]] = 1;
1133 int emask[3] = {3, 7, 11};
1134 int eemask[3] = {0, 1, 2};
1135 for (i = 0; i < 3; i++) {
1138 int nst[3] = {st[0] +
len, st[1] +
len, st[2] +
len};
1142 LeafNode *
node = locateLeafCheck(nst);
1143 if (
node ==
nullptr) {
1147 if (getStoredEdgesParity(
node, eemask[i])) {
1148 pts[emask[i]] = getEdgeOffsetNormalByIndex(
node, eemask[i], norms[emask[i]]);
1149 parity[emask[i]] = 1;
1156 LeafNode *updateEdgeOffsetsNormals(
1157 LeafNode *leaf,
int oldlen,
int newlen,
float offs[3],
float a[3],
float b[3],
float c[3])
1160 LeafNode *nleaf = createLeaf(newlen);
1164 setEdgeOffsetsNormals(nleaf, offs, a,
b, c, newlen);
1167 removeLeaf(oldlen, leaf);
1176 LeafNode *locateLeaf(
const int st[3])
1180 int index = (((st[0] >> i) & 1) << 2) | (((st[1] >> i) & 1) << 1) | (((st[2] >> i) & 1));
1187 const LeafNode *locateLeaf(
const int st[3])
const
1191 int index = (((st[0] >> i) & 1) << 2) | (((st[1] >> i) & 1) << 1) | (((st[2] >> i) & 1));
1198 LeafNode *locateLeaf(InternalNode *parent,
int len,
const int st[3])
1200 Node *
node = (Node *)parent;
1203 index = (((st[0] & i) ? 4 : 0) | ((st[1] & i) ? 2 : 0) | ((st[2] & i) ? 1 : 0));
1210 LeafNode *locateLeafCheck(
const int st[3])
1214 int index = (((st[0] >> i) & 1) << 2) | (((st[1] >> i) & 1) << 1) | (((st[2] >> i) & 1));
1224 const LeafNode *locateLeafCheck(
const int st[3])
const
1228 int index = (((st[0] >> i) & 1) << 2) | (((st[1] >> i) & 1) << 1) | (((st[2] >> i) & 1));
1238 InternalNode *locateParent(
int len,
const int st[3],
int &count)
1240 InternalNode *
node = (InternalNode *)
root;
1241 InternalNode *pre =
nullptr;
1243 for (
int i =
dimen / 2; i >=
len; i >>= 1) {
1244 index = (((st[0] & i) ? 4 : 0) | ((st[1] & i) ? 2 : 0) | ((st[2] & i) ? 1 : 0));
1253 InternalNode *locateParent(InternalNode *parent,
int len,
const int st[3],
int &count)
1255 InternalNode *
node = parent;
1256 InternalNode *pre =
nullptr;
1259 index = (((st[0] & i) ? 4 : 0) | ((st[1] & i) ? 2 : 0) | ((st[2] & i) ? 1 : 0));
1271 InternalNode *addChild(InternalNode *
node,
int index, Node *child,
int aLeaf)
1274 int num =
node->get_num_children();
1275 InternalNode *rnode = createInternal(num + 1);
1279 int count1 = 0, count2 = 0;
1280 for (i = 0; i < 8; i++) {
1290 else if (
node->has_child(i)) {
1291 if (
node->is_child_leaf(i)) {
1302 removeInternal(num,
node);
1307 InternalNode *createInternal(
int length)
1315 LeafNode *createLeaf(
int length)
1327 void removeInternal(
int num, InternalNode *
node)
1332 void removeLeaf(
int num, LeafNode *leaf)
1334 assert(num >= 0 && num <= 3);
1339 InternalNode *addLeafChild(InternalNode *par,
int index,
int count, LeafNode *leaf)
1342 InternalNode *npar = createInternal(num);
1350 for (i = 0; i < count; i++) {
1354 for (i = count + 1; i <
num; i++) {
1359 removeInternal(num - 1, par);
1363 InternalNode *addInternalChild(InternalNode *par,
int index,
int count, InternalNode *
node)
1366 InternalNode *npar = createInternal(num);
1374 for (i = 0; i < count; i++) {
1378 for (i = count + 1; i <
num; i++) {
1383 removeInternal(num - 1, par);
1387 MEM_CXX_CLASS_ALLOC_FUNCS(
"DUALCON:Octree")
btBroadphasePair * findPair(btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1)
SIMD_FORCE_INLINE btScalar length() const
Return the length of the vector.
unsigned short flood_fill
unsigned short primary_edge_intersections
float edge_intersections[0]
unsigned short in_process
unsigned short edge_parity
VirtualMemoryAllocator * alloc[9]
VirtualMemoryAllocator * leafalloc[4]
Octree(const BoundBox &bbox)
virtual void deallocate(void *obj)=0
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]
const int dirCell[3][4][3]
const int dirCell[3][4][3]
void *(*) DualConAllocOutput(int totvert, int totquad)
void(*) DualConAddQuad(void *output, const int vert_indices[4])
void(*) DualConAddVert(void *output, const float co[3])
#define assert(assertion)
const ManifoldIndices manifold_table[256]
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
void add(Depsgraph &depsgraph, std::function< void()> fn)
ATTR_WARN_UNUSED_RESULT const size_t num
void allocate(PageAllocator &allocator, TileMaps &tilemaps, Statistics &stats, const uint3 global_id, const uint local_tile)
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
unsigned char child_is_leaf_bitfield
Node * get_child(int count)
unsigned char has_child_bitfield
const Node * get_child(int count) const
static int childrenCountTable[256][8]
void set_leaf_child(int index, int count, LeafNode *chd)
int get_child_index(int count)
static int numChildrenTable[256]
int has_child(int index) const
static int childrenIndexTable[256][8]
int get_num_children() const
const int * get_child_counts() const
void fill_children(Node *children[8], int leaf[8])
int is_child_leaf(int index) const
void set_internal_child(int index, int count, InternalNode *chd)
void set_child(int count, Node *chd)
int get_child_count(int index) const