gfx/layers/BSPTree.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "BSPTree.h"
   8 #include "mozilla/gfx/Polygon.h"
   9
  10 namespace mozilla {
  11
  12 class nsDisplayTransform;
  13
  14 namespace layers {
  15
  16 template <typename T>
  17 void BSPTree<T>::BuildDrawOrder(BSPTreeNode<T>* aNode,
  18                                 nsTArray<BSPPolygon<T>>& aLayers) const {
  19   const gfx::Point4D& normal = aNode->First().GetNormal();
  20
  21   BSPTreeNode<T>* front = aNode->front;
  22   BSPTreeNode<T>* back = aNode->back;
  23
  24   // Since the goal is to return the draw order from back to front, we reverse
  25   // the traversal order if the current polygon is facing towards the camera.
  26   const bool reverseOrder = normal.z > 0.0f;
  27
  28   if (reverseOrder) {
  29     std::swap(front, back);
  30   }
  31
  32   if (front) {
  33     BuildDrawOrder(front, aLayers);
  34   }
  35
  36   for (BSPPolygon<T>& layer : aNode->layers) {
  37     MOZ_ASSERT(layer.geometry);
  38
  39     if (layer.geometry->GetPoints().Length() >= 3) {
  40       aLayers.AppendElement(std::move(layer));
  41     }
  42   }
  43
  44   if (back) {
  45     BuildDrawOrder(back, aLayers);
  46   }
  47 }
  48
  49 template <typename T>
  50 void BSPTree<T>::BuildTree(BSPTreeNode<T>* aRoot, PolygonList<T>& aLayers) {
  51   MOZ_ASSERT(!aLayers.empty());
  52
  53   aRoot->layers.push_back(std::move(aLayers.front()));
  54   aLayers.pop_front();
  55
  56   if (aLayers.empty()) {
  57     return;
  58   }
  59
  60   const gfx::Polygon& plane = aRoot->First();
  61   MOZ_ASSERT(!plane.IsEmpty());
  62
  63   const gfx::Point4D& planeNormal = plane.GetNormal();
  64   const gfx::Point4D& planePoint = plane.GetPoints()[0];
  65
  66   PolygonList<T> backLayers, frontLayers;
  67   for (BSPPolygon<T>& layerPolygon : aLayers) {
  68     const nsTArray<gfx::Point4D>& geometry = layerPolygon.geometry->GetPoints();
  69
  70     // Calculate the plane-point distances for the polygon classification.
  71     size_t pos = 0, neg = 0;
  72     nsTArray<float> distances = CalculatePointPlaneDistances(
  73         geometry, planeNormal, planePoint, pos, neg);
  74
  75     // Back polygon
  76     if (pos == 0 && neg > 0) {
  77       backLayers.push_back(std::move(layerPolygon));
  78     }
  79     // Front polygon
  80     else if (pos > 0 && neg == 0) {
  81       frontLayers.push_back(std::move(layerPolygon));
  82     }
  83     // Coplanar polygon
  84     else if (pos == 0 && neg == 0) {
  85       aRoot->layers.push_back(std::move(layerPolygon));
  86     }
  87     // Polygon intersects with the splitting plane.
  88     else if (pos > 0 && neg > 0) {
  89       nsTArray<gfx::Point4D> backPoints, frontPoints;
  90       // Clip the polygon against the plane. We reuse the previously calculated
  91       // distances to find the plane-edge intersections.
  92       ClipPointsWithPlane(geometry, planeNormal, distances, backPoints,
  93                           frontPoints);
  94
  95       const gfx::Point4D& normal = layerPolygon.geometry->GetNormal();
  96       T* data = layerPolygon.data;
  97
  98       if (backPoints.Length() >= 3) {
  99         backLayers.emplace_back(data, std::move(backPoints), normal);
 100       }
 101
 102       if (frontPoints.Length() >= 3) {
 103         frontLayers.emplace_back(data, std::move(frontPoints), normal);
 104       }
 105     }
 106   }
 107
 108   if (!backLayers.empty()) {
 109     aRoot->back = new (mPool) BSPTreeNode(mListPointers);
 110     BuildTree(aRoot->back, backLayers);
 111   }
 112
 113   if (!frontLayers.empty()) {
 114     aRoot->front = new (mPool) BSPTreeNode(mListPointers);
 115     BuildTree(aRoot->front, frontLayers);
 116   }
 117 }
 118
 119 template void BSPTree<BSPTestData>::BuildTree(
 120     BSPTreeNode<BSPTestData>* aRoot, PolygonList<BSPTestData>& aLayers);
 121 template void BSPTree<BSPTestData>::BuildDrawOrder(
 122     BSPTreeNode<BSPTestData>* aNode,
 123     nsTArray<BSPPolygon<BSPTestData>>& aLayers) const;
 124
 125 template void BSPTree<nsDisplayTransform>::BuildTree(
 126     BSPTreeNode<nsDisplayTransform>* aRoot,
 127     PolygonList<nsDisplayTransform>& aLayers);
 128 template void BSPTree<nsDisplayTransform>::BuildDrawOrder(
 129     BSPTreeNode<nsDisplayTransform>* aNode,
 130     nsTArray<BSPPolygon<nsDisplayTransform>>& aLayers) const;
 131
 132 }  // namespace layers
 133 }  // namespace mozilla