diff options
author | maximius <none@none> | 2009-10-17 15:51:44 -0700 |
---|---|---|
committer | maximius <none@none> | 2009-10-17 15:51:44 -0700 |
commit | e585187b248f48b3c6e9247b49fa07c6565d65e5 (patch) | |
tree | 637c5b7ddacf41040bef4ea4f75a97da64c6a9bc /src/shared/vmap | |
parent | 26b5e033ffde3d161382fc9addbfa99738379641 (diff) |
*Backed out changeset 3be01fb200a5
--HG--
branch : trunk
Diffstat (limited to 'src/shared/vmap')
27 files changed, 905 insertions, 0 deletions
diff --git a/src/shared/vmap/AABSPTree.h b/src/shared/vmap/AABSPTree.h index 5fe9c59cf2b..ff4335b6774 100644 --- a/src/shared/vmap/AABSPTree.h +++ b/src/shared/vmap/AABSPTree.h @@ -1,14 +1,21 @@ /** @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" @@ -26,47 +33,60 @@ #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 @@ -76,50 +96,65 @@ namespace G3D { 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 @@ -130,21 +165,26 @@ namespace G3D { 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 @@ -156,75 +196,97 @@ namespace _AABSPTree { 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) { @@ -235,14 +297,18 @@ public: } }; + /** 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]) { @@ -253,15 +319,19 @@ public: } }; + /** 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; @@ -274,31 +344,41 @@ public: } } }; + // 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 @@ -306,6 +386,7 @@ public: increase when performing intersection computations. */ Array<AABox> boundsArray; + /** Creates node with NULL children */ Node() { splitAxis = Vector3::X_AXIS; @@ -315,6 +396,7 @@ public: child[i] = NULL; } } + /** Doesn't clone children. */ @@ -326,6 +408,7 @@ public: 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) { @@ -334,22 +417,26 @@ public: 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. @@ -362,35 +449,44 @@ public: } } } + 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) @@ -410,6 +506,7 @@ public: } } } + /** Clears the member table */ static Node* deserializeStructure(BinaryInput& bi) { if (bi.readUInt8() == 0) { @@ -427,6 +524,7 @@ public: #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 @@ -441,11 +539,13 @@ public: 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. */ @@ -454,6 +554,7 @@ public: 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]; @@ -462,22 +563,27 @@ public: 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) { @@ -485,12 +591,14 @@ public: 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 @@ -499,10 +607,13 @@ public: 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, @@ -511,13 +622,16 @@ public: 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; @@ -526,9 +640,11 @@ public: 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. @@ -538,24 +654,32 @@ public: 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; } @@ -569,12 +693,14 @@ public: 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. @@ -586,16 +712,21 @@ public: 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( @@ -603,28 +734,40 @@ public: 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) { @@ -636,6 +779,7 @@ public: 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)) { @@ -645,6 +789,7 @@ public: 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 @@ -654,16 +799,21 @@ public: 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. @@ -672,20 +822,25 @@ public: 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) { @@ -693,15 +848,20 @@ public: 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. @@ -709,36 +869,47 @@ public: */ 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. @@ -746,14 +917,17 @@ public: 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(); @@ -763,13 +937,16 @@ public: ++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 @@ -780,19 +957,25 @@ public: // 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 @@ -815,6 +998,7 @@ public: root->boundsArray[j] = h->bounds; memberTable.set(Member(h), root); } + } else { // Insert at appropriate tree depth. for (int i = 0; i < valueArray.size(); ++i) { @@ -823,6 +1007,7 @@ public: } } + /** Returns true if this object is in the set, otherwise returns false. O(1) time. @@ -833,10 +1018,12 @@ public: 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, @@ -846,34 +1033,44 @@ public: 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 @@ -888,18 +1085,22 @@ public: 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 @@ -911,33 +1112,41 @@ public: // 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. */ @@ -946,12 +1155,15 @@ protected: 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]) { @@ -959,13 +1171,16 @@ protected: } } } 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] && @@ -976,7 +1191,9 @@ protected: } } } + public: + /** Returns all members inside the set of planes. @param members The results are appended to this array. @@ -985,12 +1202,15 @@ public: 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; @@ -1001,11 +1221,14 @@ public: */ 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 @@ -1019,26 +1242,34 @@ public: 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 @@ -1046,10 +1277,13 @@ public: // 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; @@ -1064,41 +1298,49 @@ public: (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). @@ -1109,6 +1351,7 @@ public: 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])) { @@ -1120,8 +1363,10 @@ public: } } } + return *this; } + private: /** Post increment (much slower than preincrement!). Intentionally overloaded to preclude accidentally slow code. @@ -1132,19 +1377,23 @@ public: ++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 { @@ -1153,16 +1402,19 @@ public: } }; + /** 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. @@ -1174,18 +1426,25 @@ public: 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; @@ -1194,24 +1453,30 @@ public: } } }; + // 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. */ @@ -1222,9 +1487,12 @@ public: float& distance, bool pStopAtFirstHit, bool intersectCallbackIsFast = false) const { + root->intersectRay(ray, intersectCallback, distance, pStopAtFirstHit, intersectCallbackIsFast); + } + /** @param members The results are appended to this array. */ @@ -1232,9 +1500,11 @@ public: if (root == NULL) { return; } + AABox box; sphere.getBounds(box); root->getIntersectingMembers(box, sphere, members, true); + } #if 0 /** @@ -1245,6 +1515,7 @@ public: void serializeStructure(BinaryOutput& bo) const { Node::serializeStructure(root, bo); } + /** Clears the member table */ void deserializeStructure(BinaryInput& bi) { clear(); @@ -1262,6 +1533,7 @@ public: } } + /** C++ STL style iterator variable. See begin(). Overloads the -> (dereference) operator, so this acts like a pointer @@ -1270,17 +1542,23 @@ public: 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. */ @@ -1288,6 +1566,7 @@ public: ++it; return *this; } + private: /** Post increment (slower than preincrement). Intentionally unimplemented to prevent slow code. @@ -1298,17 +1577,21 @@ public: 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 @@ -1319,6 +1602,7 @@ public: return Iterator(memberTable.begin()); } + /** C++ STL style iterator method. Returns one after the last iterator element. @@ -1327,7 +1611,11 @@ public: return Iterator(memberTable.end()); } }; + } + #endif + + diff --git a/src/shared/vmap/BaseModel.cpp b/src/shared/vmap/BaseModel.cpp index 335a9a128e0..2ffd5672218 100644 --- a/src/shared/vmap/BaseModel.cpp +++ b/src/shared/vmap/BaseModel.cpp @@ -17,12 +17,16 @@ * 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++) @@ -30,12 +34,15 @@ namespace VMAP 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; @@ -45,16 +52,21 @@ namespace VMAP 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, @@ -64,7 +76,9 @@ namespace VMAP 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 @@ -73,9 +87,12 @@ namespace VMAP 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 index 1e896bb62ec..098e1d9381b 100644 --- a/src/shared/vmap/BaseModel.h +++ b/src/shared/vmap/BaseModel.h @@ -17,22 +17,29 @@ * 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: @@ -48,31 +55,48 @@ namespace VMAP 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 index e4aa5e08893..39d1165f115 100644 --- a/src/shared/vmap/CoordModelMapping.cpp +++ b/src/shared/vmap/CoordModelMapping.cpp @@ -17,34 +17,45 @@ * 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> #include <stdio.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)); } + const std::string CMappingEntry::getKeyString( unsigned int pMapId, int pXPos, int pYPos ) { char b[100]; sprintf(b,"%03u_%d_%d", pMapId, pXPos, pYPos); return(std::string(b)); } + //============================================================ //============================================================ //============================================================ + CoordModelMapping::~CoordModelMapping() { Array<std::string> keys = iMapObjectFiles.getKeys(); @@ -58,7 +69,9 @@ namespace VMAP } } } + //============================================================ + int findPosChar(const char *namebuffer, char pSearch, int pCount) { int result = -1; @@ -87,7 +100,9 @@ namespace VMAP printf("ERROR: Can't open file: %s\n",pDirectoryFileName.c_str()); return false; } + char buffer[500+1]; + CMappingEntry* cMappingEntry; while(fgets(buffer, 500, f)) { @@ -96,7 +111,9 @@ namespace VMAP 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))) @@ -107,6 +124,7 @@ namespace VMAP // 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])); @@ -120,6 +138,7 @@ namespace VMAP xpos = 0; // store all files under the groupKey ypos = 0; } + std::string key = CMappingEntry::getKeyString(mapId, xpos, ypos); cMappingEntry = getCMappingEntry(key); if(cMappingEntry == 0) @@ -136,15 +155,19 @@ namespace VMAP fclose(f); return true; } + //============================================================ + 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()) { @@ -170,6 +193,8 @@ namespace VMAP } return result; } + //================================================================= + } diff --git a/src/shared/vmap/CoordModelMapping.h b/src/shared/vmap/CoordModelMapping.h index 8600620cc99..7684bf1b373 100644 --- a/src/shared/vmap/CoordModelMapping.h +++ b/src/shared/vmap/CoordModelMapping.h @@ -17,32 +17,43 @@ * 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 <cstdio> #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(const std::string& pStr) { iMainFiles.append(pStr); } void appendToSingle(const std::string& pStr) { iSingeFiles.append(pStr); } + size_t size() { return (iMainFiles.size() + iSingeFiles.size()); } }; + //===================================================== + class CMappingEntry { private: @@ -50,6 +61,7 @@ namespace VMAP int yPos; unsigned int iMapId; G3D::Array<std::string> iFilenames; + public: CMappingEntry() { }; CMappingEntry(unsigned int pMapId, const int pXPos, const int pYPos) @@ -58,12 +70,17 @@ namespace VMAP 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); + }; + //===================================================== + class CoordModelMapping { private: @@ -72,10 +89,12 @@ namespace VMAP 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)) @@ -83,14 +102,19 @@ namespace VMAP 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(const std::string& pName) { size_t spos; + spos = pName.find_last_of('/'); std::string basename = pName.substr(0, spos); spos = basename.find_last_of('/'); @@ -98,9 +122,11 @@ namespace VMAP unsigned int mapId = atoi(groupname.c_str()); return(mapId); } + const G3D::Array<unsigned int>& getMaps() const { return iMapIds; } bool isAlreadyProcessedSingleFile(const std::string& pName) const { return iProcesseSingleFiles.containsKey(pName); } void addAlreadyProcessedSingleFile(const std::string& pName) { iProcesseSingleFiles.set(pName,pName); } + inline void addWorldAreaMap(unsigned int pMapId) { if(!iWorldAreaGroups.contains(pMapId)) @@ -110,6 +136,7 @@ namespace VMAP } 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 index 5b5fbebdd59..c899606045b 100644 --- a/src/shared/vmap/DebugCmdLogger.cpp +++ b/src/shared/vmap/DebugCmdLogger.cpp @@ -17,12 +17,17 @@ * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ + #include <cstdio> + #include "DebugCmdLogger.h" #include <stdio.h> + using namespace G3D; + namespace VMAP { + bool CommandFileRW::appendCmd(const Command& #ifdef _DEBUG pCommand @@ -50,7 +55,9 @@ namespace VMAP return true; #endif } + //========================================================= + bool CommandFileRW::appendCmds(const Array<Command>& #ifdef _DEBUG pCmdArray @@ -67,6 +74,7 @@ namespace VMAP else f = fopen(iFileName.c_str(), "ab"); resetfile = false; + if(f) { result = true; @@ -86,7 +94,9 @@ namespace VMAP return true; #endif } + //========================================================= + bool CommandFileRW::getNewCommands(Array<Command>& pCmdArray) { bool result = false; diff --git a/src/shared/vmap/DebugCmdLogger.h b/src/shared/vmap/DebugCmdLogger.h index f67687343c1..5493ab6f332 100644 --- a/src/shared/vmap/DebugCmdLogger.h +++ b/src/shared/vmap/DebugCmdLogger.h @@ -17,16 +17,21 @@ * 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 { @@ -41,6 +46,7 @@ namespace VMAP TEST_HEIGHT, TEST_OBJECT_HIT, }; + class Command { int iType; @@ -48,11 +54,14 @@ namespace VMAP 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; } @@ -78,9 +87,12 @@ namespace VMAP 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: @@ -97,9 +109,11 @@ namespace VMAP 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 index 40bb3164c0e..243a15aef73 100644 --- a/src/shared/vmap/IVMapManager.h +++ b/src/shared/vmap/IVMapManager.h @@ -17,36 +17,50 @@ * 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; /** @@ -58,6 +72,7 @@ namespace VMAP 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 @@ -68,9 +83,11 @@ namespace VMAP 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. @@ -79,6 +96,7 @@ namespace VMAP */ virtual void preventMapsFromBeingUsed(const char* pMapIdString) =0; }; + } #endif diff --git a/src/shared/vmap/ManagedModelContainer.cpp b/src/shared/vmap/ManagedModelContainer.cpp index a5258d86660..c7bfefe7179 100644 --- a/src/shared/vmap/ManagedModelContainer.cpp +++ b/src/shared/vmap/ManagedModelContainer.cpp @@ -17,16 +17,22 @@ * 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 index c909aa878cf..e6862f915c7 100644 --- a/src/shared/vmap/ManagedModelContainer.h +++ b/src/shared/vmap/ManagedModelContainer.h @@ -17,16 +17,21 @@ * 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 { @@ -35,10 +40,12 @@ namespace VMAP 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 index 94d453079d2..4a722d2585b 100644 --- a/src/shared/vmap/ModelContainer.cpp +++ b/src/shared/vmap/ModelContainer.cpp @@ -17,12 +17,17 @@ * 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 { //========================================================== @@ -34,25 +39,32 @@ namespace VMAP 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++) { @@ -62,6 +74,7 @@ namespace VMAP nNodes += m->getNNodes(); nTriangles += m->getNTriangles(); } + if(pNode.child[0] != 0) { countSubModelsAndNodesAndTriangles(*pNode.child[0], nSubModels, nNodes, nTriangles); @@ -72,6 +85,7 @@ namespace VMAP } } //========================================================== + 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 @@ -79,20 +93,26 @@ namespace VMAP 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()); @@ -105,6 +125,7 @@ namespace VMAP } */ // get absolute bounds + if(pNode.child[0] != 0) { treeNode.setChildPos(0, pTreeNodePos); @@ -115,45 +136,62 @@ namespace VMAP 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) { @@ -161,11 +199,13 @@ namespace VMAP 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; @@ -173,28 +213,35 @@ namespace VMAP 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; @@ -207,6 +254,7 @@ namespace VMAP if(rf) { free(); + result = true; char magic[8]; // Ignore the added magic header fread(magic,1,8,rf); @@ -219,6 +267,7 @@ namespace VMAP 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; @@ -226,25 +275,32 @@ namespace VMAP 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) @@ -260,12 +316,15 @@ namespace VMAP } 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 @@ -275,6 +334,7 @@ namespace VMAP 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; @@ -282,12 +342,16 @@ namespace VMAP 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) { @@ -302,7 +366,9 @@ namespace VMAP { pAABox = pMc.getAABoxBounds(); } + //================================================================= + void getBounds(const ModelContainer* pMc, G3D::AABox& pAABox) { pAABox = pMc->getAABoxBounds(); diff --git a/src/shared/vmap/ModelContainer.h b/src/shared/vmap/ModelContainer.h index 6a595bec39f..abc96261050 100644 --- a/src/shared/vmap/ModelContainer.h +++ b/src/shared/vmap/ModelContainer.h @@ -17,18 +17,23 @@ * 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 { /** @@ -39,41 +44,65 @@ namespace VMAP 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); diff --git a/src/shared/vmap/NodeValueAccess.h b/src/shared/vmap/NodeValueAccess.h index 01c085be834..54fc5ee99b6 100644 --- a/src/shared/vmap/NodeValueAccess.h +++ b/src/shared/vmap/NodeValueAccess.h @@ -17,25 +17,32 @@ * 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; } }; diff --git a/src/shared/vmap/ShortBox.h b/src/shared/vmap/ShortBox.h index f2d87bc6abe..0e98677aa9e 100644 --- a/src/shared/vmap/ShortBox.h +++ b/src/shared/vmap/ShortBox.h @@ -17,18 +17,24 @@ * 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: @@ -42,15 +48,18 @@ namespace VMAP 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 @@ -61,7 +70,9 @@ namespace VMAP extern bool myfound; #endif #endif + static const G3D::Vector3 dummyZeroPosition = G3D::Vector3(0,0,0); + class TriangleBox { private: @@ -74,16 +85,20 @@ namespace VMAP _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]); @@ -94,15 +109,19 @@ namespace VMAP 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; @@ -113,6 +132,7 @@ namespace VMAP 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); @@ -125,6 +145,7 @@ namespace VMAP } } }; + } #endif diff --git a/src/shared/vmap/ShortVector.h b/src/shared/vmap/ShortVector.h index 4de8cfde73d..5f0fb7d9fd8 100644 --- a/src/shared/vmap/ShortVector.h +++ b/src/shared/vmap/ShortVector.h @@ -17,25 +17,31 @@ * 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; @@ -59,6 +65,7 @@ namespace VMAP 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)); } @@ -70,6 +77,7 @@ namespace VMAP iY = float2Short(pVector.y); iZ = float2Short(pVector.z); } + inline ShortVector(float pX, float pY, float pZ) { iX = float2Short(pX); @@ -88,10 +96,13 @@ namespace VMAP 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; @@ -100,6 +111,7 @@ namespace VMAP if(pShortVector.iZ > iZ) { result.iZ = iZ; } return(result); } + inline ShortVector max(const ShortVector pShortVector) { ShortVector result = pShortVector; @@ -108,14 +120,17 @@ namespace VMAP 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 index f04090c6269..370c80062d6 100644 --- a/src/shared/vmap/SubModel.cpp +++ b/src/shared/vmap/SubModel.cpp @@ -17,13 +17,18 @@ * 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 @@ -32,16 +37,19 @@ namespace VMAP { 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()); } + //========================================================== //========================================================== //========================================================== @@ -53,7 +61,9 @@ namespace VMAP iNodesPos = pNodesPos; iHasInternalMemAlloc = false; } + //========================================================== + SubModel::~SubModel(void) { if(iHasInternalMemAlloc) @@ -61,10 +71,13 @@ namespace VMAP free(); } } + //========================================================== + bool SubModel::operator==(const SubModel& pSm2) const { bool result = false; + if(getNNodes() == pSm2.getNNodes() && getNTriangles() == pSm2.getNTriangles() && getBasePosition() == pSm2.getBasePosition() && @@ -76,6 +89,7 @@ namespace VMAP return result; } //========================================================== + enum BIN_POSITIONS { BP_iNTriangles=8, @@ -99,14 +113,18 @@ namespace VMAP 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); @@ -116,15 +134,20 @@ namespace VMAP 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]; @@ -132,8 +155,10 @@ namespace VMAP 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); @@ -144,29 +169,39 @@ namespace VMAP 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 @@ -177,6 +212,7 @@ namespace VMAP extern bool myfound; #endif #endif + //========================================================== void SubModel::intersect(const G3D::Ray& pRay, float& pMaxDist, bool pStopAtFirstHit, G3D::Vector3& /*pOutLocation*/, G3D::Vector3& /*pOutNormal*/) const { @@ -189,12 +225,16 @@ namespace VMAP #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) { @@ -206,5 +246,6 @@ namespace VMAP } } //========================================================== + } diff --git a/src/shared/vmap/SubModel.h b/src/shared/vmap/SubModel.h index d562f36d94e..89ea9b91d7b 100644 --- a/src/shared/vmap/SubModel.h +++ b/src/shared/vmap/SubModel.h @@ -17,15 +17,19 @@ * 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 { /** @@ -46,30 +50,44 @@ namespace VMAP #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> @@ -77,6 +95,7 @@ namespace VMAP 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); diff --git a/src/shared/vmap/TileAssembler.cpp b/src/shared/vmap/TileAssembler.cpp index 509696f39a2..75997a847a2 100644 --- a/src/shared/vmap/TileAssembler.cpp +++ b/src/shared/vmap/TileAssembler.cpp @@ -17,20 +17,27 @@ * 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); @@ -39,8 +46,10 @@ namespace VMAP out = ixMatrix * out; out = iyMatrix * out; return(out); + } //================================================================= + TileAssembler::TileAssembler(const std::string& pSrcDirName, const std::string& pDestDirName) { iCurrentUniqueNameId = 0; @@ -50,12 +59,16 @@ namespace VMAP //mkdir(iDestDir); init(); } + //================================================================= + TileAssembler::~TileAssembler() { delete iCoordModelMapping; } + //================================================================= + void TileAssembler::init() { iCoordModelMapping = new CoordModelMapping(); @@ -65,16 +78,20 @@ namespace VMAP addWorldAreaMapId(571); //Expansion02 } //================================================================= + 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; @@ -83,11 +100,14 @@ namespace VMAP 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); @@ -105,7 +125,9 @@ namespace VMAP dirEntry.append(".vmap"); return(dirEntry); } + //================================================================= + void emptyArray(Array<ModelContainer*>& mc) { int no=mc.size(); @@ -116,6 +138,7 @@ namespace VMAP mc.remove(no); } } + //================================================================= bool TileAssembler::convertWorld() { @@ -126,22 +149,27 @@ namespace VMAP ::g_df = fopen("../TileAssembler_release.txt", "wb"); # endif #endif + std::string fname = iSrcDir; fname.append("/"); fname.append("dir"); iCoordModelMapping->setModelNameFilterMethod(iFilterMethod); + printf("Read coordinate mapping...\n"); if(!iCoordModelMapping->readCoordinateMapping(fname)) return false; + Array<unsigned int> mapIds = iCoordModelMapping->getMaps(); if(mapIds.size() == 0) { printf("Fatal error: empty map list!\n"); return false; } + for(int i=0; i<mapIds.size(); ++i) { unsigned int mapId = mapIds[i]; + #ifdef _ASSEMBLER_DEBUG if(mapId == 0) // "Azeroth" just for debug { @@ -172,12 +200,15 @@ namespace VMAP { sprintf(buffer, "%03u",mapId); dirname = std::string(buffer); + // prevent spam for small maps if(x==0 && y==0) printf("%s...\n",dirname.c_str()); } + bool result = fillModelContainerArray(dirname, mapId, x, y, mc); emptyArray(mc); + if(!result) return false; } @@ -187,15 +218,20 @@ namespace VMAP #ifdef _ASSEMBLER_DEBUG if(::g_df) fclose(::g_df); #endif + return true; } + //================================================================= + bool TileAssembler::fillModelContainerArray(const std::string& pDirFileName, unsigned int pMapId, int pXPos, int pYPos, Array<ModelContainer*>& pMC) { ModelContainer* modelContainer; + NameCollection nameCollection = iCoordModelMapping->getFilenamesForCoordinate(pMapId, pXPos, pYPos); if(nameCollection.size() == 0) return true; // no data... + char dirfilename[500]; sprintf(dirfilename,"%s/%s.vmdir",iDestDir.c_str(),pDirFileName.c_str()); FILE *dirfile = fopen(dirfilename, "ab"); @@ -204,8 +240,10 @@ namespace VMAP printf("ERROR: Can't create file %s",dirfilename); return false; } + char destnamebuffer[500]; char fullnamedestnamebuffer[500]; + if(nameCollection.iMainFiles.size() >0) { sprintf(destnamebuffer,"%03u_%i_%i.vmap",pMapId, pYPos, pXPos); // flip it here too @@ -241,8 +279,10 @@ namespace VMAP 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()); @@ -255,10 +295,13 @@ namespace VMAP } ++pos; } + fclose(dirfile); return true; } + //================================================================= + void removeEntriesFromTree(AABSPTree<SubModel *>* pTree) { Array<SubModel *> submodelArray; @@ -270,18 +313,24 @@ namespace VMAP 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; @@ -296,9 +345,12 @@ namespace VMAP modelContainer->writeFile(pDestFileName); } removeEntriesFromTree(mainTree); + delete mainTree; + return(modelContainer); } + //================================================================= bool TileAssembler::readRawFile(std::string& pModelFilename, ModelPosition& pModelPosition, AABSPTree<SubModel *> *pMainTree) { @@ -317,14 +369,18 @@ namespace VMAP filename.append(baseModelFilename); rf = fopen(filename.c_str(), "rb"); } + if(!rf) { printf("ERROR: Can't open model file in form: %s",pModelFilename.c_str()); printf("... or form: %s",filename.c_str() ); return false; } + char ident[8]; + int trianglecount =0; + #ifdef _ASSEMBLER_DEBUG int startgroup = 0; //2; int endgroup = INT_MAX; //2; @@ -335,11 +391,13 @@ namespace VMAP int startgroup = 0; int endgroup = INT_MAX; #endif + // temporary use defines to simplify read/check code (close file and return at fail) #define READ_OR_RETURN(V,S) if(fread((V), (S), 1, rf) != 1) { \ fclose(rf); return(false); } #define CMP_OR_RETURN(V,S) if(strcmp((V),(S)) != 0) { \ fclose(rf); return(false); } + READ_OR_RETURN(&ident, 8); if(strcmp(ident, "VMAP001") == 0) { @@ -350,6 +408,7 @@ namespace VMAP // we have to read one int. This is needed during the export and we have to skip it here int tempNVectors; READ_OR_RETURN(&tempNVectors, sizeof(int)); + } else { @@ -361,13 +420,17 @@ namespace VMAP char blockId[5]; blockId[4] = 0; int blocksize; + READ_OR_RETURN(&groups, sizeof(G3D::uint32)); + 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>(); + // add free gtree at fail #undef READ_OR_RETURN #undef CMP_OR_RETURN @@ -375,8 +438,10 @@ namespace VMAP fclose(rf); delete gtree; return(false); } #define CMP_OR_RETURN(V,S) if(strcmp((V),(S)) != 0) { \ fclose(rf); delete gtree; return(false); } + G3D::uint32 flags; READ_OR_RETURN(&flags, sizeof(G3D::uint32)); + G3D::uint32 branches; READ_OR_RETURN(&blockId, 4); CMP_OR_RETURN(blockId, "GRP "); @@ -388,6 +453,7 @@ namespace VMAP // indexes for each branch (not used jet) READ_OR_RETURN(&indexes, sizeof(G3D::uint32)); } + // ---- indexes READ_OR_RETURN(&blockId, 4); CMP_OR_RETURN(blockId, "INDX"); @@ -405,13 +471,16 @@ namespace VMAP } delete[] indexarray; } + // ---- vectors READ_OR_RETURN(&blockId, 4); CMP_OR_RETURN(blockId, "VERT"); READ_OR_RETURN(&blocksize, sizeof(int)); unsigned int nvectors; READ_OR_RETURN(&nvectors, sizeof(int)); + float *vectorarray = 0; + // add vectorarray free #undef READ_OR_RETURN #undef CMP_OR_RETURN @@ -419,6 +488,7 @@ namespace VMAP fclose(rf); delete gtree; delete[] vectorarray; return(false); } #define CMP_OR_RETURN(V,S) if(strcmp((V),(S)) != 0) { \ fclose(rf); delete gtree; delete[] vectorarray; return(false); } + if(nvectors >0) { vectorarray = new float[nvectors*sizeof(float)*3]; @@ -434,22 +504,27 @@ namespace VMAP 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]] ); @@ -460,13 +535,16 @@ namespace VMAP gtree->insert(t); } } + // drop of temporary use defines #undef READ_OR_RETURN #undef CMP_OR_RETURN + if(vectorarray != 0) { delete vectorarray; } + if(gtree->size() >0) { gtree->balance(); @@ -486,31 +564,40 @@ namespace VMAP fclose(rf); return true; } + //================================================================= + bool TileAssembler::fillModelIntoTree(AABSPTree<SubModel *> *pMainTree, const Vector3& pBasePos, std::string& pPos, std::string& pModelFilename) { ModelPosition modelPosition; getModelPosition(pPos, modelPosition); // all should be relative to object base position modelPosition.moveToBasePos(pBasePos); + modelPosition.init(); + return readRawFile(pModelFilename, modelPosition, pMainTree); } + //================================================================= 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 index 27cddbc2c1c..d2183794a9e 100644 --- a/src/shared/vmap/TileAssembler.h +++ b/src/shared/vmap/TileAssembler.h @@ -17,14 +17,19 @@ * 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 { /** @@ -32,6 +37,7 @@ namespace VMAP To start the conversion call convertWorld(). */ //=============================================== + class ModelPosition { private: @@ -44,15 +50,18 @@ namespace VMAP 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: @@ -62,13 +71,17 @@ namespace VMAP 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); diff --git a/src/shared/vmap/TreeNode.cpp b/src/shared/vmap/TreeNode.cpp index d40f2acde25..c884f9b3b1d 100644 --- a/src/shared/vmap/TreeNode.cpp +++ b/src/shared/vmap/TreeNode.cpp @@ -17,10 +17,14 @@ * 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) @@ -28,6 +32,7 @@ namespace VMAP else return(NULL); } + //================================================================= //================================================================= //================================================================= diff --git a/src/shared/vmap/TreeNode.h b/src/shared/vmap/TreeNode.h index 2b14de9ac33..1b9532001e5 100644 --- a/src/shared/vmap/TreeNode.h +++ b/src/shared/vmap/TreeNode.h @@ -17,14 +17,18 @@ * 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 { /** @@ -32,7 +36,9 @@ namespace VMAP 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: @@ -54,19 +60,30 @@ namespace VMAP 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) && @@ -76,6 +93,7 @@ namespace VMAP (iBounds == n.iBounds) && (iNumberOfValues == n.iNumberOfValues)); } + inline bool operator!=(const TreeNode& n) const { return !((iSplitLocation == n.iSplitLocation) && @@ -85,6 +103,7 @@ namespace VMAP (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 @@ -93,10 +112,13 @@ namespace VMAP 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, @@ -110,6 +132,7 @@ namespace VMAP // 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); @@ -122,9 +145,11 @@ namespace VMAP 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. @@ -133,24 +158,32 @@ namespace VMAP 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; } @@ -164,6 +197,7 @@ namespace VMAP 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); diff --git a/src/shared/vmap/VMapDefinitions.h b/src/shared/vmap/VMapDefinitions.h index 811546d44de..fd28a91d515 100644 --- a/src/shared/vmap/VMapDefinitions.h +++ b/src/shared/vmap/VMapDefinitions.h @@ -17,19 +17,23 @@ * 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 index c979a33ff82..5189f79daba 100644 --- a/src/shared/vmap/VMapFactory.cpp +++ b/src/shared/vmap/VMapFactory.cpp @@ -17,17 +17,23 @@ * 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; @@ -49,10 +55,12 @@ namespace VMAP } return(result); } + //=============================================== /** parameter: String of map ids. Delimiter = "," */ + void VMapFactory::preventSpellsFromBeingTestedForLoS(const char* pSpellIdString) { if(!iIgnoreSpellIds) @@ -69,11 +77,14 @@ namespace VMAP } } } + //=============================================== + bool VMapFactory::checkSpellForLoS(unsigned int pSpellId) { return(!iIgnoreSpellIds->containsKey(pSpellId)); } + //=============================================== // just return the instance IVMapManager* VMapFactory::createOrGetVMapManager() @@ -82,6 +93,7 @@ namespace VMAP gVMapManager= new VMapManager(); // should be taken from config ... Please change if you like :-) return gVMapManager; } + //=============================================== // delete all internal data structures void VMapFactory::clear() diff --git a/src/shared/vmap/VMapFactory.h b/src/shared/vmap/VMapFactory.h index ca529bd2715..f3375d723c1 100644 --- a/src/shared/vmap/VMapFactory.h +++ b/src/shared/vmap/VMapFactory.h @@ -17,23 +17,30 @@ * 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 index 782c9d39c8a..342da0eb9e2 100644 --- a/src/shared/vmap/VMapManager.cpp +++ b/src/shared/vmap/VMapManager.cpp @@ -17,12 +17,17 @@ * 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 @@ -30,7 +35,9 @@ namespace VMAP iCommandLogger.setResetFile(); #endif } + //========================================================= + VMapManager::~VMapManager(void) { Array<unsigned int > keyArray = iInstanceMapTrees.getKeys(); @@ -40,7 +47,9 @@ namespace VMAP iInstanceMapTrees.remove(keyArray[i]); } } + //========================================================= + Vector3 VMapManager::convertPositionToInternalRep(float x, float y, float z) const { float pos[3]; @@ -51,9 +60,12 @@ namespace VMAP double mid = full/2.0; pos[0] = full- (pos[0] + mid); pos[2] = full- (pos[2] + mid); + return(Vector3(pos)); } + //========================================================= + Vector3 VMapManager::convertPositionToTrinityRep(float x, float y, float z) const { float pos[3]; @@ -64,19 +76,24 @@ namespace VMAP 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)); } @@ -98,6 +115,7 @@ namespace VMAP } } //========================================================= + void chompAndTrim(std::string& str) { while(str.length() >0) @@ -125,8 +143,10 @@ namespace VMAP } } } + //========================================================= // result false, if no more id are found + bool getNextMapId(const std::string& pString, unsigned int& pStartPos, unsigned int& pId) { bool result = false; @@ -148,12 +168,14 @@ namespace VMAP } 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) @@ -168,7 +190,9 @@ namespace VMAP } } } + //========================================================= + int VMapManager::loadMap(const char* pBasePath, unsigned int pMapId, int x, int y) { int result = VMAP_LOAD_RESULT_IGNORED; @@ -201,8 +225,10 @@ namespace VMAP } 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; @@ -223,6 +249,7 @@ namespace VMAP } else instanceTree = iInstanceMapTrees.get(pMapId); + unsigned int mapTileIdent = MAP_TILE_IDENT(x,y); result = instanceTree->loadMap(dirFileName, mapTileIdent); if(!result) // remove on fail @@ -235,7 +262,9 @@ namespace VMAP } return(result); } + //========================================================= + bool VMapManager::_existsMap(const std::string& pBasePath, unsigned int pMapId, int x, int y, bool pForceTileLoad) { bool result = false; @@ -275,7 +304,9 @@ namespace VMAP } return result; } + //========================================================= + bool VMapManager::existsMap(const char* pBasePath, unsigned int pMapId, int x, int y) { std::string basePath = std::string(pBasePath); @@ -295,17 +326,22 @@ namespace VMAP } 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)) @@ -329,7 +365,9 @@ namespace VMAP } } } + //========================================================= + void VMapManager::unloadMap(unsigned int pMapId) { if(iInstanceMapTrees.containsKey(pMapId)) @@ -350,6 +388,7 @@ namespace VMAP } } //========================================================== + bool VMapManager::isInLineOfSight(unsigned int pMapId, float x1, float y1, float z1, float x2, float y2, float z2) { bool result = true; @@ -404,10 +443,12 @@ namespace VMAP } return result; } + //========================================================= /** get height or INVALID_HEIGHT if to height was calculated */ + //int gGetHeightCounter = 0; float VMapManager::getHeight(unsigned int pMapId, float x, float y, float z) { @@ -429,6 +470,7 @@ namespace VMAP } return(height); } + //========================================================= /** used for debugging @@ -440,6 +482,7 @@ namespace VMAP if(cmd == "startlog") { #ifdef _VMAP_LOG_DEBUG + iCommandLogger.enableWriting(true); #endif result = true; @@ -466,9 +509,11 @@ namespace VMAP } return result; } + //========================================================= //========================================================= //========================================================= + MapTree::MapTree(const char* pBaseDir) { iBasePath = std::string(pBaseDir); @@ -478,6 +523,7 @@ namespace VMAP } iTree = new AABSPTree<ModelContainer *>(); } + //========================================================= MapTree::~MapTree() { @@ -492,6 +538,7 @@ namespace VMAP delete iTree; } //========================================================= + // just for visual debugging with an external debug class #ifdef _DEBUG_VMAPS #ifndef gBoxArray @@ -501,10 +548,12 @@ namespace VMAP 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(); @@ -527,6 +576,7 @@ namespace VMAP return firstDistance; } //========================================================= + bool MapTree::isInLineOfSight(const Vector3& pos1, const Vector3& pos2) { bool result = true; @@ -545,6 +595,7 @@ namespace VMAP 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; @@ -579,7 +630,9 @@ namespace VMAP } return result; } + //========================================================= + float MapTree::getHeight(const Vector3& pPos) { float height = inf(); @@ -593,12 +646,15 @@ namespace VMAP } return(height); } + //========================================================= + bool MapTree::PrepareTree() { iTree->balance(); return true; } + bool MapTree::loadMap(const std::string& pDirFileName, unsigned int pMapTileIdent) { bool result = true; @@ -669,7 +725,9 @@ namespace VMAP } return (result); } + //========================================================= + void MapTree::unloadMap(const std::string& dirFileName, unsigned int pMapTileIdent, bool pForce) { if(hasDirFile(dirFileName) && (pForce || containsLoadedMapTile(pMapTileIdent))) @@ -703,8 +761,10 @@ namespace VMAP } } } + //========================================================= //========================================================= + void MapTree::addModelContainer(const std::string& pName, ManagedModelContainer *pMc) { iLoadedModelContainer.set(pName, pMc); diff --git a/src/shared/vmap/VMapManager.h b/src/shared/vmap/VMapManager.h index 4e0e6bdfb18..bfeba3cfe67 100644 --- a/src/shared/vmap/VMapManager.h +++ b/src/shared/vmap/VMapManager.h @@ -17,8 +17,10 @@ * 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" @@ -27,9 +29,13 @@ #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. @@ -37,18 +43,22 @@ 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; } @@ -56,22 +66,28 @@ namespace VMAP 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)); } @@ -86,17 +102,21 @@ namespace VMAP 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 { @@ -104,6 +124,7 @@ namespace VMAP std::string iDirName; std::string iMapGroupName; }; + //=========================================================== class VMapManager : public IVMapManager { @@ -112,6 +133,7 @@ namespace VMAP 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 @@ -119,6 +141,7 @@ namespace VMAP 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; @@ -129,17 +152,23 @@ namespace VMAP 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); }; } diff --git a/src/shared/vmap/VMapTools.h b/src/shared/vmap/VMapTools.h index 2460bf9dcc4..3af3a29310d 100644 --- a/src/shared/vmap/VMapTools.h +++ b/src/shared/vmap/VMapTools.h @@ -17,16 +17,21 @@ * 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> @@ -35,17 +40,21 @@ namespace VMAP 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, @@ -53,12 +62,15 @@ namespace VMAP 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) { @@ -66,6 +78,7 @@ namespace VMAP { location[i] = MinB[i]; Inside = false; + // Calculate T distances to candidate planes if (IR(dir[i])) { @@ -76,6 +89,7 @@ namespace VMAP { location[i] = MaxB[i]; Inside = false; + // Calculate T distances to candidate planes if (IR(dir[i])) { @@ -83,28 +97,33 @@ namespace VMAP } } } + 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) @@ -125,6 +144,7 @@ namespace VMAP normal[WhichPlane] = (dir[WhichPlane] > 0) ? -1.0 : 1.0; */ return true; + #undef IR } }; |