tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

BSPTree.cpp (4127B)

      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