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

Side by Side 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: Created 6 years, 4 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 unified diff | Download patch
OLDNEW
(Empty)
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 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_
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698