You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
365 lines
12 KiB
365 lines
12 KiB
/*=========================================================================
|
|
|
|
Program: Visualization Toolkit
|
|
Module: $RCSfile: vtkFrustumCoverageCuller.cxx,v $
|
|
|
|
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"
|
|
|
|
vtkCxxRevisionMacro(vtkFrustumCoverageCuller, "$Revision: 1.33 $");
|
|
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( (double)
|
|
( 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 minumum 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;
|
|
|
|
}
|
|
|