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

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: Small fixes to style/formatting, minor cleanup. 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 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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698