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-2014 Gilles Debunne. All rights reserved.
26
27 This file is part of the QGLViewer library version 2.7.2.
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
sortPrimitives(std::vector<PtrPrimitive> & primitive_tab,VRenderParams & vparams)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])) != nullptr)
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])) != nullptr)
108 tree.insert(S);
109 else if((p = dynamic_cast<Point *>(segments_and_points[j])) != nullptr)
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
122 /////////////////////////////////////////////////////////////////////////////////////////////////
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
BSPTree()157 BSPTree::BSPTree()
158 {
159 _root = nullptr;
160 }
161
~BSPTree()162 BSPTree::~BSPTree()
163 {
164 delete _root;
165 }
166
insert(Point * P)167 void BSPTree::insert(Point *P) { if(_root == nullptr) _points.push_back(P) ; else _root->insert(P); }
insert(Segment * S)168 void BSPTree::insert(Segment *S) { if(_root == nullptr) _segments.push_back(S); else _root->insert(S); }
insert(Polygone * P)169 void BSPTree::insert(Polygone *P){ if(_root == nullptr) _root = new BSPNode(P); else _root->insert(P); }
170
recursFillPrimitiveArray(vector<PtrPrimitive> & tab) const171 void BSPTree::recursFillPrimitiveArray(vector<PtrPrimitive>& tab) const
172 {
173 if(_root != nullptr) _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
~BSPNode()181 BSPNode::~BSPNode()
182 {
183 delete fils_moins;
184 delete fils_plus;
185 }
186
Classify(Point * P)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
Classify(Segment * S,Segment * & moins_,Segment * & plus_)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_ = nullptr;
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_ = nullptr;
259 return;
260 }
261 else
262 {
263 moins_ = nullptr;
264 plus_ = S;
265 return;
266 }
267 }
268 else if(s1 == 0)
269 {
270 if(s2 > 0)
271 {
272 moins_ = nullptr;
273 plus_ = S;
274 return;
275 }
276 else
277 {
278 moins_ = S;
279 plus_ = nullptr;
280 return;
281 }
282 }
283 else if(s2 == 0)
284 {
285 if(s1 > 0)
286 {
287 moins_ = nullptr;
288 plus_ = S;
289 return;
290 }
291 else
292 {
293 moins_ = S;
294 plus_ = nullptr;
295 return;
296 }
297 }
298 //else
299 //printf("BSPNode::Classify: unexpected classification case !!\n");
300 }
301
Classify(Polygone * P,Polygone * & moins_,Polygone * & plus_)302 void BSPNode::Classify(Polygone *P, Polygone * & moins_, Polygone * & plus_)
303 {
304 static int Signs[100];
305 static double Zvals[100];
306
307 moins_ = nullptr;
308 plus_ = nullptr;
309
310 if(P == nullptr)
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_ = nullptr;
346 return;
347 }
348
349 // Polygone tout positif
350
351 if(Smin == 1)
352 {
353 plus_ = P;
354 moins_ = nullptr;
355 return;
356 }
357
358 // Polygone tout negatif
359
360 if(Smax == -1)
361 {
362 plus_ = nullptr;
363 moins_ = P;
364 return;
365 }
366
367 if((Smin == -1)&&(Smax == 0))
368 {
369 plus_ = nullptr;
370 moins_ = P;
371 return;
372 }
373
374 if((Smin == 0)&&(Smax == 1))
375 {
376 plus_ = P;
377 moins_ = nullptr;
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_ = nullptr;
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
insert(Polygone * P)489 void BSPNode::insert(Polygone *P)
490 {
491 Polygone *side_plus = nullptr, *side_moins = nullptr;
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 != nullptr) {
500 if(fils_plus == nullptr)
501 fils_plus = new BSPNode(side_plus);
502 else
503 fils_plus->insert(side_plus);
504 }
505
506 if(side_moins != nullptr) {
507 if(fils_moins == nullptr)
508 fils_moins = new BSPNode(side_moins);
509 else
510 fils_moins->insert(side_moins);
511 }
512 }
513
recursFillPrimitiveArray(vector<PtrPrimitive> & primitive_tab) const514 void BSPNode::recursFillPrimitiveArray(vector<PtrPrimitive>& primitive_tab) const
515 {
516 if(fils_plus != nullptr)
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 != nullptr)
525 primitive_tab.push_back(polygone);
526
527 if(fils_moins != nullptr)
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
insert(Point * P)536 void BSPNode::insert(Point *P)
537 {
538 int res = Classify(P);
539
540 if(res == -1) {
541 if(fils_moins == nullptr)
542 pts_moins.push_back(P);
543 else
544 fils_moins->insert(P);
545 }
546
547 if(res == 1) {
548 if(fils_plus == nullptr)
549 pts_plus.push_back(P);
550 else
551 fils_plus->insert(P);
552 }
553 }
554
insert(Segment * S)555 void BSPNode::insert(Segment *S)
556 {
557 Segment *side_plus = nullptr, *side_moins = nullptr;
558
559 Classify(S,side_moins,side_plus);
560
561 if(side_plus != nullptr) {
562 if(fils_plus == nullptr)
563 seg_plus.push_back(side_plus);
564 else
565 fils_plus->insert(side_plus);
566 }
567
568 if(side_moins != nullptr) {
569 if(fils_moins == nullptr)
570 seg_moins.push_back(side_moins);
571 else
572 fils_moins->insert(side_moins);
573 }
574 }
575
BSPNode(Polygone * P)576 BSPNode::BSPNode(Polygone *P)
577 {
578 polygone = P;
579
580 initEquation(P,a,b,c,d);
581
582 fils_moins = nullptr;
583 fils_plus = nullptr;
584 }
585
initEquation(const Polygone * P,double & a,double & b,double & c,double & d)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
645