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

  Program:   Visualization Toolkit
  Module:    vtkLabelPlacementMapper.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 "vtkLabelPlacementMapper.h"

#include "vtkActor2D.h"
#include "vtkCamera.h"
#include "vtkCellArray.h"
#include "vtkExecutive.h"
#include "vtkFreeTypeLabelRenderStrategy.h"
#include "vtkIdTypeArray.h"
#include "vtkInformation.h"
#include "vtkLabelHierarchy.h"
#include "vtkLabelHierarchyCompositeIterator.h"
#include "vtkLabelRenderStrategy.h"
#include "vtkLabeledDataMapper.h"
#include "vtkMath.h"
#include "vtkObjectFactory.h"
#include "vtkPoints.h"
#include "vtkPolyDataMapper.h"
#include "vtkPolyDataMapper2D.h"
#include "vtkProperty2D.h"
#include "vtkRenderWindow.h"
#include "vtkRenderer.h"
#include "vtkSelectVisiblePoints.h"
#include "vtkSmartPointer.h"
#include "vtkTextProperty.h"
#include "vtkTimerLog.h"
#include "vtkTransformCoordinateSystems.h"

// From: http://www.flipcode.com/archives/2D_OBB_Intersection.shtml
class LabelRect
{
public:
  // Rotation origin.
  double RotationOrigin[2];

  // Rotation amount (radians).
  double Rotation;

  // Rotated label bounds (xmin, xmax, ymin, ymax).
  double Bounds[4];

  // Corners of the rotated box, where 0 is the lower left.
  // Corner 0 is lower-left, 1 is lower-right, 2 is upper-right, 3 is upper-left.
  double Corner[4][2];

  // Two edges of the box extended away from corner[0].
  double Axis[2][2];

  // origin[a] = corner[0].dot(axis[a]);
  double Origin[2];

  LabelRect(double center[2], const double w, const double h, double rotation)
  {
    double X[2];
    double Y[2];
    X[0] = cos(rotation) * w / 2;
    X[1] = sin(rotation) * w / 2;
    Y[0] = -sin(rotation) * h / 2;
    Y[1] = cos(rotation) * h / 2;

    Corner[0][0] = center[0] - X[0] - Y[0];
    Corner[0][1] = center[1] - X[1] - Y[1];
    Corner[1][0] = center[0] + X[0] - Y[0];
    Corner[1][1] = center[1] + X[1] - Y[1];
    Corner[2][0] = center[0] + X[0] + Y[0];
    Corner[2][1] = center[1] + X[1] + Y[1];
    Corner[3][0] = center[0] - X[0] + Y[0];
    Corner[3][1] = center[1] - X[1] + Y[1];

    RotationOrigin[0] = center[0];
    RotationOrigin[1] = center[1];

    Rotation = rotation;

    ComputeAxes();
  }

  LabelRect(double x[4], double rotateOrigin[2], double rotation)
  {
    Rotation = rotation;
    RotationOrigin[0] = rotateOrigin[0];
    RotationOrigin[1] = rotateOrigin[1];

    Corner[0][0] = x[0];
    Corner[0][1] = x[2];
    Corner[1][0] = x[1];
    Corner[1][1] = x[2];
    Corner[2][0] = x[1];
    Corner[2][1] = x[3];
    Corner[3][0] = x[0];
    Corner[3][1] = x[3];

    double ca = cos(rotation);
    double sa = sin(rotation);
    for (int i = 0; i < 4; ++i)
    {
      Corner[i][0] -= RotationOrigin[0];
      Corner[i][1] -= RotationOrigin[1];
      double rotx = Corner[i][0] * ca - Corner[i][1] * sa;
      double roty = Corner[i][1] * ca + Corner[i][0] * sa;
      Corner[i][0] = rotx;
      Corner[i][1] = roty;
      Corner[i][0] += RotationOrigin[0];
      Corner[i][1] += RotationOrigin[1];
    }

    ComputeAxes();
  }

