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

Side by Side Diff: cc/output/bsp_tree.cc

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, 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 #include "cc/output/bsp_tree.h"
6
7 #include <list>
8 #include <vector>
9
10 #include "base/memory/scoped_ptr.h"
11 #include "cc/base/scoped_ptr_deque.h"
12 #include "cc/base/scoped_ptr_vector.h"
13 #include "cc/output/bsp_compare_result.h"
14 #include "cc/output/bsp_controller.h"
15 #include "cc/quads/draw_polygon.h"
16
17 namespace cc {
18
19 BspNode::BspNode(scoped_ptr<DrawPolygon> data) {
20 node_data = data.Pass();
21 }
22
23 BspNode::~BspNode() {
24 }
25
26 BspTree::BspTree(BspController* bsp_controller,
enne (OOO) 2014/07/28 21:38:20 This is kind of an OO weirdness. BspController is
troyhildebrandt 2014/07/29 00:04:33 Removed the BspController, it's an artifact of an
27 ScopedPtrVector<DrawPolygon>* list)
enne (OOO) 2014/07/28 21:38:20 The BspTree takes ownership of this list, right? I
troyhildebrandt 2014/07/29 00:04:33 Now BspTree constructor takes a ScopedPtrDeque* in
troyhildebrandt 2014/07/29 00:04:33 Removed FromList, made the constructor do minimal
28 : controller_(bsp_controller) {
29 FromList(list);
30 }
31
32 // FromList takes an input list and moves the better splitting polygons to the
33 // front of the queue so when it comes time to build the tree, we already have
34 // our splitting plane decided in the first element of the queue. BuildTree is
35 // then called to perform the actual building of the tree using this list.
36 void BspTree::FromList(ScopedPtrVector<DrawPolygon>* list) {
37 if (list->size() == 0)
38 return;
39
40 ScopedPtrDeque<DrawPolygon> list_data;
41 for (ScopedPtrVector<DrawPolygon>::iterator it = list->begin();
42 it != list->end();
43 ++it) {
44 list_data.push_back(list->take(it));
45 }
46
47 root_ = scoped_ptr<BspNode>(new BspNode(list_data.take_front()));
48 BuildTree(root_.get(), &list_data);
49 }
50
51 // The idea behind using a deque for BuildTree's input is that we want to be
52 // able to place polygons that we've decided aren't splitting plane candidates
53 // at the back of the queue while moving the candidate splitting planes to the
54 // front when the heuristic decides that they're a better choice. This way we
55 // can always simply just take from the front of the deque for our node's
56 // data.
57 void BspTree::BuildTree(BspNode* node, ScopedPtrDeque<DrawPolygon>* data) {
enne (OOO) 2014/07/28 21:38:20 Can you come up with a better name than "data"?
troyhildebrandt 2014/07/29 00:04:32 Done.
58 ScopedPtrDeque<DrawPolygon> front_list;
59 ScopedPtrDeque<DrawPolygon> back_list;
60
61 // We take in a list of polygons at this level of the tree, and have to
62 // find a splitting plane, then classify polygons as either in front of
63 // or behind that splitting plane.
64 while (data->size() > 0) {
65 // Is this particular polygon in front of or behind our splitting polygon.
66 BspCompareResult comparer_result = controller_->GetNodePositionRelative(
67 *data->front(), *(node->node_data));
68
69 // If it's clearly behind or in front of the splitting plane, we use the
70 // heuristic to decide whether or not we should put it at the back
71 // or front of the list.
72 scoped_ptr<DrawPolygon> new_front;
73 scoped_ptr<DrawPolygon> new_back;
74 switch (comparer_result) {
75 case BSP_FRONT:
76 front_list.push_back(data->take_front().Pass());
77 break;
78 case BSP_BACK:
79 back_list.push_back(data->take_front().Pass());
80 break;
81 case BSP_SPLIT:
82 // Time to split this geometry, *it needs to be split by node_data.
83 if (controller_->SplitPolygon(data->take_front(),
84 *(node->node_data),
85 &new_front,
86 &new_back)) {
87 front_list.push_back(new_front.Pass());
88 back_list.push_back(new_back.Pass());
89 }
90 break;
91 case BSP_COPLANAR_FRONT:
92 node->coplanars_front.push_back(data->take_front());
93 break;
94 case BSP_COPLANAR_BACK:
95 node->coplanars_back.push_back(data->take_front());
96 break;
97 default:
98 NOTREACHED();
99 break;
100 }
101 }
102
103 // Build the back subtree using the front of the back_list as our splitter.
104 if (back_list.size() > 0) {
105 node->back_child = scoped_ptr<BspNode>(new BspNode(back_list.take_front()));
106 BuildTree(node->back_child.get(), &back_list);
107 }
108
109 // Build the front subtree using the front of the front_list as our splitter.
110 if (front_list.size() > 0) {
111 node->front_child =
112 scoped_ptr<BspNode>(new BspNode(front_list.take_front()));
113 BuildTree(node->front_child.get(), &front_list);
114 }
115 }
116
117 void BspTree::Clear() {
118 if (root_) {
119 root_.reset();
120 }
121 }
122
123 BspTree::~BspTree() {
124 Clear();
enne (OOO) 2014/07/28 21:38:19 Why does there need to be an explicit clear? Can t
troyhildebrandt 2014/07/29 00:04:32 Removed.
125 }
126
127 } // namespace cc
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698