Line data    Source code

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