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 void BspTree::FromList(ScopedPtrVector<DrawPolygon>* list) { | |
33 if (list->size() <= 0) | |
Ian Vollick
2014/07/16 20:54:32
Can size < 0?
troyhildebrandt
2014/07/18 21:48:26
Nope, it's unsigned, changed to == 0.
| |
34 return; | |
35 | |
36 float split_weight = 0.0f; | |
Ian Vollick
2014/07/16 20:54:33
nit: max_weight or max_split_weight conveys a bit
troyhildebrandt
2014/07/18 21:48:25
Done.
| |
37 ScopedPtrDeque<DrawPolygon> list_data; | |
38 for (ScopedPtrVector<DrawPolygon>::iterator it = list->begin(); | |
39 it != list->end(); | |
40 ++it) { | |
41 float poly_weight = controller_->SplitWeight(*list->back()); | |
42 if (poly_weight > split_weight) { | |
43 list_data.push_front(list->take(it)); | |
44 split_weight = poly_weight; | |
45 } else { | |
46 list_data.push_back(list->take(it)); | |
47 } | |
48 } | |
49 | |
50 root_ = scoped_ptr<BspNode>(new BspNode(list_data.take_front())); | |
51 BuildTree(root_, &list_data); | |
52 } | |
53 | |
54 void BspTree::BuildTree(const scoped_ptr<BspNode>& node, | |
55 ScopedPtrDeque<DrawPolygon>* data) { | |
56 ScopedPtrDeque<DrawPolygon> front_list; | |
57 ScopedPtrDeque<DrawPolygon> back_list; | |
58 // We keep track of the splitting weights (the "score" of a polygon that | |
59 // chooses whether or not it's the splitting plane of a new node) for both | |
60 // the front and back list independently so the better splitting plane is | |
61 // chosen for both sides. | |
62 float front_weight = 0.0f; | |
Ian Vollick
2014/07/16 20:54:32
Could you choose names for these that involve "max
troyhildebrandt
2014/07/18 21:48:26
Done.
| |
63 float back_weight = 0.0f; | |
64 | |
65 // We take in a list of polygons at this level of the tree, and have to | |
66 // find a splitting plane, then classify polygons as either in front of | |
67 // or behind that splitting plane. | |
68 while (data->size() > 0) { | |
69 // Is this particular polygon in front of or behind our splitting polygon. | |
70 BspCompareResult comparer_result = controller_->GetNodePositionRelative( | |
71 *data->front(), *(node->node_data)); | |
72 float poly_weight = controller_->SplitWeight(*data->front()); | |
73 | |
74 // If it's clearly behind or in front of the splitting plane, we use the | |
75 // heuristic to decide whether or not we should put it at the back | |
76 // or front of the list. | |
77 if (comparer_result == BSP_FRONT) { | |
Ian Vollick
2014/07/16 20:54:32
switch?
troyhildebrandt
2014/07/18 21:48:26
Done.
| |
78 if (poly_weight > front_weight) { | |
79 front_list.push_front(data->take_front()); | |
80 front_weight = poly_weight; | |
81 } else { | |
82 front_list.push_back(data->take_front()); | |
83 } | |
84 | |
85 } else if (comparer_result == BSP_BACK) { | |
86 if (poly_weight > back_weight) { | |
87 back_list.push_front(data->take_front()); | |
88 back_weight = poly_weight; | |
89 } else { | |
90 back_list.push_back(data->take_front()); | |
Ian Vollick
2014/07/16 20:54:33
The front and back behavior is so symmetric that i
troyhildebrandt
2014/07/18 21:48:26
Done.
| |
91 } | |
92 | |
93 } else if (comparer_result == BSP_SPLIT) { | |
94 // Time to split this geometry, *it needs to be split by node_data. | |
95 scoped_ptr<DrawPolygon> new_front; | |
96 scoped_ptr<DrawPolygon> new_back; | |
97 if (controller_->SplitPolygon( | |
98 data->take_front(), *(node->node_data), &new_front, &new_back)) { | |
99 // Now add new_front and new_back to their respective lists, again | |
100 // using the heuristic in an attempt to choose the best splitting | |
101 // plane, and keep track of the highest weighted polygon known so far | |
102 // so if we find something better we can use that instead. | |
103 float front_poly_weight = controller_->SplitWeight(*new_front); | |
104 float back_poly_weight = controller_->SplitWeight(*new_back); | |
105 | |
106 if (front_poly_weight > front_weight) { | |
107 front_list.push_front(new_front.Pass()); | |
108 front_weight = front_poly_weight; | |
109 } else { | |
110 front_list.push_back(new_front.Pass()); | |
Ian Vollick
2014/07/16 20:54:32
These two bits could use that helper, too.
troyhildebrandt
2014/07/18 21:48:26
Done.
| |
111 } | |
112 | |
113 if (back_poly_weight > back_weight) { | |
114 back_list.push_front(new_back.Pass()); | |
115 back_weight = back_poly_weight; | |
116 } else { | |
117 back_list.push_back(new_back.Pass()); | |
118 } | |
119 } | |
120 } else if (comparer_result == BSP_COPLANAR_FRONT) { | |
121 node->coplanars_front.push_back(data->take_front()); | |
122 } else if (comparer_result == BSP_COPLANAR_BACK) { | |
123 node->coplanars_back.push_back(data->take_front()); | |
124 } | |
Ian Vollick
2014/07/16 20:54:33
else {
NOTREACHED(); // or equivalent for the de
troyhildebrandt
2014/07/18 21:48:26
Done.
| |
125 } | |
126 | |
127 // Build the back subtree using the front of the back_list as our splitter. | |
128 if (back_list.size() > 0) { | |
129 node->back_child = scoped_ptr<BspNode>(new BspNode(back_list.take_front())); | |
130 BuildTree(node->back_child, &back_list); | |
131 } | |
132 | |
133 // Build the front subtree using the front of the front_list as our splitter. | |
134 if (front_list.size() > 0) { | |
135 node->front_child = | |
136 scoped_ptr<BspNode>(new BspNode(front_list.take_front())); | |
137 BuildTree(node->front_child, &front_list); | |
138 } | |
139 } | |
140 | |
141 void BspTree::Clear() { | |
142 if (root_) { | |
143 root_.reset(); | |
144 } | |
145 } | |
146 | |
147 BspTree::~BspTree() { | |
148 Clear(); | |
149 } | |
150 | |
151 } // namespace cc | |
OLD | NEW |