Index: cc/output/bsp_tree.h |
diff --git a/cc/output/bsp_tree.h b/cc/output/bsp_tree.h |
new file mode 100644 |
index 0000000000000000000000000000000000000000..bb9e85824c081f37cc053e5a6d1b905ef4202d09 |
--- /dev/null |
+++ b/cc/output/bsp_tree.h |
@@ -0,0 +1,111 @@ |
+// Copyright 2013 The Chromium Authors. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+#ifndef CC_OUTPUT_BSP_TREE_H_ |
+#define CC_OUTPUT_BSP_TREE_H_ |
+ |
+#include <list> |
+#include <vector> |
+ |
+#include "base/memory/scoped_ptr.h" |
+#include "cc/base/scoped_ptr_deque.h" |
+#include "cc/base/scoped_ptr_vector.h" |
+#include "cc/output/bsp_compare_result.h" |
+#include "cc/output/bsp_controller.h" |
+#include "cc/quads/draw_polygon.h" |
+ |
+namespace cc { |
+ |
+struct BspNode { |
+ // This represents the splitting plane. |
+ scoped_ptr<DrawPolygon> node_data; |
+ // This represents any coplanar geometry we found while building the BSP. |
+ ScopedPtrVector<DrawPolygon> coplanars_front; |
+ ScopedPtrVector<DrawPolygon> coplanars_back; |
+ |
+ scoped_ptr<BspNode> back_child; |
+ scoped_ptr<BspNode> front_child; |
+ |
+ explicit BspNode(scoped_ptr<DrawPolygon> data); |
+ ~BspNode(); |
+}; |
+ |
+class BspTree { |
+ public: |
+ BspTree(BspController* bsp_controller, ScopedPtrVector<DrawPolygon>* list); |
+ scoped_ptr<BspNode>& root() { return root_; } |
+ |
+ template <typename ActionHandlerType> |
+ void TraverseWithActionHandler(ActionHandlerType* action_handler) const { |
+ if (root_) { |
+ WalkInOrderRecursion<ActionHandlerType>(action_handler, root_.get()); |
+ } |
+ } |
+ |
+ void Clear(); |
+ ~BspTree(); |
+ |
+ private: |
+ scoped_ptr<BspNode> root_; |
+ BspController* controller_; |
+ |
+ void FromList(ScopedPtrVector<DrawPolygon>* list); |
+ void BuildTree(BspNode* node, ScopedPtrDeque<DrawPolygon>* data); |
+ |
+ template <typename ActionHandlerType> |
+ void WalkInOrderAction(ActionHandlerType* action_handler, |
+ DrawPolygon* item) const { |
+ (*action_handler)(item); |
+ } |
+ |
+ template <typename ActionHandlerType> |
+ void WalkInOrderVisitNodes( |
+ ActionHandlerType* action_handler, |
+ const BspNode* node, |
+ const BspNode* first_child, |
+ const BspNode* second_child, |
+ const ScopedPtrVector<DrawPolygon>& first_coplanars, |
+ const ScopedPtrVector<DrawPolygon>& second_coplanars) const { |
+ if (first_child) { |
+ WalkInOrderRecursion(action_handler, first_child); |
+ } |
+ for (unsigned int i = 0; i < first_coplanars.size(); i++) { |
enne (OOO)
2014/07/28 21:38:20
unsigned int => size_t, here and elsewhere
troyhildebrandt
2014/07/29 00:04:33
Done.
|
+ WalkInOrderAction(action_handler, first_coplanars[i]); |
+ } |
+ WalkInOrderAction(action_handler, node->node_data.get()); |
+ for (unsigned int i = 0; i < second_coplanars.size(); i++) { |
+ WalkInOrderAction(action_handler, second_coplanars[i]); |
+ } |
+ if (second_child) { |
+ WalkInOrderRecursion(action_handler, second_child); |
+ } |
+ } |
+ |
+ template <typename ActionHandlerType> |
+ void WalkInOrderRecursion(ActionHandlerType* action_handler, |
+ const BspNode* node) const { |
+ // If our view is in front of the the polygon |
+ // in this node then walk back then front. |
+ if (controller_->GetCameraPositionRelative(*(node->node_data)) == |
+ BSP_FRONT) { |
+ WalkInOrderVisitNodes<ActionHandlerType>(action_handler, |
+ node, |
+ node->back_child.get(), |
+ node->front_child.get(), |
+ node->coplanars_front, |
+ node->coplanars_back); |
+ } else { |
+ WalkInOrderVisitNodes<ActionHandlerType>(action_handler, |
+ node, |
+ node->front_child.get(), |
+ node->back_child.get(), |
+ node->coplanars_back, |
+ node->coplanars_front); |
+ } |
+ } |
+}; |
+ |
+} // namespace cc |
+ |
+#endif // CC_OUTPUT_BSP_TREE_H_ |