/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "BSPTree.h"
#include "mozilla/gfx/Polygon.h"

namespace mozilla {
namespace layers {

LayerPolygon PopFront(std::deque<LayerPolygon>& aLayers)
{
  LayerPolygon layer = Move(aLayers.front());
  aLayers.pop_front();
  return layer;
}

void
BSPTree::BuildDrawOrder(const UniquePtr<BSPTreeNode>& aNode,
                        nsTArray<LayerPolygon>& aLayers) const
{
  const gfx::Point3D& normal = aNode->First().GetNormal();

  UniquePtr<BSPTreeNode> *front = &aNode->front;
  UniquePtr<BSPTreeNode> *back = &aNode->back;

  // Since the goal is to return the draw order from back to front, we reverse
  // the traversal order if the current polygon is facing towards the camera.
  const bool reverseOrder = normal.z > 0.0f;

  if (reverseOrder) {
    std::swap(front, back);
  }

  if (*front) {
    BuildDrawOrder(*front, aLayers);
  }

  for (LayerPolygon& layer : aNode->layers) {
    MOZ_ASSERT(layer.geometry);

    if (layer.geometry->GetPoints().Length() >= 3) {
      aLayers.AppendElement(Move(layer));
    }
  }

  if (*back) {
    BuildDrawOrder(*back, aLayers);
  }
}

void
BSPTree::BuildTree(UniquePtr<BSPTreeNode>& aRoot,
                   std::deque<LayerPolygon>& aLayers)
{
  if (aLayers.empty()) {
    return;
  }

  const gfx::Polygon3D& plane = aRoot->First();
  std::deque<LayerPolygon> backLayers, frontLayers;

  for (LayerPolygon& layerPolygon : aLayers) {
    const Maybe<gfx::Polygon3D>& geometry = layerPolygon.geometry;

    size_t pos = 0, neg = 0;
    nsTArray<float> dots = geometry->CalculateDotProducts(plane, pos, neg);

    // Back polygon
    if (pos == 0 && neg > 0) {
      backLayers.push_back(Move(layerPolygon));
    }
    // Front polygon
    else if (pos > 0 && neg == 0) {
      frontLayers.push_back(Move(layerPolygon));
    }
    // Coplanar polygon
    else if (pos == 0 && neg == 0) {
      aRoot->layers.push_back(Move(layerPolygon));
    }
    // Polygon intersects with the splitting plane.
    else if (pos > 0 && neg > 0) {
      nsTArray<gfx::Point3D> backPoints, frontPoints;
      geometry->SplitPolygon(plane, dots, backPoints, frontPoints);

      const gfx::Point3D& normal = geometry->GetNormal();
      Layer *layer = layerPolygon.layer;

      backLayers.push_back(LayerPolygon(layer, Move(backPoints), normal));
      frontLayers.push_back(LayerPolygon(layer, Move(frontPoints), normal));
    }
  }

  if (!backLayers.empty()) {
    aRoot->back.reset(new BSPTreeNode(PopFront(backLayers)));
    BuildTree(aRoot->back, backLayers);
  }

  if (!frontLayers.empty()) {
    aRoot->front.reset(new BSPTreeNode(PopFront(frontLayers)));
    BuildTree(aRoot->front, frontLayers);
  }
}

} // namespace layers
} // namespace mozilla