UT_FaceGradedOctreeLabels.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * NAME:        UT_FaceGradedOctreeLabels.h ( UT Library, C++)
 *
 * COMMENTS:
 *    This class creates a face-graded octree using a pyramid of UT_VoxelArrays.
 *    Each voxel for each level is assigned a label indicating if the voxel is
 *    actually active in the octree, an ancestor of an voxel or a descendant.
 *    This class also provides easy accessors to get elements in the pyramid
 *    to assist with walking through the tree.
 */

#ifndef __UT_FaceGradedOctreeLabels__
#define __UT_FaceGradedOctreeLabels__

#include "UT_API.h"
#include "UT_ParallelUtil.h"
#include "UT_ThreadedAlgorithm.h"
#include "UT_VoxelArray.h"

class UT_API UT_FaceGradedOctreeLabels
{
public:
    // Every cell in the octree will be either:
    // 1. INACTIVE --> a grid cell at the finest level that has no ACTIVE ancestors.
    //                      Only the finest level should be labelled INACTIVE
    //                      and it corresponds to grid cells that are outside
    //                      out of the region of interest.
    // 2. ACTIVE --> a grid cell that is equivalent to a leaf node in an
    //                  actual tree representation of the octree.
    // 3. UP --> a grid cell that is conceptually a descendant of a leaf node
    //           in an actual tree. UP cells are necessary in this pyramid
    //           structure to locate ACTIVE cells.
    // 4. DOWN --> a grid cell that is the ancestor of an ACTIVE cell. Conceptually
    //              equivalent to an internal node in a tree structure.
    enum OctreeCellLabels
    {
        INACTIVE_CELL,
        ACTIVE_CELL,
        UP_CELL,
        DOWN_CELL
    };

    // Derived methods might need to also labels faces between cells
    // in the octree. They will be labeled either:
    // 1. INACTIVE_FACE --> a face that is present in the octree but not in
    //                      the active domain
    // 2. ACTIVE_FACE --> a face that is present in the octree and within 
    //                      the active domain
    // 3. UNASSIGNED_FACE -> a face that only exists in the pyramid of regular
    //                      grids but isn't actually part of the underlying
    //                      octree structure.

    enum OctreeFaceLabels
    {
        INACTIVE_FACE,
        ACTIVE_FACE,
        UNASSIGNED_FACE
    };

    UT_FaceGradedOctreeLabels() {}

    // Refinement mask should be aligned with the reference grid and store > 0
    // values for inactive voxels, 0 values for active voxels and < 0 values for
    // voxels inside the octree (e.g. UP voxels).
    void
    initFromMask(const UT_VoxelArrayF &initializer_mask,
                    const int desired_levels);

    // Make sure the tree has one and only one active cell in a vertical column.
    bool unitTest() const;

    SYS_FORCE_INLINE
    UT_Vector3I
    getParentCell(const UT_Vector3I &cell) const
    {
        UT_Vector3I parent_cell(cell);
        parent_cell /= UT_Vector3I(2);
        return parent_cell;
    }

    // !WARNING! there is no check here to make sure the child is properly aligned with
    // the parent. This is the responsibility of the caller to make sure.
    SYS_FORCE_INLINE
    UT_Vector3I
    getParentFace(const UT_Vector3I &face) const
    {
        return getParentCell(face);
    }

    SYS_FORCE_INLINE
    UT_Vector3I
    getParentNode(const UT_Vector3I &node) const
    {
        return getParentCell(node);
    }

    SYS_FORCE_INLINE
    UT_Vector3I
    getChildCell(const UT_Vector3I &cell, const int child_index) const
    {
        UT_ASSERT(child_index < 8);

        UT_Vector3I child_cell(cell);
        child_cell *= 2;

        // Child index is a binary flag indicating a forward offset of 1
        // in each axis direction.
        for (int axis : {0,1,2})
        {
            if (child_index & (1 << axis))
                ++child_cell[axis];
        }

        return child_cell;
    }

