From 851029143e20fcfdac96253a63e3d07fd267d95f Mon Sep 17 00:00:00 2001
From: James Turner <jmt@Bishop.local>
Date: Sun, 30 Dec 2012 17:01:48 +0000
Subject: [PATCH] NavDisplay: time-bound the spatial query.

At large search ranges (320 or 640NM range on the 777), the search time can blow up, especially if distant airports are being loaded. Add a time-bounded spatial query, and use it, so performance stays tolerable.
---
 src/Cockpit/NavDisplay.cxx       |  9 ++++++++-
 src/Navaids/PositionedOctree.cxx | 13 +++++++++----
 src/Navaids/PositionedOctree.hxx |  2 +-
 src/Navaids/positioned.cxx       | 17 +++++++++++++++--
 src/Navaids/positioned.hxx       |  8 +++++++-
 5 files changed, 40 insertions(+), 9 deletions(-)

diff --git a/src/Cockpit/NavDisplay.cxx b/src/Cockpit/NavDisplay.cxx
index 6c344aa9d..efd2c30a3 100644
--- a/src/Cockpit/NavDisplay.cxx
+++ b/src/Cockpit/NavDisplay.cxx
@@ -998,9 +998,16 @@ void NavDisplay::findItems()
     if (!_cachedItemsValid) {
         Filter filt(this);
         filt.minRunwayLengthFt = fgGetDouble("/sim/navdb/min-runway-length-ft", 2000);
-        _itemsInRange = FGPositioned::findClosestN(_pos, _maxSymbols, _rangeNm, &filt);
+        bool wasTimeLimited;
+        _itemsInRange = FGPositioned::findClosestNPartial(_pos, _maxSymbols, _rangeNm,
+                                                          &filt, wasTimeLimited);
         _cachedItemsValid = true;
         _cachedPos = SGVec3d::fromGeod(_pos);
+        
+        if (wasTimeLimited) {
+            // re-query next frame, to load incrementally
+            _cachedItemsValid = false;
+        }
     }
     
   // sort by distance from pos, so symbol limits are accurate
diff --git a/src/Navaids/PositionedOctree.cxx b/src/Navaids/PositionedOctree.cxx
index 9f6908f83..781fee8f2 100644
--- a/src/Navaids/PositionedOctree.cxx
+++ b/src/Navaids/PositionedOctree.cxx
@@ -223,7 +223,7 @@ int Branch::childMask() 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, FGPositioned::List& aResults, int aCutoffMsec)
 {
   aResults.clear();
   FindNearestPQueue pq;
@@ -231,13 +231,17 @@ void findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPosit
   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;
       }
     }
@@ -245,7 +249,6 @@ void findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPosit
     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
 
@@ -257,6 +260,8 @@ void findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPosit
   for (unsigned int r=0; r<numResults; ++r) {
     aResults[r] = results[r].get();
   }
+    
+  return !pq.empty();
 }
 
 bool findAllWithinRange(const SGVec3d& aPos, double aRangeM, FGPositioned::Filter* aFilter, FGPositioned::List& aResults, int aCutoffMsec)
diff --git a/src/Navaids/PositionedOctree.hxx b/src/Navaids/PositionedOctree.hxx
index 747ce985b..3a830349c 100644
--- a/src/Navaids/PositionedOctree.hxx
+++ b/src/Navaids/PositionedOctree.hxx
@@ -215,7 +215,7 @@ namespace Octree
     mutable bool childrenLoaded;
   };
 
-  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, FGPositioned::List& aResults, int aCutoffMsec);
   bool findAllWithinRange(const SGVec3d& aPos, double aRangeM, FGPositioned::Filter* aFilter, FGPositioned::List& aResults, int aCutoffMsec);
 } // of namespace Octree
 
diff --git a/src/Navaids/positioned.cxx b/src/Navaids/positioned.cxx
index e7a1e58c5..92250b906 100644
--- a/src/Navaids/positioned.cxx
+++ b/src/Navaids/positioned.cxx
@@ -251,10 +251,23 @@ FGPositioned::findClosestN(const SGGeod& aPos, unsigned int aN, double aCutoffNm
   validateSGGeod(aPos);
   
   List result;
-  Octree::findNearestN(SGVec3d::fromGeod(aPos), aN, aCutoffNm * SG_NM_TO_METER, aFilter, result);
+  int limitMsec = 0xffff;
+  Octree::findNearestN(SGVec3d::fromGeod(aPos), aN, aCutoffNm * SG_NM_TO_METER, aFilter, result, limitMsec);
   return result;
 }
- 
+
+FGPositioned::List
+FGPositioned::findClosestNPartial(const SGGeod& aPos, unsigned int aN, double aCutoffNm, Filter* aFilter, bool &aPartial)
+{
+    validateSGGeod(aPos);
+    
+    List result;
+    int limitMsec = 32;
+    aPartial = Octree::findNearestN(SGVec3d::fromGeod(aPos), aN, aCutoffNm * SG_NM_TO_METER, aFilter, result,
+                        limitMsec);
+    return result;
+}
+
 void
 FGPositioned::sortByRange(List& aResult, const SGGeod& aPos)
 {
diff --git a/src/Navaids/positioned.hxx b/src/Navaids/positioned.hxx
index f4707cbc2..e978bb6d6 100644
--- a/src/Navaids/positioned.hxx
+++ b/src/Navaids/positioned.hxx
@@ -210,7 +210,13 @@ public:
    * @param aCutoffNm - maximum distance to search within, in nautical miles
    */
   static List findClosestN(const SGGeod& aPos, unsigned int aN, double aCutoffNm, Filter* aFilter = NULL);
-  
+    
+  /**
+   * Same as above, but with a time-bound in msec too.
+   */
+  static List findClosestNPartial(const SGGeod& aPos, unsigned int aN, double aCutoffNm, Filter* aFilter,
+                           bool& aPartial);
+    
   /**
    * Map a candidate type string to a real type. Returns INVALID if the string
    * does not correspond to a defined type.
-- 
2.39.5