OLD | NEW |
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "cc/output/bsp_tree.h" | 5 #include "cc/output/bsp_tree.h" |
6 | 6 |
7 #include <vector> | 7 #include <vector> |
8 | 8 |
9 #include "base/memory/scoped_ptr.h" | 9 #include "base/memory/scoped_ptr.h" |
10 #include "cc/base/scoped_ptr_deque.h" | 10 #include "cc/base/container_util.h" |
11 #include "cc/base/scoped_ptr_vector.h" | 11 #include "cc/base/scoped_ptr_vector.h" |
12 #include "cc/output/bsp_compare_result.h" | 12 #include "cc/output/bsp_compare_result.h" |
13 #include "cc/quads/draw_polygon.h" | 13 #include "cc/quads/draw_polygon.h" |
14 | 14 |
15 namespace cc { | 15 namespace cc { |
16 | 16 |
17 BspNode::BspNode(scoped_ptr<DrawPolygon> data) : node_data(data.Pass()) { | 17 BspNode::BspNode(scoped_ptr<DrawPolygon> data) : node_data(data.Pass()) { |
18 } | 18 } |
19 | 19 |
20 BspNode::~BspNode() { | 20 BspNode::~BspNode() { |
21 } | 21 } |
22 | 22 |
23 BspTree::BspTree(ScopedPtrDeque<DrawPolygon>* list) { | 23 BspTree::BspTree(std::deque<scoped_ptr<DrawPolygon>>* list) { |
24 if (list->size() == 0) | 24 if (list->size() == 0) |
25 return; | 25 return; |
26 | 26 |
27 root_ = make_scoped_ptr(new BspNode(list->take_front())); | 27 root_ = make_scoped_ptr(new BspNode(PopFront(list))); |
28 BuildTree(root_.get(), list); | 28 BuildTree(root_.get(), list); |
29 } | 29 } |
30 | 30 |
31 // The idea behind using a deque for BuildTree's input is that we want to be | 31 // The idea behind using a deque for BuildTree's input is that we want to be |
32 // able to place polygons that we've decided aren't splitting plane candidates | 32 // able to place polygons that we've decided aren't splitting plane candidates |
33 // at the back of the queue while moving the candidate splitting planes to the | 33 // at the back of the queue while moving the candidate splitting planes to the |
34 // front when the heuristic decides that they're a better choice. This way we | 34 // front when the heuristic decides that they're a better choice. This way we |
35 // can always simply just take from the front of the deque for our node's | 35 // can always simply just take from the front of the deque for our node's |
36 // data. | 36 // data. |
37 void BspTree::BuildTree(BspNode* node, | 37 void BspTree::BuildTree(BspNode* node, |
38 ScopedPtrDeque<DrawPolygon>* polygon_list) { | 38 std::deque<scoped_ptr<DrawPolygon>>* polygon_list) { |
39 ScopedPtrDeque<DrawPolygon> front_list; | 39 std::deque<scoped_ptr<DrawPolygon>> front_list; |
40 ScopedPtrDeque<DrawPolygon> back_list; | 40 std::deque<scoped_ptr<DrawPolygon>> back_list; |
41 | 41 |
42 // We take in a list of polygons at this level of the tree, and have to | 42 // We take in a list of polygons at this level of the tree, and have to |
43 // find a splitting plane, then classify polygons as either in front of | 43 // find a splitting plane, then classify polygons as either in front of |
44 // or behind that splitting plane. | 44 // or behind that splitting plane. |
45 while (polygon_list->size() > 0) { | 45 while (!polygon_list->empty()) { |
46 // Is this particular polygon in front of or behind our splitting polygon. | 46 // Is this particular polygon in front of or behind our splitting polygon. |
47 BspCompareResult comparer_result = | 47 BspCompareResult comparer_result = |
48 GetNodePositionRelative(*polygon_list->front(), *(node->node_data)); | 48 GetNodePositionRelative(*polygon_list->front(), *(node->node_data)); |
49 | 49 |
50 // If it's clearly behind or in front of the splitting plane, we use the | 50 // If it's clearly behind or in front of the splitting plane, we use the |
51 // heuristic to decide whether or not we should put it at the back | 51 // heuristic to decide whether or not we should put it at the back |
52 // or front of the list. | 52 // or front of the list. |
53 switch (comparer_result) { | 53 switch (comparer_result) { |
54 case BSP_FRONT: | 54 case BSP_FRONT: |
55 front_list.push_back(polygon_list->take_front().Pass()); | 55 front_list.push_back(PopFront(polygon_list)); |
56 break; | 56 break; |
57 case BSP_BACK: | 57 case BSP_BACK: |
58 back_list.push_back(polygon_list->take_front().Pass()); | 58 back_list.push_back(PopFront(polygon_list)); |
59 break; | 59 break; |
60 case BSP_SPLIT: | 60 case BSP_SPLIT: |
61 { | 61 { |
62 scoped_ptr<DrawPolygon> polygon; | 62 scoped_ptr<DrawPolygon> polygon; |
63 scoped_ptr<DrawPolygon> new_front; | 63 scoped_ptr<DrawPolygon> new_front; |
64 scoped_ptr<DrawPolygon> new_back; | 64 scoped_ptr<DrawPolygon> new_back; |
65 // Time to split this geometry, *it needs to be split by node_data. | 65 // Time to split this geometry, *it needs to be split by node_data. |
66 polygon = polygon_list->take_front(); | 66 polygon = PopFront(polygon_list); |
67 bool split_result = | 67 bool split_result = |
68 polygon->Split(*(node->node_data), &new_front, &new_back); | 68 polygon->Split(*(node->node_data), &new_front, &new_back); |
69 DCHECK(split_result); | 69 DCHECK(split_result); |
70 if (!split_result) { | 70 if (!split_result) { |
71 break; | 71 break; |
72 } | 72 } |
73 front_list.push_back(new_front.Pass()); | 73 front_list.push_back(new_front.Pass()); |
74 back_list.push_back(new_back.Pass()); | 74 back_list.push_back(new_back.Pass()); |
75 break; | 75 break; |
76 } | 76 } |
77 case BSP_COPLANAR_FRONT: | 77 case BSP_COPLANAR_FRONT: |
78 node->coplanars_front.push_back(polygon_list->take_front()); | 78 node->coplanars_front.push_back(PopFront(polygon_list)); |
79 break; | 79 break; |
80 case BSP_COPLANAR_BACK: | 80 case BSP_COPLANAR_BACK: |
81 node->coplanars_back.push_back(polygon_list->take_front()); | 81 node->coplanars_back.push_back(PopFront(polygon_list)); |
82 break; | 82 break; |
83 default: | 83 default: |
84 NOTREACHED(); | 84 NOTREACHED(); |
85 break; | 85 break; |
86 } | 86 } |
87 } | 87 } |
88 | 88 |
89 // Build the back subtree using the front of the back_list as our splitter. | 89 // Build the back subtree using the front of the back_list as our splitter. |
90 if (back_list.size() > 0) { | 90 if (back_list.size() > 0) { |
91 node->back_child = make_scoped_ptr(new BspNode(back_list.take_front())); | 91 node->back_child = make_scoped_ptr(new BspNode(PopFront(&back_list))); |
92 BuildTree(node->back_child.get(), &back_list); | 92 BuildTree(node->back_child.get(), &back_list); |
93 } | 93 } |
94 | 94 |
95 // Build the front subtree using the front of the front_list as our splitter. | 95 // Build the front subtree using the front of the front_list as our splitter. |
96 if (front_list.size() > 0) { | 96 if (front_list.size() > 0) { |
97 node->front_child = | 97 node->front_child = make_scoped_ptr(new BspNode(PopFront(&front_list))); |
98 scoped_ptr<BspNode>(new BspNode(front_list.take_front())); | |
99 BuildTree(node->front_child.get(), &front_list); | 98 BuildTree(node->front_child.get(), &front_list); |
100 } | 99 } |
101 } | 100 } |
102 | 101 |
103 BspCompareResult BspTree::GetNodePositionRelative(const DrawPolygon& node_a, | 102 BspCompareResult BspTree::GetNodePositionRelative(const DrawPolygon& node_a, |
104 const DrawPolygon& node_b) { | 103 const DrawPolygon& node_b) { |
105 return DrawPolygon::SideCompare(node_a, node_b); | 104 return DrawPolygon::SideCompare(node_a, node_b); |
106 } | 105 } |
107 | 106 |
108 // The base comparer with 0,0,0 as camera position facing forward | 107 // The base comparer with 0,0,0 as camera position facing forward |
109 BspCompareResult BspTree::GetCameraPositionRelative(const DrawPolygon& node) { | 108 BspCompareResult BspTree::GetCameraPositionRelative(const DrawPolygon& node) { |
110 if (node.normal().z() > 0.0f) { | 109 if (node.normal().z() > 0.0f) { |
111 return BSP_FRONT; | 110 return BSP_FRONT; |
112 } | 111 } |
113 return BSP_BACK; | 112 return BSP_BACK; |
114 } | 113 } |
115 | 114 |
116 BspTree::~BspTree() { | 115 BspTree::~BspTree() { |
117 } | 116 } |
118 | 117 |
119 } // namespace cc | 118 } // namespace cc |
OLD | NEW |