    SYS_FORCE_INLINE
    UT_Vector3I
    getChildFace(const UT_Vector3I &face, const int axis, const int child_index) const
    {
        UT_ASSERT(axis < 3 && child_index < 4);

        UT_Vector3I child_face(face);
        child_face *= 2;

        if (child_index & 1)
            ++child_face[(axis + 1) % 3];
        if (child_index & 2)
            ++child_face[(axis + 2) % 3];

        return child_face;
    }

    SYS_FORCE_INLINE
    UT_Vector3I
    getChildEdge(const UT_Vector3I &edge, const int edge_axis, const int child_index) const
    {
        UT_ASSERT(child_index < 2);

        UT_Vector3I child_edge(edge);
        child_edge *= 2;
        if (child_index > 0)
            ++child_edge[edge_axis];

        return child_edge;
    }

    SYS_FORCE_INLINE
    UT_Vector3I
    getChildNode(const UT_Vector3I &node) const
    {
        UT_Vector3I child_node(node);
        child_node *= 2;
        return child_node;
    }

    // Get edges that lay inset in a face from a level lower
    SYS_FORCE_INLINE
    UT_Vector3I
    getChildEdgeInFace(const UT_Vector3I &face, const int face_axis,
                        const int edge_axis, const int child_index) const
    {
        UT_ASSERT(edge_axis != face_axis &&
                face_axis < 3 &&
                edge_axis < 3 &&
                child_index < 2);

        UT_Vector3I child_edge(face);
        child_edge *= 2;

        if (child_index == 1)
            ++child_edge[edge_axis];

        int offsetAxis = 3 - face_axis - edge_axis;
        ++child_edge[offsetAxis];

        return child_edge;
    }

    SYS_FORCE_INLINE
    const UT_VoxelArray<int> &
    getGridLabels(const int level) const
    {
        UT_ASSERT(level < m_octree_labels.size());
        return m_octree_labels[level];
    }

    SYS_FORCE_INLINE
    UT_Vector3I
    getVoxelRes(const int level) const
    {
        UT_ASSERT(level < m_octree_labels.size());

        return UT_Vector3I(m_octree_labels[level].getXRes(), 
                            m_octree_labels[level].getYRes(),
                            m_octree_labels[level].getZRes());
    }

    SYS_FORCE_INLINE
    int
    getOctreeLevels() const { return m_octree_levels; }

    SYS_FORCE_INLINE
    OctreeCellLabels
    getCellLabel(const UT_Vector3I &cell, const int level) const
    {
        UT_ASSERT(level >= 0 && level < m_octree_levels);
        return OctreeCellLabels(m_octree_labels[level](cell));
    }

    SYS_FORCE_INLINE
    bool
    isCellActive(const UT_Vector3I &cell, const int level) const
    {
        return getCellLabel(cell, level) == ACTIVE_CELL;
    }

private:

    SYS_FORCE_INLINE
    UT_Vector3I
    cellToCellMap(UT_Vector3I cell, const int axis, const int direction) const
    {
        UT_ASSERT(axis >= 0 && axis < 3);
        if (direction == 0)
            --cell[axis];
        else
        {
            ++cell[axis];
            UT_ASSERT(direction == 1);
        }

        return cell;
    }

    //
    // Unit test helpers
    //

    THREADED_METHOD1_CONST(UT_FaceGradedOctreeLabels,
                            m_octree_labels[0].numTiles() > 100,
                            activeCountUnitTest,
                            bool &, passed)

    void activeCountUnitTestPartial(bool &passed, const UT_JobInfo &info) const;

    THREADED_METHOD2_CONST(UT_FaceGradedOctreeLabels,
                            m_octree_labels[level].numTiles() > 100,
                            upAdjacentUnitTest,
                            bool &, passed,
                            const int, level)

    void upAdjacentUnitTestPartial(bool &passed, const int level,
                                   const UT_JobInfo &info) const;

    THREADED_METHOD2_CONST(UT_FaceGradedOctreeLabels,
                           m_octree_labels[level].numTiles() > 100,
                           activeUnitTest, bool &, passed, const int, level)

    void activeUnitTestPartial(bool &passed, const int level,
                               const UT_JobInfo &info) const;

    UT_Array<UT_Vector4I> getFaceAdjacentCells(const UT_Vector3I &cell,
                                                const int axis,
                                                const int direction,
                                                const int level) const;

