Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(3058)

Unified Diff: cc/output/bsp_tree.h

Issue 384083002: WIP BSP Tree for 3D Layer Sorting (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Removed some forgotten debug output Created 6 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
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_

Powered by Google App Engine
This is Rietveld 408576698