From cf1bdcef46da21a9c0b03a7a574d762ff1ce7998 Mon Sep 17 00:00:00 2001 From: Mathias Froehlich Date: Fri, 24 Aug 2012 21:20:40 +0200 Subject: [PATCH] bvh: Add an abstract pager implementation. Implement a paging implementation for bounding volume hierarchy nodes. We will need this for hla clients that need ground queries. --- simgear/bvh/BVHBoundingBoxVisitor.hxx | 3 + simgear/bvh/BVHLineSegmentVisitor.cxx | 9 + simgear/bvh/BVHLineSegmentVisitor.hxx | 1 + simgear/bvh/BVHNearestPointVisitor.hxx | 7 + simgear/bvh/BVHNode.hxx | 2 + simgear/bvh/BVHPageNode.cxx | 40 +++++ simgear/bvh/BVHPageNode.hxx | 66 +++++++ simgear/bvh/BVHPageRequest.cxx | 26 +++ simgear/bvh/BVHPageRequest.hxx | 42 +++++ simgear/bvh/BVHPager.cxx | 236 +++++++++++++++++++++++++ simgear/bvh/BVHPager.hxx | 60 +++++++ simgear/bvh/BVHSubTreeCollector.cxx | 16 ++ simgear/bvh/BVHSubTreeCollector.hxx | 1 + simgear/bvh/BVHVisitor.hxx | 4 +- simgear/bvh/CMakeLists.txt | 6 + 15 files changed, 518 insertions(+), 1 deletion(-) create mode 100644 simgear/bvh/BVHPageNode.cxx create mode 100644 simgear/bvh/BVHPageNode.hxx create mode 100644 simgear/bvh/BVHPageRequest.cxx create mode 100644 simgear/bvh/BVHPageRequest.hxx create mode 100644 simgear/bvh/BVHPager.cxx create mode 100644 simgear/bvh/BVHPager.hxx diff --git a/simgear/bvh/BVHBoundingBoxVisitor.hxx b/simgear/bvh/BVHBoundingBoxVisitor.hxx index d37779c3..c14ff9c2 100644 --- a/simgear/bvh/BVHBoundingBoxVisitor.hxx +++ b/simgear/bvh/BVHBoundingBoxVisitor.hxx @@ -23,6 +23,7 @@ #include "BVHVisitor.hxx" #include "BVHNode.hxx" #include "BVHGroup.hxx" +#include "BVHPageNode.hxx" #include "BVHTransform.hxx" #include "BVHMotionTransform.hxx" #include "BVHLineGeometry.hxx" @@ -45,6 +46,8 @@ public: virtual void apply(BVHGroup& node) { expandBy(node.getBoundingSphere()); } + virtual void apply(BVHPageNode& node) + { expandBy(node.getBoundingSphere()); } virtual void apply(BVHTransform& node) { expandBy(node.getBoundingSphere()); } virtual void apply(BVHMotionTransform& node) diff --git a/simgear/bvh/BVHLineSegmentVisitor.cxx b/simgear/bvh/BVHLineSegmentVisitor.cxx index 1b93cd09..86fdd659 100644 --- a/simgear/bvh/BVHLineSegmentVisitor.cxx +++ b/simgear/bvh/BVHLineSegmentVisitor.cxx @@ -27,6 +27,7 @@ #include "BVHNode.hxx" #include "BVHGroup.hxx" +#include "BVHPageNode.hxx" #include "BVHTransform.hxx" #include "BVHMotionTransform.hxx" #include "BVHLineGeometry.hxx" @@ -47,6 +48,14 @@ BVHLineSegmentVisitor::apply(BVHGroup& group) return; group.traverse(*this); } + +void +BVHLineSegmentVisitor::apply(BVHPageNode& pageNode) +{ + if (!intersects(_lineSegment, pageNode.getBoundingSphere())) + return; + pageNode.traverse(*this); +} void BVHLineSegmentVisitor::apply(BVHTransform& transform) diff --git a/simgear/bvh/BVHLineSegmentVisitor.hxx b/simgear/bvh/BVHLineSegmentVisitor.hxx index 40783ef3..aa681a28 100644 --- a/simgear/bvh/BVHLineSegmentVisitor.hxx +++ b/simgear/bvh/BVHLineSegmentVisitor.hxx @@ -60,6 +60,7 @@ public: { return _id; } virtual void apply(BVHGroup& group); + virtual void apply(BVHPageNode& node); virtual void apply(BVHTransform& transform); virtual void apply(BVHMotionTransform& transform); virtual void apply(BVHLineGeometry&); diff --git a/simgear/bvh/BVHNearestPointVisitor.hxx b/simgear/bvh/BVHNearestPointVisitor.hxx index 5b5e1975..7b3a5bbf 100644 --- a/simgear/bvh/BVHNearestPointVisitor.hxx +++ b/simgear/bvh/BVHNearestPointVisitor.hxx @@ -24,6 +24,7 @@ #include "BVHNode.hxx" #include "BVHGroup.hxx" +#include "BVHPageNode.hxx" #include "BVHTransform.hxx" #include "BVHLineGeometry.hxx" #include "BVHStaticGeometry.hxx" @@ -52,6 +53,12 @@ public: return; leaf.traverse(*this); } + virtual void apply(BVHPageNode& leaf) + { + if (!intersects(_sphere, leaf.getBoundingSphere())) + return; + leaf.traverse(*this); + } virtual void apply(BVHTransform& transform) { if (!intersects(_sphere, transform.getBoundingSphere())) diff --git a/simgear/bvh/BVHNode.hxx b/simgear/bvh/BVHNode.hxx index 10a0a957..755dd1a9 100644 --- a/simgear/bvh/BVHNode.hxx +++ b/simgear/bvh/BVHNode.hxx @@ -26,6 +26,7 @@ namespace simgear { class BVHGroup; class BVHVisitor; +class BVHPageNode; // Base for the tree nodes class BVHNode : public SGReferenced { @@ -55,6 +56,7 @@ public: protected: friend class BVHGroup; + friend class BVHPageNode; void addParent(BVHNode* parent); void removeParent(BVHNode* parent); diff --git a/simgear/bvh/BVHPageNode.cxx b/simgear/bvh/BVHPageNode.cxx new file mode 100644 index 00000000..44c0d60f --- /dev/null +++ b/simgear/bvh/BVHPageNode.cxx @@ -0,0 +1,40 @@ +// Copyright (C) 2008 - 2012 Mathias Froehlich - Mathias.Froehlich@web.de +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Library General Public +// License as published by the Free Software Foundation; either +// version 2 of the License, or (at your option) any later version. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// Library General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this program; if not, write to the Free Software +// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. +// + +#include "BVHPageNode.hxx" + +#include "BVHPager.hxx" + +namespace simgear { + +BVHPageNode::BVHPageNode() : + _useStamp(0), + _requested(false) +{ +} + +BVHPageNode::~BVHPageNode() +{ +} + +void +BVHPageNode::accept(BVHVisitor& visitor) +{ + visitor.apply(*this); +} + +} diff --git a/simgear/bvh/BVHPageNode.hxx b/simgear/bvh/BVHPageNode.hxx new file mode 100644 index 00000000..86fa5768 --- /dev/null +++ b/simgear/bvh/BVHPageNode.hxx @@ -0,0 +1,66 @@ +// Copyright (C) 2008 - 2012 Mathias Froehlich - Mathias.Froehlich@web.de +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Library General Public +// License as published by the Free Software Foundation; either +// version 2 of the License, or (at your option) any later version. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// Library General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this program; if not, write to the Free Software +// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. +// + +#ifndef BVHPageNode_hxx +#define BVHPageNode_hxx + +#include + +#include + +#include "BVHGroup.hxx" +#include "BVHVisitor.hxx" + +namespace simgear { + +class BVHPager; +class BVHPageRequest; + +class BVHPageNode : public BVHGroup { +public: + BVHPageNode(); + virtual ~BVHPageNode(); + + virtual void accept(BVHVisitor& visitor); + + /// Return the usage stamp of the last access + unsigned getUseStamp() const + { return _useStamp; } + + virtual SGSphered computeBoundingSphere() const = 0; + + virtual BVHPageRequest* newRequest() = 0; + +protected: + virtual void invalidateBound() = 0; + + bool getRequested() const + { return _requested; } + void setRequested(bool requested) + { _requested = requested; } + +private: + friend class BVHPager; + + std::list >::iterator _iterator; + unsigned _useStamp; + bool _requested; +}; + +} + +#endif diff --git a/simgear/bvh/BVHPageRequest.cxx b/simgear/bvh/BVHPageRequest.cxx new file mode 100644 index 00000000..cecd4e0e --- /dev/null +++ b/simgear/bvh/BVHPageRequest.cxx @@ -0,0 +1,26 @@ +// Copyright (C) 2008 - 2012 Mathias Froehlich - Mathias.Froehlich@web.de +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Library General Public +// License as published by the Free Software Foundation; either +// version 2 of the License, or (at your option) any later version. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// Library General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this program; if not, write to the Free Software +// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. +// + +#include "BVHPageRequest.hxx" + +namespace simgear { + +BVHPageRequest::~BVHPageRequest() +{ +} + +} diff --git a/simgear/bvh/BVHPageRequest.hxx b/simgear/bvh/BVHPageRequest.hxx new file mode 100644 index 00000000..ab7f718a --- /dev/null +++ b/simgear/bvh/BVHPageRequest.hxx @@ -0,0 +1,42 @@ +// Copyright (C) 2008 - 2012 Mathias Froehlich - Mathias.Froehlich@web.de +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Library General Public +// License as published by the Free Software Foundation; either +// version 2 of the License, or (at your option) any later version. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// Library General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this program; if not, write to the Free Software +// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. +// + +#ifndef BVHPageRequest_hxx +#define BVHPageRequest_hxx + +#include + +namespace simgear { + +class BVHPageNode; + +class BVHPageRequest : public SGReferenced { +public: + virtual ~BVHPageRequest(); + + /// Happens in the pager thread, do not modify the calling bvh tree + virtual void load() = 0; + /// Happens in the bvh main thread where the bvh is actually used. + /// So inside here it is safe to modify the paged node + virtual void insert() = 0; + /// The page node this request is for + virtual BVHPageNode* getPageNode() = 0; +}; + +} + +#endif diff --git a/simgear/bvh/BVHPager.cxx b/simgear/bvh/BVHPager.cxx new file mode 100644 index 00000000..668be8b1 --- /dev/null +++ b/simgear/bvh/BVHPager.cxx @@ -0,0 +1,236 @@ +// Copyright (C) 2008 - 2012 Mathias Froehlich - Mathias.Froehlich@web.de +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Library General Public +// License as published by the Free Software Foundation; either +// version 2 of the License, or (at your option) any later version. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// Library General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this program; if not, write to the Free Software +// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. +// + +#include "BVHPager.hxx" + +#include + +#include +#include + +#include "BVHPageNode.hxx" +#include "BVHPageRequest.hxx" + +namespace simgear { + +struct BVHPager::_PrivateData : protected SGThread { + typedef SGSharedPtr _Request; + typedef std::list<_Request> _RequestList; + typedef std::list > _PageNodeList; + + struct _LockedQueue { + void _push(const _Request& request) + { + SGGuard scopeLock(_mutex); + _requestList.push_back(request); + } + _Request _pop() + { + SGGuard scopeLock(_mutex); + if (_requestList.empty()) + return _Request(); + _Request request; + request.swap(_requestList.front()); + _requestList.pop_front(); + return request; + } + private: + SGMutex _mutex; + _RequestList _requestList; + }; + + struct _WorkQueue { + void _stop() + { + _push(_Request()); + } + void _push(const _Request& request) + { + SGGuard scopeLock(_mutex); + bool needSignal = _requestList.empty(); + _requestList.push_back(request); + if (needSignal) + _waitCondition.signal(); + } + _Request _pop() + { + SGGuard scopeLock(_mutex); + while (_requestList.empty()) + _waitCondition.wait(_mutex); + _Request request; + request.swap(_requestList.front()); + _requestList.pop_front(); + return request; + } + private: + SGMutex _mutex; + SGWaitCondition _waitCondition; + _RequestList _requestList; + }; + + _PrivateData() : + _started(false), + _useStamp(0) + { + } + virtual ~_PrivateData() + { + _stop(); + } + + virtual void run() + { + for (;;) { + _Request request = _pendingRequests._pop(); + // This means stop working + if (!request.valid()) + return; + request->load(); + _processedRequests._push(request); + } + } + + bool _start() + { + if (_started) + return true; + if (!start()) + return false; + _started = true; + return true; + } + + void _stop() + { + if (!_started) + return; + // send a stop request ... + _pendingRequests._stop(); + // ... and wait for the thread to finish + join(); + _started = false; + } + + void _use(BVHPageNode& pageNode) + { + if (pageNode._requested) { + // move it forward in the lru list + _pageNodeList.splice(_pageNodeList.end(), _pageNodeList, + pageNode._iterator); + } else { + _Request request = pageNode.newRequest(); + if (!request.valid()) + return; + + pageNode._iterator = _pageNodeList.insert(_pageNodeList.end(), + &pageNode); + pageNode._requested = true; + + if (_started) { + _pendingRequests._push(request); + } else { + request->load(); + request->insert(); + } + } + pageNode._useStamp = _useStamp; + } + + void _update(unsigned expiry) + { + // Insert all processed requests + for (;;) { + SGSharedPtr request; + request = _processedRequests._pop(); + if (!request.valid()) + break; + request->insert(); + } + + // ... and throw away stuff that is not used for a long time + unsigned useStamp = _useStamp - expiry; + _PageNodeList::iterator i = _pageNodeList.begin(); + while (i != _pageNodeList.end()) { + // Ok, this means if the highest bit in the below difference + // is set which is aequivalent to having a negative difference + // but being wraparound save. + unsigned diff = (*i)->_useStamp - useStamp; + // test the sign bit of the difference + if (!(diff & (~((~0u) >> 1)))) + break; + (*i)->clear(); + (*i)->_requested = false; + i = _pageNodeList.erase(i); + } + } + + bool _started; + unsigned _useStamp; + _WorkQueue _pendingRequests; + _LockedQueue _processedRequests; + // Store the rcu list of loaded nodes so that they can expire + _PageNodeList _pageNodeList; +}; + +BVHPager::BVHPager() : + _privateData(new _PrivateData) +{ +} + +BVHPager::~BVHPager() +{ + delete _privateData; + _privateData = 0; +} + +bool +BVHPager::start() +{ + return _privateData->_start(); +} + +void +BVHPager::stop() +{ + _privateData->_stop(); +} + +void +BVHPager::use(BVHPageNode& pageNode) +{ + _privateData->_use(pageNode); +} + +void +BVHPager::update(unsigned expiry) +{ + _privateData->_update(expiry); +} + +void +BVHPager::setUseStamp(unsigned stamp) +{ + _privateData->_useStamp = stamp; +} + +unsigned +BVHPager::getUseStamp() const +{ + return _privateData->_useStamp; +} + +} diff --git a/simgear/bvh/BVHPager.hxx b/simgear/bvh/BVHPager.hxx new file mode 100644 index 00000000..7e2e52ed --- /dev/null +++ b/simgear/bvh/BVHPager.hxx @@ -0,0 +1,60 @@ +// Copyright (C) 2008 - 2012 Mathias Froehlich - Mathias.Froehlich@web.de +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Library General Public +// License as published by the Free Software Foundation; either +// version 2 of the License, or (at your option) any later version. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// Library General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this program; if not, write to the Free Software +// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. +// + +#ifndef BVHPager_hxx +#define BVHPager_hxx + +#include + +namespace simgear { + +class BVHPageNode; +class BVHPageRequest; + +class BVHPager { +public: + BVHPager(); + ~BVHPager(); + + /// Starts the pager thread + bool start(); + + /// Stops the pager thread + void stop(); + + /// Use this page node, if loaded make it as used, if not loaded schedule + void use(BVHPageNode& pageNode); + + /// Call this from the main thread to incorporate the processed page + /// requests into the bounding volume tree + void update(unsigned expiry); + + /// The usage stamp to mark usage of BVHPageNodes + void setUseStamp(unsigned stamp); + unsigned getUseStamp() const; + +private: + BVHPager(const BVHPager&); + BVHPager& operator=(const BVHPager&); + + struct _PrivateData; + _PrivateData* _privateData; +}; + +} + +#endif diff --git a/simgear/bvh/BVHSubTreeCollector.cxx b/simgear/bvh/BVHSubTreeCollector.cxx index 5c8a915c..6928dc7b 100644 --- a/simgear/bvh/BVHSubTreeCollector.cxx +++ b/simgear/bvh/BVHSubTreeCollector.cxx @@ -59,6 +59,22 @@ BVHSubTreeCollector::apply(BVHGroup& group) popNodeList(parentNodeList); } +void +BVHSubTreeCollector::apply(BVHPageNode& group) +{ + if (!intersects(_sphere, group.getBoundingSphere())) + return; + + // The _nodeList content is somehow the 'return value' of the subtree. + // Set it to zero to see if we have something to collect down there. + NodeList parentNodeList; + pushNodeList(parentNodeList); + + group.traverse(*this); + + popNodeList(parentNodeList); +} + void BVHSubTreeCollector::apply(BVHTransform& transform) { diff --git a/simgear/bvh/BVHSubTreeCollector.hxx b/simgear/bvh/BVHSubTreeCollector.hxx index aa3e1124..72f64ace 100644 --- a/simgear/bvh/BVHSubTreeCollector.hxx +++ b/simgear/bvh/BVHSubTreeCollector.hxx @@ -43,6 +43,7 @@ public: virtual ~BVHSubTreeCollector(); virtual void apply(BVHGroup&); + virtual void apply(BVHPageNode&); virtual void apply(BVHTransform&); virtual void apply(BVHMotionTransform&); virtual void apply(BVHLineGeometry&); diff --git a/simgear/bvh/BVHVisitor.hxx b/simgear/bvh/BVHVisitor.hxx index f74f4456..b8a5c3bb 100644 --- a/simgear/bvh/BVHVisitor.hxx +++ b/simgear/bvh/BVHVisitor.hxx @@ -1,4 +1,4 @@ -// Copyright (C) 2008 - 2009 Mathias Froehlich - Mathias.Froehlich@web.de +// Copyright (C) 2008 - 2012 Mathias Froehlich - Mathias.Froehlich@web.de // // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Library General Public @@ -23,6 +23,7 @@ namespace simgear { class BVHStaticData; class BVHGroup; +class BVHPageNode; class BVHTransform; class BVHMotionTransform; class BVHStaticGeometry; @@ -41,6 +42,7 @@ public: // High level nodes to handle virtual void apply(BVHGroup&) = 0; + virtual void apply(BVHPageNode&) = 0; virtual void apply(BVHTransform&) = 0; virtual void apply(BVHMotionTransform&) = 0; virtual void apply(BVHLineGeometry&) = 0; diff --git a/simgear/bvh/CMakeLists.txt b/simgear/bvh/CMakeLists.txt index ee6f9eb5..b5b47708 100644 --- a/simgear/bvh/CMakeLists.txt +++ b/simgear/bvh/CMakeLists.txt @@ -8,6 +8,9 @@ set(HEADERS BVHMotionTransform.hxx BVHNearestPointVisitor.hxx BVHNode.hxx + BVHPageNode.hxx + BVHPageRequest.hxx + BVHPager.hxx BVHStaticBinary.hxx BVHStaticData.hxx BVHStaticGeometry.hxx @@ -27,6 +30,9 @@ set(SOURCES BVHLineSegmentVisitor.cxx BVHMotionTransform.cxx BVHNode.cxx + BVHPageNode.cxx + BVHPageRequest.cxx + BVHPager.cxx BVHStaticBinary.cxx BVHStaticGeometry.cxx BVHStaticLeaf.cxx -- 2.39.5