1 // Copyright 2014 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #ifndef COMPONENTS_VIZ_SERVICE_DISPLAY_BSP_TREE_H_
6 #define COMPONENTS_VIZ_SERVICE_DISPLAY_BSP_TREE_H_
7 
8 #include <stddef.h>
9 
10 #include <memory>
11 #include <vector>
12 
13 #include "base/containers/circular_deque.h"
14 #include "components/viz/service/display/bsp_compare_result.h"
15 #include "components/viz/service/display/draw_polygon.h"
16 #include "components/viz/service/viz_service_export.h"
17 
18 namespace viz {
19 
20 struct BspNode {
21   // This represents the splitting plane.
22   std::unique_ptr<DrawPolygon> node_data;
23   // This represents any coplanar geometry we found while building the BSP.
24   std::vector<std::unique_ptr<DrawPolygon>> coplanars_front;
25   std::vector<std::unique_ptr<DrawPolygon>> coplanars_back;
26 
27   std::unique_ptr<BspNode> back_child;
28   std::unique_ptr<BspNode> front_child;
29 
30   explicit BspNode(std::unique_ptr<DrawPolygon> data);
31   ~BspNode();
32 };
33 
34 class VIZ_SERVICE_EXPORT BspTree {
35  public:
36   explicit BspTree(base::circular_deque<std::unique_ptr<DrawPolygon>>* list);
root()37   std::unique_ptr<BspNode>& root() { return root_; }
38 
39   template <typename ActionHandlerType>
TraverseWithActionHandler(ActionHandlerType * action_handler)40   void TraverseWithActionHandler(ActionHandlerType* action_handler) const {
41     if (root_) {
42       WalkInOrderRecursion<ActionHandlerType>(action_handler, root_.get());
43     }
44   }
45 
46   ~BspTree();
47 
48  private:
49   std::unique_ptr<BspNode> root_;
50 
51   void FromList(std::vector<std::unique_ptr<DrawPolygon>>* list);
52   void BuildTree(BspNode* node,
53                  base::circular_deque<std::unique_ptr<DrawPolygon>>* data);
54 
55   template <typename ActionHandlerType>
WalkInOrderAction(ActionHandlerType * action_handler,DrawPolygon * item)56   void WalkInOrderAction(ActionHandlerType* action_handler,
57                          DrawPolygon* item) const {
58     (*action_handler)(item);
59   }
60 
61   template <typename ActionHandlerType>
WalkInOrderVisitNodes(ActionHandlerType * action_handler,const BspNode * node,const BspNode * first_child,const BspNode * second_child,const std::vector<std::unique_ptr<DrawPolygon>> & first_coplanars,const std::vector<std::unique_ptr<DrawPolygon>> & second_coplanars)62   void WalkInOrderVisitNodes(
63       ActionHandlerType* action_handler,
64       const BspNode* node,
65       const BspNode* first_child,
66       const BspNode* second_child,
67       const std::vector<std::unique_ptr<DrawPolygon>>& first_coplanars,
68       const std::vector<std::unique_ptr<DrawPolygon>>& second_coplanars) const {
69     if (first_child) {
70       WalkInOrderRecursion(action_handler, first_child);
71     }
72     for (size_t i = 0; i < first_coplanars.size(); i++) {
73       WalkInOrderAction(action_handler, first_coplanars[i].get());
74     }
75     WalkInOrderAction(action_handler, node->node_data.get());
76     for (size_t i = 0; i < second_coplanars.size(); i++) {
77       WalkInOrderAction(action_handler, second_coplanars[i].get());
78     }
79     if (second_child) {
80       WalkInOrderRecursion(action_handler, second_child);
81     }
82   }
83 
84   template <typename ActionHandlerType>
WalkInOrderRecursion(ActionHandlerType * action_handler,const BspNode * node)85   void WalkInOrderRecursion(ActionHandlerType* action_handler,
86                             const BspNode* node) const {
87     // If our view is in front of the the polygon
88     // in this node then walk back then front.
89     if (GetCameraPositionRelative(*(node->node_data)) == BSP_FRONT) {
90       WalkInOrderVisitNodes<ActionHandlerType>(
91           action_handler, node, node->back_child.get(), node->front_child.get(),
92           node->coplanars_front, node->coplanars_back);
93     } else {
94       WalkInOrderVisitNodes<ActionHandlerType>(
95           action_handler, node, node->front_child.get(), node->back_child.get(),
96           node->coplanars_back, node->coplanars_front);
97     }
98   }
99 
100   // Returns whether or not our viewer is in front of or behind the plane
101   // defined by this polygon/node
102   static BspCompareResult GetCameraPositionRelative(const DrawPolygon& node);
103 };
104 
105 }  // namespace viz
106 
107 #endif  // COMPONENTS_VIZ_SERVICE_DISPLAY_BSP_TREE_H_
108