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
BuildDrawOrder(BSPTreeNode * aNode,nsTArray<LayerPolygon> & aLayers) const13 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
BuildTree(BSPTreeNode * aRoot,std::list<LayerPolygon> & aLayers)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
116