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 namespace layers {
  12
  13 void BSPTree::BuildDrawOrder(BSPTreeNode* aNode,
  14                              nsTArray<LayerPolygon>& aLayers) const {
  15   const gfx::Point4D& normal = aNode->First().GetNormal();
  16
  17   BSPTreeNode* front = aNode->front;
  18   BSPTreeNode* back = aNode->back;
  19
  20   // Since the goal is to return the draw order from back to front, we reverse
  21   // the traversal order if the current polygon is facing towards the camera.
  22   const bool reverseOrder = normal.z > 0.0f;
  23
  24   if (reverseOrder) {
  25     std::swap(front, back);
  26   }
  27
  28   if (front) {
  29     BuildDrawOrder(front, aLayers);
  30   }
  31
  32   for (LayerPolygon& layer : aNode->layers) {
  33     MOZ_ASSERT(layer.geometry);
  34
  35     if (layer.geometry->GetPoints().Length() >= 3) {
  36       aLayers.AppendElement(std::move(layer));
  37     }
  38   }
  39
  40   if (back) {
  41     BuildDrawOrder(back, aLayers);
  42   }
  43 }
  44
  45 void BSPTree::BuildTree(BSPTreeNode* aRoot, std::list<LayerPolygon>& aLayers) {
  46   MOZ_ASSERT(!aLayers.empty());
  47
  48   aRoot->layers.push_back(std::move(aLayers.front()));
  49   aLayers.pop_front();
  50
  51   if (aLayers.empty()) {
  52     return;
  53   }
  54
  55   const gfx::Polygon& plane = aRoot->First();
  56   MOZ_ASSERT(!plane.IsEmpty());
  57
  58   const gfx::Point4D& planeNormal = plane.GetNormal();
  59   const gfx::Point4D& planePoint = plane.GetPoints()[0];
  60
  61   std::list<LayerPolygon> backLayers, frontLayers;
  62   for (LayerPolygon& layerPolygon : aLayers) {
  63     const nsTArray<gfx::Point4D>& geometry = layerPolygon.geometry->GetPoints();
  64
  65     // Calculate the plane-point distances for the polygon classification.
  66     size_t pos = 0, neg = 0;
  67     nsTArray<float> distances = CalculatePointPlaneDistances(
  68         geometry, planeNormal, planePoint, pos, neg);
  69
  70     // Back polygon
  71     if (pos == 0 && neg > 0) {
  72       backLayers.push_back(std::move(layerPolygon));
  73     }
  74     // Front polygon
  75     else if (pos > 0 && neg == 0) {
  76       frontLayers.push_back(std::move(layerPolygon));
  77     }
  78     // Coplanar polygon
  79     else if (pos == 0 && neg == 0) {
  80       aRoot->layers.push_back(std::move(layerPolygon));
  81     }
  82     // Polygon intersects with the splitting plane.
  83     else if (pos > 0 && neg > 0) {
  84       nsTArray<gfx::Point4D> backPoints, frontPoints;
  85       // Clip the polygon against the plane. We reuse the previously calculated
  86       // distances to find the plane-edge intersections.
  87       ClipPointsWithPlane(geometry, planeNormal, distances, backPoints,
  88                           frontPoints);
  89
  90       const gfx::Point4D& normal = layerPolygon.geometry->GetNormal();
  91       Layer* layer = layerPolygon.layer;
  92
  93       if (backPoints.Length() >= 3) {
  94         backLayers.emplace_back(layer, std::move(backPoints), normal);
  95       }
  96
  97       if (frontPoints.Length() >= 3) {
  98         frontLayers.emplace_back(layer, std::move(frontPoints), normal);
  99       }
 100     }
 101   }
 102
 103   if (!backLayers.empty()) {
 104     aRoot->back = new (mPool) BSPTreeNode(mListPointers);
 105     BuildTree(aRoot->back, backLayers);
 106   }
 107
 108   if (!frontLayers.empty()) {
 109     aRoot->front = new (mPool) BSPTreeNode(mListPointers);
 110     BuildTree(aRoot->front, frontLayers);
 111   }
 112 }
 113
 114 }  // namespace layers
 115 }  // namespace mozilla