Home | History | Annotate | Download | only in output 
      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 CC_OUTPUT_BSP_TREE_H_
      6 #define CC_OUTPUT_BSP_TREE_H_
      7 
      8 #include <list>
      9 #include <vector>
     10 
     11 #include "base/memory/scoped_ptr.h"
     12 #include "cc/base/scoped_ptr_deque.h"
     13 #include "cc/base/scoped_ptr_vector.h"
     14 #include "cc/output/bsp_compare_result.h"
     15 #include "cc/quads/draw_polygon.h"
     16 
     17 namespace cc {
     18 
     19 struct BspNode {
     20   // This represents the splitting plane.
     21   scoped_ptr<DrawPolygon> node_data;
     22   // This represents any coplanar geometry we found while building the BSP.
     23   ScopedPtrVector<DrawPolygon> coplanars_front;
     24   ScopedPtrVector<DrawPolygon> coplanars_back;
     25 
     26   scoped_ptr<BspNode> back_child;
     27   scoped_ptr<BspNode> front_child;
     28 
     29   explicit BspNode(scoped_ptr<DrawPolygon> data);
     30   ~BspNode();
     31 };
     32 
     33 class CC_EXPORT BspTree {
     34  public:
     35   explicit BspTree(ScopedPtrDeque<DrawPolygon>* list);
     36   scoped_ptr<BspNode>& root() { return root_; }
     37 
     38   template <typename ActionHandlerType>
     39   void TraverseWithActionHandler(ActionHandlerType* action_handler) const {
     40     if (root_) {
     41       WalkInOrderRecursion<ActionHandlerType>(action_handler, root_.get());
     42     }
     43   }
     44 
     45   ~BspTree();
     46 
     47  private:
     48   scoped_ptr<BspNode> root_;
     49 
     50   void FromList(ScopedPtrVector<DrawPolygon>* list);
     51   void BuildTree(BspNode* node, ScopedPtrDeque<DrawPolygon>* data);
     52 
     53   template <typename ActionHandlerType>
     54   void WalkInOrderAction(ActionHandlerType* action_handler,
     55                          DrawPolygon* item) const {
     56     (*action_handler)(item);
     57   }
     58 
     59   template <typename ActionHandlerType>
     60   void WalkInOrderVisitNodes(
     61       ActionHandlerType* action_handler,
     62       const BspNode* node,
     63       const BspNode* first_child,
     64       const BspNode* second_child,
     65       const ScopedPtrVector<DrawPolygon>& first_coplanars,
     66       const ScopedPtrVector<DrawPolygon>& second_coplanars) const {
     67     if (first_child) {
     68       WalkInOrderRecursion(action_handler, first_child);
     69     }
     70     for (size_t i = 0; i < first_coplanars.size(); i++) {
     71       WalkInOrderAction(action_handler, first_coplanars[i]);
     72     }
     73     WalkInOrderAction(action_handler, node->node_data.get());
     74     for (size_t i = 0; i < second_coplanars.size(); i++) {
     75       WalkInOrderAction(action_handler, second_coplanars[i]);
     76     }
     77     if (second_child) {
     78       WalkInOrderRecursion(action_handler, second_child);
     79     }
     80   }
     81 
     82   template <typename ActionHandlerType>
     83   void WalkInOrderRecursion(ActionHandlerType* action_handler,
     84                             const BspNode* node) const {
     85     // If our view is in front of the the polygon
     86     // in this node then walk back then front.
     87     if (GetCameraPositionRelative(*(node->node_data)) == BSP_FRONT) {
     88       WalkInOrderVisitNodes<ActionHandlerType>(action_handler,
     89                                                node,
     90                                                node->back_child.get(),
     91                                                node->front_child.get(),
     92                                                node->coplanars_front,
     93                                                node->coplanars_back);
     94     } else {
     95       WalkInOrderVisitNodes<ActionHandlerType>(action_handler,
     96                                                node,
     97                                                node->front_child.get(),
     98                                                node->back_child.get(),
     99                                                node->coplanars_back,
    100                                                node->coplanars_front);
    101     }
    102   }
    103 
    104   // Returns whether or not nodeA is on one or the other side of nodeB,
    105   // coplanar, or whether it crosses nodeB's plane and needs to be split
    106   static BspCompareResult GetNodePositionRelative(const DrawPolygon& node_a,
    107                                                   const DrawPolygon& node_b);
    108   // Returns whether or not our viewer is in front of or behind the plane
    109   // defined by this polygon/node
    110   static BspCompareResult GetCameraPositionRelative(const DrawPolygon& node);
    111 };
    112 
    113 }  // namespace cc
    114 
    115 #endif  // CC_OUTPUT_BSP_TREE_H_
    116