11 #ifndef hifi_PrioritySortUtil_h
12 #define hifi_PrioritySortUtil_h
14 #include <glm/glm.hpp>
16 #include "NumericalConstants.h"
17 #include "shared/ConicalViewFrustum.h"
21 const float OUT_OF_VIEW_PENALTY = -10.0f;
22 const float OUT_OF_VIEW_THRESHOLD = 0.5f * OUT_OF_VIEW_PENALTY;
24 namespace PrioritySortUtil {
26 constexpr
float DEFAULT_ANGULAR_COEF { 1.0f };
27 constexpr
float DEFAULT_CENTER_COEF { 0.5f };
28 constexpr
float DEFAULT_AGE_COEF { 0.25f };
32 virtual ~Sortable() =
default;
34 virtual glm::vec3 getPosition()
const = 0;
35 virtual float getRadius()
const = 0;
36 virtual uint64_t getTimestamp()
const = 0;
38 void setPriority(
float priority) { _priority = priority; }
39 float getPriority()
const {
return _priority; }
41 float _priority { 0.0f };
47 PriorityQueue() =
delete;
48 PriorityQueue(
const ConicalViewFrustums& views) : _views(views), _usecCurrentTime(usecTimestampNow()) { }
49 PriorityQueue(
const ConicalViewFrustums& views,
float angularWeight,
float centerWeight,
float ageWeight)
50 : _views(views), _angularWeight(angularWeight), _centerWeight(centerWeight), _ageWeight(ageWeight)
51 , _usecCurrentTime(usecTimestampNow()) {
54 void setViews(
const ConicalViewFrustums& views) { _views = views; }
56 void setWeights(
float angularWeight,
float centerWeight,
float ageWeight) {
57 _angularWeight = angularWeight;
58 _centerWeight = centerWeight;
59 _ageWeight = ageWeight;
60 _usecCurrentTime = usecTimestampNow();
63 size_t size()
const {
return _vector.size(); }
65 thing.setPriority(computePriority(thing));
66 _vector.push_back(thing);
68 void reserve(
size_t num) {
71 const std::vector<T>& getSortedVector(
int numToSort = 0) {
72 if (numToSort == 0 || numToSort >= (
int)_vector.size()) {
73 std::sort(_vector.begin(), _vector.end(),
74 [](
const T& left,
const T& right) { return left.getPriority() > right.getPriority(); });
76 std::partial_sort(_vector.begin(), _vector.begin() + numToSort, _vector.end(),
77 [](
const T& left,
const T& right) { return left.getPriority() > right.getPriority(); });
84 float computePriority(
const T& thing)
const {
85 float priority = std::numeric_limits<float>::min();
87 for (
const auto& view : _views) {
88 priority = std::max(priority, computePriority(view, thing));
94 float computePriority(
const ConicalViewFrustum& view,
const T& thing)
const {
101 glm::vec3 position = thing.getPosition();
102 glm::vec3 offset = position - view.getPosition();
103 float distance = glm::length(offset) + 0.001f;
104 const float MIN_RADIUS = 0.1f;
105 float radius = glm::max(thing.getRadius(), MIN_RADIUS);
107 float cosineAngle = glm::dot(offset, view.getDirection()) / distance;
108 if (cosineAngle > 0.0f) {
109 cosineAngle = std::sqrt(cosineAngle);
111 float age = float((_usecCurrentTime - thing.getTimestamp()) / USECS_PER_SECOND);
114 float angularSize = radius / distance;
115 float priority = (_angularWeight * angularSize + _centerWeight * cosineAngle) * (age + 1.0f) + _ageWeight * age;
118 if (distance - radius > view.getRadius()) {
119 if (!view.intersects(offset, distance, radius)) {
120 priority += OUT_OF_VIEW_PENALTY;
126 ConicalViewFrustums _views;
127 std::vector<T> _vector;
128 float _angularWeight { DEFAULT_ANGULAR_COEF };
129 float _centerWeight { DEFAULT_CENTER_COEF };
130 float _ageWeight { DEFAULT_AGE_COEF };
131 quint64 _usecCurrentTime { 0 };
136 const uint64_t MAX_UPDATE_RENDERABLES_TIME_BUDGET = 2000;
137 const uint64_t MIN_SORTED_UPDATE_RENDERABLES_TIME_BUDGET = 1000;
138 const uint64_t MAX_UPDATE_AVATARS_TIME_BUDGET = 2000;