    //
    // Build octree
    //

    THREADED_METHOD1(UT_FaceGradedOctreeLabels,
                        m_octree_labels[0].numTiles() > 100,
                        setBaseGridLabels,
                        const UT_VoxelArrayF &, initializer_mask)

    void setBaseGridLabelsPartial(const UT_VoxelArrayF &initializer_mask, const UT_JobInfo &info);

    THREADED_METHOD3(UT_FaceGradedOctreeLabels,
                        m_octree_labels[level].numTiles() > 100,
                        setActiveCellsAndParentList,
                        UT_Array<UT_Array<UT_Vector3I>> &, parallel_down_parent_list,
                        UT_Array<bool> &, is_tile_occupied_list,
                        const int, level)

    void setActiveCellsAndParentListPartial(UT_Array<UT_Array<UT_Vector3I>> &parallel_down_parent_list,
                                            UT_Array<bool> &is_tile_occupied_list,
                                            const int level,
                                            const UT_JobInfo &info);

    THREADED_METHOD2(UT_FaceGradedOctreeLabels,
                        is_tile_occupied_list.entries() > 100,
                        uncompressParentTiles,
                        const UT_Array<bool> &, is_tile_occupied_list,
                        const int, level)

    void uncompressParentTilesPartial(const UT_Array<bool> &is_tile_occupied_list,
                                        const int level,
                                        const UT_JobInfo &info);

    THREADED_METHOD3(UT_FaceGradedOctreeLabels,
                        new_parent_list.entries() > 100,
                        setParentCellLabel,
                        const UT_Array<UT_Vector3I> &, new_parent_list,
                        const int, level,
                        const OctreeCellLabels, label)

    void setParentCellLabelPartial(const UT_Array<UT_Vector3I> &new_parent_list,
                                    const int level,
                                    const OctreeCellLabels label,
                                    const UT_JobInfo &info);

    THREADED_METHOD4(UT_FaceGradedOctreeLabels, m_octree_labels[level].numTiles() > 100,
                        setFaceGrading,
                        UT_Array<UT_Array<UT_Vector3I>> &, parallel_down_parent_list,
                        UT_Array<UT_Array<UT_Vector3I>> &, parallel_parent_active_list,
                        UT_Array<bool> &, is_tile_occupied_list,
                        const int, level)

    void setFaceGradingPartial(UT_Array<UT_Array<UT_Vector3I>> &parallel_down_parent_list,
                                UT_Array<UT_Array<UT_Vector3I>> &parallel_parent_active_list,
                                UT_Array<bool> &is_tile_occupied_list,
                                const int level,
                                const UT_JobInfo &info);

    THREADED_METHOD3(UT_FaceGradedOctreeLabels, m_octree_labels[level].numTiles() > 100,
                        setParentsUp,
                        UT_Array<UT_Array<UT_Vector3I>> &, parallel_new_parent_list,
                        UT_Array<bool> &, is_tile_occupied_list,
                        const int, level)

    void setParentsUpPartial(UT_Array<UT_Array<UT_Vector3I>> &parallel_new_parent_list,
                                UT_Array<bool> &is_tile_occupied_list,
                                const int level,
                                const UT_JobInfo &info);

    THREADED_METHOD1(UT_FaceGradedOctreeLabels,
                        m_octree_labels[level].numTiles() > 100,
                        setTopLevel,
                        const int, level);

    void setTopLevelPartial(const int level, const UT_JobInfo &info);

    THREADED_METHOD2_CONST(UT_FaceGradedOctreeLabels,
                            m_octree_labels[level].numTiles() > 100,
                            checkActiveCellAtLevel,
                            bool &, has_active_cell,
                            const int, level);

    void checkActiveCellAtLevelPartial(bool &has_active_cell,
                                        const int level,
                                        const UT_JobInfo &info) const;

    // Markers to label active cells, if the cell is "above"
    // or "below" the leaf (aka active cell).
    UT_Array<UT_VoxelArray<int>> m_octree_labels;
    UT_Vector3I m_base_voxel_res;
    int m_octree_levels;
};

#endif