TopologicalSortMethod.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-2014 Gilles Debunne. All rights reserved.
26 
27  This file is part of the QGLViewer library version 2.6.3.
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 <assert.h>
46 #include <climits>
47 
48 #include "VRender.h"
49 #include "Primitive.h"
50 #include "PrimitivePositioning.h"
51 #include "AxisAlignedBox.h"
52 #include "SortMethod.h"
53 #include "Vector2.h"
54 
55 using namespace std ;
56 using namespace vrender ;
57 
58 // #define DEBUG_TS
59 
60 namespace vrender
61 {
62 class TopologicalSortUtils
63 {
64  public:
65  static void buildPrecedenceGraph(vector<PtrPrimitive>& primitive_tab, vector< vector<size_t> >& precedence_graph) ;
66 
67  static void recursFindNeighbors( const vector<PtrPrimitive>& primitive_tab,
68  const vector<size_t>& pindices,
69  vector< vector<size_t> >& precedence_graph,
70  const AxisAlignedBox_xy&,int) ;
71 
72  static void checkAndAddEdgeToGraph(size_t a,size_t b,vector< vector<size_t> >& precedence_graph) ;
73  static void suppressPrecedence(size_t a,size_t b,vector< vector<size_t> >& precedence_graph) ;
74 
75  static void recursTopologicalSort(vector< vector<size_t> >& precedence_graph,
76  vector<PtrPrimitive>& primitive_tab,
77  vector<bool>& alread_rendered,
78  vector<bool>& alread_visited,
79  vector<PtrPrimitive>&,size_t,size_t&,
80  VRenderParams& vparams,
81  size_t info_cnt,size_t& nbrendered) ;
82 
83  static void recursTopologicalSort(vector< vector<size_t> >& precedence_graph,
84  vector<PtrPrimitive>& primitive_tab,
85  vector<bool>& alread_rendered,
86  vector<bool>& alread_visited,
87  vector<PtrPrimitive>&,size_t,
88  vector<size_t>& ancestors,
89  size_t&, size_t&,
90  VRenderParams& vparams,
91  size_t info_cnt,size_t& nbrendered) ;
92 
93  static void topologicalSort( vector< vector<size_t> >& precedence_graph,
94  vector<PtrPrimitive>& primitive_tab,
95  VRenderParams&) ;
96 
97  static void topologicalSortBreakCycles(vector< vector<size_t> >& precedence_graph,
98  vector<PtrPrimitive>& primitive_tab,
99  VRenderParams&) ;
100 
101 #ifdef DEBUG_TS
102  static void printPrecedenceGraph(const vector< vector<size_t> >& precedence_graph,
103  const vector<PtrPrimitive>& primitive_tab) ;
104 #endif
105 };
106 
107 TopologicalSortMethod::TopologicalSortMethod()
108 {
109  _break_cycles = false ;
110 }
111 
112 void TopologicalSortMethod::sortPrimitives(vector<PtrPrimitive>& primitive_tab,VRenderParams& vparams)
113 {
114  // 1 - build a precedence graph
115 
116 #ifdef DEBUG_TS
117  cout << "Computing precedence graph." << endl ;
118  cout << "Old order: " ;
119  for(size_t i=0;i<primitive_tab.size();++i) cout << (void *)(primitive_tab[i]) << " " ;
120  cout << endl ;
121 #endif
122  vector< vector<size_t> > precedence_graph(primitive_tab.size());
123  TopologicalSortUtils::buildPrecedenceGraph(primitive_tab,precedence_graph) ;
124 
125 #ifdef DEBUG_TS
126  TopologicalSortUtils::printPrecedenceGraph(precedence_graph,primitive_tab) ;
127 #endif
128  // 2 - perform a topological sorting of the graph
129 
130 #ifdef DEBUG_TS
131  cout << "Sorting." << endl ;
132 #endif
133 
134  if(_break_cycles)
135  TopologicalSortUtils::topologicalSortBreakCycles(precedence_graph, primitive_tab,vparams) ;
136  else
137  TopologicalSortUtils::topologicalSort(precedence_graph, primitive_tab,vparams) ;
138 
139 #ifdef DEBUG_TS
140  cout << "New order: " ;
141  for(size_t i=0;i<primitive_tab.size();++i) cout << (void *)(primitive_tab[i]) << " " ;
142  cout << endl ;
143 #endif
144 }
145 
146 #ifdef DEBUG_TS
147 void TopologicalSortUtils::printPrecedenceGraph(const vector< vector<size_t> >& precedence_graph,
148  const vector<PtrPrimitive>& primitive_tab)
149 {
150  for(size_t i=0;i<precedence_graph.size();++i)
151  {
152  cout << i << " (" << primitive_tab[i]->nbVertices() << ") : " ;
153  for(size_t j=0;j<precedence_graph[i].size();++j)
154  cout << precedence_graph[i][j] << " " ;
155 
156  cout << endl ;
157  }
158 }
159 #endif
160 
161 void TopologicalSortUtils::buildPrecedenceGraph(vector<PtrPrimitive>& primitive_tab,
162  vector< vector<size_t> >& precedence_graph)
163 {
164  // The precedence graph is constructed by first conservatively determining which
165  // primitives can possibly intersect using a quadtree. Candidate pairs of
166  // primitives are then carefully checked to compute their exact relative positionning.
167  //
168  // Because of the conservativeness of the quadtree, some pairs of primitives may be checked
169  // multiple times for intersection. Using a buffer of already computed results may proove
170  // very efficient.
171 
172  // 0 - compute bounding box of the set of primitives.
173 
174  AxisAlignedBox_xy BBox ;
175 
176  for(size_t i=0;i<primitive_tab.size();++i)
177  {
178  BBox.include(Vector2(primitive_tab[i]->bbox().mini().x(),primitive_tab[i]->bbox().mini().y())) ;
179  BBox.include(Vector2(primitive_tab[i]->bbox().maxi().x(),primitive_tab[i]->bbox().maxi().y())) ;
180  }
181 
182  // 1 - recursively find pairs.
183 
184  vector<size_t> pindices(primitive_tab.size()) ;
185  for(size_t j=0;j<pindices.size();++j)
186  pindices[j] = j ;
187 
188  recursFindNeighbors(primitive_tab, pindices, precedence_graph, BBox,0) ;
189 }
190 
191 void TopologicalSortUtils::recursFindNeighbors(const vector<PtrPrimitive>& primitive_tab,
192  const vector<size_t>& pindices,
193  vector< vector<size_t> >& precedence_graph,
194  const AxisAlignedBox_xy& bbox,
195  int depth)
196 {
197  static const size_t MAX_PRIMITIVES_IN_CELL = 5 ;
198 
199  // Refinment: first decide which sub-cell each primitive meets, then call
200  // algorithm recursively.
201 
202  if(primitive_tab.size() > MAX_PRIMITIVES_IN_CELL)
203  {
204  vector<size_t> p_indices_min_min ;
205  vector<size_t> p_indices_min_max ;
206  vector<size_t> p_indices_max_min ;
207  vector<size_t> p_indices_max_max ;
208 
209  double xmin = bbox.mini().x() ;
210  double ymin = bbox.mini().y() ;
211  double xmax = bbox.maxi().x() ;
212  double ymax = bbox.maxi().y() ;
213 
214  double xMean = 0.5*(xmin+xmax) ;
215  double yMean = 0.5*(ymin+ymax) ;
216 
217  for(size_t i=0;i<pindices.size();++i)
218  {
219  bool left = primitive_tab[pindices[i]]->bbox().mini().x() <= xMean ;
220  bool right = primitive_tab[pindices[i]]->bbox().maxi().x() >= xMean ;
221  bool down = primitive_tab[pindices[i]]->bbox().mini().y() <= yMean ;
222  bool up = primitive_tab[pindices[i]]->bbox().maxi().y() >= yMean ;
223 
224  if(left && down) p_indices_min_min.push_back(pindices[i]) ;
225  if(right && down) p_indices_max_min.push_back(pindices[i]) ;
226  if(left && up ) p_indices_min_max.push_back(pindices[i]) ;
227  if(right && up ) p_indices_max_max.push_back(pindices[i]) ;
228  }
229 
230  // checks if refining is not too much stupid
231 
232  if(p_indices_min_min.size() < pindices.size() && p_indices_max_min.size() < pindices.size()
233  && p_indices_min_max.size() < pindices.size() && p_indices_max_max.size() < pindices.size())
234  {
235  recursFindNeighbors(primitive_tab,p_indices_min_min,precedence_graph,AxisAlignedBox_xy(Vector2(xmin,xMean),Vector2(ymin,yMean)),depth+1) ;
236  recursFindNeighbors(primitive_tab,p_indices_min_max,precedence_graph,AxisAlignedBox_xy(Vector2(xmin,xMean),Vector2(yMean,ymax)),depth+1) ;
237  recursFindNeighbors(primitive_tab,p_indices_max_min,precedence_graph,AxisAlignedBox_xy(Vector2(xMean,xmax),Vector2(ymin,yMean)),depth+1) ;
238  recursFindNeighbors(primitive_tab,p_indices_max_max,precedence_graph,AxisAlignedBox_xy(Vector2(xMean,xmax),Vector2(yMean,ymax)),depth+1) ;
239  return ;
240  }
241  }
242 
243  // No refinment either because it could not be possible, or because the number of primitives is below
244  // the predefined limit.
245 
246  for(size_t i=0;i<pindices.size();++i)
247  for(size_t j=i+1;j<pindices.size();++j)
248  {
249  // Compute the position of j as regard to i
250 
251  int prp = PrimitivePositioning::computeRelativePosition( primitive_tab[pindices[i]], primitive_tab[pindices[j]]) ;
252 
253  if(prp & PrimitivePositioning::Upper) checkAndAddEdgeToGraph(pindices[j],pindices[i],precedence_graph) ;
254  if(prp & PrimitivePositioning::Lower) checkAndAddEdgeToGraph(pindices[i],pindices[j],precedence_graph) ;
255  }
256 }
257 
258 void TopologicalSortUtils::checkAndAddEdgeToGraph(size_t a,size_t b,vector< vector<size_t> >& precedence_graph)
259 {
260 #ifdef DEBUG_TS
261  cout << "Trying to add " << a << " -> " << b << " " ;
262 #endif
263  bool found = false ;
264 
265  for(size_t k=0;k<precedence_graph[a].size() && !found;++k)
266  if(precedence_graph[a][k] == b)
267  found = true ;
268 
269 #ifdef DEBUG_TS
270  if(found)
271  cout << "already" << endl ;
272  else
273  cout << "ok" << endl ;
274 #endif
275  if(!found)
276  precedence_graph[a].push_back(b) ;
277 }
278 
279 void TopologicalSortUtils::suppressPrecedence(size_t a,size_t b,vector< vector<size_t> >& precedence_graph)
280 {
281  vector<size_t> prec_tab = vector<size_t>(precedence_graph[a]) ;
282  bool trouve = false ;
283 
284  for(size_t k=0;k<prec_tab.size();++k)
285  if(prec_tab[k] == b)
286  {
287  prec_tab[k] = prec_tab[prec_tab.size()-1] ;
288  prec_tab.pop_back() ;
289  }
290 
291  if(!trouve)
292  throw runtime_error("Unexpected error in suppressPrecedence") ;
293 }
294 
295 void TopologicalSortUtils::topologicalSort(vector< vector<size_t> >& precedence_graph,
296  vector<PtrPrimitive>& primitive_tab,
297  VRenderParams& vparams)
298 {
299  vector<PtrPrimitive> new_pr_tab ;
300  vector<bool> already_visited(primitive_tab.size(),false) ;
301  vector<bool> already_rendered(primitive_tab.size(),false) ;
302  size_t nb_skews = 0 ;
303 
304  size_t info_cnt = primitive_tab.size()/200 + 1 ;
305  size_t nbrendered = 0 ;
306 
307  // 1 - sorts primitives by rendering order
308 
309  for(size_t i=0;i<primitive_tab.size();++i)
310  if(!already_rendered[i])
311  recursTopologicalSort(precedence_graph,primitive_tab,already_rendered,already_visited,new_pr_tab,i,nb_skews,vparams,info_cnt,nbrendered);
312 
313 #ifdef DEBUG_TS
314  if(nb_skews > 0)
315  cout << nb_skews << " cycles found." << endl ;
316  else
317  cout << "No cycles found." << endl ;
318 #endif
319  primitive_tab = new_pr_tab ;
320 }
321 
322 void TopologicalSortUtils::topologicalSortBreakCycles(vector< vector<size_t> >& precedence_graph,
323  vector<PtrPrimitive>& primitive_tab,
324  VRenderParams& vparams)
325 {
326  vector<PtrPrimitive> new_pr_tab ;
327  vector<bool> already_visited(primitive_tab.size(),false) ;
328  vector<bool> already_rendered(primitive_tab.size(),false) ;
329  vector<size_t> ancestors ;
330  size_t nb_skews = 0 ;
331  size_t ancestors_backward_index ;
332 
333  size_t info_cnt = primitive_tab.size()/200 + 1 ;
334  size_t nbrendered = 0 ;
335 
336  // 1 - sorts primitives by rendering order
337 
338  for(size_t i=0;i<primitive_tab.size();++i)
339  if(!already_rendered[i])
340  recursTopologicalSort(precedence_graph,primitive_tab,already_rendered,already_visited,
341  new_pr_tab,i,ancestors,ancestors_backward_index,nb_skews,vparams,info_cnt,nbrendered) ;
342 
343 #ifdef DEBUG_TS
344  if(nb_skews > 0)
345  cout << nb_skews << " cycles found." << endl ;
346  else
347  cout << "No cycles found." << endl ;
348 #endif
349  primitive_tab = new_pr_tab ;
350 }
351 
352 void TopologicalSortUtils::recursTopologicalSort( vector< vector<size_t> >& precedence_graph,
353  vector<PtrPrimitive>& primitive_tab,
354  vector<bool>& already_rendered,
355  vector<bool>& already_visited,
356  vector<PtrPrimitive>& new_pr_tab,
357  size_t indx,
358  size_t& nb_cycles,
359  VRenderParams& vparams,
360  size_t info_cnt,size_t& nbrendered)
361 {
362  // One must first render the primitives indicated by the precedence graph,
363  // then render the current primitive. Skews are detected, but and treated.
364 
365  already_visited[indx] = true ;
366 
367  for(size_t j=0;j<precedence_graph[indx].size();++j)
368  {
369  // Both tests are important. If we ommit the second one, the recursion is
370  // always performed down to the next cycle, although this is useless if
371  // the current primitive was rendered already.
372 
373  if(!already_visited[precedence_graph[indx][j]])
374  {
375  if(!already_rendered[precedence_graph[indx][j]])
376  recursTopologicalSort( precedence_graph,primitive_tab,already_rendered,already_visited,
377  new_pr_tab,precedence_graph[indx][j],nb_cycles,vparams,info_cnt,nbrendered) ;
378  }
379  else // A cycle is detected, but in this version, it is not broken.
380  ++nb_cycles ;
381  }
382 
383  if(!already_rendered[indx])
384  {
385  new_pr_tab.push_back(primitive_tab[indx]) ;
386 
387  if((++nbrendered)%info_cnt==0)
388  vparams.progress(nbrendered/(float)primitive_tab.size(), QGLViewer::tr("Topological sort")) ;
389  }
390 
391  already_rendered[indx] = true ;
392  already_visited[indx] = false ;
393 }
394 
395 void TopologicalSortUtils::recursTopologicalSort( vector< vector<size_t> >& precedence_graph,
396  vector<PtrPrimitive>& primitive_tab,
397  vector<bool>& already_rendered,
398  vector<bool>& already_visited,
399  vector<PtrPrimitive>& new_pr_tab,
400  size_t indx,
401  vector<size_t>& ancestors,
402  size_t& ancestors_backward_index,
403  size_t& nb_cycles,
404  VRenderParams& vparams,
405  size_t info_cnt,size_t& nbrendered)
406 {
407  // One must first render the primitives indicated by the precedence graph,
408  // then render the current primitive. Skews are detected, but and treated.
409 
410  already_visited[indx] = true ;
411  ancestors.push_back(indx) ;
412 
413  for(size_t j=0;j<precedence_graph[indx].size();++j)
414  {
415  // Both tests are important. If we ommit the second one, the recursion is
416  // always performed down to the next cycle, although this is useless if
417  // the current primitive was rendered already.
418 
419  if(!already_visited[precedence_graph[indx][j]])
420  {
421  if(!already_rendered[precedence_graph[indx][j]])
422  {
423  recursTopologicalSort( precedence_graph,primitive_tab,already_rendered,already_visited,
424  new_pr_tab,precedence_graph[indx][j],ancestors,ancestors_backward_index,nb_cycles,vparams,info_cnt,nbrendered) ;
425 
426  if(ancestors_backward_index != INT_MAX && ancestors.size() > (size_t)(ancestors_backward_index+1))
427  {
428 #ifdef DEBUG_TS
429  cout << "Returning early" << endl ;
430 #endif
431  already_visited[indx] = false ;
432  ancestors.pop_back() ;
433  return;
434  }
435  if(ancestors_backward_index != INT_MAX) // we are returning from emergency. j must be re-tried
436  --j ;
437  }
438  }
439  else
440  {
441  // A cycle is detected. It must be broken. The algorithm is the following: primitives of the cycle
442  // are successively split by a chosen splitting plane and the precendence graph is updated
443  // at the same time by re-computing primitive precedence. As soon as the cycle is broken,
444  // the algorithm stops and calls recursively calls on the new precedence graph. This necessarily
445  // happens because of the BSP-node nature of the current set of primitives.
446 
447  // 0 - stats
448  ++nb_cycles ;
449 
450  // 0.5 - determine cycle beginning
451 
452  long cycle_beginning_index = -1 ;
453  for(size_t i=ancestors.size()-1; long(i) >= 0 && cycle_beginning_index < 0;--i)
454  if(ancestors[i] == precedence_graph[indx][j])
455  cycle_beginning_index = (long)i ;
456 #ifdef DEBUG_TS
457  cout << "Unbreaking cycle : " ;
458  for(size_t i=0;i<ancestors.size();++i)
459  cout << ancestors[i] << " " ;
460  cout << precedence_graph[indx][j] << endl ;
461 #endif
462 #ifdef DEBUG_TS
463  assert(cycle_beginning_index >= 0) ;
464 #endif
465  // 1 - determine splitting plane
466 
467  long split_prim_ancestor_indx = -1 ;
468  long split_prim_indx = -1 ;
469 
470  // Go down ancestors tab, starting from the skewing primitive, and stopping at it.
471 
472  for(size_t i2=(size_t)cycle_beginning_index;i2<ancestors.size() && split_prim_ancestor_indx < 0;++i2)
473  if(primitive_tab[ancestors[i2]]->nbVertices() > 2)
474  {
475  split_prim_ancestor_indx = (long)i2 ;
476  split_prim_indx = (long)ancestors[i2] ;
477  }
478 
479 #ifdef DEBUG_TS
480  cout << "Split primitive index = " << split_prim_ancestor_indx << "(primitive = " << split_prim_indx << ")" << endl ;
481 #endif
482  if(split_prim_indx < 0) // no need to unskew cycles between segments and points
483  continue ;
484 
485  // 2 - split all necessary primitives
486 
487  const Polygone *P = dynamic_cast<const Polygone *>(primitive_tab[(size_t)split_prim_indx]) ;
488  const NVector3& normal = NVector3(P->normal()) ;
489  double c(P->c()) ;
490  ancestors.push_back(precedence_graph[indx][j]) ; // sentinel
491  ancestors.push_back(ancestors[(size_t)cycle_beginning_index+1]) ; // sentinel
492  bool cycle_broken = false ;
493 
494  for(size_t i3=(size_t)cycle_beginning_index+1;i3<ancestors.size()-1 && !cycle_broken;++i3)
495  if(ancestors[i3] != (size_t)split_prim_indx)
496  {
497  bool prim_lower_ante_contains_im1 = false ;
498  bool prim_upper_ante_contains_im1 = false ;
499  bool prim_lower_prec_contains_ip1 = false ;
500  bool prim_upper_prec_contains_ip1 = false ;
501 
502  Primitive *prim_upper = NULL ;
503  Primitive *prim_lower = NULL ;
504 
505  PrimitivePositioning::splitPrimitive(primitive_tab[ancestors[i3]],normal,c,prim_upper,prim_lower) ;
506 
507  if(prim_upper == NULL || prim_lower == NULL)
508  continue ;
509 #ifdef DEBUG_TS
510  cout << "Splitted primitive " << ancestors[i3] << endl ;
511 #endif
512 
513  vector<size_t> prim_upper_prec ;
514  vector<size_t> prim_lower_prec ;
515 
516  vector<size_t> old_prec = vector<size_t>(precedence_graph[ancestors[i3]]) ;
517 
518  size_t upper_indx = precedence_graph.size() ;
519  size_t lower_indx = ancestors[i3] ;
520 
521  // Updates the precedence graph downwards.
522 
523  for(size_t k=0;k<old_prec.size();++k)
524  {
525  int prp1 = PrimitivePositioning::computeRelativePosition(prim_upper,primitive_tab[old_prec[k]]) ;
526 #ifdef DEBUG_TS
527  cout << "Compariing " << upper_indx << " and " << old_prec[k] << ": " ;
528 #endif
529  // It can not be Upper, because it was lower from the original primitive, but it is not
530  // necessary lower any longer because of the split.
531 
532  if(prp1 & PrimitivePositioning::Lower)
533  {
534 #ifdef DEBUG_TS
535  cout << " > " << endl ;
536 #endif
537  prim_upper_prec.push_back(old_prec[k]) ;
538 
539  if(old_prec[k] == ancestors[i3+1])
540  prim_upper_prec_contains_ip1 = true ;
541  }
542 #ifdef DEBUG_TS
543  else
544  cout << " I " << endl ;
545 #endif
546 
547  int prp2 = PrimitivePositioning::computeRelativePosition(prim_lower,primitive_tab[old_prec[k]]) ;
548 #ifdef DEBUG_TS
549  cout << "Compariing " << lower_indx << " and " << old_prec[k] << ": " ;
550 #endif
551  if(prp2 & PrimitivePositioning::Lower)
552  {
553 #ifdef DEBUG_TS
554  cout << " > " << endl ;
555 #endif
556  prim_lower_prec.push_back(old_prec[k]) ;
557 
558  if(old_prec[k] == ancestors[i3+1])
559  prim_lower_prec_contains_ip1 = true ;
560  }
561 #ifdef DEBUG_TS
562  else
563  cout << " I " << endl ;
564 #endif
565  }
566 
567  // We also have to update the primitives which are upper to the
568  // current one, because some of them may not be upper anymore.
569  // This would requires either a O(n^2) algorithm, or to store an
570  // dual precedence graph. For now it's O(n^2). This test can not
571  // be skipped because upper can still be lower to ancestors[i-1].
572 
573  for(size_t l=0;l<precedence_graph.size();++l)
574  if(l != (size_t)lower_indx)
575  for(size_t k=0;k<precedence_graph[l].size();++k)
576  if(precedence_graph[l][k] == ancestors[i3])
577  {
578  int prp1 = PrimitivePositioning::computeRelativePosition(prim_upper,primitive_tab[l]) ;
579 
580  // It can not be Lower, because it was upper from the original primitive, but it is not
581  // necessary upper any longer because of the split.
582 
583  if(prp1 & PrimitivePositioning::Upper)
584  {
585  // Still upper. Add the new index at end of the array
586 
587  precedence_graph[l].push_back(upper_indx) ;
588 
589  if(l == (size_t)ancestors[i3-1])
590  prim_upper_ante_contains_im1 = true ;
591  }
592  // If the primitive is not upper anymore there is
593  // nothing to change since the index has changed.
594 
595  int prp2 = PrimitivePositioning::computeRelativePosition(prim_lower,primitive_tab[l]) ;
596 #ifdef DEBUG_TS
597  cout << "Compariing " << l << " and " << lower_indx << ": " ;
598 #endif
599  if(prp2 & PrimitivePositioning::Upper)
600  {
601 #ifdef DEBUG_TS
602  cout << " > " << endl ;
603 #endif
604  if(l == (size_t)ancestors[i3-1]) // The index is the same => nothing to change.
605  prim_lower_ante_contains_im1 = true ;
606  }
607  else
608  {
609 #ifdef DEBUG_TS
610  cout << " I " << endl ;
611 #endif
612  // Not upper anymore. We have to suppress this entry from the tab.
613 
614  precedence_graph[l][k] = precedence_graph[l][precedence_graph[l].size()-1] ;
615  precedence_graph[l].pop_back() ;
616  --k ;
617  }
618 
619  break ; // each entry is present only once.
620  }
621 
622  // setup recorded new info
623 
624  primitive_tab.push_back(prim_upper) ;
625  delete primitive_tab[lower_indx] ;
626  primitive_tab[lower_indx] = prim_lower ;
627 
628  // Adds the info to the precedence graph
629 
630  precedence_graph.push_back(prim_upper_prec) ;
631  precedence_graph[lower_indx] = prim_lower_prec ;
632 
633  // Adds new entries to the 'already_rendered' and 'already_visited' vectors
634  already_visited.push_back(false) ;
635  already_rendered.push_back(false) ;
636 #ifdef DEBUG_TS
637  cout << "New precedence graph: " << endl ;
638  printPrecedenceGraph(precedence_graph,primitive_tab) ;
639 #endif
640  // Checks if the cycle is broken. Because the graph is only
641  // updated downwards, we check wether lower (which still is
642  // lower to ancestors[i-1]) is upper to ancestors[i+1], or
643  // if upper is still .
644 
645  if(( !(prim_lower_ante_contains_im1 && prim_lower_prec_contains_ip1))
646  &&(!(prim_upper_ante_contains_im1 && prim_upper_prec_contains_ip1)))
647  cycle_broken = true ;
648  }
649 
650  ancestors.pop_back() ;
651  ancestors.pop_back() ;
652 
653  // 3 - recurs call
654 
655  if(cycle_broken)
656  {
657  ancestors_backward_index = (size_t)cycle_beginning_index ;
658 #ifdef DEBUG_TS
659  cout << "Cycle broken. Jumping back to rank " << ancestors_backward_index << endl ;
660 #endif
661  already_visited[indx] = false ;
662  ancestors.pop_back() ;
663  return;
664  }
665 #ifdef DEBUG_TS
666  else
667  cout << "Cycle could not be broken !!" << endl ;
668 #endif
669  }
670  }
671 
672  if(!already_rendered[indx])
673  {
674 #ifdef DEBUG_TS
675  cout << "Returning ok. Rendered primitive " << indx << endl ;
676 #endif
677  new_pr_tab.push_back(primitive_tab[indx]) ;
678 
679  if((++nbrendered)%info_cnt==0)
680  vparams.progress(nbrendered/(float)primitive_tab.size(), QGLViewer::tr("Advanced topological sort")) ;
681  }
682 
683  already_rendered[indx] = true ;
684  ancestors_backward_index = INT_MAX ;
685  already_visited[indx] = false ;
686  ancestors.pop_back() ;
687 }
688 } // namespace
vrender::AxisAlignedBox_xy
AxisAlignedBox< Vector2 > AxisAlignedBox_xy
Definition: AxisAlignedBox.h:70
vrender::Polygone::c
double c() const
Definition: Primitive.h:200
bbox
struct bbox_shape bbox
vrender::VRenderParams::progress
void progress(float, const QString &)
Definition: VRender.cpp:255
vrender::AxisAlignedBox::maxi
const T & maxi() const
Definition: AxisAlignedBox.h:61
vrender::Polygone::normal
const NVector3 & normal() const
Definition: Primitive.h:199
bbox_shape
Definition: gpc.cpp:276
vrender::AxisAlignedBox::include
void include(const T &v)
Definition: AxisAlignedBox.h:89
vrender::AxisAlignedBox::mini
const T & mini() const
Definition: AxisAlignedBox.h:60

octovis
Author(s): Kai M. Wurm , Armin Hornung
autogenerated on Wed Jun 5 2019 19:26:39