/*=========================================================================

  Program:   Visualization Toolkit
  Module:    vtkLabelPlacer.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.

=========================================================================*/
/*-------------------------------------------------------------------------
  Copyright 2008 Sandia Corporation.
  Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
  the U.S. Government retains certain rights in this software.
-------------------------------------------------------------------------*/

#include "vtkLabelPlacer.h"

#include "vtkCamera.h"
#include "vtkCellArray.h"
#include "vtkCoordinate.h"
#include "vtkDataArray.h"
#include "vtkDoubleArray.h"
#include "vtkIdTypeArray.h"
#include "vtkInformation.h"
#include "vtkInformationVector.h"
#include "vtkLabelHierarchy.h"
#include "vtkLabelHierarchyIterator.h"
#include "vtkMatrix4x4.h"
#include "vtkObjectFactory.h"
#include "vtkPointData.h"
#include "vtkPoints.h"
#include "vtkRenderWindow.h"
#include "vtkRenderer.h"
#include "vtkSelectVisiblePoints.h"
#include "vtkSmartPointer.h"
#include "vtkStringArray.h"
#include "vtkTimerLog.h"

#include <vector>

vtkStandardNewMacro(vtkLabelPlacer);
vtkCxxSetObjectMacro(vtkLabelPlacer, AnchorTransform, vtkCoordinate);

class vtkLabelPlacer::Internal
{
public:
  /// A single label's coordinates (adjusted so that the lower left screen coords are <0,0>).
  struct LabelRect
  {
    float x[4]; // xmin, xmax, ymin, ymax
  };
  /// A rectangular tile on the screen. It contains a set of labels that overlap it.
  struct ScreenTile
  {
    std::vector<LabelRect> Labels;
    ScreenTile() = default;
    /// Is there space to place the given rectangle in this tile so that it doesn't overlap any
    /// labels in this tile?
    bool IsSpotOpen(float& opacity, struct LabelRect& r)
    {
      float d0, d1, d2, d3;
      for (std::vector<LabelRect>::iterator it = this->Labels.begin(); it != this->Labels.end();
           ++it)
      {
        d0 = it->x[0] - r.x[1];
        d1 = r.x[0] - it->x[1];
        d2 = it->x[2] - r.x[3];
        d3 = r.x[2] - it->x[3];
        if (d0 < 0. && d1 < 0. && d2 < 0. && d3 < 0.)
          return false;
        d0 = d0 < 0. ? 2. : 0.1 * d0;
        d1 = d1 < 0. ? 2. : 0.1 * d1;
        d2 = d2 < 0. ? 2. : 0.1 * d2;
        d3 = d3 < 0. ? 2. : 0.1 * d3;
        d0 = d0 < d1 ? d0 : d1;
        d2 = d2 < d3 ? d2 : d3;
        if (d0 < 1. && d2 < 1.)
        {
          if (d0 < opacity)
            opacity = d0;
          if (d2 < opacity)
            opacity = d2;
        }
      }
      return true;
    }
    /// Prepare for the next frame.
    void Reset() { this->Labels.clear(); }
    void Insert(const LabelRect& rect) { this->Labels.push_back(rect); }
  };
  std::vector<std::vector<ScreenTile>> Tiles;
  float ScreenOrigin[2];
  float TileSize[2];
  int NumTiles[2];
  vtkSmartPointer<vtkIdTypeArray> NewLabelsPlaced;
  vtkSmartPointer<vtkIdTypeArray> LastLabelsPlaced;
  static int DumpPlaced;

