1 // Copyright (C) 2012-2019 The VPaint Developers.
2 // See the COPYRIGHT file at the top-level directory of this distribution
3 // and at https://github.com/dalboris/vpaint/blob/master/COPYRIGHT
4 //
5 // Licensed under the Apache License, Version 2.0 (the "License");
6 // you may not use this file except in compliance with the License.
7 // You may obtain a copy of the License at
8 //
9 //     http://www.apache.org/licenses/LICENSE-2.0
10 //
11 // Unless required by applicable law or agreed to in writing, software
12 // distributed under the License is distributed on an "AS IS" BASIS,
13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 // See the License for the specific language governing permissions and
15 // limitations under the License.
16 
17 #include "AnimatedCycle.h"
18 
19 #include "KeyVertex.h"
20 #include "KeyEdge.h"
21 #include "InbetweenVertex.h"
22 #include "InbetweenEdge.h"
23 #include "EdgeGeometry.h"
24 #include "VAC.h"
25 
26 #include <QStack>
27 #include <QMap>
28 #include <assert.h>
29 #include <QtDebug>
30 
31 namespace VectorAnimationComplex
32 {
33 
AnimatedCycleNode(Cell * cell)34 AnimatedCycleNode::AnimatedCycleNode(Cell * cell) :
35     cell_(cell),
36     previous_(0),
37     next_(0),
38     before_(0),
39     after_(0),
40     side_(true)
41 {
42 }
43 
44 // Type
nodeType() const45 AnimatedCycleNode::NodeType AnimatedCycleNode::nodeType() const
46 {
47     if(cell_->toKeyVertex())
48         return KeyVertexNode;
49     else if(cell_->toInbetweenVertex())
50         return InbetweenVertexNode;
51     else if(cell_->toKeyEdge())
52     {
53         if(cell_->toKeyEdge()->isClosed())
54             return KeyClosedEdgeNode;
55         else
56             return KeyOpenEdgeNode;
57     }
58     else if(cell_->toInbetweenEdge())
59     {
60         if(cell_->toInbetweenEdge()->isClosed())
61             return InbetweenClosedEdgeNode;
62         else
63             return InbetweenOpenEdgeNode;
64     }
65     else
66         return InvalidNode;
67 }
cycleType(Time time) const68 AnimatedCycleNode::CycleType AnimatedCycleNode::cycleType(Time time) const
69 {
70     assert(cell()->exists(time));
71     CycleType res = InvalidCycle;
72     switch(nodeType())
73     {
74     case InvalidNode:
75         res = InvalidCycle;
76         break;
77     case KeyVertexNode:
78     case InbetweenVertexNode:
79         if(next())
80         {
81             if(next()->cell() == cell())
82                 res = SteinerCycle;
83             else
84                 res = NonSimpleCycle;
85         }
86         else
87         {
88             qWarning("Warning: invalid animated cycle");
89             res = InvalidCycle;
90         }
91         break;
92     case KeyClosedEdgeNode:
93     case InbetweenClosedEdgeNode:
94         res = SimpleCycle;
95         break;
96     case KeyOpenEdgeNode:
97     case InbetweenOpenEdgeNode:
98         res = NonSimpleCycle;
99         break;
100     }
101     return res;
102 }
103 
104 // Setters
setCell(Cell * cell)105 void AnimatedCycleNode::setCell(Cell * cell)
106 {
107     cell_ = cell;
108 }
setPrevious(AnimatedCycleNode * node)109 void AnimatedCycleNode::setPrevious(AnimatedCycleNode * node)
110 {
111     previous_ = node;
112 }
setNext(AnimatedCycleNode * node)113 void AnimatedCycleNode::setNext(AnimatedCycleNode * node)
114 {
115     next_ = node;
116 }
setBefore(AnimatedCycleNode * node)117 void AnimatedCycleNode::setBefore(AnimatedCycleNode * node)
118 {
119     before_ = node;
120 }
setAfter(AnimatedCycleNode * node)121 void AnimatedCycleNode::setAfter(AnimatedCycleNode * node)
122 {
123     after_ = node;
124 }
125 
126 // Getters
cell() const127 Cell * AnimatedCycleNode::cell() const
128 {
129     return cell_;
130 }
previous() const131 AnimatedCycleNode * AnimatedCycleNode::previous() const
132 {
133     return previous_;
134 }
next() const135 AnimatedCycleNode * AnimatedCycleNode::next() const
136 {
137     return next_;
138 }
before() const139 AnimatedCycleNode * AnimatedCycleNode::before() const
140 {
141     return before_;
142 }
after() const143 AnimatedCycleNode * AnimatedCycleNode::after() const
144 {
145     return after_;
146 }
147 
148 // Spatial cycling
previous(Time time) const149 AnimatedCycleNode * AnimatedCycleNode::previous(Time time) const
150 {
151     assert(cell()->exists(time));
152     AnimatedCycleNode * res = 0;
153     switch(nodeType())
154     {
155     case InvalidNode:
156         res = 0;
157         break;
158     case KeyVertexNode:
159     case KeyClosedEdgeNode:
160     case KeyOpenEdgeNode:
161     case InbetweenVertexNode:
162     case InbetweenClosedEdgeNode:
163         res = previous();
164         break;
165     case InbetweenOpenEdgeNode:
166         res = previous();
167         while(!res->cell()->exists(time))
168             res = res->before();
169         break;
170     }
171     return res;
172 }
next(Time time) const173 AnimatedCycleNode * AnimatedCycleNode::next(Time time) const
174 {
175     assert(cell()->exists(time));
176     AnimatedCycleNode * res = 0;
177     switch(nodeType())
178     {
179     case InvalidNode:
180         res = 0; // Redundant, but make clear that this is what I want to return
181         break;
182     case KeyVertexNode:
183     case KeyClosedEdgeNode:
184     case KeyOpenEdgeNode:
185     case InbetweenVertexNode:
186     case InbetweenClosedEdgeNode:
187         res = next();
188         break;
189     case InbetweenOpenEdgeNode:
190         res = next();
191         if(!res)
192         {
193             res = 0; // Redundant, but make clear that this is what I want to return
194             qWarning("Warning: no next, cycle is invalid");
195         }
196         else
197         {
198             while(res && !res->cell()->exists(time))
199             {
200                 res = res->after();
201                 if(!res)
202                 {
203                     res = 0; // Redundant, but make clear that this is what I want to return
204                     qWarning("Warning: no after, cycle is invalid");
205                 }
206             }
207         }
208         break;
209     }
210     return res;
211 }
212 
side() const213 bool AnimatedCycleNode::side() const
214 {
215     return side_;
216 }
217 
setSide(bool side)218 void AnimatedCycleNode::setSide(bool side)
219 {
220     side_ = side;
221 }
222 
AnimatedCycle()223 AnimatedCycle::AnimatedCycle() :
224     first_(0)
225 {
226 }
227 
AnimatedCycle(AnimatedCycleNode * first)228 AnimatedCycle::AnimatedCycle(AnimatedCycleNode * first) :
229     first_(first)
230 {
231 }
232 
AnimatedCycle(const AnimatedCycle & other)233 AnimatedCycle::AnimatedCycle(const AnimatedCycle & other) :
234     first_(0)
235 {
236     copyFrom(other);
237 }
238 
operator =(const AnimatedCycle & other)239 AnimatedCycle & AnimatedCycle::operator=(const AnimatedCycle & other)
240 {
241     if(this != &other)
242         copyFrom(other);
243 
244     return *this;
245 }
246 
~AnimatedCycle()247 AnimatedCycle::~AnimatedCycle()
248 {
249     clear();
250 }
251 
clear()252 void AnimatedCycle::clear()
253 {
254     foreach(AnimatedCycleNode * node, nodes())
255         delete node;
256 
257     first_ = 0;
258 }
259 
copyFrom(const AnimatedCycle & other)260 void AnimatedCycle::copyFrom(const AnimatedCycle & other)
261 {
262     clear();
263 
264     QMap<AnimatedCycleNode *, AnimatedCycleNode *> oldToNew;
265     oldToNew[0] = 0;
266     foreach(AnimatedCycleNode * oldNode, other.nodes())
267         oldToNew[oldNode] = new AnimatedCycleNode(oldNode->cell());
268 
269     foreach(AnimatedCycleNode * oldNode, other.nodes())
270     {
271         AnimatedCycleNode * newNode = oldToNew[oldNode];
272         newNode->setPrevious(oldToNew[oldNode->previous()]);
273         newNode->setNext(oldToNew[oldNode->next()]);
274         newNode->setBefore(oldToNew[oldNode->before()]);
275         newNode->setAfter(oldToNew[oldNode->after()]);
276         newNode->setSide(oldNode->side());
277     }
278 
279     first_ = oldToNew[other.first_];
280     tempNodes_ = other.tempNodes_;
281 }
282 
first() const283 AnimatedCycleNode  * AnimatedCycle::first() const
284 {
285     return first_;
286 }
287 
setFirst(AnimatedCycleNode * node)288 void AnimatedCycle::setFirst(AnimatedCycleNode  * node)
289 {
290     first_ = node;
291 }
292 
getNode(Time time)293 AnimatedCycleNode  * AnimatedCycle::getNode(Time time)
294 {
295     AnimatedCycleNode  * res = first_;
296     if(!res)
297     {
298         qWarning("node(t) not found: no first node");
299         return 0;
300     }
301 
302 
303     while(!res->cell()->exists(time))
304     {
305         res = res->after();
306         if(!res)
307         {
308             qWarning("node(t) not found: no after node");
309             return 0;
310         }
311     }
312 
313     return res;
314 }
315 
nodes() const316 QSet<AnimatedCycleNode*> AnimatedCycle::nodes() const
317 {
318     QSet<AnimatedCycleNode*> res;
319 
320     if(!first_)
321         return res;
322 
323     QStack<AnimatedCycleNode*> toProcess;
324     toProcess.push(first_);
325     res << first_;
326     while(!toProcess.isEmpty())
327     {
328         AnimatedCycleNode * node = toProcess.pop();
329         AnimatedCycleNode * pointedNodes[4] = { node->previous(),
330                                                 node->next(),
331                                                 node->before(),
332                                                 node->after() };
333         for(int i=0; i<4; ++i)
334         {
335             if(pointedNodes[i] && !res.contains(pointedNodes[i]))
336             {
337                 toProcess.push(pointedNodes[i]);
338                 res << pointedNodes[i];
339             }
340         }
341     }
342     return res;
343 }
344 
cells() const345 CellSet AnimatedCycle::cells() const
346 {
347     CellSet res;
348     foreach(AnimatedCycleNode * node, nodes())
349         res << node->cell();
350     return res;
351 }
beforeCells() const352 KeyCellSet AnimatedCycle::beforeCells() const
353 {
354     KeyCellSet res;
355     foreach(AnimatedCycleNode * node, nodes())
356     {
357         if(!node->before())
358             res.unite(node->cell()->beforeCells());
359     }
360     return res;
361 }
afterCells() const362 KeyCellSet AnimatedCycle::afterCells() const
363 {
364     KeyCellSet res;
365     foreach(AnimatedCycleNode * node, nodes())
366     {
367         if(!node->after())
368             res.unite(node->cell()->afterCells());
369     }
370     return res;
371 }
372 
373 
374 // Replace pointed vertex
replaceVertex(KeyVertex * oldVertex,KeyVertex * newVertex)375 void AnimatedCycle::replaceVertex(KeyVertex * oldVertex, KeyVertex * newVertex)
376 {
377     foreach(AnimatedCycleNode * node, nodes())
378     {
379         if(node->cell()->toKeyVertex() == oldVertex)
380             node->setCell(newVertex);
381     }
382 }
replaceHalfedge(const KeyHalfedge & oldHalfedge,const KeyHalfedge & newHalfedge)383 void AnimatedCycle::replaceHalfedge(const KeyHalfedge & oldHalfedge, const KeyHalfedge & newHalfedge)
384 {
385     foreach(AnimatedCycleNode * node, nodes())
386     {
387         if(node->cell()->toKeyEdge() == oldHalfedge.edge)
388         {
389             node->setCell(newHalfedge.edge);
390             node->setSide((node->side() == oldHalfedge.side) == newHalfedge.side);
391         }
392     }
393 }
replaceEdges(KeyEdge * oldEdge,const KeyEdgeList & newEdges)394 void AnimatedCycle::replaceEdges(KeyEdge * oldEdge, const KeyEdgeList & newEdges)
395 {
396     if(oldEdge->isClosed())
397     {
398         // Get the old key closed edge nodes, sorted
399         QList<AnimatedCycleNode *> oldEdgeNodes;
400         AnimatedCycleNode * oldEdgeNodeFirst = *getNodes(oldEdge).begin();
401         AnimatedCycleNode * oldEdgeNode = oldEdgeNodeFirst;
402         do
403         {
404             oldEdgeNodes << oldEdgeNode;
405             oldEdgeNode = oldEdgeNode->next();
406         }
407         while(oldEdgeNode != oldEdgeNodeFirst);
408         int nOldEdgeNodes = oldEdgeNodes.size();
409 
410         // Get before inbetween closed edge nodes
411         QList<AnimatedCycleNode *> beforeEdgeNodes;
412         AnimatedCycleNode * beforeEdgeNodesFirst = oldEdgeNodeFirst->before();
413         AnimatedCycleNode * beforeEdgeNode = beforeEdgeNodesFirst;
414         do
415         {
416             beforeEdgeNodes << beforeEdgeNode;
417             beforeEdgeNode = beforeEdgeNode->next();
418         }
419         while(beforeEdgeNode != beforeEdgeNodesFirst);
420         int nBeforeEdgeNodes = beforeEdgeNodes.size();
421         int beforeInbetweenKeyRatio = nOldEdgeNodes / nBeforeEdgeNodes;
422 
423         // Get after inbetween closed edge nodes
424         QList<AnimatedCycleNode *> afterEdgeNodes;
425         AnimatedCycleNode * afterEdgeNodesFirst = oldEdgeNodeFirst->after();
426         AnimatedCycleNode * afterEdgeNode = afterEdgeNodesFirst;
427         do
428         {
429             afterEdgeNodes << afterEdgeNode;
430             afterEdgeNode = afterEdgeNode->next();
431         }
432         while(afterEdgeNode != afterEdgeNodesFirst);
433         int nAfterEdgeNodes = afterEdgeNodes.size();
434         int afterInbetweenKeyRatio = nOldEdgeNodes / nAfterEdgeNodes;
435 
436         // Get side and num of new edge (i.e., num of new edgeNode per old edgeNode)
437         int n = newEdges.size();
438         bool side = oldEdgeNode->side();
439 
440         // Create new nodes
441         QList<AnimatedCycleNode *> newEdgeNodes;
442         QList<AnimatedCycleNode *> newVertexNodes;
443         for(int i=0; i<nOldEdgeNodes; ++i)
444         {
445             for(int j=0; j<n; ++j)
446             {
447                 AnimatedCycleNode * newEdgeNode = new AnimatedCycleNode(newEdges[i]);
448                 newEdgeNode->setSide(side);
449                 newEdgeNodes << newEdgeNode;
450 
451                 AnimatedCycleNode * newVertexNode = new AnimatedCycleNode(newEdges[i]->endVertex());
452                 newVertexNodes << newVertexNode;
453             }
454         }
455         int m = newEdgeNodes.size(); // == newVertexNodes.size() == nOldEdgeNodes*n
456 
457         // Set pointers of new nodes
458         int k = 0;
459         for(int i=0; i<nOldEdgeNodes; ++i)
460         {
461             for(int j=0; j<n; ++j)
462             {
463                 newEdgeNodes[k]->setPrevious(newVertexNodes[ (k-1+m) % m ]);
464                 newEdgeNodes[k]->setNext(newVertexNodes[k]);
465                 newEdgeNodes[k]->setBefore(oldEdgeNodes[i]->before());
466                 newEdgeNodes[k]->setAfter(oldEdgeNodes[i]->after());
467 
468                 newVertexNodes[k]->setPrevious(newEdgeNodes[k]);
469                 newVertexNodes[k]->setNext(newEdgeNodes[(k+1) % m ]);
470                 newVertexNodes[k]->setBefore(oldEdgeNodes[i]->before());
471                 newVertexNodes[k]->setAfter(oldEdgeNodes[i]->after());
472 
473                 ++k;
474             }
475         }
476 
477         // Set pointers of before inbetween closed edge nodes
478         for(int i=0; i<nBeforeEdgeNodes; ++i)
479             beforeEdgeNodes[i]->setAfter(newEdgeNodes[i*beforeInbetweenKeyRatio]);
480 
481         // Set pointers of after inbetween closed edge nodes
482         for(int i=0; i<nAfterEdgeNodes; ++i)
483             afterEdgeNodes[i]->setBefore(newEdgeNodes[i*afterInbetweenKeyRatio]);
484 
485         // Update first node. Shouldn't occur, since first_ is supposed to be a inbetween node
486         for(int i=0; i<nOldEdgeNodes; ++i)
487         {
488             if(first_ == oldEdgeNodes[i])
489                 first_ = newEdgeNodes[0];
490         }
491 
492         // Delete old nodes
493         for(int i=0; i<nOldEdgeNodes; ++i)
494             delete oldEdgeNodes[i];
495     }
496     else
497     {
498         foreach(AnimatedCycleNode * oldEdgeNode, getNodes(oldEdge))
499         {
500             int n = newEdges.size();
501             bool side = oldEdgeNode->side();
502 
503             // Create the new nodes
504             QList<AnimatedCycleNode *> newEdgeNodes; // [0..n-1]
505             QList<AnimatedCycleNode *> newVertexNodes; // [0..n-2]
506             if(side)
507             {
508                 for(int i=0; i<n; ++i)
509                 {
510                     AnimatedCycleNode * newEdgeNode = new AnimatedCycleNode(newEdges[i]);
511                     newEdgeNode->setSide(side);
512                     newEdgeNodes << newEdgeNode;
513                 }
514                 for(int i=0; i<n-1; ++i)
515                 {
516                     AnimatedCycleNode * newVertexNode = new AnimatedCycleNode(newEdges[i]->endVertex());
517                     newVertexNodes << newVertexNode;
518                 }
519             }
520             else
521             {
522                 for(int i=0; i<n; ++i)
523                 {
524                     AnimatedCycleNode * newEdgeNode = new AnimatedCycleNode(newEdges[n-1-i]);
525                     newEdgeNode->setSide(side);
526                     newEdgeNodes << newEdgeNode;
527                 }
528                 for(int i=0; i<n-1; ++i)
529                 {
530                     AnimatedCycleNode * newVertexNode = new AnimatedCycleNode(newEdges[n-1-i]->startVertex());
531                     newVertexNodes << newVertexNode;
532                 }
533             }
534 
535             // Set direct pointers
536             // previous
537             newEdgeNodes[0]->setPrevious(oldEdgeNode->previous());
538             for(int i=1; i<n; ++i)
539                 newEdgeNodes[i]->setPrevious(newVertexNodes[i-1]);
540             for(int i=0; i<n-1; ++i)
541                 newVertexNodes[i]->setPrevious(newEdgeNodes[i]);
542             // next
543             newEdgeNodes[n-1]->setNext(oldEdgeNode->next());
544             for(int i=0; i<n-1; ++i)
545                 newEdgeNodes[i]->setNext(newVertexNodes[i]);
546             for(int i=0; i<n-1; ++i)
547                 newVertexNodes[i]->setNext(newEdgeNodes[i+1]);
548             // before
549             for(int i=0; i<n; ++i)
550                 newEdgeNodes[i]->setBefore(oldEdgeNode->before());
551             for(int i=0; i<n-1; ++i)
552                 newVertexNodes[i]->setBefore(oldEdgeNode->before());
553             // after
554             for(int i=0; i<n; ++i)
555                 newEdgeNodes[i]->setAfter(oldEdgeNode->after());
556             for(int i=0; i<n-1; ++i)
557                 newVertexNodes[i]->setAfter(oldEdgeNode->after());
558 
559             // Set back pointers
560             // previous
561             oldEdgeNode->previous()->setNext(newEdgeNodes[0]);
562             // next
563             oldEdgeNode->next()->setPrevious(newEdgeNodes[n-1]);
564             // before
565             if(oldEdgeNode->before() && oldEdgeNode->before()->after() == oldEdgeNode)
566                 oldEdgeNode->before()->setAfter(newEdgeNodes[0]);
567             // after
568             if(oldEdgeNode->after() && oldEdgeNode->after()->before() == oldEdgeNode)
569                 oldEdgeNode->after()->setBefore(newEdgeNodes[n-1]);
570 
571             // Update first node
572             if(first_ == oldEdgeNode) // shouldn't occur, since first_ is supposed to be a inbetween node
573                 first_ = newEdgeNodes[0];
574 
575             // Delete node
576             delete oldEdgeNode;
577         }
578     }
579 }
580 
getNodes(Cell * cell)581 QSet<AnimatedCycleNode*>  AnimatedCycle::getNodes(Cell * cell)
582 {
583     QSet<AnimatedCycleNode*> res;
584     foreach(AnimatedCycleNode * node, nodes())
585     {
586         if(node->cell() == cell)
587             res << node;
588     }
589     return res;
590 }
591 
replaceInbetweenVertex(InbetweenVertex * sv,InbetweenVertex * sv1,KeyVertex * kv,InbetweenVertex * sv2)592 void AnimatedCycle::replaceInbetweenVertex(InbetweenVertex * sv,
593                             InbetweenVertex * sv1, KeyVertex * kv, InbetweenVertex * sv2)
594 {
595     foreach(AnimatedCycleNode * nsv, getNodes(sv))
596     {
597         // Create three new nodes
598         AnimatedCycleNode * nsv1 = new AnimatedCycleNode(sv1);
599         AnimatedCycleNode * nkv = new AnimatedCycleNode(kv);
600         AnimatedCycleNode * nsv2 = new AnimatedCycleNode(sv2);
601 
602         if(nsv->next() == nsv) // Steiner cycle case
603         {
604             // Set direct pointers
605             // previous
606             nsv1->setPrevious(nsv1);
607             nkv->setPrevious(nkv);
608             nsv2->setPrevious(nsv2);
609             // next
610             nsv1->setNext(nsv1);
611             nkv->setNext(nkv);
612             nsv2->setNext(nsv2);
613             // before
614             nsv1->setBefore(nsv->before());
615             nkv->setBefore(nsv1);
616             nsv2->setBefore(nkv);
617             // after
618             nsv1->setAfter(nkv);
619             nkv->setAfter(nsv2);
620             nsv2->setAfter(nsv->after());
621 
622             // Set back pointers
623             // previous
624             //   -> no-op
625             // next
626             //   -> no-op
627             // before
628             if(nsv->before() && nsv->before()->after() == nsv)
629                 nsv->before()->setAfter(nsv1);
630             // after
631             if(nsv->after() && nsv->after()->before() == nsv)
632                 nsv->after()->setBefore(nsv2);
633 
634         }
635         else // Non-simple cycle case
636         {
637             // Set direct pointers
638             // previous
639             nsv1->setPrevious(nsv->previous());
640             nkv->setPrevious(nsv->previous());
641             nsv2->setPrevious(nsv->previous());
642             // next
643             nsv1->setNext(nsv->next());
644             nkv->setNext(nsv->next());
645             nsv2->setNext(nsv->next());
646             // before
647             nsv1->setBefore(nsv->before());
648             nkv->setBefore(nsv1);
649             nsv2->setBefore(nkv);
650             // after
651             nsv1->setAfter(nkv);
652             nkv->setAfter(nsv2);
653             nsv2->setAfter(nsv->after());
654 
655             // Set back pointers
656             // previous
657             assert(nsv->previous());
658             if(nsv->previous()->next() == nsv)
659                 nsv->previous()->setNext(nsv1);
660             // next
661             assert(nsv->next());
662             if(nsv->next()->previous() == nsv)
663                 nsv->next()->setPrevious(nsv2);
664             // before
665             if(nsv->before() && nsv->before()->after() == nsv)
666                 nsv->before()->setAfter(nsv1);
667             // after
668             if(nsv->after() && nsv->after()->before() == nsv)
669                 nsv->after()->setBefore(nsv2);
670         }
671 
672         // Update first node
673         if(first_ == nsv)
674             first_ = nsv1;
675 
676         // Delete node
677         delete nsv;
678     }
679 }
680 
replaceInbetweenEdge(InbetweenEdge * se,InbetweenEdge * se1,KeyEdge * ke,InbetweenEdge * se2)681 void AnimatedCycle::replaceInbetweenEdge(InbetweenEdge * se,
682                                          InbetweenEdge * se1, KeyEdge * ke, InbetweenEdge * se2)
683 {
684     // Get time
685     Time t = ke->time();
686 
687     if(se->isClosed())
688     {
689         // Get old nodes, sorted
690         QSet<AnimatedCycleNode*> oldNodesUnsorted = getNodes(se);
691         if (oldNodesUnsorted.isEmpty()) {
692             // Nothing to do if `se` doesn't belong to this animated cycle
693             return;
694         }
695         AnimatedCycleNode * oldNodeFirst = *oldNodesUnsorted.begin();
696         AnimatedCycleNode * oldNode = oldNodeFirst;
697         QList<AnimatedCycleNode *> oldNodes;
698         do
699         {
700             oldNodes << oldNode;
701             oldNode = oldNode->next();
702         }
703         while(oldNode != oldNodeFirst);
704         int n = oldNodes.size();
705         bool side = oldNodeFirst->side();
706 
707         // Create new nodes and set orientation
708         QList<AnimatedCycleNode *> newNodesBefore;
709         QList<AnimatedCycleNode *> newNodesKey;
710         QList<AnimatedCycleNode *> newNodesAfter;
711         for(int i=0; i<n; ++i)
712         {
713             AnimatedCycleNode * nse1 = new AnimatedCycleNode(se1);
714             AnimatedCycleNode * nke = new AnimatedCycleNode(ke);
715             AnimatedCycleNode * nse2 = new AnimatedCycleNode(se2);
716             nse1->setSide(side);
717             nke->setSide(side);
718             nse2->setSide(side);
719             newNodesBefore << nse1;
720             newNodesKey << nke;
721             newNodesAfter << nse2;
722         }
723 
724         // Set direct pointers
725         for(int i=0; i<n; ++i)
726         {
727             newNodesBefore[i]->setPrevious(newNodesBefore[(i+n-1)%n]);
728             newNodesBefore[i]->setNext(newNodesBefore[(i+1)%n]);
729             newNodesBefore[i]->setBefore(oldNodes[i]->before());
730             newNodesBefore[i]->setAfter(newNodesKey[i]);
731 
732             newNodesKey[i]->setPrevious(newNodesKey[(i+n-1)%n]);
733             newNodesKey[i]->setNext(newNodesKey[(i+1)%n]);
734             newNodesKey[i]->setBefore(newNodesBefore[i]);
735             newNodesKey[i]->setAfter(newNodesAfter[i]);
736 
737             newNodesAfter[i]->setPrevious(newNodesAfter[(i+n-1)%n]);
738             newNodesAfter[i]->setNext(newNodesAfter[(i+1)%n]);
739             newNodesAfter[i]->setBefore(newNodesKey[i]);
740             newNodesAfter[i]->setAfter(oldNodes[i]->after());
741         }
742 
743         // Set indirect pointers
744         for(int i=0; i<n; ++i)
745         {
746             AnimatedCycleNode * nse = oldNodes[i];
747             AnimatedCycleNode * nse1 = newNodesBefore[i];
748             AnimatedCycleNode * nse2 = newNodesAfter[i];
749 
750             // before
751             AnimatedCycleNode * quasiBeforeNode = nse->before();
752             while(quasiBeforeNode && quasiBeforeNode->after() == nse)
753             {
754                 quasiBeforeNode->setAfter(nse1);
755                 quasiBeforeNode = quasiBeforeNode->previous();
756             }
757 
758             // after
759             AnimatedCycleNode * quasiAfterNode = nse->after();
760             while(quasiAfterNode && quasiAfterNode->before() == nse)
761             {
762                 quasiAfterNode->setBefore(nse2);
763                 quasiAfterNode = quasiAfterNode->next();
764             }
765 
766             // Update first node
767             if(first_ == nse)
768                 first_ = nse1;
769         }
770 
771         // Delete nodes
772         for(int i=0; i<n; ++i)
773             delete oldNodes[i];
774     }
775     else
776     {
777         // Perform substitution
778         foreach(AnimatedCycleNode * nse, getNodes(se))
779         {
780             // Get boundary nodes
781             AnimatedCycleNode * nkvprevious = nse->previous(t);
782             AnimatedCycleNode * nkvnext = nse->next(t);
783             assert(nkvprevious->cell()->toKeyVertex());
784             assert(nkvnext->cell()->toKeyVertex());
785 
786             // Create three new nodes
787             AnimatedCycleNode * nse1 = new AnimatedCycleNode(se1);
788             AnimatedCycleNode * nke = new AnimatedCycleNode(ke);
789             AnimatedCycleNode * nse2 = new AnimatedCycleNode(se2);
790 
791             // Set orientation
792             nse1->setSide(nse->side());
793             nke->setSide(nse->side());
794             nse2->setSide(nse->side());
795 
796             // Set direct pointers
797             // previous
798             nse1->setPrevious(nkvprevious->before());
799             nke->setPrevious(nkvprevious);
800             nse2->setPrevious(nse->previous());
801             // next
802             nse1->setNext(nse->next());
803             nke->setNext(nkvnext);
804             nse2->setNext(nkvnext->after());
805             // before
806             nse1->setBefore(nse->before());
807             nke->setBefore(nse1);
808             nse2->setBefore(nke);
809             // after
810             nse1->setAfter(nke);
811             nke->setAfter(nse2);
812             nse2->setAfter(nse->after());
813 
814             // Set back pointers
815             // previous
816             {
817                 assert(nse->previous());
818                 AnimatedCycleNode * quasiPreviousNode = nse->previous();
819                 AnimatedCycleNode * nextOfQuasiPreviousNode = nse2;
820                 while(quasiPreviousNode && quasiPreviousNode->next() == nse)
821                 {
822                     if(quasiPreviousNode == nkvprevious)
823                     {
824                         nextOfQuasiPreviousNode = nke;
825                         quasiPreviousNode->setNext(nextOfQuasiPreviousNode);
826                         nextOfQuasiPreviousNode = nse1;
827                     }
828                     else
829                     {
830                         quasiPreviousNode->setNext(nextOfQuasiPreviousNode);
831                     }
832                     quasiPreviousNode = quasiPreviousNode->before();
833                 }
834             }
835             // next
836             {
837                 assert(nse->next());
838                 AnimatedCycleNode * quasiNextNode = nse->next();
839                 AnimatedCycleNode * previousOfQuasiNextNode = nse1;
840                 while(quasiNextNode && quasiNextNode->previous() == nse)
841                 {
842                     if(quasiNextNode == nkvnext)
843                     {
844                         previousOfQuasiNextNode = nke;
845                         quasiNextNode->setPrevious(previousOfQuasiNextNode);
846                         previousOfQuasiNextNode = nse2;
847                     }
848                     else
849                     {
850                         quasiNextNode->setPrevious(previousOfQuasiNextNode);
851                     }
852                     quasiNextNode = quasiNextNode->after();
853                 }
854             }
855             // before
856             {
857                 AnimatedCycleNode * quasiBeforeNode = nse->before();
858                 while(quasiBeforeNode && quasiBeforeNode->after() == nse)
859                 {
860                     quasiBeforeNode->setAfter(nse1);
861                     quasiBeforeNode = quasiBeforeNode->previous();
862                 }
863             }
864             // after
865             {
866                 AnimatedCycleNode * quasiAfterNode = nse->after();
867                 while(quasiAfterNode && quasiAfterNode->before() == nse)
868                 {
869                     quasiAfterNode->setBefore(nse2);
870                     quasiAfterNode = quasiAfterNode->next();
871                 }
872             }
873 
874             // Update first node
875             if(first_ == nse)
876                 first_ = nse1;
877 
878             // Delete node
879             delete nse;
880         }
881     }
882 }
883 
884 
885 // Geometry
sample(Time time,QList<Eigen::Vector2d> & out)886 void AnimatedCycle::sample(Time time, QList<Eigen::Vector2d> & out)
887 {
888     // A robust sampling scheme. Do not assume that the cycle is valid.
889     // More specifically, the
890 
891 
892     out.clear();
893     AnimatedCycleNode * node = getNode(time);
894     if(!node)
895     {
896         qWarning("Warning: sampling failed: no node found");
897         return;
898     }
899 
900     AnimatedCycleNode::CycleType cycleType = node->cycleType(time);
901 
902     if(cycleType == AnimatedCycleNode::NonSimpleCycle)
903     {
904         AnimatedCycleNode * firstOpenHalfedge = node;
905         if(firstOpenHalfedge->nodeType() == AnimatedCycleNode::KeyVertexNode ||
906            firstOpenHalfedge->nodeType() == AnimatedCycleNode::InbetweenVertexNode)
907         {
908             firstOpenHalfedge = firstOpenHalfedge->next(time);
909             if(!firstOpenHalfedge)
910             {
911                 qWarning("Warning: sampling (partially) failed: no next node found");
912                 return;
913             }
914         }
915         //assert(firstOpenHalfedge->nodeType() == AnimatedCycleNode::KeyOpenEdgeNode ||
916         //       firstOpenHalfedge->nodeType() == AnimatedCycleNode::InbetweenOpenEdgeNode);
917         if( !(firstOpenHalfedge->nodeType() == AnimatedCycleNode::KeyOpenEdgeNode ||
918                firstOpenHalfedge->nodeType() == AnimatedCycleNode::InbetweenOpenEdgeNode))
919         {
920             qWarning("Warning: sampling (partially) failed: wrong node type");
921             return;
922         }
923 
924         AnimatedCycleNode * openHalfedge = firstOpenHalfedge;
925         do
926         {
927             //assert(openHalfedge->nodeType() == AnimatedCycleNode::KeyOpenEdgeNode ||
928             //       openHalfedge->nodeType() == AnimatedCycleNode::InbetweenOpenEdgeNode);
929             if(!(openHalfedge->nodeType() == AnimatedCycleNode::KeyOpenEdgeNode ||
930                    openHalfedge->nodeType() == AnimatedCycleNode::InbetweenOpenEdgeNode))
931             {
932                 qWarning("Warning: sampling (partially) failed: wrong node type");
933                 return;
934             }
935 
936             if(openHalfedge->nodeType() == AnimatedCycleNode::KeyOpenEdgeNode)
937             {
938                 QList<Eigen::Vector2d> sampling = openHalfedge->cell()->toKeyEdge()->geometry()->sampling();
939                 if(openHalfedge->side())
940                     for(int i=0; i<sampling.size()-1; ++i) // -1 because we don't want to duplicate last sample
941                         out << sampling[i];
942                 else
943                     for(int i=sampling.size()-1; i>0; --i) // -1 because we don't want to duplicate last sample
944                         out << sampling[i];
945             }
946             else if(openHalfedge->nodeType() == AnimatedCycleNode::InbetweenOpenEdgeNode)
947             {
948                 QList<Eigen::Vector2d> sampling = openHalfedge->cell()->toInbetweenEdge()->getGeometry(time);
949                 if(openHalfedge->side())
950                     for(int i=0; i<sampling.size()-1; ++i) // -1 because we don't want to duplicate last sample
951                         out << sampling[i];
952                 else
953                     for(int i=sampling.size()-1; i>0; --i) // -1 because we don't want to duplicate last sample
954                         out << sampling[i];
955             }
956 
957             // Go next two times, i.e.:
958             //  openHalfedge = openHalfedge->next(time)->next(time);
959             // but with safety checks
960             openHalfedge = openHalfedge->next(time);
961             if(!openHalfedge)
962             {
963                 qWarning("Warning: sampling (partially) failed: no next node found");
964                 return;
965             }
966             openHalfedge = openHalfedge->next(time);
967             if(!openHalfedge)
968             {
969                 qWarning("Warning: sampling (partially) failed: no next node found");
970                 return;
971             }
972         }
973         while(openHalfedge != firstOpenHalfedge);
974     }
975     else if(cycleType == AnimatedCycleNode::SimpleCycle)
976     {
977         //assert(node->nodeType() == AnimatedCycleNode::KeyClosedEdgeNode ||
978         //       node->nodeType() == AnimatedCycleNode::InbetweenClosedEdgeNode);
979         if(!(node->nodeType() == AnimatedCycleNode::KeyClosedEdgeNode ||
980                node->nodeType() == AnimatedCycleNode::InbetweenClosedEdgeNode))
981         {
982             qWarning("Warning: sampling (partially) failed: wrong node type");
983             return;
984         }
985 
986         AnimatedCycleNode * firstClosedHalfedge = node;
987         AnimatedCycleNode * closedHalfedge = node;
988 
989         if(node->nodeType() == AnimatedCycleNode::KeyClosedEdgeNode)
990         {
991             do
992             {
993                 //assert(closedHalfedge->nodeType() == AnimatedCycleNode::KeyClosedEdgeNode);
994                 if(closedHalfedge->nodeType() != AnimatedCycleNode::KeyClosedEdgeNode)
995                 {
996                     qWarning("Warning: sampling (partially) failed: wrong node type");
997                     return;
998                 }
999                 QList<Eigen::Vector2d> sampling = closedHalfedge->cell()->toKeyEdge()->geometry()->sampling();
1000                 if(closedHalfedge->side())
1001                     for(int i=0; i<sampling.size()-1; ++i) // -1 because we don't want to duplicate last sample
1002                         out << sampling[i];
1003                 else
1004                     for(int i=sampling.size()-1; i>0; --i) // -1 because we don't want to duplicate last sample
1005                         out << sampling[i];
1006 
1007                 closedHalfedge = closedHalfedge->next(time);
1008                 if(!closedHalfedge)
1009                 {
1010                     qWarning("Warning: sampling (partially) failed: no next node found");
1011                     return;
1012                 }
1013             }
1014             while(closedHalfedge != firstClosedHalfedge);
1015         }
1016         else // node->nodeType() == AnimatedCycleNode::InbetweenClosedEdgeNode
1017         {
1018             do
1019             {
1020                 //assert(closedHalfedge->nodeType() == AnimatedCycleNode::InbetweenClosedEdgeNode);
1021                 if(closedHalfedge->nodeType() != AnimatedCycleNode::InbetweenClosedEdgeNode)
1022                 {
1023                     qWarning("Warning: sampling (partially) failed: wrong node type");
1024                     return;
1025                 }
1026                 QList<Eigen::Vector2d> sampling = closedHalfedge->cell()->toInbetweenEdge()->getGeometry(time);
1027                 if(closedHalfedge->side())
1028                     for(int i=0; i<sampling.size()-1; ++i) // -1 because we don't want to duplicate last sample
1029                         out << sampling[i];
1030                 else
1031                     for(int i=sampling.size()-1; i>0; --i) // -1 because we don't want to duplicate last sample
1032                         out << sampling[i];
1033 
1034                 closedHalfedge = closedHalfedge->next(time);
1035                 if(!closedHalfedge)
1036                 {
1037                     qWarning("Warning: sampling (partially) failed: no next node found");
1038                     return;
1039                 }
1040             }
1041             while(closedHalfedge != firstClosedHalfedge);
1042         }
1043     }
1044     else if(cycleType == AnimatedCycleNode::SteinerCycle)
1045     {
1046         //assert(node->nodeType() == AnimatedCycleNode::KeyVertexNode ||
1047         //       node->nodeType() == AnimatedCycleNode::InbetweenVertexNode);
1048         if(!(node->nodeType() == AnimatedCycleNode::KeyVertexNode ||
1049                node->nodeType() == AnimatedCycleNode::InbetweenVertexNode))
1050         {
1051             qWarning("Warning: sampling (partially) failed: wrong node type");
1052             return;
1053         }
1054 
1055         if(node->nodeType() == AnimatedCycleNode::KeyVertexNode)
1056         {
1057             out << node->cell()->toKeyVertex()->pos();
1058         }
1059         else
1060         {
1061             out << node->cell()->toInbetweenVertex()->pos(time);
1062         }
1063     }
1064     else
1065     {
1066         qWarning("Warning: sampling failed: invalid cycle");
1067         return;
1068         //assert(false && "invalid cycle");
1069     }
1070 }
1071 
1072 
remapPointers(VAC * newVAC)1073 void AnimatedCycle::remapPointers(VAC * newVAC)
1074 {
1075     foreach(AnimatedCycleNode * node, nodes())
1076     {
1077         node->setCell(newVAC->getCell(node->cell()->id()));
1078     }
1079 }
1080 
convertTempIdsToPointers(VAC * vac)1081 void AnimatedCycle::convertTempIdsToPointers(VAC * vac)
1082 {
1083     int n = tempNodes_.size();
1084 
1085     // First pass, create all nodes
1086     QList<AnimatedCycleNode*> nodes;
1087     for(int i=0; i<n; ++i)
1088     {
1089         TempNode tempNode = tempNodes_[i];
1090         AnimatedCycleNode * node = new AnimatedCycleNode(vac->getCell(tempNode.cell));
1091         node->setSide(tempNodes_[i].side);
1092         nodes << node;
1093     }
1094 
1095     // Second pass, link nodes together
1096     for(int i=0; i<n; ++i)
1097     {
1098         nodes[i]->setPrevious(nodes[tempNodes_[i].previous]);
1099         nodes[i]->setNext(nodes[tempNodes_[i].next]);
1100         if(tempNodes_[i].before == -1)
1101             nodes[i]->setBefore(0);
1102         else
1103             nodes[i]->setBefore(nodes[tempNodes_[i].before]);
1104         if(tempNodes_[i].after == -1)
1105             nodes[i]->setAfter(0);
1106         else
1107             nodes[i]->setAfter(nodes[tempNodes_[i].after]);
1108     }
1109 
1110     // Find first
1111     if (n > 0) {
1112         first_ = nodes[0];
1113         while(first_->before())
1114             first_ = first_->before();
1115     }
1116 
1117     // Clean
1118     tempNodes_.clear();
1119 }
1120 
1121 namespace
1122 {
str(int i)1123 QString str(int i)
1124 {
1125     return QString().setNum(i);
1126 }
1127 
str(const QMap<AnimatedCycleNode *,int> & nodeMap,AnimatedCycleNode * node)1128 QString str(const QMap<AnimatedCycleNode*,int> & nodeMap, AnimatedCycleNode * node)
1129 {
1130     if(node)
1131         return str(nodeMap[node]);
1132     else
1133         return "_";
1134 }
1135 
toInt(const QMap<int,int> & map,const QString & str)1136 int toInt(const QMap<int,int> & map, const QString & str)
1137 {
1138     if(str == "" || str == "_")
1139         return -1;
1140     else
1141         return map[str.toInt()];
1142 }
1143 }
1144 
toString() const1145 QString AnimatedCycle::toString() const
1146 {
1147     // Create correspondence between node pointers and [1..n] where n is the number of nodes
1148     QMap<AnimatedCycleNode*,int> nodeMap;
1149     int id = 1;
1150     foreach(AnimatedCycleNode * node, nodes())
1151         nodeMap[node] = id++;
1152 
1153     // Write
1154     QString res;
1155     res += "[";
1156     bool first = true;
1157     foreach(AnimatedCycleNode * node, nodes())
1158     {
1159         if(first)
1160             first = false;
1161         else
1162             res += " ";
1163 
1164         // Node id
1165         res += str(nodeMap[node]) + ":(";
1166 
1167         // Referenced cell id [and side, for edges]
1168         res += str(node->cell()->id());
1169         if(node->cell()->toEdgeCell())
1170             res += ( node->side() ? "+" : "-");
1171         res += ",";
1172 
1173         // Previous/Next/Before/After node pointers
1174         res += str(nodeMap, node->previous()) + ",";
1175         res += str(nodeMap, node->next()) + ",";
1176         res += str(nodeMap, node->before()) + ",";
1177         res += str(nodeMap, node->after()) + ")";
1178     }
1179     res += "]";
1180 
1181     return res;
1182 }
1183 
fromString(const QString & str)1184 void AnimatedCycle::fromString(const QString & str)
1185 {
1186     clear();
1187     tempNodes_.clear();
1188 
1189     // Split the string into substrings corresponding to the node data
1190     // Example:
1191     //  "[1:(15+,2,5,_,_) 2:(12,1,2,3,4)]" becomes:
1192     //  [ "1" ; "15+" ; "2" ; "5" ; "_" ; "_" ; "2" ; "12" ; "1" ; "2" ; "3" ; "4" ]
1193     QStringList d = str.split(QRegExp("[\\[\\]\\s\\,\\(\\):]"), QString::SkipEmptyParts); // use , ( ) [ ] : and whitespaces as delimiters
1194 
1195     // Get the number of nodes
1196     int n = d.size()/6;
1197 
1198     // Create a map between saved node id and node id in [0..n-1],
1199     // since we will save this data into an array, and discard the "saved node id"
1200     QMap<int,int> map;
1201     for(int i=0; i<n; ++i)
1202         map[ d[6*i].toInt() ] = i;
1203 
1204     // Store data in tempNodes
1205     for(int i=0; i<n; ++i)
1206     {
1207         AnimatedCycle::TempNode tempNode;
1208 
1209         // Referenced cell and side
1210         QString cellside = d[6*i+1];
1211         int l = cellside.length();
1212         QChar side = cellside.at(l-1);
1213         QString cell = cellside.left(l-1);
1214         if(side == '+' || side == '-')
1215         {
1216             tempNode.cell = cell.toInt();
1217             tempNode.side = (side == '+') ? true : false;
1218         }
1219         else
1220         {
1221             tempNode.cell = cellside.toInt();
1222             tempNode.side = true; // true or false is irrelevant, choose true arbitrarily
1223         }
1224 
1225         // Previous/Next/Before/After node pointers
1226         tempNode.previous = toInt(map, d[6*i+2]);
1227         tempNode.next = toInt(map, d[6*i+3]);
1228         tempNode.before = toInt(map, d[6*i+4]);
1229         tempNode.after = toInt(map, d[6*i+5]);
1230 
1231         // Add to list of nodes
1232         tempNodes_ << tempNode;
1233     }
1234 }
1235 
1236 
1237 
1238 } // end namespace VectorAnimationComplex
1239 
operator <<(QTextStream & out,const VectorAnimationComplex::AnimatedCycle & cycle)1240 QTextStream & operator<<(QTextStream & out, const VectorAnimationComplex::AnimatedCycle & cycle)
1241 {
1242     using namespace VectorAnimationComplex;
1243 
1244     // Create correspondence between node pointers and [0..n-1] where n is the number of nodes
1245     QMap<AnimatedCycleNode*,int> nodeMap;
1246     int id = 0;
1247     foreach(AnimatedCycleNode * node, cycle.nodes())
1248         nodeMap[node] = id++;
1249 
1250     // Write to file
1251     out << "[";
1252     foreach(AnimatedCycleNode * node, cycle.nodes())
1253     {
1254         if(nodeMap[node]!=0) out << " ,";
1255         out << " "
1256             << "(" << node->cell()->id()
1257             << "," << nodeMap[node->previous()]
1258             << "," << nodeMap[node->next()]
1259             << "," << (node->before() ? nodeMap[node->before()] : -1)
1260             << "," << (node->after() ? nodeMap[node->after()] : -1)
1261             << "," << node->side() << ")";
1262     }
1263     out << " ]";
1264 
1265     return out;
1266 }
1267 
operator >>(QTextStream & in,VectorAnimationComplex::AnimatedCycle & cycle)1268 QTextStream & operator>>(QTextStream & in, VectorAnimationComplex::AnimatedCycle & cycle)
1269 {
1270     using namespace VectorAnimationComplex;
1271 
1272     cycle.tempNodes_.clear();
1273 
1274     // put the list to read as a string
1275     QString listAsString;
1276     in >> listAsString; // read "["
1277     int openedBracket = 1;
1278     char c;
1279     while(openedBracket != 0)
1280     {
1281         in >> c;
1282         if(c == '[')
1283             openedBracket++;
1284         if(c == ']')
1285             openedBracket--;
1286 
1287         listAsString.append(c);
1288     }
1289 
1290     // test if the list is void
1291     QString copyString = listAsString;
1292     QTextStream test(&copyString);
1293     QString b1, b2;
1294     test >> b1 >> b2;
1295 
1296     // if not void
1297     if(b2 != "]")
1298     {
1299         QString nuple;
1300         QTextStream newIn(&listAsString);
1301         newIn >> b1; // read "["
1302         QString delimiter(",");
1303         while(delimiter == ",")
1304         {
1305             newIn >> nuple;
1306             QStringList list = nuple.split(QRegExp("\\s*[\\(\\,\\)]\\s*"),
1307                                            QString::SkipEmptyParts);
1308             AnimatedCycle::TempNode tempNode;
1309             tempNode.cell = list[0].toInt();
1310             tempNode.previous = list[1].toInt();
1311             tempNode.next = list[2].toInt();
1312             tempNode.before = list[3].toInt();
1313             tempNode.after = list[4].toInt();
1314             tempNode.side = list[5].toInt();
1315             cycle.tempNodes_ << tempNode;
1316 
1317             newIn >> delimiter;
1318         }
1319     }
1320 
1321     return in;
1322 }
1323