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

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: 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 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,
27 ScopedPtrVector<DrawPolygon>* list)
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 float max_weight = 0.0f;
41 ScopedPtrDeque<DrawPolygon> list_data;
42 for (ScopedPtrVector<DrawPolygon>::iterator it = list->begin();
43 it != list->end();
44 ++it) {
45 float poly_weight = controller_->SplitWeight(*list->back());
46 if (poly_weight > max_weight) {
47 list_data.push_front(list->take(it));
48 max_weight = poly_weight;
49 } else {
50 list_data.push_back(list->take(it));
51 }
52 }
53
54 root_ = scoped_ptr<BspNode>(new BspNode(list_data.take_front()));
55 BuildTree(root_, &list_data);
56 }
57
58 static void BuildHelper(float new_weight,
Ian Vollick 2014/07/19 00:45:01 nit: how about UpdateNodeListAndMaxWeight? I know
troyhildebrandt 2014/07/21 19:16:50 Done.
59 float* current_max_weight,
60 ScopedPtrDeque<DrawPolygon>* list,
61 scoped_ptr<DrawPolygon> node_data) {
62 if (new_weight > *current_max_weight) {
63 list->push_front(node_data.Pass());
64 *current_max_weight = new_weight;
65 } else {
66 list->push_back(node_data.Pass());
67 }
68 }
69
70 // The idea behind using a deque for BuildTree's input is that we want to be
71 // able to place polygons that we've decided aren't splitting plane candidates
72 // at the back of the queue while moving the candidate splitting planes to the
73 // front when the heuristic decides that they're a better choice. This way we
74 // can always simply just take from the front of the deque for our node's
75 // data.
76 void BspTree::BuildTree(const scoped_ptr<BspNode>& node,
77 ScopedPtrDeque<DrawPolygon>* data) {
78 ScopedPtrDeque<DrawPolygon> front_list;
79 ScopedPtrDeque<DrawPolygon> back_list;
80 // We keep track of the splitting weights (the "score" of a polygon that
81 // chooses whether or not it's the splitting plane of a new node) for both
82 // the front and back list independently so the better splitting plane is
83 // chosen for both sides.
84 float max_front_weight = 0.0f;
85 float max_back_weight = 0.0f;
86
87 // We take in a list of polygons at this level of the tree, and have to
88 // find a splitting plane, then classify polygons as either in front of
89 // or behind that splitting plane.
90 while (data->size() > 0) {
91 // Is this particular polygon in front of or behind our splitting polygon.
92 BspCompareResult comparer_result = controller_->GetNodePositionRelative(
93 *data->front(), *(node->node_data));
94 float poly_weight = controller_->SplitWeight(*data->front());
95
96 // If it's clearly behind or in front of the splitting plane, we use the
97 // heuristic to decide whether or not we should put it at the back
98 // or front of the list.
99 scoped_ptr<DrawPolygon> new_front;
100 scoped_ptr<DrawPolygon> new_back;
101 float front_poly_weight = 0.0f;
102 float back_poly_weight = 0.0f;
103 switch (comparer_result) {
104 // Front.
Ian Vollick 2014/07/19 00:45:01 These comments don't add much; I'd ditch them.
troyhildebrandt 2014/07/21 19:16:50 Done.
105 case BSP_FRONT:
106 BuildHelper(poly_weight,
107 &max_front_weight,
108 &front_list,
109 data->take_front().Pass());
110 break;
111 // Back.
112 case BSP_BACK:
113 BuildHelper(poly_weight,
114 &max_back_weight,
115 &back_list,
116 data->take_front().Pass());
117 break;
118 // Split.
119 case BSP_SPLIT:
120 // Time to split this geometry, *it needs to be split by node_data.
121 if (controller_->SplitPolygon(data->take_front(),
122 *(node->node_data),
123 &new_front,
124 &new_back)) {
125 // Now add new_front and new_back to their respective lists, again
126 // using the heuristic in an attempt to choose the best splitting
127 // plane, and keep track of the highest weighted polygon known so far
128 // so if we find something better we can use that instead.
129 front_poly_weight = controller_->SplitWeight(*new_front);
130 back_poly_weight = controller_->SplitWeight(*new_back);
131
132 BuildHelper(front_poly_weight,
133 &max_front_weight,
134 &front_list,
135 new_front.Pass());
136 BuildHelper(
137 back_poly_weight, &max_back_weight, &back_list, new_back.Pass());
138 }
139 break;
140 // Coplanar front.
141 case BSP_COPLANAR_FRONT:
142 node->coplanars_front.push_back(data->take_front());
143 break;
144 // Coplanar back.
145 case BSP_COPLANAR_BACK:
146 node->coplanars_back.push_back(data->take_front());
147 break;
148 default:
149 NOTREACHED();
150 break;
151 }
152 }
153
154 // Build the back subtree using the front of the back_list as our splitter.
155 if (back_list.size() > 0) {
156 node->back_child = scoped_ptr<BspNode>(new BspNode(back_list.take_front()));
157 BuildTree(node->back_child, &back_list);
158 }
159
160 // Build the front subtree using the front of the front_list as our splitter.
161 if (front_list.size() > 0) {
162 node->front_child =
163 scoped_ptr<BspNode>(new BspNode(front_list.take_front()));
164 BuildTree(node->front_child, &front_list);
165 }
166 }
167
168 void BspTree::Clear() {
169 if (root_) {
170 root_.reset();
171 }
172 }
173
174 BspTree::~BspTree() {
175 Clear();
176 }
177
178 } // namespace cc
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698