diff options
Diffstat (limited to 'src/shared/vmap')
28 files changed, 5997 insertions, 0 deletions
diff --git a/src/shared/vmap/AABSPTree.h b/src/shared/vmap/AABSPTree.h new file mode 100644 index 00000000000..9b44470e7d9 --- /dev/null +++ b/src/shared/vmap/AABSPTree.h @@ -0,0 +1,1620 @@ +/** + @file AABSPTree.h + + @maintainer Morgan McGuire, matrix@graphics3d.com + + @created 2004-01-11 + @edited 2007-02-16 + + Copyright 2000-2007, Morgan McGuire. + All rights reserved. + + */ + +#ifndef G3D_AABSPTREE_H +#define G3D_AABSPTREE_H + +#include "VMapTools.h" + +#include "G3D/platform.h" +#include "G3D/Array.h" +#include "G3D/Table.h" +#include "G3D/Vector3.h" +#include "G3D/AABox.h" +#include "G3D/Sphere.h" +#include "G3D/Box.h" +#include "G3D/Triangle.h" +#include "G3D/Ray.h" +#include "G3D/GCamera.h" +#if 0 +#include "G3D/BinaryInput.h" +#include "G3D/BinaryOutput.h" +#endif +#include "G3D/CollisionDetection.h" +#include "G3D/GCamera.h" +#include <algorithm> + +// If defined, in debug mode the tree is checked for consistency +// as a way of detecting corruption due to implementation bugs +// #define VERIFY_TREE + +inline void getBounds(const G3D::Vector3& v, G3D::AABox& out) { + out = G3D::AABox(v); +} + + +inline void getBounds(const G3D::AABox& a, G3D::AABox& out) { + out = a; +} + +inline void getBounds(const G3D::Sphere& s, G3D::AABox& out) { + s.getBounds(out); +} + + +inline void getBounds(const G3D::Box& b, G3D::AABox& out) { + b.getBounds(out); +} + + +inline void getBounds(const G3D::Triangle& t, G3D::AABox& out) { + t.getBounds(out); +} + + + +inline void getBounds(const G3D::Vector3* v, G3D::AABox& out) { + out = G3D::AABox(*v); +} + + +inline void getBounds(const G3D::AABox* a, G3D::AABox& out) { + getBounds(*a, out); +} + +inline void getBounds(const G3D::Sphere* s, G3D::AABox& out) { + s->getBounds(out); +} + + +inline void getBounds(const G3D::Box* b, G3D::AABox& out) { + b->getBounds(out); +} + +inline void getBounds(const G3D::Triangle* t, G3D::AABox& out) { + t->getBounds(out); +} +namespace G3D { + namespace _internal { + + /** + Wraps a pointer value so that it can be treated as the instance itself; + convenient for inserting pointers into a Table but using the + object equality instead of pointer equality. + */ + template<class Type> + class Indirector { + public: + Type* handle; + + inline Indirector(Type* h) : handle(h) {} + + inline Indirector() : handle(NULL) {} + + /** Returns true iff the values referenced by the handles are equivalent. */ + inline bool operator==(const Indirector& m) { + return *handle == *(m.handle); + } + + inline bool operator==(const Type& m) { + return *handle == m; + } + + inline size_t hashCode() const { + return handle->hashCode(); + } + }; + } // namespace internal +} // namespace G3D + +template <class Handle> +struct GHashCode< G3D::_internal::Indirector<Handle> > +{ + size_t operator()(const G3D::_internal::Indirector<Handle>& key) const { return key.hashCode(); } +}; + +namespace G3D { + +/** + A set that supports spatial queries using an axis-aligned + BSP tree for speed. + + AABSPTree allows you to quickly find objects in 3D that lie within + a box or along a ray. For large sets of objects it is much faster + than testing each object for a collision. + + AABSPTree is as powerful as but more general than a Quad Tree, Oct + Tree, or KD Tree, but less general than an unconstrained BSP tree + (which is much slower to create). + + Internally, objects + are arranged into an axis-aligned BSP-tree according to their + axis-aligned bounds. This increases the cost of insertion to + O(log n) but allows fast overlap queries. + + <B>Template Parameters</B> + <DT>The template parameter <I>T</I> must be one for which + the following functions are all overloaded: + + <P><CODE>void ::getBounds(const T&, G3D::AABox&);</CODE> + <DT><CODE>bool ::operator==(const T&, const T&);</CODE> + <DT><CODE>unsigned int ::hashCode(const T&);</CODE> + <DT><CODE>T::T();</CODE> <I>(public constructor of no arguments)</I> + + G3D provides these for common classes like G3D::Vector3 and G3D::Sphere. + If you use a custom class, or a pointer to a custom class, you will need + to define those functions. + + <B>Moving %Set Members</B> + <DT>It is important that objects do not move without updating the + AABSPTree. If the axis-aligned bounds of an object are about + to change, AABSPTree::remove it before they change and + AABSPTree::insert it again afterward. For objects + where the hashCode and == operator are invariant with respect + to the 3D position, + you can use the AABSPTree::update method as a shortcut to + insert/remove an object in one step after it has moved. + + + Note: Do not mutate any value once it has been inserted into AABSPTree. Values + are copied interally. All AABSPTree iterators convert to pointers to constant + values to reinforce this. + + If you want to mutate the objects you intend to store in a AABSPTree + simply insert <I>pointers</I> to your objects instead of the objects + themselves, and ensure that the above operations are defined. (And + actually, because values are copied, if your values are large you may + want to insert pointers anyway, to save space and make the balance + operation faster.) + + <B>Dimensions</B> + Although designed as a 3D-data structure, you can use the AABSPTree + for data distributed along 2 or 1 axes by simply returning bounds + that are always zero along one or more dimensions. + +*/ +namespace _AABSPTree { + + /** Wrapper for a value that includes a cache of its bounds. + Except for the test value used in a set-query operation, there + is only ever one instance of the handle associated with any + value and the memberTable and Nodes maintain pointers to that + heap-allocated value. + */ + template<class TValue> + class Handle { + public: + /** The bounds of each object are constrained to AABox::maxFinite */ + AABox bounds; + + /** Center of bounds. We cache this value to avoid recomputing it + during the median sort, and because MSVC 6 std::sort goes into + an infinite loop if we compute the midpoint on the fly (possibly + a floating point roundoff issue, where B<A and A<B both are true).*/ + Vector3 center; + + TValue value; + + Handle<TValue>() {} + + inline Handle<TValue>(const TValue& v) : value(v) { + getBounds(v, bounds); + bounds = bounds.intersect(AABox::maxFinite()); + center = bounds.center(); + } + + inline bool operator==(const Handle<TValue>& other) const { + return (*value).operator==(*other.value); + } + + inline size_t hashCode() const { + return value->hashCode(); + } + }; + + template<> + class Handle<Triangle> { + public: + /** The bounds of each object are constrained to AABox::maxFinite */ + AABox bounds; + + /** Center of bounds. We cache this value to avoid recomputing it + during the median sort, and because MSVC 6 std::sort goes into + an infinite loop if we compute the midpoint on the fly (possibly + a floating point roundoff issue, where B<A and A<B both are true).*/ + Vector3 center; + + Triangle value; + + Handle<Triangle>() {} + + inline Handle<Triangle>(const Triangle& v) : value(v) { + getBounds(v, bounds); + bounds = bounds.intersect(AABox::maxFinite()); + center = bounds.center(); + } + + inline bool operator==(const Handle<Triangle>& other) const { + return value.operator==(other.value); + } + + inline size_t hashCode() const { + return value.hashCode(); + } + }; +} + +template<class T> class AABSPTree { +protected: +public: + + + /** Returns the bounds of the sub array. Used by makeNode. */ + static AABox computeBounds( + const Array<_AABSPTree::Handle<T>*>& point, + int beginIndex, + int endIndex) { + + Vector3 lo = Vector3::inf(); + Vector3 hi = -lo; + + for (int p = beginIndex; p <= endIndex; ++p) { + lo = lo.min(point[p]->bounds.low()); + hi = hi.max(point[p]->bounds.high()); + } + + return AABox(lo, hi); + } + + /** Compares centers */ + class CenterComparator { + public: + Vector3::Axis sortAxis; + + CenterComparator(Vector3::Axis a) : sortAxis(a) {} + + inline int operator()(_AABSPTree::Handle<T>* A, const _AABSPTree::Handle<T>* B) const { + float a = A->center[sortAxis]; + float b = B->center[sortAxis]; + + if (a < b) { + return 1; + } else if (a > b) { + return -1; + } else { + return 0; + } + } + }; + + + /** Compares bounds for strict >, <, or overlap*/ + class BoundsComparator { + public: + Vector3::Axis sortAxis; + + BoundsComparator(Vector3::Axis a) : sortAxis(a) {} + + inline int operator()(_AABSPTree::Handle<T>* A, const _AABSPTree::Handle<T>* B) const { + const AABox& a = A->bounds; + const AABox& b = B->bounds; + + if (a.high()[sortAxis] < b.low()[sortAxis]) { + return 1; + } else if (a.low()[sortAxis] > b.high()[sortAxis]) { + return -1; + } else { + return 0; + } + } + }; + + + /** Compares bounds to the sort location */ + class Comparator { + public: + Vector3::Axis sortAxis; + float sortLocation; + + Comparator(Vector3::Axis a, float l) : sortAxis(a), sortLocation(l) {} + + inline int operator()(_AABSPTree::Handle<T>* /*ignore*/, const _AABSPTree::Handle<T>* handle) const { + const AABox& box = handle->bounds; + debugAssert(ignore == NULL); + + if (box.high()[sortAxis] < sortLocation) { + // Box is strictly below the sort location + return -1; + } else if (box.low()[sortAxis] > sortLocation) { + // Box is strictly above the sort location + return 1; + } else { + // Box overlaps the sort location + return 0; + } + } + }; + + // Using System::malloc with this class provided no speed improvement. + class Node { + public: + + /** Spatial bounds on all values at this node and its children, based purely on + the parent's splitting planes. May be infinite. */ + AABox splitBounds; + + Vector3::Axis splitAxis; + + /** Location along the specified axis */ + float splitLocation; + + /** child[0] contains all values strictly + smaller than splitLocation along splitAxis. + + child[1] contains all values strictly + larger. + + Both may be NULL if there are not enough + values to bother recursing. + */ + Node* child[2]; + + /** Array of values at this node (i.e., values + straddling the split plane + all values if + this is a leaf node). + + This is an array of pointers because that minimizes + data movement during tree building, which accounts + for about 15% of the time cost of tree building. + */ + Array<_AABSPTree::Handle<T> * > valueArray; + + /** For each object in the value array, a copy of its bounds. + Packing these into an array at the node level + instead putting them in the valueArray improves + cache coherence, which is about a 3x performance + increase when performing intersection computations. + */ + Array<AABox> boundsArray; + + /** Creates node with NULL children */ + Node() { + splitAxis = Vector3::X_AXIS; + splitLocation = 0; + splitBounds = AABox(-Vector3::inf(), Vector3::inf()); + for (int i = 0; i < 2; ++i) { + child[i] = NULL; + } + } + + /** + Doesn't clone children. + */ + Node(const Node& other) : valueArray(other.valueArray), boundsArray(other.boundsArray) { + splitAxis = other.splitAxis; + splitLocation = other.splitLocation; + splitBounds = other.splitBounds; + for (int i = 0; i < 2; ++i) { + child[i] = NULL; + } + } + + /** Copies the specified subarray of pt into point, NULLs the children. + Assumes a second pass will set splitBounds. */ + Node(const Array<_AABSPTree::Handle<T> * >& pt) : valueArray(pt) { + splitAxis = Vector3::X_AXIS; + splitLocation = 0; + for (int i = 0; i < 2; ++i) { + child[i] = NULL; + } + + boundsArray.resize(valueArray.size()); + for (int i = 0; i < valueArray.size(); ++i) { + boundsArray[i] = valueArray[i]->bounds; + } + } + + /** Deletes the children (but not the values) */ + ~Node() { + for (int i = 0; i < 2; ++i) { + delete child[i]; + } + } + + /** Returns true if this node is a leaf (no children) */ + inline bool isLeaf() const { + return (child[0] == NULL) && (child[1] == NULL); + } + + + /** + Recursively appends all handles and children's handles + to the array. + */ + void getHandles(Array<_AABSPTree::Handle<T> * >& handleArray) const { + handleArray.append(valueArray); + for (int i = 0; i < 2; ++i) { + if (child[i] != NULL) { + child[i]->getHandles(handleArray); + } + } + } + + void verifyNode(const Vector3& lo, const Vector3& hi) { + // debugPrintf("Verifying: split %d @ %f [%f, %f, %f], [%f, %f, %f]\n", + // splitAxis, splitLocation, lo.x, lo.y, lo.z, hi.x, hi.y, hi.z); + + debugAssert(lo == splitBounds.low()); + debugAssert(hi == splitBounds.high()); + + for (int i = 0; i < valueArray.length(); ++i) { + const AABox& b = valueArray[i]->bounds; + debugAssert(b == boundsArray[i]); + + for(int axis = 0; axis < 3; ++axis) { + debugAssert(b.low()[axis] <= b.high()[axis]); + 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 < boundsArray.size(); ++v) { + const AABox& bounds = boundsArray[v]; + 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]); + +# if defined(G3D_DEBUG) && defined(VERIFY_TREE) + // Verify the split + for (int v = 0; v < boundsArray.size(); ++v) { + const AABox& bounds = boundsArray[v]; + debugAssert(myBounds.contains(bounds)); + } +# endif + + for (int c = 0; c < 2; ++c) { + if (child[c]) { + child[c]->assignSplitBounds(childBounds[c]); + } + } + } + + /** Returns true if the ray intersects this node */ + bool intersects(const Ray& ray, float distance) const { + // See if the ray will ever hit this node or its children + Vector3 location; + bool alreadyInsideBounds = false; + bool rayWillHitBounds = + VMAP::MyCollisionDetection::collisionLocationForMovingPointFixedAABox( + ray.origin, ray.direction, splitBounds, location, alreadyInsideBounds); + + bool canHitThisNode = (alreadyInsideBounds || + (rayWillHitBounds && ((location - ray.origin).squaredLength() < square(distance)))); + + return canHitThisNode; + } + + template<typename RayCallback> + void intersectRay( + const Ray& ray, + RayCallback& intersectCallback, + float& distance, + bool pStopAtFirstHit, + bool intersectCallbackIsFast) const { + float enterDistance = distance; + + if (! intersects(ray, distance)) { + // The ray doesn't hit this node, so it can't hit the children of the node. + return; + } + + // Test for intersection against every object at this node. + for (int v = 0; v < valueArray.size(); ++v) { + bool canHitThisObject = true; + + if (! intersectCallbackIsFast) { + // See if + Vector3 location; + const AABox& bounds = boundsArray[v]; + bool alreadyInsideBounds = false; + bool rayWillHitBounds = + VMAP::MyCollisionDetection::collisionLocationForMovingPointFixedAABox( + ray.origin, ray.direction, bounds, location, alreadyInsideBounds); + + canHitThisObject = (alreadyInsideBounds || + (rayWillHitBounds && ((location - ray.origin).squaredLength() < square(distance)))); + } + + if (canHitThisObject) { + // It is possible that this ray hits this object. Look for the intersection using the + // callback. + const T& value = valueArray[v]->value; + intersectCallback(ray, value, pStopAtFirstHit, distance); + } + if(pStopAtFirstHit && distance < enterDistance) + return; + } + + // There are three cases to consider next: + // + // 1. the ray can start on one side of the splitting plane and never enter the other, + // 2. the ray can start on one side and enter the other, and + // 3. the ray can travel exactly down the splitting plane + + enum {NONE = -1}; + int firstChild = NONE; + int secondChild = NONE; + + if (ray.origin[splitAxis] < splitLocation) { + + // The ray starts on the small side + firstChild = 0; + + if (ray.direction[splitAxis] > 0) { + // The ray will eventually reach the other side + secondChild = 1; + } + + } else if (ray.origin[splitAxis] > splitLocation) { + + // The ray starts on the large side + firstChild = 1; + + if (ray.direction[splitAxis] < 0) { + secondChild = 0; + } + } else { + // The ray starts on the splitting plane + if (ray.direction[splitAxis] < 0) { + // ...and goes to the small side + firstChild = 0; + } else if (ray.direction[splitAxis] > 0) { + // ...and goes to the large side + firstChild = 1; + } + } + + // Test on the side closer to the ray origin. + if ((firstChild != NONE) && child[firstChild]) { + child[firstChild]->intersectRay(ray, intersectCallback, distance, pStopAtFirstHit, intersectCallbackIsFast); + if(pStopAtFirstHit && distance < enterDistance) + return; + } + + if (ray.direction[splitAxis] != 0) { + // See if there was an intersection before hitting the splitting plane. + // If so, there is no need to look on the far side and recursion terminates. + float distanceToSplittingPlane = (splitLocation - ray.origin[splitAxis]) / ray.direction[splitAxis]; + if (distanceToSplittingPlane > distance) { + // We aren't going to hit anything else before hitting the splitting plane, + // so don't bother looking on the far side of the splitting plane at the other + // child. + return; + } + } + + // Test on the side farther from the ray origin. + if ((secondChild != NONE) && child[secondChild]) { + child[secondChild]->intersectRay(ray, intersectCallback, distance, pStopAtFirstHit, intersectCallbackIsFast); + } + + } + }; + + + /** + Recursively subdivides the subarray. + + Clears the source array as soon as it is no longer needed. + + Call assignSplitBounds() on the root node after making a tree. + */ + Node* makeNode( + Array<_AABSPTree::Handle<T> * >& source, + int valuesPerNode, + int numMeanSplits, + Array<_AABSPTree::Handle<T> * >& temp) { + + Node* node = NULL; + + if (source.size() <= valuesPerNode) { + // Make a new leaf node + node = new Node(source); + + // Set the pointers in the memberTable + for (int i = 0; i < source.size(); ++i) { + memberTable.set(Member(source[i]), node); + } + source.clear(); + + } else { + // Make a new internal node + node = new Node(); + + const AABox bounds = computeBounds(source, 0, source.size() - 1); + const Vector3 extent = bounds.high() - bounds.low(); + + Vector3::Axis splitAxis = extent.primaryAxis(); + + float splitLocation; + + // Arrays for holding the children + Array<_AABSPTree::Handle<T> * > lt, gt; + + if (numMeanSplits <= 0) { + + source.medianPartition(lt, node->valueArray, gt, temp, CenterComparator(splitAxis)); + + // Choose the split location to be the center of whatever fell in the center + splitLocation = node->valueArray[0]->center[splitAxis]; + + // Some of the elements in the lt or gt array might really overlap the split location. + // Move them as needed. + for (int i = 0; i < lt.size(); ++i) { + const AABox& bounds = lt[i]->bounds; + if ((bounds.low()[splitAxis] <= splitLocation) && (bounds.high()[splitAxis] >= splitLocation)) { + node->valueArray.append(lt[i]); + // Remove this element and process the new one that + // is swapped in in its place. + lt.fastRemove(i); --i; + } + } + + for (int i = 0; i < gt.size(); ++i) { + const AABox& bounds = gt[i]->bounds; + if ((bounds.low()[splitAxis] <= splitLocation) && (bounds.high()[splitAxis] >= splitLocation)) { + node->valueArray.append(gt[i]); + // Remove this element and process the new one that + // is swapped in in its place. + gt.fastRemove(i); --i; + } + } + + if ((node->valueArray.size() > (source.size() / 2)) && + (source.size() > 6)) { + // This was a bad partition; we ended up putting the splitting plane right in the middle of most of the + // objects. We could try to split on a different axis, or use a different partition (e.g., the extents mean, + // or geometric mean). This implementation falls back on the extents mean, since that case is already handled + // below. + numMeanSplits = 1; + } + } + + // Note: numMeanSplits may have been increased by the code in the previous case above in order to + // force a re-partition. + + if (numMeanSplits > 0) { + // Split along the mean + splitLocation = (bounds.high()[splitAxis] + + bounds.low()[splitAxis]) / 2.0; + + source.partition(NULL, lt, node->valueArray, gt, Comparator(splitAxis, splitLocation)); + + // The Comparator ensures that elements are strictly on the correct side of the split + } + + +# if defined(G3D_DEBUG) && defined(VERIFY_TREE) + debugAssert(lt.size() + node->valueArray.size() + gt.size() == source.size()); + // Verify that all objects ended up on the correct side of the split. + // (i.e., make sure that the Array partition was correct) + for (int i = 0; i < lt.size(); ++i) { + const AABox& bounds = lt[i]->bounds; + debugAssert(bounds.high()[splitAxis] < splitLocation); + } + + for (int i = 0; i < gt.size(); ++i) { + const AABox& bounds = gt[i]->bounds; + debugAssert(bounds.low()[splitAxis] > splitLocation); + } + + for (int i = 0; i < node->valueArray.size(); ++i) { + const AABox& bounds = node->valueArray[i]->bounds; + debugAssert(bounds.high()[splitAxis] >= splitLocation); + debugAssert(bounds.low()[splitAxis] <= splitLocation); + } +# endif + + // The source array is no longer needed + source.clear(); + + node->splitAxis = splitAxis; + node->splitLocation = splitLocation; + + // Update the bounds array and member table + node->boundsArray.resize(node->valueArray.size()); + for (int i = 0; i < node->valueArray.size(); ++i) { + _AABSPTree::Handle<T> * v = node->valueArray[i]; + node->boundsArray[i] = v->bounds; + memberTable.set(Member(v), node); + } + + if (lt.size() > 0) { + node->child[0] = makeNode(lt, valuesPerNode, numMeanSplits - 1, temp); + } + + if (gt.size() > 0) { + node->child[1] = makeNode(gt, valuesPerNode, numMeanSplits - 1, temp); + } + + } + + 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(Member(dst->valueArray[i]), dst); + } + + // Clone children + for (int i = 0; i < 2; ++i) { + if (src->child[i] != NULL) { + dst->child[i] = cloneTree(src->child[i]); + } + } + + return dst; + } + + /** + Wrapper for a Handle; used to create a memberTable that acts like Table<Handle, Node*> but + stores only Handle* internally to avoid memory copies. + */ + typedef _internal::Indirector<_AABSPTree::Handle<T> > Member; + + typedef Table<Member, Node*> MemberTable; + + /** Maps members to the node containing them */ + MemberTable memberTable; + + Node* root; + +public: + + /** 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); + return *this; + } + + + ~AABSPTree() { + clear(); + } + + /** + Throws out all elements of the set. + */ + void clear() { + typedef typename Table<_internal::Indirector<_AABSPTree::Handle<T> >, Node* >::Iterator It; + + // Delete all handles stored in the member table + It cur = memberTable.begin(); + It end = memberTable.end(); + while (cur != end) { + delete cur->key.handle; + cur->key.handle = NULL; + ++cur; + } + memberTable.clear(); + + // Delete the tree structure itself + delete root; + root = NULL; + } + + size_t size() const { + return memberTable.size(); + } + + /** + Inserts an object into the set if it is not + already present. O(log n) time. Does not + cause the tree to be balanced. + */ + void insert(const T& value) { + if (contains(value)) { + // Already in the set + return; + } + + _AABSPTree::Handle<T>* h = new _AABSPTree::Handle<T>(value); + + if (root == NULL) { + // This is the first node; create a root node + root = new Node(); + } + + Node* node = root->findDeepestContainingNode(h->bounds); + + // Insert into the node + node->valueArray.append(h); + node->boundsArray.append(h->bounds); + + // Insert into the node table + Member m(h); + memberTable.set(m, node); + } + + /** Inserts each elements in the array in turn. If the tree + begins empty (no structure and no elements), this is faster + than inserting each element in turn. You still need to balance + the tree at the end.*/ + void insert(const Array<T>& valueArray) { + if (root == NULL) { + // Optimized case for an empty tree; don't bother + // searching or reallocating the root node's valueArray + // as we incrementally insert. + root = new Node(); + root->valueArray.resize(valueArray.size()); + root->boundsArray.resize(root->valueArray.size()); + for (int i = 0; i < valueArray.size(); ++i) { + // Insert in opposite order so that we have the exact same + // data structure as if we inserted each (i.e., order is reversed + // from array). + _AABSPTree::Handle<T>* h = new _AABSPTree::Handle<T>(valueArray[i]); + int j = valueArray.size() - i - 1; + root->valueArray[j] = h; + root->boundsArray[j] = h->bounds; + memberTable.set(Member(h), root); + } + + } else { + // Insert at appropriate tree depth. + for (int i = 0; i < valueArray.size(); ++i) { + insert(valueArray[i]); + } + } + } + + + /** + Returns true if this object is in the set, otherwise + returns false. O(1) time. + */ + bool contains(const T& value) { + // Temporarily create a handle and member + _AABSPTree::Handle<T> h(value); + return memberTable.containsKey(Member(&h)); + } + + + /** + Removes an object from the set in O(1) time. + It is an error to remove members that are not already + present. May unbalance the tree. + + Removing an element never causes a node (split plane) to be removed... + nodes are only changed when the tree is rebalanced. This behavior + is desirable because it allows the split planes to be serialized, + and then deserialized into an empty tree which can be repopulated. + */ + void remove(const T& value) { + debugAssertM(contains(value), + "Tried to remove an element from a " + "AABSPTree that was not present"); + + // Get the list of elements at the node + _AABSPTree::Handle<T> h(value); + Member m(&h); + + Array<_AABSPTree::Handle<T> * >& list = memberTable[m]->valueArray; + + _AABSPTree::Handle<T>* ptr = NULL; + + // Find the element and remove it + for (int i = list.length() - 1; i >= 0; --i) { + if (list[i]->value == value) { + // This was the element. Grab the pointer so that + // we can delete it below + ptr = list[i]; + + // Remove the handle from the node + list.fastRemove(i); + + // Remove the corresponding bounds + memberTable[m]->boundsArray.fastRemove(i); + break; + } + } + + // Remove the member + memberTable.remove(m); + + // Delete the handle data structure + delete ptr; + ptr = NULL; + } + + + /** + If the element is in the set, it is removed. + The element is then inserted. + + This is useful when the == and hashCode methods + on <I>T</I> are independent of the bounds. In + that case, you may call update(v) to insert an + element for the first time and call update(v) + again every time it moves to keep the tree + up to date. + */ + void update(const T& value) { + if (contains(value)) { + remove(value); + } + insert(value); + } + + + /** + Rebalances the tree (slow). Call when objects + have moved substantially from their original positions + (which unbalances the tree and causes the spatial + queries to be slow). + + @param valuesPerNode Maximum number of elements to put at + a node. + + @param numMeanSplits numMeanSplits = 0 gives a + fully axis aligned BSP-tree, where the balance operation attempts to balance + the tree so that every splitting plane has an equal number of left + and right children (i.e. it is a <B>median</B> split along that axis). + This tends to maximize average performance. + + You can override this behavior by + setting a number of <B>mean</B> (average) splits. numMeanSplits = MAX_INT + creates a full oct-tree, which tends to optimize peak performance at the expense of + average performance. It tends to have better clustering behavior when + members are not uniformly distributed. + */ + void balance(int valuesPerNode = 5, int numMeanSplits = 3) { + if (root == NULL) { + // Tree is empty + return; + } + + // Get all handles and delete the old tree structure + Node* oldRoot = root; + for (int c = 0; c < 2; ++c) { + if (root->child[c] != NULL) { + root->child[c]->getHandles(root->valueArray); + + // Delete the child; this will delete all structure below it + delete root->child[c]; + root->child[c] = NULL; + } + } + + Array<_AABSPTree::Handle<T> * > temp; + // Make a new root. Work with a copy of the value array because + // makeNode clears the source array as it progresses + Array<_AABSPTree::Handle<T> * > copy(oldRoot->valueArray); + root = makeNode(copy, valuesPerNode, numMeanSplits, temp); + + // Throw away the old root node + delete oldRoot; + oldRoot = NULL; + + // Walk the tree, assigning splitBounds. We start with unbounded + // space. This will override the current member table. + root->assignSplitBounds(AABox::maxFinite()); + +# ifdef _DEBUG + // Ensure that the balanced tree is till correct + root->verifyNode(Vector3::minFinite(), Vector3::maxFinite()); +# endif + } + +protected: + + /** + @param parentMask The mask that this node returned from culledBy. + */ + static void getIntersectingMembers( + const Array<Plane>& plane, + Array<T>& members, + Node* node, + uint32 parentMask) { + + int dummy; + + if (parentMask == 0) { + // None of these planes can cull anything + for (int v = node->valueArray.size() - 1; v >= 0; --v) { + members.append(node->valueArray[v]->value); + } + + // Iterate through child nodes + for (int c = 0; c < 2; ++c) { + if (node->child[c]) { + getIntersectingMembers(plane, members, node->child[c], 0); + } + } + } else { + + // Test values at this node against remaining planes + for (int v = node->boundsArray.size() - 1; v >= 0; --v) { + if (! node->boundsArray[v].culledBy(plane, dummy, parentMask)) { + members.append(node->valueArray[v]->value); + } + } + + uint32 childMask = 0xFFFFFF; + + // Iterate through child nodes + for (int c = 0; c < 2; ++c) { + if (node->child[c] && + ! node->child[c]->splitBounds.culledBy(plane, dummy, parentMask, childMask)) { + // This node was not culled + getIntersectingMembers(plane, members, node->child[c], childMask); + } + } + } + } + +public: + + /** + Returns all members inside the set of planes. + @param members The results are appended to this array. + */ + void getIntersectingMembers(const Array<Plane>& plane, Array<T>& members) const { + if (root == NULL) { + return; + } + + getIntersectingMembers(plane, members, root, 0xFFFFFF); + } + + /** + Typically used to find all visible + objects inside the view frustum (see also GCamera::getClipPlanes)... i.e. all objects + <B>not<B> culled by frustum. + + Example: + <PRE> + Array<Object*> visible; + tree.getIntersectingMembers(camera.frustum(), visible); + // ... Draw all objects in the visible array. + </PRE> + @param members The results are appended to this array. + */ + void getIntersectingMembers(const GCamera::Frustum& frustum, Array<T>& members) const { + Array<Plane> plane; + + for (int i = 0; i < frustum.faceArray.size(); ++i) { + plane.append(frustum.faceArray[i].plane); + } + + getIntersectingMembers(plane, members); + } + + /** + C++ STL style iterator variable. See beginBoxIntersection(). + The iterator overloads the -> (dereference) operator, so this + acts like a pointer to the current member. + */ + // This iterator turns Node::getIntersectingMembers into a + // coroutine. It first translates that method from recursive to + // stack based, then captures the system state (analogous to a Scheme + // continuation) after each element is appended to the member array, + // and allowing the computation to be restarted. + class BoxIntersectionIterator { + private: + friend class AABSPTree<T>; + + /** True if this is the "end" iterator instance */ + bool isEnd; + + /** The box that we're testing against. */ + AABox box; + + /** Node that we're currently looking at. Undefined if isEnd + is true. */ + Node* node; + + /** Nodes waiting to be processed */ + // We could use backpointers within the tree and careful + // state management to avoid ever storing the stack-- but + // it is much easier this way and only inefficient if the + // caller uses post increment (which they shouldn't!). + Array<Node*> stack; + + /** The next index of current->valueArray to return. + Undefined when isEnd is true.*/ + int nextValueArrayIndex; + + BoxIntersectionIterator() : isEnd(true) {} + + BoxIntersectionIterator(const AABox& b, const Node* root) : + isEnd(root == NULL), box(b), + node(const_cast<Node*>(root)), nextValueArrayIndex(-1) { + + // We intentionally start at the "-1" index of the current + // node so we can use the preincrement operator to move + // ourselves to element 0 instead of repeating all of the + // code from the preincrement method. Note that this might + // cause us to become the "end" instance. + ++(*this); + } + + public: + + inline bool operator!=(const BoxIntersectionIterator& other) const { + return ! (*this == other); + } + + bool operator==(const BoxIntersectionIterator& other) const { + if (isEnd) { + return other.isEnd; + } else if (other.isEnd) { + return false; + } else { + // Two non-end iterators; see if they match. This is kind of + // silly; users shouldn't call == on iterators in general unless + // one of them is the end iterator. + if ((box != other.box) || (node != other.node) || + (nextValueArrayIndex != other.nextValueArrayIndex) || + (stack.length() != other.stack.length())) { + return false; + } + + // See if the stacks are the same + for (int i = 0; i < stack.length(); ++i) { + if (stack[i] != other.stack[i]) { + return false; + } + } + + // We failed to find a difference; they must be the same + return true; + } + } + + /** + Pre increment. + */ + BoxIntersectionIterator& operator++() { + ++nextValueArrayIndex; + + bool foundIntersection = false; + while (! isEnd && ! foundIntersection) { + + // Search for the next node if we've exhausted this one + while ((! isEnd) && (nextValueArrayIndex >= node->valueArray.length())) { + // If we entered this loop, then the iterator has exhausted the elements at + // node (possibly because it just switched to a child node with no members). + // This loop continues until it finds a node with members or reaches + // the end of the whole intersection search. + + // If the right child overlaps the box, push it onto the stack for + // processing. + if ((node->child[1] != NULL) && + (box.high()[node->splitAxis] > node->splitLocation)) { + stack.push(node->child[1]); + } + + // If the left child overlaps the box, push it onto the stack for + // processing. + if ((node->child[0] != NULL) && + (box.low()[node->splitAxis] < node->splitLocation)) { + stack.push(node->child[0]); + } + + if (stack.length() > 0) { + // Go on to the next node (which may be either one of the ones we + // just pushed, or one from farther back the tree). + node = stack.pop(); + nextValueArrayIndex = 0; + } else { + // That was the last node; we're done iterating + isEnd = true; + } + } + + // Search for the next intersection at this node until we run out of children + while (! isEnd && ! foundIntersection && (nextValueArrayIndex < node->valueArray.length())) { + if (box.intersects(node->boundsArray[nextValueArrayIndex])) { + foundIntersection = true; + } else { + ++nextValueArrayIndex; + // If we exhaust this node, we'll loop around the master loop + // to find a new node. + } + } + } + + return *this; + } + + private: + /** + Post increment (much slower than preincrement!). Intentionally overloaded to preclude accidentally slow code. + */ + BoxIntersectionIterator operator++(int); + /*{ + BoxIntersectionIterator old = *this; + ++this; + return old; + }*/ + + public: + + /** Overloaded dereference operator so the iterator can masquerade as a pointer + to a member */ + const T& operator*() const { + alwaysAssertM(! isEnd, "Can't dereference the end element of an iterator"); + return node->valueArray[nextValueArrayIndex]->value; + } + + /** Overloaded dereference operator so the iterator can masquerade as a pointer + to a member */ + T const * operator->() const { + alwaysAssertM(! isEnd, "Can't dereference the end element of an iterator"); + return &(stack.last()->valueArray[nextValueArrayIndex]->value); + } + + /** Overloaded cast operator so the iterator can masquerade as a pointer + to a member */ + operator T*() const { + alwaysAssertM(! isEnd, "Can't dereference the end element of an iterator"); + return &(stack.last()->valueArray[nextValueArrayIndex]->value); + } + }; + + + /** + Iterates through the members that intersect the box + */ + BoxIntersectionIterator beginBoxIntersection(const AABox& box) const { + return BoxIntersectionIterator(box, root); + } + + BoxIntersectionIterator endBoxIntersection() const { + // The "end" iterator instance + return BoxIntersectionIterator(); + } + + /** + Appends all members whose bounds intersect the box. + See also AABSPTree::beginBoxIntersection. + */ + void getIntersectingMembers(const AABox& box, Array<T>& members) const { + if (root == NULL) { + return; + } + root->getIntersectingMembers(box, Sphere(Vector3::zero(), 0), members, false); + } + + + /** + Invoke a callback for every member along a ray until the closest intersection is found. + + @param callback either a function or an instance of a class with an overloaded operator() of the form: + + <code>void callback(const Ray& ray, const T& object, float& distance)</code>. If the ray hits the object + before travelling distance <code>distance</code>, updates <code>distance</code> with the new distance to + the intersection, otherwise leaves it unmodified. A common example is: + + <pre> + class Entity { + public: + + void intersect(const Ray& ray, float& maxDist, Vector3& outLocation, Vector3& outNormal) { + float d = maxDist; + + // ... search for intersection distance d + + if ((d > 0) && (d < maxDist)) { + // Intersection occured + maxDist = d; + outLocation = ...; + outNormal = ...; + } + } + }; + + // Finds the surface normal and location of the first intersection with the scene + class Intersection { + public: + Entity* closestEntity; + Vector3 hitLocation; + Vector3 hitNormal; + + void operator()(const Ray& ray, const Entity* entity, float& distance) { + entity->intersect(ray, distance, hitLocation, hitNormal); + } + }; + + AABSPTree<Entity*> scene; + + Intersection intersection; + float distance = inf(); + scene.intersectRay(camera.worldRay(x, y), intersection, distance); + </pre> + + + @param distance When the method is invoked, this is the maximum distance that the tree should search for an intersection. + On return, this is set to the distance to the first intersection encountered. + + @param intersectCallbackIsFast If false, each object's bounds are tested before the intersectCallback is invoked. + If the intersect callback runs at the same speed or faster than AABox-ray intersection, set this to true. + */ + template<typename RayCallback> + void intersectRay( + const Ray& ray, + RayCallback& intersectCallback, + float& distance, + bool pStopAtFirstHit, + bool intersectCallbackIsFast = false) const { + + root->intersectRay(ray, intersectCallback, distance, pStopAtFirstHit, intersectCallbackIsFast); + + } + + + /** + @param members The results are appended to this array. + */ + void getIntersectingMembers(const Sphere& sphere, Array<T>& members) const { + if (root == NULL) { + return; + } + + AABox box; + sphere.getBounds(box); + root->getIntersectingMembers(box, sphere, members, true); + + } +#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. + */ + void serializeStructure(BinaryOutput& bo) const { + Node::serializeStructure(root, bo); + } + + /** Clears the member table */ + void deserializeStructure(BinaryInput& bi) { + clear(); + root = Node::deserializeStructure(bi); + } +#endif + /** + Returns an array of all members of the set. See also AABSPTree::begin. + */ + void getMembers(Array<T>& members) const { + Array<Member> temp; + memberTable.getKeys(temp); + for (int i = 0; i < temp.size(); ++i) { + members.append(temp[i].handle->value); + } + } + + + /** + C++ STL style iterator variable. See begin(). + Overloads the -> (dereference) operator, so this acts like a pointer + to the current member. + */ + class Iterator { + private: + friend class AABSPTree<T>; + + // Note: this is a Table iterator, we are currently defining + // Set iterator + typename Table<Member, Node*>::Iterator it; + + Iterator(const typename Table<Member, Node*>::Iterator& it) : it(it) {} + + public: + + inline bool operator!=(const Iterator& other) const { + return !(*this == other); + } + + bool operator==(const Iterator& other) const { + return it == other.it; + } + + /** + Pre increment. + */ + Iterator& operator++() { + ++it; + return *this; + } + + private: + /** + Post increment (slower than preincrement). Intentionally unimplemented to prevent slow code. + */ + Iterator operator++(int);/* { + Iterator old = *this; + ++(*this); + return old; + }*/ + public: + + const T& operator*() const { + return it->key.handle->value; + } + + T* operator->() const { + return &(it->key.handle->value); + } + + operator T*() const { + return &(it->key.handle->value); + } + }; + + + /** + C++ STL style iterator method. Returns the first member. + Use preincrement (++entry) to get to the next element (iteration + order is arbitrary). + Do not modify the set while iterating. + */ + Iterator begin() const { + return Iterator(memberTable.begin()); + } + + + /** + C++ STL style iterator method. Returns one after the last iterator + element. + */ + Iterator end() const { + return Iterator(memberTable.end()); + } +}; + +} + +#endif + + + diff --git a/src/shared/vmap/BaseModel.cpp b/src/shared/vmap/BaseModel.cpp new file mode 100644 index 00000000000..9a1e9fd1002 --- /dev/null +++ b/src/shared/vmap/BaseModel.cpp @@ -0,0 +1,95 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "BaseModel.h" +#include "VMapTools.h" + +using namespace G3D; + +namespace VMAP +{ + //========================================================== + + void BaseModel::getMember(Array<TriangleBox>& pMembers) + { + for(unsigned int i=0; i<iNTriangles; i++) + { + pMembers.append(iTriangles[i]); + } + } + + //========================================================== + BaseModel::BaseModel(unsigned int pNNodes, unsigned int pNTriangles) + { + init(pNNodes, pNTriangles); + }; + + //========================================================== + + void BaseModel::init(unsigned int pNNodes, unsigned int pNTriangles) + { + iNNodes = pNNodes; + iNTriangles = pNTriangles; + iTriangles = 0; + iTreeNodes = 0; + if(iNNodes >0) iTreeNodes = new TreeNode[iNNodes]; + if(iNTriangles >0) iTriangles = new TriangleBox[iNTriangles]; + } + + //========================================================== + + void BaseModel::free() + { + if(getTriangles() != 0) delete [] getTriangles(); setNTriangles(0); + if(getTreeNodes() != 0) delete [] getTreeNodes(); setNNodes(0); + } + + //========================================================== + + void BaseModel::intersect(const G3D::AABox& pBox, const G3D::Ray& pRay, float& pMaxDist, G3D::Vector3& pOutLocation, G3D::Vector3& /*pOutNormal*/) const + { + bool isInside = false; + + float d = MyCollisionDetection::collisionLocationForMovingPointFixedAABox( + pRay.origin, pRay.direction, + pBox, + pOutLocation, isInside); + if (!isInside && ((d > 0) && (d < pMaxDist))) + { + pMaxDist = d; + } + } + + //========================================================== + + bool BaseModel::intersect(const G3D::AABox& pBox, const G3D::Ray& pRay, float& pMaxDist) const + { + // See if the ray will ever hit this node or its children + Vector3 location; + bool alreadyInsideBounds = false; + bool rayWillHitBounds = + MyCollisionDetection::collisionLocationForMovingPointFixedAABox( + pRay.origin, pRay.direction, pBox, location, alreadyInsideBounds); + + bool canHitThisNode = (alreadyInsideBounds || + (rayWillHitBounds && ((location - pRay.origin).squaredLength() < (pMaxDist * pMaxDist)))); + + return canHitThisNode; + } + +} // VMAP diff --git a/src/shared/vmap/BaseModel.h b/src/shared/vmap/BaseModel.h new file mode 100644 index 00000000000..78ded7811b6 --- /dev/null +++ b/src/shared/vmap/BaseModel.h @@ -0,0 +1,99 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _BASEMODEL_H_ +#define _BASEMODEL_H_ + +#include <G3D/AABox.h> +#include <G3D/Vector3.h> + +#include "ShortVector.h" +#include "ShortBox.h" +#include "TreeNode.h" + +/** +A model is based on triangles. To be able to check intersection we need a BSP-Tree. +This Class holds the array of triangles as well as the management information for the BSP-Tree. +Both are stored in static array and index information is used instead of pointers. +Therefore we can load the whole object as a binary block. + +The vectors are relative to a base position. +*/ + +namespace VMAP +{ + + class BaseModel + { + protected: + TriangleBox *iTriangles; + TreeNode *iTreeNodes; + unsigned int iNTriangles; + unsigned int iNNodes; + G3D::Vector3 iBasePosition; + public: + BaseModel() { iNTriangles = 0; iNNodes = 0; iTriangles = 0; iTreeNodes = 0;}; + BaseModel(unsigned int pNNodes , TreeNode* pTreeNode, unsigned int pNTriangles, TriangleBox* pTriangleBox) + { + iNNodes = pNNodes; iNTriangles = pNTriangles; iTriangles = pTriangleBox; iTreeNodes = pTreeNode; + }; + BaseModel(unsigned int pNNodes, unsigned int pNTriangles); + + // destructor does nothing ! The subclass controles the array memory and knows when to free it + ~BaseModel() {} + + void free(); + void init(unsigned int pNNodes, unsigned int pNTriangles); + + void getMember(G3D::Array<TriangleBox>& pMembers); + + inline const TriangleBox& getTriangle(int pPos) const { return(iTriangles[pPos]); } + inline TriangleBox& getTriangle(int pPos) { return(iTriangles[pPos]); } + + inline void setTriangle(const TriangleBox& pTriangleBox, int pPos) { iTriangles[pPos] = pTriangleBox; } + + inline const TreeNode& getTreeNode(int pPos) const { return(getTreeNodes()[pPos]); } + inline TreeNode& getTreeNode(int pPos) { return(getTreeNodes()[pPos]); } + + inline void setTreeNode(const TreeNode& pTreeNode, int pPos) { getTreeNodes()[pPos] = pTreeNode; } + + inline void setBasePosition(const G3D::Vector3& pBasePosition) { iBasePosition = pBasePosition; } + + inline const G3D::Vector3& getBasePosition() const { return(iBasePosition); } + + inline unsigned int getNNodes() const { return(iNNodes); } + inline unsigned int getNTriangles() const { return(iNTriangles); } + + inline void setNNodes(unsigned int pNNodes) { iNNodes = pNNodes; } + inline void setNTriangles(unsigned int pNTriangles) { iNTriangles = pNTriangles; } + + inline void setTriangleArray(TriangleBox *pGlobalTriangleArray ) { iTriangles = pGlobalTriangleArray ; } + inline void setTreeNodeArray(TreeNode *pGlobalTreeNodeArray ) { iTreeNodes = pGlobalTreeNodeArray ; } + + inline TriangleBox* getTriangles() const { return(iTriangles); } + + inline TreeNode* getTreeNodes() const{ return(iTreeNodes); } + + inline size_t getMemUsage() { return(iNTriangles * sizeof(TriangleBox) + iNNodes * sizeof(TreeNode) + sizeof(BaseModel)); } + + void intersect(const G3D::AABox& pBox, const G3D::Ray& pRay, float& pMaxDist, G3D::Vector3& pOutLocation, G3D::Vector3& pOutNormal) const; + bool intersect(const G3D::AABox& pBox, const G3D::Ray& pRay, float& pMaxDist) const; + }; + +} +#endif /*BASEMODEL_H_*/ diff --git a/src/shared/vmap/CoordModelMapping.cpp b/src/shared/vmap/CoordModelMapping.cpp new file mode 100644 index 00000000000..0ea0261c894 --- /dev/null +++ b/src/shared/vmap/CoordModelMapping.cpp @@ -0,0 +1,187 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "CoordModelMapping.h" + +#include <string.h> + +using namespace G3D; + +namespace VMAP +{ + + //============================================================ + //============================================================ + + void CMappingEntry::addFilename(char *pName) + { + std::string name = std::string(pName); + if(!iFilenames.contains(name)) + iFilenames.append(std::string(pName)); + } + + //============================================================ + + const std::string CMappingEntry::getKeyString() const + { + return(CMappingEntry::getKeyString(iMapId,xPos, yPos)); + } + + //============================================================ + //============================================================ + //============================================================ + + CoordModelMapping::~CoordModelMapping() + { + Array<std::string> keys = iMapObjectFiles.getKeys(); + for (int k = 0; k < keys.length(); k++) + { + CMappingEntry *value = getCMappingEntry(keys[k]); + if(value != 0) + { + iMapObjectFiles.remove(keys[k]); + delete value; + } + } + } + + //============================================================ + + int findPosChar(const char *namebuffer, char pSearch, int pCount) + { + int result = -1; + int pos=0; + while(namebuffer[pos] != 0) + { + if(namebuffer[pos] == pSearch) + { + --pCount; + } + if(pCount == 0) + { + result = pos; + break; + } + ++pos; + } + return result; + } + //============================================================ + bool CoordModelMapping::readCoordinateMapping(const std::string& pDirectoryFileName) + { + FILE *f = fopen(pDirectoryFileName.c_str(), "rb"); + bool result = false; + char buffer[500+1]; + + if(f) + { + result = true; + CMappingEntry* cMappingEntry; + while(fgets(buffer, 500, f)) + { + //char namebuffer[500]; + char positionbuffer[500]; + int xpos, ypos, noVec; + float scale; + xpos = ypos = noVec = 0; + + //sscanf(buffer, "%d %d %s %s %f %d", &xpos, &ypos, namebuffer,positionbuffer, &scale, &noVec); + + // this is ugly, but the format has no read delimiter and a space could be in the first part of the name + int nameStart = findPosChar(buffer, ' ', 2);// find the 2. space + if(nameStart > -1 && (iFilterMethod == NULL || (*iFilterMethod)(buffer))) + { + ++nameStart; + // find the 1. / (now a space only can be found at the end of the name) + int nameEnd = nameStart + findPosChar(&buffer[nameStart], '/', 1); + // find the 1. space (after the name) + nameEnd += findPosChar(&buffer[nameEnd], ' ', 1); + buffer[nameEnd] = 0; // terminate the name + + sscanf(buffer, "%d %d", &xpos, &ypos); + sscanf(&buffer[nameEnd+1], "%s %f %d", positionbuffer, &scale, &noVec); + unsigned int mapId = getMapIdFromFilename(std::string(&buffer[nameStart])); + if(!iMapIds.contains(mapId)) + { + iMapIds.append(mapId); + } + if(!isWorldAreaMap(mapId)) + { + xpos = 0; // store all files under the groupKey + ypos = 0; + } + + std::string key = CMappingEntry::getKeyString(mapId, xpos, ypos); + cMappingEntry = getCMappingEntry(key); + if(cMappingEntry == 0) + { + cMappingEntry = new CMappingEntry(mapId, xpos, ypos); + addCMappingEntry(cMappingEntry); + } + char namebuffer2[500]; + sprintf(namebuffer2, "%d %s#%s_%f", noVec, &buffer[nameStart], positionbuffer, scale); + cMappingEntry->addFilename(namebuffer2); + //break; + } + } + fclose(f); + } + return result; + } + + //============================================================ + + const NameCollection CoordModelMapping::getFilenamesForCoordinate(unsigned int pMapId, int xPos, int yPos) + { + NameCollection result; + Array<std::string> rawNames; + + CMappingEntry *entry = getCMappingEntry(CMappingEntry::getKeyString(pMapId, xPos, yPos)); + if(entry != 0) + { + rawNames = entry->getFilenames(); + + int pos = 0; + while(pos < rawNames.size()) + { + char namebuffer[500]; + int noVerc; + int startName = findPosChar(rawNames[pos].c_str(), ' ', 1) + 1; + int endName = (int) rawNames[pos].length(); + sscanf(rawNames[pos].c_str(), "%d", &noVerc); + memcpy(namebuffer, &rawNames[pos].c_str()[startName], endName-startName); + namebuffer[endName-startName] = 0; + sscanf(rawNames[pos].c_str(), "%d", &noVerc); + std::string modelPosFileName = std::string(namebuffer); + if(noVerc > MIN_VERTICES_FOR_OWN_CONTAINER_FILE) + { + result.appendToSingle(modelPosFileName); + } + else + { + result.appendToMain(modelPosFileName); + } + ++pos; + } + } + return result; + } + + //================================================================= + +} diff --git a/src/shared/vmap/CoordModelMapping.h b/src/shared/vmap/CoordModelMapping.h new file mode 100644 index 00000000000..908c56e66dd --- /dev/null +++ b/src/shared/vmap/CoordModelMapping.h @@ -0,0 +1,144 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _COORDMODELMAPPING_H_ +#define _COORDMODELMAPPING_H_ + +#include <G3D/Table.h> +#include <G3D/Array.h> + +/** +This Class is a helper Class to convert the raw vector data into BSP-Trees. +We read the directory file of the raw data output and build logical groups. +Models with a lot of vectors are not merged into a resulting model, but separated into an additional file. +*/ + +namespace VMAP +{ + + #define MIN_VERTICES_FOR_OWN_CONTAINER_FILE 65000 + + // if we are in an instance + #define MIN_INST_VERTICES_FOR_OWN_CONTAINER_FILE 40000 + + //===================================================== + class NameCollection + { + public: + G3D::Array<std::string> iMainFiles; + G3D::Array<std::string> iSingeFiles; + + void appendToMain(std::string pStr) { iMainFiles.append(pStr); } + void appendToSingle(std::string pStr) { iSingeFiles.append(pStr); } + + size_t size() { return (iMainFiles.size() + iSingeFiles.size()); } + }; + + //===================================================== + + class CMappingEntry + { + private: + int xPos; + int yPos; + unsigned int iMapId; + G3D::Array<std::string> iFilenames; + + public: + CMappingEntry() { }; + CMappingEntry(unsigned int pMapId, const int pXPos, const int pYPos) + { + iMapId = pMapId; + xPos = pXPos; yPos = pYPos; + }; + ~CMappingEntry() {}; + + void addFilename(char *pName); + const std::string getKeyString() const; + inline const G3D::Array<std::string>& getFilenames() const { return(iFilenames); } + + static const std::string getKeyString(unsigned int pMapId, int pXPos, int pYPos) + { + char b[100]; + sprintf(b,"%03u_%d_%d", pMapId, pXPos, pYPos); + return(std::string(b)); + } + + }; + + //===================================================== + + class CoordModelMapping + { + private: + G3D::Table<std::string, CMappingEntry *> iMapObjectFiles; + G3D::Table<std::string, std::string> iProcesseSingleFiles; + G3D::Array<unsigned int> iMapIds; + G3D::Array<unsigned int> iWorldAreaGroups; + bool (*iFilterMethod)(char *pName); + + inline void addCMappingEntry(CMappingEntry* pCMappingEntry) + { + iMapObjectFiles.set(pCMappingEntry->getKeyString(), pCMappingEntry); + } + + inline CMappingEntry* getCMappingEntry(const std::string& pKey) + { + if(iMapObjectFiles.containsKey(pKey)) + return(iMapObjectFiles.get(pKey)); + else + return 0; + } + + public: + CoordModelMapping() { iFilterMethod = NULL; } + virtual ~CoordModelMapping(); + + bool readCoordinateMapping(const std::string& pDirectoryFileName); + + const NameCollection getFilenamesForCoordinate(unsigned int pMapId, int xPos, int yPos); + + static unsigned int getMapIdFromFilename(std::string pName) + { + size_t spos; + + spos = pName.find_last_of('/'); + std::string basename = pName.substr(0, spos); + spos = basename.find_last_of('/'); + std::string groupname = basename.substr(spos+1, basename.length()); + unsigned int mapId = atoi(groupname.c_str()); + return(mapId); + } + + const G3D::Array<unsigned int>& getMaps() const { return iMapIds; } + inline bool isAlreadyProcessedSingleFile(std::string pName) { return(iProcesseSingleFiles.containsKey(pName)); } + inline void addAlreadyProcessedSingleFile(std::string pName) { iProcesseSingleFiles.set(pName,pName); } + + inline void addWorldAreaMap(unsigned int pMapId) + { + if(!iWorldAreaGroups.contains(pMapId)) + { + iWorldAreaGroups.append(pMapId); + } + } + inline bool isWorldAreaMap(unsigned int pMapId) { return(iWorldAreaGroups.contains(pMapId)); } + void setModelNameFilterMethod(bool (*pFilterMethod)(char *pName)) { iFilterMethod = pFilterMethod; } + + }; +} +#endif /*_COORDMODELMAPPING_H_*/ diff --git a/src/shared/vmap/DebugCmdLogger.cpp b/src/shared/vmap/DebugCmdLogger.cpp new file mode 100644 index 00000000000..56a5d3ffd2a --- /dev/null +++ b/src/shared/vmap/DebugCmdLogger.cpp @@ -0,0 +1,125 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "DebugCmdLogger.h" + +using namespace G3D; + +namespace VMAP +{ + + bool CommandFileRW::appendCmd(const Command& +#ifdef _DEBUG + pCommand +#endif + ) + { + #ifdef _DEBUG + bool result = false; + if(iWritingEnabled || pCommand.isCoreCmd()) + { + FILE* f = fopen(iFileName.c_str(), "ab"); + if(f) + { + result = true; + if(fwrite(&pCommand, sizeof(Command), 1, f) != 1) { result = false; } + fclose(f); + } + } + else + { + result = true; + } + return result; + #else + return true; + #endif + } + + //========================================================= + + bool CommandFileRW::appendCmds(const Array<Command>& +#ifdef _DEBUG + pCmdArray +#endif + ) + { + #ifdef _DEBUG + bool result = false; + if(iWritingEnabled) + { + FILE* f; + if(resetfile) + f = fopen(iFileName.c_str(), "wb"); + else + f = fopen(iFileName.c_str(), "ab"); + resetfile = false; + + if(f) + { + result = true; + for(int i=0; i<pCmdArray.size(); ++i) + { + if(fwrite(&pCmdArray[i], sizeof(Command), 1, f) != 1) { result = false; break; } + } + fclose(f); + } + } + else + { + result = true; + } + return result; + #else + return true; + #endif + } + + //========================================================= + + bool CommandFileRW::getNewCommands(Array<Command>& pCmdArray) + { + bool result = false; + FILE* f = fopen(iFileName.c_str(), "rb"); + if(f) + { + Command cmd; + if(fseek(f, iLastPos, SEEK_SET) == 0) { result = true; } + while(result) + { + if(fread(&cmd, sizeof(Command), 1, f) != 1) + { + result = false; + } + iLastPos = ftell(f); + if(cmd.getType() == STOP) + { + break; + } + pCmdArray.append(cmd); + } + fclose(f); + } + if(result) + { + iCommandArray.append(pCmdArray); + } + return(result); + } + //======================================================== +} diff --git a/src/shared/vmap/DebugCmdLogger.h b/src/shared/vmap/DebugCmdLogger.h new file mode 100644 index 00000000000..8440707d75f --- /dev/null +++ b/src/shared/vmap/DebugCmdLogger.h @@ -0,0 +1,116 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _DEBUGCMDLOGGER_H +#define _DEBUGCMDLOGGER_H + +#include <G3D/Vector3.h> +#include <G3D/Array.h> + +/** +Class is used for debugging. We log activities into a file. +With an external Class we read that log and display the activity in a graphical view. +*/ + +namespace VMAP +{ + + //========================================== + enum C_TYPES + { + STOP, + START, + LOAD_TILE, + UNLOAD_TILE, + SET_POS, + TEST_VIS, + LOAD_INSTANCE, + UNLOAD_INSTANCE, + TEST_HEIGHT, + TEST_OBJECT_HIT, + }; + + class Command + { + int iType; + float floats[9]; + int ints[4]; + char buffer[100]; + public: + + Command() { iType = STOP; } + + inline int getType() { return iType; } + inline G3D::Vector3 getVector(int pos) { return(G3D::Vector3(floats[pos*3+0], floats[pos*3+1], floats[pos*3+2])); } + inline int getInt(int pos) { return(ints[pos]); } + inline char* getBuffer() { return(buffer); } + + void fillStopCmd() { iType = STOP; } + void fillStartCmd() { iType = START; } + void fillLoadTileCmd(int x, int y, G3D::uint32 pMapId) { iType = LOAD_TILE; ints[0] = x; ints[1] = y; ints[2] = pMapId; } + //void fillLoadTileCmd(int x,int y) { iType = LOAD_TILE; ints[0] = x; ints[1] = y; } + void fillUnloadTileCmd(G3D::uint32 pMapId) { iType = UNLOAD_INSTANCE; ints[0] = pMapId; } + void fillUnloadTileCmd(unsigned int pMapId, int x,int y) { iType = UNLOAD_TILE; ints[0] = x; ints[1] = y; ints[0]=pMapId; } + void fillSetPosCmd(G3D::Vector3 pPos) { iType = SET_POS; floats[0] = pPos.x; floats[1]=pPos.y; floats[2]=pPos.z; } + void fillTestVisCmd(int pMapId, G3D::Vector3 pPos1, G3D::Vector3 pPos2, bool result) + { + iType = TEST_VIS; floats[0] = pPos1.x; floats[1]=pPos1.y; floats[2]=pPos1.z; + floats[3] = pPos2.x; floats[4]=pPos2.y; floats[5]=pPos2.z; + ints[0] = result; ints[1] = pMapId; + } + void fillTestHeightCmd(int pMapId, G3D::Vector3 pPos, float result) + { + iType = TEST_HEIGHT; floats[0] = pPos.x; floats[1]=pPos.y; floats[2]=pPos.z; + floats[3] = result; ints[0] = pMapId; + } + void fillTestObjectHitCmd(int pMapId, G3D::Vector3 pPos1, G3D::Vector3 pPos2, G3D::Vector3 pResultPos, bool result) + { + iType = TEST_OBJECT_HIT; floats[0] = pPos1.x; floats[1]=pPos1.y; floats[2]=pPos1.z; + floats[3] = pPos2.x; floats[4]=pPos2.y; floats[5]=pPos2.z; + floats[6] = pResultPos.x; floats[7]=pResultPos.y; floats[8]=pResultPos.z; + ints[0] = result; ints[1] = pMapId; + } + + bool isCoreCmd() const { return(iType != TEST_VIS); } + }; + + //========================================== + + class CommandFileRW + { + private: + std::string iFileName; + long iLastPos; + G3D::Array<G3D::Array<Command> > iCommandArray; + bool resetfile; + bool iWritingEnabled; + public: + CommandFileRW() { iLastPos=0; iWritingEnabled = true; resetfile = true;} + CommandFileRW(const std::string& pFileName) { iLastPos = 0; iFileName = pFileName; iWritingEnabled = true; resetfile = true; } + void setResetFile() { resetfile = true; } + void enableWriting(bool pValue) { iWritingEnabled = pValue; } + void setFileName(const std::string& pName) { iFileName = pName; } + bool getNewCommands(G3D::Array<Command>& commandArray); + const G3D::Array<G3D::Array<Command> >& getFullCommandArray() { return iCommandArray; } + + bool appendCmd(const Command& pCommand); + bool appendCmds(const G3D::Array<Command>& pCmdArray); + }; + +} +#endif diff --git a/src/shared/vmap/IVMapManager.h b/src/shared/vmap/IVMapManager.h new file mode 100644 index 00000000000..67321f29e3d --- /dev/null +++ b/src/shared/vmap/IVMapManager.h @@ -0,0 +1,99 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _IVMAPMANAGER_H +#define _IVMAPMANAGER_H + +#include<string> + +//=========================================================== + +/** +This is the minimum interface to the VMapMamager. +*/ + +namespace VMAP +{ + + enum VMAP_LOAD_RESULT + { + VMAP_LOAD_RESULT_ERROR, + VMAP_LOAD_RESULT_OK, + VMAP_LOAD_RESULT_IGNORED, + }; + + #define VMAP_INVALID_HEIGHT -100000.0f // for check + #define VMAP_INVALID_HEIGHT_VALUE -200000.0f // real assigned value in unknown height case + + //=========================================================== + class IVMapManager + { + private: + bool iEnableLineOfSightCalc; + bool iEnableHeightCalc; + + public: + IVMapManager() : iEnableLineOfSightCalc(true), iEnableHeightCalc(true) {} + + virtual ~IVMapManager(void) {} + + virtual int loadMap(const char* pBasePath, unsigned int pMapId, int x, int y) = 0; + + virtual bool existsMap(const char* pBasePath, unsigned int pMapId, int x, int y) = 0; + + virtual void unloadMap(unsigned int pMapId, int x, int y) = 0; + virtual void unloadMap(unsigned int pMapId) = 0; + + virtual bool isInLineOfSight(unsigned int pMapId, float x1, float y1, float z1, float x2, float y2, float z2) = 0; + virtual float getHeight(unsigned int pMapId, float x, float y, float z) = 0; + /** + test if we hit an object. return true if we hit one. rx,ry,rz will hold the hit position or the dest position, if no intersection was found + return a position, that is pReduceDist closer to the origin + */ + virtual bool getObjectHitPos(unsigned int pMapId, float x1, float y1, float z1, float x2, float y2, float z2, float& rx, float &ry, float& rz, float pModifyDist) = 0; + /** + send debug commands + */ + virtual bool processCommand(char *pCommand)= 0; + + /** + Enable/disable LOS calculation + It is enabled by default. If it is enabled in mid game the maps have to loaded manualy + */ + void setEnableLineOfSightCalc(bool pVal) { iEnableLineOfSightCalc = pVal; } + /** + Enable/disable model height calculation + It is enabled by default. If it is enabled in mid game the maps have to loaded manualy + */ + void setEnableHeightCalc(bool pVal) { iEnableHeightCalc = pVal; } + + bool isLineOfSightCalcEnabled() const { return(iEnableLineOfSightCalc); } + bool isHeightCalcEnabled() const { return(iEnableHeightCalc); } + bool isMapLoadingEnabled() const { return(iEnableLineOfSightCalc || iEnableHeightCalc ); } + + virtual std::string getDirFileName(unsigned int pMapId, int x, int y) const =0; + /** + Block maps from being used. + parameter: String of map ids. Delimiter = "," + e.g.: "0,1,530" + */ + virtual void preventMapsFromBeingUsed(const char* pMapIdString) =0; + }; + +} +#endif diff --git a/src/shared/vmap/Makefile.am b/src/shared/vmap/Makefile.am new file mode 100644 index 00000000000..322c94bfad1 --- /dev/null +++ b/src/shared/vmap/Makefile.am @@ -0,0 +1,54 @@ +# Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> +# +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software +# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +## Process this file with automake to produce Makefile.in + +noinst_LIBRARIES = libvmaps.a + +## Preprocessor flags +libvmaps_a_CPPFLAGS = \ +-I$(top_srcdir)/dep/include \ +-I$(top_srcdir)/dep/include/g3dlite + +libvmaps_a_SOURCES = \ +$(srcdir)/AABSPTree.h \ +$(srcdir)/BaseModel.cpp \ +$(srcdir)/BaseModel.h \ +$(srcdir)/CoordModelMapping.cpp \ +$(srcdir)/CoordModelMapping.h \ +$(srcdir)/DebugCmdLogger.cpp \ +$(srcdir)/DebugCmdLogger.h \ +$(srcdir)/IVMapManager.h \ +$(srcdir)/ManagedModelContainer.cpp \ +$(srcdir)/ManagedModelContainer.h \ +$(srcdir)/ModelContainer.cpp \ +$(srcdir)/ModelContainer.h \ +$(srcdir)/NodeValueAccess.h \ +$(srcdir)/ShortBox.h \ +$(srcdir)/ShortVector.h \ +$(srcdir)/SubModel.cpp \ +$(srcdir)/SubModel.h \ +$(srcdir)/TileAssembler.cpp \ +$(srcdir)/TileAssembler.h \ +$(srcdir)/TreeNode.cpp \ +$(srcdir)/TreeNode.h \ +$(srcdir)/VMapDefinitions.h \ +$(srcdir)/VMapFactory.cpp \ +$(srcdir)/VMapFactory.h \ +$(srcdir)/VMapManager.cpp \ +$(srcdir)/VMapManager.h \ +$(srcdir)/VMapTools.h + diff --git a/src/shared/vmap/ManagedModelContainer.cpp b/src/shared/vmap/ManagedModelContainer.cpp new file mode 100644 index 00000000000..bc3ba5ba3ec --- /dev/null +++ b/src/shared/vmap/ManagedModelContainer.cpp @@ -0,0 +1,35 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "ManagedModelContainer.h" + +using namespace G3D; + +namespace VMAP +{ + + ManagedModelContainer::ManagedModelContainer(void) : ModelContainer() + { + refCount = 0; + } + + ManagedModelContainer::~ManagedModelContainer(void) + { + } + +} diff --git a/src/shared/vmap/ManagedModelContainer.h b/src/shared/vmap/ManagedModelContainer.h new file mode 100644 index 00000000000..9766813d66c --- /dev/null +++ b/src/shared/vmap/ManagedModelContainer.h @@ -0,0 +1,49 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _MANAGEDMODELCONTAINER_H +#define _MANAGEDMODELCONTAINER_H + +#include "ModelContainer.h" + +//======================================================= +/** +This is a ModelContainer with reference count information. +*/ + +namespace VMAP +{ + //======================================================= + + class ManagedModelContainer : + public ModelContainer + { + private: + int refCount; + public: + ManagedModelContainer(void) ; + ~ManagedModelContainer(void); + + void incRefCount() { ++refCount; } + void decRefCount() { --refCount; if(refCount < 0) refCount = 0; } + int getRefCount() { return refCount; } + }; + + //======================================================= +} +#endif diff --git a/src/shared/vmap/ModelContainer.cpp b/src/shared/vmap/ModelContainer.cpp new file mode 100644 index 00000000000..43a947b12dd --- /dev/null +++ b/src/shared/vmap/ModelContainer.cpp @@ -0,0 +1,375 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include <iostream> +#include <fstream> + +#include <string.h> + +#include "ModelContainer.h" +#include "VMapDefinitions.h" + +using namespace G3D; + +namespace VMAP +{ + //========================================================== + /** + Functions to use ModelContainer with a AABSPTree + */ + size_t hashCode(const ModelContainer& pMc) + { + return (pMc.getBasePosition() * pMc.getNTriangles()).hashCode(); + } + //========================================================== + + ModelContainer::ModelContainer(unsigned int pNTriangles, unsigned int pNNodes, unsigned int pNSubModel) : + BaseModel(pNNodes, pNTriangles) + { + + iNSubModel = pNSubModel; + iSubModel = 0; + if(pNSubModel > 0) iSubModel = new SubModel[iNSubModel]; + } + + //========================================================== + + bool ModelContainer::operator==(const ModelContainer& pMc2) const + { + if (this->iNSubModel == 0 && pMc2.iNSubModel == 0 && this->iSubModel == 0 && pMc2.iSubModel == 0) + return true; + return this == &pMc2; + } + + //========================================================== + + void ModelContainer::countSubModelsAndNodesAndTriangles(AABSPTree<SubModel *>::Node& pNode, int& nSubModels, int& nNodes, int& nTriangles) + { + // For this node we will need a TreeNode as well as for the internal nodes + ++nNodes; + + nSubModels += pNode.valueArray.size(); + for(int i=0;i<pNode.valueArray.size(); i++) + { + G3D::_AABSPTree::Handle<SubModel*>* h= pNode.valueArray[i]; + SubModel *m = h->value; + // add the internal nodes as well + nNodes += m->getNNodes(); + nTriangles += m->getNTriangles(); + } + + if(pNode.child[0] != 0) + { + countSubModelsAndNodesAndTriangles(*pNode.child[0], nSubModels, nNodes, nTriangles); + } + if(pNode.child[1] != 0) + { + countSubModelsAndNodesAndTriangles(*pNode.child[1], nSubModels, nNodes, nTriangles); + } + } + //========================================================== + + void ModelContainer::fillContainer(const AABSPTree<SubModel *>::Node& pNode, int &pSubModelPos, int &pTreeNodePos, int &pTrianglePos, Vector3& pLo, Vector3& pHi, Vector3& pFinalLo, Vector3& pFinalHi) + { + // TreeNode for the SubModel + TreeNode treeNode = TreeNode(pNode.valueArray.size(), pSubModelPos); + treeNode.setSplitAxis(pNode.splitAxis); + treeNode.setSplitLocation(pNode.splitLocation); + int currentTreeNodePos = pTreeNodePos++; + + Vector3 lo = Vector3(inf(),inf(),inf()); + Vector3 hi = Vector3(-inf(),-inf(),-inf()); + + for(int i=0;i<pNode.valueArray.size(); i++) + { + G3D::_AABSPTree::Handle<SubModel*>* h= pNode.valueArray[i]; + SubModel *m = h->value; + + memcpy(&getTreeNodes()[pTreeNodePos], &m->getTreeNode(0), sizeof(TreeNode) * m->getNNodes()); + memcpy(&getTriangles()[pTrianglePos], &m->getTriangle(0), sizeof(TriangleBox) * m->getNTriangles()); + + SubModel newModel = SubModel(m->getNTriangles(), getTriangles(), pTrianglePos, m->getNNodes(), getTreeNodes(), pTreeNodePos); + newModel.setReletiveBounds(m->getReletiveBounds().getLo(), m->getReletiveBounds().getHi()); + newModel.setBasePosition(m->getBasePosition()); + iSubModel[pSubModelPos++] = newModel; + + pTreeNodePos += m->getNNodes(); + pTrianglePos += m->getNTriangles(); + + AABox box = m->getAABoxBounds(); + lo = lo.min(box.low()); + hi = hi.max(box.high()); + pFinalLo = pFinalLo.min(lo); + pFinalHi = pFinalHi.max(hi); + } + /* + if(pNode.valueArray.size() == 0) { + int xxx = 0; // just for the breakpoint + } + */ + // get absolute bounds + + if(pNode.child[0] != 0) + { + treeNode.setChildPos(0, pTreeNodePos); + fillContainer(*pNode.child[0], pSubModelPos, pTreeNodePos, pTrianglePos, lo, hi,pFinalLo,pFinalHi); + } + if(pNode.child[1] != 0) + { + treeNode.setChildPos(1, pTreeNodePos); + fillContainer(*pNode.child[1], pSubModelPos, pTreeNodePos, pTrianglePos, lo, hi,pFinalLo,pFinalHi); + } + + pLo = pLo.min(lo); + pHi = pHi.max(hi); + + treeNode.setBounds(lo,hi); + + setTreeNode(treeNode, currentTreeNodePos); + + } + + //========================================================== + /** + Create the structure out of a AABSPTree + */ + + ModelContainer::ModelContainer(AABSPTree<SubModel *> *pTree) + { + + int nSubModels, nNodes, nTriangles; + nSubModels = nNodes = nTriangles = 0; + countSubModelsAndNodesAndTriangles(*pTree->root, nSubModels, nNodes, nTriangles); + + init(nNodes, nTriangles); + + iNSubModel = nSubModels; + + iSubModel = new SubModel[iNSubModel]; + + int subModelPos,treeNodePos, trianglePos; + subModelPos = treeNodePos = trianglePos = 0; + + Vector3 lo = Vector3(inf(),inf(),inf()); + Vector3 hi = Vector3(-inf(),-inf(),-inf()); + Vector3 finalLo, finalHi; + finalLo = lo; + finalHi = hi; + + fillContainer(*pTree->root, subModelPos, treeNodePos, trianglePos, lo, hi, finalLo, finalHi); + setBounds(finalLo, finalHi); + } + + //========================================================== + + ModelContainer::~ModelContainer(void) + { + free(); + if(iSubModel != 0) delete [] iSubModel; + } + //========================================================== + + bool ModelContainer::writeFile(const char *filename) + { + bool result = false; + unsigned int flags=0; + unsigned int size; + + FILE *wf =fopen(filename,"wb"); + if(wf) + { + fwrite(VMAP_MAGIC,1,8,wf); + result = true; + if(result && fwrite("CTREE01",8,1,wf) != 1) result = false; + if(result && fwrite(&flags,sizeof(unsigned int),1,wf) != 1) result = false; + + if(result && fwrite("POS ",4,1,wf) != 1) result = false; + size = sizeof(float)*3; + if(result && fwrite(&size,4,1,wf) != 1) result = false; + Vector3 basePos = getBasePosition(); + if(result && fwrite(&basePos,sizeof(float),3,wf) != 3) result = false; + + if(result && fwrite("BOX ",4,1,wf) != 1) result = false; + size = sizeof(float)*6; + if(result && fwrite(&size,4,1,wf) != 1) result = false; + Vector3 low = iBox.low(); + if(result && fwrite(&low,sizeof(float),3,wf) != 3) result = false; + Vector3 high = iBox.high(); + if(result && fwrite(&high,sizeof(float),3,wf) != 3) result = false; + + if(result && fwrite("NODE",4,1,wf) != 1) result = false; + size = sizeof(unsigned int)+ sizeof(TreeNode)*getNNodes(); + if(result && fwrite(&size,4,1,wf) != 1) result = false; + unsigned int val = getNNodes(); + if(result && fwrite(&val,sizeof(unsigned int),1,wf) != 1) result = false; + if(result && fwrite(getTreeNodes(),sizeof(TreeNode),getNNodes(),wf) != getNNodes()) result = false; + + if(result && fwrite("TRIB",4,1,wf) != 1) result = false; + size = sizeof(unsigned int)+ sizeof(TriangleBox)*getNTriangles(); + if(result && fwrite(&size,4,1,wf) != 1) result = false; + val = getNTriangles(); + if(result && fwrite(&val,sizeof(unsigned int),1,wf) != 1) result = false; + if(result && fwrite(getTriangles(),sizeof(TriangleBox),getNTriangles(),wf) != getNTriangles()) result = false; + + if(result && fwrite("SUBM",4,1,wf) != 1) result = false; + size = sizeof(unsigned int)+ sizeof(SubModel)*iNSubModel; + if(result && fwrite(&size,4,1,wf) != 1) result = false; + if(result && fwrite(&iNSubModel,sizeof(unsigned int),1,wf) != 1) result = false; + if(result && fwrite(iSubModel,sizeof(SubModel),iNSubModel,wf) != iNSubModel) result = false; + + fclose(wf); + } + + return(result); + } + + //=============================================================== + + bool ModelContainer::readFile(const char *filename) + { + bool result = false; + unsigned int flags; + unsigned int size; + char ident[8]; + char chunk[4]; + unsigned int ival; + FILE *rf = fopen(filename, "rb"); + if(rf) + { + free(); + + result = true; + char magic[8]; // Ignore the added magic header + fread(magic,1,8,rf); + if(strncmp(VMAP_MAGIC,magic,8)) result = false; + if(result && fread(ident,8,1,rf) != 1) result = false; + if(result && fread(&flags,sizeof(unsigned int),1,rf) != 1) result = false; + //POS + if(result && fread(chunk,4,1,rf) != 1) result = false; + if(result && fread(&size,4,1,rf) != 1) result = false; + Vector3 basePos; + if(result && fread(&basePos,sizeof(float),3,rf) != 3) result = false; + setBasePosition(basePos); + + //---- Box + if(result && fread(chunk,4,1,rf) != 1) result = false; + if(result && fread(&size,4,1,rf) != 1) result = false; + Vector3 low,high; + if(result && fread(&low,sizeof(float),3,rf) != 3) result = false; + if(result && fread(&high,sizeof(float),3,rf) != 3) result = false; + setBounds(low, high); + + //---- TreeNodes + if(result && fread(chunk,4,1,rf) != 1) result = false; + if(result && fread(&size,4,1,rf) != 1) result = false; + + if(result && fread(&ival,sizeof(unsigned int),1,rf) != 1) result = false; + if(result) setNNodes(ival); + if(result) setTreeNodeArray(new TreeNode[getNNodes()]); + if(result && fread(getTreeNodes(),sizeof(TreeNode),getNNodes(),rf) != getNNodes()) result = false; + + //---- TriangleBoxes + if(result && fread(chunk,4,1,rf) != 1) result = false; + if(result && fread(&size,4,1,rf) != 1) result = false; + + if(result && fread(&ival,sizeof(unsigned int),1,rf) != 1) result = false; + setNTriangles(ival); + if(result) setTriangleArray(new TriangleBox[getNTriangles()]); + if(result && fread(getTriangles(),sizeof(TriangleBox),getNTriangles(),rf) != getNTriangles()) result = false; + + //---- SubModel + if(result && fread(chunk,4,1,rf) != 1) result = false; + if(result && fread(&size,4,1,rf) != 1) result = false; + + if(result && fread(&iNSubModel,sizeof(unsigned int),1,rf) != 1) result = false; + if(result) iSubModel = new SubModel[iNSubModel]; + + if(result) + { + for(unsigned int i=0;i<iNSubModel && result; ++i) + { + unsigned char readBuffer[52]; // this is the size of SubModel on 32 bit systems + if(fread(readBuffer,sizeof(readBuffer),1,rf) != 1) result = false; + iSubModel[i].initFromBinBlock(readBuffer); + iSubModel[i].setTriangleArray(getTriangles()); + iSubModel[i].setTreeNodeArray(getTreeNodes()); + } + } + fclose(rf); + } + return result; + } + + //================================================================= + + size_t ModelContainer::getMemUsage() + { + // BaseModel is included in ModelContainer + return(iNSubModel * sizeof(SubModel) + BaseModel::getMemUsage() + sizeof(ModelContainer) - sizeof(BaseModel)); + } + + //================================================================= +#ifdef _DEBUG_VMAPS +#ifndef gBoxArray + extern Vector3 p1,p2,p3,p4,p5,p6,p7; + extern Array<AABox>gBoxArray; + extern int gCount1, gCount2, gCount3, gCount4; + extern bool myfound; +#endif +#endif + + void ModelContainer::intersect(const G3D::Ray& pRay, float& pMaxDist, bool pStopAtFirstHit, G3D::Vector3& /*pOutLocation*/, G3D::Vector3& /*pOutNormal*/) const + { + IntersectionCallBack<SubModel> intersectCallback; + NodeValueAccess<TreeNode, SubModel> vna = NodeValueAccess<TreeNode, SubModel>(getTreeNodes(), iSubModel); + Ray relativeRay = Ray::fromOriginAndDirection(pRay.origin - getBasePosition(), pRay.direction); + iTreeNodes[0].intersectRay(pRay, intersectCallback, pMaxDist, vna, pStopAtFirstHit, false); + } + + //========================================================== + + bool ModelContainer::intersect(const G3D::Ray& pRay, float& pMaxDist) const + { + return BaseModel::intersect(getAABoxBounds(), pRay, pMaxDist); + } + + //================================================================= + + template<typename RayCallback> + void ModelContainer::intersectRay(const G3D::Ray& pRay, RayCallback& intersectCallback, float& pMaxDist, bool pStopAtFirstHit, bool intersectCallbackIsFast) + { + if(intersect(pRay, pMaxDist)) + { + NodeValueAccess<TreeNode, SubModel> vna = NodeValueAccess<TreeNode, SubModel>(getTreeNodes(), iSubModel); + iTreeNodes[0].intersectRay(pRay, intersectCallback, distance, vna, pStopAtFirstHit, true); + } + } + //================================================================= + void getBounds(const ModelContainer& pMc, G3D::AABox& pAABox) + { + pAABox = pMc.getAABoxBounds(); + } + + //================================================================= + + void getBounds(const ModelContainer* pMc, G3D::AABox& pAABox) + { + pAABox = pMc->getAABoxBounds(); + } + //================================================================= +} // VMAP diff --git a/src/shared/vmap/ModelContainer.h b/src/shared/vmap/ModelContainer.h new file mode 100644 index 00000000000..636be1713b4 --- /dev/null +++ b/src/shared/vmap/ModelContainer.h @@ -0,0 +1,108 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _MODELCONTAINER_H +#define _MODELCONTAINER_H + +// load our modified version first !! +#include "AABSPTree.h" + +#include <G3D/AABox.h> +#include <G3D/Vector3.h> +#include <G3D/Ray.h> + +#include "ShortBox.h" +#include "TreeNode.h" +#include "VMapTools.h" +#include "SubModel.h" +#include "BaseModel.h" + +namespace VMAP +{ + /** + The ModelContainer is a balanced BSP-Tree of SubModels. + We store a map tile or an instance in one ModelContainer. + The ModelContainer manages the memory used for the tree nodes, the SubModels and its triangles in static arrays. + The tree nodes are used for the BSP-Tree of SubModels as well as for the BSP-Tree of triangles within one SubModel. + The references are done by indexes within these static arrays. + Therefore we are able to just load a binary block and do not need to mess around with memory allocation and pointers. + */ + + //===================================================== + + class ModelContainer : public BaseModel + { + private: + unsigned int iNSubModel; + SubModel *iSubModel; + G3D::AABox iBox; + + ModelContainer (const ModelContainer& c): BaseModel(c) {} + ModelContainer& operator=(const ModelContainer& ) {} + + public: + ModelContainer() : BaseModel() { iNSubModel =0; iSubModel = 0; }; + + // for the mainnode + ModelContainer(unsigned int pNTriangles, unsigned int pNNodes, unsigned int pNSubModel); + + ModelContainer(G3D::AABSPTree<SubModel *> *pTree); + + ~ModelContainer(void); + + inline const void setSubModel(const SubModel& pSubModel, int pPos) { iSubModel[pPos] = pSubModel; } + + inline const SubModel& getSubModel(int pPos) const { return iSubModel[pPos]; } + + inline unsigned int getNSubModel() const { return(iNSubModel); } + + void countSubModelsAndNodesAndTriangles(G3D::AABSPTree<SubModel *>::Node& pNode, int& nSubModels, int& nNodes, int& nTriangles); + + void fillContainer(const G3D::AABSPTree<SubModel *>::Node& pNode, int &pSubModelPos, int &pTreeNodePos, int &pTrianglePos, G3D::Vector3& pLo, G3D::Vector3& pHi, G3D::Vector3& pFinalLo, G3D::Vector3& pFinalHi); + + bool readRawFile(const char *name); + + inline const G3D::AABox& getAABoxBounds() const { return(iBox); } + + inline void setBounds(const G3D::Vector3& lo, const G3D::Vector3& hi) { iBox.set(lo,hi); } + + bool writeFile(const char *filename); + + bool readFile(const char *filename); + + size_t getMemUsage(); + size_t hashCode() { return (getBasePosition() * getNTriangles()).hashCode(); } + + void intersect(const G3D::Ray& pRay, float& pMaxDist, bool pStopAtFirstHit, G3D::Vector3& pOutLocation, G3D::Vector3& pOutNormal) const; + bool intersect(const G3D::Ray& pRay, float& pMaxDist) const; + + template<typename RayCallback> + void intersectRay(const G3D::Ray& ray, RayCallback& intersectCallback, float& distance, bool pStopAtFirstHit, bool intersectCallbackIsFast = false); + + bool operator==(const ModelContainer& pMc2) const; + }; + + //===================================================== + + //===================================================== + + size_t hashCode(const ModelContainer& pMc); + void getBounds(const ModelContainer& pMc, G3D::AABox& pAABox); + void getBounds(const ModelContainer* pMc, G3D::AABox& pAABox); +} +#endif diff --git a/src/shared/vmap/NodeValueAccess.h b/src/shared/vmap/NodeValueAccess.h new file mode 100644 index 00000000000..fb7a771baf0 --- /dev/null +++ b/src/shared/vmap/NodeValueAccess.h @@ -0,0 +1,48 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _NODEVALUEACCESS_H +#define _NODEVALUEACCESS_H + +namespace VMAP +{ + /** + This is a helper Class to get access to SubModels or triangles when analyzing the BSP-Tree. + */ + + template<class TNode, class TValue> class NodeValueAccess + { + private: + TNode const* iNodeArray; + TValue const* iValueArray; + + public: + inline NodeValueAccess() : iNodeArray(NULL), iValueArray(NULL) {} + + inline NodeValueAccess(TNode const* pNodeArray, TValue const* pValueArray) : iNodeArray(pNodeArray), iValueArray(pValueArray) {} + inline TNode const* getNodePtr() const { return(iNodeArray); } + inline TValue const* getValuePtr() const { return(iValueArray); } + + inline TNode const& getNode(unsigned int pPos) const { return(iNodeArray[pPos]); } + inline void setNode(const TNode& pNode, unsigned int pPos) { iNodeArray[pPos] = pNode; } + + inline TValue const& getValue(unsigned int pPos) const { return(iValueArray[pPos]); } + inline void setValue(const TValue& pValue, unsigned int pPos) { iValueArray[pPos] = pValue; } + }; +} +#endif diff --git a/src/shared/vmap/ShortBox.h b/src/shared/vmap/ShortBox.h new file mode 100644 index 00000000000..d43bc61caa7 --- /dev/null +++ b/src/shared/vmap/ShortBox.h @@ -0,0 +1,148 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _SHORTBOX_H +#define _SHORTBOX_H + +#include <G3D/Vector3.h> +#include <G3D/AABox.h> +#include <G3D/Triangle.h> +#include <G3D/Ray.h> + +#include "ShortVector.h" + +/** +This is a box and a triangle Class using ShortVectors. Each vector has 16 bit an a fixed point 12.4 representation. +*/ + +namespace VMAP +{ + + class ShortBox + { + private: + ShortVector iV1; + ShortVector iV2; + public: + ShortBox() {} + inline const ShortVector& getLo() const { return(iV1); } + inline const ShortVector& getHi() const { return(iV2); } + inline void setLo(const ShortVector& pV){ iV1 = pV; } + inline void setHi(const ShortVector& pV){ iV2 = pV; } + inline void setLo(const G3D::Vector3& pV){ iV1 = ShortVector(pV); } + inline void setHi(const G3D::Vector3& pV){ iV2 = ShortVector(pV); } + + inline bool operator==(const ShortBox& b) const + { + return ((iV1 == b.iV1) && (iV2 == b.iV2)); + } + + inline bool operator!=(const ShortBox& b) const + { + return !((iV1 == b.iV1) && (iV2 == b.iV2)); + } + }; + + //===================================================================== +#ifdef _DEBUG_VMAPS +#ifndef gBoxArray + extern G3D::Vector3 p1,p2,p3,p4,p5,p6,p7; + extern G3D::Array<G3D::AABox>gBoxArray; + extern G3D::Array<G3D::Triangle>gTriArray; + extern int gCount1, gCount2, gCount3, gCount4; + extern bool myfound; +#endif +#endif + + static const G3D::Vector3 dummyZeroPosition = G3D::Vector3(0,0,0); + + class TriangleBox + { + private: + ShortVector _vertex[3]; + //ShortBox iBox; + public: + inline TriangleBox() { } + inline TriangleBox(const ShortVector& pV1, const ShortVector& pV2, const ShortVector& pV3) + { + _vertex[0] = pV1; + _vertex[1] = pV2; + _vertex[2] = pV3; + + } + inline const ShortVector& vertex (int n) const + { + return(_vertex[n]); + } + + inline const ShortBox getBounds()const + { + ShortBox box; + + ShortVector lo = _vertex[0]; + ShortVector hi = lo; + + for (int i = 1; i < 3; ++i) + { + lo = lo.min(_vertex[i]); + hi = hi.max(_vertex[i]); + } + box.setLo(lo); + box.setHi(hi); + return(box); + } + inline const G3D::Vector3& getBasePosition() { return(dummyZeroPosition); } + + inline const G3D::AABox getAABoxBounds() const { ShortBox box = getBounds(); return(G3D::AABox(box.getLo().getVector3(), box.getHi().getVector3())); } + + inline bool operator==(const TriangleBox& t) const + { + return ((_vertex[0] == t._vertex[0]) && (_vertex[1] == t._vertex[1]) &&(_vertex[2] == t._vertex[2])); + } + + inline bool operator!=(const TriangleBox& t) const + { + return !((_vertex[0] == t._vertex[0]) && (_vertex[1] == t._vertex[1]) &&(_vertex[2] == t._vertex[2])); + } + + inline void intersect(const G3D::Ray& pRay, float& pMaxDist, bool /*pStopAtFirstHitDummy*/, G3D::Vector3& /*pOutLocationDummy*/, G3D::Vector3& /*pOutNormalDummy*/) const + { + static const double epsilon = 0.00001; + G3D::Triangle testT(vertex(0).getVector3(),vertex(1).getVector3(),vertex(2).getVector3()); + float t = pRay.intersectionTime(testT); + if ((t < pMaxDist) || t < (pMaxDist + epsilon)) + pMaxDist = t; + else + { + testT = G3D::Triangle(vertex(2).getVector3(),vertex(1).getVector3(),vertex(0).getVector3()); + +#ifdef _DEBUG_VMAPS + { + G3D::Triangle myt(testT.vertex(0)+p6, testT.vertex(1)+p6,testT.vertex(2)+p6); + gTriArray.push_back(myt); + } +#endif + t = pRay.intersectionTime(testT); + if ((t < pMaxDist) || t < (pMaxDist + epsilon)) + pMaxDist = t; + } + } + }; + +} +#endif diff --git a/src/shared/vmap/ShortVector.h b/src/shared/vmap/ShortVector.h new file mode 100644 index 00000000000..642f5b53c1b --- /dev/null +++ b/src/shared/vmap/ShortVector.h @@ -0,0 +1,134 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _SHORTVECTOR_H +#define _SHORTVECTOR_H + +#include <G3D/Vector3.h> + +namespace VMAP +{ + /** + Vector with 16 bit fix point values 12.4 bit. + */ + + class ShortVector + { + private: + short iX; + short iY; + short iZ; + + const static short maxvalue = 0x7fff; + const static short minvalue = -0x7fff; + const static int fixpointdiv = 16; + const static short fixpoint_maxvalue = maxvalue / fixpointdiv; + const static short fixpoint_minvalue = minvalue / fixpointdiv; + + inline short float2Short(float fv) const + { + short sv; + debugAssert((fv <= fixpoint_maxvalue || fv >= 1000000) && (fv >= fixpoint_minvalue || fv <= -1000000)); + if(fv >= fixpoint_maxvalue) + sv=maxvalue; + else if(fv <= fixpoint_minvalue) + sv=minvalue; + else + sv = (short) (fv * fixpointdiv + 0.5); + return(sv); + } + inline float short2Float(short sv) const + { + float fv; + if(sv >= maxvalue) + fv=G3D::inf(); + else if(sv <= minvalue) + fv=-G3D::inf(); + else + fv = ((float)sv) / fixpointdiv; + return fv; + } + + inline float getFX() const { return(short2Float(iX)); } + inline float getFY() const { return(short2Float(iY)); } + inline float getFZ() const { return(short2Float(iZ)); } + public: + inline ShortVector() {} + inline ShortVector(const G3D::Vector3& pVector) + { + iX = float2Short(pVector.x); + iY = float2Short(pVector.y); + iZ = float2Short(pVector.z); + } + + inline ShortVector(float pX, float pY, float pZ) + { + iX = float2Short(pX); + iY = float2Short(pY); + iZ = float2Short(pZ); + } + inline ShortVector(short pX, short pY, short pZ) + { + iX = pX; + iY = pY; + iZ = pZ; + } + inline ShortVector(const ShortVector& pShortVector) + { + iX = pShortVector.iX; + iY = pShortVector.iY; + iZ = pShortVector.iZ; + } + + inline float getX() const { return(iX); } + inline float getY() const { return(iY); } + inline float getZ() const { return(iZ); } + + inline G3D::Vector3 getVector3() const { return(G3D::Vector3(getFX(), getFY(), getFZ())); } + + inline ShortVector min(const ShortVector pShortVector) + { + ShortVector result = pShortVector; + if(pShortVector.iX > iX) { result.iX = iX; } + if(pShortVector.iY > iY) { result.iY = iY; } + if(pShortVector.iZ > iZ) { result.iZ = iZ; } + return(result); + } + + inline ShortVector max(const ShortVector pShortVector) + { + ShortVector result = pShortVector; + if(pShortVector.iX < iX) { result.iX = iX; } + if(pShortVector.iY < iY) { result.iY = iY; } + if(pShortVector.iZ < iZ) { result.iZ = iZ; } + return(result); + } + + inline bool operator==(const ShortVector& v) const + { + return (iX == v.iX && iY == v.iY && iZ == v.iZ); + } + + inline bool operator!=(const ShortVector& v) const + { + return !(iX == v.iX && iY == v.iY && iZ == v.iZ); + } + + }; +} +#endif diff --git a/src/shared/vmap/SubModel.cpp b/src/shared/vmap/SubModel.cpp new file mode 100644 index 00000000000..2a46b3c6a1f --- /dev/null +++ b/src/shared/vmap/SubModel.cpp @@ -0,0 +1,248 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "SubModel.h" + +#ifdef _ASSEMBLER_DEBUG +extern FILE *::g_df; +#endif + +using namespace G3D; + +namespace VMAP +{ + + //========================================================== + /** + Functions to use ModelContainer with a AABSPTree + */ + unsigned int hashCode(const SubModel& pSm) + { + return pSm.getNTriangles(); + } + + void getBounds(const SubModel& pSm, G3D::AABox& pAABox) + { + ShortBox box = pSm.getReletiveBounds(); + pAABox.set(box.getLo().getVector3()+pSm.getBasePosition(), box.getHi().getVector3()+pSm.getBasePosition()); + } + + void getBounds(const SubModel* pSm, G3D::AABox& pAABox) + { + ShortBox box = pSm->getReletiveBounds(); + pAABox.set(box.getLo().getVector3()+pSm->getBasePosition(), box.getHi().getVector3()+pSm->getBasePosition()); + } + + //========================================================== + //========================================================== + //========================================================== + //========================================================== + SubModel::SubModel(unsigned int pNTriangles, TriangleBox *pTriangles, unsigned int pTrianglesPos, unsigned int pNNodes, TreeNode *pTreeNodes, unsigned int pNodesPos) : + BaseModel(pNNodes, pTreeNodes, pNTriangles, pTriangles) + { + iTrianglesPos = pTrianglesPos; + iNodesPos = pNodesPos; + iHasInternalMemAlloc = false; + } + + //========================================================== + + SubModel::~SubModel(void) + { + if(iHasInternalMemAlloc) + { + free(); + } + } + + //========================================================== + + bool SubModel::operator==(const SubModel& pSm2) const + { + bool result = false; + + if(getNNodes() == pSm2.getNNodes() && + getNTriangles() == pSm2.getNTriangles() && + getBasePosition() == pSm2.getBasePosition() && + getNodesPos() == pSm2.getNodesPos() && + getTrianglesPos() == pSm2.getTrianglesPos()) + { + result = true; + } + return result; + } + //========================================================== + + enum BIN_POSITIONS + { + BP_iNTriangles=8, + BP_iNNodes=12, + BP_iBasePosition=16, + BP_iNodesPos=28, + BP_iTrianglesPos=32, + BP_iHasInternalMemAlloc=36, + BP_iBox=38, + }; + /** + This is ugly, but due to compatibility and 64 bit support we have to do that ... sorry + */ + void SubModel::initFromBinBlock(void *pBinBlock) + { + iNTriangles = *((unsigned int *)(((char *) pBinBlock) + BP_iNTriangles)); + iNNodes = *((unsigned int *) (((char *) pBinBlock) + BP_iNNodes)); + iBasePosition = *((Vector3 *) (((char *) pBinBlock) + BP_iBasePosition)); + iNodesPos = *((unsigned int *) (((char *) pBinBlock) + BP_iNodesPos)); + iTrianglesPos = *((unsigned int *) (((char *) pBinBlock) + BP_iTrianglesPos)); + iHasInternalMemAlloc = *((bool *) (((char *) pBinBlock) + BP_iHasInternalMemAlloc)); + iBox = *((ShortBox *) (((char *) pBinBlock) + BP_iBox)); + } + + //========================================================== + + void SubModel::countNodesAndTriangles(AABSPTree<Triangle>::Node& pNode, int &pNNodes, int &pNTriabgles) + { + ++pNNodes; + pNTriabgles += pNode.valueArray.size(); + + #ifdef _ASSEMBLER_DEBUG + fprintf(::g_df, "Nodes: %d, Tris: %d\n",pNNodes, pNTriabgles); + #endif + + if(pNode.child[0] != 0) + { + countNodesAndTriangles(*pNode.child[0], pNNodes, pNTriabgles); + } + if(pNode.child[1] != 0) + { + countNodesAndTriangles(*pNode.child[1], pNNodes, pNTriabgles); + } + } + + //========================================================== + + void SubModel::fillContainer(const AABSPTree<Triangle>::Node& pNode, int &pTreeNodePos, int &pTrianglePos, Vector3& pLo, Vector3& pHi) + { + TreeNode treeNode = TreeNode(pNode.valueArray.size(), pTrianglePos); + treeNode.setSplitAxis(pNode.splitAxis); + treeNode.setSplitLocation(pNode.splitLocation); + + int currentTreeNodePos = pTreeNodePos++; + + Vector3 lo = Vector3(inf(),inf(),inf()); + Vector3 hi = Vector3(-inf(),-inf(),-inf()); + + for(int i=0;i<pNode.valueArray.size(); i++) + { + G3D::_AABSPTree::Handle<Triangle>* h= pNode.valueArray[i]; + Triangle t = h->value; + TriangleBox triangleBox = TriangleBox(t.vertex(0),t.vertex(1), t.vertex(2)); + lo = lo.min(triangleBox.getBounds().getLo().getVector3()); + hi = hi.max(triangleBox.getBounds().getHi().getVector3()); + + getTriangles()[pTrianglePos++] = triangleBox; + } + + if(pNode.child[0] != 0) + { + treeNode.setChildPos(0, pTreeNodePos); + fillContainer(*pNode.child[0], pTreeNodePos, pTrianglePos, lo, hi); + } + if(pNode.child[1] != 0) + { + treeNode.setChildPos(1, pTreeNodePos); + fillContainer(*pNode.child[1], pTreeNodePos, pTrianglePos, lo, hi); + } + + treeNode.setBounds(lo,hi); + + // get absolute bounds + pLo = pLo.min(lo); + pHi = pHi.max(hi); + + getTreeNodes()[currentTreeNodePos] = treeNode; + } + + //========================================================== + + SubModel::SubModel(AABSPTree<Triangle> *pTree) + { + int nNodes, nTriangles; + nNodes = nTriangles = 0; + countNodesAndTriangles(*pTree->root, nNodes, nTriangles); + + init(nNodes, nTriangles); + + iTrianglesPos = 0; // this is the global array + iNodesPos = 0; // this is the global array + iHasInternalMemAlloc = true; + int treeNodePos, trianglePos; + treeNodePos = trianglePos = 0; + + Vector3 lo = Vector3(inf(),inf(),inf()); + Vector3 hi = Vector3(-inf(),-inf(),-inf()); + + fillContainer(*pTree->root, treeNodePos, trianglePos, lo, hi); + setReletiveBounds(lo, hi); + } + + //========================================================== +#ifdef _DEBUG_VMAPS +#ifndef gBoxArray + extern Vector3 p1,p2,p3,p4,p5,p6,p7; + extern Array<AABox>gBoxArray; + extern Array<G3D::Triangle>gTriArray; + extern int gCount1, gCount2, gCount3, gCount4; + extern bool myfound; +#endif +#endif + + //========================================================== + void SubModel::intersect(const G3D::Ray& pRay, float& pMaxDist, bool pStopAtFirstHit, G3D::Vector3& /*pOutLocation*/, G3D::Vector3& /*pOutNormal*/) const + { + NodeValueAccess<TreeNode, TriangleBox> vna = NodeValueAccess<TreeNode, TriangleBox>(getTreeNodes(), getTriangles()); + IntersectionCallBack<TriangleBox> intersectCallback; + Ray relativeRay = Ray::fromOriginAndDirection(pRay.origin - getBasePosition(), pRay.direction); +#ifdef _DEBUG_VMAPS + //p6=getBasePosition(); + //gBoxArray.push_back(getAABoxBounds()); +#endif + getTreeNode(0).intersectRay(relativeRay, intersectCallback, pMaxDist, vna, pStopAtFirstHit, false); + } + + //========================================================== + + bool SubModel::intersect(const G3D::Ray& pRay, float& pMaxDist) const + { + return BaseModel::intersect(getAABoxBounds(), pRay, pMaxDist); + } + + //========================================================== + + template<typename RayCallback> + void SubModel::intersectRay(const Ray& pRay, RayCallback& pIntersectCallback, float& pMaxDist, bool pStopAtFirstHit, bool intersectCallbackIsFast) + { + if(intersect(pRay, pMaxDist)) + { + NodeValueAccess<TreeNode, TriangleBox> vna = NodeValueAccess<TreeNode, TriangleBox>(getTreeNodes(), getTriangles()); + IntersectionCallBack<TriangleBox> intersectCallback; + getTreeNode(0).intersectRay(pRay, intersectCallback, pMaxDist, vna, pStopAtFirstHit, false); + } + } + //========================================================== + +} diff --git a/src/shared/vmap/SubModel.h b/src/shared/vmap/SubModel.h new file mode 100644 index 00000000000..d72b603e298 --- /dev/null +++ b/src/shared/vmap/SubModel.h @@ -0,0 +1,102 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _SUBMODEL_H +#define _SUBMODEL_H + +// load our modified version first !! +#include "AABSPTree.h" + +#include "ShortVector.h" +#include "ShortBox.h" +#include "TreeNode.h" +#include "VMapTools.h" +#include "BaseModel.h" + +namespace VMAP +{ + /** + This is a balanced static BSP-Tree of triangles. + The memory for the tree nodes and the triangles are managed by the ModelContainer. + The exception to this is during the conversion of raw data info balanced BSP-Trees. + During this conversion the memory management is done internally. + */ + class SubModel : public BaseModel + { + private: + unsigned int iNodesPos; + unsigned int iTrianglesPos; + bool iHasInternalMemAlloc; + ShortBox iBox; + #ifdef _DEBUG_VIEW + G3D::Array<TriangleBox *> iDrawBox; + #endif + public: + SubModel() : BaseModel(){ }; + + SubModel(unsigned int pNTriangles, TriangleBox *pTriangles, unsigned int pTrianglesPos, unsigned int pNNodes, TreeNode *pTreeNodes, unsigned int pNodesPos); + SubModel(G3D::AABSPTree<G3D::Triangle> *pTree); + ~SubModel(void); + //Gets a 50 byte binary block + void initFromBinBlock(void *pBinBlock); + + void fillRenderArray(G3D::Array<TriangleBox> &pArray, const TreeNode* pTreeNode); + + void countNodesAndTriangles(G3D::AABSPTree<G3D::Triangle>::Node& pNode, int &pNNodes, int &pNTriabgles); + + void fillContainer(const G3D::AABSPTree<G3D::Triangle>::Node& pNode, int &pTreeNodePos, int &pTrianglePos, G3D::Vector3& pLo, G3D::Vector3& pHi); + + inline const ShortBox& getReletiveBounds() const { return(iBox); } + + inline void setReletiveBounds(const ShortVector& lo, const ShortVector& hi) { iBox.setLo(lo); iBox.setHi(hi); } + + inline const G3D::AABox getAABoxBounds() const { return(G3D::AABox(iBox.getLo().getVector3() + getBasePosition(), iBox.getHi().getVector3()+ getBasePosition())); } + + // get start pos bases on the global array + inline TriangleBox const* getTriangles() const { return &BaseModel::getTriangle(iTrianglesPos); } + inline TriangleBox * getTriangles() { return &BaseModel::getTriangle(iTrianglesPos); } + + // get start pos bases on the global array + inline TreeNode const* getTreeNodes() const { return &BaseModel::getTreeNode(iNodesPos); } + inline TreeNode * getTreeNodes() { return &BaseModel::getTreeNode(iNodesPos); } + + // internal method usign internal offset + inline const TreeNode& getTreeNode(int pPos) const { return(SubModel::getTreeNodes()[pPos]); } + + // internal method usign internal offset + inline const TriangleBox& getTriangle(int pPos) const { return(SubModel::getTriangles()[pPos]); } + + inline unsigned int getNodesPos() const { return(iNodesPos); } + inline unsigned int getTrianglesPos() const { return(iTrianglesPos); } + + //unsigned int hashCode() { return (getBasePosition() * getNTriangles()).hashCode(); } + + void intersect(const G3D::Ray& pRay, float& pMaxDist, bool pStopAtFirstHit, G3D::Vector3& pOutLocation, G3D::Vector3& pOutNormal) const; + bool intersect(const G3D::Ray& pRay, float& pMaxDist) const; + template<typename RayCallback> + void intersectRay(const G3D::Ray& ray, RayCallback& intersectCallback, float& distance, bool pStopAtFirstHit, bool intersectCallbackIsFast = false); + bool operator==(const SubModel& pSm2) const; + unsigned int hashCode() const { return BaseModel::getNTriangles(); } + }; + + unsigned int hashCode(const SubModel& pSm); + void getBounds(const SubModel& pSm, G3D::AABox& pAABox); + void getBounds(const SubModel* pSm, G3D::AABox& pAABox); + //==================================== +} // VMAP +#endif diff --git a/src/shared/vmap/TileAssembler.cpp b/src/shared/vmap/TileAssembler.cpp new file mode 100644 index 00000000000..a51e2c86d63 --- /dev/null +++ b/src/shared/vmap/TileAssembler.cpp @@ -0,0 +1,571 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include <G3D/Vector3.h> +#include <G3D/Triangle.h> + +#include "TileAssembler.h" +#include "CoordModelMapping.h" +#include "ModelContainer.h" + +#include <limits.h> +#include <string.h> + +#ifdef _ASSEMBLER_DEBUG +FILE *g_df = NULL; +#endif + +using namespace G3D; + +namespace VMAP +{ + //================================================================= + + Vector3 ModelPosition::transform(const Vector3& pIn) const + { + //return(pIn); + Vector3 out = pIn * iScale; + out = izMatrix * out; + out = ixMatrix * out; + out = iyMatrix * out; + return(out); + + } + //================================================================= + + TileAssembler::TileAssembler(const std::string& pSrcDirName, const std::string& pDestDirName) + { + iCurrentUniqueNameId = 0; + iFilterMethod = NULL; + iSrcDir = pSrcDirName; + iDestDir = pDestDirName; + //mkdir(iDestDir); + init(); + } + + //================================================================= + + TileAssembler::~TileAssembler() + { + delete iCoordModelMapping; + } + + //================================================================= + + void TileAssembler::init() + { + iCoordModelMapping = new CoordModelMapping(); + addWorldAreaMapId(0); //Azeroth + addWorldAreaMapId(1); //Kalimdor + addWorldAreaMapId(530); //Expansion01 + } + //================================================================= + + std::string getModNameFromModPosName(const std::string& pModPosName) + { + + size_t spos = pModPosName.find_first_of('#'); + std::string modelFileName = pModPosName.substr(0,spos); + return(modelFileName); + } + + //================================================================= + + unsigned int TileAssembler::getUniqueNameId(const std::string pName) + { + unsigned int result; + + if(!iUniqueNameIds.containsKey(pName)) + { + ++iCurrentUniqueNameId; + iUniqueNameIds.set(pName, iCurrentUniqueNameId); + } + result = iUniqueNameIds.get(pName); + return result; + } + + //================================================================= + + std::string TileAssembler::getDirEntryNameFromModName(unsigned int pMapId, const std::string& pModPosName) + { + size_t spos; + char buffer[20]; + + std::string modelFileName = getModNameFromModPosName(pModPosName); + //std::string fext = pModPosName.substr(modelFileName.length(),pModPosName.length()); + unsigned int fextId = getUniqueNameId(pModPosName); + sprintf(buffer, "_%07d",fextId); + std::string fext(buffer); + spos = modelFileName.find_last_of('/'); + std::string fname = modelFileName.substr(spos+1, modelFileName.length()); + spos = fname.find_last_of('.'); + fname = fname.substr(0,spos); + sprintf(buffer, "%03u", pMapId); + std::string dirEntry(buffer); + dirEntry.append("_"); + dirEntry.append(fname); + dirEntry.append(fext); + dirEntry.append(".vmap"); + return(dirEntry); + } + + //================================================================= + + void emptyArray(Array<ModelContainer*>& mc) + { + int no=mc.size(); + while(no > 0) + { + --no; + delete mc[no]; + mc.remove(no); + } + } + + //================================================================= + bool TileAssembler::convertWorld() + { + + #ifdef _ASSEMBLER_DEBUG + # ifdef _DEBUG + ::g_df = fopen("../TileAssembler_debug.txt", "wb"); + # else + ::g_df = fopen("../TileAssembler_release.txt", "wb"); + # endif + #endif + + bool result = true; + std::string fname = iSrcDir; + fname.append("/"); + fname.append("dir"); + iCoordModelMapping->setModelNameFilterMethod(iFilterMethod); + iCoordModelMapping->readCoordinateMapping(fname); + + Array<unsigned int> mapIds = iCoordModelMapping->getMaps(); + if(mapIds.size() == 0) + { + result = false; + } + for(int i=0; i<mapIds.size() && result; ++i) + { + unsigned int mapId = mapIds[i]; + + #ifdef _ASSEMBLER_DEBUG + if(mapId == 0) // "Azeroth" just for debug + { + for(int x=28; x<29 && result; ++x) //debug + { + for(int y=28; y<29 && result; ++y) + { + #else + // ignore DeeprunTram (369) it is too large for short vector and not important + // ignore test (13), Test (29) , development (451) + if(mapId != 369 && mapId != 13 && mapId != 29 && mapId != 451) + { + for(int x=0; x<66 && result; ++x) + { + for(int y=0; y<66 && result; ++y) + { + #endif + Array<ModelContainer*> mc; + std::string dirname; + char buffer[100]; + if(iCoordModelMapping->isWorldAreaMap(mapId) && x<65 && y<65) + { + sprintf(buffer, "%03u_%d_%d",mapId,y,x); // Let's flip x and y here + dirname = std::string(buffer); + } + else + { + sprintf(buffer, "%03u",mapId); + dirname = std::string(buffer); + } + result = fillModelContainerArray(dirname, mapId, x, y, mc); + emptyArray(mc); + } + } + } + } + #ifdef _ASSEMBLER_DEBUG + if(::g_df) fclose(::g_df); + #endif + + return result; + } + + //================================================================= + + bool TileAssembler::fillModelContainerArray(const std::string& pDirFileName, unsigned int pMapId, int pXPos, int pYPos, Array<ModelContainer*>& pMC) + { + bool result = true; + ModelContainer* modelContainer; + + NameCollection nameCollection = iCoordModelMapping->getFilenamesForCoordinate(pMapId, pXPos, pYPos); + if(nameCollection.size() > 0) + { + result = false; + char dirfilename[500]; + sprintf(dirfilename,"%s/%s.vmdir",iDestDir.c_str(),pDirFileName.c_str()); + FILE *dirfile = fopen(dirfilename, "ab"); + if(dirfile) + { + result = true; + char destnamebuffer[500]; + char fullnamedestnamebuffer[500]; + if(nameCollection.iMainFiles.size() >0) + { + sprintf(destnamebuffer,"%03u_%i_%i.vmap",pMapId, pYPos, pXPos); // flip it here too + std::string checkDoubleStr = std::string(dirfilename); + checkDoubleStr.append("##"); + checkDoubleStr.append(std::string(destnamebuffer)); + // Check, if same file already is in the same dir file + if(!iCoordModelMapping->isAlreadyProcessedSingleFile(checkDoubleStr)) + { + iCoordModelMapping->addAlreadyProcessedSingleFile(checkDoubleStr); + fprintf(dirfile, "%s\n",destnamebuffer); + sprintf(fullnamedestnamebuffer,"%s/%s",iDestDir.c_str(),destnamebuffer); + modelContainer = processNames(nameCollection.iMainFiles, fullnamedestnamebuffer); + if(modelContainer) + { + pMC.append(modelContainer); + } + else + { + result = false; + } + } + } + // process the large singe files + int pos = 0; + while(result && (pos < nameCollection.iSingeFiles.size())) + { + std::string destFileName = iDestDir; + destFileName.append("/"); + std::string dirEntryName = getDirEntryNameFromModName(pMapId,nameCollection.iSingeFiles[pos]); + std::string checkDoubleStr = std::string(dirfilename); + checkDoubleStr.append("##"); + checkDoubleStr.append(nameCollection.iSingeFiles[pos]); + // Check, if same file already is in the same dir file + if(!iCoordModelMapping->isAlreadyProcessedSingleFile(checkDoubleStr)) + { + iCoordModelMapping->addAlreadyProcessedSingleFile(checkDoubleStr); + fprintf(dirfile, "%s\n",dirEntryName.c_str()); + destFileName.append(dirEntryName); + + Array<std::string> positionarray; + positionarray.append(nameCollection.iSingeFiles[pos]); + + if(!iCoordModelMapping->isAlreadyProcessedSingleFile(nameCollection.iSingeFiles[pos])) + { + modelContainer = processNames(positionarray, destFileName.c_str()); + iCoordModelMapping->addAlreadyProcessedSingleFile(nameCollection.iSingeFiles[pos]); + if(modelContainer) + { + pMC.append(modelContainer); + } + else + { + result = false; + } + } + } + ++pos; + } + fclose(dirfile); + } + } + return(result); + } + + //================================================================= + + void removeEntriesFromTree(AABSPTree<SubModel *>* pTree) + { + Array<SubModel *> submodelArray; + pTree->getMembers(submodelArray); + int no = submodelArray.size(); + while(no > 0) + { + --no; + delete submodelArray[no]; + } + } + + //================================================================= + + ModelContainer* TileAssembler::processNames(const Array<std::string>& pPositions, const char* pDestFileName) + { + ModelContainer *modelContainer = 0; + + Vector3 basepos = Vector3(0,0,0); + AABSPTree<SubModel *>* mainTree = new AABSPTree<SubModel *>(); + + int pos = 0; + + bool result = true; + while(result && (pos < pPositions.size())) + { + std::string modelPosString = pPositions[pos]; + std::string modelFileName = getModNameFromModPosName(modelPosString); + + if(!fillModelIntoTree(mainTree, basepos, modelPosString, modelFileName)) + { + result = false; + break; + } + ++pos; + } + if(result && mainTree->size() > 0) + { + mainTree->balance(); + modelContainer = new ModelContainer(mainTree); + modelContainer->writeFile(pDestFileName); + } + removeEntriesFromTree(mainTree); + + delete mainTree; + + return(modelContainer); + } + + //================================================================= + bool TileAssembler::readRawFile(std::string& pModelFilename, ModelPosition& pModelPosition, AABSPTree<SubModel *> *pMainTree) + { + bool result = false; + + std::string filename = iSrcDir; + if(filename.length() >0) + filename.append("/"); + filename.append(pModelFilename); + FILE *rf = fopen(filename.c_str(), "rb"); + if(!rf) + { + // depending on the extractor version, the data could be located in the root dir + std::string baseModelFilename = pModelFilename.substr((pModelFilename.find_first_of("/")+1),pModelFilename.length()); + filename = iSrcDir; + if(filename.length() >0) + filename.append("/"); + filename.append(baseModelFilename); + rf = fopen(filename.c_str(), "rb"); + } + char ident[8]; + + int trianglecount =0; + + #ifdef _ASSEMBLER_DEBUG + int startgroup = 0; //2; + int endgroup = INT_MAX; //2; + fprintf(::g_df,"-------------------------------------------------\n"); + fprintf(::g_df,"%s\n", pModelFilename.c_str()); + fprintf(::g_df,"-------------------------------------------------\n"); + #else + int startgroup = 0; + int endgroup = INT_MAX; + #endif + + if(rf) + { + if(fread(&ident, 8, 1, rf) != 1) { fclose(rf); return(false); } + if(strcmp(ident, "VMAP001") == 0) + { + // OK, do nothing + } + else if(strcmp(ident, "VMAP002") == 0) + { + // we have to read one int. This is needed during the export and we have to skip it here + int tempNVectors; + if(fread(&tempNVectors, sizeof(int), 1, rf) != 1) { fclose(rf); return(false); } + + } + else + { + // wrong version + fclose(rf); + return(false); + } + G3D::uint32 groups; + char blockId[5]; + blockId[4] = 0; + int blocksize; + + if(fread(&groups, sizeof(G3D::uint32), 1, rf) != 1) { fclose(rf); return(false); } + + for(int g=0;g<(int)groups;g++) + { + // group MUST NOT have more then 65536 indexes !! Array will have a problem with that !! (strange ...) + Array<int> tempIndexArray; + Array<Vector3> tempVertexArray; + + AABSPTree<Triangle> *gtree = new AABSPTree<Triangle>(); + + G3D::uint32 flags; + if(fread(&flags, sizeof(G3D::uint32), 1, rf) != 1) { fclose(rf); return(false); } + + G3D::uint32 branches; + if(fread(&blockId, 4, 1, rf) != 1) { fclose(rf); return(false); } + if(strcmp(blockId, "GRP ") != 0) { fclose(rf); return(false); } + if(fread(&blocksize, sizeof(int), 1, rf) != 1) { fclose(rf); return(false); } + if(fread(&branches, sizeof(G3D::uint32), 1, rf) != 1) { fclose(rf); return(false); } + for(int b=0;b<(int)branches; b++) + { + G3D::uint32 indexes; + // indexes for each branch (not used jet) + if(fread(&indexes, sizeof(G3D::uint32), 1, rf) != 1) { fclose(rf); return(false); } + } + + // ---- indexes + if(fread(&blockId, 4, 1, rf) != 1) { fclose(rf); return(false); } + if(strcmp(blockId, "INDX") != 0) { fclose(rf); return(false); } + if(fread(&blocksize, sizeof(int), 1, rf) != 1) { fclose(rf); return(false); } + unsigned int nindexes; + if(fread(&nindexes, sizeof(G3D::uint32), 1, rf) != 1) { fclose(rf); return(false); } + if(nindexes >0) + { + unsigned short *indexarray = new unsigned short[nindexes*sizeof(unsigned short)]; + if(fread(indexarray, sizeof(unsigned short), nindexes, rf) != nindexes) { fclose(rf); return(false); } + for(int i=0;i<(int)nindexes; i++) + { + unsigned short val = indexarray[i]; + tempIndexArray.append(val); + } + delete indexarray; + } + + // ---- vectors + if(fread(&blockId, 4, 1, rf) != 1) {fclose(rf); return(false); } + if(strcmp(blockId, "VERT") != 0) { fclose(rf); return(false); } + if(fread(&blocksize, sizeof(int), 1, rf) != 1) { fclose(rf); return(false); } + unsigned int nvectors; + if(fread(&nvectors, sizeof(int), 1, rf) != 1) { fclose(rf); return(false); } + float *vectorarray = 0; + if(nvectors >0) + { + vectorarray = new float[nvectors*sizeof(float)*3]; + if(fread(vectorarray, sizeof(float)*3, nvectors, rf) != nvectors) { fclose(rf); return(false); } + } + // ----- liquit + if(flags & 1) + { + // we have liquit -> not handled yet ... skip + if(fread(&blockId, 4, 1, rf) != 1) { fclose(rf); return(false); } + if(strcmp(blockId, "LIQU") != 0) { fclose(rf); return(false); } + if(fread(&blocksize, sizeof(int), 1, rf) != 1) { fclose(rf); return(false); } + fseek(rf, blocksize, SEEK_CUR); + } + + for(unsigned int i=0, indexNo=0; indexNo<nvectors; indexNo++) + { + Vector3 v = Vector3(vectorarray[i+2], vectorarray[i+1], vectorarray[i+0]); + i+=3; + v = pModelPosition.transform(v); + + float swapy = v.y; + v.y = v.x; + v.x = swapy; + + tempVertexArray.append(v); + } + + // ---- calculate triangles + int rest = nindexes%3; + if(rest != 0) + { + nindexes -= rest; + } + + for(unsigned int i=0;i<(nindexes);) + { + Triangle t = Triangle(tempVertexArray[tempIndexArray[i+2]], tempVertexArray[tempIndexArray[i+1]], tempVertexArray[tempIndexArray[i+0]] ); + i+=3; + ++trianglecount; + if(g>= startgroup && g <= endgroup) + { + gtree->insert(t); + } + } + + if(vectorarray != 0) + { + delete vectorarray; + } + + if(gtree->size() >0) + { + gtree->balance(); + SubModel *sm = new SubModel(gtree); + #ifdef _ASSEMBLER_DEBUG + if(::g_df) fprintf(::g_df,"group trianglies: %d, Tris: %d, Nodes: %d, gtree.triangles: %d\n", g, sm->getNTriangles(), sm->getNNodes(), gtree->memberTable.size()); + if(sm->getNTriangles() != gtree->memberTable.size()) + { + if(::g_df) fprintf(::g_df,"ERROR !!!! group trianglies: %d, Tris: %d, Nodes: %d, gtree.triangles: %d\n", g, sm->getNTriangles(), sm->getNNodes(), gtree->memberTable.size()); + } + #endif + sm->setBasePosition(pModelPosition.iPos); + pMainTree->insert(sm); + } + delete gtree; + } + fclose(rf); + result = true; + } + return(result); + } + + //================================================================= + + bool TileAssembler::fillModelIntoTree(AABSPTree<SubModel *> *pMainTree, const Vector3& pBasePos, std::string& pPos, std::string& pModelFilename) + { + bool result = false; + ModelPosition modelPosition; + getModelPosition(pPos, modelPosition); + // all should be relative to object base position + modelPosition.moveToBasePos(pBasePos); + + modelPosition.init(); + + if(readRawFile(pModelFilename, modelPosition, pMainTree)) + { + result = true; + } + + return result; + } + + //================================================================= + void TileAssembler::getModelPosition(std::string& pPosString, ModelPosition& pModelPosition) + { + float vposarray[3]; + float vdirarray[3]; + float scale; + + size_t spos = pPosString.find_first_of('#'); + std::string stripedPosString = pPosString.substr(spos+1,pPosString.length()); + + sscanf(stripedPosString.c_str(), "%f,%f,%f_%f,%f,%f_%f", + &vposarray[0],&vposarray[1],&vposarray[2], + &vdirarray[0],&vdirarray[1],&vdirarray[2], + &scale); + + pModelPosition.iPos = Vector3(vposarray[0], vposarray[1], vposarray[2]); + pModelPosition.iDir = Vector3(vdirarray[0], vdirarray[1], vdirarray[2]); + pModelPosition.iScale = scale; + + } + //========================================== + + } // VMAP diff --git a/src/shared/vmap/TileAssembler.h b/src/shared/vmap/TileAssembler.h new file mode 100644 index 00000000000..afcce24c664 --- /dev/null +++ b/src/shared/vmap/TileAssembler.h @@ -0,0 +1,93 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _TILEASSEMBLER_H_ +#define _TILEASSEMBLER_H_ + +// load our modified version first !! +#include "AABSPTree.h" + +#include <G3D/Vector3.h> + +#include "CoordModelMapping.h" +#include "SubModel.h" +#include "ModelContainer.h" + +namespace VMAP +{ + /** + This Class is used to convert raw vector data into balanced BSP-Trees. + To start the conversion call convertWorld(). + */ + //=============================================== + + class ModelPosition + { + private: + G3D::Matrix3 ixMatrix; + G3D::Matrix3 iyMatrix; + G3D::Matrix3 izMatrix; + public: + G3D::Vector3 iPos; + G3D::Vector3 iDir; + float iScale; + void init() + { + + // Swap x and y the raw data uses the axis differently + ixMatrix = G3D::Matrix3::fromAxisAngle(G3D::Vector3::unitY(),-(G3D::pi()*iDir.x/180.0)); + iyMatrix = G3D::Matrix3::fromAxisAngle(G3D::Vector3::unitX(),-(G3D::pi()*iDir.y/180.0)); + izMatrix = G3D::Matrix3::fromAxisAngle(G3D::Vector3::unitZ(),-(G3D::pi()*iDir.z/180.0)); + + } + G3D::Vector3 transform(const G3D::Vector3& pIn) const; + void moveToBasePos(const G3D::Vector3& pBasePos) { iPos -= pBasePos; } + }; + //=============================================== + + class TileAssembler + { + private: + CoordModelMapping *iCoordModelMapping; + std::string iDestDir; + std::string iSrcDir; + bool (*iFilterMethod)(char *pName); + G3D::Table<std::string, unsigned int > iUniqueNameIds; + unsigned int iCurrentUniqueNameId; + + public: + TileAssembler(const std::string& pSrcDirName, const std::string& pDestDirName); + virtual ~TileAssembler(); + + bool fillModelContainerArray(const std::string& pDirFileName, unsigned int pMapId, int pXPos, int pYPos, G3D::Array<ModelContainer*>& pMC); + ModelContainer* processNames(const G3D::Array<std::string>& pPosFileNames, const char* pDestFileName); + + void init(); + bool convertWorld(); + + bool fillModelIntoTree(G3D::AABSPTree<SubModel *> *pMainTree, const G3D::Vector3& pBasePos, std::string& pPosFilename, std::string& pModelFilename); + void getModelPosition(std::string& pPosString, ModelPosition& pModelPosition); + bool readRawFile(std::string& pModelFilename, ModelPosition& pModelPosition, G3D::AABSPTree<SubModel *> *pMainTree); + void addWorldAreaMapId(unsigned int pMapId) { iCoordModelMapping->addWorldAreaMap(pMapId); } + void setModelNameFilterMethod(bool (*pFilterMethod)(char *pName)) { iFilterMethod = pFilterMethod; } + std::string getDirEntryNameFromModName(unsigned int pMapId, const std::string& pModPosName); + unsigned int getUniqueNameId(const std::string pName); + }; + //=============================================== +} // VMAP +#endif /*_TILEASSEMBLER_H_*/ diff --git a/src/shared/vmap/TreeNode.cpp b/src/shared/vmap/TreeNode.cpp new file mode 100644 index 00000000000..97846d6c992 --- /dev/null +++ b/src/shared/vmap/TreeNode.cpp @@ -0,0 +1,37 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "TreeNode.h" + +using namespace G3D; + +namespace VMAP +{ + + TreeNode const* TreeNode::getChild(TreeNode const* pValueArray,int pNo) const + { + if(iChilds[pNo] != -1) + return(&pValueArray[iChilds[pNo]]); + else + return(NULL); + } + + //================================================================= + //================================================================= + //================================================================= +} diff --git a/src/shared/vmap/TreeNode.h b/src/shared/vmap/TreeNode.h new file mode 100644 index 00000000000..c034b3c88f3 --- /dev/null +++ b/src/shared/vmap/TreeNode.h @@ -0,0 +1,223 @@ +/* +* Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> +* +* This program is free software; you can redistribute it and/or modify +* it under the terms of the GNU General Public License as published by +* the Free Software Foundation; either version 2 of the License, or +* (at your option) any later version. +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with this program; if not, write to the Free Software +* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +*/ + +#ifndef _TREENODE_H +#define _TREENODE_H + +#include "ShortVector.h" +#include "ShortBox.h" +#include "NodeValueAccess.h" +#include "VMapTools.h" + +#include <G3D/Vector3.h> +#include <G3D/AABox.h> + +namespace VMAP +{ + /** + This Class is mainly taken from G3D/AABSPTree.h and modified to match our data structure. + It is the node within our static BSP-Trees. + It does not use pointers but indexes to access the values and other nodes. + */ + + //===================================================== + + class TreeNode + { + private: + /** Location along the specified axis */ + float iSplitLocation; + // Offest or the clients + int iChilds[2]; + //Position within the TriangleBox array + unsigned int iStartPosition; + G3D::Vector3::Axis iSplitAxis; + G3D::AABox iBounds; + unsigned short iNumberOfValues; + public: + TreeNode() {} + TreeNode(unsigned short pNValues, unsigned int pStartPosition) + { + iChilds[0] = -1; + iChilds[1] = -1; + iStartPosition = pStartPosition; + iNumberOfValues = pNValues; + } + + bool hasChilds() const { return(iChilds[0] >= 0 || iChilds[1] >= 0); } + + TreeNode const* getChild(TreeNode const* pValueArray, int pNo) const; + // pChildNo = 0 or 1 + inline void setChildPos(int pChildNo, int pChildPosInTreeNodeArray) { iChilds[pChildNo] = pChildPosInTreeNodeArray; } + + inline G3D::Vector3::Axis getSplitAxis() const { return(iSplitAxis); } + + inline void setSplitAxis(G3D::Vector3::Axis a) { iSplitAxis = a; } + inline void setSplitLocation(float l) { iSplitLocation = l; } + + inline void setBounds(const G3D::AABox& pBox) { iBounds = pBox; } + + inline void setBounds(const G3D::Vector3& lo, const G3D::Vector3& hi) { iBounds.set(lo,hi); } + + inline void getBounds(G3D::AABox& pBox) const { pBox.set(iBounds.low(),iBounds.high()); } + + inline float getSplitLocation() const { return(iSplitLocation); } + + inline unsigned short getNValues() const { return (iNumberOfValues); } + + inline unsigned int getStartPosition() const { return(iStartPosition); } + + inline bool operator==(const TreeNode& n) const + { + return ((iSplitLocation == n.iSplitLocation) && + (iChilds[0] == n.iChilds[0]) && (iChilds[1] == n.iChilds[1]) && + (iStartPosition == n.iStartPosition) && + (iSplitAxis == n.iSplitAxis) && + (iBounds == n.iBounds) && + (iNumberOfValues == n.iNumberOfValues)); + } + + inline bool operator!=(const TreeNode& n) const + { + return !((iSplitLocation == n.iSplitLocation) && + (iChilds[0] == n.iChilds[0]) && (iChilds[1] == n.iChilds[1]) && + (iStartPosition == n.iStartPosition) && + (iSplitAxis == n.iSplitAxis) && + (iBounds == n.iBounds) && + (iNumberOfValues == n.iNumberOfValues)); + } + + /** Returns true if the ray intersects this node */ + bool intersects(const G3D::Ray& ray, float distance) const { + // See if the ray will ever hit this node or its children + G3D::Vector3 location; + bool alreadyInsideBounds = false; + bool rayWillHitBounds = + MyCollisionDetection::collisionLocationForMovingPointFixedAABox( + ray.origin, ray.direction, iBounds, location, alreadyInsideBounds); + + bool canHitThisNode = (alreadyInsideBounds || + (rayWillHitBounds && ((location - ray.origin).squaredLength() < (distance*distance)))); + + return canHitThisNode; + } + + template<typename RayCallback, typename TNode, typename TValue> + void intersectRay( + const G3D::Ray& ray, + RayCallback& intersectCallback, + float& distance, + const NodeValueAccess<TNode, TValue>& pNodeValueAccess, + bool pStopAtFirstHit, + bool intersectCallbackIsFast) const { + float enterDistance = distance; + if (! intersects(ray, distance)) { + // The ray doesn't hit this node, so it can't hit the children of the node. + return; + } + + // Test for intersection against every object at this node. + for (unsigned int v = iStartPosition; v < (iNumberOfValues+iStartPosition); ++v) { + const TValue& nodeValue = pNodeValueAccess.getValue(v); + bool canHitThisObject = true; + if (! intersectCallbackIsFast) { + // See if + G3D::Vector3 location; + const G3D::AABox& bounds = nodeValue.getAABoxBounds(); + bool alreadyInsideBounds = false; + bool rayWillHitBounds = + MyCollisionDetection::collisionLocationForMovingPointFixedAABox( + ray.origin, ray.direction, bounds, location, alreadyInsideBounds); + + canHitThisObject = (alreadyInsideBounds || + (rayWillHitBounds && ((location - ray.origin).squaredLength() < (distance*distance)))); + } + + if (canHitThisObject) { + // It is possible that this ray hits this object. Look for the intersection using the + // callback. + intersectCallback(ray, &nodeValue, pStopAtFirstHit, distance); + } + if(pStopAtFirstHit && distance < enterDistance) + return; + } + + // There are three cases to consider next: + // + // 1. the ray can start on one side of the splitting plane and never enter the other, + // 2. the ray can start on one side and enter the other, and + // 3. the ray can travel exactly down the splitting plane + + enum {NONE = -1}; + int firstChild = NONE; + int secondChild = NONE; + + if (ray.origin[iSplitAxis] < iSplitLocation) { + + // The ray starts on the small side + firstChild = 0; + + if (ray.direction[iSplitAxis] > 0) { + // The ray will eventually reach the other side + secondChild = 1; + } + + } else if (ray.origin[iSplitAxis] > iSplitLocation) { + + // The ray starts on the large side + firstChild = 1; + + if (ray.direction[iSplitAxis] < 0) { + secondChild = 0; + } + } else { + // The ray starts on the splitting plane + if (ray.direction[iSplitAxis] < 0) { + // ...and goes to the small side + firstChild = 0; + } else if (ray.direction[iSplitAxis] > 0) { + // ...and goes to the large side + firstChild = 1; + } + } + + // Test on the side closer to the ray origin. + if ((firstChild != NONE) && iChilds[firstChild]>0) { + getChild(pNodeValueAccess.getNodePtr() , firstChild)->intersectRay(ray, intersectCallback, distance, pNodeValueAccess, pStopAtFirstHit,intersectCallbackIsFast); + if(pStopAtFirstHit && distance < enterDistance) + return; + } + if (ray.direction[iSplitAxis] != 0) { + // See if there was an intersection before hitting the splitting plane. + // If so, there is no need to look on the far side and recursion terminates. + float distanceToSplittingPlane = (iSplitLocation - ray.origin[iSplitAxis]) / ray.direction[iSplitAxis]; + if (distanceToSplittingPlane > distance) { + // We aren't going to hit anything else before hitting the splitting plane, + // so don't bother looking on the far side of the splitting plane at the other + // child. + return; + } + } + // Test on the side farther from the ray origin. + if ((secondChild != NONE) && iChilds[secondChild]>0) { + getChild(pNodeValueAccess.getNodePtr() , secondChild)->intersectRay(ray, intersectCallback, distance, pNodeValueAccess, pStopAtFirstHit,intersectCallbackIsFast); + } + } + }; +} +#endif diff --git a/src/shared/vmap/VMapDefinitions.h b/src/shared/vmap/VMapDefinitions.h new file mode 100644 index 00000000000..ec7858b0cc1 --- /dev/null +++ b/src/shared/vmap/VMapDefinitions.h @@ -0,0 +1,37 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _VMAPDEFINITIONS_H +#define _VMAPDEFINITIONS_H +#include <cstring> + +namespace VMAP +{ + //===================================== + #define MAX_CAN_FALL_DISTANCE 10.0 + const char VMAP_MAGIC[] = "VMAP_2.0"; + + class VMapDefinitions + { + public: + static const double getMaxCanFallDistance() { return(MAX_CAN_FALL_DISTANCE); } + }; + + //====================================== +} +#endif diff --git a/src/shared/vmap/VMapFactory.cpp b/src/shared/vmap/VMapFactory.cpp new file mode 100644 index 00000000000..15454533c8b --- /dev/null +++ b/src/shared/vmap/VMapFactory.cpp @@ -0,0 +1,104 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include <sys/types.h> +#include "VMapFactory.h" +#include "VMapManager.h" + +using namespace G3D; + +namespace VMAP +{ + extern void chompAndTrim(std::string& str); + + VMapManager *gVMapManager = 0; + Table<unsigned int , bool>* iIgnoreSpellIds=0; + + //=============================================== + // result false, if no more id are found + + bool getNextId(const std::string& pString, unsigned int& pStartPos, unsigned int& pId) + { + bool result = false; + unsigned int i; + for(i=pStartPos;i<pString.size(); ++i) + { + if(pString[i] == ',') + { + break; + } + } + if(i>pStartPos) + { + std::string idString = pString.substr(pStartPos, i-pStartPos); + pStartPos = i+1; + chompAndTrim(idString); + pId = atoi(idString.c_str()); + result = true; + } + return(result); + } + + //=============================================== + /** + parameter: String of map ids. Delimiter = "," + */ + + void VMapFactory::preventSpellsFromBeingTestedForLoS(const char* pSpellIdString) + { + if(!iIgnoreSpellIds) + iIgnoreSpellIds = new Table<unsigned int , bool>(); + if(pSpellIdString != NULL) + { + unsigned int pos =0; + unsigned int id; + std::string confString(pSpellIdString); + chompAndTrim(confString); + while(getNextId(confString, pos, id)) + { + iIgnoreSpellIds->set(id, true); + } + } + } + + //=============================================== + + bool VMapFactory::checkSpellForLoS(unsigned int pSpellId) + { + return(!iIgnoreSpellIds->containsKey(pSpellId)); + } + + //=============================================== + // just return the instance + IVMapManager* VMapFactory::createOrGetVMapManager() + { + if(gVMapManager == 0) + gVMapManager= new VMapManager(); // should be taken from config ... Please change if you like :-) + return gVMapManager; + } + + //=============================================== + // delete all internal data structures + void VMapFactory::clear() + { + if(iIgnoreSpellIds) + delete iIgnoreSpellIds; + if(gVMapManager) + delete gVMapManager; + } +} diff --git a/src/shared/vmap/VMapFactory.h b/src/shared/vmap/VMapFactory.h new file mode 100644 index 00000000000..d63f10d94b4 --- /dev/null +++ b/src/shared/vmap/VMapFactory.h @@ -0,0 +1,43 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _VMAPFACTORY_H +#define _VMAPFACTORY_H + +#include "IVMapManager.h" + +/** +This is the access point to the VMapManager. +*/ + +namespace VMAP +{ + //=========================================================== + + class VMapFactory + { + public: + static IVMapManager* createOrGetVMapManager(); + static void clear(); + + static void preventSpellsFromBeingTestedForLoS(const char* pSpellIdString); + static bool checkSpellForLoS(unsigned int pSpellId); + }; + +} +#endif diff --git a/src/shared/vmap/VMapManager.cpp b/src/shared/vmap/VMapManager.cpp new file mode 100644 index 00000000000..a4427060184 --- /dev/null +++ b/src/shared/vmap/VMapManager.cpp @@ -0,0 +1,780 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "VMapManager.h" +#include "VMapDefinitions.h" + +using namespace G3D; + +namespace VMAP +{ + + //========================================================= + + VMapManager::VMapManager() + { +#ifdef _VMAP_LOG_DEBUG + iCommandLogger.setFileName("vmapcmd.log"); + iCommandLogger.setResetFile(); +#endif + } + + //========================================================= + + VMapManager::~VMapManager(void) + { + Array<unsigned int > keyArray = iInstanceMapTrees.getKeys(); + for(int i=0;i<keyArray.size(); ++i) + { + delete iInstanceMapTrees.get(keyArray[i]); + iInstanceMapTrees.remove(keyArray[i]); + } + } + + //========================================================= + + Vector3 VMapManager::convertPositionToInternalRep(float x, float y, float z) const + { + float pos[3]; + pos[0] = y; + pos[1] = z; + pos[2] = x; + double full = 64.0*533.33333333; + double mid = full/2.0; + pos[0] = full- (pos[0] + mid); + pos[2] = full- (pos[2] + mid); + + return(Vector3(pos)); + } + + //========================================================= + + Vector3 VMapManager::convertPositionToMangosRep(float x, float y, float z) const + { + float pos[3]; + pos[0] = z; + pos[1] = x; + pos[2] = y; + double full = 64.0*533.33333333; + double mid = full/2.0; + pos[0] = -((mid+pos[0])-full); + pos[1] = -((mid+pos[1])-full); + + return(Vector3(pos)); + } + //========================================================= + + std::string VMapManager::getDirFileName(unsigned int pMapId, int x, int y) const + { + char name[FILENAMEBUFFER_SIZE]; + + sprintf(name, "%03u_%d_%d%s",pMapId, x, y, DIR_FILENAME_EXTENSION); + return(std::string(name)); + } + + //========================================================= + std::string VMapManager::getDirFileName(unsigned int pMapId) const + { + char name[FILENAMEBUFFER_SIZE]; + + sprintf(name, "%03d%s",pMapId, DIR_FILENAME_EXTENSION); + return(std::string(name)); + } + //========================================================= + // remote last return or LF + void chomp(std::string& str) + { + while(str.length() >0) + { + char lc = str[str.length()-1]; + if(lc == '\r' || lc == '\n') + { + str = str.substr(0,str.length()-1); + } + else + { + break; + } + } + } + //========================================================= + + void chompAndTrim(std::string& str) + { + while(str.length() >0) + { + char lc = str[str.length()-1]; + if(lc == '\r' || lc == '\n' || lc == ' ' || lc == '"' || lc == '\'') + { + str = str.substr(0,str.length()-1); + } + else + { + break; + } + } + while(str.length() >0) + { + char lc = str[0]; + if(lc == ' ' || lc == '"' || lc == '\'') + { + str = str.substr(1,str.length()-1); + } + else + { + break; + } + } + } + + //========================================================= + // result false, if no more id are found + + bool getNextMapId(const std::string& pString, unsigned int& pStartPos, unsigned int& pId) + { + bool result = false; + unsigned int i; + for(i=pStartPos;i<pString.size(); ++i) + { + if(pString[i] == ',') + { + break; + } + } + if(i>pStartPos) + { + std::string idString = pString.substr(pStartPos, i-pStartPos); + pStartPos = i+1; + chompAndTrim(idString); + pId = atoi(idString.c_str()); + result = true; + } + return(result); + } + + //========================================================= + /** + Block maps from being used. + parameter: String of map ids. Delimiter = "," + e.g.: "0,1,590" + */ + + void VMapManager::preventMapsFromBeingUsed(const char* pMapIdString) + { + if(pMapIdString != NULL) + { + unsigned int pos =0; + unsigned int id; + std::string confString(pMapIdString); + chompAndTrim(confString); + while(getNextMapId(confString, pos, id)) + { + iIgnoreMapIds.set(id, true); + } + } + } + + //========================================================= + + int VMapManager::loadMap(const char* pBasePath, unsigned int pMapId, int x, int y) + { + int result = VMAP_LOAD_RESULT_IGNORED; + if(isMapLoadingEnabled() && !iIgnoreMapIds.containsKey(pMapId)) + { + bool loaded = _loadMap(pBasePath, pMapId, x, y, false); + if(!loaded) + { + // if we can't load the map it might be splitted into tiles. Try that one and store the result + loaded = _loadMap(pBasePath, pMapId, x, y, true); + if(loaded) + { + iMapsSplitIntoTiles.set(pMapId, true); + } + } + if(loaded) + { + result = VMAP_LOAD_RESULT_OK; + // just for debugging +#ifdef _VMAP_LOG_DEBUG + Command c = Command(); + c.fillLoadTileCmd(x, y, pMapId); + iCommandLogger.appendCmd(c); +#endif + } + else + { + result = VMAP_LOAD_RESULT_ERROR; + } + } + return result; + } + + //========================================================= + // load one tile (internal use only) + + bool VMapManager::_loadMap(const char* pBasePath, unsigned int pMapId, int x, int y, bool pForceTileLoad) + { + bool result = false; + std::string dirFileName; + if(pForceTileLoad || iMapsSplitIntoTiles.containsKey(pMapId)) + { + dirFileName = getDirFileName(pMapId,x,y); + } + else + { + dirFileName = getDirFileName(pMapId); + } + MapTree* instanceTree; + if(!iInstanceMapTrees.containsKey(pMapId)) + { + instanceTree = new MapTree(pBasePath); + iInstanceMapTrees.set(pMapId, instanceTree); + } + else + instanceTree = iInstanceMapTrees.get(pMapId); + + unsigned int mapTileIdent = MAP_TILE_IDENT(x,y); + result = instanceTree->loadMap(dirFileName, mapTileIdent); + if(!result) // remove on fail + { + if(instanceTree->size() == 0) + { + iInstanceMapTrees.remove(pMapId); + delete instanceTree; + } + } + return(result); + } + + //========================================================= + + bool VMapManager::_existsMap(const std::string& pBasePath, unsigned int pMapId, int x, int y, bool pForceTileLoad) + { + bool result = false; + std::string dirFileName; + if(pForceTileLoad || iMapsSplitIntoTiles.containsKey(pMapId)) + { + dirFileName = getDirFileName(pMapId,x,y); + } + else + { + dirFileName = getDirFileName(pMapId); + } + size_t len = pBasePath.length() + dirFileName.length(); + char *filenameBuffer = new char[len+1]; + sprintf(filenameBuffer, "%s%s", pBasePath.c_str(), dirFileName.c_str()); + FILE* df = fopen(filenameBuffer, "rb"); + if(df) + { + char lineBuffer[FILENAMEBUFFER_SIZE]; + if (fgets(lineBuffer, FILENAMEBUFFER_SIZE-1, df) != 0) + { + std::string name = std::string(lineBuffer); + chomp(name); + if(name.length() >1) + { + sprintf(filenameBuffer, "%s%s", pBasePath.c_str(), name.c_str()); + FILE* df2 = fopen(filenameBuffer, "rb"); + if(df2) + { + char magic[8]; + fread(magic,1,8,df2); + if(!strncmp(VMAP_MAGIC,magic,8)) + result = true; + fclose(df2); + } + } + } + fclose(df); + } + delete[] filenameBuffer; + return result; + } + + //========================================================= + + bool VMapManager::existsMap(const char* pBasePath, unsigned int pMapId, int x, int y) + { + std::string basePath = std::string(pBasePath); + if(basePath.length() > 0 && (basePath[basePath.length()-1] != '/' || basePath[basePath.length()-1] != '\\')) + { + basePath.append("/"); + } + bool found = _existsMap(basePath, pMapId, x, y, false); + if(!found) + { + // if we can't load the map it might be splitted into tiles. Try that one and store the result + found = _existsMap(basePath, pMapId, x, y, true); + if(found) + { + iMapsSplitIntoTiles.set(pMapId, true); + } + } + return found; + } + + //========================================================= + + void VMapManager::unloadMap(unsigned int pMapId, int x, int y) + { + _unloadMap(pMapId, x, y); + +#ifdef _VMAP_LOG_DEBUG + Command c = Command(); + c.fillUnloadTileCmd(pMapId, x,y); + iCommandLogger.appendCmd(c); +#endif + } + + //========================================================= + + void VMapManager::_unloadMap(unsigned int pMapId, int x, int y) + { + if(iInstanceMapTrees.containsKey(pMapId)) + { + MapTree* instanceTree = iInstanceMapTrees.get(pMapId); + std::string dirFileName; + if(iMapsSplitIntoTiles.containsKey(pMapId)) + { + dirFileName = getDirFileName(pMapId,x,y); + } + else + { + dirFileName = getDirFileName(pMapId); + } + unsigned int mapTileIdent = MAP_TILE_IDENT(x,y); + instanceTree->unloadMap(dirFileName, mapTileIdent); + if(instanceTree->size() == 0) + { + iInstanceMapTrees.remove(pMapId); + delete instanceTree; + } + } + } + + //========================================================= + + void VMapManager::unloadMap(unsigned int pMapId) + { + if(iInstanceMapTrees.containsKey(pMapId)) + { + MapTree* instanceTree = iInstanceMapTrees.get(pMapId); + std::string dirFileName = getDirFileName(pMapId); + instanceTree->unloadMap(dirFileName, 0, true); + if(instanceTree->size() == 0) + { + iInstanceMapTrees.remove(pMapId); + delete instanceTree; + } +#ifdef _VMAP_LOG_DEBUG + Command c = Command(); + c.fillUnloadTileCmd(pMapId); + iCommandLogger.appendCmd(c); +#endif + } + } + //========================================================== + + bool VMapManager::isInLineOfSight(unsigned int pMapId, float x1, float y1, float z1, float x2, float y2, float z2) + { + bool result = true; + if(isLineOfSightCalcEnabled() && iInstanceMapTrees.containsKey(pMapId)) + { + Vector3 pos1 = convertPositionToInternalRep(x1,y1,z1); + Vector3 pos2 = convertPositionToInternalRep(x2,y2,z2); + if(pos1 != pos2) + { + MapTree* mapTree = iInstanceMapTrees.get(pMapId); + result = mapTree->isInLineOfSight(pos1, pos2); +#ifdef _VMAP_LOG_DEBUG + Command c = Command(); + // save the orig vectors + c.fillTestVisCmd(pMapId,Vector3(x1,y1,z1),Vector3(x2,y2,z2),result); + iCommandLogger.appendCmd(c); +#endif + } + } + return(result); + } + //========================================================= + /** + get the hit position and return true if we hit something + otherwise the result pos will be the dest pos + */ + bool VMapManager::getObjectHitPos(unsigned int pMapId, float x1, float y1, float z1, float x2, float y2, float z2, float& rx, float &ry, float& rz, float pModifyDist) + { + bool result = false; + rx=x2; + ry=y2; + rz=z2; + if(isLineOfSightCalcEnabled()) + { + if(iInstanceMapTrees.containsKey(pMapId)) + { + Vector3 pos1 = convertPositionToInternalRep(x1,y1,z1); + Vector3 pos2 = convertPositionToInternalRep(x2,y2,z2); + Vector3 resultPos; + MapTree* mapTree = iInstanceMapTrees.get(pMapId); + result = mapTree->getObjectHitPos(pos1, pos2, resultPos, pModifyDist); + resultPos = convertPositionToMangosRep(resultPos.x,resultPos.y,resultPos.z); + rx = resultPos.x; + ry = resultPos.y; + rz = resultPos.z; +#ifdef _VMAP_LOG_DEBUG + Command c = Command(); + c.fillTestObjectHitCmd(pMapId, pos1, pos2, resultPos, result); + iCommandLogger.appendCmd(c); +#endif + } + } + return result; + } + + //========================================================= + /** + get height or INVALID_HEIGHT if to hight was calculated + */ + + //int gGetHeightCounter = 0; + float VMapManager::getHeight(unsigned int pMapId, float x, float y, float z) + { + float height = VMAP_INVALID_HEIGHT_VALUE; //no height + if(isHeightCalcEnabled() && iInstanceMapTrees.containsKey(pMapId)) + { + Vector3 pos = convertPositionToInternalRep(x,y,z); + MapTree* mapTree = iInstanceMapTrees.get(pMapId); + height = mapTree->getHeight(pos); + if(!(height < inf())) + { + height = VMAP_INVALID_HEIGHT_VALUE; //no height + } +#ifdef _VMAP_LOG_DEBUG + Command c = Command(); + c.fillTestHeightCmd(pMapId,Vector3(x,y,z),height); + iCommandLogger.appendCmd(c); +#endif + } + return(height); + } + + //========================================================= + /** + used for debugging + */ + bool VMapManager::processCommand(char *pCommand) + { + bool result = false; + std::string cmd = std::string(pCommand); + if(cmd == "startlog") + { +#ifdef _VMAP_LOG_DEBUG + + iCommandLogger.enableWriting(true); +#endif + result = true; + } + else if(cmd == "stoplog") + { +#ifdef _VMAP_LOG_DEBUG + iCommandLogger.appendCmd(Command()); // Write stop command + iCommandLogger.enableWriting(false); +#endif + result = true; + } + else if(cmd.find_first_of("pos ") == 0) + { + float x,y,z; + sscanf(pCommand, "pos %f,%f,%f",&x,&y,&z); +#ifdef _VMAP_LOG_DEBUG + Command c = Command(); + c.fillSetPosCmd(convertPositionToInternalRep(x,y,z)); + iCommandLogger.appendCmd(c); + iCommandLogger.enableWriting(false); +#endif + result = true; + } + return result; + } + + //========================================================= + //========================================================= + //========================================================= + + MapTree::MapTree(const char* pBaseDir) + { + iBasePath = std::string(pBaseDir); + if(iBasePath.length() > 0 && (iBasePath[iBasePath.length()-1] != '/' || iBasePath[iBasePath.length()-1] != '\\')) + { + iBasePath.append("/"); + } + iTree = new AABSPTree<ModelContainer *>(); + } + + //========================================================= + MapTree::~MapTree() + { + Array<ModelContainer *> mcArray; + iTree->getMembers(mcArray); + int no = mcArray.size(); + while(no >0) + { + --no; + delete mcArray[no]; + } + delete iTree; + } + //========================================================= + + // just for visual debugging with an external debug class + #ifdef _DEBUG_VMAPS + #ifndef gBoxArray + extern Vector3 p1,p2,p3,p4,p5,p6,p7; + extern Array<AABox>gBoxArray; + extern int gCount1, gCount2, gCount3, gCount4; + extern bool myfound; + #endif + #endif + + //========================================================= + /** + return dist to hit or inf() if no hit + */ + + float MapTree::getIntersectionTime(const Ray& pRay, float pMaxDist, bool pStopAtFirstHit) + { + float firstDistance = inf(); + IntersectionCallBack<ModelContainer> intersectionCallBack; + float t = pMaxDist; + iTree->intersectRay(pRay, intersectionCallBack, t, pStopAtFirstHit, false); +#ifdef _DEBUG_VMAPS + { + if(t < pMaxDist) + { + myfound = true; + p4 = pRay.origin + pRay.direction*t; + } + } +#endif + if(t > 0 && t < inf() && pMaxDist > t) + { + firstDistance = t; + } + return firstDistance; + } + //========================================================= + + bool MapTree::isInLineOfSight(const Vector3& pos1, const Vector3& pos2) + { + bool result = true; + float maxDist = abs((pos2 - pos1).magnitude()); + // direction with length of 1 + Ray ray = Ray::fromOriginAndDirection(pos1, (pos2 - pos1)/maxDist); + float resultDist = getIntersectionTime(ray, maxDist, true); + if(resultDist < maxDist) + { + result = false; + } + return result; + } + //========================================================= + /** + When moving from pos1 to pos2 check if we hit an object. Return true and the position if we hit one + Return the hit pos or the original dest pos + */ + + bool MapTree::getObjectHitPos(const Vector3& pPos1, const Vector3& pPos2, Vector3& pResultHitPos, float pModifyDist) + { + bool result; + float maxDist = abs((pPos2 - pPos1).magnitude()); + Vector3 dir = (pPos2 - pPos1)/maxDist; // direction with length of 1 + Ray ray = Ray::fromOriginAndDirection(pPos1, dir); + float dist = getIntersectionTime(ray, maxDist, false); + if(dist < maxDist) + { + pResultHitPos = pPos1 + dir * dist; + if(pModifyDist < 0) + { + if(abs((pResultHitPos - pPos1).magnitude()) > -pModifyDist) + { + pResultHitPos = pResultHitPos + dir*pModifyDist; + } + else + { + pResultHitPos = pPos1; + } + } + else + { + pResultHitPos = pResultHitPos + dir*pModifyDist; + } + result = true; + } + else + { + pResultHitPos = pPos2; + result = false; + } + return result; + } + + //========================================================= + + float MapTree::getHeight(const Vector3& pPos) + { + float height = inf(); + Vector3 dir = Vector3(0,-1,0); + Ray ray = Ray::fromOriginAndDirection(pPos, dir); // direction with length of 1 + float maxDist = VMapDefinitions::getMaxCanFallDistance(); + float dist = getIntersectionTime(ray, maxDist, false); + if(dist < inf()) + { + height = (pPos + dir * dist).y; + } + return(height); + } + + //========================================================= + + bool MapTree::PrepareTree() + { + iTree->balance(); + return true; + } + + bool MapTree::loadMap(const std::string& pDirFileName, unsigned int pMapTileIdent) + { + bool result = true; + size_t len = iBasePath.length() + pDirFileName.length(); + char *filenameBuffer = new char[len+1]; + if(!hasDirFile(pDirFileName)) + { + FilesInDir filesInDir; + result = false; + sprintf(filenameBuffer, "%s%s", iBasePath.c_str(), pDirFileName.c_str()); + FILE* df = fopen(filenameBuffer, "rb"); + if(df) + { + char lineBuffer[FILENAMEBUFFER_SIZE]; + result = true; + bool newModelLoaded = false; + while(result && (fgets(lineBuffer, FILENAMEBUFFER_SIZE-1, df) != 0)) + { + std::string name = std::string(lineBuffer); + chomp(name); + if(name.length() >1) + { + filesInDir.append(name); + ManagedModelContainer *mc; + if(!isAlreadyLoaded(name)) + { + std::string fname = iBasePath; + fname.append(name); + mc = new ManagedModelContainer(); + result = mc->readFile(fname.c_str()); + if(result) + { + addModelContainer(name, mc); + newModelLoaded = true; + } + } + else + { + mc = getModelContainer(name); + } + mc->incRefCount(); + } + } + if(result && newModelLoaded) + { + iTree->balance(); + } + if(result && ferror(df) != 0) + { + result = false; + } + fclose(df); + if(result) + { + filesInDir.incRefCount(); + addDirFile(pDirFileName, filesInDir); + setLoadedMapTile(pMapTileIdent); + } + } + } + else + { + // Already loaded, so just inc. the ref count if mapTileIdent is new + if(!containsLoadedMapTile(pMapTileIdent)) + { + setLoadedMapTile(pMapTileIdent); + FilesInDir& filesInDir = getDirFiles(pDirFileName); + filesInDir.incRefCount(); + } + } + delete [] filenameBuffer; + return (result); + } + + //========================================================= + + void MapTree::unloadMap(const std::string& dirFileName, unsigned int pMapTileIdent, bool pForce) + { + if(hasDirFile(dirFileName) && (pForce || containsLoadedMapTile(pMapTileIdent))) + { + if(containsLoadedMapTile(pMapTileIdent)) + removeLoadedMapTile(pMapTileIdent); + FilesInDir& filesInDir = getDirFiles(dirFileName); + filesInDir.decRefCount(); + if(filesInDir.getRefCount() <= 0) + { + Array<std::string> fileNames = filesInDir.getFiles(); + bool treeChanged = false; + for(int i=0; i<fileNames.size(); ++i) + { + std::string name = fileNames[i]; + ManagedModelContainer* mc = getModelContainer(name); + mc->decRefCount(); + if(mc->getRefCount() <= 0) + { + iLoadedModelContainer.remove(name); + iTree->remove(mc); + delete mc; + treeChanged = true; + } + } + iLoadedDirFiles.remove(dirFileName); + if(treeChanged) + { + iTree->balance(); + } + } + } + } + + //========================================================= + //========================================================= + + void MapTree::addModelContainer(const std::string& pName, ManagedModelContainer *pMc) + { + iLoadedModelContainer.set(pName, pMc); + iTree->insert(pMc); + } + //========================================================= + //========================================================= + //========================================================= +} diff --git a/src/shared/vmap/VMapManager.h b/src/shared/vmap/VMapManager.h new file mode 100644 index 00000000000..aef9e0fa8f1 --- /dev/null +++ b/src/shared/vmap/VMapManager.h @@ -0,0 +1,173 @@ +/* + * Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _VMAPMANAGER_H +#define _VMAPMANAGER_H + +// load our modified version first !! +#include "AABSPTree.h" +#include "ManagedModelContainer.h" +#include "IVMapManager.h" +#ifdef _VMAP_LOG_DEBUG +#include "DebugCmdLogger.h" +#endif +#include <G3D/Table.h> + +//=========================================================== + +#define DIR_FILENAME_EXTENSION ".vmdir" + +#define FILENAMEBUFFER_SIZE 500 + +/** +This is the main Class to manage loading and unloading of maps, line of sight, height calculation and so on. +For each map or map tile to load it reads a directory file that contains the ModelContainer files used by this map or map tile. +Each global map or instance has its own dynamic BSP-Tree. +The loaded ModelContainers are included in one of these BSP-Trees. +Additionally a table to match map ids and map names is used. +*/ + +// Create a value describing the map tile +#define MAP_TILE_IDENT(x,y) ((x<<8) + y) +//=========================================================== + +namespace VMAP +{ + //=========================================================== + + class FilesInDir + { + private: + int iRefCount; + G3D::Array<std::string> iFiles; + public: + + FilesInDir() { iRefCount = 0; } + void append(const std::string& pName) { iFiles.append(pName); } + void incRefCount() { ++iRefCount; } + void decRefCount() { if(iRefCount > 0) --iRefCount; } + int getRefCount() { return iRefCount; } + const G3D::Array<std::string>& getFiles() const { return iFiles; } + }; + + //=========================================================== + //=========================================================== + //=========================================================== + //=========================================================== + + class MapTree + { + private: + G3D::AABSPTree<ModelContainer *> *iTree; + + // Key: filename, value ModelContainer + G3D::Table<std::string, ManagedModelContainer *> iLoadedModelContainer; + + // Key: dir file name, value FilesInDir + G3D::Table<std::string, FilesInDir> iLoadedDirFiles; + + // Store all the map tile idents that are loaded for that map + // some maps are not splitted into tiles and we have to make sure, not removing the map before all tiles are removed + G3D::Table<unsigned int, bool> iLoadedMapTiles; + std::string iBasePath; + + private: + float getIntersectionTime(const G3D::Ray& pRay, float pMaxDist, bool pStopAtFirstHit); + bool isAlreadyLoaded(const std::string& pName) { return(iLoadedModelContainer.containsKey(pName)); } + void setLoadedMapTile(unsigned int pTileIdent) { iLoadedMapTiles.set(pTileIdent, true); } + void removeLoadedMapTile(unsigned int pTileIdent) { iLoadedMapTiles.remove(pTileIdent); } + bool hasLoadedMapTiles() { return(iLoadedMapTiles.size() > 0); } + bool containsLoadedMapTile(unsigned int pTileIdent) { return(iLoadedMapTiles.containsKey(pTileIdent)); } + public: + ManagedModelContainer *getModelContainer(const std::string& pName) { return(iLoadedModelContainer.get(pName)); } + const bool hasDirFile(const std::string& pDirName) const { return(iLoadedDirFiles.containsKey(pDirName)); } + FilesInDir& getDirFiles(const std::string& pDirName) const { return(iLoadedDirFiles.get(pDirName)); } + public: + MapTree(const char *pBasePath); + ~MapTree(); + + bool isInLineOfSight(const G3D::Vector3& pos1, const G3D::Vector3& pos2); + bool getObjectHitPos(const G3D::Vector3& pos1, const G3D::Vector3& pos2, G3D::Vector3& pResultHitPos, float pModifyDist); + float getHeight(const G3D::Vector3& pPos); + + bool PrepareTree(); + bool loadMap(const std::string& pDirFileName, unsigned int pMapTileIdent); + void addModelContainer(const std::string& pName, ManagedModelContainer *pMc); + void unloadMap(const std::string& dirFileName, unsigned int pMapTileIdent, bool pForce=false); + + void getModelContainer(G3D::Array<ModelContainer *>& pArray ) { iTree->getMembers(pArray); } + const void addDirFile(const std::string& pDirName, const FilesInDir& pFilesInDir) { iLoadedDirFiles.set(pDirName, pFilesInDir); } + size_t size() { return(iTree->size()); } + }; + + //=========================================================== + class MapIdNames + { + public: + std::string iDirName; + std::string iMapGroupName; + }; + + //=========================================================== + class VMapManager : public IVMapManager + { + private: + // Tree to check collision + G3D::Table<unsigned int , MapTree *> iInstanceMapTrees; + G3D::Table<unsigned int , bool> iMapsSplitIntoTiles; + G3D::Table<unsigned int , bool> iIgnoreMapIds; + +#ifdef _VMAP_LOG_DEBUG + CommandFileRW iCommandLogger; +#endif + private: + bool _loadMap(const char* pBasePath, unsigned int pMapId, int x, int y, bool pForceTileLoad=false); + void _unloadMap(unsigned int pMapId, int x, int y); + bool _existsMap(const std::string& pBasePath, unsigned int pMapId, int x, int y, bool pForceTileLoad); + + public: + // public for debug + G3D::Vector3 convertPositionToInternalRep(float x, float y, float z) const; + G3D::Vector3 convertPositionToMangosRep(float x, float y, float z) const; + std::string getDirFileName(unsigned int pMapId) const; + std::string getDirFileName(unsigned int pMapId, int x, int y) const; + MapTree* getInstanceMapTree(int pMapId) { return(iInstanceMapTrees.get(pMapId)); } + public: + VMapManager(); + ~VMapManager(void); + + int loadMap(const char* pBasePath, unsigned int pMapId, int x, int y); + + bool existsMap(const char* pBasePath, unsigned int pMapId, int x, int y); + + void unloadMap(unsigned int pMapId, int x, int y); + void unloadMap(unsigned int pMapId); + + bool isInLineOfSight(unsigned int pMapId, float x1, float y1, float z1, float x2, float y2, float z2) ; + /** + fill the hit pos and return true, if an object was hit + */ + bool getObjectHitPos(unsigned int pMapId, float x1, float y1, float z1, float x2, float y2, float z2, float& rx, float &ry, float& rz, float pModifyDist); + float getHeight(unsigned int pMapId, float x, float y, float z); + + bool processCommand(char *pCommand); // for debug and extensions + + void preventMapsFromBeingUsed(const char* pMapIdString); + }; +} +#endif diff --git a/src/shared/vmap/VMapTools.h b/src/shared/vmap/VMapTools.h new file mode 100644 index 00000000000..b368b18ee86 --- /dev/null +++ b/src/shared/vmap/VMapTools.h @@ -0,0 +1,150 @@ +/* +* Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/> +* +* This program is free software; you can redistribute it and/or modify +* it under the terms of the GNU General Public License as published by +* the Free Software Foundation; either version 2 of the License, or +* (at your option) any later version. +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with this program; if not, write to the Free Software +* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +*/ + +#ifndef _VMAPTOOLS_H +#define _VMAPTOOLS_H + +#include <G3D/CollisionDetection.h> +#include <G3D/AABox.h> + +#include "NodeValueAccess.h" + +/** +The Class is mainly taken from G3D/AABSPTree.h but modified to be able to use our internal data structure. +This is an iterator that helps us analysing the BSP-Trees. +The collision detection is modified to return true, if we are inside an object. +*/ + +namespace VMAP +{ + template<class TValue> + class IntersectionCallBack { + public: + TValue* closestEntity; + G3D::Vector3 hitLocation; + G3D::Vector3 hitNormal; + + void operator()(const G3D::Ray& ray, const TValue* entity, bool pStopAtFirstHit, float& distance) { + entity->intersect(ray, distance, pStopAtFirstHit, hitLocation, hitNormal); + } + }; + + //============================================================== + //============================================================== + //============================================================== + + class MyCollisionDetection + { + private: + public: + + static bool collisionLocationForMovingPointFixedAABox( + const G3D::Vector3& origin, + const G3D::Vector3& dir, + const G3D::AABox& box, + G3D::Vector3& location, + bool& Inside) + { + + // Integer representation of a floating-point value. +#define IR(x) ((G3D::uint32&)x) + + Inside = true; + const G3D::Vector3& MinB = box.low(); + const G3D::Vector3& MaxB = box.high(); + G3D::Vector3 MaxT(-1.0f, -1.0f, -1.0f); + + // Find candidate planes. + for (int i = 0; i < 3; ++i) + { + if (origin[i] < MinB[i]) + { + location[i] = MinB[i]; + Inside = false; + + // Calculate T distances to candidate planes + if (IR(dir[i])) + { + MaxT[i] = (MinB[i] - origin[i]) / dir[i]; + } + } + else if (origin[i] > MaxB[i]) + { + location[i] = MaxB[i]; + Inside = false; + + // Calculate T distances to candidate planes + if (IR(dir[i])) + { + MaxT[i] = (MaxB[i] - origin[i]) / dir[i]; + } + } + } + + if (Inside) + { + // definite hit + location = origin; + return true; + } + + // Get largest of the maxT's for final choice of intersection + int WhichPlane = 0; + if (MaxT[1] > MaxT[WhichPlane]) + { + WhichPlane = 1; + } + + if (MaxT[2] > MaxT[WhichPlane]) + { + WhichPlane = 2; + } + + // Check final candidate actually inside box + if (IR(MaxT[WhichPlane]) & 0x80000000) + { + // Miss the box + return false; + } + + for (int i = 0; i < 3; ++i) + { + if (i != WhichPlane) + { + location[i] = origin[i] + MaxT[WhichPlane] * dir[i]; + if ((location[i] < MinB[i]) || + (location[i] > MaxB[i])) + { + // On this plane we're outside the box extents, so + // we miss the box + return false; + } + } + } + /* + // Choose the normal to be the plane normal facing into the ray + normal = G3D::Vector3::zero(); + normal[WhichPlane] = (dir[WhichPlane] > 0) ? -1.0 : 1.0; + */ + return true; + +#undef IR + } + }; +} +#endif |