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