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