1 #include "vcg_mesh.h"
2 #include "ocme_impostor.h"
3 #include "ocme_extract.h"
4
5 /* UGLY: this dependency is because of the templates..it should be removed*/
6 #ifdef SIMPLE_DB
7 #include "../ooc_vector/io/ooc_chains.hpp"
8 #else
9 #include "../ooc_vector/io/ooc_chains_kcdb.hpp"
10 #endif
11
12 #include <vcg/complex/algorithms/pointcloud_normal.h>
13
14 extern unsigned int generic_bool;
15 int COff(const int & h);
16
ComputeImpostors()17 void OCME::ComputeImpostors( ){
18 for(CellsIterator ci = cells.begin(); ci != cells.end(); ++ci){
19 vcgMesh m;
20 this->ClearImpostor((*ci).second->key);
21 this->ExtractVerticesFromASingleCell((*ci).second->key,m);
22
23 vcg::tri::PointCloudNormal<vcgMesh>::Compute(m,vcg::tri::PointCloudNormal<vcgMesh>::Param(),0);
24 for(vcgMesh::VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
25 (*ci).second->impostor->AddSample((*vi).P(),(*vi).cN(),vcg::Color4b::Gray);
26 }
27 }
ImpostorsToMesh(vcgMesh & m)28 void OCME::ImpostorsToMesh(vcgMesh & m){
29
30 //{
31 // vcg::Point3f p,n;
32 // vcg::Point3<unsigned char> c;
33
34 // m.Clear();
35 // for(CellsIterator ci = cells.begin(); ci != cells.end();++ci){
36 // Impostor * imp = (*ci).second->impostor;
37 // vcgMesh::VertexIterator vi = vcg::tri::Allocator<vcgMesh>::AddVertices(m,imp->proxies.size());
38 // for( Impostor::PointCellIterator pi = imp->proxies.begin(); pi != imp->proxies .end(); ++pi,++vi ){
39 // imp->GetPointNormalColor(*pi,p,n,c);
40 // (*vi).N() = n;
41 // (*vi).C() = vcg::Color4b(c[0],c[1],c[2],255);
42 // (*vi).P() = p;
43 // }
44 // }
45 //}
46
47 {
48 vcg::Point3f p,n;
49 vcg::Point3<unsigned char> c;
50
51 m.Clear();
52 for(CellsIterator cc = cells.begin(); cc != cells.end();++cc){
53 Impostor * imp = (*cc).second->impostor;
54
55 std::map<unsigned short,vcg::Point3<char> >::iterator pi,ni;
56 std::map<unsigned short,vcg::Point3<unsigned char> >::iterator ci;
57
58 pi = imp->centroids.data.begin();
59 ni = imp->normals.data.begin();
60 ci = imp->colors.data.begin();
61
62 vcgMesh::VertexIterator vi = vcg::tri::Allocator<vcgMesh>::AddVertices(m,imp->centroids.data.size());
63
64 for(; pi != imp->centroids.data.end(); ++pi,++ni,++ci,++vi){
65
66 unsigned char i,j,k;
67 stdMatrix3Sparse<vcg::Point3<char>,8>::Index((*pi).first,i,j,k);
68 vcg::Point3<char> & a = (*pi).second;
69 p = vcg::Point3f(imp->C2F (a[0],i,0),imp->C2F (a[1],j,1),imp->C2F (a[2],k,2));
70 vcg::Point3<char> & b = (*ni).second;
71 n = vcg::Point3f(imp->C2F_01(b[0]),imp->C2F_01(b[1]),imp->C2F_01(b[2])).Normalize();
72
73 c = (*ci).second;
74
75 (*vi).N() = n;
76 (*vi).C() = vcg::Color4b(c[0],c[1],c[2],255);
77 (*vi).P() = p;
78 }
79 }
80 }
81 }
82
ClearImpostor(const CellKey & ck)83 bool OCME::ClearImpostor(const CellKey & ck){
84
85 std::vector<CellKey> chl;
86
87 Cell * c = GetCell(ck,false), * c_c;
88 if(!c)
89 return false; // c is a root
90
91 // first consider the data in this cell
92 this->Children(ck,chl);
93 float changed_occupancy = 0.f;
94
95 for(unsigned int cc = 0; cc < 8; ++cc){
96 if(c->impostor->non_empty_children & (1<<cc) ){
97 c_c = GetCell(chl[cc],false);
98 if(!c_c){
99 /* this cell was marked as a child at the last
100 impostor updates. If it is not there anymore
101 it means it has been deleted
102 */
103 c->impostor->non_empty_children &= ~(1<<cc); // update the children bit
104 changed_occupancy+=0.125f;
105 }else
106 if(c_c->generic_bool())// it is one of the touched cells
107 changed_occupancy+=0.125f;
108 }
109 }
110
111 if(changed_occupancy >= c->impostor->occupancy * 0.5 ){ // if at half of the 8 children must be updated then the parent must be updated too
112 if(!c->generic_bool()) c->generic_bool = FBool(&generic_bool);
113 c->generic_bool = true;
114 c->impostor->ClearDataCumulate();
115 c->impostor->data_occupancy = 0;
116 c->impostor->proxies.clear();
117 RemoveImpostor(c->key);
118 }
119
120 return c->generic_bool();
121 }
122
ClearImpostors(std::vector<CellKey> & fromCells)123 void OCME::ClearImpostors(std::vector<CellKey> & fromCells){
124 ++impostor_updated;
125 ++generic_bool; // used to mark the touched cells
126
127 std::vector<CellKey> cells_by_level [256];
128
129 // phase 1. fill the array of level with the cells and reset their occupancy
130 for(std::vector<CellKey>::iterator ci = fromCells.begin(); ci != fromCells.end(); ++ci){
131 Cell *c = GetCell(*ci,false);
132 c->generic_bool= FBool(&generic_bool);
133 c->impostor->ClearDataCumulate();
134 c->impostor->proxies.clear();
135 c->impostor->data_occupancy = 0;
136 RemoveImpostor(c->key);
137
138 CellKey & ck = (*ci);
139 cells_by_level[COff(ck.h)].push_back(ck);
140 }
141
142 unsigned int level = 0;
143 while( (level < 256) && cells_by_level[level].empty() ) {++level;} // find the lowest non empty level
144 if(level == 256) return; // if the database is empty return
145
146 // phase 2., bottom up clearing of the impostors
147 for( ; level < 255;++level ){
148 ::RemoveDuplicates(cells_by_level[level]);
149 for(unsigned int i = 0; i <cells_by_level[level].size();++i){
150 const CellKey & k = cells_by_level[level][i];
151 Cell* cell = GetCell( k,false);
152 assert(cell);
153 const CellKey & pk = Parent(k);
154 if(ClearImpostor(pk))
155 cells_by_level[level+1].push_back(pk);
156 }
157 }
158 }
159
FillSamples(std::vector<CellKey> & cs)160 void OCME::FillSamples(std::vector<CellKey> & cs){
161
162 for(unsigned int i = 0; i < cs.size(); ++i){
163 vcgMesh tmp;
164 Cell *c = GetCell(cs[i],false);
165 if(!c) continue;
166 // *** actually there is no need to do all the work.
167 // *** instead of ExtractContainedFacesFromASingleCell
168 // *** we should have an ad hoc function FillSamplesFromASingleCell
169 // *** TO DO.
170
171 this->ExtractContainedFacesFromASingleCell(cs[i],tmp);
172
173 /* clear the data that will be recomputed */
174 c->impostor->ClearDataCumulate();
175
176 bool hasColor = vcg::tri::HasPerVertexColor(tmp);
177
178 for(vcgMesh::FaceIterator fi = tmp.face.begin(); fi != tmp.face.end(); ++fi){
179 vcg::Point3f bary = vcg::Barycenter(*fi);
180 vcg::Point3f pp[3];
181 vcg::Point3f n = vcg::Normal(*fi).Normalize();
182 vcg::Color4b color = (hasColor)? (*fi).V(0)->cC() : vcg::Color4b::Gray;
183 c->impostor->AddSample(bary,n,color); // collect a sample for the impostor
184 }
185 }
186 }
187
UpdateImpostor(const CellKey & ck)188 bool OCME::UpdateImpostor(const CellKey & ck){
189 /*
190 This function assume that the samples are up-to-date and present
191 in the cell ck and its 8 children
192 */
193 std::vector<CellKey> chl;
194 vcgMesh m;
195 Cell * c = GetCell(ck,true), * c_c;
196 // first consider the data in this cell
197 std::vector<vcg::Point3f> smp;
198
199 c->impostor->InitDataCumulate(ck.BBox3f());
200 c->impostor->occupancy = 0;
201 c->impostor->ComputeDataOccupancy();
202
203 // then take the samples from all the children
204 const unsigned int & gridsize = c->impostor->Gridsize();
205 this->Children(ck,chl);
206 for(unsigned int cc = 0; cc < 8; ++cc){
207 c_c = GetCell(chl[cc],false);
208 if(c_c){
209
210 c->impostor->AddSamplesFromImpostor(c_c->impostor);
211
212 c->impostor->occupancy += c_c->impostor->occupancy * 0.125f; // == ../8
213 c->impostor->non_empty_children |= 1<<cc; // raise the corresponding bit
214 if(!c_c->rd->impostor_updated()){
215 c_c->rd->impostor_updated = FBool(&impostor_updated);
216 c_c->rd->impostor_updated = true;
217 }
218 }
219 }
220
221 /*
222 the occupancy of a cell as impostor is the maximum between the occupancy of its children and its own data occupancy
223 */
224 if(c->impostor->occupancy < c->impostor->data_occupancy/float(gridsize*gridsize*gridsize))
225 c->impostor->occupancy = c->impostor->data_occupancy/float(gridsize*gridsize*gridsize);
226
227
228 c->impostor->SetCentroids(false);
229 return (c->impostor->occupancy < 0.2f/float(gridsize*gridsize*gridsize));
230 }
231
232
233
BuildImpostorsHierarchy()234 void OCME::BuildImpostorsHierarchy(){BuildImpostorsHierarchy(this->cells);}
BuildImpostorsHierarchy(std::vector<CellKey> & fromCells)235 void OCME::BuildImpostorsHierarchy(std::vector<CellKey> & fromCells){
236 std::vector<Cell*> cs;
237 for(std::vector<CellKey>::iterator ci = fromCells.begin(); ci != fromCells.end(); ++ci) {
238 Cell * c = GetCell(*ci,false);
239 cs.push_back(c);
240 }
241 BuildImpostorsHierarchy(cs);
242 }
BuildImpostorsHierarchy(CellsContainer & fromCells)243 void OCME::BuildImpostorsHierarchy(CellsContainer & fromCells){
244 std::vector<Cell*> cs;
245 for(CellsIterator ci = fromCells.begin(); ci != fromCells.end(); ++ci) cs.push_back((*ci).second);
246 BuildImpostorsHierarchy(cs);
247 }
248
BuildImpostorsHierarchy(std::vector<Cell * > & fromCells)249 void OCME::BuildImpostorsHierarchy(std::vector<Cell*> & fromCells){
250 ++impostor_updated;
251 /*
252 The impostors are built bottom up, starting from the smallest cells (lowest h)
253 */
254 std::vector<CellKey> cells_by_level [256];
255
256 std::vector<Cell*>::iterator ci;
257
258
259 // phase 1. fill the array of level with the cells and compute centroid and data occupancy
260 for(ci = fromCells.begin(); ci != fromCells.end(); ++ci){
261 (*ci)->impostor->SetCentroids();
262 CellKey & ck = (*ci)->key;
263 cells_by_level[COff(ck.h)].push_back(ck);
264 }
265
266 unsigned int level = 0;
267 while( (level < 256) && cells_by_level[level].empty() ) {++level;} // find the lowest non empty level
268 if(level == 256) return; // if the database is empty return
269
270 // phase 2., bottom up updating of the impostors
271 std::vector<vcg::Point3f> smp;
272 // unsigned int tmpEnd = level+5;
273 for( ; level < 255;++level ){
274
275 ::RemoveDuplicates(cells_by_level[level]);
276 // build of the impostors of this level
277 for(unsigned int i = 0; i <cells_by_level[level].size();++i)
278 GetCell( cells_by_level[level][i],false)->impostor->Create( this,cells_by_level[level][i]);
279 for(unsigned int i = 0; i <cells_by_level[level].size();++i)
280 GetCell( cells_by_level[level][i],false)->impostor->ClearDataCumulate();
281
282 for(unsigned int i = 0; i <cells_by_level[level].size();++i){
283 const CellKey & k = cells_by_level[level][i];
284 Cell* cell = GetCell( k,false);
285 assert(cell);
286 if(!cell->rd->impostor_updated()){
287 const CellKey & pk = Parent(k);
288 // to_insert = (GetCell( pk,false)==NULL);
289 if(!UpdateImpostor(pk) /*&& to_insert*/)
290 cells_by_level[level+1].push_back(pk);
291 else
292 octree_roots.push_back(GetCell(pk));
293 }
294 }
295 }
296 }
297
298
299
UpdateImpostorPartial(const CellKey & ck)300 bool OCME::UpdateImpostorPartial(const CellKey & ck){
301 /*
302 This function assume that the samples are up-to-date and present
303 in the cell ck and its 8 children
304 */
305 std::vector<CellKey> chl;
306 vcgMesh m;
307 Cell * c = GetCell(ck,true), * c_c;
308 // first consider the data in this cell
309 std::vector<vcg::Point3f> smp;
310
311 c->impostor->InitDataCumulate(ck.BBox3f());
312 c->impostor->occupancy = 0;
313 c->impostor->ComputeDataOccupancy();
314
315 // then take the samples from all the children
316 const unsigned int & gridsize = c->impostor->Gridsize();
317 this->Children(ck,chl);
318 for(unsigned int cc = 0; cc < 8; ++cc){
319 c_c = GetCell(chl[cc],false);
320 if(c_c){
321
322 c->impostor->AddSamplesFromImpostor(c_c->impostor);
323
324 c->impostor->occupancy += c_c->impostor->occupancy * 0.125f; // == ../8
325 c->impostor->non_empty_children |= 1<<cc; // raise the corresponding bit
326 if(!c_c->rd->impostor_updated()){
327 c_c->rd->impostor_updated = FBool(&impostor_updated);
328 c_c->rd->impostor_updated = true;
329 }
330 }
331 }
332
333 /*
334 the occupancy of a cell as impostor is the maximum between the occupancy of its children and its own data occupancy
335 */
336 if(c->impostor->occupancy < c->impostor->data_occupancy/float(gridsize*gridsize*gridsize))
337 c->impostor->occupancy = c->impostor->data_occupancy/float(gridsize*gridsize*gridsize);
338
339
340 c->impostor->SetCentroids(false);
341 return (c->impostor->occupancy < 0.2f/float(gridsize*gridsize*gridsize));
342 }
BuildImpostorsHierarchyPartial(std::vector<CellKey> & fromCells)343 void OCME::BuildImpostorsHierarchyPartial(std::vector<CellKey> & fromCells){
344 std::vector<Cell*> cs;
345 for(std::vector<CellKey>::iterator ci = fromCells.begin(); ci != fromCells.end(); ++ci) {
346 Cell * c = GetCell(*ci,false);
347 cs.push_back(c);
348 }
349 BuildImpostorsHierarchyPartial(cs);
350 }
BuildImpostorsHierarchyPartial(std::vector<Cell * > & fromCells)351 void OCME::BuildImpostorsHierarchyPartial(std::vector<Cell*> & fromCells){
352 ++impostor_updated;
353 /*
354 The impostors are built bottom up, starting from the smallest cells (lowest h)
355 */
356 std::vector<CellKey> cells_by_level [256];
357 std::vector<Cell*>::iterator ci;
358
359 // phase 1. fill the array of level with the cells and compute centroid and data occupancy
360 // This assume the samples per cells have already been collected
361 for(ci = fromCells.begin(); ci != fromCells.end(); ++ci){
362 (*ci)->impostor->SetCentroids();
363 CellKey & ck = (*ci)->key;
364 cells_by_level[COff(ck.h)].push_back(ck);
365 }
366
367 unsigned int level = 0;
368 while( (level < 256) && cells_by_level[level].empty() ) {++level;} // find the lowest non empty level
369 if(level == 256) return; // if empty return
370
371 // phase 2., bottom up updating of the impostors
372 //bool to_insert = false;
373
374 for( ; level < 255;++level ){
375 ::RemoveDuplicates(cells_by_level[level]);
376 // build of the impostors of this level
377 for(unsigned int i = 0; i <cells_by_level[level].size();++i)
378 GetCell( cells_by_level[level][i],false)->impostor->Create( this,cells_by_level[level][i]);
379
380 for(unsigned int i = 0; i <cells_by_level[level].size();++i){
381 const CellKey & k = cells_by_level[level][i];
382 Cell* cell = GetCell( k,false);
383 assert(cell);
384 if(!cell->rd->impostor_updated()){
385 const CellKey & pk = Parent(k);
386
387 if(!UpdateImpostorPartial(pk) )
388 cells_by_level[level+1].push_back(pk);
389 else
390 octree_roots.push_back(GetCell(pk)); // to be redone
391 }
392 }
393 }
394 }
395