  // Returns true if the intersection of the boxes is non-empty.
  bool Overlaps(const LabelRect& other) const
  {
    // Take care of easy case first
    if (Rotation == 0.0 && other.Rotation == 0.0)
    {
      double d0 = Corner[0][0] - other.Corner[2][0];
      double d1 = other.Corner[0][0] - Corner[2][0];
      double d2 = Corner[0][1] - other.Corner[2][1];
      double d3 = other.Corner[0][1] - Corner[2][1];
      return d0 < 0. && d1 < 0. && d2 < 0. && d3 < 0.;
    }
    else
    {
      return Overlaps1Way(other) && other.Overlaps1Way(*this);
    }
  }

  void Render(
    vtkRenderer* ren, int shape, int style, double margin, double color[3], double opacity) const
  {
    if (shape == vtkLabelPlacementMapper::NONE)
    {
      return;
    }

    vtkSmartPointer<vtkCellArray> cells = vtkSmartPointer<vtkCellArray>::New();
    vtkSmartPointer<vtkPoints> pts = vtkSmartPointer<vtkPoints>::New();
    vtkSmartPointer<vtkPolyDataMapper2D> mapper = vtkSmartPointer<vtkPolyDataMapper2D>::New();
    vtkSmartPointer<vtkPolyData> poly = vtkSmartPointer<vtkPolyData>::New();
    vtkSmartPointer<vtkActor2D> actor = vtkSmartPointer<vtkActor2D>::New();

    double dx[2];
    double dy[2];
    double ax0len = sqrt(Axis[0][0] * Axis[0][0] + Axis[0][1] * Axis[0][1]);
    dx[0] = margin * Axis[0][0] / ax0len;
    dx[1] = margin * Axis[0][1] / ax0len;
    double ax1len = sqrt(Axis[1][0] * Axis[1][0] + Axis[1][1] * Axis[1][1]);
    dy[0] = margin * Axis[1][0] / ax1len;
    dy[1] = margin * Axis[1][1] / ax1len;
    switch (shape)
    {
      case vtkLabelPlacementMapper::ROUNDED_RECT:
      {
        double roundedFactor = vtkMath::Pi() / 4;
        double rx[2];
        double ry[2];
        rx[0] = roundedFactor * dx[0];
        rx[1] = roundedFactor * dx[1];
        ry[0] = roundedFactor * dy[0];
        ry[1] = roundedFactor * dy[1];
        pts->InsertNextPoint(Corner[0][0] - dx[0], Corner[0][1] - dx[1], 0);
        pts->InsertNextPoint(Corner[0][0] - rx[0] - ry[0], Corner[0][1] - rx[1] - ry[1], 0);
        pts->InsertNextPoint(Corner[0][0] - dy[0], Corner[0][1] - dy[1], 0);
        pts->InsertNextPoint(Corner[1][0] - dy[0], Corner[1][1] - dy[1], 0);
        pts->InsertNextPoint(Corner[1][0] + rx[0] - ry[0], Corner[1][1] + rx[1] - ry[1], 0);
        pts->InsertNextPoint(Corner[1][0] + dx[0], Corner[1][1] + dx[1], 0);
        pts->InsertNextPoint(Corner[2][0] + dx[0], Corner[2][1] + dx[1], 0);
        pts->InsertNextPoint(Corner[2][0] + rx[0] + ry[0], Corner[2][1] + rx[1] + ry[1], 0);
        pts->InsertNextPoint(Corner[2][0] + dy[0], Corner[2][1] + dy[1], 0);
        pts->InsertNextPoint(Corner[3][0] + dy[0], Corner[3][1] + dy[1], 0);
        pts->InsertNextPoint(Corner[3][0] - rx[0] + ry[0], Corner[3][1] - rx[1] + ry[1], 0);
        pts->InsertNextPoint(Corner[3][0] - dx[0], Corner[3][1] - dx[1], 0);
        cells->InsertNextCell(13);
        for (int i = 0; i < 13; ++i)
        {
          cells->InsertCellPoint(i % 12);
        }
        break;
      }
      case vtkLabelPlacementMapper::RECT:
      default:
      {
        pts->InsertNextPoint(Corner[0][0] - dx[0] - dy[0], Corner[0][1] - dx[1] - dy[1], 0);
        pts->InsertNextPoint(Corner[1][0] + dx[0] - dy[0], Corner[1][1] + dx[1] - dy[1], 0);
        pts->InsertNextPoint(Corner[2][0] + dx[0] + dy[0], Corner[2][1] + dx[1] + dy[1], 0);
        pts->InsertNextPoint(Corner[3][0] - dx[0] + dy[0], Corner[3][1] - dx[1] + dy[1], 0);
        cells->InsertNextCell(5);
        for (int c = 0; c < 5; ++c)
        {
          cells->InsertCellPoint(c % 4);
        }
        break;
      }
    }
    poly->SetPoints(pts);
    if (style == vtkLabelPlacementMapper::OUTLINE)
    {
      poly->SetLines(cells);
    }
    else
    {
      poly->SetPolys(cells);
    }
    mapper->SetInputData(poly);
    actor->SetMapper(mapper);
    actor->GetProperty()->SetColor(color);
    actor->GetProperty()->SetOpacity(opacity);
    actor->RenderOverlay(ren);
  }

private:
  // Returns true if other overlaps one dimension of this.
  bool Overlaps1Way(const LabelRect& other) const
  {
    for (int a = 0; a < 2; ++a)
    {
      // double t = other.corner[0].dot(axis[a]);
      double t = other.Corner[0][0] * Axis[a][0] + other.Corner[0][1] * Axis[a][1];

      // Find the extent of box 2 on axis a
      double tMin = t;
      double tMax = t;

      for (int c = 1; c < 4; ++c)
      {
        // t = other.corner[c].dot(axis[a]);
        t = other.Corner[c][0] * Axis[a][0] + other.Corner[c][1] * Axis[a][1];

        if (t < tMin)
        {
          tMin = t;
        }
        else if (t > tMax)
        {
          tMax = t;
        }
      }

      // We have to subtract off the origin

      // See if [tMin, tMax] intersects [0, 1]
      if ((tMin > 1 + Origin[a]) || (tMax < Origin[a]))
      {
        // There was no intersection along this dimension;
        // the boxes cannot possibly overlap.
        return false;
      }
    }

    // There was no dimension along which there is no intersection.
    // Therefore the boxes overlap.
    return true;
  }

