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