Source code

Revision control

Other Tools

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
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
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