1 #include "boxm2_refine_block_function.h"
2 //:
3 // \file
4
5 #define copy_parent_data_ 1
6
7
8 //: initialize generic data base pointers as their data type
init_data(const boxm2_scene_sptr & scene,boxm2_block * blk,std::vector<boxm2_data_base * > & datas,float prob_thresh)9 bool boxm2_refine_block_function::init_data(const boxm2_scene_sptr& scene, boxm2_block* blk, std::vector<boxm2_data_base*> & datas, float prob_thresh)
10 {
11 //store block and pointer to uchar16 3d block
12 scene_ = scene;
13 blk_ = blk;
14
15 //store data buffers
16 int i=0;
17 alpha_ = (float*) datas[i++]->data_buffer();
18 mog_ = (uchar8*) datas[i++]->data_buffer();
19 num_obs_ = (ushort4*) datas[i++]->data_buffer();
20
21 //block max level
22 max_level_ = blk_->max_level();
23
24 //max alpha integrated
25 max_alpha_int_ = -std::log(1.f - prob_thresh);
26
27 //Data length now is constant
28 data_len_ = 65536;
29
30 //length of one side of a sub block
31 block_len_ = blk_->sub_block_dim().x();
32
33 //USE rootlevel to determine MAX_INNER and MAX_CELLS
34 if (max_level_ == 1) {
35 std::cout<<"Trying to refine scene with max level 1"<<std::endl;
36 return true;
37 }
38 else if (max_level_ == 2) {
39 MAX_INNER_CELLS_=1, MAX_CELLS_=9;
40 }
41 else if (max_level_ == 3) {
42 MAX_INNER_CELLS_=9, MAX_CELLS_=73;
43 }
44 else if (max_level_ == 4) {
45 MAX_INNER_CELLS_=73, MAX_CELLS_=585;
46 }
47
48 std::cout<<"Refine Info: [blk "<<blk->block_id()
49 <<"] [blk_len "<<block_len_
50 <<"] [data_len "<<data_len_
51 <<"] [max_alpha_int "<<max_alpha_int_
52 <<"] [max level "<<max_level_
53 <<']'<<std::endl;
54
55 //for debugging
56 num_split_ = 0;
57
58 return true;
59 }
60
61 //----- IF THE BLOCK IS NOT RANDOMLY DISTRIBUTED, USE DETERMINISTIC METHOD -----
62 // New Method Summary:
63 // - NEED TO CLEAR OUT THE GPU CACHE BEFORE YOU START.. so you don't overwrite stuff accidentally...
64 // - Create Block Copy, refine trees into that copy, maintaining old copy and array of new tree sizes
65 // - Do scan on size vector (cum sum)
66 // - Swap data into new buffers: For each data type
67 // - get BOCL_MEM* data independent of cpu pointer (from cache)
68 // - remove the BOCL_MEM* from the gpu cache (don't delete it)
69 // - do a deep delete (delete CPU buffer from CPU cache)
70 // - get a new data pointer (with newSize), will create CPU buffer and GPU buffer
71 // - Run refine_data_kernel with the two buffers
72 // - delete the old BOCL_MEM*, and that's it...
refine_deterministic(std::vector<boxm2_data_base * > & datas)73 bool boxm2_refine_block_function::refine_deterministic(std::vector<boxm2_data_base*>& datas)
74 {
75 std::cout<<"CPU deterministic refine:"<<std::endl;
76
77 //loop over each tree, refine it in place (keep a vector of locations for
78 // posterities sake
79 boxm2_array_3d<uchar16> trees = blk_->trees_copy(); //trees to refine
80 auto* trees_copy = new uchar16[trees.size()]; //copy of those trees
81 int* dataIndex = new int[trees.size()]; //data index for each new tree
82 int currIndex = 0; //curr tree being looked at
83 int dataSize = 0; //running sum of data size
84 boxm2_array_3d<uchar16>::iterator blk_iter;
85 for (blk_iter = trees.begin(); blk_iter != trees.end(); ++blk_iter, ++currIndex)
86 {
87 //0. store data index for eahc tree.
88 dataIndex[currIndex] = dataSize;
89
90 //1. get current tree information
91 uchar16 tree = (*blk_iter);
92 boct_bit_tree curr_tree( (unsigned char*) tree.data_block(), max_level_);
93
94 //3. refine tree locally (only updates refined_tree and returns new tree size)
95 boct_bit_tree refined_tree = this->refine_bit_tree(curr_tree, 0, false); //i.e. is not random
96 int newSize = refined_tree.num_cells();
97
98 //cache refined tree
99 std::memcpy (trees_copy[currIndex].data_block(), refined_tree.get_bits(), 16);
100 dataSize += newSize;
101 }
102
103
104 //2. allocate new data arrays of the appropriate size
105 std::cout<<"Allocating new data blocks"<<std::endl;
106 boxm2_block_id id = datas[0]->block_id();
107 boxm2_data_base* newA = new boxm2_data_base(new char[dataSize * sizeof(float) ], dataSize * sizeof(float), id);
108 boxm2_data_base* newM = new boxm2_data_base(new char[dataSize * sizeof(uchar8)], dataSize * sizeof(uchar8), id);
109 boxm2_data_base* newN = new boxm2_data_base(new char[dataSize * sizeof(ushort4)], dataSize * sizeof(ushort4), id);
110 auto* alpha_cpy = (float*) newA->data_buffer();
111 auto* mog_cpy = (uchar8*) newM->data_buffer();
112 auto* num_obs_cpy = (ushort4*) newN->data_buffer();
113
114 //3. loop through tree again, putting the data in the right place
115 std::cout<<"Swapping data into new blocks..."<<std::endl;
116 int newInitCount = 0;
117 currIndex = 0;
118 for (blk_iter = trees.begin(); blk_iter != trees.end(); ++blk_iter, ++currIndex)
119 {
120 //1. get current tree information
121 uchar16 tree = (*blk_iter);
122 boct_bit_tree old_tree( (unsigned char*) tree.data_block(), max_level_);
123
124 //2. refine tree locally (only updates refined_tree and returns new tree size)
125 boct_bit_tree refined_tree( (unsigned char*) trees_copy[currIndex].data_block(), max_level_);
126
127 //2.5 pack data bits into refined tree
128 //store data index in bits [10, 11, 12, 13] ;
129 int root_index = dataIndex[currIndex];
130 refined_tree.set_data_ptr(root_index, false); //is not random
131
132 //3. swap data from old location to new location
133 newInitCount += this->move_data(old_tree, refined_tree, alpha_cpy, mog_cpy, num_obs_cpy);
134
135 //4. store old tree in new tree, swap data out
136 std::memcpy(blk_iter, refined_tree.get_bits(), 16);
137 }
138 blk_->set_trees(trees);
139 std::cout<<"Number of new cells: "<<newInitCount<<std::endl;
140
141 //3. Replace data in the cache
142 boxm2_cache_sptr cache = boxm2_cache::instance();
143 cache->replace_data_base(scene_, id, boxm2_data_traits<BOXM2_ALPHA>::prefix(), newA);
144 cache->replace_data_base(scene_, id, boxm2_data_traits<BOXM2_MOG3_GREY>::prefix(), newM);
145 cache->replace_data_base(scene_, id, boxm2_data_traits<BOXM2_NUM_OBS>::prefix(), newN);
146
147 return true;
148 }
149
150 /////////////////////////////////////////////////////////////////
151 ////Refine Tree (refines local tree)
152 ////Depth first search iteration of the tree (keeping track of node level)
153 ////1) parent pointer, 2) child pointer 3) data pointer 4) nothing right now
154 // Kind of a weird mix of functions - the tree structure is modified locally,
155 // so no tree_buffer information is needed, whereas the data is modified
156 // on the global level, so buffers, offsets are used
157 /////////////////////////////////////////////////////////////////
refine_bit_tree(boct_bit_tree & unrefined_tree,int buff_offset,bool is_random)158 boct_bit_tree boxm2_refine_block_function::refine_bit_tree(boct_bit_tree& unrefined_tree,
159 int buff_offset,
160 bool is_random)
161 {
162 //initialize tree to return
163 boct_bit_tree refined_tree(unrefined_tree.get_bits(), max_level_);
164
165 //no need to do depth first search, just iterate and check each node along the way
166 //(iterate through the max number of inner cells)
167 for (int i=0; i<MAX_INNER_CELLS_; ++i)
168 {
169 //if current bit is 0 and parent bit is 1, you're at a leaf
170 int pi = (i-1)>>3; //Bit_index of parent bit
171 bool validParent = unrefined_tree.bit_at(pi) || (i==0); // special case for root
172 if (validParent && unrefined_tree.bit_at(i)==0)
173 {
174 //////////////////////////////////////////////////
175 //LEAF CODE HERE
176 //////////////////////////////////////////////////
177 //find side length for cell of this level = block_len/2^currDepth
178 int currDepth = unrefined_tree.depth_at(i);
179 double side_len = block_len_/ double(1<<currDepth);
180
181 //get alpha value for this cell;
182 int dataIndex = unrefined_tree.get_data_index(i, is_random);
183 if (is_random) {
184 dataIndex %= data_len_; //gets offset within buffer
185 dataIndex += buff_offset;
186 }
187 float alpha = alpha_[dataIndex];
188
189 //integrate alpha value
190 float alpha_int = alpha * float(side_len);
191
192 //IF alpha value triggers split, tack on 8 children to end of tree array
193 if (alpha_int > max_alpha_int_ && currDepth < max_level_-1)
194 {
195 //change value of bit_at(i) to 1;
196 refined_tree.set_bit_at(i, true);
197
198 //keep track of number of nodes that split
199 ++num_split_;
200 }
201 ////////////////////////////////////////////
202 //END LEAF SPECIFIC CODE
203 ////////////////////////////////////////////
204 }
205 }
206 return refined_tree;
207 }
208
209
210 //Deterministic move data
211 //moves data from src to destination
212 //returns the number of split nodes for this tree (for assertions)
move_data(boct_bit_tree & unrefined_tree,boct_bit_tree & refined_tree,float * alpha_cpy,uchar8 * mog_cpy,ushort4 * num_obs_cpy)213 int boxm2_refine_block_function::move_data(boct_bit_tree& unrefined_tree,
214 boct_bit_tree& refined_tree,
215 float* alpha_cpy,
216 uchar8* mog_cpy,
217 ushort4* num_obs_cpy )
218 {
219 int newSize = refined_tree.num_cells();
220
221 //zip through each leaf cell and
222 int oldDataPtr = unrefined_tree.get_data_ptr(false);
223 int newDataPtr = refined_tree.get_data_ptr(false);
224 int newInitCount = 0;
225 int cellsMoved = 0;
226 for (int j=0; j<MAX_CELLS_ && cellsMoved<newSize; ++j)
227 {
228 //--------------------------------------------------------------------
229 //4 Cases:
230 // - Old cell and new cell exist - transfer data over
231 // - new cell exists, old cell doesn't - create new occupancy based on depth
232 // - old cell exists, new cell doesn't - uh oh this is bad news
233 // - neither cell exists - do nothing and carry on
234 //--------------------------------------------------------------------
235 //if parent bit is 1, then you're a valid cell
236 int pj = (j-1)>>3; //Bit_index of parent bit
237 bool validCellOld = (j==0) || unrefined_tree.bit_at(pj);
238 bool validCellNew = (j==0) || refined_tree.bit_at(pj);
239 if (validCellOld && validCellNew) {
240 //move root data to new location
241 alpha_cpy[newDataPtr] = alpha_[oldDataPtr];
242 mog_cpy[newDataPtr] = mog_[oldDataPtr];
243 num_obs_cpy[newDataPtr]= num_obs_[oldDataPtr];
244
245 //increment
246 ++oldDataPtr;
247 ++newDataPtr;
248 ++cellsMoved;
249 }
250 //case where it's a new leaf...
251 else if (validCellNew) {
252 //move root data to new location
253 int parentLevel = unrefined_tree.depth_at(pj);
254 double side_len = block_len_ / double(1<<parentLevel);
255 int dataIndex = unrefined_tree.get_data_index(pj, false);
256 alpha_cpy[newDataPtr] = float(max_alpha_int_ / side_len); // (float(-std::log(1.0f - p_init_) / side_len));
257 #if copy_parent_data_
258 mog_cpy[newDataPtr] = mog_[dataIndex];
259 #else
260 mog_cpy[newDataPtr] = uchar8((uchar) 0);
261 #endif
262 num_obs_cpy[newDataPtr]= ushort4((ushort) 0);
263
264 //update new data pointer
265 ++newDataPtr;
266 ++newInitCount;
267 ++cellsMoved;
268 }
269 }
270 return newInitCount;
271 }
272
273
free_space(int startPtr,int endPtr)274 int boxm2_refine_block_function::free_space(int startPtr, int endPtr)
275 {
276 int freeSpace = (startPtr >= endPtr)? startPtr-endPtr : data_len_ - (endPtr-startPtr);
277 return freeSpace;
278 }
279
280
281 ////////////////////////////////////////////////////////////////////////////////
282 //MAIN REFINE FUNCTION
283 ////////////////////////////////////////////////////////////////////////////////
boxm2_refine_block(const boxm2_scene_sptr & scene,boxm2_block * blk,std::vector<boxm2_data_base * > & datas,float prob_thresh,bool)284 void boxm2_refine_block( const boxm2_scene_sptr& scene,
285 boxm2_block* blk,
286 std::vector<boxm2_data_base*> & datas,
287 float prob_thresh,
288 bool /*is_random*/)
289 {
290 boxm2_refine_block_function refine_block;
291 refine_block.init_data(scene, blk, datas, prob_thresh);
292
293 refine_block.refine_deterministic(datas);
294 }
295