#include <simgear/debug/logstream.hxx>
#include <simgear/structure/exception.hxx>
+#include <simgear/timing/timestamp.hxx>
namespace flightgear
{
childrenLoaded = true;
}
-
+
+void Leaf::addPolyLine(PolyLineRef aLine)
+{
+ lines.push_back(aLine);
+}
+
+void Leaf::visitForLines(const SGVec3d& aPos, double aCutoff,
+ PolyLineList& aLines,
+ FindLinesDeque& aQ) const
+{
+ aLines.insert(aLines.end(), lines.begin(), lines.end());
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
Branch::Branch(const SGBoxd& aBox, int64_t aIdent) :
Node(aBox, aIdent),
childrenLoaded(false)
aQ.push(Ordered<Node*>(children[i], d));
} // of child iteration
}
+
+void Branch::visitForLines(const SGVec3d& aPos, double aCutoff,
+ PolyLineList& aLines,
+ FindLinesDeque& aQ) const
+{
+ for (unsigned int i=0; i<8; ++i) {
+ if (!children[i]) {
+ continue;
+ }
+
+ double d = children[i]->distToNearest(aPos);
+ if (d > aCutoff) {
+ continue; // exceeded cutoff
+ }
+
+ aQ.push_back(children[i]);
+ } // of child iteration
+}
Node* Branch::childForPos(const SGVec3d& aCart) const
{
return result;
}
-void findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPositioned::Filter* aFilter, FGPositioned::List& aResults)
+bool findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPositioned::Filter* aFilter, FGPositionedList& aResults, int aCutoffMsec)
{
aResults.clear();
FindNearestPQueue pq;
pq.push(Ordered<Node*>(global_spatialOctree, 0));
double cut = aCutoffM;
- while (!pq.empty()) {
+ SGTimeStamp tm;
+ tm.stamp();
+
+ while (!pq.empty() && (tm.elapsedMSec() < aCutoffMsec)) {
if (!results.empty()) {
// terminate the search if we have sufficent results, and we are
// sure no node still on the queue contains a closer match
double furthestResultOrder = results.back().order();
- // std::cout << "furthest result:" << furthestResultOrder << ", top node order:" << pq.top().order() << std::endl;
if ((results.size() >= aN) && (furthestResultOrder < pq.top().order())) {
+ // clear the PQ to mark this has 'full results' instead of partial
+ pq = FindNearestPQueue();
break;
}
}
Node* nd = pq.top().get();
pq.pop();
-// std::cout << "visiting:" << std::oct << nd->guid() << "(" << std::dec << nd->guid() << ")" << std::endl;
nd->visit(aPos, cut, aFilter, results, pq);
} // of queue iteration
for (unsigned int r=0; r<numResults; ++r) {
aResults[r] = results[r].get();
}
+
+ return !pq.empty();
}
-void findAllWithinRange(const SGVec3d& aPos, double aRangeM, FGPositioned::Filter* aFilter, FGPositioned::List& aResults)
+bool findAllWithinRange(const SGVec3d& aPos, double aRangeM, FGPositioned::Filter* aFilter, FGPositionedList& aResults, int aCutoffMsec)
{
aResults.clear();
FindNearestPQueue pq;
pq.push(Ordered<Node*>(global_spatialOctree, 0));
double rng = aRangeM;
- while (!pq.empty()) {
+ SGTimeStamp tm;
+ tm.stamp();
+
+ while (!pq.empty() && (tm.elapsedMSec() < aCutoffMsec)) {
Node* nd = pq.top().get();
pq.pop();
for (unsigned int r=0; r<numResults; ++r) {
aResults[r] = results[r].get();
}
+
+ return !pq.empty();
}
} // of namespace Octree