101 for (
int i = 0; i < 8; i++) {
169 extern const int faceMap[6][4];
176 extern const int dirCell[3][4][3];
177 extern const int dirEdge[3][4];
301 void printMemUsage();
306 void resetMinimalEdges();
308 void cellProcParity(
Node *
node,
int leaf,
int depth);
309 void faceProcParity(
Node *
node[2],
int leaf[2],
int depth[2],
int maxdep,
int dir);
310 void edgeProcParity(
Node *
node[4],
int leaf[4],
int depth[4],
int maxdep,
int dir);
312 void processEdgeParity(
LeafNode *
node[4],
int depths[4],
int maxdep,
int dir);
317 void addAllTriangles();
318 void addTriangle(
Triangle *trian,
int triind);
343 Node *
node[2],
int leaf[2],
int depth[2],
int *
st[2],
int maxdep,
int dir,
PathList *&paths);
388 void getFacePoint(
PathElement *leaf,
int dir,
int &
x,
int &
y,
float &p,
float &q);
422 void buildSigns(
unsigned char table[],
Node *
node,
int isLeaf,
int sg,
int rvalue[8]);
437 void countIntersection(
Node *
node,
int height,
int &nedge,
int &ncell,
int &nface);
439 void computeMinimizer(
const LeafNode *leaf,
int st[3],
int len,
float rvalue[3])
const;
444 void cellProcContour(
Node *
node,
int leaf,
int depth);
445 void faceProcContour(
Node *
node[2],
int leaf[2],
int depth[2],
int maxdep,
int dir);
446 void edgeProcContour(
Node *
node[4],
int leaf[4],
int depth[4],
int maxdep,
int dir);
447 void processEdgeWrite(
Node *
node[4],
int depths[4],
int maxdep,
int dir);
460 int edgeCountTable[8][3];
465 for (
int i = 0; i < 256; i++) {
468 for (
int j = 0; j < 8; j++) {
472 count += ((i >> j) & 1);
476 for (
int i = 0; i < 8; i++) {
479 for (
int j = 0; j < 3; j++) {
480 numEdgeTable[i] += ((i >> j) & 1);
481 edgeCountTable[i][j] =
count;
482 count += ((i >> j) & 1);
490 return getSign(&
node->leaf, index);
493 if (
node->internal.has_child(index)) {
495 node->internal.get_child(
node->internal.get_child_count(index)),
height - 1, index);
499 node->internal.get_child(0),
height - 1, 7 -
node->internal.get_child_index(0));
506 void printInfo(
int st[3])
513 printf(
"Leaf not exists!\n");
516 void printInfo(
const LeafNode *leaf)
532 printf(
"Sign mask: ");
533 for (
int i = 0; i < 8; i++) {
534 printf(
"%d ", getSign(leaf, i));
540 int getSign(
const LeafNode *leaf,
int index)
542 return ((leaf->
signs >> index) & 1);
546 void setSign(
LeafNode *leaf,
int index)
548 leaf->
signs |= (1 << index);
553 leaf->
signs &= (~(1 << index));
557 int getSignMask(
const LeafNode *leaf)
const
562 void setInProcessAll(
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(
int st[3],
int dir)
581 for (
int i = 0; i < 4; i++) {
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,
unsigned char table[],
int start)
618 if ((start ^ leaf->
signs) & 1) {
624 int getEdgeParity(
const LeafNode *leaf,
int index)
const
626 assert(index >= 0 && index <= 11);
632 int getFaceParity(
LeafNode *leaf,
int index)
634 int a = getEdgeParity(leaf,
faceMap[index][0]) + getEdgeParity(leaf,
faceMap[index][1]) +
635 getEdgeParity(leaf,
faceMap[index][2]) + getEdgeParity(leaf,
faceMap[index][3]);
638 int getFaceEdgeNum(
LeafNode *leaf,
int index)
640 int a = getEdgeParity(leaf,
faceMap[index][0]) + getEdgeParity(leaf,
faceMap[index][1]) +
641 getEdgeParity(leaf,
faceMap[index][2]) + getEdgeParity(leaf,
faceMap[index][3]);
646 void flipEdge(
LeafNode *leaf,
int index)
648 assert(index >= 0 && index <= 11);
654 void setEdge(
LeafNode *leaf,
int index)
656 assert(index >= 0 && index <= 11);
662 void resetEdge(
LeafNode *leaf,
int index)
664 assert(index >= 0 && index <= 11);
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);
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);
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, (
LeafNode *)leaf);
755 int getEdgeIntersectionByIndex(
int st[3],
int index,
float pt[3],
int check)
const
760 leaf = locateLeafCheck(
st);
763 leaf = locateLeaf(
st);
766 if (leaf && getStoredEdgesParity(leaf, index)) {
767 float off = getEdgeOffset(leaf, getEdgeCount(leaf, index));
781 int getPrimalEdgesMask(
const LeafNode *leaf)
const
786 int getPrimalEdgesMask2(
LeafNode *leaf)
793 int getEdgeCount(
const LeafNode *leaf,
int index)
const
795 return edgeCountTable[getPrimalEdgesMask(leaf)][index];
799 return numEdgeTable[getPrimalEdgesMask(leaf)];
804 return numEdgeTable[getPrimalEdgesMask2(leaf)];
818 void setEdgeOffsets(
LeafNode *leaf,
float pt[3],
int len)
821 for (
int i = 0; i <
len; i++) {
833 LeafNode *updateEdgeOffsets(
LeafNode *leaf,
int oldlen,
int newlen,
float offs[3])
836 LeafNode *nleaf = createLeaf(newlen);
840 setEdgeOffsets(nleaf, offs, newlen);
843 removeLeaf(oldlen, leaf);
849 void setMinimizerIndex(
LeafNode *leaf,
int index)
855 int getMinimizerIndex(
LeafNode *leaf)
860 int getMinimizerIndex(
LeafNode *leaf,
int eind)
867 void getMinimizerIndices(
LeafNode *leaf,
int eind,
int inds[2])
880 void setEdgeOffsetNormal(
LeafNode *leaf,
float pt,
float a,
float b,
float c,
int count)
889 float getEdgeOffsetNormal(
LeafNode *leaf,
int count,
float &
a,
float &
b,
float &
c)
895 return pts[4 *
count];
899 void setEdgeOffsetsNormals(
900 LeafNode *leaf,
const float pt[],
const float a[],
const float b[],
const float c[],
int len)
903 for (
int i = 0; i <
len; i++) {
904 if (pt[i] > 1 || pt[i] < 0) {
905 printf(
"\noffset: %f\n", pt[i]);
908 pts[i * 4 + 1] =
a[i];
909 pts[i * 4 + 2] =
b[i];
910 pts[i * 4 + 3] =
c[i];
915 void getEdgeIntersectionByIndex(
916 const LeafNode *leaf,
int index,
int st[3],
int len,
float pt[3],
float nm[3])
const
918 int count = getEdgeCount(leaf, index);
921 float off = pts[4 *
count];
926 pt[index] += (off *
len);
928 nm[0] = pts[4 *
count + 1];
929 nm[1] = pts[4 *
count + 2];
930 nm[2] = pts[4 *
count + 3];
933 float getEdgeOffsetNormalByIndex(
LeafNode *leaf,
int index,
float nm[3])
935 int count = getEdgeCount(leaf, index);
938 float off = pts[4 *
count];
940 nm[0] = pts[4 *
count + 1];
941 nm[1] = pts[4 *
count + 2];
942 nm[2] = pts[4 *
count + 3];
947 void fillEdgeIntersections(
948 const LeafNode *leaf,
int st[3],
int len,
float pts[12][3],
float norms[12][3])
const
954 int pmask[3] = {0, 4, 8};
955 for (i = 0; i < 3; i++) {
956 if (getEdgeParity(leaf, pmask[i])) {
958 getEdgeIntersectionByIndex(leaf, i,
st,
len, pts[pmask[i]], norms[pmask[i]]);
963 int fmask[3][2] = {{6, 10}, {2, 9}, {1, 5}};
964 int femask[3][2] = {{1, 2}, {0, 2}, {0, 1}};
965 for (i = 0; i < 3; i++) {
966 int e1 = getEdgeParity(leaf, fmask[i][0]);
967 int e2 = getEdgeParity(leaf, fmask[i][1]);
969 int nst[3] = {
st[0],
st[1],
st[2]};
978 getEdgeIntersectionByIndex(
979 node, femask[i][0], nst,
len, pts[fmask[i][0]], norms[fmask[i][0]]);
984 getEdgeIntersectionByIndex(
985 node, femask[i][1], nst,
len, pts[fmask[i][1]], norms[fmask[i][1]]);
991 int emask[3] = {3, 7, 11};
992 int eemask[3] = {0, 1, 2};
993 for (i = 0; i < 3; i++) {
994 if (getEdgeParity(leaf, emask[i])) {
1002 getEdgeIntersectionByIndex(
node, eemask[i], nst,
len, pts[emask[i]], norms[emask[i]]);
1007 void fillEdgeIntersections(
const LeafNode *leaf,
1012 int parity[12])
const
1015 for (i = 0; i < 12; i++) {
1021 int pmask[3] = {0, 4, 8};
1022 for (i = 0; i < 3; i++) {
1023 if (getStoredEdgesParity(leaf, i)) {
1025 getEdgeIntersectionByIndex(leaf, i,
st,
len, pts[pmask[i]], norms[pmask[i]]);
1026 parity[pmask[i]] = 1;
1031 int fmask[3][2] = {{6, 10}, {2, 9}, {1, 5}};
1032 int femask[3][2] = {{1, 2}, {0, 2}, {0, 1}};
1033 for (i = 0; i < 3; i++) {
1035 int nst[3] = {
st[0],
st[1],
st[2]};
1044 int e1 = getStoredEdgesParity(
node, femask[i][0]);
1045 int e2 = getStoredEdgesParity(
node, femask[i][1]);
1050 getEdgeIntersectionByIndex(
1051 node, femask[i][0], nst,
len, pts[fmask[i][0]], norms[fmask[i][0]]);
1052 parity[fmask[i][0]] = 1;
1057 getEdgeIntersectionByIndex(
1058 node, femask[i][1], nst,
len, pts[fmask[i][1]], norms[fmask[i][1]]);
1059 parity[fmask[i][1]] = 1;
1065 int emask[3] = {3, 7, 11};
1066 int eemask[3] = {0, 1, 2};
1067 for (i = 0; i < 3; i++) {
1079 if (getStoredEdgesParity(
node, eemask[i])) {
1081 getEdgeIntersectionByIndex(
node, eemask[i], nst,
len, pts[emask[i]], norms[emask[i]]);
1082 parity[emask[i]] = 1;
1088 void fillEdgeOffsetsNormals(
1089 LeafNode *leaf,
int st[3],
int len,
float pts[12],
float norms[12][3],
int parity[12])
1092 for (i = 0; i < 12; i++) {
1098 int pmask[3] = {0, 4, 8};
1099 for (i = 0; i < 3; i++) {
1100 if (getStoredEdgesParity(leaf, i)) {
1101 pts[pmask[i]] = getEdgeOffsetNormalByIndex(leaf, i, norms[pmask[i]]);
1102 parity[pmask[i]] = 1;
1107 int fmask[3][2] = {{6, 10}, {2, 9}, {1, 5}};
1108 int femask[3][2] = {{1, 2}, {0, 2}, {0, 1}};
1109 for (i = 0; i < 3; i++) {
1111 int nst[3] = {
st[0],
st[1],
st[2]};
1120 int e1 = getStoredEdgesParity(
node, femask[i][0]);
1121 int e2 = getStoredEdgesParity(
node, femask[i][1]);
1124 pts[fmask[i][0]] = getEdgeOffsetNormalByIndex(
node, femask[i][0], norms[fmask[i][0]]);
1125 parity[fmask[i][0]] = 1;
1128 pts[fmask[i][1]] = getEdgeOffsetNormalByIndex(
node, femask[i][1], norms[fmask[i][1]]);
1129 parity[fmask[i][1]] = 1;
1135 int emask[3] = {3, 7, 11};
1136 int eemask[3] = {0, 1, 2};
1137 for (i = 0; i < 3; i++) {
1149 if (getStoredEdgesParity(
node, eemask[i])) {
1150 pts[emask[i]] = getEdgeOffsetNormalByIndex(
node, eemask[i], norms[emask[i]]);
1151 parity[emask[i]] = 1;
1158 LeafNode *updateEdgeOffsetsNormals(
1159 LeafNode *leaf,
int oldlen,
int newlen,
float offs[3],
float a[3],
float b[3],
float c[3])
1162 LeafNode *nleaf = createLeaf(newlen);
1166 setEdgeOffsetsNormals(nleaf, offs,
a,
b,
c, newlen);
1169 removeLeaf(oldlen, leaf);
1181 int index = (((
st[0] >> i) & 1) << 2) | (((
st[1] >> i) & 1) << 1) | (((
st[2] >> i) & 1));
1182 node =
node->internal.get_child(
node->internal.get_child_count(index));
1192 int index = (((
st[0] >> i) & 1) << 2) | (((
st[1] >> i) & 1) << 1) | (((
st[2] >> i) & 1));
1193 node =
node->internal.get_child(
node->internal.get_child_count(index));
1204 index = (((
st[0] & i) ? 4 : 0) | ((
st[1] & i) ? 2 : 0) | ((
st[2] & i) ? 1 : 0));
1205 node =
node->internal.get_child(
node->internal.get_child_count(index));
1215 int index = (((
st[0] >> i) & 1) << 2) | (((
st[1] >> i) & 1) << 1) | (((
st[2] >> i) & 1));
1216 if (!
node->internal.has_child(index)) {
1219 node =
node->internal.get_child(
node->internal.get_child_count(index));
1225 const LeafNode *locateLeafCheck(
int st[3])
const
1229 int index = (((
st[0] >> i) & 1) << 2) | (((
st[1] >> i) & 1) << 1) | (((
st[2] >> i) & 1));
1230 if (!
node->internal.has_child(index)) {
1233 node =
node->internal.get_child(
node->internal.get_child_count(index));
1244 for (
int i =
dimen / 2; i >=
len; i >>= 1) {
1245 index = (((
st[0] & i) ? 4 : 0) | ((
st[1] & i) ? 2 : 0) | ((
st[2] & i) ? 1 : 0));
1247 node = &
node->get_child(
node->get_child_count(index))->
internal;
1260 index = (((
st[0] & i) ? 4 : 0) | ((
st[1] & i) ? 2 : 0) | ((
st[2] & i) ? 1 : 0));
1262 node = &
node->get_child(
node->get_child_count(index))->
internal;
1275 int num =
node->get_num_children();
1280 int count1 = 0, count2 = 0;
1281 for (i = 0; i < 8; i++) {
1291 else if (
node->has_child(i)) {
1292 if (
node->is_child_leaf(i)) {
1303 removeInternal(num,
node);
1333 void removeLeaf(
int num,
LeafNode *leaf)
1335 assert(num >= 0 && num <= 3);
1351 for (i = 0; i <
count; i++) {
1355 for (i =
count + 1; i < num; i++) {
1360 removeInternal(num - 1, par);
1375 for (i = 0; i <
count; i++) {
1379 for (i =
count + 1; i < num; i++) {
1384 removeInternal(num - 1, par);
1388 #ifdef WITH_CXX_GUARDEDALLOC
1389 MEM_CXX_CLASS_ALLOC_FUNCS(
"DUALCON:Octree")
typedef float(TangentPoint)[2]
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei height
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint y
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
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(ModelReader *mr, DualConAllocOutput alloc_output_func, DualConAddVert add_vert_func, DualConAddQuad add_quad_func, DualConFlags flags, DualConMode mode, int depth, float threshold, float hermite_num)
virtual void deallocate(void *obj)=0
void(* DualConAddQuad)(void *output, const int vert_indices[4])
void(* DualConAddVert)(void *output, const float co[3])
void *(* DualConAllocOutput)(int totvert, int totquad)
ccl_gpu_kernel_postfix ccl_global float int int int int float threshold
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
const ManifoldIndices manifold_table[256]
bool add(void *owner, const AttributeIDRef &attribute_id, eAttrDomain domain, eCustomDataType data_type, const AttributeInit &initializer)
T length(const vec_base< T, Size > &a)
static const pxr::TfToken st("st", pxr::TfToken::Immortal)
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
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]
unsigned char child_is_leaf_bitfield
Node * get_child(int count)
unsigned char has_child_bitfield
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
const int * get_child_counts() const
static int childrenIndexTable[256][8]
int get_num_children() 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)
const Node * get_child(int count) const
int get_child_count(int index) const