diff options
Diffstat (limited to 'intern/opensubdiv/internal/evaluator/patch_map.h')
| -rw-r--r-- | intern/opensubdiv/internal/evaluator/patch_map.h | 264 |
1 files changed, 264 insertions, 0 deletions
diff --git a/intern/opensubdiv/internal/evaluator/patch_map.h b/intern/opensubdiv/internal/evaluator/patch_map.h new file mode 100644 index 00000000000..af804d6ca71 --- /dev/null +++ b/intern/opensubdiv/internal/evaluator/patch_map.h @@ -0,0 +1,264 @@ +// Original code copyright 2013 Pixar. +// +// Licensed under the Apache License, Version 2.0 (the "Apache License") +// with the following modification; you may not use this file except in +// compliance with the Apache License and the following modification to it: +// Section 6. Trademarks. is deleted and replaced with: +// +// 6. Trademarks. This License does not grant permission to use the trade +// names, trademarks, service marks, or product names of the Licensor +// and its affiliates, except as required to comply with Section 4(c) of +// the License and to reproduce the content of the NOTICE file. +// +// You may obtain a copy of the Apache License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the Apache License with the above modification is +// distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the Apache License for the specific +// language governing permissions and limitations under the Apache License. +// +// Modifications copyright 2021 Blender Foundation. All rights reserved. + +#ifndef OPENSUBDIV_PATCH_MAP_H_ +#define OPENSUBDIV_PATCH_MAP_H_ + +#include <opensubdiv/far/patchTable.h> + +namespace blender { +namespace opensubdiv { + +/// \brief An quadtree-based map connecting coarse faces to their sub-patches +/// +/// PatchTable::PatchArrays contain lists of patches that represent the limit +/// surface of a mesh, sorted by their topological type. These arrays break the +/// connection between coarse faces and their sub-patches. +/// +/// The PatchMap provides a quad-tree based lookup structure that, given a singular +/// parametric location, can efficiently return a handle to the sub-patch that +/// contains this location. +/// +class PatchMap { + public: + // Quadtree node with 4 children, tree is just a vector of nodes + struct QuadNode { + QuadNode() + { + std::memset(this, 0, sizeof(QuadNode)); + } + + struct Child { + unsigned int isSet : 1; // true if the child has been set + unsigned int isLeaf : 1; // true if the child is a QuadNode + unsigned int index : 30; // child index (either QuadNode or Handle) + }; + + // sets all the children to point to the patch of given index + void SetChildren(int index); + + // sets the child in "quadrant" to point to the node or patch of the given index + void SetChild(int quadrant, int index, bool isLeaf); + + Child children[4]; + }; + + typedef OpenSubdiv::Far::PatchTable::PatchHandle Handle; + + /// \brief Constructor + /// + /// @param patchTable A valid PatchTable + /// + PatchMap(OpenSubdiv::Far::PatchTable const &patchTable); + + /// \brief Returns a handle to the sub-patch of the face at the given (u,v). + /// Note that the patch face ID corresponds to potentially quadrangulated + /// face indices and not the base face indices (see Far::PtexIndices for more + /// details). + /// + /// @param patchFaceId The index of the patch (Ptex) face + /// + /// @param u Local u parameter + /// + /// @param v Local v parameter + /// + /// @return A patch handle or 0 if the face is not supported (index + /// out of bounds) or is tagged as a hole + /// + Handle const *FindPatch(int patchFaceId, double u, double v) const; + + int getMinPatchFace() const + { + return _minPatchFace; + } + + int getMaxPatchFace() const + { + return _maxPatchFace; + } + + int getMaxDepth() const + { + return _maxDepth; + } + + bool getPatchesAreTriangular() const + { + return _patchesAreTriangular; + } + + const std::vector<Handle> &getHandles() + { + return _handles; + } + + const std::vector<QuadNode> &nodes() + { + return _quadtree; + } + + private: + void initializeHandles(OpenSubdiv::Far::PatchTable const &patchTable); + void initializeQuadtree(OpenSubdiv::Far::PatchTable const &patchTable); + + typedef std::vector<QuadNode> QuadTree; + + // Internal methods supporting quadtree construction and queries + void assignRootNode(QuadNode *node, int index); + QuadNode *assignLeafOrChildNode(QuadNode *node, bool isLeaf, int quad, int index); + + template<class T> static int transformUVToQuadQuadrant(T const &median, T &u, T &v); + template<class T> + static int transformUVToTriQuadrant(T const &median, T &u, T &v, bool &rotated); + + private: + bool _patchesAreTriangular; // tri and quad assembly and search requirements differ + + int _minPatchFace; // minimum patch face index supported by the map + int _maxPatchFace; // maximum patch face index supported by the map + int _maxDepth; // maximum depth of a patch in the tree + + std::vector<Handle> _handles; // all the patches in the PatchTable + std::vector<QuadNode> _quadtree; // quadtree nodes +}; + +// +// Given a median value for both U and V, these methods transform a (u,v) pair +// into the quadrant that contains them and returns the quadrant index. +// +// Quadrant indexing for tri and quad patches -- consistent with PatchParam's +// usage of UV bits: +// +// (0,1) o-----o-----o (1,1) (0,1) o (1,0) o-----o-----o (0,0) +// | | | |\ \ 1 |\ 0 | +// | 2 | 3 | | \ \ | \ | +// | | | | 2 \ \| 3 \| +// o-----o-----o o-----o o-----o +// | | | |\ 3 |\ \ 2 | +// | 0 | 1 | | \ | \ \ | +// | | | | 0 \| 1 \ \| +// (0,0) o-----o-----o (1,0) (0,0) o-----o-----o (1,0) o (0,1) +// +// The triangular case also takes and returns/affects the rotation of the +// quadrant being searched and identified (quadrant 3 imparts a rotation). +// +template<class T> inline int PatchMap::transformUVToQuadQuadrant(T const &median, T &u, T &v) +{ + + int uHalf = (u >= median); + if (uHalf) + u -= median; + + int vHalf = (v >= median); + if (vHalf) + v -= median; + + return (vHalf << 1) | uHalf; +} + +template<class T> +int inline PatchMap::transformUVToTriQuadrant(T const &median, T &u, T &v, bool &rotated) +{ + + if (!rotated) { + if (u >= median) { + u -= median; + return 1; + } + if (v >= median) { + v -= median; + return 2; + } + if ((u + v) >= median) { + rotated = true; + return 3; + } + return 0; + } + else { + if (u < median) { + v -= median; + return 1; + } + if (v < median) { + u -= median; + return 2; + } + u -= median; + v -= median; + if ((u + v) < median) { + rotated = false; + return 3; + } + return 0; + } +} + +/// Returns a handle to the sub-patch of the face at the given (u,v). +inline PatchMap::Handle const *PatchMap::FindPatch(int faceid, double u, double v) const +{ + + // + // Reject patch faces not supported by this map, or those corresponding + // to holes or otherwise unassigned (the root node for a patch will + // have all or no quadrants set): + // + if ((faceid < _minPatchFace) || (faceid > _maxPatchFace)) + return 0; + + QuadNode const *node = &_quadtree[faceid - _minPatchFace]; + + if (!node->children[0].isSet) + return 0; + + // + // Search the tree for the sub-patch containing the given (u,v) + // + assert((u >= 0.0) && (u <= 1.0) && (v >= 0.0) && (v <= 1.0)); + + double median = 0.5; + bool triRotated = false; + + for (int depth = 0; depth <= _maxDepth; ++depth, median *= 0.5) { + + int quadrant = _patchesAreTriangular ? transformUVToTriQuadrant(median, u, v, triRotated) : + transformUVToQuadQuadrant(median, u, v); + + // holes should have been rejected at the root node of the face + assert(node->children[quadrant].isSet); + + if (node->children[quadrant].isLeaf) { + return &_handles[node->children[quadrant].index]; + } + else { + node = &_quadtree[node->children[quadrant].index]; + } + } + assert(0); + return 0; +} +} // namespace opensubdiv +} // namespace blender + +#endif // OPENSUBDIV_PATCH_MAP_H_ |