  Internal(float viewport[4], float tilesize[2])
  {
    this->NewLabelsPlaced = vtkSmartPointer<vtkIdTypeArray>::New();
    this->LastLabelsPlaced = vtkSmartPointer<vtkIdTypeArray>::New();
    this->ScreenOrigin[0] = viewport[0];
    this->ScreenOrigin[1] = viewport[2];
    this->TileSize[0] = tilesize[0];
    this->TileSize[1] = tilesize[1];
    this->NumTiles[0] = static_cast<int>(ceil((viewport[1] - viewport[0]) / tilesize[0]));
    this->NumTiles[1] = static_cast<int>(ceil((viewport[3] - viewport[2]) / tilesize[1]));
    this->Tiles.resize(this->NumTiles[0]);
    for (int i = 0; i < this->NumTiles[0]; ++i)
      this->Tiles[i].resize(this->NumTiles[1]);
  }

  bool PlaceLabel(float& opacity, float x0, float x1, float x2, float x3)
  {
    // Translate to origin to simplify bucketing
    LabelRect r;
    r.x[0] = x0 - ScreenOrigin[0];
    r.x[1] = x1 - ScreenOrigin[0];
    r.x[2] = x2 - ScreenOrigin[1];
    r.x[3] = x3 - ScreenOrigin[1];
    // Determine intersected tiles
    float rx0 = x0 / TileSize[0];
    float rx1 = x1 / TileSize[0];
    float ry0 = x2 / TileSize[1];
    float ry1 = x3 / TileSize[1];
    int tx0 = static_cast<int>(floor(rx0));
    int tx1 = static_cast<int>(ceil(rx1));
    int ty0 = static_cast<int>(floor(ry0));
    int ty1 = static_cast<int>(ceil(ry1));
    if (tx0 > NumTiles[0] || tx1 < 0 || ty0 > NumTiles[1] || ty1 < 0)
      return false; // Don't intersect screen.
    if (tx0 < 0)
    {
      tx0 = 0;
      rx0 = 0.;
    }
    if (ty0 < 0)
    {
      ty0 = 0;
      ry0 = 0.;
    }
    if (tx1 >= this->NumTiles[0])
    {
      tx1 = this->NumTiles[0] - 1;
      rx1 = tx1;
    }
    if (ty1 >= this->NumTiles[1])
    {
      ty1 = this->NumTiles[1] - 1;
      ry1 = ty1;
    }
    // Check all applicable tiles for overlap.
    for (int tx = tx0; tx <= tx1; ++tx)
    {
      for (int ty = ty0; ty <= ty1; ++ty)
      {
        std::vector<ScreenTile>* trow = &this->Tiles[tx];
        // Do this check here for speed, even though we repeat w/ small mod below.
        if (!(*trow)[ty].IsSpotOpen(opacity, r))
          return false;
      }
    }
    // OK, we made it this far... we can place the label.
    // Add it to each tile it overlaps.
    for (int tx = tx0; tx <= tx1; ++tx)
    {
      for (int ty = ty0; ty <= ty1; ++ty)
      {
        this->Tiles[tx][ty].Insert(r);
      }
    }
    return true;
  }

  void Reset(float viewport[4], float tileSize[2])
  {
    // Clear out any tiles we get to reuse
    for (int tx = 0; tx < this->NumTiles[0]; ++tx)
      for (int ty = 0; ty < this->NumTiles[1]; ++ty)
        this->Tiles[tx][ty].Reset();

    // Set new parameter values in case the viewport changed
    this->ScreenOrigin[0] = viewport[0];
    this->ScreenOrigin[1] = viewport[2];
    this->TileSize[0] = tileSize[0];
    this->TileSize[1] = tileSize[1];
    this->NumTiles[0] = static_cast<int>(ceil((viewport[1] - viewport[0]) / tileSize[0]));
    this->NumTiles[1] = static_cast<int>(ceil((viewport[3] - viewport[2]) / tileSize[1]));

    // Allocate new tiles (where required...)
    this->Tiles.resize(this->NumTiles[0]);
    for (int i = 0; i < this->NumTiles[0]; ++i)
      this->Tiles[i].resize(this->NumTiles[1]);

    // Save labels from the last frame for use later...
    vtkSmartPointer<vtkIdTypeArray> tmp = this->LastLabelsPlaced;
    this->LastLabelsPlaced = this->NewLabelsPlaced;
    this->NewLabelsPlaced = tmp;
    this->NewLabelsPlaced->Reset();
  }
};

