OLD | NEW |
---|---|
(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 | |
OLD | NEW |