Blender  V3.3
octree.h
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #ifndef __OCTREE_H__
4 #define __OCTREE_H__
5 
6 #include "GeoCommon.h"
7 #include "MemoryAllocator.h"
8 #include "ModelReader.h"
9 #include "Projections.h"
10 #include "Queue.h"
11 #include "cubes.h"
12 #include "dualcon.h"
13 #include "manifold_table.h"
14 #include <cassert>
15 #include <cstring>
16 #include <math.h>
17 #include <stdio.h>
18 
26 /* Global defines */
27 /* Uncomment to see debug information */
28 // #define IN_DEBUG_MODE
29 
30 /* Uncomment to see more output messages during repair */
31 // #define IN_VERBOSE_MODE
32 
33 /* Set scan convert params */
34 
35 #define EDGE_FLOATS 4
36 
37 union Node;
38 struct LeafNode;
39 
40 struct InternalNode {
41  /* Initialized in Octree::BuildTable */
42  static int numChildrenTable[256];
43  static int childrenCountTable[256][8];
44  static int childrenIndexTable[256][8];
45 
46  /* Bit N indicates whether child N exists or not */
47  unsigned char has_child_bitfield;
48  /* Bit N indicates whether child N is a leaf or not */
49  unsigned char child_is_leaf_bitfield;
50 
51  /* Can have up to eight children */
53 
55  int is_child_leaf(int index) const
56  {
57  return (child_is_leaf_bitfield >> index) & 1;
58  }
59 
61  int has_child(int index) const
62  {
63  return (has_child_bitfield >> index) & 1;
64  }
65 
68  {
69  return children[count];
70  }
71 
72  const Node *get_child(int count) const
73  {
74  return children[count];
75  }
76 
78  int get_num_children() const
79  {
81  }
82 
84  int get_child_count(int index) const
85  {
87  }
89  {
91  }
92  const int *get_child_counts() const
93  {
95  }
96 
98  void fill_children(Node *children[8], int leaf[8])
99  {
100  int count = 0;
101  for (int i = 0; i < 8; i++) {
102  leaf[i] = is_child_leaf(i);
103  if (has_child(i)) {
104  children[i] = get_child(count);
105  count++;
106  }
107  else {
108  children[i] = NULL;
109  leaf[i] = 0;
110  }
111  }
112  }
113 
115  void set_child(int count, Node *chd)
116  {
117  children[count] = chd;
118  }
119  void set_internal_child(int index, int count, InternalNode *chd)
120  {
121  set_child(count, (Node *)chd);
122  has_child_bitfield |= (1 << index);
123  }
124  void set_leaf_child(int index, int count, LeafNode *chd)
125  {
126  set_child(count, (Node *)chd);
127  has_child_bitfield |= (1 << index);
128  child_is_leaf_bitfield |= (1 << index);
129  }
130 };
131 
143 struct LeafNode /* TODO: remove this attribute once everything is fixed */ {
144  unsigned short edge_parity : 12;
145  unsigned short primary_edge_intersections : 3;
146 
147  /* XXX: maybe actually unused? */
148  unsigned short in_process : 1;
149 
150  /* bitfield */
151  char signs;
152 
154 
155  unsigned short flood_fill;
156 
158 };
159 
160 /* Doesn't get directly allocated anywhere, just used for passing
161  pointers to nodes that could be internal or leaf. */
162 union Node {
163  InternalNode internal;
165 };
166 
167 /* Global variables */
168 extern const int edgemask[3];
169 extern const int faceMap[6][4];
170 extern const int cellProcFaceMask[12][3];
171 extern const int cellProcEdgeMask[6][5];
172 extern const int faceProcFaceMask[3][4][3];
173 extern const int edgeProcEdgeMask[3][2][5];
174 extern const int faceProcEdgeMask[3][4][6];
175 extern const int processEdgeMask[3][4];
176 extern const int dirCell[3][4][3];
177 extern const int dirEdge[3][4];
178 
183 struct PathElement {
184  /* Origin */
185  int pos[3];
186 
187  /* link */
189 };
190 
191 struct PathList {
192  /* Head */
195 
196  /* Length of the list */
197  int length;
198 
199  /* Next list */
201 };
202 
206 class Octree {
207  public:
208  /* Public members */
209 
213 
216 
219 
222 
224  int dimen;
226 
228  int maxDepth;
229 
231  float origin[3];
232  float range;
233 
237  int nodeCounts[9];
238 
240 
242 
244  int outType; /* 0 for OFF, 1 for PLY, 2 for VOL */
245 
246  /* For flood filling */
248  float thresh;
249 
251 
252  float hermite_num;
253 
255 
256  public:
260  Octree(ModelReader *mr,
261  DualConAllocOutput alloc_output_func,
262  DualConAddVert add_vert_func,
263  DualConAddQuad add_quad_func,
264  DualConFlags flags,
266  int depth,
267  float threshold,
268  float hermite_num);
269 
273  ~Octree();
274 
278  void scanConvert();
279 
281  {
282  return output_mesh;
283  }
284 
285  private:
286  /* Helper functions */
287 
291  void initMemory();
292 
296  void freeMemory();
297 
301  void printMemUsage();
302 
306  void resetMinimalEdges();
307 
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);
311 
312  void processEdgeParity(LeafNode *node[4], int depths[4], int maxdep, int dir);
313 
317  void addAllTriangles();
318  void addTriangle(Triangle *trian, int triind);
319  InternalNode *addTriangle(InternalNode *node, CubeTriangleIsect *p, int height);
320 
324  LeafNode *updateCell(LeafNode *node, CubeTriangleIsect *p);
325 
326  /* Routines to detect and patch holes */
327  int numRings;
328  int totRingLengths;
329  int maxRingLength;
330 
334  void trace();
338  Node *trace(Node *node, int *st, int len, int depth, PathList *&paths);
342  void findPaths(
343  Node *node[2], int leaf[2], int depth[2], int *st[2], int maxdep, int dir, PathList *&paths);
348  void combinePaths(PathList *&list1, PathList *list2, PathList *paths, PathList *&rings);
352  PathList *combineSinglePath(PathList *&head1,
353  PathList *pre1,
354  PathList *&list1,
355  PathList *&head2,
356  PathList *pre2,
357  PathList *&list2);
358 
362  Node *patch(Node *node, int st[3], int len, PathList *rings);
363  Node *patchSplit(Node *node,
364  int st[3],
365  int len,
366  PathList *rings,
367  int dir,
368  PathList *&nrings1,
369  PathList *&nrings2);
370  Node *patchSplitSingle(Node *node,
371  int st[3],
372  int len,
373  PathElement *head,
374  int dir,
375  PathList *&nrings1,
376  PathList *&nrings2);
377  Node *connectFace(Node *node, int st[3], int len, int dir, PathElement *f1, PathElement *f2);
378  Node *locateCell(InternalNode *node,
379  int st[3],
380  int len,
381  int ori[3],
382  int dir,
383  int side,
384  Node *&rleaf,
385  int rst[3],
386  int &rlen);
387  void compressRing(PathElement *&ring);
388  void getFacePoint(PathElement *leaf, int dir, int &x, int &y, float &p, float &q);
389  LeafNode *patchAdjacent(InternalNode *node,
390  int len,
391  int st1[3],
392  LeafNode *leaf1,
393  int st2[3],
394  LeafNode *leaf2,
395  int walkdir,
396  int inc,
397  int dir,
398  int side,
399  float alpha);
400  int findPair(PathElement *head, int pos, int dir, PathElement *&pre1, PathElement *&pre2);
401  int getSide(PathElement *e, int pos, int dir);
402  int isEqual(PathElement *e1, PathElement *e2);
403  void preparePrimalEdgesMask(InternalNode *node);
404  void testFacePoint(PathElement *e1, PathElement *e2);
405 
409  void deletePath(PathList *&head, PathList *pre, PathList *&curr);
410  void printPath(PathList *path);
411  void printPath(PathElement *path);
412  void printElement(PathElement *ele);
413  void printPaths(PathList *path);
414  void checkElement(PathElement *ele);
415  void checkPath(PathElement *path);
416 
421  void buildSigns();
422  void buildSigns(unsigned char table[], Node *node, int isLeaf, int sg, int rvalue[8]);
423 
424  /************************************************************************/
425  /* To remove disconnected components */
426  /************************************************************************/
427  void floodFill();
428  void clearProcessBits(Node *node, int height);
429  int floodFill(LeafNode *leaf, int st[3], int len, int height, int threshold);
430  int floodFill(Node *node, int st[3], int len, int height, int threshold);
431 
435  void writeOut();
436 
437  void countIntersection(Node *node, int height, int &nedge, int &ncell, int &nface);
438  void generateMinimizer(Node *node, int st[3], int len, int height, int &offset);
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);
448 
449  /* output callbacks/data */
450  DualConAllocOutput alloc_output;
451  DualConAddVert add_vert;
452  DualConAddQuad add_quad;
453  void *output_mesh;
454 
455  private:
456  /************ Operators for all nodes ************/
457 
459  int numEdgeTable[8];
460  int edgeCountTable[8][3];
461 
463  void buildTable()
464  {
465  for (int i = 0; i < 256; i++) {
467  int count = 0;
468  for (int j = 0; j < 8; j++) {
469  InternalNode::numChildrenTable[i] += ((i >> j) & 1);
472  count += ((i >> j) & 1);
473  }
474  }
475 
476  for (int i = 0; i < 8; i++) {
477  numEdgeTable[i] = 0;
478  int count = 0;
479  for (int j = 0; j < 3; j++) {
480  numEdgeTable[i] += ((i >> j) & 1);
481  edgeCountTable[i][j] = count;
482  count += ((i >> j) & 1);
483  }
484  }
485  }
486 
487  int getSign(Node *node, int height, int index)
488  {
489  if (height == 0) {
490  return getSign(&node->leaf, index);
491  }
492  else {
493  if (node->internal.has_child(index)) {
494  return getSign(
495  node->internal.get_child(node->internal.get_child_count(index)), height - 1, index);
496  }
497  else {
498  return getSign(
499  node->internal.get_child(0), height - 1, 7 - node->internal.get_child_index(0));
500  }
501  }
502  }
503 
504  /************ Operators for leaf nodes ************/
505 
506  void printInfo(int st[3])
507  {
508  printf("INFO AT: %d %d %d\n", st[0] >> minshift, st[1] >> minshift, st[2] >> minshift);
509  LeafNode *leaf = (LeafNode *)locateLeafCheck(st);
510  if (leaf)
511  printInfo(leaf);
512  else
513  printf("Leaf not exists!\n");
514  }
515 
516  void printInfo(const LeafNode *leaf)
517  {
518  /*
519  printf("Edge mask: ");
520  for(int i = 0; i < 12; i ++)
521  {
522  printf("%d ", getEdgeParity(leaf, i));
523  }
524  printf("\n");
525  printf("Stored edge mask: ");
526  for(i = 0; i < 3; i ++)
527  {
528  printf("%d ", getStoredEdgesParity(leaf, i));
529  }
530  printf("\n");
531  */
532  printf("Sign mask: ");
533  for (int i = 0; i < 8; i++) {
534  printf("%d ", getSign(leaf, i));
535  }
536  printf("\n");
537  }
538 
540  int getSign(const LeafNode *leaf, int index)
541  {
542  return ((leaf->signs >> index) & 1);
543  }
544 
546  void setSign(LeafNode *leaf, int index)
547  {
548  leaf->signs |= (1 << index);
549  }
550 
551  void setSign(LeafNode *leaf, int index, int sign)
552  {
553  leaf->signs &= (~(1 << index));
554  leaf->signs |= ((sign & 1) << index);
555  }
556 
557  int getSignMask(const LeafNode *leaf) const
558  {
559  return leaf->signs;
560  }
561 
562  void setInProcessAll(int st[3], int dir)
563  {
564  int nst[3], eind;
565  for (int i = 0; i < 4; i++) {
566  nst[0] = st[0] + dirCell[dir][i][0] * mindimen;
567  nst[1] = st[1] + dirCell[dir][i][1] * mindimen;
568  nst[2] = st[2] + dirCell[dir][i][2] * mindimen;
569  eind = dirEdge[dir][i];
570 
571  LeafNode *cell = locateLeafCheck(nst);
572  assert(cell);
573 
574  setInProcess(cell, eind);
575  }
576  }
577 
578  void flipParityAll(int st[3], int dir)
579  {
580  int nst[3], eind;
581  for (int i = 0; i < 4; i++) {
582  nst[0] = st[0] + dirCell[dir][i][0] * mindimen;
583  nst[1] = st[1] + dirCell[dir][i][1] * mindimen;
584  nst[2] = st[2] + dirCell[dir][i][2] * mindimen;
585  eind = dirEdge[dir][i];
586 
587  LeafNode *cell = locateLeaf(nst);
588  flipEdge(cell, eind);
589  }
590  }
591 
592  void setInProcess(LeafNode *leaf, int eind)
593  {
594  assert(eind >= 0 && eind <= 11);
595 
596  leaf->flood_fill |= (1 << eind);
597  }
598 
599  void setOutProcess(LeafNode *leaf, int eind)
600  {
601  assert(eind >= 0 && eind <= 11);
602 
603  leaf->flood_fill &= ~(1 << eind);
604  }
605 
606  int isInProcess(LeafNode *leaf, int eind)
607  {
608  assert(eind >= 0 && eind <= 11);
609 
610  return (leaf->flood_fill >> eind) & 1;
611  }
612 
614  void generateSigns(LeafNode *leaf, unsigned char table[], int start)
615  {
616  leaf->signs = table[leaf->edge_parity];
617 
618  if ((start ^ leaf->signs) & 1) {
619  leaf->signs = ~(leaf->signs);
620  }
621  }
622 
624  int getEdgeParity(const LeafNode *leaf, int index) const
625  {
626  assert(index >= 0 && index <= 11);
627 
628  return (leaf->edge_parity >> index) & 1;
629  }
630 
632  int getFaceParity(LeafNode *leaf, int index)
633  {
634  int a = getEdgeParity(leaf, faceMap[index][0]) + getEdgeParity(leaf, faceMap[index][1]) +
635  getEdgeParity(leaf, faceMap[index][2]) + getEdgeParity(leaf, faceMap[index][3]);
636  return (a & 1);
637  }
638  int getFaceEdgeNum(LeafNode *leaf, int index)
639  {
640  int a = getEdgeParity(leaf, faceMap[index][0]) + getEdgeParity(leaf, faceMap[index][1]) +
641  getEdgeParity(leaf, faceMap[index][2]) + getEdgeParity(leaf, faceMap[index][3]);
642  return a;
643  }
644 
646  void flipEdge(LeafNode *leaf, int index)
647  {
648  assert(index >= 0 && index <= 11);
649 
650  leaf->edge_parity ^= (1 << index);
651  }
652 
654  void setEdge(LeafNode *leaf, int index)
655  {
656  assert(index >= 0 && index <= 11);
657 
658  leaf->edge_parity |= (1 << index);
659  }
660 
662  void resetEdge(LeafNode *leaf, int index)
663  {
664  assert(index >= 0 && index <= 11);
665 
666  leaf->edge_parity &= ~(1 << index);
667  }
668 
670  void createPrimalEdgesMask(LeafNode *leaf)
671  {
672  leaf->primary_edge_intersections = getPrimalEdgesMask2(leaf);
673  }
674 
675  void setStoredEdgesParity(LeafNode *leaf, int pindex)
676  {
677  assert(pindex <= 2 && pindex >= 0);
678 
679  leaf->primary_edge_intersections |= (1 << pindex);
680  }
681 
682  int getStoredEdgesParity(const LeafNode *leaf, int pindex) const
683  {
684  assert(pindex <= 2 && pindex >= 0);
685 
686  return (leaf->primary_edge_intersections >> pindex) & 1;
687  }
688 
689  LeafNode *flipEdge(LeafNode *leaf, int index, float alpha)
690  {
691  flipEdge(leaf, index);
692 
693  if ((index & 3) == 0) {
694  int ind = index / 4;
695  if (getEdgeParity(leaf, index) && !getStoredEdgesParity(leaf, ind)) {
696  /* Create a new node */
697  int num = getNumEdges(leaf) + 1;
698  setStoredEdgesParity(leaf, ind);
699  int count = getEdgeCount(leaf, ind);
700  LeafNode *nleaf = createLeaf(num);
701  *nleaf = *leaf;
702 
703  setEdgeOffset(nleaf, alpha, count);
704 
705  if (num > 1) {
706  float *pts = leaf->edge_intersections;
707  float *npts = nleaf->edge_intersections;
708  for (int i = 0; i < count; i++) {
709  for (int j = 0; j < EDGE_FLOATS; j++) {
710  npts[i * EDGE_FLOATS + j] = pts[i * EDGE_FLOATS + j];
711  }
712  }
713  for (int i = count + 1; i < num; i++) {
714  for (int j = 0; j < EDGE_FLOATS; j++) {
715  npts[i * EDGE_FLOATS + j] = pts[(i - 1) * EDGE_FLOATS + j];
716  }
717  }
718  }
719 
720  removeLeaf(num - 1, (LeafNode *)leaf);
721  leaf = nleaf;
722  }
723  }
724 
725  return leaf;
726  }
727 
729  void updateParent(InternalNode *node, int len, int st[3], LeafNode *leaf)
730  {
731  /* First, locate the parent */
732  int count;
733  InternalNode *parent = locateParent(node, len, st, count);
734 
735  /* Update */
736  parent->set_child(count, (Node *)leaf);
737  }
738 
739  void updateParent(InternalNode *node, int len, int st[3])
740  {
741  if (len == dimen) {
742  root = (Node *)node;
743  return;
744  }
745 
746  /* First, locate the parent */
747  int count;
748  InternalNode *parent = locateParent(len, st, count);
749 
750  /* Update */
751  parent->set_child(count, (Node *)node);
752  }
753 
755  int getEdgeIntersectionByIndex(int st[3], int index, float pt[3], int check) const
756  {
757  /* First, locat the leaf */
758  const LeafNode *leaf;
759  if (check) {
760  leaf = locateLeafCheck(st);
761  }
762  else {
763  leaf = locateLeaf(st);
764  }
765 
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];
771  pt[index] += off * mindimen;
772 
773  return 1;
774  }
775  else {
776  return 0;
777  }
778  }
779 
781  int getPrimalEdgesMask(const LeafNode *leaf) const
782  {
783  return leaf->primary_edge_intersections;
784  }
785 
786  int getPrimalEdgesMask2(LeafNode *leaf)
787  {
788  return (((leaf->edge_parity & 0x1) >> 0) | ((leaf->edge_parity & 0x10) >> 3) |
789  ((leaf->edge_parity & 0x100) >> 6));
790  }
791 
793  int getEdgeCount(const LeafNode *leaf, int index) const
794  {
795  return edgeCountTable[getPrimalEdgesMask(leaf)][index];
796  }
797  int getNumEdges(LeafNode *leaf)
798  {
799  return numEdgeTable[getPrimalEdgesMask(leaf)];
800  }
801 
802  int getNumEdges2(LeafNode *leaf)
803  {
804  return numEdgeTable[getPrimalEdgesMask2(leaf)];
805  }
806 
808  void setEdgeOffset(LeafNode *leaf, float pt, int count)
809  {
810  float *pts = leaf->edge_intersections;
811  pts[EDGE_FLOATS * count] = pt;
812  pts[EDGE_FLOATS * count + 1] = 0;
813  pts[EDGE_FLOATS * count + 2] = 0;
814  pts[EDGE_FLOATS * count + 3] = 0;
815  }
816 
818  void setEdgeOffsets(LeafNode *leaf, float pt[3], int len)
819  {
820  float *pts = leaf->edge_intersections;
821  for (int i = 0; i < len; i++) {
822  pts[i] = pt[i];
823  }
824  }
825 
827  float getEdgeOffset(const LeafNode *leaf, int count) const
828  {
829  return leaf->edge_intersections[4 * count];
830  }
831 
833  LeafNode *updateEdgeOffsets(LeafNode *leaf, int oldlen, int newlen, float offs[3])
834  {
835  /* First, create a new leaf node */
836  LeafNode *nleaf = createLeaf(newlen);
837  *nleaf = *leaf;
838 
839  /* Next, fill in the offsets */
840  setEdgeOffsets(nleaf, offs, newlen);
841 
842  /* Finally, delete the old leaf */
843  removeLeaf(oldlen, leaf);
844 
845  return nleaf;
846  }
847 
849  void setMinimizerIndex(LeafNode *leaf, int index)
850  {
851  leaf->minimizer_index = index;
852  }
853 
855  int getMinimizerIndex(LeafNode *leaf)
856  {
857  return leaf->minimizer_index;
858  }
859 
860  int getMinimizerIndex(LeafNode *leaf, int eind)
861  {
862  int add = manifold_table[getSignMask(leaf)].pairs[eind][0] - 1;
863  assert(add >= 0);
864  return leaf->minimizer_index + add;
865  }
866 
867  void getMinimizerIndices(LeafNode *leaf, int eind, int inds[2])
868  {
869  const int *add = manifold_table[getSignMask(leaf)].pairs[eind];
870  inds[0] = leaf->minimizer_index + add[0] - 1;
871  if (add[0] == add[1]) {
872  inds[1] = -1;
873  }
874  else {
875  inds[1] = leaf->minimizer_index + add[1] - 1;
876  }
877  }
878 
880  void setEdgeOffsetNormal(LeafNode *leaf, float pt, float a, float b, float c, int count)
881  {
882  float *pts = leaf->edge_intersections;
883  pts[4 * count] = pt;
884  pts[4 * count + 1] = a;
885  pts[4 * count + 2] = b;
886  pts[4 * count + 3] = c;
887  }
888 
889  float getEdgeOffsetNormal(LeafNode *leaf, int count, float &a, float &b, float &c)
890  {
891  float *pts = leaf->edge_intersections;
892  a = pts[4 * count + 1];
893  b = pts[4 * count + 2];
894  c = pts[4 * count + 3];
895  return pts[4 * count];
896  }
897 
899  void setEdgeOffsetsNormals(
900  LeafNode *leaf, const float pt[], const float a[], const float b[], const float c[], int len)
901  {
902  float *pts = leaf->edge_intersections;
903  for (int i = 0; i < len; i++) {
904  if (pt[i] > 1 || pt[i] < 0) {
905  printf("\noffset: %f\n", pt[i]);
906  }
907  pts[i * 4] = pt[i];
908  pts[i * 4 + 1] = a[i];
909  pts[i * 4 + 2] = b[i];
910  pts[i * 4 + 3] = c[i];
911  }
912  }
913 
915  void getEdgeIntersectionByIndex(
916  const LeafNode *leaf, int index, int st[3], int len, float pt[3], float nm[3]) const
917  {
918  int count = getEdgeCount(leaf, index);
919  const float *pts = leaf->edge_intersections;
920 
921  float off = pts[4 * count];
922 
923  pt[0] = (float)st[0];
924  pt[1] = (float)st[1];
925  pt[2] = (float)st[2];
926  pt[index] += (off * len);
927 
928  nm[0] = pts[4 * count + 1];
929  nm[1] = pts[4 * count + 2];
930  nm[2] = pts[4 * count + 3];
931  }
932 
933  float getEdgeOffsetNormalByIndex(LeafNode *leaf, int index, float nm[3])
934  {
935  int count = getEdgeCount(leaf, index);
936  float *pts = leaf->edge_intersections;
937 
938  float off = pts[4 * count];
939 
940  nm[0] = pts[4 * count + 1];
941  nm[1] = pts[4 * count + 2];
942  nm[2] = pts[4 * count + 3];
943 
944  return off;
945  }
946 
947  void fillEdgeIntersections(
948  const LeafNode *leaf, int st[3], int len, float pts[12][3], float norms[12][3]) const
949  {
950  int i;
951  // int stt[3] = {0, 0, 0};
952 
953  // The three primal edges are easy
954  int pmask[3] = {0, 4, 8};
955  for (i = 0; i < 3; i++) {
956  if (getEdgeParity(leaf, pmask[i])) {
957  // getEdgeIntersectionByIndex(leaf, i, stt, 1, pts[pmask[i]], norms[pmask[i]]);
958  getEdgeIntersectionByIndex(leaf, i, st, len, pts[pmask[i]], norms[pmask[i]]);
959  }
960  }
961 
962  // 3 face adjacent cubes
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]);
968  if (e1 || e2) {
969  int nst[3] = {st[0], st[1], st[2]};
970  nst[i] += len;
971  // int nstt[3] = {0, 0, 0};
972  // nstt[i] += 1;
973  const LeafNode *node = locateLeaf(nst);
974 
975  if (e1) {
976  // getEdgeIntersectionByIndex(node, femask[i][0], nstt, 1, pts[fmask[i][0]],
977  // norms[fmask[i][0]]);
978  getEdgeIntersectionByIndex(
979  node, femask[i][0], nst, len, pts[fmask[i][0]], norms[fmask[i][0]]);
980  }
981  if (e2) {
982  // getEdgeIntersectionByIndex(node, femask[i][1], nstt, 1, pts[fmask[i][1]],
983  // norms[fmask[i][1]]);
984  getEdgeIntersectionByIndex(
985  node, femask[i][1], nst, len, pts[fmask[i][1]], norms[fmask[i][1]]);
986  }
987  }
988  }
989 
990  // 3 edge adjacent cubes
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])) {
995  int nst[3] = {st[0] + len, st[1] + len, st[2] + len};
996  nst[i] -= len;
997  // int nstt[3] = {1, 1, 1};
998  // nstt[i] -= 1;
999  const LeafNode *node = locateLeaf(nst);
1000 
1001  // getEdgeIntersectionByIndex(node, eemask[i], nstt, 1, pts[emask[i]], norms[emask[i]]);
1002  getEdgeIntersectionByIndex(node, eemask[i], nst, len, pts[emask[i]], norms[emask[i]]);
1003  }
1004  }
1005  }
1006 
1007  void fillEdgeIntersections(const LeafNode *leaf,
1008  int st[3],
1009  int len,
1010  float pts[12][3],
1011  float norms[12][3],
1012  int parity[12]) const
1013  {
1014  int i;
1015  for (i = 0; i < 12; i++) {
1016  parity[i] = 0;
1017  }
1018  // int stt[3] = {0, 0, 0};
1019 
1020  // The three primal edges are easy
1021  int pmask[3] = {0, 4, 8};
1022  for (i = 0; i < 3; i++) {
1023  if (getStoredEdgesParity(leaf, i)) {
1024  // getEdgeIntersectionByIndex(leaf, i, stt, 1, pts[pmask[i]], norms[pmask[i]]);
1025  getEdgeIntersectionByIndex(leaf, i, st, len, pts[pmask[i]], norms[pmask[i]]);
1026  parity[pmask[i]] = 1;
1027  }
1028  }
1029 
1030  // 3 face adjacent cubes
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++) {
1034  {
1035  int nst[3] = {st[0], st[1], st[2]};
1036  nst[i] += len;
1037  // int nstt[3] = {0, 0, 0};
1038  // nstt[i] += 1;
1039  const LeafNode *node = locateLeafCheck(nst);
1040  if (node == NULL) {
1041  continue;
1042  }
1043 
1044  int e1 = getStoredEdgesParity(node, femask[i][0]);
1045  int e2 = getStoredEdgesParity(node, femask[i][1]);
1046 
1047  if (e1) {
1048  // getEdgeIntersectionByIndex(node, femask[i][0], nstt, 1, pts[fmask[i][0]],
1049  // norms[fmask[i][0]]);
1050  getEdgeIntersectionByIndex(
1051  node, femask[i][0], nst, len, pts[fmask[i][0]], norms[fmask[i][0]]);
1052  parity[fmask[i][0]] = 1;
1053  }
1054  if (e2) {
1055  // getEdgeIntersectionByIndex(node, femask[i][1], nstt, 1, pts[fmask[i][1]],
1056  // norms[fmask[i][1]]);
1057  getEdgeIntersectionByIndex(
1058  node, femask[i][1], nst, len, pts[fmask[i][1]], norms[fmask[i][1]]);
1059  parity[fmask[i][1]] = 1;
1060  }
1061  }
1062  }
1063 
1064  // 3 edge adjacent cubes
1065  int emask[3] = {3, 7, 11};
1066  int eemask[3] = {0, 1, 2};
1067  for (i = 0; i < 3; i++) {
1068  // if(getEdgeParity(leaf, emask[i]))
1069  {
1070  int nst[3] = {st[0] + len, st[1] + len, st[2] + len};
1071  nst[i] -= len;
1072  // int nstt[3] = {1, 1, 1};
1073  // nstt[i] -= 1;
1074  const LeafNode *node = locateLeafCheck(nst);
1075  if (node == NULL) {
1076  continue;
1077  }
1078 
1079  if (getStoredEdgesParity(node, eemask[i])) {
1080  // getEdgeIntersectionByIndex(node, eemask[i], nstt, 1, pts[emask[i]], norms[emask[i]]);
1081  getEdgeIntersectionByIndex(node, eemask[i], nst, len, pts[emask[i]], norms[emask[i]]);
1082  parity[emask[i]] = 1;
1083  }
1084  }
1085  }
1086  }
1087 
1088  void fillEdgeOffsetsNormals(
1089  LeafNode *leaf, int st[3], int len, float pts[12], float norms[12][3], int parity[12])
1090  {
1091  int i;
1092  for (i = 0; i < 12; i++) {
1093  parity[i] = 0;
1094  }
1095  // int stt[3] = {0, 0, 0};
1096 
1097  // The three primal edges are easy
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;
1103  }
1104  }
1105 
1106  // 3 face adjacent cubes
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++) {
1110  {
1111  int nst[3] = {st[0], st[1], st[2]};
1112  nst[i] += len;
1113  // int nstt[3] = {0, 0, 0};
1114  // nstt[i] += 1;
1115  LeafNode *node = locateLeafCheck(nst);
1116  if (node == NULL) {
1117  continue;
1118  }
1119 
1120  int e1 = getStoredEdgesParity(node, femask[i][0]);
1121  int e2 = getStoredEdgesParity(node, femask[i][1]);
1122 
1123  if (e1) {
1124  pts[fmask[i][0]] = getEdgeOffsetNormalByIndex(node, femask[i][0], norms[fmask[i][0]]);
1125  parity[fmask[i][0]] = 1;
1126  }
1127  if (e2) {
1128  pts[fmask[i][1]] = getEdgeOffsetNormalByIndex(node, femask[i][1], norms[fmask[i][1]]);
1129  parity[fmask[i][1]] = 1;
1130  }
1131  }
1132  }
1133 
1134  // 3 edge adjacent cubes
1135  int emask[3] = {3, 7, 11};
1136  int eemask[3] = {0, 1, 2};
1137  for (i = 0; i < 3; i++) {
1138  // if(getEdgeParity(leaf, emask[i]))
1139  {
1140  int nst[3] = {st[0] + len, st[1] + len, st[2] + len};
1141  nst[i] -= len;
1142  // int nstt[3] = {1, 1, 1};
1143  // nstt[i] -= 1;
1144  LeafNode *node = locateLeafCheck(nst);
1145  if (node == NULL) {
1146  continue;
1147  }
1148 
1149  if (getStoredEdgesParity(node, eemask[i])) {
1150  pts[emask[i]] = getEdgeOffsetNormalByIndex(node, eemask[i], norms[emask[i]]);
1151  parity[emask[i]] = 1;
1152  }
1153  }
1154  }
1155  }
1156 
1158  LeafNode *updateEdgeOffsetsNormals(
1159  LeafNode *leaf, int oldlen, int newlen, float offs[3], float a[3], float b[3], float c[3])
1160  {
1161  /* First, create a new leaf node */
1162  LeafNode *nleaf = createLeaf(newlen);
1163  *nleaf = *leaf;
1164 
1165  /* Next, fill in the offsets */
1166  setEdgeOffsetsNormals(nleaf, offs, a, b, c, newlen);
1167 
1168  /* Finally, delete the old leaf */
1169  removeLeaf(oldlen, leaf);
1170 
1171  return nleaf;
1172  }
1173 
1177  LeafNode *locateLeaf(int st[3])
1178  {
1179  Node *node = (Node *)root;
1180  for (int i = GRID_DIMENSION - 1; i > GRID_DIMENSION - maxDepth - 1; i--) {
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));
1183  }
1184 
1185  return &node->leaf;
1186  }
1187 
1188  const LeafNode *locateLeaf(int st[3]) const
1189  {
1190  const Node *node = root;
1191  for (int i = GRID_DIMENSION - 1; i > GRID_DIMENSION - maxDepth - 1; i--) {
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));
1194  }
1195 
1196  return &node->leaf;
1197  }
1198 
1199  LeafNode *locateLeaf(InternalNode *parent, int len, int st[3])
1200  {
1201  Node *node = (Node *)parent;
1202  int index;
1203  for (int i = len / 2; i >= mindimen; i >>= 1) {
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));
1206  }
1207 
1208  return &node->leaf;
1209  }
1210 
1211  LeafNode *locateLeafCheck(int st[3])
1212  {
1213  Node *node = (Node *)root;
1214  for (int i = GRID_DIMENSION - 1; i > GRID_DIMENSION - maxDepth - 1; i--) {
1215  int index = (((st[0] >> i) & 1) << 2) | (((st[1] >> i) & 1) << 1) | (((st[2] >> i) & 1));
1216  if (!node->internal.has_child(index)) {
1217  return NULL;
1218  }
1219  node = node->internal.get_child(node->internal.get_child_count(index));
1220  }
1221 
1222  return &node->leaf;
1223  }
1224 
1225  const LeafNode *locateLeafCheck(int st[3]) const
1226  {
1227  const Node *node = root;
1228  for (int i = GRID_DIMENSION - 1; i > GRID_DIMENSION - maxDepth - 1; i--) {
1229  int index = (((st[0] >> i) & 1) << 2) | (((st[1] >> i) & 1) << 1) | (((st[2] >> i) & 1));
1230  if (!node->internal.has_child(index)) {
1231  return NULL;
1232  }
1233  node = node->internal.get_child(node->internal.get_child_count(index));
1234  }
1235 
1236  return &node->leaf;
1237  }
1238 
1239  InternalNode *locateParent(int len, int st[3], int &count)
1240  {
1242  InternalNode *pre = NULL;
1243  int index = 0;
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));
1246  pre = node;
1247  node = &node->get_child(node->get_child_count(index))->internal;
1248  }
1249 
1250  count = pre->get_child_count(index);
1251  return pre;
1252  }
1253 
1254  InternalNode *locateParent(InternalNode *parent, int len, int st[3], int &count)
1255  {
1256  InternalNode *node = parent;
1257  InternalNode *pre = NULL;
1258  int index = 0;
1259  for (int i = len / 2; i >= mindimen; i >>= 1) {
1260  index = (((st[0] & i) ? 4 : 0) | ((st[1] & i) ? 2 : 0) | ((st[2] & i) ? 1 : 0));
1261  pre = node;
1262  node = &node->get_child(node->get_child_count(index))->internal;
1263  }
1264 
1265  count = pre->get_child_count(index);
1266  return pre;
1267  }
1268 
1269  /************ Operators for internal nodes ************/
1270 
1272  InternalNode *addChild(InternalNode *node, int index, Node *child, int aLeaf)
1273  {
1274  // Create new internal node
1275  int num = node->get_num_children();
1276  InternalNode *rnode = createInternal(num + 1);
1277 
1278  // Establish children
1279  int i;
1280  int count1 = 0, count2 = 0;
1281  for (i = 0; i < 8; i++) {
1282  if (i == index) {
1283  if (aLeaf) {
1284  rnode->set_leaf_child(i, count2, &child->leaf);
1285  }
1286  else {
1287  rnode->set_internal_child(i, count2, &child->internal);
1288  }
1289  count2++;
1290  }
1291  else if (node->has_child(i)) {
1292  if (node->is_child_leaf(i)) {
1293  rnode->set_leaf_child(i, count2, &node->get_child(count1)->leaf);
1294  }
1295  else {
1296  rnode->set_internal_child(i, count2, &node->get_child(count1)->internal);
1297  }
1298  count1++;
1299  count2++;
1300  }
1301  }
1302 
1303  removeInternal(num, node);
1304  return rnode;
1305  }
1306 
1308  InternalNode *createInternal(int length)
1309  {
1310  InternalNode *inode = (InternalNode *)alloc[length]->allocate();
1311  inode->has_child_bitfield = 0;
1312  inode->child_is_leaf_bitfield = 0;
1313  return inode;
1314  }
1315 
1316  LeafNode *createLeaf(int length)
1317  {
1318  assert(length <= 3);
1319 
1320  LeafNode *lnode = (LeafNode *)leafalloc[length]->allocate();
1321  lnode->edge_parity = 0;
1322  lnode->primary_edge_intersections = 0;
1323  lnode->signs = 0;
1324 
1325  return lnode;
1326  }
1327 
1328  void removeInternal(int num, InternalNode *node)
1329  {
1330  alloc[num]->deallocate(node);
1331  }
1332 
1333  void removeLeaf(int num, LeafNode *leaf)
1334  {
1335  assert(num >= 0 && num <= 3);
1336  leafalloc[num]->deallocate(leaf);
1337  }
1338 
1340  InternalNode *addLeafChild(InternalNode *par, int index, int count, LeafNode *leaf)
1341  {
1342  int num = par->get_num_children() + 1;
1343  InternalNode *npar = createInternal(num);
1344  *npar = *par;
1345 
1346  if (num == 1) {
1347  npar->set_leaf_child(index, 0, leaf);
1348  }
1349  else {
1350  int i;
1351  for (i = 0; i < count; i++) {
1352  npar->set_child(i, par->get_child(i));
1353  }
1354  npar->set_leaf_child(index, count, leaf);
1355  for (i = count + 1; i < num; i++) {
1356  npar->set_child(i, par->get_child(i - 1));
1357  }
1358  }
1359 
1360  removeInternal(num - 1, par);
1361  return npar;
1362  }
1363 
1364  InternalNode *addInternalChild(InternalNode *par, int index, int count, InternalNode *node)
1365  {
1366  int num = par->get_num_children() + 1;
1367  InternalNode *npar = createInternal(num);
1368  *npar = *par;
1369 
1370  if (num == 1) {
1371  npar->set_internal_child(index, 0, node);
1372  }
1373  else {
1374  int i;
1375  for (i = 0; i < count; i++) {
1376  npar->set_child(i, par->get_child(i));
1377  }
1378  npar->set_internal_child(index, count, node);
1379  for (i = count + 1; i < num; i++) {
1380  npar->set_child(i, par->get_child(i - 1));
1381  }
1382  }
1383 
1384  removeInternal(num - 1, par);
1385  return npar;
1386  }
1387 
1388 #ifdef WITH_CXX_GUARDEDALLOC
1389  MEM_CXX_CLASS_ALLOC_FUNCS("DUALCON:Octree")
1390 #endif
1391 };
1392 
1393 #endif /* __OCTREE_H__ */
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
#define GRID_DIMENSION
Definition: Projections.h:10
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
Definition: cubes.h:9
unsigned short flood_fill
Definition: octree.h:155
unsigned short primary_edge_intersections
Definition: octree.h:145
char signs
Definition: octree.h:151
float edge_intersections[0]
Definition: octree.h:157
unsigned short in_process
Definition: octree.h:148
unsigned short edge_parity
Definition: octree.h:144
int minimizer_index
Definition: octree.h:153
Definition: octree.h:206
int nodeCounts[9]
Definition: octree.h:237
int use_flood_fill
Definition: octree.h:247
int use_manifold
Definition: octree.h:250
int dimen
Definition: octree.h:224
float range
Definition: octree.h:232
int maxTrianglePerCell
Definition: octree.h:243
float thresh
Definition: octree.h:248
ModelReader * reader
Definition: octree.h:218
void * getOutputMesh()
Definition: octree.h:280
VirtualMemoryAllocator * alloc[9]
Definition: octree.h:211
int maxDepth
Definition: octree.h:228
int nodeSpace
Definition: octree.h:236
VirtualMemoryAllocator * leafalloc[4]
Definition: octree.h:212
~Octree()
Definition: octree.cpp:91
float origin[3]
Definition: octree.h:231
Cubes * cubes
Definition: octree.h:221
int nodeCount
Definition: octree.h:235
float hermite_num
Definition: octree.h:252
int minshift
Definition: octree.h:225
int actualQuads
Definition: octree.h:239
DualConMode mode
Definition: octree.h:254
void scanConvert()
Definition: octree.cpp:97
int outType
Definition: octree.h:244
int mindimen
Definition: octree.h:225
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)
Definition: octree.cpp:31
Node * root
Definition: octree.h:215
PathList * ringList
Definition: octree.h:241
int actualVerts
Definition: octree.h:239
virtual void deallocate(void *obj)=0
OperationNode * node
int len
Definition: draw_manager.c:108
DualConMode
Definition: dualcon.h:47
void(* DualConAddQuad)(void *output, const int vert_indices[4])
Definition: dualcon.h:41
void(* DualConAddVert)(void *output, const float co[3])
Definition: dualcon.h:39
DualConFlags
Definition: dualcon.h:43
void *(* DualConAllocOutput)(int totvert, int totquad)
Definition: dualcon.h:37
uint pos
int count
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]
static unsigned c
Definition: RandGen.cpp:83
static unsigned a[3]
Definition: RandGen.cpp:78
double sign(double arg)
Definition: utility.h:250
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]
Definition: octree.cpp:2865
const int edgeProcEdgeMask[3][2][5]
Definition: octree.cpp:2859
const int faceProcFaceMask[3][4][3]
Definition: octree.cpp:2850
const int cellProcFaceMask[12][3]
Definition: octree.cpp:2826
const int faceMap[6][4]
Definition: octree.cpp:2817
const int faceProcEdgeMask[3][4][6]
Definition: octree.cpp:2854
const int cellProcEdgeMask[6][5]
Definition: octree.cpp:2841
#define EDGE_FLOATS
Definition: octree.h:35
const int dirEdge[3][4]
Definition: octree.cpp:2875
const int dirCell[3][4][3]
Definition: octree.cpp:2871
const int edgemask[3]
Definition: octree.cpp:2815
unsigned char child_is_leaf_bitfield
Definition: octree.h:49
Node * get_child(int count)
Definition: octree.h:67
unsigned char has_child_bitfield
Definition: octree.h:47
static int childrenCountTable[256][8]
Definition: octree.h:43
void set_leaf_child(int index, int count, LeafNode *chd)
Definition: octree.h:124
int get_child_index(int count)
Definition: octree.h:88
static int numChildrenTable[256]
Definition: octree.h:42
int has_child(int index) const
Definition: octree.h:61
const int * get_child_counts() const
Definition: octree.h:92
static int childrenIndexTable[256][8]
Definition: octree.h:44
int get_num_children() const
Definition: octree.h:78
void fill_children(Node *children[8], int leaf[8])
Definition: octree.h:98
int is_child_leaf(int index) const
Definition: octree.h:55
void set_internal_child(int index, int count, InternalNode *chd)
Definition: octree.h:119
void set_child(int count, Node *chd)
Definition: octree.h:115
const Node * get_child(int count) const
Definition: octree.h:72
Node * children[0]
Definition: octree.h:52
int get_child_count(int index) const
Definition: octree.h:84
int pairs[12][2]
Definition: manifold_table.h:8
LeafNode leaf
Definition: octree.h:164
InternalNode internal
Definition: octree.h:163
PathElement * next
Definition: octree.h:188
int pos[3]
Definition: octree.h:185
int length
Definition: octree.h:197
PathElement * tail
Definition: octree.h:194
PathList * next
Definition: octree.h:200
PathElement * head
Definition: octree.h:193