int vtkLabelPlacer::Internal::DumpPlaced = 0;

vtkLabelPlacer::vtkLabelPlacer()
{
  this->Renderer = nullptr;
  this->Gravity = CenterCenter;
  this->AnchorTransform = vtkCoordinate::New();
  this->AnchorTransform->SetCoordinateSystemToWorld();
  this->MaximumLabelFraction = 0.05; // Take up no more than 5% of screen real estate with labels.
  this->Buckets = nullptr;
  this->PositionsAsNormals = false;
  // this->IteratorType = vtkLabelHierarchy::DEPTH_FIRST;
  // this->IteratorType = vtkLabelHierarchy::FULL_SORT;
  this->IteratorType = vtkLabelHierarchy::QUEUE;
  this->VisiblePoints = vtkSelectVisiblePoints::New();
  this->VisiblePoints->SetTolerance(0.002);

  this->LastRendererSize[0] = 0;
  this->LastRendererSize[1] = 0;
  this->LastCameraPosition[0] = 0.0;
  this->LastCameraPosition[1] = 0.0;
  this->LastCameraPosition[2] = 0.0;
  this->LastCameraFocalPoint[0] = 0.0;
  this->LastCameraFocalPoint[1] = 0.0;
  this->LastCameraFocalPoint[2] = 0.0;
  this->LastCameraViewUp[0] = 0.0;
  this->LastCameraViewUp[1] = 0.0;
  this->LastCameraViewUp[2] = 0.0;
  this->LastCameraParallelScale = 0.0;

  this->OutputCoordinateSystem = vtkLabelPlacer::WORLD;

  this->OutputTraversedBounds = false;
  this->GeneratePerturbedLabelSpokes = false;
  this->UseDepthBuffer = false;

  this->SetNumberOfOutputPorts(4);
  // this->DebugOn();
}

vtkLabelPlacer::~vtkLabelPlacer()
{
  this->AnchorTransform->Delete();
  delete this->Buckets;
  this->VisiblePoints->Delete();
}

void vtkLabelPlacer::SetRenderer(vtkRenderer* ren)
{
  // Do not keep a reference count to avoid a reference loop
  if (this->Renderer != ren)
  {
    this->Renderer = ren;
    this->VisiblePoints->SetRenderer(ren);
    this->Modified();
  }
}

void vtkLabelPlacer::PrintSelf(ostream& os, vtkIndent indent)
{
  this->Superclass::PrintSelf(os, indent);
  os << indent << "Renderer: " << this->Renderer << "\n";
  os << indent << "AnchorTransform: " << this->AnchorTransform << "\n";
  os << indent << "Gravity: " << this->Gravity << "\n";
  os << indent << "MaximumLabelFraction: " << this->MaximumLabelFraction << "\n";
  os << indent << "PositionsAsNormals: " << (this->PositionsAsNormals ? "ON" : "OFF") << "\n";
  os << indent << "IteratorType: " << this->IteratorType << "\n";
  os << indent << "OutputTraversedBounds: " << (this->OutputTraversedBounds ? "ON" : "OFF") << "\n";
  os << indent
     << "GeneratePerturbedLabelSpokes: " << (this->GeneratePerturbedLabelSpokes ? "ON" : "OFF")
     << "\n";
  os << indent << "UseDepthBuffer: " << (this->UseDepthBuffer ? "ON" : "OFF") << "\n";
  os << indent << "OutputCoordinateSystem: " << this->OutputCoordinateSystem << "\n";
}

/**\brief Set the default label gravity.
 *
 * This method does not allow invalid gravities to be specified.
 * The default value (CenterCenter) is both vertically and horizontally centered.
 * Baseline vertical gravity is not yet supported properly since no text is associated with labels
 * yet.
 */
