DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Header

Mercurial (d09edbe2abfe)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* 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 {

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

  BSPTreeNode* front = aNode->front;
  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(std::move(layer));
    }
  }

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

void BSPTree::BuildTree(BSPTreeNode* aRoot, std::list<LayerPolygon>& aLayers) {
  MOZ_ASSERT(!aLayers.empty());

  aRoot->layers.push_back(std::move(aLayers.front()));
  aLayers.pop_front();

  if (aLayers.empty()) {
    return;
  }

  const gfx::Polygon& plane = aRoot->First();
  MOZ_ASSERT(!plane.IsEmpty());

  const gfx::Point4D& planeNormal = plane.GetNormal();
  const gfx::Point4D& planePoint = plane.GetPoints()[0];

  std::list<LayerPolygon> backLayers, frontLayers;
  for (LayerPolygon& layerPolygon : aLayers) {
    const nsTArray<gfx::Point4D>& geometry = layerPolygon.geometry->GetPoints();

    // Calculate the plane-point distances for the polygon classification.
    size_t pos = 0, neg = 0;
    nsTArray<float> distances = CalculatePointPlaneDistances(
        geometry, planeNormal, planePoint, pos, neg);

    // Back polygon
    if (pos == 0 && neg > 0) {
      backLayers.push_back(std::move(layerPolygon));
    }
    // Front polygon
    else if (pos > 0 && neg == 0) {
      frontLayers.push_back(std::move(layerPolygon));
    }
    // Coplanar polygon
    else if (pos == 0 && neg == 0) {
      aRoot->layers.push_back(std::move(layerPolygon));
    }
    // Polygon intersects with the splitting plane.
    else if (pos > 0 && neg > 0) {
      nsTArray<gfx::Point4D> backPoints, frontPoints;
      // Clip the polygon against the plane. We reuse the previously calculated
      // distances to find the plane-edge intersections.
      ClipPointsWithPlane(geometry, planeNormal, distances, backPoints,
                          frontPoints);

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

      if (backPoints.Length() >= 3) {
        backLayers.emplace_back(layer, std::move(backPoints), normal);
      }

      if (frontPoints.Length() >= 3) {
        frontLayers.emplace_back(layer, std::move(frontPoints), normal);
      }
    }
  }

  if (!backLayers.empty()) {
    aRoot->back = new (mPool) BSPTreeNode(mListPointers);
    BuildTree(aRoot->back, backLayers);
  }

  if (!frontLayers.empty()) {
    aRoot->front = new (mPool) BSPTreeNode(mListPointers);
    BuildTree(aRoot->front, frontLayers);
  }
}

}  // namespace layers
}  // namespace mozilla