  // Updates the axes after the corners move.  Assumes the
  // corners actually form a rectangle.
  void ComputeAxes()
  {
    Axis[0][0] = Corner[1][0] - Corner[0][0];
    Axis[0][1] = Corner[1][1] - Corner[0][1];
    Axis[1][0] = Corner[3][0] - Corner[0][0];
    Axis[1][1] = Corner[3][1] - Corner[0][1];

    // Make the length of each axis 1/edge length so we know any
    // dot product must be less than 1 to fall within the edge.

    for (int a = 0; a < 2; ++a)
    {
      double len = Axis[a][0] * Axis[a][0] + Axis[a][1] * Axis[a][1];
      Axis[a][0] /= len;
      Axis[a][1] /= len;
      Origin[a] = Corner[0][0] * Axis[a][0] + Corner[0][1] * Axis[a][1];
    }

    Bounds[0] = Corner[0][0];
    Bounds[1] = Corner[0][0];
    Bounds[2] = Corner[0][1];
    Bounds[3] = Corner[0][1];
    for (int i = 1; i < 4; ++i)
    {
      if (Corner[i][0] < Bounds[0])
      {
        Bounds[0] = Corner[i][0];
      }
      if (Corner[i][0] > Bounds[1])
      {
        Bounds[1] = Corner[i][0];
      }
      if (Corner[i][1] < Bounds[2])
      {
        Bounds[2] = Corner[i][1];
      }
      if (Corner[i][1] > Bounds[3])
      {
        Bounds[3] = Corner[i][1];
      }
    }
  }
};