void vtkLabelPlacer::SetGravity(int gravity)
{
  if (gravity == this->Gravity)
    return;

  if (!(gravity & HorizontalBitMask))
  {
    vtkWarningMacro("Ignoring gravity " << gravity << " with no horizontal bit set");
    return;
  }

  if (!(gravity & VerticalBitMask))
  {
    vtkWarningMacro("Ignoring gravity " << gravity << " with no vertical bit set");
    return;
  }

  this->Gravity = gravity;
  this->Modified();
}

vtkMTimeType vtkLabelPlacer::GetMTime()
{
  // Check for minimal changes
  if (this->Renderer)
  {
    const int* sz = this->Renderer->GetSize();
    if (this->LastRendererSize[0] != sz[0] || this->LastRendererSize[1] != sz[1])
    {
      this->LastRendererSize[0] = sz[0];
      this->LastRendererSize[1] = sz[1];
      this->Modified();
    }
    vtkCamera* cam = this->Renderer->GetActiveCamera();
    if (cam)
    {
      double* pos = cam->GetPosition();
      if (this->LastCameraPosition[0] != pos[0] || this->LastCameraPosition[1] != pos[1] ||
        this->LastCameraPosition[2] != pos[2])
      {
        this->LastCameraPosition[0] = pos[0];
        this->LastCameraPosition[1] = pos[1];
        this->LastCameraPosition[2] = pos[2];
        this->Modified();
      }
      double* fp = cam->GetFocalPoint();
      if (this->LastCameraFocalPoint[0] != fp[0] || this->LastCameraFocalPoint[1] != fp[1] ||
        this->LastCameraFocalPoint[2] != fp[2])
      {
        this->LastCameraFocalPoint[0] = fp[0];
        this->LastCameraFocalPoint[1] = fp[1];
        this->LastCameraFocalPoint[2] = fp[2];
        this->Modified();
      }
      double* up = cam->GetViewUp();
      if (this->LastCameraViewUp[0] != up[0] || this->LastCameraViewUp[1] != up[1] ||
        this->LastCameraViewUp[2] != up[2])
      {
        this->LastCameraViewUp[0] = up[0];
        this->LastCameraViewUp[1] = up[1];
        this->LastCameraViewUp[2] = up[2];
        this->Modified();
      }
      double scale = cam->GetParallelScale();
      if (this->LastCameraParallelScale != scale)
      {
        this->LastCameraParallelScale = scale;
        this->Modified();
      }
    }
  }
  return Superclass::GetMTime();
}

int vtkLabelPlacer::FillInputPortInformation(int vtkNotUsed(port), vtkInformation* info)
{
  info->Set(vtkAlgorithm::INPUT_REQUIRED_DATA_TYPE(), "vtkLabelHierarchy");
  return 1;
}

