aabsptree.h

WOW 服务模拟端 支持2.4.3版本 来自开源的ASCENT 自己REPACK

                            debugAssert(b.low()[axis] >= lo[axis]);
                            debugAssert(b.high()[axis] <= hi[axis]);
                        }
                    }

                    if (child[0] || child[1]) {
                        debugAssert(lo[splitAxis] < splitLocation);
                        debugAssert(hi[splitAxis] > splitLocation);
                    }

                    Vector3 newLo = lo;
                    newLo[splitAxis] = splitLocation;
                    Vector3 newHi = hi;
                    newHi[splitAxis] = splitLocation;

                    if (child[0] != NULL) {
                        child[0]->verifyNode(lo, newHi);
                    }

                    if (child[1] != NULL) {
                        child[1]->verifyNode(newLo, hi);
                    }
                }

#if 0
                /**
                Stores the locations of the splitting planes (the structure but not the content)
                so that the tree can be quickly rebuilt from a previous configuration without 
                calling balance.
                */
                static void serializeStructure(const Node* n, BinaryOutput& bo) {
                    if (n == NULL) {
                        bo.writeUInt8(0);
                    } else {
                        bo.writeUInt8(1);
                        n->splitBounds.serialize(bo);
                        serialize(n->splitAxis, bo);
                        bo.writeFloat32(n->splitLocation);
                        for (int c = 0; c < 2; ++c) {
                            serializeStructure(n->child[c], bo);
                        }
                    }
                }

                /** Clears the member table */
                static Node* deserializeStructure(BinaryInput& bi) {
                    if (bi.readUInt8() == 0) {
                        return NULL;
                    } else {
                        Node* n = new Node();
                        n->splitBounds.deserialize(bi);
                        deserialize(n->splitAxis, bi);
                        n->splitLocation = bi.readFloat32();
                        for (int c = 0; c < 2; ++c) {
                            n->child[c] = deserializeStructure(bi);
                        }
                    }
                }