class vtkLabelPlacementMapper::Internal
{
public:
  /// 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(const LabelRect& r)
    {
      for (std::vector<LabelRect>::iterator it = this->Labels.begin(); it != this->Labels.end();
           ++it)
      {
        if (r.Overlaps(*it))
        {
          return false;
        }
      }
      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;

  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(const LabelRect& r)
  {
    // Determine intersected tiles
    float rx0 = r.Bounds[0] / TileSize[0];
    float rx1 = r.Bounds[1] / TileSize[0];
    float ry0 = r.Bounds[2] / TileSize[1];
    float ry1 = r.Bounds[3] / 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(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();
  }
};

vtkStandardNewMacro(vtkLabelPlacementMapper);
vtkCxxSetObjectMacro(vtkLabelPlacementMapper, AnchorTransform, vtkCoordinate);
vtkCxxSetObjectMacro(vtkLabelPlacementMapper, RenderStrategy, vtkLabelRenderStrategy);

//------------------------------------------------------------------------------
vtkLabelPlacementMapper::vtkLabelPlacementMapper()
{
  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::QUEUE;
  this->VisiblePoints = vtkSelectVisiblePoints::New();
  this->VisiblePoints->SetTolerance(0.002);
  this->PlaceAllLabels = false;
  this->OutputTraversedBounds = false;
  this->GeneratePerturbedLabelSpokes = false;
  this->Style = FILLED;
  this->Shape = NONE;
  this->Margin = 5;
  this->BackgroundColor[0] = 0.5;
  this->BackgroundColor[1] = 0.5;
  this->BackgroundColor[2] = 0.5;
  this->BackgroundOpacity = 1.0;

  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->UseDepthBuffer = false;

  this->RenderStrategy = nullptr;
  vtkSmartPointer<vtkFreeTypeLabelRenderStrategy> s =
    vtkSmartPointer<vtkFreeTypeLabelRenderStrategy>::New();
  this->SetRenderStrategy(s);
}

//------------------------------------------------------------------------------
vtkLabelPlacementMapper::~vtkLabelPlacementMapper()
{
  this->AnchorTransform->Delete();
  delete this->Buckets;
  this->VisiblePoints->Delete();
  if (this->RenderStrategy)
  {
    this->RenderStrategy->Delete();
  }
}

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

//------------------------------------------------------------------------------
void vtkLabelPlacementMapper::RenderOverlay(vtkViewport* viewport, vtkActor2D* vtkNotUsed(actor))
{
  vtkSmartPointer<vtkTimerLog> log = vtkSmartPointer<vtkTimerLog>::New();
  log->StartTimer();

  vtkRenderer* ren = vtkRenderer::SafeDownCast(viewport);
  if (!ren)
  {
    vtkErrorMacro("No renderer -- can't determine screen space size.");
    return;
  }

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

  // 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 (ren->GetRenderWindow()->GetNeverRendered())
  {
    vtkDebugMacro("RenderWindow not initialized -- aborting update.");
    return;
  }

  vtkCamera* cam = ren->GetActiveCamera();
  if (!cam)
  {
    return;
  }

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

  // Update the pipeline if necessary
  this->Update();

  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];
  ren->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[2];
  double ur[2];
  double x[3];
  double sz[4];
  int origin[2];
  int dispx[2];

  // Compute frustum for excluding labels that are outside the visible region.
  double frustumPlanes[24];
  vtkLabelHierarchy::GetAnchorFrustumPlanes(frustumPlanes, ren, 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);
  }

  // Make a composite iterator that will iterate over all the input
  // label hierarchies in a round-robin sequence.
  vtkSmartPointer<vtkLabelHierarchyCompositeIterator> inIter =
    vtkSmartPointer<vtkLabelHierarchyCompositeIterator>::New();

  vtkSmartPointer<vtkPolyData> boundsPoly = vtkSmartPointer<vtkPolyData>::New();
  if (this->OutputTraversedBounds)
  {
    vtkSmartPointer<vtkPoints> pts = vtkSmartPointer<vtkPoints>::New();
    boundsPoly->SetPoints(pts);
    vtkSmartPointer<vtkCellArray> lines = vtkSmartPointer<vtkCellArray>::New();
    boundsPoly->SetLines(lines);
    inIter->SetTraversedBounds(boundsPoly);
  }

  int numInputs = this->GetNumberOfInputConnections(0);
  for (int i = 0; i < numInputs; ++i)
  {
    vtkLabelHierarchy* inData = vtkLabelHierarchy::SafeDownCast(this->GetInputDataObject(0, i));
    vtkLabelHierarchyIterator* it = inData->NewIterator(
      this->IteratorType, ren, cam, frustumPlanes, this->PositionsAsNormals, tileSize);
    inIter->AddIterator(it);
    it->Delete();
  }

  vtkSmartPointer<vtkTimerLog> timer = vtkSmartPointer<vtkTimerLog>::New();
  timer->StartTimer();

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

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

  // Start rendering labels
  this->RenderStrategy->SetRenderer(ren);
  this->RenderStrategy->StartFrame();

