BVB Source Codes

CRYENGINE Show ClusterDetector.cpp Source code

Return Download CRYENGINE: download ClusterDetector.cpp Source code - Download CRYENGINE Source code - Type:.cpp
  1. // Copyright 2001-2016 Crytek GmbH / Crytek Group. All rights reserved.
  2.  
  3. #include "StdAfx.h"
  4. #include "ClusterDetector.h"
  5.  
  6. #define MIN_ACCEPTABLE_DISTANCE_DIFFERENCE_SQ sqr(0.1f)
  7.  
  8. /* **********************
  9.    ClusterInternalState
  10.  ** ********************** */
  11.  
  12. void ClusterDetector::CurrentRequestState::Reset()
  13. {
  14.         pCurrentRequest = NULL;
  15.         stl::free_container(clusters);
  16.         aabbCenter.zero();
  17.         spawningPositionForNextCluster.zero();
  18. }
  19.  
  20. /* *********************
  21.     ClusterDetector
  22.  ** ********************* */
  23.  
  24. ClusterDetector::ClusterDetector()
  25.         : m_nextUniqueRequestID(0)
  26.         , m_status(eStatus_Waiting)
  27. {
  28. }
  29.  
  30. IClusterDetector::IClusterRequestPair ClusterDetector::CreateNewRequest()
  31. {
  32.         ClusterRequestID uniqueId = GenerateUniqueClusterRequestId();
  33.         m_requests.push_back(ClusterRequestPair(uniqueId, ClusterRequest()));
  34.         return std::make_pair(uniqueId, &(m_requests.back().second));
  35. }
  36.  
  37. void ClusterDetector::QueueRequest(const ClusterRequestID requestId)
  38. {
  39.         RequestsList::iterator it = m_requests.begin();
  40.         while (it != m_requests.end())
  41.         {
  42.                 if (it->first == requestId)
  43.                 {
  44.                         if (it->second.GetNumberOfPoint() != 0)
  45.                         {
  46.                                 it->second.m_state = ClusterRequest::eRequestState_ReadyToBeProcessed;
  47.                         }
  48.                         else
  49.                         {
  50.                                 // If an empty request is queued, let's remove it
  51.                                 it = m_requests.erase(it);
  52.                         }
  53.  
  54.                         return;
  55.                 }
  56.                 ++it;
  57.         }
  58.  
  59. }
  60.  
  61. void ClusterDetector::Reset()
  62. {
  63.         m_internalState.Reset();
  64.         m_requests.clear();
  65.         m_nextUniqueRequestID = 0;
  66.         m_status = eStatus_Waiting;
  67. }
  68.  
  69. ClusterDetector::ClusterRequestID ClusterDetector::GenerateUniqueClusterRequestId()
  70. {
  71.         return ++m_nextUniqueRequestID;
  72. }
  73.  
  74. void ClusterDetector::Update(float frameDeltaTime)
  75. {
  76.         if (m_requests.empty())
  77.                 return;
  78.  
  79.         if (m_status == eStatus_Waiting)
  80.         {
  81.                 bool hasRequestReadyToProcess = InitializeNextRequest();
  82.                 if (!hasRequestReadyToProcess)
  83.                         return;
  84.  
  85.                 m_status = eStatus_ClusteringInProgress;
  86.         }
  87.         // At this point a current request should always be set
  88.         assert(m_internalState.pCurrentRequest);
  89.  
  90.         if (m_status == eStatus_ClusteringInProgress)
  91.         {
  92.                 /*
  93.                    The clustering algorithm used is K-Mean.
  94.                    The algorithm steps are the following:
  95.                    1) K-cluster centers are placed in the world (we place them spread
  96.                      over a circle shape in the center of the bounding box containing
  97.                      the points we want to cluster)
  98.                    2) Per each step:
  99.                    a) We calculate the distance of each point from each center and we
  100.                       assign a point to the closest cluster center
  101.                    b) We calculate the new position of each cluster center as the middle
  102.                       point of the points that belongs to that cluster
  103.                    3) We iterate until no point is assigned to a different cluster.
  104.  
  105.                    As additional step for our needs we also try to calculate the optimal
  106.                    clusters number. To do that we assign a maximum distance we allow for
  107.                    a point to be considered part of the cluster.
  108.                    If after each refinement we have point in a group that is at a further
  109.                    distance than the maximum allowed we add a new cluster center and we
  110.                    proceed to re-cluster the points.
  111.                  */
  112.  
  113.                 while (true)
  114.                 {
  115.                         bool isFurtherRefinementNeeded = false;
  116.                         while (true)
  117.                         {
  118.                                 ResetClustersElements();
  119.                                 isFurtherRefinementNeeded = ExecuteClusteringStep();
  120.                                 UpdateClustersCenter();
  121.                                 if (!isFurtherRefinementNeeded)
  122.                                         break;
  123.                         }
  124.  
  125.                         if (IsNewClusterNeeded())
  126.                                 AddNewCluster();
  127.                         else
  128.                                 break;
  129.                 }
  130.  
  131.                 m_status = eStatus_ClusteringCompleted;
  132.         }
  133.  
  134.         if (m_status == eStatus_ClusteringCompleted)
  135.         {
  136.                 m_internalState.pCurrentRequest->m_totalClustersNumber = m_internalState.clusters.size();
  137.                 m_internalState.pCurrentRequest->m_callback(m_internalState.pCurrentRequest);
  138.  
  139.                 m_internalState.Reset();
  140.                 m_requests.pop_front();
  141.  
  142.                 m_status = eStatus_Waiting;
  143.         }
  144. }
  145.  
  146. bool ClusterDetector::IsNewClusterNeeded()
  147. {
  148.         bool isNewClusterNeeded = false;
  149.         Cluster::DistancePointPair furtherPointFromAClusterCenter(FLT_MIN, Vec3(ZERO));
  150.         ClusterDetector::ClustersArray::iterator it = m_internalState.clusters.begin();
  151.         for (; it != m_internalState.clusters.end(); ++it)
  152.         {
  153.                 if (it->pointAtMaxDistanceSqFromCenter.first > m_internalState.pCurrentRequest->m_maxDistanceSq &&
  154.                     it->pointAtMaxDistanceSqFromCenter.first > furtherPointFromAClusterCenter.first)
  155.                 {
  156.                         furtherPointFromAClusterCenter = it->pointAtMaxDistanceSqFromCenter;
  157.                         isNewClusterNeeded = true;
  158.                 }
  159.         }
  160.         m_internalState.spawningPositionForNextCluster = furtherPointFromAClusterCenter.second;
  161.         return isNewClusterNeeded;
  162. }
  163.  
  164. bool ClusterDetector::ExecuteClusteringStep()
  165. {
  166.         FUNCTION_PROFILER(GetISystem(), PROFILE_AI);
  167.  
  168.         bool isFurtherRefinementNeeded = false;
  169.         ClusterRequest::PointsList& points = m_internalState.pCurrentRequest->m_points;
  170.         ClusterRequest::PointsList::iterator pointIt = points.begin();
  171.         for (; pointIt != points.end(); ++pointIt)
  172.         {
  173.                 float minDistanceSq = FLT_MAX;
  174.                 size_t bestClusterId = ~0;
  175.                 ClusterDetector::ClustersArray::iterator clusterIt = m_internalState.clusters.begin();
  176.                 for (; clusterIt != m_internalState.clusters.end(); ++clusterIt)
  177.                 {
  178.                         const Vec3& clusterCenter = clusterIt->centerPos;
  179.                         float curDistanceSq = Distance::Point_PointSq(clusterCenter, pointIt->pos);
  180.  
  181.                         if ((minDistanceSq - curDistanceSq) > MIN_ACCEPTABLE_DISTANCE_DIFFERENCE_SQ)
  182.                         {
  183.                                 minDistanceSq = curDistanceSq;
  184.                                 bestClusterId = clusterIt - m_internalState.clusters.begin();
  185.                         }
  186.                 }
  187.                 if (pointIt->clusterId != bestClusterId)
  188.                 {
  189.                         isFurtherRefinementNeeded = true;
  190.                         pointIt->clusterId = bestClusterId;
  191.                 }
  192.                 assert(pointIt->clusterId < m_internalState.clusters.size());
  193.                 Cluster& clusterForCurrentPoint = m_internalState.clusters[pointIt->clusterId];
  194.                 if ((minDistanceSq - clusterForCurrentPoint.pointAtMaxDistanceSqFromCenter.first) >= .0f)
  195.                 {
  196.                         clusterForCurrentPoint.pointAtMaxDistanceSqFromCenter = Cluster::DistancePointPair(minDistanceSq, pointIt->pos);
  197.                 }
  198.  
  199.                 ++(clusterForCurrentPoint.numberOfElements);
  200.         }
  201.  
  202.         return isFurtherRefinementNeeded;
  203. }
  204.  
  205. ClusterDetector::ClusterRequestPair* ClusterDetector::ChooseRequestToServe()
  206. {
  207.         RequestsList::iterator it = m_requests.begin();
  208.         for (; it != m_requests.end(); ++it)
  209.         {
  210.                 if (it->second.m_state == ClusterRequest::eRequestState_ReadyToBeProcessed)
  211.                 {
  212.                         return &(*it);
  213.                 }
  214.         }
  215.         return NULL;
  216. }
  217.  
  218. size_t ClusterDetector::CalculateRuleOfThumbClusterSize(const size_t numberOfPoints)
  219. {
  220.         const size_t halfPoints = numberOfPoints >> 1;
  221.         const float approxSqrtHalfPoints = sqrt_fast_tpl(static_cast<float>(halfPoints));
  222.         return static_cast<size_t>(approxSqrtHalfPoints + .5f);
  223. }
  224.  
  225. bool ClusterDetector::InitializeNextRequest()
  226. {
  227.         FUNCTION_PROFILER(GetISystem(), PROFILE_AI);
  228.  
  229.         m_internalState.Reset();
  230.  
  231.         ClusterDetector::ClusterRequestPair* pCurrentRequestPair = ChooseRequestToServe();
  232.         if (pCurrentRequestPair == NULL)
  233.                 return false;
  234.  
  235.         m_internalState.currentRequestId = pCurrentRequestPair->first;
  236.         m_internalState.pCurrentRequest = &(pCurrentRequestPair->second);
  237.  
  238.         //Calculating the center of the aabb containing all the points of the request
  239.  
  240.         const ClusterRequest::PointsList& points = m_internalState.pCurrentRequest->m_points;
  241.         const float positionsWeight = 1.0f / points.size();
  242.         ClusterRequest::PointsList::const_iterator pointIt = points.begin();
  243.         for (; pointIt != points.end(); ++pointIt)
  244.         {
  245.                 m_internalState.aabbCenter += pointIt->pos;
  246.         }
  247.         m_internalState.aabbCenter *= positionsWeight;
  248.  
  249.         const size_t startupClusterNumber = std::max(CalculateRuleOfThumbClusterSize(m_internalState.pCurrentRequest->m_points.size()), size_t(1));
  250.         m_internalState.clusters.reserve(2 * startupClusterNumber);
  251.         m_internalState.clusters = ClustersArray(startupClusterNumber);
  252.  
  253.         InitializeClusters();
  254.         return true;
  255. }
  256.  
  257. void ClusterDetector::InitializeClusters()
  258. {
  259.         float spreadAngleUnit = (2.0f * gf_PI) / m_internalState.clusters.size();
  260.         ClusterDetector::ClustersArray::iterator it = m_internalState.clusters.begin();
  261.         for (; it != m_internalState.clusters.end(); ++it)
  262.         {
  263.                 size_t clusterIndex = it - m_internalState.clusters.begin();
  264.                 const Vec3& pos = CalculateInitialClusterPosition(clusterIndex, spreadAngleUnit);
  265.                 it->centerPos = pos;
  266.         }
  267. }
  268.  
  269. Vec3 ClusterDetector::CalculateInitialClusterPosition(const size_t clusterIndex, const float spreadAngleUnit) const
  270. {
  271.         FUNCTION_PROFILER(GetISystem(), PROFILE_AI);
  272.  
  273.         Vec3 offset(2.0f, 0.0f, 0.0f);
  274.         offset = offset.GetRotated(Vec3Constants<float>::fVec3_OneZ, spreadAngleUnit * clusterIndex);
  275.         return m_internalState.aabbCenter + offset;
  276. }
  277.  
  278. void ClusterDetector::UpdateClustersCenter()
  279. {
  280.         FUNCTION_PROFILER(GetISystem(), PROFILE_AI);
  281.  
  282.         ClusterDetector::ClustersArray::iterator it = m_internalState.clusters.begin();
  283.         for (; it != m_internalState.clusters.end(); ++it)
  284.         {
  285.                 IF_UNLIKELY (it->numberOfElements == 0)
  286.                 {
  287.                         // This should not happen anymore but if it does, for specific
  288.                         // of layout the points to be clustered, it's still gracefully
  289.                         // handled and it won't cause any issue
  290.                         continue;
  291.                 }
  292.                 it->centerPos.zero();
  293.                 it->pointsWeight = 1.0f / it->numberOfElements;
  294.         }
  295.  
  296.         const ClusterRequest::PointsList& points = m_internalState.pCurrentRequest->m_points;
  297.         ClusterRequest::PointsList::const_iterator pointIt = points.begin();
  298.         for (; pointIt != points.end(); ++pointIt)
  299.         {
  300.                 Cluster& c = m_internalState.clusters[pointIt->clusterId];
  301.                 c.centerPos += pointIt->pos * c.pointsWeight;
  302.         }
  303. }
  304.  
  305. void ClusterDetector::ResetClustersElements()
  306. {
  307.         ClusterDetector::ClustersArray::iterator it = m_internalState.clusters.begin();
  308.         for (; it != m_internalState.clusters.end(); ++it)
  309.         {
  310.                 it->numberOfElements = 0;
  311.                 it->pointsWeight = 1.0f;
  312.                 it->pointAtMaxDistanceSqFromCenter = Cluster::DistancePointPair(FLT_MIN, Vec3(ZERO));
  313.         }
  314. }
  315.  
  316. bool ClusterDetector::AddNewCluster()
  317. {
  318.         m_internalState.clusters.push_back(Cluster());
  319.         if (!m_internalState.spawningPositionForNextCluster.IsZero())
  320.         {
  321.                 Cluster& c = m_internalState.clusters.back();
  322.                 c.centerPos = m_internalState.spawningPositionForNextCluster;
  323.         }
  324.         else
  325.         {
  326.                 InitializeClusters();
  327.         }
  328.         return true;
  329. }
  330.  
downloadClusterDetector.cpp Source code - Download CRYENGINE Source code
Related Source Codes/Software:
postal - 2017-06-11
reactide - Reactide is the first dedicated IDE for React web ... 2017-06-11
rkt - rkt is a pod-native container engine for Linux. It... 2017-06-11
uWebSockets - Tiny WebSockets https://for... 2017-06-11
realworld - TodoMVC for the RealWorld - Exemplary fullstack Me... 2017-06-11
CRYENGINE - CRYENGINE is a powerful real-time game development... 2017-06-11
goreplay - GoReplay is an open-source tool for capturing and ... 2017-06-10
pyenv - Simple Python version management 2017-06-10
redux-saga - An alternative side effect model for Redux apps ... 2017-06-10
angular-starter - 2017-06-10

 Back to top