/usr/include/thunderbird/mozilla/layers/BSPTree.h is in thunderbird-dev 1:52.8.0-1~deb8u1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* 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/. */
#ifndef MOZILLA_LAYERS_BSPTREE_H
#define MOZILLA_LAYERS_BSPTREE_H
#include "mozilla/gfx/Polygon.h"
#include "mozilla/Move.h"
#include "mozilla/UniquePtr.h"
#include "nsTArray.h"
#include <deque>
namespace mozilla {
namespace layers {
class Layer;
// Represents a layer that might have a non-rectangular geometry.
struct LayerPolygon {
explicit LayerPolygon(Layer *aLayer)
: layer(aLayer) {}
LayerPolygon(Layer *aLayer,
gfx::Polygon3D&& aGeometry)
: layer(aLayer), geometry(Some(aGeometry)) {}
LayerPolygon(Layer *aLayer,
nsTArray<gfx::Point3D>&& aPoints, const gfx::Point3D& aNormal)
: layer(aLayer), geometry(Some(gfx::Polygon3D(Move(aPoints), aNormal))) {}
Layer *layer;
Maybe<gfx::Polygon3D> geometry;
};
LayerPolygon PopFront(std::deque<LayerPolygon>& aLayers);
// Represents a node in a BSP tree. The node contains at least one layer with
// associated geometry that is used as a splitting plane, and at most two child
// nodes that represent the splitting planes that further subdivide the space.
struct BSPTreeNode {
explicit BSPTreeNode(LayerPolygon&& layer)
{
layers.push_back(Move(layer));
}
const gfx::Polygon3D& First() const
{
MOZ_ASSERT(layers[0].geometry);
return *layers[0].geometry;
}
UniquePtr<BSPTreeNode> front;
UniquePtr<BSPTreeNode> back;
std::deque<LayerPolygon> layers;
};
// BSPTree class takes a list of layers as an input and uses binary space
// partitioning algorithm to create a tree structure that can be used for
// depth sorting.
//
// Sources for more information:
// https://en.wikipedia.org/wiki/Binary_space_partitioning
// ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html
class BSPTree {
public:
// This constructor takes the ownership of layers in the given list.
explicit BSPTree(std::deque<LayerPolygon>& aLayers)
{
MOZ_ASSERT(!aLayers.empty());
mRoot.reset(new BSPTreeNode(PopFront(aLayers)));
BuildTree(mRoot, aLayers);
}
// Returns the root node of the BSP tree.
const UniquePtr<BSPTreeNode>& GetRoot() const
{
return mRoot;
}
// Builds and returns the back-to-front draw order for the created BSP tree.
nsTArray<LayerPolygon> GetDrawOrder() const
{
nsTArray<LayerPolygon> layers;
BuildDrawOrder(mRoot, layers);
return layers;
}
private:
UniquePtr<BSPTreeNode> mRoot;
// BuildDrawOrder and BuildTree are called recursively. The depth of the
// recursion depends on the amount of polygons and their intersections.
void BuildDrawOrder(const UniquePtr<BSPTreeNode>& aNode,
nsTArray<LayerPolygon>& aLayers) const;
void BuildTree(UniquePtr<BSPTreeNode>& aRoot,
std::deque<LayerPolygon>& aLayers);
};
} // namespace layers
} // namespace mozilla
#endif /* MOZILLA_LAYERS_BSPTREE_H */
|