  timer->StopTimer();
  vtkDebugMacro("Iterator initialization time: " << timer->GetElapsedTime());
  timer->StartTimer();

  vtkSmartPointer<vtkTextProperty> tpropCopy = vtkSmartPointer<vtkTextProperty>::New();

  for (; !inIter->IsAtEnd(); inIter->Next())
  {
    // Ignore labels that don't have text or an icon.
    vtkIdType labelType = inIter->GetType();
    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);
    int* originPtr = this->AnchorTransform->GetComputedDisplayValue(ren);
    origin[0] = originPtr[0];
    origin[1] = originPtr[1];

    // Determine the label bounds
    vtkTextProperty* tprop = inIter->GetHierarchy()->GetTextProperty();
    tpropCopy->ShallowCopy(tprop);

    if (this->RenderStrategy->SupportsRotation() && inIter->GetHierarchy()->GetOrientations())
    {
      tpropCopy->SetOrientation(inIter->GetOrientation());
    }

    double bds[4];
    this->RenderStrategy->ComputeLabelBounds(tpropCopy, inIter->GetLabel(), bds);

    // Offset display position by lower left corner of bounding box
    dispx[0] = static_cast<int>(origin[0] + bds[0]);
    dispx[1] = static_cast<int>(origin[1] + bds[2]);

    sz[0] = bds[1] - bds[0];
    sz[1] = bds[3] - bds[2];

    if (sz[0] < 0)
      sz[0] = -sz[0];
    if (sz[1] < 0)
      sz[1] = -sz[1];

    // If it has no size, skip it
    if (sz[0] == 0.0 || sz[1] == 0.0)
    {
      continue;
    }

    ll[0] = dispx[0];
    ll[1] = dispx[1];
    ur[0] = dispx[0] + sz[0];
    ur[1] = dispx[1] + sz[1];

    if (ll[1] > kdbounds[3] || ur[1] < kdbounds[2] || ll[0] > kdbounds[1] || ur[0] < kdbounds[0])
    {
      continue; // cull label not in frame
    }

    // Special case: if there are bounded sizes, try to render every one we encounter.
    if (this->RenderStrategy->SupportsBoundedSize() && inIter->GetHierarchy()->GetBoundedSizes())
    {
      double p[3] = { static_cast<double>(origin[0]), static_cast<double>(origin[1]), 0.0 };
      double boundedSize[2];
      inIter->GetBoundedSize(boundedSize);

      // Figure out if width is too small to fit
      double xWidth[3] = { x[0] + boundedSize[0], x[1], x[2] };
      this->AnchorTransform->SetValue(xWidth);
      int* origin2 = this->AnchorTransform->GetComputedDisplayValue(ren);
      double pWidth[3] = { static_cast<double>(origin2[0]), static_cast<double>(origin2[1]), 0.0 };
      int width = static_cast<int>(sqrt(vtkMath::Distance2BetweenPoints(p, pWidth)));
      if (width < 20)
      {
        continue;
      }

      // Figure out if height is too small to fit
      double xHeight[3] = { x[0], x[1] + boundedSize[1], x[2] };
      this->AnchorTransform->SetValue(xHeight);
      origin2 = this->AnchorTransform->GetComputedDisplayValue(ren);
      double pHeight[3] = { static_cast<double>(origin2[0]), static_cast<double>(origin2[1]), 0.0 };
      int height = static_cast<int>(sqrt(vtkMath::Distance2BetweenPoints(p, pHeight)));
      if (height < bds[3] - bds[2])
      {
        continue;
      }

      // Label is not text
      if (labelType != 0)
      {
        continue;
      }

      // Render it
      this->RenderStrategy->RenderLabel(origin, tpropCopy, inIter->GetLabel(), width);

      int renderedHeight = static_cast<int>(bds[3] - bds[2]);
      int renderedWidth = static_cast<int>((bds[1] - bds[0] < width) ? (bds[1] - bds[0]) : width);
      renderedLabelArea += static_cast<unsigned long>(renderedWidth * renderedHeight);
      continue;
    }

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

    double orient = tpropCopy->GetOrientation();

    // Translate to origin to simplify bucketing
    double xTrans[4];
    xTrans[0] = ll[0] - kdbounds[0];
    xTrans[1] = ur[0] - kdbounds[0];
    xTrans[2] = ll[1] - kdbounds[2];
    xTrans[3] = ur[1] - kdbounds[2];

