Method Create

GTE/Mathematics/BVTree.h:103–139

The derived classes must compute the centroids of the primitives and store them in the member mCentroids before calling create. The input height specifies the desired height of the tree and must be no larger than 31. If std::numeric_limits ::max(), the the entire tree is built and the actual height is computed from centroids.size(). If larger than 31, the height is clamped to 31.

        // the entire tree is built and the actual height is computed from
        // centroids.size(). If larger than 31, the height is clamped to 31.
        void Create(size_t height)
        {
            LogAssert(mCentroids.size() > 0, "Invalid input.");

            if (height == std::numeric_limits<size_t>::max())
            {
                uint64_t minPowerOfTwo = BitHacks::RoundUpToPowerOfTwo(
                    static_cast<uint32_t>(mCentroids.size()));
                uint32_t logMinPowerOfTwo = BitHacks::Log2OfPowerOfTwo(
                    static_cast<uint32_t>(minPowerOfTwo));
                mHeight = static_cast<size_t>(logMinPowerOfTwo);
            }
            else
            {
                mHeight = std::min(height, static_cast<size_t>(31));
            }

            // The tree is built recursively. Preallocate the nodes because
            // the BuiltTree function declares references on the stack, so
            // we must guarantee that no reallocations occur in order to avoid
            // invalidating those references.
            size_t const numNodes = (static_cast<size_t>(1) << (mHeight + 1)) - 1;
            mNodes.resize(numNodes);

            // The array mPartition stores indices into mCentroids so that at
            // a node, the centroids represented by the node are the indices
            // [mPartition[node.minIndex], mPartition[node.maxIndex]].
            mPartition.resize(mCentroids.size());
            std::iota(mPartition.begin(), mPartition.end(), 0);

            // Build the tree recursively.
            size_t const depth = 0;
            size_t const nodeIndex = 0;
            size_t const i0 = 0;
            size_t const i1 = mCentroids.size() - 1;
            BuildTree(depth, nodeIndex, i0, i1);
        }

        // Member access.
        inline std::vector<Vector3<T>> const& GetCentroids() const