int vtkLabelPlacer::RequestData(vtkInformation* vtkNotUsed(request),
  vtkInformationVector** inputVector, vtkInformationVector* outputVector)
{
  if (!this->Renderer)
  {
    vtkErrorMacro("No renderer -- can't determine screen space size.");
    return 0;
  }

  if (!this->Renderer->GetRenderWindow())
  {
    vtkErrorMacro("No render window -- can't get window size to query z buffer.");
    return 0;
  }

  // This will trigger if you do something like ResetCamera before the Renderer or
  // RenderWindow have allocated their appropriate system resources (like creating
  // an OpenGL context)." Resource allocation must occur before we can use the Z
  // buffer.
  if (this->Renderer->GetRenderWindow()->GetNeverRendered())
  {
    vtkDebugMacro("RenderWindow not initialized -- aborting update.");
    return 1;
  }

  vtkCamera* cam = this->Renderer->GetActiveCamera();
  if (!cam)
  {
    return 1;
  }

  vtkInformation* inInfo = inputVector[0]->GetInformationObject(0);
  vtkInformation* outInfo0 = outputVector->GetInformationObject(0);
  vtkInformation* outInfo1 = outputVector->GetInformationObject(1);
  vtkInformation* outInfo2 = outputVector->GetInformationObject(2);
  vtkInformation* outInfo3 = outputVector->GetInformationObject(3);

  vtkLabelHierarchy* inData =
    vtkLabelHierarchy::SafeDownCast(inInfo->Get(vtkDataObject::DATA_OBJECT()));
  vtkPolyData* ouData0 = vtkPolyData::SafeDownCast(outInfo0->Get(vtkDataObject::DATA_OBJECT()));
  vtkPolyData* ouData1 = vtkPolyData::SafeDownCast(outInfo1->Get(vtkDataObject::DATA_OBJECT()));
  vtkPolyData* ouData2 = vtkPolyData::SafeDownCast(outInfo2->Get(vtkDataObject::DATA_OBJECT()));
  vtkPolyData* ouData3 = vtkPolyData::SafeDownCast(outInfo3->Get(vtkDataObject::DATA_OBJECT()));

  vtkStringArray* nameArr0 = vtkStringArray::New();
  nameArr0->SetName("LabelText");
  ouData0->GetPointData()->AddArray(nameArr0);
  nameArr0->Delete();

  vtkDoubleArray* opArr0 = vtkDoubleArray::New();
  opArr0->SetName("Opacity");
  ouData0->GetPointData()->AddArray(opArr0);
  opArr0->Delete();

  vtkIntArray* iconIndexArr1 = vtkIntArray::New();
  iconIndexArr1->SetName("IconIndex");
  ouData1->GetPointData()->AddArray(iconIndexArr1);
  iconIndexArr1->Delete();

  vtkIntArray* idArr0 = vtkIntArray::New();
  idArr0->SetName("ID");
  ouData0->GetPointData()->AddArray(idArr0);
  idArr0->Delete();

  vtkStringArray* nameArr = vtkArrayDownCast<vtkStringArray>(inData->GetLabels());
  vtkIntArray* iconIndexArr = vtkArrayDownCast<vtkIntArray>(inData->GetIconIndices());

  if (!inData)
  {
    // vtkErrorMacro( "No input data" );
    return 1;
  }

  vtkPoints* ipts = inData->GetPoints();
  if (!ipts)
  {
    return 1;
  }
  vtkDataArray* isz = inData->GetPointData()->GetArray("LabelSize");
  if (!isz) //|| isz->GetNumberOfComponents() > 2 )
  {
    vtkWarningMacro("Missing or improper label size point array -- output will be empty.");
    return 1;
  }

  // If the renderer size is zero, silently place no labels.
  const int* renSize = this->Renderer->GetSize();
  if (renSize[0] == 0 || renSize[1] == 0)
  {
    return 1;
  }

  if (!ouData0 || !ouData1)
  {
    vtkErrorMacro("No output data.");
    return 0;
  }

  // Prepare both icon and text output datasets
  vtkPoints* opts0 = ouData0->GetPoints();
  if (!opts0)
  {
    opts0 = vtkPoints::New();
    ouData0->SetPoints(opts0);
    opts0->FastDelete();
  }
  ouData0->AllocateExact(1024, 1024);

  vtkPoints* opts1 = ouData1->GetPoints();
  if (!opts1)
  {
    opts1 = vtkPoints::New();
    ouData1->SetPoints(opts1);
    opts1->FastDelete();
  }
  ouData1->AllocateExact(1024, 1024);

  vtkPoints* opts2 = ouData2->GetPoints();
  if (!opts2)
  {
    opts2 = vtkPoints::New();
    ouData2->SetPoints(opts2);
    opts2->FastDelete();
  }
  ouData2->AllocateExact(1024, 1024);

  vtkPoints* opts3 = ouData3->GetPoints();
  vtkCellArray* ocells3 = ouData3->GetLines();
  if (!opts3)
  {
    opts3 = vtkPoints::New();
    ouData3->SetPoints(opts3);
    opts3->FastDelete();
  }
  if (!ocells3)
  {
    ocells3 = vtkCellArray::New();
    ouData3->SetLines(ocells3);
    ocells3->FastDelete();
  }
  ouData3->AllocateExact(1024, 1024);

  int tvpsz[4]; // tiled viewport size (and origin)
  // kd-tree bounds on screenspace (as floats... eventually we
  // should use a median kd-tree -- not naive version)
  float kdbounds[4];
  this->Renderer->GetTiledSizeAndOrigin(tvpsz, tvpsz + 1, tvpsz + 2, tvpsz + 3);
  kdbounds[0] = tvpsz[2];
  kdbounds[1] = tvpsz[0] + tvpsz[2];
  kdbounds[2] = tvpsz[3];
  kdbounds[3] = tvpsz[1] + tvpsz[3];
  float tileSize[2] = { 128., 128. }; // fixed for now
  if (!this->Buckets || this->Buckets->NumTiles[0] * this->Buckets->TileSize[0] < tvpsz[2] ||
    this->Buckets->NumTiles[1] * this->Buckets->TileSize[1] < tvpsz[3])
  {
    this->Buckets = new Internal(kdbounds, tileSize);
  }
  else
  {
    this->Buckets->Reset(kdbounds, tileSize);
  }

  float* zPtr = nullptr;
  int placed = 0;
  int occluded = 0;

  double ll[3], lr[3], ul[3], ur[3];
  ll[2] = lr[2] = ul[2] = ur[2] = 0.;
  double x[3];
  double sz[4];
  int* dispx;

  // Compute frustum for excluding labels that are outside the visible region.
  double frustumPlanes[24];
  vtkLabelHierarchy::GetAnchorFrustumPlanes(frustumPlanes, this->Renderer, this->AnchorTransform);

  unsigned long allowableLabelArea = static_cast<unsigned long>(
    ((kdbounds[1] - kdbounds[0]) * (kdbounds[3] - kdbounds[2])) * this->MaximumLabelFraction);
  (void)allowableLabelArea;
  unsigned long renderedLabelArea = 0;
  double camVec[3];
  if (this->PositionsAsNormals)
  {
    cam->GetViewPlaneNormal(camVec);
  }

  vtkLabelHierarchyIterator* inIter = inData->NewIterator(
    this->IteratorType, this->Renderer, cam, frustumPlanes, this->PositionsAsNormals, tileSize);

  if (this->OutputTraversedBounds)
  {
    inIter->SetTraversedBounds(ouData2);
  }
  vtkSmartPointer<vtkTimerLog> timer = vtkSmartPointer<vtkTimerLog>::New();
  timer->StartTimer();

  inIter->Begin(this->Buckets->LastLabelsPlaced);
  this->Buckets->NewLabelsPlaced->Initialize();

  if (this->UseDepthBuffer)
  {
    zPtr = this->VisiblePoints->Initialize(true);
  }

  timer->StopTimer();
  vtkDebugMacro("Iterator initialization time: " << timer->GetElapsedTime());
  timer->StartTimer();
  for (; !inIter->IsAtEnd(); inIter->Next())
  {
    // Ignore labels that don't have text or an icon.
    vtkIdType labelType = inIter->GetType();
    int gravity = this->Gravity;
    if (labelType == 0)
    {
      gravity = HorizontalLeftBit | VerticalBaselineBit;
    }
    if (labelType < 0 || labelType > 1)
    {
      vtkDebugMacro("Arf. Bad label type " << labelType);
      continue;
    }

    inIter->GetPoint(x);

    if (this->AnchorTransform->GetCoordinateSystem() == VTK_WORLD)
    {
      // Cull points behind the camera. Cannot rely on hither-yon planes because the camera
      // position gets changed during vtkInteractorStyle::Dolly() and RequestData() called from
      // within ResetCameraClippingRange() before the frustum planes are updated.
      // Cull points outside hither-yon planes (other planes get tested below)
      double* eye = cam->GetPosition();
      double* dir = cam->GetViewPlaneNormal();
      if ((x[0] - eye[0]) * dir[0] + (x[1] - eye[1]) * dir[1] + (x[2] - eye[2]) * dir[2] > 0)
      {
        continue;
      }

      // Ignore labels pointing the wrong direction (HACK)
      if (this->PositionsAsNormals)
      {
        if (camVec[0] * x[0] + camVec[1] * x[1] + camVec[2] * x[2] < 0.)
        {
          continue;
        }
      }

      // Test for occlusion using the z-buffer
      if (this->UseDepthBuffer && !this->VisiblePoints->IsPointOccluded(x, zPtr))
      {
        occluded++;
        continue;
      }
    }

    this->AnchorTransform->SetValue(x);
    dispx = this->AnchorTransform->GetComputedDisplayValue(this->Renderer);
    inIter->GetSize(sz);
    if (sz[0] < 0)
      sz[0] = -sz[0];
    if (sz[1] < 0)
      sz[1] = -sz[1];
    // !!!! Commented out a few lines here as sz[2] && sz[3] never are initialized
    // Move anchor so no "space" characters are included in the layout.
    // dispx[0] -= static_cast<int>( sz[2] );
    // By default, the anchor will be at the text baseline. Adjust if user has selected otherwise.
    // if ( ( gravity & VerticalBitMask ) != VerticalBaselineBit )
    // dispx[1] -= static_cast<int>( sz[3] );
    // Without this check things get *really* slow (at least with naive bucket placement tests)
    // FIXME: Don't count area clipped off by viewport when culling above is fixed.
    double t1, t2;
    switch (gravity & HorizontalBitMask)
    {
      case HorizontalLeftBit:
        t1 = dispx[0] < kdbounds[0] ? kdbounds[0] : dispx[0];
        t2 = dispx[0] + sz[0];
        if (t2 > kdbounds[1])
          t2 = kdbounds[1];
        ll[0] = ul[0] = t1;
        lr[0] = ur[0] = t2;
        break;
      case HorizontalRightBit:
        t1 = dispx[0] - sz[0];
        if (t1 < kdbounds[0])
          t1 = kdbounds[0];
        t2 = dispx[0] > kdbounds[1] ? kdbounds[1] : dispx[0];
        ll[0] = ul[0] = t1;
        lr[0] = ur[0] = t2;
        break;
      default:
      case HorizontalCenterBit:
        t1 = dispx[0] - sz[0] / 2;
        if (t1 < kdbounds[0])
          t1 = kdbounds[0];
        t2 = dispx[0] + sz[0] / 2;
        if (t2 > kdbounds[1])
          t2 = kdbounds[1];
        ll[0] = ul[0] = t1;
        lr[0] = ur[0] = t2;
        break;
    }
    if (ll[0] > kdbounds[1] || lr[0] < kdbounds[0])
    {
      continue; // cull label not in frame
    }

    switch (gravity & VerticalBitMask)
    {
      case VerticalBottomBit:
      case VerticalBaselineBit:
        t1 = dispx[1] < kdbounds[2] ? kdbounds[2] : dispx[1];
        t2 = dispx[1] + sz[1];
        if (t2 > kdbounds[3])
          t2 = kdbounds[3];
        ll[1] = lr[1] = t1;
        ul[1] = ur[1] = t2;
        break;
      case VerticalTopBit:
        t1 = dispx[1] - sz[1];
        if (t1 < kdbounds[2])
          t1 = kdbounds[2];
        t2 = dispx[1] > kdbounds[3] ? kdbounds[3] : dispx[1];
        ll[1] = lr[1] = t1;
        ul[1] = ur[1] = t2;
        break;
      default:
      case VerticalCenterBit:
        t1 = dispx[1] - sz[1] / 2;
        if (t1 < kdbounds[2])
          t1 = kdbounds[2];
        t2 = dispx[1] + sz[1] / 2;
        if (t2 > kdbounds[3])
          t2 = kdbounds[3];
        ll[1] = lr[1] = t1;
        ul[1] = ur[1] = t2;
        break;
    }
    if (ll[1] > kdbounds[3] || lr[1] < kdbounds[2])
    {
      continue; // cull label not in frame
    }

    if (this->Debug)
    {
      vtkDebugMacro("Try: " << inIter->GetLabelId() << " (" << ll[0] << ", " << ll[1] << "  "
                            << ur[0] << "," << ur[1] << ")");
      if (labelType == 0)
      {
        vtkDebugMacro("Area: " << renderedLabelArea << "  /  " << allowableLabelArea << " \""
                               << nameArr->GetValue(inIter->GetLabelId()).c_str() << "\"");
      }
      else
      {
        vtkDebugMacro("Area: " << renderedLabelArea << "  /  " << allowableLabelArea);
      }
    }

    float opacity = 1.;
    if (this->Buckets->PlaceLabel(opacity, ll[0], ur[0], ll[1], ur[1]))
    {
      renderedLabelArea += static_cast<unsigned long>(sz[0] * sz[1]);
      vtkIdType conn[4];
      OutputCoordinates coordSys = static_cast<OutputCoordinates>(this->OutputCoordinateSystem);
      if (labelType == 0)
      { // label is text
        if (vtkLabelPlacer::Internal::DumpPlaced)
        {
          vtkDebugMacro(<< ll[0] << " -- " << ur[0] << ", " << ll[1] << " -- " << ur[1] << ": "
                        << nameArr->GetValue(inIter->GetLabelId()).c_str());
        }
        switch (coordSys)
        {
          default:
          case WORLD:
            conn[0] = opts0->InsertNextPoint(x);
            break;
          case DISPLAY:
            conn[0] = opts0->InsertNextPoint(dispx[0], dispx[1], 0.);
            break;
        }
        // Store the anchor point in world coordinates
        ouData0->InsertNextCell(VTK_VERTEX, 1, conn);
        nameArr0->InsertNextValue(nameArr->GetValue(inIter->GetLabelId()));
        opArr0->InsertNextValue(opacity);
        idArr0->InsertNextValue(0);
      }
      else
      { // label is an icon
        if (vtkLabelPlacer::Internal::DumpPlaced)
        {
          vtkDebugMacro(<< ll[0] << " -- " << ur[0] << ", " << ll[1] << " -- " << ur[1] << ": Icon "
                        << iconIndexArr->GetValue(inIter->GetLabelId()));
        }
        switch (coordSys)
        {
          default:
          case WORLD:
            conn[0] = opts1->InsertNextPoint(x);
            break;
          case DISPLAY:
            conn[0] = opts1->InsertNextPoint(dispx[0], dispx[1], 0.);
            break;
        }
        vtkIdType cid = ouData1->InsertNextCell(VTK_VERTEX, 1, conn);
        (void)cid;
        vtkDebugMacro("     Point: " << conn[0] << " (" << x[0] << "," << x[1] << "," << x[2]
                                     << ") Vertex: " << cid);
        iconIndexArr1->InsertNextValue(iconIndexArr->GetValue(inIter->GetLabelId()));
      }

      // Handle Spokes for perturbed points
      if (this->GeneratePerturbedLabelSpokes)
      {
        // inData->CenterPts
        // inData->
      }

      // Uncomment to actually store the previous labels.
      // Currently starting with a clean slate each time.
      this->Buckets->NewLabelsPlaced->InsertNextValue(inIter->GetLabelId());
      vtkDebugMacro("Placed: " << inIter->GetLabelId() << " (" << ll[0] << ", " << ll[1] << "  "
                               << ur[0] << "," << ur[1] << ") " << labelType);
      placed++;
    }
  }
  vtkDebugMacro("------");
  // cout << "Not Placed: " << notPlaced << endl;
  // cout << "Labels Occluded: " << occluded << endl;

  inIter->Delete();
  delete[] zPtr;

  timer->StopTimer();
  vtkDebugMacro("Iteration time: " << timer->GetElapsedTime());

  return 1;
}