    double originTrans[2];
    originTrans[0] = origin[0] - kdbounds[0];
    originTrans[1] = origin[1] - kdbounds[2];

    double orientRad = vtkMath::RadiansFromDegrees(orient);
    LabelRect r(xTrans, originTrans, orientRad);

    if (this->PlaceAllLabels || this->Buckets->PlaceLabel(r))
    {
      r.Render(ren, this->Shape, this->Style, this->Margin, this->BackgroundColor,
        this->BackgroundOpacity);
      renderedLabelArea += static_cast<unsigned long>(sz[0] * sz[1]);
      if (labelType == 0)
      {
        // label is text
        this->RenderStrategy->RenderLabel(origin, tpropCopy, inIter->GetLabel());

        // TODO: 1. Perturb coincident points.
        //       2. Use GeneratePerturbedLabelSpokes to possibly render perturbed points.
      }
      else
      { // label is an icon
        // TODO: Do something ...
      }

      vtkDebugMacro("Placed: " << inIter->GetLabelId() << " (" << ll[0] << ", " << ll[1] << "  "
                               << ur[0] << "," << ur[1] << ") " << labelType);
      placed++;
    }
  }

  // Done rendering labels
  this->RenderStrategy->EndFrame();
  this->RenderStrategy->SetRenderer(nullptr);

  if (this->OutputTraversedBounds)
  {
    // For some reason I cannot use vtkPolyDataMapper, I need to use
    // vtkPolyDataMapper2D. This causes lines behind the camera to be sometimes
    // transformed on-screen. Since this is for debugging, I'm going to punt
    // on this one.
    vtkSmartPointer<vtkTransformCoordinateSystems> trans =
      vtkSmartPointer<vtkTransformCoordinateSystems>::New();
    vtkSmartPointer<vtkPolyDataMapper2D> boundsMapper = vtkSmartPointer<vtkPolyDataMapper2D>::New();
    vtkSmartPointer<vtkActor2D> boundsActor = vtkSmartPointer<vtkActor2D>::New();
    trans->SetInputCoordinateSystemToWorld();
    trans->SetOutputCoordinateSystemToDisplay();
    trans->SetInputData(boundsPoly);
    trans->SetViewport(ren);
    boundsMapper->SetInputConnection(trans->GetOutputPort());
    boundsMapper->RenderOverlay(ren, boundsActor);
  }

  vtkDebugMacro("------");
  vtkDebugMacro("Placed: " << placed);
  vtkDebugMacro("Labels Occluded: " << occluded);

  delete[] zPtr;

  timer->StopTimer();
  vtkDebugMacro("Iteration time: " << timer->GetElapsedTime());
  log->StopTimer();
  // cerr << log->GetElapsedTime() << endl;
}

//------------------------------------------------------------------------------
void vtkLabelPlacementMapper::ReleaseGraphicsResources(vtkWindow* win)
{
  this->RenderStrategy->ReleaseGraphicsResources(win);
}

//------------------------------------------------------------------------------
void vtkLabelPlacementMapper::PrintSelf(ostream& os, vtkIndent indent)
{
  this->Superclass::PrintSelf(os, indent);
  os << indent << "AnchorTransform: " << this->AnchorTransform << "\n";
  os << indent << "MaximumLabelFraction: " << this->MaximumLabelFraction << "\n";
  os << indent << "PositionsAsNormals: " << (this->PositionsAsNormals ? "ON" : "OFF") << "\n";
  os << indent << "IteratorType: " << this->IteratorType << "\n";
  os << indent << "RenderStrategy: " << this->RenderStrategy << "\n";
  os << indent << "PlaceAllLabels: " << (this->PlaceAllLabels ? "ON" : "OFF") << "\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 << "Style: " << this->Style << "\n";
  os << indent << "Shape: " << this->Shape << "\n";
  os << indent << "Margin: " << this->Margin << "\n";
  os << indent << "BackgroundColor: " << this->BackgroundColor[0] << ", "
     << this->BackgroundColor[1] << ", " << this->BackgroundColor[2] << endl;
  os << indent << "BackgroundOpacity: " << this->BackgroundOpacity << "\n";
}