?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
changed: gcc8 base update
[opensg.git] / Source / System / NodeCores / Drawables / Particles / OSGParticleBSP.cpp
blob6a8dbe92c56ea4b79b4af9184cb69074237d6e18
1 /*---------------------------------------------------------------------------*\
2 * OpenSG *
3 * *
4 * *
5 * Copyright (C) 2000-2002 by the OpenSG Forum *
6 * *
7 * www.opensg.org *
8 * *
9 * contact: dirk@opensg.org, gerrit.voss@vossg.org, jbehr@zgdv.de *
10 * *
11 \*---------------------------------------------------------------------------*/
12 /*---------------------------------------------------------------------------*\
13 * License *
14 * *
15 * This library is free software; you can redistribute it and/or modify it *
16 * under the terms of the GNU Library General Public License as published *
17 * by the Free Software Foundation, version 2. *
18 * *
19 * This library is distributed in the hope that it will be useful, but *
20 * WITHOUT ANY WARRANTY; without even the implied warranty of *
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
22 * Library General Public License for more details. *
23 * *
24 * You should have received a copy of the GNU Library General Public *
25 * License along with this library; if not, write to the Free Software *
26 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. *
27 * *
28 \*---------------------------------------------------------------------------*/
29 /*---------------------------------------------------------------------------*\
30 * Changes *
31 * *
32 * *
33 * *
34 * *
35 * *
36 * *
37 \*---------------------------------------------------------------------------*/
38
39 //---------------------------------------------------------------------------
40 // Includes
41 //---------------------------------------------------------------------------
42
43 #include <cstdlib>
44 #include <cstdio>
45
46 #include "OSGConfig.h"
47
48 #include "OSGBaseFunctions.h"
49
50 #include "OSGNode.h"
51 #include "OSGParticleBSP.h"
52
53 #include "OSGParticles.h"
54
55 OSG_USING_NAMESPACE
56
57 /*! \class OSG::ParticleBSPTree
58
59 A very simple BSP tree, optimized for particle sorting.
60 */
61
62 /*! \class OSG::ParticleBSPNode
63
64 A node of the ParticleBSPTree.
65 */
66
67 /*----------------------- constructors & destructors ----------------------*/
68
69 ParticleBSPNode::ParticleBSPNode(void) :
70 _axis()
71 {
72 }
73
74 ParticleBSPNode::ParticleBSPNode(const ParticleBSPNode &source) :
75 _axis(source._axis)
76 {
77 if(isLeaf())
78 {
79 _value = source._value;
80 }
81 else
82 {
83 _splitvalue = source._splitvalue;
84 }
85 }
86
87 ParticleBSPNode::ParticleBSPNode(UInt32 value) :
88 _axis(Leaf),
89 _value(value)
90 {
91 }
92
93 ParticleBSPNode::ParticleBSPNode(UInt8 axis, Real32 splitvalue) :
94 _axis(axis),
95 _splitvalue(splitvalue)
96 {
97 }
98
99 ParticleBSPNode::~ParticleBSPNode(void)
100 {
101 }
102
103 /*---------------------------------- output -------------------------------*/
104
105 void ParticleBSPNode::dump( UInt32 OSG_CHECK_ARG(uiIndent),
106 const BitVector OSG_CHECK_ARG(bvFlags )) const
107 {
108 static const char *axisname = "XYZL";
109
110 Real32 v = isLeaf()?_value:_splitvalue;
111
112 PLOG << "(" << axisname[_axis] << " " << v << ")";
113 }
114
115
116 /*-------------------------------------------------------------------------*/
117 /*---------------------------- BSP Tree -----------------------------------*/
118 /*-------------------------------------------------------------------------*/
119
120 /*----------------------- constructors & destructors ----------------------*/
121
122 ParticleBSPTree::ParticleBSPTree(void) :
123 _tree()
124 {
125 }
126
127 ParticleBSPTree::~ParticleBSPTree(void)
128 {
129 }
130
131 /*---------------------------------- output -------------------------------*/
132
133 void ParticleBSPTree::dump( UInt32 OSG_CHECK_ARG(uiIndent),
134 const BitVector OSG_CHECK_ARG(bvFlags )) const
135 {
136 PLOG << "ParticleBSPTree(";
137
138 if(!_tree.empty())
139 {
140 for(std::vector<ParticleBSPNode>::const_iterator i = _tree.begin() + 1;
141 i != _tree.end(); ++i )
142 {
143 i->dump();
144 }
145 }
146
147 PLOG << ")" << std::endl;
148 }
149
150 #if 0
151 void ParticleBSPTree::putToString(std::string &outVal) const
152 {
153 outVal.assign(TypeTraits<UInt32>::putToString(_tree.size()));
154 outVal.append(";");
155
156 if(! _tree.empty())
157 {
158 for(std::vector<ParticleBSPNode>::const_iterator i = _tree.begin() + 1;
159 i != _tree.end(); ++i )
160 {
161 outVal.append(TypeTraits<UInt8>::putToString(i->getAxis()));
162 outVal.append(":");
163 if(i->isLeaf())
164 {
165 outVal.append(TypeTraits<Int32>::putToString(i->getValue()));
166 }
167 else
168 {
169 outVal.append(TypeTraits<Real32>::putToString(
170 i->getSplitValue()));
171 }
172 outVal.append(";");
173 }
174 }
175 }
176
177 bool ParticleBSPTree::getFromString(const Char8 *&inVal)
178 {
179 UInt32 size = TypeTraits<UInt32>::getFromString(inVal);
180
181 const Char8 *c = strchr(inVal, ';');
182
183 if(!c)
184 return false;
185 c++;
186
187 _tree.resize(size);
188
189 for(UInt32 i = 1; i < size; ++i)
190 {
191 UInt8 axis = TypeTraits<UInt8>::getFromString(c);
192 c = strchr(c, ':');
193 if(!c)
194 return false;
195 c++;
196
197 if(axis == ParticleBSPNode::Leaf)
198 {
199 Int32 value = TypeTraits<Int32>::getFromString(c);
200 _tree[i].setValue(value);
201 }
202 else
203 {
204 Real32 value = TypeTraits<Real32>::getFromString(c);
205 _tree[i].setSplit(axis, value);
206 }
207 c = strchr(c, ';');
208 if(!c)
209 return false;
210 c++;
211 }
212
213 return true;
214 }
215 #endif
216
217 SizeT ParticleBSPTree::getBinSize(void) const
218 {
219 return sizeof(UInt32) // num elements
220 + (sizeof(UInt8)+sizeof(UInt32)) * _tree.size();
221 }
222
223 void ParticleBSPTree::copyToBin(BinaryDataHandler &pMem) const
224 {
225 UInt8 axis;
226 Int32 value;
227 Real32 splitvalue;
228 UInt32 i;
229 UInt32 size = UInt32(_tree.size());
230 pMem.putValue(size);
231
232 for(i=0;i<size;++i)
233 {
234 axis=_tree[i].getAxis();
235 pMem.putValue(axis);
236 if(axis==ParticleBSPNode::Leaf)
237 {
238 value=_tree[i].getValue();
239 pMem.putValue(value);
240 }
241 else
242 {
243 splitvalue=_tree[i].getSplitValue();
244 pMem.putValue(splitvalue);
245 }
246 }
247 }
248
249 void ParticleBSPTree::copyFromBin(BinaryDataHandler &pMem)
250 {
251 UInt8 axis;
252 Int32 value;
253 Real32 splitvalue;
254 UInt32 i;
255 UInt32 size;
256 pMem.getValue(size);
257 _tree.resize(size);
258
259 for(i=0;i<size;++i)
260 {
261 pMem.getValue(axis);
262 if(axis==ParticleBSPNode::Leaf)
263 {
264 pMem.getValue(value);
265 _tree[i].setValue(value);
266 }
267 else
268 {
269 pMem.getValue(splitvalue);
270 _tree[i].setSplit(axis, Real32(value));
271 }
272 }
273 }
274
275 bool ParticleBSPTree::operator ==(const ParticleBSPTree &source) const
276 {
277 return false;
278 }
279
280 /*-------------------------------- traversal ------------------------------*/
281
282 Int32 *ParticleBSPTree::traverse(const Pnt3f &refPoint, UInt32 &length,
283 Int32 *order) const
284 {
285 if(_tree.empty())
286 return NULL;
287
288 if(order == NULL)
289 {
290 order = new Int32 [length];
291 }
292
293 length = doTraverse(refPoint,1,0,order);
294
295 return order;
296 }
297
298 UInt32 ParticleBSPTree::doTraverse(const Pnt3f &refPoint, UInt32 index,
299 UInt32 length, Int32 *order) const
300 {
301 const ParticleBSPNode *n = &_tree[index];
302
303 if(n->isLeaf())
304 {
305 order[length] = n->getValue();
306 return ++length;
307 }
308 else
309 {
310 if(refPoint[n->getAxis()] > n->getSplitValue())
311 {
312 length = doTraverse(refPoint, index * 2 , length, order);
313 length = doTraverse(refPoint, index * 2 + 1, length, order);
314 }
315 else
316 {
317 length = doTraverse(refPoint, index * 2 + 1, length, order);
318 length = doTraverse(refPoint, index * 2 , length, order);
319 }
320 }
321 return length;
322 }
323
324 Int32 *ParticleBSPTree::traverse(const Vec3f &refVec, UInt32 &length,
325 Int32 *order) const
326 {
327 if(order == NULL)
328 {
329 order = new Int32 [length];
330 }
331
332 length = doTraverse(refVec,1,0,order);
333
334 return order;
335 }
336
337 UInt32 ParticleBSPTree::doTraverse(const Vec3f &refVec, UInt32 index,
338 UInt32 length, Int32 *order) const
339 {
340 const ParticleBSPNode *n = &_tree[index];
341
342 if(n->isLeaf())
343 {
344 order[length] = n->getValue();
345 return ++length;
346 }
347 else
348 {
349 if(refVec[n->getAxis()] > 0.f)
350 {
351 length = doTraverse(refVec, index * 2 , length, order);
352 length = doTraverse(refVec, index * 2 + 1, length, order);
353 }
354 else
355 {
356 length = doTraverse(refVec, index * 2 + 1, length, order);
357 length = doTraverse(refVec, index * 2 , length, order);
358 }
359 }
360 return length;
361 }
362
363 /*--------------------------------- creation ------------------------------*/
364
365 void ParticleBSPTree::build(Particles *core)
366 {
367 _tree.clear();
368
369 if(core == NULL)
370 {
371 FWARNING(("ParticleBSP::build: no core!!\n"));
372 return;
373 }
374
375 GeoVectorProperty * const pos = core->getPositions();
376
377 if(pos == NULL)
378 return;
379
380 const MFInt32 *indices = core->getMFIndices();
381
382 // 1. create list for particles
383
384 std::vector<Int32> order;
385 order.reserve(pos->size());
386
387 for(UInt32 i = 0; i < pos->size32(); ++i )
388 {
389 if(indices->size() == pos->size())
390 {
391 order.push_back((*indices)[i]);
392 }
393 else
394 {
395 order.push_back(i);
396 }
397 }
398
399 // reserve mem for tree
400
401 _tree.resize(osgNextPower2(order.size()) * 2);
402
403 // 2. recursively build the tree
404
405 UInt32 nnodes = doBuild(order.begin(), order.end(), 1, pos);
406
407 // 3. remove the unneeded elements from the end
408
409 if(nnodes < _tree.size())
410 _tree.erase( _tree.begin() + nnodes, _tree.end());
411
412 // done
413 }
414
415 /*! \ingroup GrpDrawablesParticlesHelpers
416 \nohierarchy
417 */
418
419 struct ParticleCompare : public std::binary_function<Int32, Int32, bool>
420 {
421 ParticleCompare(GeoVectorProperty *pos, UInt8 axis) :
422 _pos(pos),
423 _axis(axis)
424 {}
425
426 bool operator()(Int32 x, Int32 y)
427 {
428 Pnt3f px,py;
429 _pos->getValue(px, x);
430 _pos->getValue(py, y);
431
432 return px[_axis] < py[_axis];
433 }
434
435 GeoVectorProperty *_pos;
436 UInt8 _axis;
437 };
438
439 UInt32 ParticleBSPTree::doBuild(std::vector<Int32>::iterator begin,
440 std::vector<Int32>::iterator end,
441 UInt32 nodeindex,
442 GeoVectorProperty *pos)
443 {
444 // reached a leaf?
445
446 if(begin + 1 == end)
447 {
448 _tree[nodeindex].setValue(*begin);
449 return nodeindex + 1;
450 }
451
452 // find the bounding volume of the group
453
454 BoxVolume b;
455 Pnt3f p;
456
457 b.setEmpty();
458
459 for(std::vector<Int32>::iterator i = begin; i != end; ++i)
460 {
461 pos->getValue(p,*i);
462 b.extendBy(p);
463 }
464
465 // find the axis with the longest extension
466
467 Vec3f d = b.getMax() - b.getMin();
468
469 UInt8 axis = ParticleBSPNode::X;
470 Real32 maxval = d[0];
471
472 if(d[1] > maxval)
473 {
474 axis = ParticleBSPNode::Y;
475 maxval = d[1];
476 }
477 if(d[2] > maxval)
478 {
479 axis = ParticleBSPNode::Z;
480 maxval = d[2];
481 }
482
483 // sort in that axis
484 ParticleCompare comp(pos, axis);
485
486 std::sort(begin,end,comp);
487
488 // find median value
489 std::vector<Int32>::iterator mid = begin + (end - begin) / 2;
490
491 Pnt3f p2;
492 pos->getValue(p ,*mid);
493 pos->getValue(p2,(*mid)-1);
494 _tree[nodeindex].setSplit(axis, (p[axis] + p2[axis]) / 2.f);
495
496 return osgMax( doBuild(begin, mid, nodeindex * 2 , pos),
497 doBuild( mid, end, nodeindex * 2 + 1, pos) );
498 }
499
500
501 void ParticleBSPTree::destroy()
502 {
503 _tree.clear();
504 }
505
506
507 #include "OSGSField.ins"
508 #include "OSGMField.ins"
509
510 OSG_BEGIN_NAMESPACE
511
512 /*-------------------------- field instantiations -------------------------*/
513
514 DataType FieldTraits<ParticleBSPTree>::_type("ParticleBSPTree",
515 "TypeRoot");
516
517 OSG_FIELDTRAITS_GETTYPE(ParticleBSPTree)
518
519 OSG_FIELD_DLLEXPORT_DEF1(SField, ParticleBSPTree)
520
521 OSG_END_NAMESPACE
522