HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_FaceGradedOctreeLabels.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_FaceGradedOctreeLabels.h ( UT Library, C++)
7  *
8  * COMMENTS:
9  * This class creates a face-graded octree using a pyramid of UT_VoxelArrays.
10  * Each voxel for each level is assigned a label indicating if the voxel is
11  * actually active in the octree, an ancestor of an voxel or a descendant.
12  * This class also provides easy accessors to get elements in the pyramid
13  * to assist with walking through the tree.
14  */
15 
16 #ifndef __UT_FaceGradedOctreeLabels__
17 #define __UT_FaceGradedOctreeLabels__
18 
19 #include "UT_API.h"
20 #include "UT_ParallelUtil.h"
21 #include "UT_ThreadedAlgorithm.h"
22 #include "UT_VoxelArray.h"
23 
25 {
26 public:
27  // Every cell in the octree will be either:
28  // 1. INACTIVE --> a grid cell at the finest level that has no ACTIVE ancestors.
29  // Only the finest level should be labelled INACTIVE
30  // and it corresponds to grid cells that are outside
31  // out of the region of interest.
32  // 2. ACTIVE --> a grid cell that is equivalent to a leaf node in an
33  // actual tree representation of the octree.
34  // 3. UP --> a grid cell that is conceptually a descendant of a leaf node
35  // in an actual tree. UP cells are necessary in this pyramid
36  // structure to locate ACTIVE cells.
37  // 4. DOWN --> a grid cell that is the ancestor of an ACTIVE cell. Conceptually
38  // equivalent to an internal node in a tree structure.
40  {
44  DOWN_CELL
45  };
46 
47  // Derived methods might need to also labels faces between cells
48  // in the octree. They will be labeled either:
49  // 1. INACTIVE_FACE --> a face that is present in the octree but not in
50  // the active domain
51  // 2. ACTIVE_FACE --> a face that is present in the octree and within
52  // the active domain
53  // 3. UNASSIGNED_FACE -> a face that only exists in the pyramid of regular
54  // grids but isn't actually part of the underlying
55  // octree structure.
56 
58  {
61  UNASSIGNED_FACE
62  };
63 
65 
66  // Refinement mask should be aligned with the reference grid and store > 0
67  // values for inactive voxels, 0 values for active voxels and < 0 values for
68  // voxels inside the octree (e.g. UP voxels).
69  void
70  initFromMask(const UT_VoxelArrayF &initializer_mask,
71  const int desired_levels);
72 
73  // Make sure the tree has one and only one active cell in a vertical column.
74  bool unitTest() const;
75 
78  getParentCell(const UT_Vector3I &cell) const
79  {
80  UT_Vector3I parent_cell(cell);
81  parent_cell /= UT_Vector3I(2);
82  return parent_cell;
83  }
84 
85  // !WARNING! there is no check here to make sure the child is properly aligned with
86  // the parent. This is the responsibility of the caller to make sure.
89  getParentFace(const UT_Vector3I &face) const
90  {
91  return getParentCell(face);
92  }
93 
96  getParentNode(const UT_Vector3I &node) const
97  {
98  return getParentCell(node);
99  }
100 
103  getChildCell(const UT_Vector3I &cell, const int child_index) const
104  {
105  UT_ASSERT(child_index < 8);
106 
107  UT_Vector3I child_cell(cell);
108  child_cell *= 2;
109 
110  // Child index is a binary flag indicating a forward offset of 1
111  // in each axis direction.
112  for (int axis : {0,1,2})
113  {
114  if (child_index & (1 << axis))
115  ++child_cell[axis];
116  }
117 
118  return child_cell;
119  }
120 
123  getChildFace(const UT_Vector3I &face, const int axis, const int child_index) const
124  {
125  UT_ASSERT(axis < 3 && child_index < 4);
126 
127  UT_Vector3I child_face(face);
128  child_face *= 2;
129 
130  if (child_index & 1)
131  ++child_face[(axis + 1) % 3];
132  if (child_index & 2)
133  ++child_face[(axis + 2) % 3];
134 
135  return child_face;
136  }
137 
140  getChildEdge(const UT_Vector3I &edge, const int edge_axis, const int child_index) const
141  {
142  UT_ASSERT(child_index < 2);
143 
144  UT_Vector3I child_edge(edge);
145  child_edge *= 2;
146  if (child_index > 0)
147  ++child_edge[edge_axis];
148 
149  return child_edge;
150  }
151 
154  getChildNode(const UT_Vector3I &node) const
155  {
156  UT_Vector3I child_node(node);
157  child_node *= 2;
158  return child_node;
159  }
160 
161  // Get edges that lay inset in a face from a level lower
164  getChildEdgeInFace(const UT_Vector3I &face, const int face_axis,
165  const int edge_axis, const int child_index) const
166  {
167  UT_ASSERT(edge_axis != face_axis &&
168  face_axis < 3 &&
169  edge_axis < 3 &&
170  child_index < 2);
171 
172  UT_Vector3I child_edge(face);
173  child_edge *= 2;
174 
175  if (child_index == 1)
176  ++child_edge[edge_axis];
177 
178  int offsetAxis = 3 - face_axis - edge_axis;
179  ++child_edge[offsetAxis];
180 
181  return child_edge;
182  }
183 
185  const UT_VoxelArray<int> &
186  getGridLabels(const int level) const
187  {
188  UT_ASSERT(level < m_octree_labels.size());
189  return m_octree_labels[level];
190  }
191 
194  getVoxelRes(const int level) const
195  {
196  UT_ASSERT(level < m_octree_labels.size());
197 
198  return UT_Vector3I(m_octree_labels[level].getXRes(),
199  m_octree_labels[level].getYRes(),
200  m_octree_labels[level].getZRes());
201  }
202 
204  int
205  getOctreeLevels() const { return m_octree_levels; }
206 
208  OctreeCellLabels
209  getCellLabel(const UT_Vector3I &cell, const int level) const
210  {
211  UT_ASSERT(level >= 0 && level < m_octree_levels);
212  return OctreeCellLabels(m_octree_labels[level](cell));
213  }
214 
216  bool
217  isCellActive(const UT_Vector3I &cell, const int level) const
218  {
219  return getCellLabel(cell, level) == ACTIVE_CELL;
220  }
221 
222 private:
223 
226  cellToCellMap(UT_Vector3I cell, const int axis, const int direction) const
227  {
228  UT_ASSERT(axis >= 0 && axis < 3);
229  if (direction == 0)
230  --cell[axis];
231  else
232  {
233  ++cell[axis];
234  UT_ASSERT(direction == 1);
235  }
236 
237  return cell;
238  }
239 
240  //
241  // Unit test helpers
242  //
243 
245  m_octree_labels[0].numTiles() > 100,
246  activeCountUnitTest,
247  bool &, passed)
248 
249  void activeCountUnitTestPartial(bool &passed, const UT_JobInfo &info) const;
250 
252  m_octree_labels[level].numTiles() > 100,
253  upAdjacentUnitTest,
254  bool &, passed,
255  const int, level)
256 
257  void upAdjacentUnitTestPartial(bool &passed, const int level,
258  const UT_JobInfo &info) const;
259 
260  THREADED_METHOD2_CONST(UT_FaceGradedOctreeLabels,
261  m_octree_labels[level].numTiles() > 100,
262  activeUnitTest, bool &, passed, const int, level)
263 
264  void activeUnitTestPartial(bool &passed, const int level,
265  const UT_JobInfo &info) const;
266 
267  UT_Array<UT_Vector4I> getFaceAdjacentCells(const UT_Vector3I &cell,
268  const int axis,
269  const int direction,
270  const int level) const;
271 
272  //
273  // Build octree
274  //
275 
276  THREADED_METHOD1(UT_FaceGradedOctreeLabels,
277  m_octree_labels[0].numTiles() > 100,
278  setBaseGridLabels,
279  const UT_VoxelArrayF &, initializer_mask)
280 
281  void setBaseGridLabelsPartial(const UT_VoxelArrayF &initializer_mask, const UT_JobInfo &info);
282 
283  THREADED_METHOD3(UT_FaceGradedOctreeLabels,
284  m_octree_labels[level].numTiles() > 100,
285  setActiveCellsAndParentList,
286  UT_Array<UT_Array<UT_Vector3I>> &, parallel_down_parent_list,
287  UT_Array<bool> &, is_tile_occupied_list,
288  const int, level)
289 
290  void setActiveCellsAndParentListPartial(UT_Array<UT_Array<UT_Vector3I>> &parallel_down_parent_list,
291  UT_Array<bool> &is_tile_occupied_list,
292  const int level,
293  const UT_JobInfo &info);
294 
295  THREADED_METHOD2(UT_FaceGradedOctreeLabels,
296  is_tile_occupied_list.entries() > 100,
297  uncompressParentTiles,
298  const UT_Array<bool> &, is_tile_occupied_list,
299  const int, level)
300 
301  void uncompressParentTilesPartial(const UT_Array<bool> &is_tile_occupied_list,
302  const int level,
303  const UT_JobInfo &info);
304 
305  THREADED_METHOD3(UT_FaceGradedOctreeLabels,
306  new_parent_list.entries() > 100,
307  setParentCellLabel,
308  const UT_Array<UT_Vector3I> &, new_parent_list,
309  const int, level,
310  const OctreeCellLabels, label)
311 
312  void setParentCellLabelPartial(const UT_Array<UT_Vector3I> &new_parent_list,
313  const int level,
314  const OctreeCellLabels label,
315  const UT_JobInfo &info);
316 
317  THREADED_METHOD4(UT_FaceGradedOctreeLabels, m_octree_labels[level].numTiles() > 100,
318  setFaceGrading,
319  UT_Array<UT_Array<UT_Vector3I>> &, parallel_down_parent_list,
320  UT_Array<UT_Array<UT_Vector3I>> &, parallel_parent_active_list,
321  UT_Array<bool> &, is_tile_occupied_list,
322  const int, level)
323 
324  void setFaceGradingPartial(UT_Array<UT_Array<UT_Vector3I>> &parallel_down_parent_list,
325  UT_Array<UT_Array<UT_Vector3I>> &parallel_parent_active_list,
326  UT_Array<bool> &is_tile_occupied_list,
327  const int level,
328  const UT_JobInfo &info);
329 
330  THREADED_METHOD3(UT_FaceGradedOctreeLabels, m_octree_labels[level].numTiles() > 100,
331  setParentsUp,
332  UT_Array<UT_Array<UT_Vector3I>> &, parallel_new_parent_list,
333  UT_Array<bool> &, is_tile_occupied_list,
334  const int, level)
335 
336  void setParentsUpPartial(UT_Array<UT_Array<UT_Vector3I>> &parallel_new_parent_list,
337  UT_Array<bool> &is_tile_occupied_list,
338  const int level,
339  const UT_JobInfo &info);
340 
341  THREADED_METHOD1(UT_FaceGradedOctreeLabels,
342  m_octree_labels[level].numTiles() > 100,
343  setTopLevel,
344  const int, level);
345 
346  void setTopLevelPartial(const int level, const UT_JobInfo &info);
347 
348  THREADED_METHOD2_CONST(UT_FaceGradedOctreeLabels,
349  m_octree_labels[level].numTiles() > 100,
350  checkActiveCellAtLevel,
351  bool &, has_active_cell,
352  const int, level);
353 
354  void checkActiveCellAtLevelPartial(bool &has_active_cell,
355  const int level,
356  const UT_JobInfo &info) const;
357 
358  // Markers to label active cells, if the cell is "above"
359  // or "below" the leaf (aka active cell).
360  UT_Array<UT_VoxelArray<int>> m_octree_labels;
361  UT_Vector3I m_base_voxel_res;
362  int m_octree_levels;
363 };
364 
365 #endif
SYS_FORCE_INLINE UT_Vector3I getChildCell(const UT_Vector3I &cell, const int child_index) const
GLuint GLsizei const GLchar * label
Definition: glcorearb.h:2545
SYS_FORCE_INLINE UT_Vector3I getParentFace(const UT_Vector3I &face) const
SYS_FORCE_INLINE UT_Vector3I getChildNode(const UT_Vector3I &node) const
void
Definition: png.h:1083
SYS_FORCE_INLINE UT_Vector3I getChildEdge(const UT_Vector3I &edge, const int edge_axis, const int child_index) const
#define THREADED_METHOD1(CLASSNAME, DOMULTI, METHOD, PARMTYPE1, PARMNAME1)
IMF_EXPORT IMATH_NAMESPACE::V3f direction(const IMATH_NAMESPACE::Box2i &dataWindow, const IMATH_NAMESPACE::V2f &pixelPosition)
GLint level
Definition: glcorearb.h:108
SYS_FORCE_INLINE UT_Vector3I getParentNode(const UT_Vector3I &node) const
#define UT_API
Definition: UT_API.h:14
UT_Vector3T< int64 > UT_Vector3I
#define THREADED_METHOD3(CLASSNAME, DOMULTI, METHOD, PARMTYPE1, PARMNAME1, PARMTYPE2, PARMNAME2, PARMTYPE3, PARMNAME3)
SYS_FORCE_INLINE int getOctreeLevels() const
SYS_FORCE_INLINE UT_Vector3I getChildEdgeInFace(const UT_Vector3I &face, const int face_axis, const int edge_axis, const int child_index) const
SYS_FORCE_INLINE UT_Vector3I getParentCell(const UT_Vector3I &cell) const
SYS_FORCE_INLINE UT_Vector3I cellToCellMap(const UT_Vector3I &cell, const int axis, const int direction)
SYS_FORCE_INLINE UT_Vector3I getChildFace(const UT_Vector3I &face, const int axis, const int child_index) const
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
#define THREADED_METHOD2(CLASSNAME, DOMULTI, METHOD, PARMTYPE1, PARMNAME1, PARMTYPE2, PARMNAME2)
#define THREADED_METHOD4(CLASSNAME, DOMULTI, METHOD, PARMTYPE1, PARMNAME1, PARMTYPE2, PARMNAME2, PARMTYPE3, PARMNAME3, PARMTYPE4, PARMNAME4)
#define THREADED_METHOD2_CONST(CLASSNAME, DOMULTI, METHOD, PARMTYPE1, PARMNAME1, PARMTYPE2, PARMNAME2)
#define THREADED_METHOD1_CONST(CLASSNAME, DOMULTI, METHOD, PARMTYPE1, PARMNAME1)
SYS_FORCE_INLINE bool isCellActive(const UT_Vector3I &cell, const int level) const
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:156
SYS_FORCE_INLINE OctreeCellLabels getCellLabel(const UT_Vector3I &cell, const int level) const
SYS_FORCE_INLINE const UT_VoxelArray< int > & getGridLabels(const int level) const
SYS_FORCE_INLINE UT_Vector3I getVoxelRes(const int level) const