Code/CryEngine/CrySchematyc2/BaseEnv/Utils/BaseEnv_SpatialIndex.cpp

   1 // Copyright 2001-2019 Crytek GmbH / Crytek Group. All rights reserved.
   2
   3 #include "StdAfx.h"
   4 #include "BaseEnv/Utils/BaseEnv_SpatialIndex.h"
   5
   6 #include <CryRenderer/IRenderAuxGeom.h>
   7
   8 SERIALIZATION_ENUM_BEGIN_NESTED(SchematycBaseEnv, ESpatialVolumeShape, "Spatial volume shape")
   9         SERIALIZATION_ENUM(SchematycBaseEnv::ESpatialVolumeShape::Box, "Box", "Box")
  10         SERIALIZATION_ENUM(SchematycBaseEnv::ESpatialVolumeShape::Sphere, "Sphere", "Sphere")
  11         SERIALIZATION_ENUM(SchematycBaseEnv::ESpatialVolumeShape::Point, "Point", "Point")
  12 SERIALIZATION_ENUM_END()
  13
  14 namespace SchematycBaseEnv
  15 {
  16         const uint32 CSpatialIndex::s_volumeIdxMask   = 0x0000ffff;
  17         const uint32 CSpatialIndex::s_volumeSaltShift = 16;
  18         const uint32 CSpatialIndex::s_volumeSaltMask  = 0xffff0000;
  19
  20         CSpatialVolumeBounds::CSpatialVolumeBounds()
  21                 : m_shape(ESpatialVolumeShape::None)
  22         {}
  23
  24         CSpatialVolumeBounds::CSpatialVolumeBounds(const OBB& rhs)
  25                 : m_shape(ESpatialVolumeShape::Box)
  26         {
  27                 new (m_storage) OBB(rhs);
  28         }
  29
  30         CSpatialVolumeBounds::CSpatialVolumeBounds(const Sphere& rhs)
  31                 : m_shape(ESpatialVolumeShape::Sphere)
  32         {
  33                 new (m_storage) Sphere(rhs);
  34         }
  35
  36         CSpatialVolumeBounds::CSpatialVolumeBounds(const Vec3& rhs)
  37                 : m_shape(ESpatialVolumeShape::Point)
  38         {
  39                 new (m_storage) Vec3(rhs);
  40         }
  41
  42         CSpatialVolumeBounds::CSpatialVolumeBounds(const CSpatialVolumeBounds& rhs)
  43                 : m_shape(rhs.m_shape)
  44         {
  45                 Copy(rhs);
  46         }
  47
  48         CSpatialVolumeBounds::~CSpatialVolumeBounds()
  49         {
  50                 Release();
  51         }
  52
  53         CSpatialVolumeBounds CSpatialVolumeBounds::CreateOBB(const Matrix34& volumeTM, const Vec3& pos, const Vec3& size, const Matrix33& rot)
  54         {
  55                 const QuatT transform = QuatT(volumeTM) * QuatT(Quat(rot), pos);
  56                 return CSpatialVolumeBounds(OBB::CreateOBB(Matrix33(transform.q), size*0.5f, transform.q.GetInverted() * transform.t));
  57         }
  58
  59         CSpatialVolumeBounds CSpatialVolumeBounds::CreateSphere(const Matrix34& volumeTM, const Vec3& pos, float radius)
  60         {
  61                 return CSpatialVolumeBounds(Sphere(volumeTM.TransformPoint(pos), radius));
  62         }
  63
  64         CSpatialVolumeBounds CSpatialVolumeBounds::CreatePoint(const Matrix34& volumeTM, const Vec3& pos)
  65         {
  66                 return CSpatialVolumeBounds(volumeTM.TransformPoint(pos));
  67         }
  68
  69         ESpatialVolumeShape CSpatialVolumeBounds::GetShape() const
  70         {
  71                 return m_shape;
  72         }
  73
  74         const OBB& CSpatialVolumeBounds::AsBox() const
  75         {
  76                 CRY_ASSERT(m_shape == ESpatialVolumeShape::Box);
  77                 return *reinterpret_cast<const OBB*>(m_storage);
  78         }
  79
  80         const Sphere& CSpatialVolumeBounds::AsSphere() const
  81         {
  82                 CRY_ASSERT(m_shape == ESpatialVolumeShape::Sphere);
  83                 return *reinterpret_cast<const Sphere*>(m_storage);
  84         }
  85
  86         const Vec3& CSpatialVolumeBounds::AsPoint() const
  87         {
  88                 CRY_ASSERT(m_shape == ESpatialVolumeShape::Point);
  89                 return *reinterpret_cast<const Vec3*>(m_storage);
  90         }
  91
  92         AABB CSpatialVolumeBounds::CalculateAABB() const
  93         {
  94                 switch(m_shape)
  95                 {
  96                 case ESpatialVolumeShape::Box:
  97                         {
  98                                 return AABB::CreateAABBfromOBB(Vec3(ZERO), AsBox());
  99                         }
 100                 case ESpatialVolumeShape::Sphere:
 101                         {
 102                                 return AABB(AsSphere().center, AsSphere().radius);
 103                         }
 104                 case ESpatialVolumeShape::Point:
 105                         {
 106                                 return AABB(AsPoint(), AsPoint());
 107                         }
 108                 }
 109                 return AABB(0.0f);
 110         }
 111
 112         bool CSpatialVolumeBounds::Overlap(const CSpatialVolumeBounds& rhs) const
 113         {
 114                 switch(m_shape)
 115                 {
 116                 case ESpatialVolumeShape::Box:
 117                         {
 118                                 switch(rhs.m_shape)
 119                                 {
 120                                 case ESpatialVolumeShape::Box:
 121                                         {
 122                                                 return Overlap::OBB_OBB(Vec3(ZERO), AsBox(), Vec3(ZERO), rhs.AsBox());
 123                                         }
 124                                 case ESpatialVolumeShape::Sphere:
 125                                         {
 126                                                 return Overlap::Sphere_OBB(rhs.AsSphere(), AsBox());
 127                                         }
 128                                 case ESpatialVolumeShape::Point:
 129                                         {
 130                                                 return Overlap::Point_OBB(rhs.AsPoint(), Vec3(ZERO), AsBox());
 131                                         }
 132                                 }
 133                                 break;
 134                         }
 135                 case ESpatialVolumeShape::Sphere:
 136                         {
 137                                 switch(rhs.m_shape)
 138                                 {
 139                                 case ESpatialVolumeShape::Box:
 140                                         {
 141                                                 return Overlap::Sphere_OBB(AsSphere(), rhs.AsBox());
 142                                         }
 143                                 case ESpatialVolumeShape::Sphere:
 144                                         {
 145                                                 return Overlap::Sphere_Sphere(AsSphere(), rhs.AsSphere());
 146                                         }
 147                                 case ESpatialVolumeShape::Point:
 148                                         {
 149                                                 return Overlap::Point_Sphere(rhs.AsPoint(), AsSphere());
 150                                         }
 151                                 }
 152                                 break;
 153                         }
 154                 case ESpatialVolumeShape::Point:
 155                         {
 156                                 switch(rhs.m_shape)
 157                                 {
 158                                 case ESpatialVolumeShape::Box:
 159                                         {
 160                                                 return Overlap::Point_OBB(AsPoint(), Vec3(ZERO), rhs.AsBox());
 161                                         }
 162                                 case ESpatialVolumeShape::Sphere:
 163                                         {
 164                                                 return Overlap::Point_Sphere(AsPoint(), rhs.AsSphere());
 165                                         }
 166                                 // N.B. No case for ESpatialVolumeShape::Point because we should never need to detect overlapping points.
 167                                 }
 168                                 break;
 169                         }
 170                 }
 171                 return false;
 172         }
 173
 174         void CSpatialVolumeBounds::operator = (const CSpatialVolumeBounds& rhs)
 175         {
 176                 Release();
 177                 Copy(rhs);
 178         }
 179
 180         void CSpatialVolumeBounds::Copy(const CSpatialVolumeBounds& rhs)
 181         {
 182                 m_shape = rhs.m_shape;
 183                 switch(rhs.m_shape)
 184                 {
 185                 case ESpatialVolumeShape::Box:
 186                         {
 187                                 new (m_storage) OBB(rhs.AsBox());
 188                                 break;
 189                         }
 190                 case ESpatialVolumeShape::Sphere:
 191                         {
 192                                 new (m_storage) Sphere(rhs.AsSphere());
 193                                 break;
 194                         }
 195                 case ESpatialVolumeShape::Point:
 196                         {
 197                                 new (m_storage) Vec3(rhs.AsPoint());
 198                                 break;
 199                         }
 200                 }
 201         }
 202
 203         void CSpatialVolumeBounds::Release()
 204         {
 205                 switch(m_shape)
 206                 {
 207                 case ESpatialVolumeShape::Box:
 208                         {
 209                                 reinterpret_cast<const OBB*>(m_storage)->~OBB();
 210                                 break;
 211                         }
 212                 case ESpatialVolumeShape::Sphere:
 213                         {
 214                                 reinterpret_cast<const Sphere*>(m_storage)->~Sphere();
 215                                 break;
 216                         }
 217                 case ESpatialVolumeShape::Point:
 218                         {
 219                                 reinterpret_cast<const Vec3*>(m_storage)->~Vec3();
 220                                 break;
 221                         }
 222                 }
 223         }
 224
 225         SSpatialVolumeTagName::SSpatialVolumeTagName() {}
 226
 227         SSpatialVolumeTagName::SSpatialVolumeTagName(const string& _value)
 228                 : value(_value)
 229         {}
 230
 231         bool SSpatialVolumeTagName::operator == (const SSpatialVolumeTagName& rhs) const
 232         {
 233                 return value == rhs.value;
 234         }
 235
 236         bool Serialize(Serialization::IArchive& archive, SSpatialVolumeTagName& value, const char* szName, const char* szLabel)
 237         {
 238                 /*const Serialization::StringList& tagNames = g_pGame->GetSchematycEnv().GetEntityDetectionVolumeSystem().GetTagNames();
 239                 if(archive.isInput())
 240                 {
 241                         Serialization::StringListValue temp(tagNames, 0);
 242                         archive(temp, szName, szLabel);
 243                         value.value = temp.c_str();
 244                 }
 245                 else if(archive.isOutput())
 246                 {
 247                         const int pos = tagNames.find(value.value.c_str());
 248                         archive(Serialization::StringListValue(tagNames, pos), szName, szLabel);
 249                 }*/
 250                 return true;
 251         }
 252
 253         SSpatialVolumeParams::SSpatialVolumeParams()
 254                 : tags(ESpatialVolumeTags::None)
 255                 , monitorTags(ESpatialVolumeTags::None)
 256                 , entityId(0)
 257         {}
 258
 259         SSpatialVolumeParams::SSpatialVolumeParams(const CSpatialVolumeBounds& _bounds, ESpatialVolumeTags _tags, ESpatialVolumeTags _monitorTags, EntityId _entityId)
 260                 : bounds(_bounds)
 261                 , tags(_tags)
 262                 , monitorTags(_monitorTags)
 263                 , entityId(_entityId)
 264         {}
 265
 266         void CSpatialIndex::SSettings::Serialize(Serialization::IArchive& archive)
 267         {
 268                 archive(userTags, "userTags", "+User Tags");
 269                 if(archive.isInput())
 270                 {
 271                         RefreshTags();
 272                 }
 273         }
 274
 275         void CSpatialIndex::SSettings::RefreshTags()
 276         {
 277                 tagNames.clear();
 278                 tagValues.clear();
 279
 280                 const Serialization::EnumDescription& tagsEnumDescription = Serialization::getEnumDescription<ESpatialVolumeTags>();
 281                 UserTags::const_iterator              itUserTag = userTags.begin();
 282                 UserTags::const_iterator              itEndUserTag = userTags.end();
 283                 for(int tagValue = static_cast<int>(ESpatialVolumeTags::Begin); tagValue != static_cast<int>(ESpatialVolumeTags::End); tagValue <<= 1)
 284                 {
 285                         const int tagIdx = tagsEnumDescription.indexByValue(tagValue);
 286                         if(tagIdx != -1)
 287                         {
 288                                 tagNames.push_back(tagsEnumDescription.labelByIndex(tagIdx));
 289                                 tagValues.push_back(tagValue);
 290                         }
 291                         else if(itUserTag != itEndUserTag)
 292                         {
 293                                 tagNames.push_back(*itUserTag);
 294                                 tagValues.push_back(tagValue);
 295                                 ++ itUserTag;
 296                         }
 297                 }
 298         }
 299
 300         CSpatialIndex::SVolume::SVolume()
 301                 : monitorTags(ESpatialVolumeTags::None)
 302                 , entityId(0)
 303         {}
 304
 305         CSpatialIndex::SBroadPhaseVolume::SBroadPhaseVolume()
 306                 : tags(ESpatialVolumeTags::None)
 307         {}
 308
 309         CSpatialIndex::CSpatialIndex()
 310                 : m_pSettings(new SSettings())
 311                 , m_salt(0)
 312         {
 313                 m_pSettings->RefreshTags();
 314                 gEnv->pSchematyc2->GetEnvRegistry().RegisterSettings("spatial_index_settings", m_pSettings);
 315
 316                 m_volumes.reserve(256);
 317                 m_broadPhaseVolumes.reserve(256);
 318                 m_freeVolumes.reserve(64);
 319                 m_broadPhaseResults.reserve(64);
 320                 m_monitorResults.reserve(16);
 321                 m_eventQueue.reserve(64);
 322         }
 323
 324         SpatialVolumeId CSpatialIndex::CreateVolume(const SSpatialVolumeParams& params, const SpatialIndexEventCallback& eventCallback)
 325         {
 326                 uint32 volumeIdx;
 327                 if(m_freeVolumes.empty())
 328                 {
 329                         const uint32 volumeCount = m_volumes.size();
 330                         if(volumeCount > s_volumeIdxMask)
 331                         {
 332                                 return SpatialVolumeId();
 333                         }
 334                         else
 335                         {
 336                                 volumeIdx = volumeCount;
 337                                 m_volumes.push_back(SVolume());
 338                                 m_broadPhaseVolumes.push_back(SBroadPhaseVolume());
 339                         }
 340                 }
 341                 else
 342                 {
 343                         volumeIdx = m_freeVolumes.back();
 344                         m_freeVolumes.pop_back();
 345                 }
 346
 347                 SVolume& volume = m_volumes[volumeIdx];
 348                 volume.bounds        = params.bounds;
 349                 volume.monitorTags   = params.monitorTags;
 350                 volume.id            = GenerateVolumeId(volumeIdx);
 351                 volume.entityId      = params.entityId;
 352                 volume.eventCallback = eventCallback;
 353
 354                 volume.monitorCache.clear();
 355                 if(params.monitorTags != ESpatialVolumeTags::None)
 356                 {
 357                         volume.monitorCache.reserve(16);
 358                 }
 359
 360                 SBroadPhaseVolume& broadPhaseVolume = m_broadPhaseVolumes[volumeIdx];
 361                 broadPhaseVolume.tags = params.tags;
 362                 broadPhaseVolume.aabb = params.bounds.CalculateAABB();
 363
 364                 return volume.id;
 365         }
 366
 367         void CSpatialIndex::DestroyVolume(const SpatialVolumeId& id)
 368         {
 369                 if(id != SpatialVolumeId::s_invalid)
 370                 {
 371                         const uint32 volumeCount = m_volumes.size();
 372                         const uint32 volumeIdx = VolumeIdxFromId(id);
 373                         CRY_ASSERT(volumeIdx < volumeCount);
 374                         if(volumeIdx < volumeCount)
 375                         {
 376                                 SVolume& volume = m_volumes[volumeIdx];
 377                                 CRY_ASSERT(volume.id == id);
 378                                 if(volume.id == id)
 379                                 {
 380                                         volume.bounds                       = CSpatialVolumeBounds();
 381                                         volume.monitorTags                  = ESpatialVolumeTags::None;
 382                                         volume.eventCallback                = SpatialIndexEventCallback();
 383                                         m_broadPhaseVolumes[volumeIdx].tags = ESpatialVolumeTags::None;
 384                                         m_freeVolumes.push_back(volumeIdx);
 385                                 }
 386                         }
 387                 }
 388         }
 389
 390         void CSpatialIndex::UpdateVolumeBounds(const SpatialVolumeId& id, const CSpatialVolumeBounds& bounds)
 391         {
 392                 if(id != SpatialVolumeId::s_invalid)
 393                 {
 394                         CRY_PROFILE_FUNCTION(PROFILE_GAME);
 395
 396                         const uint32 volumeCount = m_volumes.size();
 397                         const uint32 volumeIdx = VolumeIdxFromId(id);
 398                         CRY_ASSERT(volumeIdx < volumeCount);
 399                         if(volumeIdx < volumeCount)
 400                         {
 401                                 SVolume& volume = m_volumes[volumeIdx];
 402                                 CRY_ASSERT(volume.id == id);
 403                                 if(volume.id == id)
 404                                 {
 405                                         volume.bounds                       = bounds;
 406                                         m_broadPhaseVolumes[volumeIdx].aabb = bounds.CalculateAABB();
 407                                 }
 408                         }
 409                 }
 410         }
 411
 412         void CSpatialIndex::SetVolumeTags(const SpatialVolumeId& id, ESpatialVolumeTags tags, bool bValue)
 413         {
 414                 if(id != SpatialVolumeId::s_invalid)
 415                 {
 416                         const uint32 volumeCount = m_volumes.size();
 417                         const uint32 volumeIdx = VolumeIdxFromId(id);
 418                         CRY_ASSERT(volumeIdx < volumeCount);
 419                         if(volumeIdx < volumeCount)
 420                         {
 421                                 SVolume& volume = m_volumes[volumeIdx];
 422                                 CRY_ASSERT(volume.id == id);
 423                                 if(volume.id == id)
 424                                 {
 425                                         if(bValue)
 426                                         {
 427                                                 m_broadPhaseVolumes[volumeIdx].tags |= tags;
 428                                         }
 429                                         else
 430                                         {
 431                                                 m_broadPhaseVolumes[volumeIdx].tags &= ~tags;
 432                                         }
 433                                 }
 434                         }
 435                 }
 436         }
 437
 438         void CSpatialIndex::SetVolumeMonitorTags(const SpatialVolumeId& id, ESpatialVolumeTags tags, bool bValue)
 439         {
 440                 if(id != SpatialVolumeId::s_invalid)
 441                 {
 442                         const uint32 volumeCount = m_volumes.size();
 443                         const uint32 volumeIdx = VolumeIdxFromId(id);
 444                         CRY_ASSERT(volumeIdx < volumeCount);
 445                         if(volumeIdx < volumeCount)
 446                         {
 447                                 SVolume& volume = m_volumes[volumeIdx];
 448                                 CRY_ASSERT(volume.id == id);
 449                                 if(volume.id == id)
 450                                 {
 451                                         if(bValue)
 452                                         {
 453                                                 volume.monitorTags |= tags;
 454                                         }
 455                                         else
 456                                         {
 457                                                 volume.monitorTags &= ~tags;
 458                                         }
 459                                 }
 460                         }
 461                 }
 462         }
 463
 464         SSpatialVolumeParams CSpatialIndex::GetVolumeParams(const SpatialVolumeId& id) const
 465         {
 466                 if(id != SpatialVolumeId::s_invalid)
 467                 {
 468                         const uint32 volumeCount = m_volumes.size();
 469                         const uint32 volumeIdx = VolumeIdxFromId(id);
 470                         CRY_ASSERT(volumeIdx < volumeCount);
 471                         if(volumeIdx < volumeCount)
 472                         {
 473                                 const SVolume& volume = m_volumes[volumeIdx];
 474                                 CRY_ASSERT(volume.id == id);
 475                                 if(volume.id == id)
 476                                 {
 477                                         SSpatialVolumeParams volumeParams;
 478                                         volumeParams.bounds      = volume.bounds;
 479                                         volumeParams.tags        = m_broadPhaseVolumes[volumeIdx].tags;
 480                                         volumeParams.monitorTags = volume.monitorTags;
 481                                         volumeParams.entityId    = volume.entityId;
 482                                         return volumeParams;
 483                                 }
 484                         }
 485                 }
 486                 return SSpatialVolumeParams();
 487         }
 488
 489         void CSpatialIndex::Query(const SpatialVolumeId& id, ESpatialVolumeTags tags, SpatialVolumeIds& results)
 490         {
 491                 CRY_PROFILE_FUNCTION(PROFILE_GAME);
 492                 if(id != SpatialVolumeId::s_invalid)
 493                 {
 494                         const uint32 volumeCount = m_volumes.size();
 495                         const uint32 volumeIdx = VolumeIdxFromId(id);
 496                         CRY_ASSERT(volumeIdx < volumeCount);
 497                         if(volumeIdx < volumeCount)
 498                         {
 499                                 SVolume& volume = m_volumes[volumeIdx];
 500                                 CRY_ASSERT(volume.id == id);
 501                                 if(volume.id == id)
 502                                 {
 503                                         // Perform broad phase query.
 504                                         m_broadPhaseResults.clear();
 505                                         BroadPhaseQuery(volumeIdx, tags, m_broadPhaseResults);
 506                                         // Perform narrow phase tests.
 507                                         for(uint32 otherVolumeIdx : m_broadPhaseResults)
 508                                         {
 509                                                 SVolume& otherVolume = m_volumes[otherVolumeIdx];
 510                                                 if(volume.bounds.Overlap(otherVolume.bounds))
 511                                                 {
 512                                                         results.push_back(otherVolume.id);
 513                                                 }
 514                                         }
 515                                         // Sort results by index.
 516                                         std::sort(results.begin(), results.end(), SCompareVolumeIds());
 517                                 }
 518                         }
 519                 }
 520         }
 521
 522         void CSpatialIndex::Update()
 523         {
 524                 CRY_PROFILE_FUNCTION(PROFILE_GAME);
 525                 UpdateMonitoredVolumes();
 526                 ProcessEventQueue(m_eventQueue);
 527                 /*if(EnvCVars::sc_DebugDrawDetectionVolumes == 1)
 528                 {
 529                         DebugDraw();
 530                 }*/
 531         }
 532
 533         ESpatialVolumeTags CSpatialIndex::CreateTag(const SSpatialVolumeTagName& tagName) const
 534         {
 535                 const int tagIdx = m_pSettings->tagNames.find(tagName.value.c_str());
 536                 if(tagIdx != Serialization::StringList::npos)
 537                 {
 538                         return static_cast<ESpatialVolumeTags>(m_pSettings->tagValues[tagIdx]);
 539                 }
 540                 return ESpatialVolumeTags::None;
 541         }
 542
 543         ESpatialVolumeTags CSpatialIndex::CreateTags(const SpatialVolumeTagNames& tagNames) const
 544         {
 545                 ESpatialVolumeTags result = ESpatialVolumeTags::None;
 546                 for(const SSpatialVolumeTagName& tagName : tagNames)
 547                 {
 548                         result |= CreateTag(tagName);
 549                 }
 550                 return result;
 551         }
 552
 553         const Serialization::StringList& CSpatialIndex::GetTagNames() const
 554         {
 555                 return m_pSettings->tagNames;
 556         }
 557
 558         const SpatialVolumeTagValues& CSpatialIndex::GetTagValues() const
 559         {
 560                 return m_pSettings->tagValues;
 561         }
 562
 563         SpatialVolumeId CSpatialIndex::GenerateVolumeId(uint32 volumeIdx)
 564         {
 565                 const uint32          salt = m_salt ++;
 566                 const SpatialVolumeId volumeId((volumeIdx & s_volumeIdxMask) | ((salt << s_volumeSaltShift) & s_volumeSaltMask));
 567                 CRY_ASSERT(VolumeIdxFromId(volumeId) == volumeIdx);
 568                 return volumeId;
 569         }
 570
 571         uint32 CSpatialIndex::VolumeIdxFromId(const SpatialVolumeId& id) const
 572         {
 573                 return id.GetValue() & s_volumeIdxMask;
 574         }
 575
 576         inline bool CSpatialIndex::CompareVolumeIds(const SpatialVolumeId& lhs, const SpatialVolumeId& rhs) const
 577         {
 578                 return (lhs.GetValue() & s_volumeIdxMask) < (rhs.GetValue() & s_volumeIdxMask);
 579         }
 580
 581         void CSpatialIndex::BroadPhaseQuery(uint32 volumeIdx, ESpatialVolumeTags tags, VolumeIdxs& results) const
 582         {
 583                 const SBroadPhaseVolume broadPhaseVolume = m_broadPhaseVolumes[volumeIdx];
 584                 for(uint32 otherVolumeIdx = 0, volumeCount = m_volumes.size(); otherVolumeIdx < volumeCount; ++ otherVolumeIdx)
 585                 {
 586                         if(otherVolumeIdx != volumeIdx)
 587                         {
 588                                 const SBroadPhaseVolume& otherBroadPhaseVolume = m_broadPhaseVolumes[otherVolumeIdx];
 589                                 if((tags & otherBroadPhaseVolume.tags) != 0)
 590                                 {
 591                                         if(Overlap::AABB_AABB(broadPhaseVolume.aabb, otherBroadPhaseVolume.aabb))
 592                                         {
 593                                                 results.push_back(otherVolumeIdx);
 594                                         }
 595                                 }
 596                         }
 597                 }
 598         }
 599
 600         void CSpatialIndex::UpdateMonitoredVolumes()
 601         {
 602                 CRY_PROFILE_FUNCTION(PROFILE_GAME);
 603                 // Update monitored volumes.
 604                 for(SVolume& volume : m_volumes)
 605                 {
 606                         // Query for overlapping volumes?
 607                         m_monitorResults.clear();
 608                         if(volume.monitorTags != ESpatialVolumeTags::None)
 609                         {
 610                                 Query(volume.id, volume.monitorTags, m_monitorResults);
 611                         }
 612                         // Check for volumes leaving monitored volume.
 613                         for(uint32 cacheVolumeIdx = 0, cacheVolumeCount = volume.monitorCache.size(); cacheVolumeIdx < cacheVolumeCount; )
 614                         {
 615                                 const SpatialVolumeId      cacheVolumeId = volume.monitorCache[cacheVolumeIdx];
 616
 617
 618                                 SpatialVolumeIds::iterator itLowerBoundVolume = std::lower_bound(m_monitorResults.begin(), m_monitorResults.end(), cacheVolumeId, SCompareVolumeIds());
 619
 620                                 if((itLowerBoundVolume == m_monitorResults.end()) || (*itLowerBoundVolume != cacheVolumeId))
 621                                 {
 622                                         SSpatialIndexEvent event;
 623                                         event.id           = ESpatialIndexEventId::Leaving;
 624                                         event.volumeIds[0] = volume.id;
 625                                         event.volumeIds[1] = cacheVolumeId;
 626                                         m_eventQueue.push_back(event);
 627
 628                                         volume.monitorCache.erase(volume.monitorCache.begin() + cacheVolumeIdx);
 629                                         -- cacheVolumeCount;
 630                                 }
 631                                 else
 632                                 {
 633                                         ++ cacheVolumeIdx;
 634                                 }
 635                         }
 636                         // Check for volumes entering monitored volume.
 637                         for(uint32 newVolumeIdx = 0, newVolumeCount = m_monitorResults.size(); newVolumeIdx < newVolumeCount; ++ newVolumeIdx)
 638                         {
 639                                 const SpatialVolumeId      newVolumeId = m_monitorResults[newVolumeIdx];
 640                                 SpatialVolumeIds::iterator itLowerBoundVolume = std::lower_bound(volume.monitorCache.begin(), volume.monitorCache.end(), newVolumeId);
 641                                 if((itLowerBoundVolume == volume.monitorCache.end()) || (*itLowerBoundVolume != newVolumeId))
 642                                 {
 643                                         volume.monitorCache.insert(itLowerBoundVolume, newVolumeId);
 644
 645                                         SSpatialIndexEvent event;
 646                                         event.id           = ESpatialIndexEventId::Entering;
 647                                         event.volumeIds[0] = volume.id;
 648                                         event.volumeIds[1] = newVolumeId;
 649                                         m_eventQueue.push_back(event);
 650                                 }
 651                         }
 652                 }
 653         }
 654
 655         void CSpatialIndex::ProcessEventQueue(EventQueue& eventQueue) const
 656         {
 657                 CRY_PROFILE_FUNCTION(PROFILE_GAME);
 658                 // Send out all events in queue. N.B. This is performed after the update logic in order to reduce cache misses.
 659                 for(const SSpatialIndexEvent& event : eventQueue)
 660                 {
 661                         const SVolume& volume = m_volumes[VolumeIdxFromId(event.volumeIds[0])];
 662                         if(volume.eventCallback)
 663                         {
 664                                 volume.eventCallback(event);
 665                         }
 666                 }
 667                 eventQueue.clear();
 668         }
 669
 670         void CSpatialIndex::DebugDraw() const
 671         {
 672                 IRenderAuxGeom& renderAuxGeom = *gEnv->pRenderer->GetIRenderAuxGeom();
 673                 for(const SVolume& volume : m_volumes)
 674                 {
 675                         ColorB color = ColorB(0, 150, 0);
 676                         if(!volume.monitorCache.empty())
 677                         {
 678                                 color = ColorB(150, 0, 0);
 679                         }
 680                         else if(volume.monitorTags != ESpatialVolumeTags::None)
 681                         {
 682                                 color = ColorB(150, 150, 0);
 683                         }
 684                         switch(volume.bounds.GetShape())
 685                         {
 686                         case ESpatialVolumeShape::Box:
 687                                 {
 688                                         renderAuxGeom.DrawOBB(volume.bounds.AsBox(), Matrix34(IDENTITY), false, color, eBBD_Faceted);
 689                                         break;
 690                                 }
 691                         case ESpatialVolumeShape::Sphere:
 692                                 {
 693                                         SAuxGeomRenderFlags prevRenderFlags = renderAuxGeom.GetRenderFlags();
 694                                         renderAuxGeom.SetRenderFlags(e_Def3DPublicRenderflags | e_AlphaBlended);
 695                                         renderAuxGeom.DrawSphere(volume.bounds.AsSphere().center, volume.bounds.AsSphere().radius, ColorB(color.r, color.g, color.b, 64), false);
 696                                         renderAuxGeom.SetRenderFlags(prevRenderFlags);
 697                                         break;
 698                                 }
 699                         case ESpatialVolumeShape::Point:
 700                                 {
 701                                         renderAuxGeom.DrawSphere(volume.bounds.AsPoint(), 0.1f, color, false);
 702                                         break;
 703                                 }
 704                         }
 705                 }
 706         }
 707 }