forked from Kitware/VTK
-
Notifications
You must be signed in to change notification settings - Fork 0
/
vtkFrustumCoverageCuller.cxx
363 lines (334 loc) · 12.1 KB
/
vtkFrustumCoverageCuller.cxx
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
/*=========================================================================
Program: Visualization Toolkit
Module: vtkFrustumCoverageCuller.cxx
Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
All rights reserved.
See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
This software is distributed WITHOUT ANY WARRANTY; without even
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the above copyright notice for more information.
=========================================================================*/
#include "vtkFrustumCoverageCuller.h"
#include "vtkCamera.h"
#include "vtkMath.h"
#include "vtkObjectFactory.h"
#include "vtkProp.h"
#include "vtkRenderer.h"
vtkStandardNewMacro(vtkFrustumCoverageCuller);
// Create a frustum coverage culler with default values
vtkFrustumCoverageCuller::vtkFrustumCoverageCuller()
{
this->MinimumCoverage = 0.0;
this->MaximumCoverage = 1.0;
this->SortingStyle = VTK_CULLER_SORT_NONE;
}
// The coverage is computed for each prop, and a resulting allocated
// render time is computed. This is multiplied by the current allocated
// render time of the prop. After this, props with no allocated time are
// removed from the list (and the list length is shortened) to make sure
// that they are not considered again by another culler or for rendering.
double vtkFrustumCoverageCuller::Cull( vtkRenderer *ren,
vtkProp **propList,
int& listLength,
int& initialized )
{
vtkProp *prop;
double total_time;
double *bounds, center[3];
double radius = 0.0;
double planes[24], d;
double coverage, screen_bounds[4];
double previous_time;
int i, propLoop;
double full_w, full_h, part_w, part_h;
double *allocatedTimeList;
double *distanceList;
int index1, index2;
double tmp;
// We will create a center distance entry for each prop in the list
// If SortingStyle is set to BackToFront or FrontToBack we will then
// sort the props that have a non-zero AllocatedRenderTime by their
// center distance
distanceList = new double[listLength];
// We will return the total time of all props. This is used for
// normalization.
total_time = 0;
// Get the view frustum planes from the active camera
ren->GetActiveCamera()->GetFrustumPlanes(
ren->GetTiledAspectRatio(), planes );
// Keep a list of allocated times to help with sorting / removing
// props later
allocatedTimeList = new double[listLength];
// For each prop, compute coverage
for ( propLoop = 0; propLoop < listLength; propLoop++ )
{
// Get the prop out of the list
prop = propList[propLoop];
// If allocated render time has not been initialized yet (if this
// is the first culler, it hasn't) then the previous time is set
// to 0.0
if ( !initialized )
{
previous_time = 1.0;
}
else
{
previous_time = prop->GetRenderTimeMultiplier();
}
// Get the bounds of the prop and compute an enclosing sphere
bounds = prop->GetBounds();
// We start with a coverage of 1.0 and set it to zero if the prop
// is culled during the plane tests
coverage = 1.0;
// make sure the bounds are defined - they won't be for a 2D prop which
// means that they will never be culled. Maybe this should be changed in
// the future?
if (bounds)
{
// a duff dataset like a polydata with no cells will have bad bounds
if (!vtkMath::AreBoundsInitialized(bounds))
{
coverage = 0.0;
}
else
{
center[0] = (bounds[0] + bounds[1]) / 2.0;
center[1] = (bounds[2] + bounds[3]) / 2.0;
center[2] = (bounds[4] + bounds[5]) / 2.0;
radius = 0.5 * sqrt( ( bounds[1] - bounds[0] ) *
( bounds[1] - bounds[0] ) +
( bounds[3] - bounds[2] ) *
( bounds[3] - bounds[2] ) +
( bounds[5] - bounds[4] ) *
( bounds[5] - bounds[4] ) );
for ( i = 0; i < 6; i++ )
{
// Compute how far the center of the sphere is from this plane
d =
planes[i*4 + 0] * center[0] +
planes[i*4 + 1] * center[1] +
planes[i*4 + 2] * center[2] +
planes[i*4 + 3];
// If d < -radius the prop is not within the view frustum
if ( d < -radius )
{
coverage = 0.0;
i = 7;
}
// The first four planes are the ones bounding the edges of the
// view plane (the last two are the near and far planes) The
// distance from the edge of the sphere to these planes is stored
// to compute coverage.
if ( i < 4 )
{
screen_bounds[i] = d - radius;
}
// The fifth plane is the near plane - use the distance to
// the center (d) as the value to sort by
if ( i == 4 )
{
distanceList[propLoop] = d;
}
}
}
// If the prop wasn't culled during the plane tests...
if ( coverage > 0.0 )
{
// Compute the width and height of this slice through the
// view frustum that contains the center of the sphere
full_w = screen_bounds[0] + screen_bounds[1] + 2.0 * radius;
full_h = screen_bounds[2] + screen_bounds[3] + 2.0 * radius;
// Subtract from the full width to get the width of the square
// enclosing the circle slice from the sphere in the plane
// through the center of the sphere. If the screen bounds for
// the left and right planes (0,1) are greater than zero, then
// the edge of the sphere was a positive distance away from the
// plane, so there is a gap between the edge of the plane and
// the edge of the box.
part_w = full_w;
if ( screen_bounds[0] > 0.0 )
{
part_w -= screen_bounds[0];
}
if ( screen_bounds[1] > 0.0 )
{
part_w -= screen_bounds[1];
}
// Do the same thing for the height with the top and bottom
// planes (2,3).
part_h = full_h;
if ( screen_bounds[2] > 0.0 )
{
part_h -= screen_bounds[2];
}
if ( screen_bounds[3] > 0.0 )
{
part_h -= screen_bounds[3];
}
// Prevent a single point from being culled if we
// are not culling based on screen coverage
if ( ((full_w*full_h == 0.0) ||
(part_w*part_h/(full_w*full_h) <= 0.0)) && this->MinimumCoverage == 0.0 )
{
coverage = 0.0001;
}
// Compute the fraction of coverage
else if ((full_w * full_h)!=0.0)
{
coverage = (part_w * part_h) / (full_w * full_h);
}
else
{
coverage = 0;
}
// Convert this to an allocated render time - coverage less than
// the minimum result in 0.0 time, greater than the maximum result in
// 1.0 time, and in between a linear ramp is used
if ( coverage < this->MinimumCoverage )
{
coverage = 0;
}
else if ( coverage > this->MaximumCoverage )
{
coverage = 1.0;
}
else
{
coverage = (coverage-this->MinimumCoverage) /
this->MaximumCoverage;
}
}
}
// This is a 2D prop - keep them at the beginning of the list in the same
// order they came in (by giving them all the same distance) and set
// the coverage to something small so that they won't get much
// allocated render time (because they aren't LOD it doesn't matter,
// and they generally do draw fast so you don't want to take too much
// time away from the 3D prop because you added a title to your
// window for example) They are put at the beginning of the list so
// that when sorted back to front they will be rendered last.
else
{
distanceList[propLoop] = -VTK_DOUBLE_MAX;
coverage = 0.001;
}
// Multiply the new allocated time by the previous allocated time
coverage *= previous_time;
prop->SetRenderTimeMultiplier( coverage );
// Save this in our array of allocated times which matches the
// prop array. Also save the center distance
allocatedTimeList[propLoop] = coverage;
// Add the time for this prop to the total time
total_time += coverage;
}
// Now traverse the list from the beginning, swapping any zero entries back
// in the list, while preserving the order of the non-zero entries. This
// requires two indices for the two items we are comparing at any step.
// The second index always moves back by one, but the first index moves back
// by one only when it is pointing to something that has a non-zero value.
index1 = 0;
for ( index2 = 1; index2 < listLength; index2++ )
{
if ( allocatedTimeList[index1] == 0.0 )
{
if ( allocatedTimeList[index2] != 0.0 )
{
allocatedTimeList[index1] = allocatedTimeList[index2];
distanceList[index1] = distanceList[index2];
propList[index1] = propList[index2];
propList[index2] = NULL;
allocatedTimeList[index2] = 0.0;
distanceList[index2] = 0.0;
}
else
{
propList[index1] = propList[index2] = NULL;
allocatedTimeList[index1] = allocatedTimeList[index2] = 0.0;
distanceList[index1] = distanceList[index2] = 0.0;
}
}
if ( allocatedTimeList[index1] != 0.0 )
{
index1++;
}
}
// Compute the new list length - index1 is always pointing to the
// first 0.0 entry or the last entry if none were zero (in which case
// we won't change the list length)
listLength = (allocatedTimeList[index1] == 0.0)?(index1):listLength;
// Now reorder the list if sorting is on
// Do it by a simple bubble sort - there probably aren't that
// many props....
if ( this->SortingStyle == VTK_CULLER_SORT_FRONT_TO_BACK )
{
for ( propLoop = 1; propLoop < listLength; propLoop++ )
{
index1 = propLoop;
while ( (index1 - 1) >= 0 &&
distanceList[index1] < distanceList[index1-1] )
{
tmp = distanceList[index1-1];
distanceList[index1-1] = distanceList[index1];
distanceList[index1] = tmp;
prop = propList[index1-1];
propList[index1-1] = propList[index1];
propList[index1] = prop;
index1--;
}
}
}
if ( this->SortingStyle == VTK_CULLER_SORT_BACK_TO_FRONT )
{
for ( propLoop = 1; propLoop < listLength; propLoop++ )
{
index1 = propLoop;
while ( (index1 - 1) >= 0 &&
distanceList[index1] > distanceList[index1-1] )
{
tmp = distanceList[index1-1];
distanceList[index1-1] = distanceList[index1];
distanceList[index1] = tmp;
prop = propList[index1-1];
propList[index1-1] = propList[index1];
propList[index1] = prop;
index1--;
}
}
}
// The allocated render times are now initialized
initialized = 1;
delete [] allocatedTimeList;
delete [] distanceList;
return total_time;
}
// Description:
// Return the sorting style as a descriptive character string.
const char *vtkFrustumCoverageCuller::GetSortingStyleAsString(void)
{
if( this->SortingStyle == VTK_CULLER_SORT_NONE )
{
return "None";
}
if( this->SortingStyle == VTK_CULLER_SORT_FRONT_TO_BACK )
{
return "Front To Back";
}
if( this->SortingStyle == VTK_CULLER_SORT_BACK_TO_FRONT )
{
return "Back To Front";
}
else
{
return "Unknown";
}
}
void vtkFrustumCoverageCuller::PrintSelf(ostream& os, vtkIndent indent)
{
this->Superclass::PrintSelf(os,indent);
os << indent << "Minimum Coverage: "
<< this->MinimumCoverage << endl;
os << indent << "Maximum Coverage: "
<< this->MaximumCoverage << endl;
os << indent << "Sorting Style: "
<< this->GetSortingStyleAsString() << endl;
}