09833bf4b4aad3ec3975b1730d1e47c8d3ca9724
[blender.git] / source / blender / freestyle / intern / stroke / Operators.cpp
1
2 //
3 //  Copyright (C) : Please refer to the COPYRIGHT file distributed 
4 //   with this source distribution. 
5 //
6 //  This program is free software; you can redistribute it and/or
7 //  modify it under the terms of the GNU General Public License
8 //  as published by the Free Software Foundation; either version 2
9 //  of the License, or (at your option) any later version.
10 //
11 //  This program is distributed in the hope that it will be useful,
12 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
13 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 //  GNU General Public License for more details.
15 //
16 //  You should have received a copy of the GNU General Public License
17 //  along with this program; if not, write to the Free Software
18 //  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19 //
20 ///////////////////////////////////////////////////////////////////////////////
21
22 #include "Operators.h"
23 #include <algorithm>
24 #include <stdexcept>
25 #include "Canvas.h"
26 #include "Stroke.h"
27
28 LIB_STROKE_EXPORT Operators::I1DContainer         Operators::_current_view_edges_set;
29 LIB_STROKE_EXPORT Operators::I1DContainer               Operators::_current_chains_set;
30 LIB_STROKE_EXPORT Operators::I1DContainer*      Operators::_current_set = NULL;
31 LIB_STROKE_EXPORT Operators::StrokesContainer   Operators::_current_strokes_set;
32
33 int Operators::select(UnaryPredicate1D& pred) {
34   if (!_current_set)
35     return 0;
36   if(_current_set->empty())
37     return 0;
38   I1DContainer new_set;
39   I1DContainer rejected;
40   Functions1D::ChainingTimeStampF1D cts;
41   Functions1D::TimeStampF1D ts;
42   I1DContainer::iterator it = _current_set->begin();
43   I1DContainer::iterator itbegin = it;
44   while (it != _current_set->end()) {
45     Interface1D * i1d = *it;
46     cts(*i1d); // mark everyone's chaining time stamp anyway
47         if(pred(*i1d) < 0){
48           new_set.clear();
49           rejected.clear();
50           return -1;
51         }
52         if(pred.result){
53       new_set.push_back(i1d);
54       ts(*i1d);
55     }else{
56       rejected.push_back(i1d);
57     }
58     ++it;
59   }
60   if((*itbegin)->getExactTypeName() != "ViewEdge"){
61     for (it = rejected.begin();
62        it != rejected.end();
63        ++it)
64     delete *it;
65   }
66   rejected.clear();
67   _current_set->clear();
68   *_current_set = new_set;
69   return 0;
70 }
71
72
73 int Operators::chain(ViewEdgeInternal::ViewEdgeIterator& it,
74                       UnaryPredicate1D& pred,
75                       UnaryFunction1D_void& modifier) {
76   if (_current_view_edges_set.empty())
77     return 0;
78
79   unsigned id = 0;
80   ViewEdge* edge;
81   I1DContainer new_chains_set;
82
83   for (I1DContainer::iterator it_edge = _current_view_edges_set.begin();
84        it_edge != _current_view_edges_set.end();
85        ++it_edge) {
86         if (pred(**it_edge) < 0)
87           goto error;
88         if (pred.result)
89       continue;
90
91     edge = dynamic_cast<ViewEdge*>(*it_edge);
92     it.setBegin(edge);
93     it.setCurrentEdge(edge);
94
95     Chain* new_chain = new Chain(id);++id;
96     for (;;) {
97       new_chain->push_viewedge_back(*it, it.getOrientation());
98           if (modifier(**it) < 0) {
99                 delete new_chain;
100                 goto error;
101           }
102       ++it;
103           if (it.isEnd())
104                 break;
105           if (pred(**it) < 0) {
106                 delete new_chain;
107                 goto error;
108           }
109           if (pred.result)
110             break;
111         }
112     new_chains_set.push_back(new_chain);
113   }
114   
115   if (!new_chains_set.empty()) {
116         for (I1DContainer::iterator it = new_chains_set.begin(); it != new_chains_set.end(); ++it) {
117           _current_chains_set.push_back(*it);
118         }
119         new_chains_set.clear();
120     _current_set = &_current_chains_set;
121   }
122   return 0;
123
124 error:
125   for (I1DContainer::iterator it = new_chains_set.begin(); it != new_chains_set.end(); ++it) {
126         delete (*it);
127   }
128   new_chains_set.clear();
129   return -1;
130 }
131
132
133 int Operators::chain(ViewEdgeInternal::ViewEdgeIterator& it,
134                       UnaryPredicate1D& pred) {
135   if (_current_view_edges_set.empty())
136     return 0;
137
138   unsigned id = 0;
139   Functions1D::IncrementChainingTimeStampF1D ts;
140   Predicates1D::EqualToChainingTimeStampUP1D pred_ts(TimeStamp::instance()->getTimeStamp()+1);
141   ViewEdge* edge;
142   I1DContainer new_chains_set;
143
144   for (I1DContainer::iterator it_edge = _current_view_edges_set.begin();
145        it_edge != _current_view_edges_set.end();
146        ++it_edge) {
147         if (pred(**it_edge) < 0)
148           goto error;
149     if (pred.result)
150           continue;
151         if (pred_ts(**it_edge) < 0)
152           goto error;
153         if (pred_ts.result)
154       continue;
155
156     edge = dynamic_cast<ViewEdge*>(*it_edge);
157     it.setBegin(edge);
158     it.setCurrentEdge(edge);
159
160     Chain* new_chain = new Chain(id);++id;
161     for (;;) {
162       new_chain->push_viewedge_back(*it, it.getOrientation());
163       ts(**it);
164       ++it;
165           if (it.isEnd())
166                 break;
167           if (pred(**it) < 0) {
168                 delete new_chain;
169             goto error;
170           }
171           if (pred.result)
172                 break;
173           if (pred_ts(**it) < 0) {
174                 delete new_chain;
175             goto error;
176           }
177           if (pred_ts.result)
178                 break;
179         }
180     new_chains_set.push_back(new_chain);
181   }
182   
183   if (!new_chains_set.empty()) {
184         for (I1DContainer::iterator it = new_chains_set.begin(); it != new_chains_set.end(); ++it) {
185           _current_chains_set.push_back(*it);
186         }
187         new_chains_set.clear();
188     _current_set = &_current_chains_set;
189   }
190   return 0;
191
192 error:
193   for (I1DContainer::iterator it = new_chains_set.begin(); it != new_chains_set.end(); ++it) {
194         delete (*it);
195   }
196   new_chains_set.clear();
197   return -1;
198 }
199
200
201 //void Operators::bidirectionalChain(ViewEdgeIterator& it,
202 //                                 UnaryPredicate1D& pred,
203 //                                 UnaryFunction1D_void& modifier) {
204 //  if (_current_view_edges_set.empty())
205 //    return;
206 //
207 //  unsigned id = 0;
208 //  ViewEdge* edge;
209 //  Chain* new_chain;
210 //
211 //  for (I1DContainer::iterator it_edge = _current_view_edges_set.begin();
212 //       it_edge != _current_view_edges_set.end();
213 //       ++it_edge) {
214 //    if (pred(**it_edge))
215 //      continue;
216 //
217 //    edge = dynamic_cast<ViewEdge*>(*it_edge);
218 //    it.setBegin(edge);
219 //    it.setCurrentEdge(edge);
220 //
221 //    Chain* new_chain = new Chain(id);++id;
222 //    //ViewEdgeIterator it_back(it);--it_back; // FIXME
223 //    do {
224 //      new_chain->push_viewedge_back(*it, it.getOrientation());
225 //      modifier(**it);
226 //      ++it;
227 //    } while (!it.isEnd() && !pred(**it));
228 //    it.setBegin(edge);
229 //    it.setCurrentEdge(edge);
230 //    --it;
231 //    while (!it.isEnd() && !pred(**it)) {
232 //      new_chain->push_viewedge_front(*it, it.getOrientation());
233 //      modifier(**it);
234 //      --it;
235 //    }
236 //
237 //    _current_chains_set.push_back(new_chain);
238 //  }
239 //
240 //  if (!_current_chains_set.empty())
241 //    _current_set = &_current_chains_set;
242 //}
243 //
244 //void Operators::bidirectionalChain(ViewEdgeIterator& it,
245 //                                 UnaryPredicate1D& pred) {
246 //  if (_current_view_edges_set.empty())
247 //    return;
248 //
249 //  unsigned id = 0;
250 //  Functions1D::IncrementChainingTimeStampF1D ts;
251 //  Predicates1D::EqualToChainingTimeStampUP1D pred_ts(TimeStamp::instance()->getTimeStamp()+1);
252 //
253 //  ViewEdge* edge;
254 //  Chain* new_chain;
255 //
256 //  for (I1DContainer::iterator it_edge = _current_view_edges_set.begin();
257 //       it_edge != _current_view_edges_set.end();
258 //       ++it_edge) {
259 //    if (pred(**it_edge) || pred_ts(**it_edge))
260 //      continue;
261 //
262 //    edge = dynamic_cast<ViewEdge*>(*it_edge);
263 //    it.setBegin(edge);
264 //    it.setCurrentEdge(edge);
265           //
266           //    Chain* new_chain = new Chain(id);++id;
267           //    //ViewEdgeIterator it_back(it);--it_back;//FIXME
268           //    do {
269           //      new_chain->push_viewedge_back(*it, it.getOrientation());
270           //      ts(**it);
271           //      ++it;
272           //    } while (!it.isEnd() && !pred(**it) && !pred_ts(**it));
273           //    it.setBegin(edge);
274           //    it.setCurrentEdge(edge);
275           //    --it;
276           //    while (!it.isEnd() && !pred(**it) && !pred_ts(**it)) {
277           //      new_chain->push_viewedge_front(*it, it.getOrientation());
278           //      ts(**it);
279           //      --it;
280           //    }
281           //
282           //    _current_chains_set.push_back(new_chain);
283           //  }
284           //
285           //  if (!_current_chains_set.empty())
286           //    _current_set = &_current_chains_set;
287           //}
288
289 int Operators::bidirectionalChain(ChainingIterator& it, UnaryPredicate1D& pred) {
290   if (_current_view_edges_set.empty())
291     return 0;
292
293   unsigned id = 0;
294   Functions1D::IncrementChainingTimeStampF1D ts;
295   Predicates1D::EqualToChainingTimeStampUP1D pred_ts(TimeStamp::instance()->getTimeStamp()+1);
296   ViewEdge* edge;
297   I1DContainer new_chains_set;
298
299   for (I1DContainer::iterator it_edge = _current_view_edges_set.begin();
300   it_edge != _current_view_edges_set.end();
301   ++it_edge) {
302         if (pred(**it_edge) < 0)
303           goto error;
304     if (pred.result)
305       continue;
306         if (pred_ts(**it_edge) < 0)
307           goto error;
308     if (pred_ts.result)
309       continue;
310     
311     edge = dynamic_cast<ViewEdge*>(*it_edge);
312     // re-init iterator
313     it.setBegin(edge);
314     it.setCurrentEdge(edge);
315     it.setOrientation(true);
316     if (it.init() < 0)
317           goto error;
318     
319     Chain* new_chain = new Chain(id);++id;
320     //ViewEdgeIterator it_back(it);--it_back;//FIXME
321     for (;;) {
322       new_chain->push_viewedge_back(*it, it.getOrientation());
323       ts(**it);
324           if (it.increment() < 0) {
325             delete new_chain;
326             goto error;
327           }
328           if (it.isEnd())
329                 break;
330           if (pred(**it) < 0) {
331             delete new_chain;
332             goto error;
333           }
334           if (pred.result)
335                 break;
336     }
337     it.setBegin(edge);
338     it.setCurrentEdge(edge);
339     it.setOrientation(true);
340         if (it.decrement() < 0) {
341           delete new_chain;
342           goto error;
343         }
344     while (!it.isEnd()) {
345           if (pred(**it) < 0) {
346             delete new_chain;
347             goto error;
348           }
349           if (pred.result)
350                 break;
351       new_chain->push_viewedge_front(*it, it.getOrientation());
352       ts(**it);
353           if (it.decrement() < 0) {
354             delete new_chain;
355             goto error;
356           }
357     }
358     new_chains_set.push_back(new_chain);
359   }
360   
361   if (!new_chains_set.empty()) {
362         for (I1DContainer::iterator it = new_chains_set.begin(); it != new_chains_set.end(); ++it) {
363           _current_chains_set.push_back(*it);
364         }
365         new_chains_set.clear();
366     _current_set = &_current_chains_set;
367   }
368   return 0;
369
370 error:
371   for (I1DContainer::iterator it = new_chains_set.begin(); it != new_chains_set.end(); ++it) {
372         delete (*it);
373   }
374   new_chains_set.clear();
375   return -1;
376 }
377
378 int Operators::bidirectionalChain(ChainingIterator& it) {
379   if (_current_view_edges_set.empty())
380     return 0;
381
382   unsigned id = 0;
383   Functions1D::IncrementChainingTimeStampF1D ts;
384   Predicates1D::EqualToChainingTimeStampUP1D pred_ts(TimeStamp::instance()->getTimeStamp()+1);
385   ViewEdge* edge;
386   I1DContainer new_chains_set;
387   
388   for (I1DContainer::iterator it_edge = _current_view_edges_set.begin();
389   it_edge != _current_view_edges_set.end();
390   ++it_edge) {
391     if (pred_ts(**it_edge) < 0)
392           goto error;
393         if (pred_ts.result)
394       continue;
395     
396     edge = dynamic_cast<ViewEdge*>(*it_edge);
397     // re-init iterator
398     it.setBegin(edge);
399     it.setCurrentEdge(edge);
400     it.setOrientation(true);
401     if (it.init() < 0)
402           goto error;
403     
404     Chain* new_chain = new Chain(id);++id;
405     //ViewEdgeIterator it_back(it);--it_back;//FIXME
406     do {
407       new_chain->push_viewedge_back(*it, it.getOrientation());
408       ts(**it);
409           if (it.increment() < 0) { // FIXME
410                 delete new_chain;
411             goto error;
412           }
413     } while (!it.isEnd());
414     it.setBegin(edge);
415     it.setCurrentEdge(edge);
416     it.setOrientation(true);
417         if (it.decrement() < 0) { // FIXME
418           delete new_chain;
419           goto error;
420         }
421     while (!it.isEnd()) {
422       new_chain->push_viewedge_front(*it, it.getOrientation());
423       ts(**it);
424           if (it.decrement() < 0) { // FIXME
425                 delete new_chain;
426             goto error;
427           }
428     }
429     new_chains_set.push_back(new_chain);
430   }
431   
432   if (!new_chains_set.empty()) {
433         for (I1DContainer::iterator it = new_chains_set.begin(); it != new_chains_set.end(); ++it) {
434           _current_chains_set.push_back(*it);
435         }
436         new_chains_set.clear();
437     _current_set = &_current_chains_set;
438   }
439   return 0;
440
441 error:
442   for (I1DContainer::iterator it = new_chains_set.begin(); it != new_chains_set.end(); ++it) {
443         delete (*it);
444   }
445   new_chains_set.clear();
446   return -1;
447 }
448
449 int Operators::sequentialSplit(UnaryPredicate0D& pred, 
450                                 float sampling)
451 {
452   if (_current_chains_set.empty()) {
453     cerr << "Warning: current set empty" << endl;
454     return 0;
455   }
456   CurvePoint *point;
457   Chain * new_curve;
458   I1DContainer splitted_chains;
459   Interface0DIterator first;
460   Interface0DIterator end;
461   Interface0DIterator last;
462   Interface0DIterator it;
463   I1DContainer::iterator cit = _current_chains_set.begin(), citend = _current_chains_set.end();
464   for (;
465        cit != citend;
466        ++cit) {
467     
468     Id currentId = (*cit)->getId();
469     new_curve = new Chain(currentId);
470     first = (*cit)->pointsBegin(sampling);
471     end = (*cit)->pointsEnd(sampling);
472     last = end;--last;
473     it = first;
474
475     point = dynamic_cast<CurvePoint*>(&(*it));
476     new_curve->push_vertex_back(point);++it;
477     for(; it!= end; ++it)
478       {
479         point = dynamic_cast<CurvePoint*>(&(*it));
480         new_curve->push_vertex_back(point);
481                 if(pred(it) < 0)
482                   {
483                         delete new_curve;
484                         goto error;
485                   }
486         if(pred.result && (it!=last))
487           {
488             splitted_chains.push_back(new_curve);
489             currentId.setSecond(currentId.getSecond()+1);
490             new_curve = new Chain(currentId);
491             new_curve->push_vertex_back(point);
492           }
493       }
494     if(new_curve->nSegments() == 0){
495       delete new_curve;
496       return 0;
497     }
498
499     splitted_chains.push_back(new_curve);
500   }
501
502   // Update the current set of chains:
503   cit = _current_chains_set.begin();
504   for(;
505       cit != citend;
506       ++cit){
507     delete (*cit);
508   }
509   _current_chains_set.clear();
510 #if 0
511   _current_chains_set = splitted_chains;
512 #else
513   for (cit = splitted_chains.begin(), citend = splitted_chains.end();
514            cit != citend;
515            ++cit) {
516         if ((*cit)->getLength2D() < M_EPSILON) {
517           delete (*cit);
518           continue;
519         }
520     _current_chains_set.push_back(*cit);
521   }
522 #endif
523   splitted_chains.clear();
524
525   if (!_current_chains_set.empty())
526     _current_set = &_current_chains_set;
527   return 0;
528
529 error:
530   cit = splitted_chains.begin();
531   citend = splitted_chains.end();
532   for(;
533   cit != citend;
534   ++cit){
535     delete (*cit);
536   }
537   splitted_chains.clear();
538   return -1;
539 }
540
541 int Operators::sequentialSplit(UnaryPredicate0D& startingPred, UnaryPredicate0D& stoppingPred, 
542                                 float sampling)
543 {
544   if (_current_chains_set.empty()) {
545     cerr << "Warning: current set empty" << endl;
546     return 0;
547   }
548   CurvePoint *point;
549   Chain * new_curve;
550   I1DContainer splitted_chains;
551   Interface0DIterator first;
552   Interface0DIterator end;
553   Interface0DIterator last;
554   Interface0DIterator itStart;
555   Interface0DIterator itStop;
556   I1DContainer::iterator cit = _current_chains_set.begin(), citend = _current_chains_set.end();
557   for (;
558   cit != citend;
559   ++cit) {
560     Id currentId = (*cit)->getId();
561     first = (*cit)->pointsBegin(sampling);
562     end = (*cit)->pointsEnd(sampling);
563     last = end;--last;
564     itStart = first;
565     do{
566       itStop = itStart;++itStop;
567       
568       new_curve = new Chain(currentId);
569       currentId.setSecond(currentId.getSecond()+1);
570       
571       point = dynamic_cast<CurvePoint*>(&(*itStart));
572       new_curve->push_vertex_back(point);    
573       do{
574         point = dynamic_cast<CurvePoint*>(&(*itStop));
575         new_curve->push_vertex_back(point);    
576         ++itStop;
577                 if(itStop == end)
578                   break;
579                 if(stoppingPred(itStop) < 0){
580                   delete new_curve;
581                   goto error;
582                 }
583       }while(!stoppingPred.result);
584       if(itStop!=end){
585         point = dynamic_cast<CurvePoint*>(&(*itStop));
586         new_curve->push_vertex_back(point);    
587       }
588       if(new_curve->nSegments() == 0){
589         delete new_curve;
590       }else{
591         splitted_chains.push_back(new_curve);
592       }
593       // find next start
594       do{
595         ++itStart;
596                 if(itStart == end)
597                   break;
598                 if(startingPred(itStart) < 0)
599                   goto error;
600       }while(!startingPred.result);
601     }while((itStart!=end) && (itStart!=last));
602   }
603   
604   // Update the current set of chains:
605   cit = _current_chains_set.begin();
606   for(;
607   cit != citend;
608   ++cit){
609     delete (*cit);
610   }
611   _current_chains_set.clear();
612 #if 0
613   _current_chains_set = splitted_chains;
614 #else
615   for (cit = splitted_chains.begin(), citend = splitted_chains.end();
616            cit != citend;
617            ++cit) {
618         if ((*cit)->getLength2D() < M_EPSILON) {
619           delete (*cit);
620           continue;
621         }
622     _current_chains_set.push_back(*cit);
623   }
624 #endif
625   splitted_chains.clear();
626   
627   if (!_current_chains_set.empty())
628     _current_set = &_current_chains_set;
629   return 0;
630
631 error:
632   cit = splitted_chains.begin();
633   citend = splitted_chains.end();
634   for(;
635   cit != citend;
636   ++cit){
637     delete (*cit);
638   }
639   splitted_chains.clear();
640   return -1;
641 }
642
643 #include "CurveIterators.h"
644
645 // Internal function
646 int __recursiveSplit(Chain *_curve, UnaryFunction0D<double>& func, UnaryPredicate1D& pred, float sampling,
647                       Operators::I1DContainer& newChains, Operators::I1DContainer& splitted_chains)
648 {
649   if(((_curve->nSegments() == 1) && (sampling == 0)) || (_curve->getLength2D() <= sampling)){
650     newChains.push_back(_curve);
651     return 0;
652   }
653
654   CurveInternal::CurvePointIterator first             = _curve->curvePointsBegin(sampling);
655   CurveInternal::CurvePointIterator second            = first; ++second;
656   CurveInternal::CurvePointIterator end               = _curve->curvePointsEnd(sampling);
657   CurveInternal::CurvePointIterator it                = second;
658   CurveInternal::CurvePointIterator split             = second;
659   Interface0DIterator it0d                            = it.castToInterface0DIterator();
660   real _min                                           = FLT_MAX;++it;//func(it0d);++it;
661   CurveInternal::CurvePointIterator next              = it;++next;
662   
663   bool bsplit = false;
664   for(; ((it != end) && (next != end)); ++it,++next){
665     it0d = it.castToInterface0DIterator();
666         if (func(it0d) < 0)
667           return -1;
668     if(func.result < _min){
669       _min = func.result;
670       split = it;
671       bsplit = true;
672     }
673   }
674   
675   if(!bsplit){ // we didn't find any minimum
676     newChains.push_back(_curve);
677     return 0;
678   }
679
680   // retrieves the current splitting id
681   Id * newId = _curve->getSplittingId();
682   if(newId == 0){
683     newId = new Id(_curve->getId());
684     _curve->setSplittingId(newId);
685   } 
686
687   Chain *new_curve_a = new Chain(*newId);
688   newId->setSecond(newId->getSecond()+1);
689   new_curve_a->setSplittingId(newId);
690   Chain *new_curve_b = new Chain(*newId);
691   newId->setSecond(newId->getSecond()+1);
692   new_curve_b->setSplittingId(newId);
693   
694   CurveInternal::CurvePointIterator vit = _curve->curveVerticesBegin(), vitend=_curve->curveVerticesEnd();
695   CurveInternal::CurvePointIterator vnext = vit; ++vnext;
696
697   
698   for(; (vit!=vitend)&&(vnext!=vitend)&&(vnext._CurvilinearLength<split._CurvilinearLength); ++vit,++vnext){
699     new_curve_a->push_vertex_back(&(*vit));
700   }
701   if((vit==vitend) || (vnext == vitend)){
702     cout << "The split takes place in bad location" << endl;
703     newChains.push_back(_curve);
704     delete new_curve_a;
705     delete new_curve_b;
706     return 0;
707   }
708
709   // build the two resulting chains
710   new_curve_a->push_vertex_back(&(*vit));
711   new_curve_a->push_vertex_back(&(*split));
712   new_curve_b->push_vertex_back(&(*split));
713
714   for(vit=vnext;vit!=vitend;++vit)
715     new_curve_b->push_vertex_back(&(*vit));
716   
717   // let's check whether one or two of the two new curves 
718   // satisfy the stopping condition or not.
719   // (if one of them satisfies it, we don't split)
720   if (pred(*new_curve_a) < 0 || (!pred.result && pred(*new_curve_b) < 0)) {
721     delete new_curve_a;
722     delete new_curve_b;
723         return -1;
724   }
725   if(pred.result){
726     // we don't actually create these two chains
727     newChains.push_back(_curve);
728     delete new_curve_a;
729     delete new_curve_b;
730     return 0;
731   }
732   // here we know we'll split _curve:
733   splitted_chains.push_back(_curve);
734
735   __recursiveSplit(new_curve_a, func, pred, sampling, newChains, splitted_chains);
736   __recursiveSplit(new_curve_b, func, pred, sampling, newChains, splitted_chains);
737   return 0;
738 }
739
740 int Operators::recursiveSplit(UnaryFunction0D<double>& func, UnaryPredicate1D& pred, float sampling)
741 {
742   if (_current_chains_set.empty()) {
743     cerr << "Warning: current set empty" << endl;
744     return 0;
745   }
746
747   Chain *currentChain = 0;
748   I1DContainer splitted_chains;
749   I1DContainer newChains;
750   I1DContainer::iterator cit = _current_chains_set.begin(), citend = _current_chains_set.end();
751   for (;
752        cit != citend;
753        ++cit) {
754     currentChain = dynamic_cast<Chain*>(*cit);
755     if(!currentChain)
756       continue;
757     // let's check the first one:
758         if (pred(*currentChain) < 0)
759           return -1;
760     if(!pred.result){
761       __recursiveSplit(currentChain, func, pred, sampling, newChains, splitted_chains);
762     }else{
763       newChains.push_back(currentChain);
764     }
765   }
766   // Update the current set of chains:
767   if(!splitted_chains.empty()){
768     for(cit = splitted_chains.begin(), citend = splitted_chains.end();
769         cit != citend;
770         ++cit){
771       delete (*cit);
772     } 
773   splitted_chains.clear();
774   } 
775   
776   _current_chains_set.clear();
777 #if 0
778   _current_chains_set = newChains;
779 #else
780   for (cit = newChains.begin(), citend = newChains.end();
781            cit != citend;
782            ++cit) {
783         if ((*cit)->getLength2D() < M_EPSILON) {
784           delete (*cit);
785           continue;
786         }
787     _current_chains_set.push_back(*cit);
788   }
789 #endif
790   newChains.clear();
791
792   if (!_current_chains_set.empty())
793     _current_set = &_current_chains_set;
794   return 0;
795 }
796
797
798 // recursive split with pred 0D
799 int __recursiveSplit(Chain *_curve, UnaryFunction0D<double>& func, UnaryPredicate0D& pred0d, UnaryPredicate1D& pred, float sampling,
800                       Operators::I1DContainer& newChains, Operators::I1DContainer& splitted_chains)
801 {
802   if(((_curve->nSegments() == 1) && (sampling == 0)) || (_curve->getLength2D() <= sampling)){
803     newChains.push_back(_curve);
804     return 0;
805   }
806
807   CurveInternal::CurvePointIterator first             = _curve->curvePointsBegin(sampling);
808   CurveInternal::CurvePointIterator second            = first; ++second;
809   CurveInternal::CurvePointIterator end               = _curve->curvePointsEnd(sampling);
810   CurveInternal::CurvePointIterator it                = second;
811   CurveInternal::CurvePointIterator split             = second;
812   Interface0DIterator it0d                            = it.castToInterface0DIterator();
813   //real _min                                           = func(it0d);++it;
814   real _min                                           = FLT_MAX;++it;
815   real mean                                           = 0.f;
816   //soc unused - real variance                                       = 0.f;
817   unsigned count                                      = 0;
818   CurveInternal::CurvePointIterator next              = it;++next;
819   
820   bool bsplit = false;
821   for(; ((it != end) && (next != end)); ++it,++next){
822     ++count;
823     it0d = it.castToInterface0DIterator();
824         if(pred0d(it0d) < 0)
825           return -1;
826     if(!pred0d.result)
827       continue;
828         if(func(it0d) < 0)
829           return -1;
830     mean += func.result;
831     if(func.result < _min){
832       _min = func.result;
833       split = it;
834       bsplit = true;
835     }
836   }
837   mean /= (float)count;
838
839   //if((!bsplit) || (mean-_min>mean)){ // we didn't find any minimum
840   if(!bsplit){ // we didn't find any minimum
841     newChains.push_back(_curve);
842     return 0;
843   }
844
845   // retrieves the current splitting id
846   Id * newId = _curve->getSplittingId();
847   if(newId == 0){
848     newId = new Id(_curve->getId());
849     _curve->setSplittingId(newId);
850   } 
851
852   Chain *new_curve_a = new Chain(*newId);
853   newId->setSecond(newId->getSecond()+1);
854   new_curve_a->setSplittingId(newId);
855   Chain *new_curve_b = new Chain(*newId);
856   newId->setSecond(newId->getSecond()+1);
857   new_curve_b->setSplittingId(newId);
858   
859   CurveInternal::CurvePointIterator vit = _curve->curveVerticesBegin(), vitend=_curve->curveVerticesEnd();
860   CurveInternal::CurvePointIterator vnext = vit; ++vnext;
861
862   
863   for(; (vit!=vitend)&&(vnext!=vitend)&&(vnext._CurvilinearLength<split._CurvilinearLength); ++vit,++vnext){
864     new_curve_a->push_vertex_back(&(*vit));
865   }
866   if((vit==vitend) || (vnext == vitend)){
867     cout << "The split takes place in bad location" << endl;
868     newChains.push_back(_curve);
869     delete new_curve_a;
870     delete new_curve_b;
871     return 0;
872   }
873
874   // build the two resulting chains
875   new_curve_a->push_vertex_back(&(*vit));
876   new_curve_a->push_vertex_back(&(*split));
877   new_curve_b->push_vertex_back(&(*split));
878
879   for(vit=vnext;vit!=vitend;++vit)
880     new_curve_b->push_vertex_back(&(*vit));
881   
882   // let's check whether one or two of the two new curves 
883   // satisfy the stopping condition or not.
884   // (if one of them satisfies it, we don't split)
885   if (pred(*new_curve_a) < 0 || (!pred.result && pred(*new_curve_b) < 0)) {
886     delete new_curve_a;
887     delete new_curve_b;
888     return -1;
889   }
890   if(pred.result){
891     // we don't actually create these two chains
892     newChains.push_back(_curve);
893     delete new_curve_a;
894     delete new_curve_b;
895     return 0;
896   }
897   // here we know we'll split _curve:
898   splitted_chains.push_back(_curve);
899
900   __recursiveSplit(new_curve_a, func, pred0d, pred, sampling, newChains, splitted_chains);
901   __recursiveSplit(new_curve_b, func, pred0d, pred, sampling, newChains, splitted_chains);
902   return 0;
903 }
904
905 int Operators::recursiveSplit(UnaryFunction0D<double>& func, UnaryPredicate0D& pred0d,  UnaryPredicate1D& pred, float sampling)
906 {
907   if (_current_chains_set.empty()) {
908     cerr << "Warning: current set empty" << endl;
909     return 0;
910   }
911
912   Chain *currentChain = 0;
913   I1DContainer splitted_chains;
914   I1DContainer newChains;
915   I1DContainer::iterator cit = _current_chains_set.begin(), citend = _current_chains_set.end();
916   for (;
917        cit != citend;
918        ++cit) {
919     currentChain = dynamic_cast<Chain*>(*cit);
920     if(!currentChain)
921       continue;
922     // let's check the first one:
923         if(pred(*currentChain) < 0)
924           return -1;
925     if(!pred.result){
926       __recursiveSplit(currentChain, func, pred0d, pred, sampling, newChains, splitted_chains);
927     }else{
928       newChains.push_back(currentChain);
929     }
930   }
931   // Update the current set of chains:
932   if(!splitted_chains.empty()){
933     for(cit = splitted_chains.begin(), citend = splitted_chains.end();
934         cit != citend;
935         ++cit){
936       delete (*cit);
937     } 
938   splitted_chains.clear();
939   } 
940   
941   _current_chains_set.clear();
942 #if 0
943   _current_chains_set = newChains;
944 #else
945   for (cit = newChains.begin(), citend = newChains.end();
946            cit != citend;
947            ++cit) {
948         if ((*cit)->getLength2D() < M_EPSILON) {
949           delete (*cit);
950           continue;
951         }
952     _current_chains_set.push_back(*cit);
953   }
954 #endif
955   newChains.clear();
956
957   if (!_current_chains_set.empty())
958     _current_set = &_current_chains_set;
959   return 0;
960 }
961 // Internal class
962 class PredicateWrapper
963 {
964 public:
965
966   inline PredicateWrapper(BinaryPredicate1D& pred) {
967     _pred = &pred;
968   }
969
970   inline bool operator()(Interface1D* i1, Interface1D* i2) {
971         if ((*_pred)(*i1, *i2) < 0)
972                 throw std::runtime_error("comparison failed");
973     return _pred->result;
974   }
975
976 private:
977
978   BinaryPredicate1D* _pred;
979 };
980
981 int Operators::sort(BinaryPredicate1D& pred) {
982   if (!_current_set)
983     return 0;
984   PredicateWrapper wrapper(pred);
985   try {
986         std::sort(_current_set->begin(), _current_set->end(), wrapper);
987   }
988   catch (std::runtime_error &e) {
989         cerr << "Warning: Operator.sort(): " << e.what() << endl;
990         return -1;
991   }
992   return 0;
993 }
994
995 Stroke* createStroke(Interface1D& inter) {
996   Stroke* stroke = new Stroke;
997   stroke->setId(inter.getId());
998
999   float currentCurvilignAbscissa = 0.f;
1000
1001   Interface0DIterator it = inter.verticesBegin(), itend = inter.verticesEnd();
1002   Interface0DIterator itfirst = it;
1003
1004   Vec2r current(it->getPoint2D());
1005   Vec2r previous = current;
1006   SVertex* sv;
1007   CurvePoint* cp;
1008   StrokeVertex* stroke_vertex = NULL;  
1009   bool hasSingularity = false;
1010
1011   do {
1012     cp = dynamic_cast<CurvePoint*>(&(*it));
1013     if (!cp) {
1014       sv = dynamic_cast<SVertex*>(&(*it));
1015       if (!sv) {
1016   cerr << "Warning: unexpected Vertex type" << endl;
1017   continue;
1018       }
1019       stroke_vertex = new StrokeVertex(sv);
1020     }
1021     else
1022       stroke_vertex = new StrokeVertex(cp);
1023     current = stroke_vertex->getPoint2D();
1024     Vec2r vec_tmp(current - previous);
1025   real dist = vec_tmp.norm();
1026   if (dist < 1e-6) hasSingularity = true;
1027   currentCurvilignAbscissa += dist;
1028   stroke_vertex->setCurvilinearAbscissa(currentCurvilignAbscissa);
1029   stroke->push_back(stroke_vertex);
1030   previous = current;
1031     ++it;
1032   } while((it != itend) && (it != itfirst));
1033
1034   if (it == itfirst) {
1035     // Add last vertex:
1036     cp = dynamic_cast<CurvePoint*>(&(*it));
1037     if (!cp) {
1038       sv = dynamic_cast<SVertex*>(&(*it));
1039       if (!sv)
1040   cerr << "Warning: unexpected Vertex type" << endl;
1041       else
1042   stroke_vertex = new StrokeVertex(sv);
1043     }
1044     else
1045       stroke_vertex = new StrokeVertex(cp);
1046     current = stroke_vertex->getPoint2D();
1047     Vec2r vec_tmp(current - previous);
1048   real dist = vec_tmp.norm();
1049   if (dist < 1e-6) hasSingularity = true;
1050   currentCurvilignAbscissa += dist;
1051     stroke_vertex->setCurvilinearAbscissa(currentCurvilignAbscissa);
1052     stroke->push_back(stroke_vertex);
1053   }
1054   // Discard the stroke if the number of stroke vertices is less than two
1055   if (stroke->strokeVerticesSize() < 2) {
1056     delete stroke;
1057     return NULL;
1058   }
1059   stroke->setLength(currentCurvilignAbscissa);
1060   if (hasSingularity) {
1061     // Try to address singular points such that the distance between two
1062     // subsequent vertices are smaller than epsilon.
1063     Interface0DIterator v = stroke->verticesBegin();
1064     Interface0DIterator vnext = v; ++vnext;
1065     Vec2r next((*v).getPoint2D());
1066     while (!vnext.isEnd()) {
1067       current = next;
1068       next = (*vnext).getPoint2D();
1069       if ((next - current).norm() < 1e-6) {
1070         Interface0DIterator vprevious = v;
1071         if (!vprevious.isBegin())
1072           --vprevious;
1073
1074         // collect a set of overlapping vertices (except the first one)
1075         std::vector<Interface0D *> overlapping_vertices;
1076         do {
1077           overlapping_vertices.push_back(&(*vnext));
1078           current = next;
1079           ++v; ++vnext;
1080           if (vnext.isEnd())
1081             break;
1082           next = (*vnext).getPoint2D();
1083         } while ((next - current).norm() < 1e-6);
1084
1085         Vec2r target;
1086         bool reverse;
1087         if (!vnext.isEnd()) {
1088           target = (*vnext).getPoint2D();
1089           reverse = false;
1090         } else if (!vprevious.isBegin()) {
1091           target = (*vprevious).getPoint2D();
1092           reverse = true;
1093         } else {
1094           // Discard the stroke because all stroke vertices are overlapping
1095           delete stroke;
1096           return NULL;
1097         }
1098         Vec2r dir(target - current);
1099         real dist = dir.norm();
1100         real len = 1e-3; // default offset length
1101         int nvert = overlapping_vertices.size();
1102         if (dist < len * nvert) {
1103           len = dist / (nvert + 1);
1104         }
1105         dir.normalize();
1106         Vec2r offset(dir * len);
1107         //cout << "#vert " << nvert << " len " << len << " reverse? " << reverse << endl;
1108
1109         // add the offset to the overlapping vertices
1110         StrokeVertex* sv;
1111         std::vector<Interface0D *>::iterator it = overlapping_vertices.begin(),
1112           itend = overlapping_vertices.end();
1113         if (!reverse) {
1114           int n = 1;
1115           for (; it != itend; ++it) {
1116             sv = dynamic_cast<StrokeVertex*>(*it);
1117             sv->setPoint(sv->getPoint() + offset * n);
1118             ++n;
1119           }
1120         } else {
1121           int n = nvert;
1122           for (; it != itend; ++it) {
1123             sv = dynamic_cast<StrokeVertex*>(*it);
1124             sv->setPoint(sv->getPoint() + offset * n);
1125             --n;
1126           }
1127         }
1128
1129         if (vnext.isEnd())
1130           break;
1131       }
1132       ++v; ++vnext;
1133     }
1134   }
1135   {
1136     // Check if the stroke no longer contains singular points
1137     Interface0DIterator v = stroke->verticesBegin();
1138     Interface0DIterator vnext = v; ++vnext;
1139     Vec2r next((*v).getPoint2D());
1140     bool warning = false;
1141     while (!vnext.isEnd()) {
1142       current = next;
1143       next = (*vnext).getPoint2D();
1144       if ((next - current).norm() < 1e-6) {
1145         warning = true;
1146         break;
1147       }
1148       ++v; ++vnext;
1149     }
1150     if (warning) {
1151       printf("Warning: stroke contains singular points.\n");
1152     }
1153   }
1154   return stroke;
1155 }
1156
1157
1158 inline int applyShading(Stroke& stroke, vector<StrokeShader*>& shaders) {
1159   for (vector<StrokeShader*>::iterator it = shaders.begin(); it != shaders.end(); ++it) {
1160     if ((*it)->shade(stroke) < 0) {
1161           return -1;
1162         }
1163   }
1164   return 0;
1165 }
1166
1167
1168 int Operators::create(UnaryPredicate1D& pred, vector<StrokeShader*> shaders) {
1169   //Canvas* canvas = Canvas::getInstance();
1170   if (!_current_set) {
1171     cerr << "Warning: current set empty" << endl;
1172     return 0;
1173   }
1174   StrokesContainer new_strokes_set;
1175   for (Operators::I1DContainer::iterator it = _current_set->begin();
1176        it != _current_set->end();
1177        ++it) {
1178         if (pred(**it) < 0)
1179           goto error;
1180     if (!pred.result)
1181       continue;
1182         
1183         Stroke* stroke = createStroke(**it);
1184     if (stroke) {
1185           if (applyShading(*stroke, shaders) < 0) {
1186                   delete stroke;
1187                   goto error;
1188           }
1189       //canvas->RenderStroke(stroke);
1190       new_strokes_set.push_back(stroke);
1191     }
1192   }
1193   
1194   for (StrokesContainer::iterator it = new_strokes_set.begin(); it != new_strokes_set.end(); ++it) {
1195     _current_strokes_set.push_back(*it);
1196   }
1197   new_strokes_set.clear();
1198   return 0;
1199
1200 error:
1201   for (StrokesContainer::iterator it = new_strokes_set.begin(); it != new_strokes_set.end(); ++it) {
1202         delete (*it);
1203   }
1204   new_strokes_set.clear();
1205   return -1;
1206 }
1207
1208
1209 void Operators::reset() {
1210   ViewMap* vm = ViewMap::getInstance();
1211   if (!vm) {
1212     cerr << "Error: no ViewMap computed yet" << endl;
1213     return;
1214   }
1215   _current_view_edges_set.clear();
1216   for (I1DContainer::iterator it = _current_chains_set.begin();
1217        it != _current_chains_set.end();
1218        ++it)
1219     delete *it;
1220   _current_chains_set.clear();
1221 #if 0
1222   _current_view_edges_set.insert(_current_view_edges_set.begin(),
1223                                  vm->ViewEdges().begin(),
1224                                  vm->ViewEdges().end());
1225 #else
1226   ViewMap::viewedges_container& vedges = vm->ViewEdges();
1227   ViewMap::viewedges_container::iterator ve=vedges.begin(), veend=vedges.end();
1228   for (; ve != veend; ++ve) {
1229     if ((*ve)->getLength2D() < M_EPSILON)
1230       continue;
1231     _current_view_edges_set.push_back(*ve);
1232   }
1233 #endif
1234   _current_set = &_current_view_edges_set;
1235   _current_strokes_set.clear();
1236 }