BSPSortMethod.cpp
Go to the documentation of this file.
1 /*
2  This file is part of the VRender library.
3  Copyright (C) 2005 Cyril Soler (Cyril.Soler@imag.fr)
4  Version 1.0.0, released on June 27, 2005.
5 
6  http://artis.imag.fr/Members/Cyril.Soler/VRender
7 
8  VRender is free software; you can redistribute it and/or modify
9  it under the terms of the GNU General Public License as published by
10  the Free Software Foundation; either version 2 of the License, or
11  (at your option) any later version.
12 
13  VRender is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with VRender; if not, write to the Free Software Foundation, Inc.,
20  51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
21 */
22 
23 /****************************************************************************
24 
25  Copyright (C) 2002-2013 Gilles Debunne. All rights reserved.
26 
27  This file is part of the QGLViewer library version 2.4.0.
28 
29  http://www.libqglviewer.com - contact@libqglviewer.com
30 
31  This file may be used under the terms of the GNU General Public License
32  versions 2.0 or 3.0 as published by the Free Software Foundation and
33  appearing in the LICENSE file included in the packaging of this file.
34  In addition, as a special exception, Gilles Debunne gives you certain
35  additional rights, described in the file GPL_EXCEPTION in this package.
36 
37  libQGLViewer uses dual licensing. Commercial/proprietary software must
38  purchase a libQGLViewer Commercial License.
39 
40  This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
41  WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
42 
43 *****************************************************************************/
44 
45 #include "VRender.h"
46 #include "Primitive.h"
47 #include "SortMethod.h"
48 #include "math.h" // fabs
49 
50 using namespace vrender;
51 using namespace std;
52 
53 double EGALITY_EPS = 0.0001;
54 double LINE_EGALITY_EPS = 0.0001;
55 
56 typedef enum { BSP_CROSS_PLANE, BSP_UPPER, BSP_LOWER } BSPPosition;
57 
58 class BSPNode;
59 
60 class BSPTree
61 {
62  public:
63  BSPTree();
64  ~BSPTree();
65 
66  void insert(Polygone *);
67  void insert(Segment *);
68  void insert(Point *);
69 
70  void recursFillPrimitiveArray(vector<PtrPrimitive>&) const;
71  private:
72  BSPNode *_root;
73  vector<Segment *> _segments; // these are for storing segments and points when _root is null
74  vector<Point *> _points;
75 };
76 
77 void BSPSortMethod::sortPrimitives(std::vector<PtrPrimitive>& primitive_tab,VRenderParams& vparams)
78 {
79  // 1 - build BSP using polygons only
80 
81  BSPTree tree;
82  Polygone *P;
83 
84  unsigned int N = primitive_tab.size()/200 +1;
85  int nbinserted = 0;
86 
87  vector<PtrPrimitive> segments_and_points; // Store segments and points for pass 2, because polygons are deleted
88  // by the insertion and can not be dynamic_casted anymore.
89  for(unsigned int i=0;i<primitive_tab.size();++i,++nbinserted)
90  {
91  if((P = dynamic_cast<Polygone *>(primitive_tab[i])) != NULL)
92  tree.insert(P);
93  else
94  segments_and_points.push_back(primitive_tab[i]);
95 
96  if(nbinserted%N==0)
97  vparams.progress(nbinserted/(float)primitive_tab.size(), QGLViewer::tr("BSP Construction"));
98  }
99 
100  // 2 - insert points and segments into the BSP
101 
102  Segment *S;
103  Point *p;
104 
105  for(unsigned int j=0;j<segments_and_points.size();++j,++nbinserted)
106  {
107  if((S = dynamic_cast<Segment *>(segments_and_points[j])) != NULL)
108  tree.insert(S);
109  else if((p = dynamic_cast<Point *>(segments_and_points[j])) != NULL)
110  tree.insert(p);
111 
112  if(nbinserted%N==0)
113  vparams.progress(nbinserted/(float)primitive_tab.size(), QGLViewer::tr("BSP Construction"));
114  }
115 
116  // 3 - refill the array with the content of the BSP
117 
118  primitive_tab.resize(0);
119  tree.recursFillPrimitiveArray(primitive_tab);
120 }
121 
123 
124 class BSPNode
125 {
126  public:
127  BSPNode(Polygone *);
128  ~BSPNode();
129 
130  void recursFillPrimitiveArray(vector<PtrPrimitive>&) const;
131 
132  void insert(Polygone *);
133  void insert(Segment *);
134  void insert(Point *);
135 
136  private:
137  double a,b,c,d;
138 
139  BSPNode *fils_moins;
140  BSPNode *fils_plus;
141 
142  vector<Segment *> seg_plus;
143  vector<Segment *> seg_moins;
144 
145  vector<Point *> pts_plus;
146  vector<Point *> pts_moins;
147 
148  Polygone *polygone;
149 
150  void Classify(Polygone *, Polygone * &, Polygone * &);
151  void Classify(Segment *, Segment * &, Segment * &);
152  int Classify(Point *);
153 
154  void initEquation(const Polygone *P,double & a, double & b, double & c, double & d);
155 };
156 
157 BSPTree::BSPTree()
158 {
159  _root = NULL;
160 }
161 
162 BSPTree::~BSPTree()
163 {
164  delete _root;
165 }
166 
167 void BSPTree::insert(Point *P) { if(_root == NULL) _points.push_back(P) ; else _root->insert(P); }
168 void BSPTree::insert(Segment *S) { if(_root == NULL) _segments.push_back(S); else _root->insert(S); }
169 void BSPTree::insert(Polygone *P){ if(_root == NULL) _root = new BSPNode(P); else _root->insert(P); }
170 
171 void BSPTree::recursFillPrimitiveArray(vector<PtrPrimitive>& tab) const
172 {
173  if(_root != NULL) _root->recursFillPrimitiveArray(tab);
174 
175  for(unsigned int i=0;i<_points.size();++i) tab.push_back(_points[i]);
176  for(unsigned int j=0;j<_segments.size();++j) tab.push_back(_segments[j]);
177 }
178 
179 //----------------------------------------------------------------------------//
180 
181 BSPNode::~BSPNode()
182 {
183  delete fils_moins;
184  delete fils_plus;
185 }
186 
187 int BSPNode::Classify(Point *P)
188 {
189  double Z = P->sommet3DColor(0).x() * a + P->sommet3DColor(0).y() * b + P->sommet3DColor(0).z() * c - d;
190 
191  if(Z > EGALITY_EPS)
192  return 1;
193  else
194  return -1;
195 }
196 
197 void BSPNode::Classify(Segment *S, Segment * & moins_, Segment * & plus_)
198 {
199  double Z1 = S->sommet3DColor(0).x() * a + S->sommet3DColor(0).y() * b + S->sommet3DColor(0).z() * c - d;
200  double Z2 = S->sommet3DColor(1).x() * a + S->sommet3DColor(1).y() * b + S->sommet3DColor(1).z() * c - d;
201 
202  int s1, s2;
203 
204  if(Z1 < -LINE_EGALITY_EPS)
205  s1 = -1;
206  else if(Z1 > EGALITY_EPS)
207  s1 = 1;
208  else
209  s1 = 0;
210 
211  if(Z2 < -LINE_EGALITY_EPS)
212  s2 = -1;
213  else if(Z2 > EGALITY_EPS)
214  s2 = 1;
215  else
216  s2 = 0;
217 
218  if(s1 == -s2)
219  {
220  if(s1 == 0)
221  {
222  moins_ = S;
223  plus_ = NULL;
224  return;
225  }
226  else
227  {
228  double t = fabs(Z1/(Z2 - Z1));
229 
230  if((t < 0.0)||(t > 1.0))
231  {
232  if(t > 1.0) t = 0.999;
233  if(t < 0.0) t = 0.001;
234  }
235 
236  Feedback3DColor newVertex((1-t)*S->sommet3DColor(0) + t*S->sommet3DColor(1));
237 
238  if(s1 > 0)
239  {
240  plus_ = new Segment(S->sommet3DColor(0), newVertex);
241  moins_ = new Segment(newVertex, S->sommet3DColor(1));
242  }
243  else
244  {
245  plus_ = new Segment(newVertex, S->sommet3DColor(1));
246  moins_ = new Segment(S->sommet3DColor(0), newVertex);
247  }
248 
249  delete S;
250  return;
251  }
252  }
253  else if(s1 == s2)
254  {
255  if(s1 == -1)
256  {
257  moins_ = S;
258  plus_ = NULL;
259  return;
260  }
261  else
262  {
263  moins_ = NULL;
264  plus_ = S;
265  return;
266  }
267  }
268  else if(s1 == 0)
269  {
270  if(s2 > 0)
271  {
272  moins_ = NULL;
273  plus_ = S;
274  return;
275  }
276  else
277  {
278  moins_ = S;
279  plus_ = NULL;
280  return;
281  }
282  }
283  else if(s2 == 0)
284  {
285  if(s1 > 0)
286  {
287  moins_ = NULL;
288  plus_ = S;
289  return;
290  }
291  else
292  {
293  moins_ = S;
294  plus_ = NULL;
295  return;
296  }
297  }
298  //else
299  //printf("BSPNode::Classify: unexpected classification case !!\n");
300 }
301 
302 void BSPNode::Classify(Polygone *P, Polygone * & moins_, Polygone * & plus_)
303 {
304  static int Signs[100];
305  static double Zvals[100];
306 
307  moins_ = NULL;
308  plus_ = NULL;
309 
310  if(P == NULL)
311  {
312  //printf("BSPNode::Classify: Error. Null polygon.\n");
313  return;
314  }
315 
316  int n = P->nbVertices();
317 
318  int Smin = 1;
319  int Smax = -1;
320 
321  // On classe les sommets en fonction de leur signe
322 
323  for(int i=0;i<n;i++)
324  {
325  double Z = P->vertex(i).x() * a + P->vertex(i).y() * b + P->vertex(i).z() * c - d;
326 
327  if(Z < -EGALITY_EPS)
328  Signs[i] = -1;
329  else if(Z > EGALITY_EPS)
330  Signs[i] = 1;
331  else
332  Signs[i] = 0;
333 
334  Zvals[i] = Z;
335 
336  if(Smin > Signs[i]) Smin = Signs[i];
337  if(Smax < Signs[i]) Smax = Signs[i];
338  }
339 
340  // Polygone inclus dans le plan
341 
342  if((Smin == 0)&&(Smax == 0))
343  {
344  moins_ = P;
345  plus_ = NULL;
346  return;
347  }
348 
349  // Polygone tout positif
350 
351  if(Smin == 1)
352  {
353  plus_ = P;
354  moins_ = NULL;
355  return;
356  }
357 
358  // Polygone tout negatif
359 
360  if(Smax == -1)
361  {
362  plus_ = NULL;
363  moins_ = P;
364  return;
365  }
366 
367  if((Smin == -1)&&(Smax == 0))
368  {
369  plus_ = NULL;
370  moins_ = P;
371  return;
372  }
373 
374  if((Smin == 0)&&(Smax == 1))
375  {
376  plus_ = P;
377  moins_ = NULL;
378  return;
379  }
380 
381  // Reste le cas Smin = -1 et Smax = 1. Il faut couper
382 
383  vector<Feedback3DColor> Ps;
384  vector<Feedback3DColor> Ms;
385 
386  // On teste la coherence des signes.
387 
388  int nZero = 0;
389  int nconsZero = 0;
390 
391  for(int j=0;j<n;j++)
392  {
393  if(Signs[j] == 0)
394  {
395  nZero++;
396 
397  if(Signs[(j+1)%n] == 0)
398  nconsZero++;
399  }
400  }
401 
402  if((nZero > 2)||(nconsZero > 0))
403  {
404  // Ils y a des imprecisions numeriques dues au fait que le poly estpres du plan.
405 
406  moins_ = P;
407  plus_ = NULL;
408  return;
409  }
410 
411  int dep=0;
412 
413  while(Signs[dep] == 0) dep++;
414 
415  int prev_sign = Signs[dep];
416 
417  for(int k=1;k<=n;k++)
418  {
419  int sign = Signs[(k+dep)%n];
420 
421  if(sign == prev_sign)
422  {
423  if(sign == 1)
424  Ps.push_back(P->sommet3DColor(k+dep));
425 
426  if(sign == -1)
427  Ms.push_back(P->sommet3DColor(k+dep));
428  }
429  else if(sign == -prev_sign)
430  {
431  // Il faut effectuer le calcul en utilisant les memes valeurs que pour le calcul des signes,
432  // sinon on risque des incoherences dues aux imprecisions numeriques.
433 
434  double Z1 = Zvals[(k+dep-1)%n];
435  double Z2 = Zvals[(k+dep)%n];
436 
437  double t = fabs(Z1/(Z2 - Z1));
438 
439  if((t < 0.0)||(t > 1.0))
440  {
441  if(t > 1.0) t = 0.999;
442  if(t < 0.0) t = 0.001;
443  }
444 
445  Feedback3DColor newVertex((1-t)*P->sommet3DColor(k+dep-1) + t*P->sommet3DColor(k+dep));
446 
447  Ps.push_back(newVertex);
448  Ms.push_back(newVertex);
449 
450  if(sign == 1)
451  Ps.push_back(P->sommet3DColor(k+dep));
452 
453  if(sign == -1)
454  Ms.push_back(P->sommet3DColor(k+dep));
455 
456  prev_sign = sign;
457  } // prev_sign != 0 donc necessairement sign = 0. Le sommet tombe dans le plan
458  else
459  {
460  Feedback3DColor newVertex = P->sommet3DColor(k+dep);
461 
462  Ps.push_back(newVertex);
463  Ms.push_back(newVertex);
464 
465  prev_sign = -prev_sign;
466  }
467  }
468 
469  //if((Ps.size() > 100)||(Ms.size() > 100))
470  //printf("BSPNode::Classify: Error. nPs = %d, nMs = %d.\n",int(Ps.size()),int(Ms.size()));
471 
472  //if(Ps.size() < 3)
473  //printf("BSPNode::Classify: Error. nPs = %d.\n",int(Ps.size()));
474 
475  //if(Ms.size() < 3)
476  //printf("BSPNode::Classify: Error. nMs = %d.\n",int(Ms.size()));
477 
478  // Les polygones sont convexes, car OpenGL les clip lui-meme.
479 
480  // Si les parents ne sont pas degeneres, plus et moins ne le
481  // sont pas non plus.
482 
483  plus_ = new Polygone(Ps);
484  moins_ = new Polygone(Ms);
485 
486  delete P;
487 }
488 
489 void BSPNode::insert(Polygone *P)
490 {
491  Polygone *side_plus = NULL, *side_moins = NULL;
492 
493  // 1 - Check on which size the polygon is, possibly split.
494 
495  Classify(P,side_moins,side_plus);
496 
497  // 2 - insert polygons
498 
499  if(side_plus != NULL) {
500  if(fils_plus == NULL)
501  fils_plus = new BSPNode(side_plus);
502  else
503  fils_plus->insert(side_plus);
504  }
505 
506  if(side_moins != NULL) {
507  if(fils_moins == NULL)
508  fils_moins = new BSPNode(side_moins);
509  else
510  fils_moins->insert(side_moins);
511  }
512 }
513 
514 void BSPNode::recursFillPrimitiveArray(vector<PtrPrimitive>& primitive_tab) const
515 {
516  if(fils_plus != NULL)
517  fils_plus->recursFillPrimitiveArray(primitive_tab);
518 
519  for(unsigned int i=0;i<seg_plus.size();++i)
520  primitive_tab.push_back(seg_plus[i]);
521  for(unsigned int j=0;j<pts_plus.size();++j)
522  primitive_tab.push_back(pts_plus[j]);
523 
524  if(polygone != NULL)
525  primitive_tab.push_back(polygone);
526 
527  if(fils_moins != NULL)
528  fils_moins->recursFillPrimitiveArray(primitive_tab);
529 
530  for(unsigned int i2=0;i2<seg_moins.size();++i2)
531  primitive_tab.push_back(seg_moins[i2]);
532  for(unsigned int j2=0;j2<pts_moins.size();++j2)
533  primitive_tab.push_back(pts_moins[j2]);
534 }
535 
536 void BSPNode::insert(Point *P)
537 {
538  int res = Classify(P);
539 
540  if(res == -1) {
541  if(fils_moins == NULL)
542  pts_moins.push_back(P);
543  else
544  fils_moins->insert(P);
545  }
546 
547  if(res == 1) {
548  if(fils_plus == NULL)
549  pts_plus.push_back(P);
550  else
551  fils_plus->insert(P);
552  }
553 }
554 
555 void BSPNode::insert(Segment *S)
556 {
557  Segment *side_plus = NULL, *side_moins = NULL;
558 
559  Classify(S,side_moins,side_plus);
560 
561  if(side_plus != NULL) {
562  if(fils_plus == NULL)
563  seg_plus.push_back(side_plus);
564  else
565  fils_plus->insert(side_plus);
566  }
567 
568  if(side_moins != NULL) {
569  if(fils_moins == NULL)
570  seg_moins.push_back(side_moins);
571  else
572  fils_moins->insert(side_moins);
573  }
574 }
575 
576 BSPNode::BSPNode(Polygone *P)
577 {
578  polygone = P;
579 
580  initEquation(P,a,b,c,d);
581 
582  fils_moins = NULL;
583  fils_plus = NULL;
584 }
585 
586 void BSPNode::initEquation(const Polygone *P,double & a, double & b, double & c, double & d)
587 {
588  Vector3 n(0.,0.,0.);
589  unsigned int j = 0;
590 
591  while((j < P->nbVertices())&& n.infNorm() <= 0.00001)
592  {
593  n = (P->vertex(j+2) - P->vertex(j+1))^(P->vertex(j) - P->vertex(j+1));
594  j++;
595  }
596 
597  if(n.infNorm() <= 0.00001)
598  {
599  unsigned int ind = P->nbVertices();
600 
601  for(unsigned int i=0;i<P->nbVertices();i++)
602  if((P->vertex(i+1)-P->vertex(i)).infNorm() > 0.00001)
603  {
604  ind = i;
605  i = P->nbVertices();
606  }
607 
608  if(ind < P->nbVertices()) // the polygon is a true segment
609  {
610  if((P->vertex(ind+1).x() != P->vertex(ind).x())||(P->vertex(ind+1).y() != P->vertex(ind).y()))
611  {
612  n[0] = - P->vertex(ind+1).y() + P->vertex(ind).y();
613  n[1] = P->vertex(ind+1).x() - P->vertex(ind).x();
614  n[2] = 0;
615  }
616  else
617  {
618  n[0] = - P->vertex(ind+1).z() + P->vertex(ind).z();
619  n[1] = 0;
620  n[2] = P->vertex(ind+1).x() - P->vertex(ind).x();
621  }
622  }
623  else // the polygon is a point
624  {
625  n[0] = 1.0;
626  n[1] = 0.0;
627  n[2] = 0.0;
628  }
629  }
630 
631  double D = n.norm();
632 
633  if(n[2] < 0.0)
634  n /= -D;
635  else
636  n /= D;
637 
638  d = n*P->vertex(0);
639 
640  a = n[0];
641  b = n[1];
642  c = n[2];
643 }
644 
BSPNode::fils_plus
BSPNode * fils_plus
Definition: BSPSortMethod.cpp:140
vrender::BSPSortMethod::sortPrimitives
virtual void sortPrimitives(std::vector< PtrPrimitive > &, VRenderParams &)
Definition: BSPSortMethod.cpp:77
vrender::Polygone::nbVertices
virtual unsigned int nbVertices() const
Definition: Primitive.h:197
BSPNode::Classify
void Classify(Polygone *, Polygone *&, Polygone *&)
Definition: BSPSortMethod.cpp:302
vrender::Feedback3DColor::x
FLOAT x() const
Definition: Primitive.h:82
BSPNode::insert
void insert(Polygone *)
Definition: BSPSortMethod.cpp:489
BSPTree::_root
BSPNode * _root
Definition: BSPSortMethod.cpp:72
BSPNode::pts_moins
vector< Point * > pts_moins
Definition: BSPSortMethod.cpp:146
vrender::Vector3::z
double z() const
Definition: Vector3.h:83
BSPTree::recursFillPrimitiveArray
void recursFillPrimitiveArray(vector< PtrPrimitive > &) const
Definition: BSPSortMethod.cpp:171
BSPNode::initEquation
void initEquation(const Polygone *P, double &a, double &b, double &c, double &d)
Definition: BSPSortMethod.cpp:586
BSPNode::seg_moins
vector< Segment * > seg_moins
Definition: BSPSortMethod.cpp:143
vrender::Vector3::x
double x() const
Definition: Vector3.h:81
BSPPosition
BSPPosition
Definition: BSPSortMethod.cpp:56
vrender::Polygone::sommet3DColor
virtual const Feedback3DColor & sommet3DColor(int) const
Definition: Primitive.cpp:91
BSPNode::recursFillPrimitiveArray
void recursFillPrimitiveArray(vector< PtrPrimitive > &) const
Definition: BSPSortMethod.cpp:514
vrender::VRenderParams::progress
void progress(float, const QString &)
Definition: VRender.cpp:255
EGALITY_EPS
double EGALITY_EPS
Definition: BSPSortMethod.cpp:53
BSPNode::fils_moins
BSPNode * fils_moins
Definition: BSPSortMethod.cpp:139
vrender::Polygone::vertex
virtual const Vector3 & vertex(int) const
Definition: Primitive.cpp:96
vrender::Vector3::y
double y() const
Definition: Vector3.h:82
BSPTree::_segments
vector< Segment * > _segments
Definition: BSPSortMethod.cpp:73
BSPNode::pts_plus
vector< Point * > pts_plus
Definition: BSPSortMethod.cpp:145
vrender::Vector3::infNorm
double infNorm() const
Infinite norm.
Definition: Vector3.cpp:146
vrender::Feedback3DColor::z
FLOAT z() const
Definition: Primitive.h:84
BSPTree::insert
void insert(Polygone *)
Definition: BSPSortMethod.cpp:169
LINE_EGALITY_EPS
double LINE_EGALITY_EPS
Definition: BSPSortMethod.cpp:54
vrender::Feedback3DColor::y
FLOAT y() const
Definition: Primitive.h:83
vrender::Point::sommet3DColor
virtual const Feedback3DColor & sommet3DColor(int) const
Definition: Primitive.cpp:63
BSPNode::BSPNode
BSPNode(Polygone *)
Definition: BSPSortMethod.cpp:576
BSPTree::_points
vector< Point * > _points
Definition: BSPSortMethod.cpp:74
BSPNode::seg_plus
vector< Segment * > seg_plus
Definition: BSPSortMethod.cpp:142
ind
static unsigned int ind(unsigned int i, unsigned int j)
Definition: camera.cpp:1128
vrender::Segment::sommet3DColor
virtual const Feedback3DColor & sommet3DColor(int i) const
Definition: Primitive.cpp:68
BSPNode::polygone
Polygone * polygone
Definition: BSPSortMethod.cpp:148
vrender::Vector3::norm
double norm() const
Norm.
Definition: Vector3.cpp:132

octovis
Author(s): Kai M. Wurm , Armin Hornung
autogenerated on Mon Jun 10 2019 14:00:24