Line data    Source code

       1             : /****************************************************************************/
       2             : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
       3             : // Copyright (C) 2001-2024 German Aerospace Center (DLR) and others.
       4             : // This program and the accompanying materials are made available under the
       5             : // terms of the Eclipse Public License 2.0 which is available at
       6             : // https://www.eclipse.org/legal/epl-2.0/
       7             : // This Source Code may also be made available under the following Secondary
       8             : // Licenses when the conditions for such availability set forth in the Eclipse
       9             : // Public License 2.0 are satisfied: GNU General Public License, version 2
      10             : // or later which is available at
      11             : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
      12             : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
      13             : /****************************************************************************/
      14             : /// @file    SUMORTree.h
      15             : /// @author  Daniel Krajzewicz
      16             : /// @date    27.10.2008
      17             : ///
      18             : // A RT-tree for efficient storing of SUMO's GL-objects
      19             : /****************************************************************************/
      20             : #pragma once
      21             : #include <config.h>
      22             : 
      23             : #include <utils/foxtools/fxheader.h>
      24             : #include <utils/common/MsgHandler.h>
      25             : #include <utils/geom/Boundary.h>
      26             : #include <utils/gui/globjects/GUIGlObject.h>
      27             : #include <utils/gui/settings/GUIVisualizationSettings.h>
      28             : #include <utils/gui/div/GUIIOGlobals.h>
      29             : 
      30             : #include "RTree.h"
      31             : 
      32             : 
      33             : #define GUI_RTREE_QUAL RTree<GUIGlObject*, GUIGlObject, float, 2, GUIVisualizationSettings>
      34             : 
      35             : // specialized implementation for speedup and avoiding warnings
      36             : 
      37             : template<>
      38             : inline float GUI_RTREE_QUAL::RectSphericalVolume(Rect* a_rect) {
      39             :   ASSERT(a_rect);
      40     9532010 :   const float extent0 = a_rect->m_max[0] - a_rect->m_min[0];
      41     9532010 :   const float extent1 = a_rect->m_max[1] - a_rect->m_min[1];
      42     6583382 :   return .78539816f * (extent0 * extent0 + extent1 * extent1);
      43             : }
      44             : 
      45             : template<>
      46             : inline GUI_RTREE_QUAL::Rect GUI_RTREE_QUAL::CombineRect(Rect* a_rectA, Rect* a_rectB) {
      47             :     ASSERT(a_rectA && a_rectB);
      48             :     Rect newRect;
      49     9316531 :     newRect.m_min[0] = rtree_min(a_rectA->m_min[0], a_rectB->m_min[0]);
      50     9316531 :     newRect.m_max[0] = rtree_max(a_rectA->m_max[0], a_rectB->m_max[0]);
      51     9316531 :     newRect.m_min[1] = rtree_min(a_rectA->m_min[1], a_rectB->m_min[1]);
      52     9316531 :     newRect.m_max[1] = rtree_max(a_rectA->m_max[1], a_rectB->m_max[1]);
      53             :     return newRect;
      54             : }
      55             : 
      56             : 
      57             : // ===========================================================================
      58             : // class definitions
      59             : // ===========================================================================
      60             : /** @class SUMORTree
      61             :  * @brief A RT-tree for efficient storing of SUMO's GL-objects
      62             :  *
      63             :  * This class specialises the used RT-tree implementation from "rttree.h" and
      64             :  *  extends it by a mutex for avoiding parallel change and traversal of the tree.
      65             :  */
      66             : class SUMORTree : private GUI_RTREE_QUAL, public Boundary {
      67             : public:
      68             :     /// @brief Constructor
      69       28928 :     SUMORTree() :
      70             :         GUI_RTREE_QUAL(&GUIGlObject::drawGL),
      71       28928 :         myLock(true) {
      72       28928 :     }
      73             : 
      74             :     /// @brief Destructor
      75       43302 :     virtual ~SUMORTree() {
      76             :         // check if lock is locked before insert objects
      77       28868 :         if (myLock.locked()) {
      78             :             // cannot throw exception in destructor
      79           0 :             WRITE_ERROR("Mutex of SUMORTree is locked during call of the destructor");
      80             :         }
      81             :         // show information in gui testing debug gl mode
      82       28868 :         WRITE_GLDEBUG("Number of objects in SUMORTree during call of the destructor: " + toString(myTreeDebug.size()));
      83       43302 :     }
      84             : 
      85             :     /** @brief Insert entry
      86             :      * @param a_min Min of bounding rect
      87             :      * @param a_max Max of bounding rect
      88             :      * @param a_dataId Positive Id of data.  Maybe zero, but negative numbers not allowed.
      89             :      * @see RTree::Insert
      90             :      */
      91      388759 :     virtual void Insert(const float a_min[2], const float a_max[2], GUIGlObject* const & a_dataId) {
      92      388759 :         FXMutexLock locker(myLock);
      93      388759 :         GUI_RTREE_QUAL::Insert(a_min, a_max, a_dataId);
      94      388759 :     }
      95             : 
      96             :     /** @brief Remove entry
      97             :      * @param a_min Min of bounding rect
      98             :      * @param a_max Max of bounding rect
      99             :      * @param a_dataId Positive Id of data.  Maybe zero, but negative numbers not allowed.
     100             :      * @see RTree::Remove
     101             :      */
     102        3119 :     virtual void Remove(const float a_min[2], const float a_max[2], GUIGlObject* const & a_dataId) {
     103        3119 :         FXMutexLock locker(myLock);
     104        3119 :         GUI_RTREE_QUAL::Remove(a_min, a_max, a_dataId);
     105        3119 :     }
     106             : 
     107             :     /** @brief Find all within search rectangle
     108             :      * @param a_min Min of search bounding rect
     109             :      * @param a_max Max of search bounding rect
     110             :      * @param a_searchResult Search result array.  Caller should set grow size. Function will reset, not append to array.
     111             :      * @param a_resultCallback Callback function to return result.  Callback should return 'true' to continue searching
     112             :      * @param a_context User context to pass as parameter to a_resultCallback
     113             :      * @return Returns the number of entries found
     114             :      * @see RTree::Search
     115             :      */
     116      962008 :     virtual int Search(const float a_min[2], const float a_max[2], const GUIVisualizationSettings& c) const {
     117      962008 :         FXMutexLock locker(myLock);
     118     1924014 :         return GUI_RTREE_QUAL::Search(a_min, a_max, c);
     119             :     }
     120             : 
     121             :     /** @brief Adds an additional object (detector/shape/trigger) for visualisation
     122             :      * @param[in] o The object to add
     123             :      */
     124       28981 :     void addAdditionalGLObject(GUIGlObject *o, const double exaggeration = 1) {
     125             :         // check if lock is locked before insert objects
     126       28981 :         if (myLock.locked()) {
     127           0 :             throw ProcessError("Mutex of SUMORTree is locked before object insertion");
     128             :         }
     129             :         // lock mutex
     130             :         FXMutexLock locker(myLock);
     131             :         // obtain boundary of object
     132       28981 :         Boundary b = o->getCenteringBoundary();
     133             :         // grow using exaggeration
     134       28981 :         if (exaggeration > 1) {
     135           0 :             b.scale(exaggeration);
     136             :         }
     137             :         // show information in gui testing debug gl mode
     138       28981 :         if (MsgHandler::writeDebugGLMessages()) {
     139           0 :             if ((b.getWidth() == 0) || (b.getHeight() == 0)) {
     140           0 :                 throw ProcessError(StringUtils::format("Boundary of GUIGlObject % has an invalid size", o->getMicrosimID()));
     141             :             } else if (myTreeDebug.count(o) > 0) {
     142           0 :                 throw ProcessError("GUIGlObject was already inserted");
     143             :             } else {
     144           0 :                 myTreeDebug[o] = b;
     145             :                 // write GL Debug
     146           0 :                 WRITE_GLDEBUG("\tInserted " + o->getFullName() + " into SUMORTree with boundary " + toString(b));
     147             :             }
     148             :         }
     149             :         // insert it in Tree
     150       28981 :         const float cmin[2] = {(float) b.xmin(), (float) b.ymin()};
     151       28981 :         const float cmax[2] = {(float) b.xmax(), (float) b.ymax()};
     152       28981 :         Insert(cmin, cmax, o);
     153             :         // update tree size
     154       28981 :         myTreeSize++;
     155       57962 :     }
     156             : 
     157             :     /** @brief Removes an additional object (detector/shape/trigger) from being visualised
     158             :      * @param[in] o The object to remove
     159             :      */
     160        3119 :     void removeAdditionalGLObject(GUIGlObject *o, const double exaggeration = 1) {
     161             :         // check if lock is locked remove insert objects
     162        3119 :         if (myLock.locked()) {
     163           0 :             throw ProcessError("Mutex of SUMORTree is locked before object remove");
     164             :         }
     165             :         // lock mutex
     166             :         FXMutexLock locker(myLock);
     167             :         // obtain boundary of object
     168        3119 :         Boundary b = o->getCenteringBoundary();
     169             :         // grow using exaggeration
     170        3119 :         if (exaggeration > 1) {
     171           0 :             b.scale(exaggeration);
     172             :         }
     173             :         // show information in gui testing debug gl mode
     174        3119 :         if (MsgHandler::writeDebugGLMessages()) {
     175           0 :             if ((b.getWidth() == 0) || (b.getHeight() == 0)) {
     176           0 :                 throw ProcessError(StringUtils::format("Boundary of GUIGlObject % has an invalid size", o->getMicrosimID()));
     177             :             } else if (myTreeDebug.count(o) == 0) {
     178           0 :                 throw ProcessError("GUIGlObject wasn't inserted");
     179           0 :             } else if (toString(b) != toString(myTreeDebug.at(o))) {
     180             :                 // show information in console before throwing exception
     181           0 :                 std::cout << "Tree: " << toString(myTreeDebug.at(o)) << " original: " << toString(b) << std::endl;
     182           0 :                 throw ProcessError("add boundary of GUIGlObject " + o->getMicrosimID() + " is different of removed boundary (" + toString(b) + " != " + toString(myTreeDebug.at(o)) + ")");
     183             :             } else {
     184             :                 myTreeDebug.erase(o);
     185           0 :                 WRITE_GLDEBUG("\tRemoved object " + o->getFullName() + " from SUMORTree with boundary " + toString(b));
     186             :             }
     187             :         }
     188             :         // remove it from Tree
     189        3119 :         const float cmin[2] = {(float) b.xmin(), (float) b.ymin()};
     190        3119 :         const float cmax[2] = {(float) b.xmax(), (float) b.ymax()};
     191        3119 :         Remove(cmin, cmax, o);
     192             :         // update tree size
     193        3119 :         myTreeSize--;
     194        6238 :     }
     195             : 
     196             :     /// @brief update boundaries
     197             :     void updateBoundaries(GUIGlObjectType type) {
     198             :         // declare vector with glObjects to update
     199             :         std::vector<GUIGlObject*> glObjects;
     200             :         glObjects.reserve(myTreeSize);
     201             :         // declare iterator
     202             :         GUI_RTREE_QUAL::Iterator it;
     203             :         GetFirst(it);
     204             :         // iterate over entire tree and keep glObject in glObjects
     205             :         while (!IsNull(it)) {
     206             :             const auto glType = (*it)->getType();
     207             :             if ((glType == type) ||
     208             :                 ((glType > GLO_ADDITIONALELEMENT) && (glType < GLO_SHAPE)) ||   // Additionals
     209             :                 ((glType >= GLO_TAZ) && (glType < GLO_LOCKICON))) {             // TAZ Elements
     210             :                 glObjects.push_back(*it);
     211             :             }
     212             :             GetNext(it);
     213             :         }
     214             :         // remove and insert all elements again with the new boundary
     215             :         for (const auto &glObject : glObjects) {
     216             :             removeAdditionalGLObject(glObject);
     217             :             removeObjectFromTreeDebug(glObject);
     218             :             addAdditionalGLObject(glObject);
     219             :         }
     220             :     }
     221             : 
     222             : protected:
     223             :     /// @brief A mutex avoiding parallel change and traversal of the tree
     224             :     mutable FXMutex myLock;
     225             : 
     226             :     /// @brief number of inserted elements
     227             :     int myTreeSize = 0;
     228             : 
     229             : private:
     230             :     /**@brief Map only used for check that SUMORTree works as expected, only is used if option "gui-testing-debug-gl" is enabled.
     231             :      * @note Warning: DO NOT USE in release mode and use it in debug mode carefully, due it produces a slowdown.
     232             :      */
     233             :     std::map<GUIGlObject*, Boundary> myTreeDebug;
     234             : 
     235             :     /// @brief remove object from TreeDebug
     236             :     bool removeObjectFromTreeDebug(const GUIGlObject* obj) {
     237             :         for (auto it = myTreeDebug.begin(); it != myTreeDebug.end(); it++) {
     238             :             if (it->first == obj) {
     239             :                 myTreeDebug.erase(it);
     240             :                 return true;
     241             :             }
     242             :         }
     243             :         return false;
     244             :     }
     245             : };