vtkStreamingPriorityQueue.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (c) Kitware Inc.
// SPDX-License-Identifier: BSD-3-Clause
#ifndef vtkStreamingPriorityQueue_h
#define vtkStreamingPriorityQueue_h
#ifndef VTK_WRAPPING_CXX

#include "vtkBoundingBox.h"   // for vtkBoundingBox
#include "vtkMath.h"          // for vtkMath
#include "vtkWrappingHints.h" // for wrapping attributes

#include <queue> // for std::priority_queue

//*****************************************************************************
namespace
{
// this code is stolen from vtkFrustumCoverageCuller.
inline double vtkComputeScreenCoverage(const double planes[24], const double bounds[6],
  double& distance, double& centeredness, double& itemCoverage)
{
  distance = 0.0;
  centeredness = 0.0;
  itemCoverage = 0.0;

  // a duff dataset like a polydata with no cells will have bad bounds
  if (!vtkMath::AreBoundsInitialized(const_cast<double*>(bounds)))
  {
    return 0.0;
  }
  double screen_bounds[4];

  double center[3];
  center[0] = (bounds[0] + bounds[1]) / 2.0;
  center[1] = (bounds[2] + bounds[3]) / 2.0;
  center[2] = (bounds[4] + bounds[5]) / 2.0;
  double 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 (int i = 0; i < 6; i++)
  {
    // Compute how far the center of the sphere is from this plane
    double 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)
    {
      return 0.0;
    }

    // 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)
    {
      distance = d;
    }
  }

  // If the prop wasn't culled during the plane tests...
  // Compute the width and height of this slice through the
  // view frustum that contains the center of the sphere
  double full_w = screen_bounds[0] + screen_bounds[1] + 2.0 * radius;
  double full_h = screen_bounds[2] + screen_bounds[3] + 2.0 * radius;

  // Multiply the distances from each side to get a measure of how centered
  // the sphere is on the screen (divide by half the length in that dimension
  // squared to get a measure of how centered the object is in that dimension).
  double measure_w =
    (screen_bounds[0] + radius) * (screen_bounds[1] + radius) / (full_w * full_w / 4.0);
  double measure_h =
    (screen_bounds[2] + radius) * (screen_bounds[3] + radius) / (full_h * full_h / 4.0);

  // If the object is off the edge of the screen, treat it as if it is just
  // inside the edge (which we know it is since it wasn't culled)
  measure_w = std::max(measure_w, 0.01);
  measure_h = std::max(measure_h, 0.01);
  centeredness = measure_w * measure_h;

  double w = 2 * radius;
  double h = 2 * radius;
  if (screen_bounds[0] < 0.0)
  {
    w += screen_bounds[0];
  }
  if (screen_bounds[1] < 0.0)
  {
    w += screen_bounds[1];
  }
  if (screen_bounds[2] < 0.0)
  {
    h += screen_bounds[2];
  }
  if (screen_bounds[3] < 0.0)
  {
    h += screen_bounds[3];
  }
  itemCoverage = h * w / (4 * radius * 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.
  double 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).
  double 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];
  }

  // Compute the fraction of coverage
  if ((full_w * full_h) != 0.0)
  {
    return (part_w * part_h) / (full_w * full_h);
  }

  return 0;
}
}

class VTK_WRAPEXCLUDE vtkStreamingPriorityQueueItem
{
public:
  unsigned int Identifier; // this is used to identify this block when making a
                           // request.
  double Refinement;       // Where lower the Refinement cheaper is the
                           // processing for this block. 0 is considered as
                           // undefined.
  double ScreenCoverage;   // computed coverage for the block.
  double Centeredness; // how centered the object is on the screen (1 is centered, 0.0001 is near
                       // the edge)
  double Priority;     // Computed priority for this block.
  double Distance;
  double AmountOfDetail;
  double ItemCoverage;   // amount of the item that is onscreen (fraction, if whole item is onscreen
                         // it is 1)
  vtkBoundingBox Bounds; // Bounds for the block.

  vtkStreamingPriorityQueueItem()
    : Identifier(0)
    , Refinement(0)
    , ScreenCoverage(0)
    , Priority(0)
    , Distance(0)
    , AmountOfDetail(-1)
  {
  }
};

class VTK_WRAPEXCLUDE vtkStreamingPriorityQueueItemComparator
{
public:
  bool operator()(
    const vtkStreamingPriorityQueueItem& me, const vtkStreamingPriorityQueueItem& other) const
  {
    return me.Priority < other.Priority;
  }
};

template <typename Comparator = vtkStreamingPriorityQueueItemComparator>
class VTK_WRAPEXCLUDE vtkStreamingPriorityQueue
  : public std::priority_queue<vtkStreamingPriorityQueueItem,
      std::vector<vtkStreamingPriorityQueueItem>, Comparator>
{
public:

  void UpdatePriorities(const double view_planes[24], const double clamp_bounds[6])
  {
    bool clamp_bounds_initialized =
      (vtkMath::AreBoundsInitialized(const_cast<double*>(clamp_bounds)) != 0);
    vtkBoundingBox clampBox(const_cast<double*>(clamp_bounds));

    vtkStreamingPriorityQueue current_queue;
    std::swap(current_queue, *this);

    for (; !current_queue.empty(); current_queue.pop())
    {
      vtkStreamingPriorityQueueItem item = current_queue.top();
      if (!item.Bounds.IsValid())
      {
        continue;
      }

      double block_bounds[6];
      item.Bounds.GetBounds(block_bounds);

      if (clamp_bounds_initialized)
      {
        if (!clampBox.ContainsPoint(block_bounds[0], block_bounds[2], block_bounds[4]) &&
          !clampBox.ContainsPoint(block_bounds[1], block_bounds[3], block_bounds[5]))
        {
          // if the block_bounds is totally outside the clamp_bounds, skip it.
          continue;
        }
      }

      double refinement2 = item.Refinement * item.Refinement;
      double distance, centeredness, itemCoverage;
      double coverage =
        vtkComputeScreenCoverage(view_planes, block_bounds, distance, centeredness, itemCoverage);
      item.ScreenCoverage = coverage;
      item.Distance = distance;
      item.Centeredness = centeredness;
      item.ItemCoverage = itemCoverage;

      if (coverage > 0)
      {
        //        item.Priority =  coverage / (item.Refinement/* * distance*/) ;// / distance;
        //        //coverage * coverage / ( 1 + refinement2 + distance);
        item.Priority = coverage * coverage * centeredness / (1 + refinement2 + distance);
      }
      else
      {
        item.Priority = 0;
      }
      this->push(item);
    }
  }
};
#endif
#endif
// VTK-HeaderTest-Exclude: vtkStreamingPriorityQueue.h