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(©String);
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