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