#endif

                /** Returns the deepest node that completely contains bounds. */
                Node* findDeepestContainingNode(const AABox& bounds) {

                    // See which side of the splitting plane the bounds are on
                    if (bounds.high()[splitAxis] < splitLocation) {
                        // Bounds are on the low side.  Recurse into the child
                        // if it exists.
                        if (child[0] != NULL) {
                            return child[0]->findDeepestContainingNode(bounds);
                        }
                    } else if (bounds.low()[splitAxis] > splitLocation) {
                        // Bounds are on the high side, recurse into the child
                        // if it exists.
                        if (child[1] != NULL) {
                            return child[1]->findDeepestContainingNode(bounds);
                        }
                    }

                    // There was no containing child, so this node is the
                    // deepest containing node.
                    return this;
                }


                /** Appends all members that intersect the box. 
                If useSphere is true, members that pass the box test
                face a second test against the sphere. */
                void getIntersectingMembers(
                    const AABox&        box, 
                    const Sphere&       sphere,
                    Array<T>&           members,
                    bool                useSphere) const {

                        // Test all values at this node
                        for (int v = 0; v < valueArray.size(); ++v) {
                            const AABox& bounds = valueArray[v].bounds;
                            if (bounds.intersects(box) &&
                                (! useSphere || bounds.intersects(sphere))) {
                                    members.append(valueArray[v].value);
                                }
                        }

                        // If the left child overlaps the box, recurse into it
                        if ((child[0] != NULL) && (box.low()[splitAxis] < splitLocation)) {
                            child[0]->getIntersectingMembers(box, sphere, members, useSphere);
                        }

                        // If the right child overlaps the box, recurse into it
                        if ((child[1] != NULL) && (box.high()[splitAxis] > splitLocation)) {
                            child[1]->getIntersectingMembers(box, sphere, members, useSphere);
                        }
                    }

                    /**
                    Recurse through the tree, assigning splitBounds fields.
                    */
                    void assignSplitBounds(const AABox& myBounds) {
                        splitBounds = myBounds;

                        AABox childBounds[2];
                        myBounds.split(splitAxis, splitLocation, childBounds[0], childBounds[1]);

                        for (int c = 0; c < 2; ++c) {
                            if (child[c]) {
                                child[c]->assignSplitBounds(childBounds[c]);
                            }
                        }
                    }
            };


            /**
            Recursively subdivides the subarray.
            Begin and end indices are inclusive.

            Call assignSplitBounds() on the root node after making a tree.
            */
            Node* makeNode(Array<Handle>& point, int beginIndex, 
                int endIndex, int valuesPerNode, 
                int numMeanSplits)  {

                    Node* node = NULL;

                    if (endIndex - beginIndex + 1 <= valuesPerNode) {
                        // Make a new leaf node
                        node = new Node(point, beginIndex, endIndex);

                        // Set the pointers in the memberTable
                        for (int i = beginIndex; i <= endIndex; ++i) {
                            memberTable.set(point[i].value, node);
                        }

                    } else {
                        // Make a new internal node
                        node = new Node();

                        const AABox bounds = computeBounds(point, beginIndex, endIndex);
                        const Vector3 extent = bounds.high() - bounds.low();

                        Vector3::Axis splitAxis = extent.primaryAxis();

                        double splitLocation;

                        if (numMeanSplits > 0) {
                            // Compute the mean along the axis

                            splitLocation = (bounds.high()[splitAxis] + 
                                bounds.low()[splitAxis]) / 2.0;

                        } else {

                            // Compute the median along the axis

                            // Sort only the subarray
                            std::sort(
                                point.getCArray() + beginIndex,
                                point.getCArray() + endIndex + 1,
                                CenterLT(splitAxis));

                            // Intentional integer divide
                            int midIndex = (beginIndex + endIndex) / 2;

                            // Choose the split location between the two middle elements
                            const Vector3 median = 
                                (point[midIndex].bounds.high() +
                                point[iMin(midIndex + 1, 
                                point.size() - 1)].bounds.low()) * 0.5;

                            splitLocation = median[splitAxis];
                        }


                        // Re-sort around the split. This will allow us to easily
                        // test for overlap
                        std::sort(
                            point.getCArray() + beginIndex,
                            point.getCArray() + endIndex + 1,
                            PivotLT(splitAxis, splitLocation));

                        // Some number of nodes may actually overlap the midddle, so
                        // they must be found and added to *this* node, not one of
                        // its children
                        int overlapBeginIndex, overlapEndIndex;

                        for (overlapBeginIndex = beginIndex;
                            (overlapBeginIndex <= endIndex) &&
                            (point[overlapBeginIndex].bounds.high()[splitAxis] <
                            splitLocation);
                        ++overlapBeginIndex) {}

                        for (overlapEndIndex = endIndex;
                            (overlapEndIndex >= beginIndex) &&
                            (point[overlapEndIndex].bounds.low()[splitAxis] >
                            splitLocation);
                        --overlapEndIndex) {}
#ifdef _ASSEMBLER_DEBUG
                        fprintf(::g_df,"splitLocation: %f, beginIndex: %d, endIndex:%d, overlapBeginIndex: %d, overlapEndIndex: %d\n",splitLocation, beginIndex, endIndex, overlapBeginIndex, overlapEndIndex);
                        if(beginIndex == 220) {
                            float oldf = -100000.0f;

                            for (int xxx = beginIndex;
                                (xxx <= endIndex);
                                ++xxx) {
                                    fprintf(::g_df,"    xxx:%d, point[xxx].bounds.high()[splitAxis]: %f\n",xxx, point[xxx].bounds.high()[splitAxis]);
                                    if(oldf > point[xxx].bounds.high()[splitAxis]) {
                                        fprintf(::g_df,"    huch ...\n");
                                    }
                                    oldf = point[xxx].bounds.high()[splitAxis];
                                }
                        }
#endif
                        // put overlapping boxes in this node
                        for (int i = overlapBeginIndex; i <= overlapEndIndex; ++i) {
                            node->valueArray.push(point[i]);
                            memberTable.set(point[i].value, node);
                        }

                        node->splitAxis     = splitAxis;
                        node->splitLocation = splitLocation;

                        if (overlapBeginIndex > beginIndex) {
                            node->child[0]      = 
                                makeNode(point, beginIndex, overlapBeginIndex - 1, 
                                valuesPerNode, numMeanSplits - 1);
                        }

                        if (overlapEndIndex < endIndex) {
                            node->child[1]      = 
                                makeNode(point, overlapEndIndex + 1, endIndex, valuesPerNode, numMeanSplits - 1);
                        }

                    }

                    return node;
                }

                /**
                Recursively clone the passed in node tree, setting
                pointers for members in the memberTable as appropriate.
                called by the assignment operator.
                */
                Node* cloneTree(Node* src) {
                    Node* dst = new Node(*src);

                    // Make back pointers
                    for (int i = 0; i < dst->valueArray.size(); ++i) {
                        memberTable.set(dst->valueArray[i].value, dst);
                    }

                    // Clone children
                    for (int i = 0; i < 2; ++i) {
                        if (src->child[i] != NULL) {
                            dst->child[i] = cloneTree(src->child[i]);
                        }
                    }

                    return dst;
                }

                /** Maps members to the node containing them */
                Table<T, Node*>         memberTable;

                Node*                   root;



                /** To construct a balanced tree, insert the elements and then call
                AABSPTree::balance(). */
                AABSPTree() : root(NULL) {}


                AABSPTree(const AABSPTree& src) : root(NULL) {
                    *this = src;
                }


                AABSPTree& operator=(const AABSPTree& src) {
                    delete root;
                    // Clone tree takes care of filling out the memberTable.
                    root = cloneTree(src.root);
                }


                ~AABSPTree() {
                    clear();
                }

                /**
                Throws out all elements of the set.
                */
                void clear() {
                    memberTable.clear();
                    delete root;
                    root = NULL;
                }

                size_t size() const {
                    return memberTable.size();
                }

                /**
                Inserts an object into the set if it is not