ParaView
vtkStreamingPriorityQueue.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: ParaView
4  Module: vtkStreamingPriorityQueue
5 
6  Copyright (c) Kitware, Inc.
7  All rights reserved.
8  See Copyright.txt or http://www.paraview.org/HTML/Copyright.html for details.
9 
10  This software is distributed WITHOUT ANY WARRANTY; without even
11  the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12  PURPOSE. See the above copyright notice for more information.
13 
14 =========================================================================*/
25 #ifndef vtkStreamingPriorityQueue_h
26 #define vtkStreamingPriorityQueue_h
27 
28 #include "vtkBoundingBox.h"
29 #include "vtkMath.h"
30 
31 #include <algorithm>
32 #include <queue>
33 
34 //*****************************************************************************
35 namespace
36 {
37 // this code is stolen from vtkFrustumCoverageCuller.
38 double vtkComputeScreenCoverage(const double planes[24], const double bounds[6], double& distance,
39  double& centeredness, double& itemCoverage)
40 {
41  distance = 0.0;
42  centeredness = 0.0;
43  itemCoverage = 0.0;
44 
45  // a duff dataset like a polydata with no cells will have bad bounds
46  if (!vtkMath::AreBoundsInitialized(const_cast<double*>(bounds)))
47  {
48  return 0.0;
49  }
50  double screen_bounds[4];
51 
52  double center[3];
53  center[0] = (bounds[0] + bounds[1]) / 2.0;
54  center[1] = (bounds[2] + bounds[3]) / 2.0;
55  center[2] = (bounds[4] + bounds[5]) / 2.0;
56  double radius = 0.5 * sqrt((bounds[1] - bounds[0]) * (bounds[1] - bounds[0]) +
57  (bounds[3] - bounds[2]) * (bounds[3] - bounds[2]) +
58  (bounds[5] - bounds[4]) * (bounds[5] - bounds[4]));
59  for (int i = 0; i < 6; i++)
60  {
61  // Compute how far the center of the sphere is from this plane
62  double d = planes[i * 4 + 0] * center[0] + planes[i * 4 + 1] * center[1] +
63  planes[i * 4 + 2] * center[2] + planes[i * 4 + 3];
64  // If d < -radius the prop is not within the view frustum
65  if (d < -radius)
66  {
67  return 0.0;
68  }
69 
70  // The first four planes are the ones bounding the edges of the
71  // view plane (the last two are the near and far planes) The
72  // distance from the edge of the sphere to these planes is stored
73  // to compute coverage.
74  if (i < 4)
75  {
76  screen_bounds[i] = d - radius;
77  }
78  // The fifth plane is the near plane - use the distance to
79  // the center (d) as the value to sort by
80  if (i == 4)
81  {
82  distance = d;
83  }
84  }
85 
86  // If the prop wasn't culled during the plane tests...
87  // Compute the width and height of this slice through the
88  // view frustum that contains the center of the sphere
89  double full_w = screen_bounds[0] + screen_bounds[1] + 2.0 * radius;
90  double full_h = screen_bounds[2] + screen_bounds[3] + 2.0 * radius;
91 
92  // Multiply the distances from each side to get a measure of how centered
93  // the sphere is on the screen (divide by half the length in that dimension
94  // squared to get a measure of how centered the object is in that dimension).
95  double measure_w =
96  (screen_bounds[0] + radius) * (screen_bounds[1] + radius) / (full_w * full_w / 4.0);
97  double measure_h =
98  (screen_bounds[2] + radius) * (screen_bounds[3] + radius) / (full_h * full_h / 4.0);
99 
100  // If the object is off the edge of the screen, treat it as if it is just
101  // inside the edge (which we know it is since it wasn't culled)
102  if (measure_w < 0.01)
103  {
104  measure_w = 0.01;
105  }
106  if (measure_h < 0.01)
107  {
108  measure_h = 0.01;
109  }
110  centeredness = measure_w * measure_h;
111 
112  double w = 2 * radius;
113  double h = 2 * radius;
114  if (screen_bounds[0] < 0.0)
115  {
116  w += screen_bounds[0];
117  }
118  if (screen_bounds[1] < 0.0)
119  {
120  w += screen_bounds[1];
121  }
122  if (screen_bounds[2] < 0.0)
123  {
124  h += screen_bounds[2];
125  }
126  if (screen_bounds[3] < 0.0)
127  {
128  h += screen_bounds[3];
129  }
130  itemCoverage = h * w / (4 * radius * radius);
131 
132  // Subtract from the full width to get the width of the square
133  // enclosing the circle slice from the sphere in the plane
134  // through the center of the sphere. If the screen bounds for
135  // the left and right planes (0,1) are greater than zero, then
136  // the edge of the sphere was a positive distance away from the
137  // plane, so there is a gap between the edge of the plane and
138  // the edge of the box.
139  double part_w = full_w;
140  if (screen_bounds[0] > 0.0)
141  {
142  part_w -= screen_bounds[0];
143  }
144  if (screen_bounds[1] > 0.0)
145  {
146  part_w -= screen_bounds[1];
147  }
148  // Do the same thing for the height with the top and bottom
149  // planes (2,3).
150  double part_h = full_h;
151  if (screen_bounds[2] > 0.0)
152  {
153  part_h -= screen_bounds[2];
154  }
155  if (screen_bounds[3] > 0.0)
156  {
157  part_h -= screen_bounds[3];
158  }
159 
160  // Compute the fraction of coverage
161  if ((full_w * full_h) != 0.0)
162  {
163  return (part_w * part_h) / (full_w * full_h);
164  }
165 
166  return 0;
167 }
168 }
169 
171 {
172 public:
173  unsigned int Identifier; // this is used to identify this block when making a
174  // request.
175  double Refinement; // Where lower the Refinement cheaper is the
176  // processing for this block. 0 is considered as
177  // undefined.
178  double ScreenCoverage; // computed coverage for the block.
179  double Centeredness; // how centered the object is on the screen (1 is centered, 0.0001 is near
180  // the edge)
181  double Priority; // Computed priority for this block.
182  double Distance;
184  double ItemCoverage; // amount of the item that is onscreen (fraction, if whole item is onscreen
185  // it is 1)
186  vtkBoundingBox Bounds; // Bounds for the block.
187 
189  : Identifier(0)
190  , Refinement(0)
191  , ScreenCoverage(0)
192  , Priority(0)
193  , Distance(0)
194  , AmountOfDetail(-1)
195  {
196  }
197 };
198 
200 {
201 public:
203  const vtkStreamingPriorityQueueItem& me, const vtkStreamingPriorityQueueItem& other) const
204  {
205  return me.Priority < other.Priority;
206  }
207 };
208 
209 template <typename Comparator = vtkStreamingPriorityQueueItemComparator>
210 class vtkStreamingPriorityQueue : public std::priority_queue<vtkStreamingPriorityQueueItem,
211  std::vector<vtkStreamingPriorityQueueItem>, Comparator>
212 {
213 public:
215 
218  void UpdatePriorities(const double view_planes[24], const double clamp_bounds[6])
219  {
220  bool clamp_bounds_initialized =
221  (vtkMath::AreBoundsInitialized(const_cast<double*>(clamp_bounds)) != 0);
222  vtkBoundingBox clampBox(const_cast<double*>(clamp_bounds));
224 
225  vtkStreamingPriorityQueue current_queue;
226  std::swap(current_queue, *this);
227 
228  for (; !current_queue.empty(); current_queue.pop())
229  {
230  vtkStreamingPriorityQueueItem item = current_queue.top();
231  if (!item.Bounds.IsValid())
232  {
233  continue;
234  }
235 
236  double block_bounds[6];
237  item.Bounds.GetBounds(block_bounds);
238 
239  if (clamp_bounds_initialized)
240  {
241  if (!clampBox.ContainsPoint(block_bounds[0], block_bounds[2], block_bounds[4]) &&
242  !clampBox.ContainsPoint(block_bounds[1], block_bounds[3], block_bounds[5]))
243  {
244  // if the block_bounds is totally outside the clamp_bounds, skip it.
245  continue;
246  }
247  }
248 
249  double refinement2 = item.Refinement * item.Refinement;
250  double distance, centeredness, itemCoverage;
251  double coverage =
252  vtkComputeScreenCoverage(view_planes, block_bounds, distance, centeredness, itemCoverage);
253  item.ScreenCoverage = coverage;
254  item.Distance = distance;
255  item.Centeredness = centeredness;
256  item.ItemCoverage = itemCoverage;
257 
258  if (coverage > 0)
259  {
260  // item.Priority = coverage / (item.Refinement/* * distance*/) ;// / distance;
261  // //coverage * coverage / ( 1 + refinement2 + distance);
262  item.Priority = coverage * coverage * centeredness / (1 + refinement2 + distance);
263  }
264  else
265  {
266  item.Priority = 0;
267  }
268  this->push(item);
269  }
270  }
271 };
272 #endif
273 
274 // VTK-HeaderTest-Exclude: vtkStreamingPriorityQueue.h
void UpdatePriorities(const double view_planes[24], const double clamp_bounds[6])
Updates the priorities of items in the queue.
bool operator()(const vtkStreamingPriorityQueueItem &me, const vtkStreamingPriorityQueueItem &other) const
provides a datastructure for building priority queues.