diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 19:33:14 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 19:33:14 +0000 |
commit | 36d22d82aa202bb199967e9512281e9a53db42c9 (patch) | |
tree | 105e8c98ddea1c1e4784a60a5a6410fa416be2de /gfx/layers/BSPTree.cpp | |
parent | Initial commit. (diff) | |
download | firefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.tar.xz firefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.zip |
Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'gfx/layers/BSPTree.cpp')
-rw-r--r-- | gfx/layers/BSPTree.cpp | 133 |
1 files changed, 133 insertions, 0 deletions
diff --git a/gfx/layers/BSPTree.cpp b/gfx/layers/BSPTree.cpp new file mode 100644 index 0000000000..bcec125e4b --- /dev/null +++ b/gfx/layers/BSPTree.cpp @@ -0,0 +1,133 @@ +/* -*- 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 { + +class nsDisplayTransform; + +namespace layers { + +template <typename T> +void BSPTree<T>::BuildDrawOrder(BSPTreeNode<T>* aNode, + nsTArray<BSPPolygon<T>>& aLayers) const { + const gfx::Point4D& normal = aNode->First().GetNormal(); + + BSPTreeNode<T>* front = aNode->front; + BSPTreeNode<T>* 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 (BSPPolygon<T>& layer : aNode->layers) { + MOZ_ASSERT(layer.geometry); + + if (layer.geometry->GetPoints().Length() >= 3) { + aLayers.AppendElement(std::move(layer)); + } + } + + if (back) { + BuildDrawOrder(back, aLayers); + } +} + +template <typename T> +void BSPTree<T>::BuildTree(BSPTreeNode<T>* aRoot, PolygonList<T>& 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]; + + PolygonList<T> backLayers, frontLayers; + for (BSPPolygon<T>& 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(); + T* data = layerPolygon.data; + + if (backPoints.Length() >= 3) { + backLayers.emplace_back(data, std::move(backPoints), normal); + } + + if (frontPoints.Length() >= 3) { + frontLayers.emplace_back(data, 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); + } +} + +template void BSPTree<BSPTestData>::BuildTree( + BSPTreeNode<BSPTestData>* aRoot, PolygonList<BSPTestData>& aLayers); +template void BSPTree<BSPTestData>::BuildDrawOrder( + BSPTreeNode<BSPTestData>* aNode, + nsTArray<BSPPolygon<BSPTestData>>& aLayers) const; + +template void BSPTree<nsDisplayTransform>::BuildTree( + BSPTreeNode<nsDisplayTransform>* aRoot, + PolygonList<nsDisplayTransform>& aLayers); +template void BSPTree<nsDisplayTransform>::BuildDrawOrder( + BSPTreeNode<nsDisplayTransform>* aNode, + nsTArray<BSPPolygon<nsDisplayTransform>>& aLayers) const; + +} // namespace layers +} // namespace mozilla |