Merged changes in the trunk up to revision 28600.
[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   //soc unused - Chain* new_chain;
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           return -1;
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                 return -1;
101           }
102       ++it;
103           if (it.isEnd())
104                 break;
105           if (pred(**it) < 0) {
106                 delete new_chain;
107                 return -1;
108           }
109           if (pred.result)
110             break;
111         }
112
113     _current_chains_set.push_back(new_chain);
114   }
115
116   if (!_current_chains_set.empty())
117     _current_set = &_current_chains_set;
118   return 0;
119 }
120
121
122 int Operators::chain(ViewEdgeInternal::ViewEdgeIterator& it,
123                       UnaryPredicate1D& pred) {
124   if (_current_view_edges_set.empty())
125     return 0;
126
127   unsigned id = 0;
128   Functions1D::IncrementChainingTimeStampF1D ts;
129   Predicates1D::EqualToChainingTimeStampUP1D pred_ts(TimeStamp::instance()->getTimeStamp()+1);
130
131   ViewEdge* edge;
132   //soc Chain* new_chain;
133
134   for (I1DContainer::iterator it_edge = _current_view_edges_set.begin();
135        it_edge != _current_view_edges_set.end();
136        ++it_edge) {
137         if (pred(**it_edge) < 0)
138           return -1;
139     if (pred.result)
140           continue;
141         if (pred_ts(**it_edge) < 0)
142           return -1;
143         if (pred_ts.result)
144       continue;
145
146     edge = dynamic_cast<ViewEdge*>(*it_edge);
147     it.setBegin(edge);
148     it.setCurrentEdge(edge);
149
150     Chain* new_chain = new Chain(id);++id;
151     for (;;) {
152       new_chain->push_viewedge_back(*it, it.getOrientation());
153       ts(**it);
154       ++it;
155           if (it.isEnd())
156                 break;
157           if (pred(**it) < 0) {
158                 delete new_chain;
159                 return -1;
160           }
161           if (pred.result)
162                 break;
163           if (pred_ts(**it) < 0) {
164                 delete new_chain;
165                 return -1;
166           }
167           if (pred_ts.result)
168                 break;
169         }
170
171     _current_chains_set.push_back(new_chain);
172   }
173
174   if (!_current_chains_set.empty())
175     _current_set = &_current_chains_set;
176   return 0;
177 }
178
179
180 //void Operators::bidirectionalChain(ViewEdgeIterator& it,
181 //                                 UnaryPredicate1D& pred,
182 //                                 UnaryFunction1D_void& modifier) {
183 //  if (_current_view_edges_set.empty())
184 //    return;
185 //
186 //  unsigned id = 0;
187 //  ViewEdge* edge;
188 //  Chain* new_chain;
189 //
190 //  for (I1DContainer::iterator it_edge = _current_view_edges_set.begin();
191 //       it_edge != _current_view_edges_set.end();
192 //       ++it_edge) {
193 //    if (pred(**it_edge))
194 //      continue;
195 //
196 //    edge = dynamic_cast<ViewEdge*>(*it_edge);
197 //    it.setBegin(edge);
198 //    it.setCurrentEdge(edge);
199 //
200 //    Chain* new_chain = new Chain(id);++id;
201 //    //ViewEdgeIterator it_back(it);--it_back; // FIXME
202 //    do {
203 //      new_chain->push_viewedge_back(*it, it.getOrientation());
204 //      modifier(**it);
205 //      ++it;
206 //    } while (!it.isEnd() && !pred(**it));
207 //    it.setBegin(edge);
208 //    it.setCurrentEdge(edge);
209 //    --it;
210 //    while (!it.isEnd() && !pred(**it)) {
211 //      new_chain->push_viewedge_front(*it, it.getOrientation());
212 //      modifier(**it);
213 //      --it;
214 //    }
215 //
216 //    _current_chains_set.push_back(new_chain);
217 //  }
218 //
219 //  if (!_current_chains_set.empty())
220 //    _current_set = &_current_chains_set;
221 //}
222 //
223 //void Operators::bidirectionalChain(ViewEdgeIterator& it,
224 //                                 UnaryPredicate1D& pred) {
225 //  if (_current_view_edges_set.empty())
226 //    return;
227 //
228 //  unsigned id = 0;
229 //  Functions1D::IncrementChainingTimeStampF1D ts;
230 //  Predicates1D::EqualToChainingTimeStampUP1D pred_ts(TimeStamp::instance()->getTimeStamp()+1);
231 //
232 //  ViewEdge* edge;
233 //  Chain* new_chain;
234 //
235 //  for (I1DContainer::iterator it_edge = _current_view_edges_set.begin();
236 //       it_edge != _current_view_edges_set.end();
237 //       ++it_edge) {
238 //    if (pred(**it_edge) || pred_ts(**it_edge))
239 //      continue;
240 //
241 //    edge = dynamic_cast<ViewEdge*>(*it_edge);
242 //    it.setBegin(edge);
243 //    it.setCurrentEdge(edge);
244           //
245           //    Chain* new_chain = new Chain(id);++id;
246           //    //ViewEdgeIterator it_back(it);--it_back;//FIXME
247           //    do {
248           //      new_chain->push_viewedge_back(*it, it.getOrientation());
249           //      ts(**it);
250           //      ++it;
251           //    } while (!it.isEnd() && !pred(**it) && !pred_ts(**it));
252           //    it.setBegin(edge);
253           //    it.setCurrentEdge(edge);
254           //    --it;
255           //    while (!it.isEnd() && !pred(**it) && !pred_ts(**it)) {
256           //      new_chain->push_viewedge_front(*it, it.getOrientation());
257           //      ts(**it);
258           //      --it;
259           //    }
260           //
261           //    _current_chains_set.push_back(new_chain);
262           //  }
263           //
264           //  if (!_current_chains_set.empty())
265           //    _current_set = &_current_chains_set;
266           //}
267
268 int Operators::bidirectionalChain(ChainingIterator& it, UnaryPredicate1D& pred) {
269   if (_current_view_edges_set.empty())
270     return 0;
271
272   unsigned id = 0;
273   Functions1D::IncrementChainingTimeStampF1D ts;
274   Predicates1D::EqualToChainingTimeStampUP1D pred_ts(TimeStamp::instance()->getTimeStamp()+1);
275   
276   ViewEdge* edge;
277   //soc unused - Chain* new_chain;
278   
279   for (I1DContainer::iterator it_edge = _current_view_edges_set.begin();
280   it_edge != _current_view_edges_set.end();
281   ++it_edge) {
282         if (pred(**it_edge) < 0)
283           return -1;
284     if (pred.result)
285       continue;
286         if (pred_ts(**it_edge) < 0)
287           return -1;
288     if (pred_ts.result)
289       continue;
290     
291     edge = dynamic_cast<ViewEdge*>(*it_edge);
292     // re-init iterator
293     it.setBegin(edge);
294     it.setCurrentEdge(edge);
295     it.setOrientation(true);
296     if (it.init() < 0)
297           return -1;
298     
299     Chain* new_chain = new Chain(id);++id;
300     //ViewEdgeIterator it_back(it);--it_back;//FIXME
301     for (;;) {
302       new_chain->push_viewedge_back(*it, it.getOrientation());
303       ts(**it);
304           if (it.increment() < 0) { // FIXME
305             delete new_chain;
306                 return -1;
307           }
308           if (it.isEnd())
309                 break;
310           if (pred(**it) < 0) {
311             delete new_chain;
312                 return -1;
313           }
314           if (pred.result)
315                 break;
316     }
317     it.setBegin(edge);
318     it.setCurrentEdge(edge);
319     it.setOrientation(true);
320         if (it.decrement() < 0) { // FIXME
321           delete new_chain;
322           return -1;
323         }
324     while (!it.isEnd()) {
325           if (pred(**it) < 0) {
326             delete new_chain;
327                 return -1;
328           }
329           if (pred.result)
330                 break;
331       new_chain->push_viewedge_front(*it, it.getOrientation());
332       ts(**it);
333           if (it.decrement() < 0) { // FIXME
334             delete new_chain;
335                 return -1;
336           }
337     }
338     _current_chains_set.push_back(new_chain);
339   }
340   
341   if (!_current_chains_set.empty())
342     _current_set = &_current_chains_set;
343   return 0;
344 }
345
346 int Operators::bidirectionalChain(ChainingIterator& it) {
347   if (_current_view_edges_set.empty())
348     return 0;
349
350   unsigned id = 0;
351   Functions1D::IncrementChainingTimeStampF1D ts;
352   Predicates1D::EqualToChainingTimeStampUP1D pred_ts(TimeStamp::instance()->getTimeStamp()+1);
353   
354   ViewEdge* edge;
355   //soc unused - Chain* new_chain;
356   
357   for (I1DContainer::iterator it_edge = _current_view_edges_set.begin();
358   it_edge != _current_view_edges_set.end();
359   ++it_edge) {
360     if (pred_ts(**it_edge) < 0)
361           return -1;
362         if (pred_ts.result)
363       continue;
364     
365     edge = dynamic_cast<ViewEdge*>(*it_edge);
366     // re-init iterator
367     it.setBegin(edge);
368     it.setCurrentEdge(edge);
369     it.setOrientation(true);
370     if (it.init() < 0)
371           return -1;
372     
373     Chain* new_chain = new Chain(id);++id;
374     //ViewEdgeIterator it_back(it);--it_back;//FIXME
375     do {
376       new_chain->push_viewedge_back(*it, it.getOrientation());
377       ts(**it);
378           if (it.increment() < 0) { // FIXME
379                 delete new_chain;
380                 return -1;
381           }
382     } while (!it.isEnd());
383     it.setBegin(edge);
384     it.setCurrentEdge(edge);
385     it.setOrientation(true);
386         if (it.decrement() < 0) { // FIXME
387           delete new_chain;
388           return -1;
389         }
390     while (!it.isEnd()) {
391       new_chain->push_viewedge_front(*it, it.getOrientation());
392       ts(**it);
393           if (it.decrement() < 0) { // FIXME
394                 delete new_chain;
395                 return -1;
396           }
397     }
398     _current_chains_set.push_back(new_chain);
399   }
400   
401   if (!_current_chains_set.empty())
402     _current_set = &_current_chains_set;
403   return 0;
404 }
405
406 int Operators::sequentialSplit(UnaryPredicate0D& pred, 
407                                 float sampling)
408 {
409   if (_current_chains_set.empty()) {
410     cerr << "Warning: current set empty" << endl;
411     return 0;
412   }
413   CurvePoint *point;
414   Chain * new_curve;
415   I1DContainer splitted_chains;
416   Interface0DIterator first;
417   Interface0DIterator end;
418   Interface0DIterator last;
419   Interface0DIterator it;
420   I1DContainer::iterator cit = _current_chains_set.begin(), citend = _current_chains_set.end();
421   for (;
422        cit != citend;
423        ++cit) {
424     
425     Id currentId = (*cit)->getId();
426     new_curve = new Chain(currentId);
427     first = (*cit)->pointsBegin(sampling);
428     end = (*cit)->pointsEnd(sampling);
429     last = end;--last;
430     it = first;
431
432     point = dynamic_cast<CurvePoint*>(&(*it));
433     new_curve->push_vertex_back(point);++it;
434     for(; it!= end; ++it)
435       {
436         point = dynamic_cast<CurvePoint*>(&(*it));
437         new_curve->push_vertex_back(point);
438                 if(pred(it) < 0)
439                   {
440                         delete new_curve;
441                         goto error;
442                   }
443         if(pred.result && (it!=last))
444           {
445             splitted_chains.push_back(new_curve);
446             currentId.setSecond(currentId.getSecond()+1);
447             new_curve = new Chain(currentId);
448             new_curve->push_vertex_back(point);
449           }
450       }
451     if(new_curve->nSegments() == 0){
452       delete new_curve;
453       return 0;
454     }
455
456     splitted_chains.push_back(new_curve);
457   }
458
459   // Update the current set of chains:
460   cit = _current_chains_set.begin();
461   for(;
462       cit != citend;
463       ++cit){
464     delete (*cit);
465   }
466   _current_chains_set.clear();
467   _current_chains_set = splitted_chains;
468   splitted_chains.clear();
469
470   if (!_current_chains_set.empty())
471     _current_set = &_current_chains_set;
472   return 0;
473
474 error:
475   cit = splitted_chains.begin();
476   citend = splitted_chains.end();
477   for(;
478   cit != citend;
479   ++cit){
480     delete (*cit);
481   }
482   splitted_chains.clear();
483   return -1;
484 }
485
486 int Operators::sequentialSplit(UnaryPredicate0D& startingPred, UnaryPredicate0D& stoppingPred, 
487                                 float sampling)
488 {
489   if (_current_chains_set.empty()) {
490     cerr << "Warning: current set empty" << endl;
491     return 0;
492   }
493   CurvePoint *point;
494   Chain * new_curve;
495   I1DContainer splitted_chains;
496   Interface0DIterator first;
497   Interface0DIterator end;
498   Interface0DIterator last;
499   Interface0DIterator itStart;
500   Interface0DIterator itStop;
501   I1DContainer::iterator cit = _current_chains_set.begin(), citend = _current_chains_set.end();
502   for (;
503   cit != citend;
504   ++cit) {
505     Id currentId = (*cit)->getId();
506     first = (*cit)->pointsBegin(sampling);
507     end = (*cit)->pointsEnd(sampling);
508     last = end;--last;
509     itStart = first;
510     do{
511       itStop = itStart;++itStop;
512       
513       new_curve = new Chain(currentId);
514       currentId.setSecond(currentId.getSecond()+1);
515       
516       point = dynamic_cast<CurvePoint*>(&(*itStart));
517       new_curve->push_vertex_back(point);    
518       do{
519         point = dynamic_cast<CurvePoint*>(&(*itStop));
520         new_curve->push_vertex_back(point);    
521         ++itStop;
522                 if(itStop == end)
523                   break;
524                 if(stoppingPred(itStop) < 0){
525                   delete new_curve;
526                   goto error;
527                 }
528       }while(!stoppingPred.result);
529       if(itStop!=end){
530         point = dynamic_cast<CurvePoint*>(&(*itStop));
531         new_curve->push_vertex_back(point);    
532       }
533       if(new_curve->nSegments() == 0){
534         delete new_curve;
535       }else{
536         splitted_chains.push_back(new_curve);
537       }
538       // find next start
539       do{
540         ++itStart;
541                 if(itStart == end)
542                   break;
543                 if(startingPred(itStart) < 0)
544                   goto error;
545       }while(!startingPred.result);
546     }while((itStart!=end) && (itStart!=last));
547   }
548   
549   // Update the current set of chains:
550   cit = _current_chains_set.begin();
551   for(;
552   cit != citend;
553   ++cit){
554     delete (*cit);
555   }
556   _current_chains_set.clear();
557   _current_chains_set = splitted_chains;
558   splitted_chains.clear();
559   
560   if (!_current_chains_set.empty())
561     _current_set = &_current_chains_set;
562   return 0;
563
564 error:
565   cit = splitted_chains.begin();
566   citend = splitted_chains.end();
567   for(;
568   cit != citend;
569   ++cit){
570     delete (*cit);
571   }
572   splitted_chains.clear();
573   return -1;
574 }
575
576 #include "CurveIterators.h"
577
578 // Internal function
579 int __recursiveSplit(Chain *_curve, UnaryFunction0D<double>& func, UnaryPredicate1D& pred, float sampling,
580                       Operators::I1DContainer& newChains, Operators::I1DContainer& splitted_chains)
581 {
582   if(((_curve->nSegments() == 1) && (sampling == 0)) || (_curve->getLength2D() <= sampling)){
583     newChains.push_back(_curve);
584     return 0;
585   }
586
587   CurveInternal::CurvePointIterator first             = _curve->curvePointsBegin(sampling);
588   CurveInternal::CurvePointIterator second            = first; ++second;
589   CurveInternal::CurvePointIterator end               = _curve->curvePointsEnd(sampling);
590   CurveInternal::CurvePointIterator it                = second;
591   CurveInternal::CurvePointIterator split             = second;
592   Interface0DIterator it0d                            = it.castToInterface0DIterator();
593   real _min                                           = FLT_MAX;++it;//func(it0d);++it;
594   CurveInternal::CurvePointIterator next              = it;++next;
595   
596   bool bsplit = false;
597   for(; ((it != end) && (next != end)); ++it,++next){
598     it0d = it.castToInterface0DIterator();
599         if (func(it0d) < 0)
600           return -1;
601     if(func.result < _min){
602       _min = func.result;
603       split = it;
604       bsplit = true;
605     }
606   }
607   
608   if(!bsplit){ // we didn't find any minimum
609     newChains.push_back(_curve);
610     return 0;
611   }
612
613   // retrieves the current splitting id
614   Id * newId = _curve->getSplittingId();
615   if(newId == 0){
616     newId = new Id(_curve->getId());
617     _curve->setSplittingId(newId);
618   } 
619
620   Chain *new_curve_a = new Chain(*newId);
621   newId->setSecond(newId->getSecond()+1);
622   new_curve_a->setSplittingId(newId);
623   Chain *new_curve_b = new Chain(*newId);
624   newId->setSecond(newId->getSecond()+1);
625   new_curve_b->setSplittingId(newId);
626   
627   CurveInternal::CurvePointIterator vit = _curve->curveVerticesBegin(), vitend=_curve->curveVerticesEnd();
628   CurveInternal::CurvePointIterator vnext = vit; ++vnext;
629
630   
631   for(; (vit!=vitend)&&(vnext!=vitend)&&(split._CurvilinearLength-vit._CurvilinearLength> 0.001); ++vit,++vnext){
632     new_curve_a->push_vertex_back(&(*vit));
633   }
634   if((vit==vitend) || (vnext == vitend)){
635     cout << "The split takes place in bad location" << endl;
636     newChains.push_back(_curve);
637     delete new_curve_a;
638     delete new_curve_b;
639     return 0;
640   }
641
642   // build the two resulting chains
643   if(fabs(vit._CurvilinearLength-split._CurvilinearLength) > 0.001){
644     new_curve_a->push_vertex_back(&(*split));
645     new_curve_b->push_vertex_back(&(*split));
646   }
647   else{
648     new_curve_a->push_vertex_back(&(*vit));
649   }
650
651   for(;vit!=vitend;++vit)
652     new_curve_b->push_vertex_back(&(*vit));
653   
654   // let's check whether one or two of the two new curves 
655   // satisfy the stopping condition or not.
656   // (if one of them satisfies it, we don't split)
657   if (pred(*new_curve_a) < 0 || (!pred.result && pred(*new_curve_b) < 0)) {
658     delete new_curve_a;
659     delete new_curve_b;
660         return -1;
661   }
662   if(pred.result){
663     // we don't actually create these two chains
664     newChains.push_back(_curve);
665     delete new_curve_a;
666     delete new_curve_b;
667     return 0;
668   }
669   // here we know we'll split _curve:
670   splitted_chains.push_back(_curve);
671
672   __recursiveSplit(new_curve_a, func, pred, sampling, newChains, splitted_chains);
673   __recursiveSplit(new_curve_b, func, pred, sampling, newChains, splitted_chains);
674   return 0;
675 }
676
677 int Operators::recursiveSplit(UnaryFunction0D<double>& func, UnaryPredicate1D& pred, float sampling)
678 {
679   if (_current_chains_set.empty()) {
680     cerr << "Warning: current set empty" << endl;
681     return 0;
682   }
683
684   Chain *currentChain = 0;
685   I1DContainer splitted_chains;
686   I1DContainer newChains;
687   I1DContainer::iterator cit = _current_chains_set.begin(), citend = _current_chains_set.end();
688   for (;
689        cit != citend;
690        ++cit) {
691     currentChain = dynamic_cast<Chain*>(*cit);
692     if(!currentChain)
693       continue;
694     // let's check the first one:
695         if (pred(*currentChain) < 0)
696           return -1;
697     if(!pred.result){
698       __recursiveSplit(currentChain, func, pred, sampling, newChains, splitted_chains);
699     }else{
700       newChains.push_back(currentChain);
701     }
702   }
703   // Update the current set of chains:
704   if(!splitted_chains.empty()){
705     for(cit = splitted_chains.begin(), citend = splitted_chains.end();
706         cit != citend;
707         ++cit){
708       delete (*cit);
709     } 
710   splitted_chains.clear();
711   } 
712   
713   _current_chains_set.clear();
714   _current_chains_set = newChains;
715   newChains.clear();
716
717   if (!_current_chains_set.empty())
718     _current_set = &_current_chains_set;
719   return 0;
720 }
721
722
723 // recursive split with pred 0D
724 int __recursiveSplit(Chain *_curve, UnaryFunction0D<double>& func, UnaryPredicate0D& pred0d, UnaryPredicate1D& pred, float sampling,
725                       Operators::I1DContainer& newChains, Operators::I1DContainer& splitted_chains)
726 {
727   if(((_curve->nSegments() == 1) && (sampling == 0)) || (_curve->getLength2D() <= sampling)){
728     newChains.push_back(_curve);
729     return 0;
730   }
731
732   CurveInternal::CurvePointIterator first             = _curve->curvePointsBegin(sampling);
733   CurveInternal::CurvePointIterator second            = first; ++second;
734   CurveInternal::CurvePointIterator end               = _curve->curvePointsEnd(sampling);
735   CurveInternal::CurvePointIterator it                = second;
736   CurveInternal::CurvePointIterator split             = second;
737   Interface0DIterator it0d                            = it.castToInterface0DIterator();
738   //real _min                                           = func(it0d);++it;
739   real _min                                           = FLT_MAX;++it;
740   real mean                                           = 0.f;
741   //soc unused - real variance                                       = 0.f;
742   unsigned count                                      = 0;
743   CurveInternal::CurvePointIterator next              = it;++next;
744   
745   bool bsplit = false;
746   for(; ((it != end) && (next != end)); ++it,++next){
747     ++count;
748     it0d = it.castToInterface0DIterator();
749         if(pred0d(it0d) < 0)
750           return -1;
751     if(!pred0d.result)
752       continue;
753         if(func(it0d) < 0)
754           return -1;
755     mean += func.result;
756     if(func.result < _min){
757       _min = func.result;
758       split = it;
759       bsplit = true;
760     }
761   }
762   mean /= (float)count;
763
764   //if((!bsplit) || (mean-_min>mean)){ // we didn't find any minimum
765   if(!bsplit){ // we didn't find any minimum
766     newChains.push_back(_curve);
767     return 0;
768   }
769
770   // retrieves the current splitting id
771   Id * newId = _curve->getSplittingId();
772   if(newId == 0){
773     newId = new Id(_curve->getId());
774     _curve->setSplittingId(newId);
775   } 
776
777   Chain *new_curve_a = new Chain(*newId);
778   newId->setSecond(newId->getSecond()+1);
779   new_curve_a->setSplittingId(newId);
780   Chain *new_curve_b = new Chain(*newId);
781   newId->setSecond(newId->getSecond()+1);
782   new_curve_b->setSplittingId(newId);
783   
784   CurveInternal::CurvePointIterator vit = _curve->curveVerticesBegin(), vitend=_curve->curveVerticesEnd();
785   CurveInternal::CurvePointIterator vnext = vit; ++vnext;
786
787   
788   for(; (vit!=vitend)&&(vnext!=vitend)&&(split._CurvilinearLength-vit._CurvilinearLength> 0.001); ++vit,++vnext){
789     new_curve_a->push_vertex_back(&(*vit));
790   }
791   if((vit==vitend) || (vnext == vitend)){
792     cout << "The split takes place in bad location" << endl;
793     newChains.push_back(_curve);
794     delete new_curve_a;
795     delete new_curve_b;
796     return 0;
797   }
798
799   // build the two resulting chains
800   if(fabs(vit._CurvilinearLength-split._CurvilinearLength) > 0.001){
801     new_curve_a->push_vertex_back(&(*split));
802     new_curve_b->push_vertex_back(&(*split));
803   }
804   else{
805     new_curve_a->push_vertex_back(&(*vit));
806   }
807
808   for(;vit!=vitend;++vit)
809     new_curve_b->push_vertex_back(&(*vit));
810   
811   // let's check whether one or two of the two new curves 
812   // satisfy the stopping condition or not.
813   // (if one of them satisfies it, we don't split)
814   if (pred(*new_curve_a) < 0 || (!pred.result && pred(*new_curve_b) < 0)) {
815     delete new_curve_a;
816     delete new_curve_b;
817     return -1;
818   }
819   if(pred.result){
820     // we don't actually create these two chains
821     newChains.push_back(_curve);
822     delete new_curve_a;
823     delete new_curve_b;
824     return 0;
825   }
826   // here we know we'll split _curve:
827   splitted_chains.push_back(_curve);
828
829   __recursiveSplit(new_curve_a, func, pred0d, pred, sampling, newChains, splitted_chains);
830   __recursiveSplit(new_curve_b, func, pred0d, pred, sampling, newChains, splitted_chains);
831   return 0;
832 }
833
834 int Operators::recursiveSplit(UnaryFunction0D<double>& func, UnaryPredicate0D& pred0d,  UnaryPredicate1D& pred, float sampling)
835 {
836   if (_current_chains_set.empty()) {
837     cerr << "Warning: current set empty" << endl;
838     return 0;
839   }
840
841   Chain *currentChain = 0;
842   I1DContainer splitted_chains;
843   I1DContainer newChains;
844   I1DContainer::iterator cit = _current_chains_set.begin(), citend = _current_chains_set.end();
845   for (;
846        cit != citend;
847        ++cit) {
848     currentChain = dynamic_cast<Chain*>(*cit);
849     if(!currentChain)
850       continue;
851     // let's check the first one:
852         if(pred(*currentChain) < 0)
853           return -1;
854     if(!pred.result){
855       __recursiveSplit(currentChain, func, pred0d, pred, sampling, newChains, splitted_chains);
856     }else{
857       newChains.push_back(currentChain);
858     }
859   }
860   // Update the current set of chains:
861   if(!splitted_chains.empty()){
862     for(cit = splitted_chains.begin(), citend = splitted_chains.end();
863         cit != citend;
864         ++cit){
865       delete (*cit);
866     } 
867   splitted_chains.clear();
868   } 
869   
870   _current_chains_set.clear();
871   _current_chains_set = newChains;
872   newChains.clear();
873
874   if (!_current_chains_set.empty())
875     _current_set = &_current_chains_set;
876   return 0;
877 }
878 // Internal class
879 class PredicateWrapper
880 {
881 public:
882
883   inline PredicateWrapper(BinaryPredicate1D& pred) {
884     _pred = &pred;
885   }
886
887   inline bool operator()(Interface1D* i1, Interface1D* i2) {
888         if ((*_pred)(*i1, *i2) < 0)
889                 throw std::runtime_error("comparison failed");
890     return _pred->result;
891   }
892
893 private:
894
895   BinaryPredicate1D* _pred;
896 };
897
898 int Operators::sort(BinaryPredicate1D& pred) {
899   if (!_current_set)
900     return 0;
901   PredicateWrapper wrapper(pred);
902   try {
903         std::sort(_current_set->begin(), _current_set->end(), wrapper);
904   }
905   catch (std::runtime_error &e) {
906         cerr << "Warning: Operator.sort(): " << e.what() << endl;
907         return -1;
908   }
909   return 0;
910 }
911
912 Stroke* createStroke(Interface1D& inter) {
913   Stroke* stroke = new Stroke;
914   stroke->setId(inter.getId());
915
916   float currentCurvilignAbscissa = 0.f;
917
918   Interface0DIterator it = inter.verticesBegin(), itend = inter.verticesEnd();
919   Interface0DIterator itfirst = it;
920
921   Vec3r current(it->getProjectedX(), it->getProjectedY(), it->getProjectedZ());
922   Vec3r previous = current;
923   SVertex* sv;
924   CurvePoint* cp;
925   StrokeVertex* stroke_vertex = NULL;  
926
927   do {
928     cp = dynamic_cast<CurvePoint*>(&(*it));
929     if (!cp) {
930       sv = dynamic_cast<SVertex*>(&(*it));
931       if (!sv) {
932         cerr << "Warning: unexpected Vertex type" << endl;
933         continue;
934       }
935       stroke_vertex = new StrokeVertex(sv);
936     }
937     else
938       stroke_vertex = new StrokeVertex(cp);
939     current = stroke_vertex->point2d();
940     Vec3r vec_tmp(current - previous);
941     currentCurvilignAbscissa += vec_tmp.norm();
942     stroke_vertex->setCurvilinearAbscissa(currentCurvilignAbscissa);
943     stroke->push_back(stroke_vertex);
944     previous = current;
945     ++it;
946   } while((it != itend) && (it != itfirst));
947
948   if (it == itfirst) {
949     // Add last vertex:
950     cp = dynamic_cast<CurvePoint*>(&(*it));
951     if (!cp) {
952       sv = dynamic_cast<SVertex*>(&(*it));
953       if (!sv)
954         cerr << "Warning: unexpected Vertex type" << endl;
955       else
956         stroke_vertex = new StrokeVertex(sv);
957     }
958     else
959       stroke_vertex = new StrokeVertex(cp);
960     current = stroke_vertex->point2d();
961     Vec3r vec_tmp(current - previous);
962     currentCurvilignAbscissa += vec_tmp.norm();
963     stroke_vertex->setCurvilinearAbscissa(currentCurvilignAbscissa);
964     stroke->push_back(stroke_vertex);
965   }
966   stroke->setLength(currentCurvilignAbscissa);
967   return stroke;
968 }
969
970
971 inline int applyShading(Stroke& stroke, vector<StrokeShader*>& shaders) {
972   for (vector<StrokeShader*>::iterator it = shaders.begin(); it != shaders.end(); ++it) {
973     if ((*it)->shade(stroke) < 0) {
974           return -1;
975         }
976   }
977   return 0;
978 }
979
980
981 int Operators::create(UnaryPredicate1D& pred, vector<StrokeShader*> shaders) {
982   //Canvas* canvas = Canvas::getInstance();
983   if (!_current_set) {
984     cerr << "Warning: current set empty" << endl;
985     return 0;
986   }
987   for (Operators::I1DContainer::iterator it = _current_set->begin();
988        it != _current_set->end();
989        ++it) {
990         if (pred(**it) < 0)
991           return -1;
992     if (!pred.result)
993       continue;
994         
995         Stroke* stroke = createStroke(**it);
996     if (stroke) {
997       if (applyShading(*stroke, shaders) < 0)
998                   return -1;
999       //canvas->RenderStroke(stroke);
1000       _current_strokes_set.push_back(stroke);
1001     }
1002   }
1003   return 0;
1004 }
1005
1006
1007 void Operators::reset() {
1008   ViewMap* vm = ViewMap::getInstance();
1009   if (!vm) {
1010     cerr << "Error: no ViewMap computed yet" << endl;
1011     return;
1012   }
1013   _current_view_edges_set.clear();
1014   for (I1DContainer::iterator it = _current_chains_set.begin();
1015        it != _current_chains_set.end();
1016        ++it)
1017     delete *it;
1018   _current_chains_set.clear();
1019   _current_view_edges_set.insert(_current_view_edges_set.begin(),
1020                                  vm->ViewEdges().begin(),
1021                                  vm->ViewEdges().end());
1022   _current_set = &_current_view_edges_set;
1023   _current_strokes_set.clear();
1024 }