1 // renderimpl.cpp
2 // this file is part of Context Free
3 // ---------------------
4 // Copyright (C) 2006-2008 Mark Lentczner - markl@glyphic.com
5 // Copyright (C) 2006-2014 John Horigan - john@glyphic.com
6 //
7 // This program is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU General Public License
9 // as published by the Free Software Foundation; either version 2
10 // of the License, or (at your option) any later version.
11 //
12 // This program is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 // GNU General Public License for more details.
16 //
17 // You should have received a copy of the GNU General Public License
18 // along with this program; if not, write to the Free Software
19 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
20 //
21 // John Horigan can be contacted at john@glyphic.com or at
22 // John Horigan, 1209 Villa St., Mountain View, CA 94041-1123, USA
23 //
24 // Mark Lentczner can be contacted at markl@glyphic.com or at
25 // Mark Lentczner, 1209 Villa St., Mountain View, CA 94041-1123, USA
26 //
27 //
28 
29 
30 #include "renderimpl.h"
31 
32 #include <iterator>
33 #include <string>
34 #include <algorithm>
35 #include <stack>
36 #include <cassert>
37 #include <functional>
38 #include <cstddef>
39 
40 #include <cmath>
41 using std::isfinite;
42 
43 #include "shapeSTL.h"
44 #include "primShape.h"
45 #include "builder.h"
46 #include "astreplacement.h"
47 #include "CmdInfo.h"
48 #include "tiledCanvas.h"
49 
50 using namespace AST;
51 
52 //#define DEBUG_SIZES
53 unsigned int RendererImpl::MoveFinishedAt = 0;     // when this many, move to file
54 unsigned int RendererImpl::MoveUnfinishedAt = 0;   // when this many, move to files
55 unsigned int RendererImpl::MaxMergeFiles = 0;      // maximum number of files to merge at once
56 
57 const double SHAPE_BORDER = 1.0; // multiplier of shape size when calculating bounding box
58 const double FIXED_BORDER = 8.0; // fixed extra border, in pixels
59 
RendererImpl(const cfdg_ptr & cfdg,int width,int height,double minSize,int variation,double border)60 RendererImpl::RendererImpl( const cfdg_ptr& cfdg,
61                             int width, int height, double minSize,
62                             int variation, double border)
63     : RendererAST(width, height), m_cfdg(std::dynamic_pointer_cast<CFDGImpl>(cfdg)),
64       m_canvas(nullptr), mColorConflict(false),
65       m_maxShapes(500000000), mVariation(variation), m_border(border),
66       mScaleArea(0.0), mScale(0.0), m_currScale(0.0), m_currArea(0.0),
67       m_minSize(minSize), mFrameTimeBounds(1.0, -Renderer::Infinity, Renderer::Infinity),
68       shapeCopies(primShape::shapeMap), shapeMap{}
69 {
70     assert(m_cfdg);
71     if (MoveFinishedAt == 0) {
72 #ifndef DEBUG_SIZES
73         std::size_t mem = m_cfdg->system()->getPhysicalMemory();
74         if (mem == 0) {
75             MoveFinishedAt = MoveUnfinishedAt = 2000000;
76         } else {
77             MoveFinishedAt = MoveUnfinishedAt = static_cast<unsigned int>(mem / (sizeof(FinishedShape) * 4));
78         }
79         MaxMergeFiles      =      200; // maximum number of files to merge at once
80 #else
81         MoveFinishedAt     =    1000; // when this many, move to file
82         MoveUnfinishedAt   =     200; // when this many, move to files
83         MaxMergeFiles      =       4; // maximum number of files to merge at once
84 #endif
85     }
86 
87     for (std::size_t i = 0; i < shapeMap.size(); ++i)
88         shapeMap[i] = CommandInfo(&shapeCopies[i]);
89 
90     m_cfdg->hasParameter(CFG::FrameTime, mCurrentTime, nullptr);
91     m_cfdg->hasParameter(CFG::Frame, mCurrentFrame, nullptr);
92 }
93 
94 void
colorConflict(const yy::location & w)95 RendererImpl::colorConflict(const yy::location& w)
96 {
97     if (mColorConflict) return;
98     CfdgError err(w, "Conflicting color change");
99     system()->error();
100     system()->syntaxError(err);
101     mColorConflict = true;
102 }
103 
104 void
init()105 RendererImpl::init()
106 {
107     // Performs RendererImpl initializations that are needed before rendering
108     // and before each frame of an animation
109 
110     mCurrentSeed.seed(static_cast<unsigned long long>(mVariation));
111     mCurrentSeed();
112 
113     mLogicalStackTop = mCFstack.data();
114     mStackSize = 0;
115 
116     Shape dummy;
117     for (const rep_ptr& rep: m_cfdg->mCFDGcontents.mBody) {
118         if (const ASTdefine* def = dynamic_cast<const ASTdefine*> (rep.get()))
119             def->traverse(dummy, false, this);
120     }
121 
122     mFinishedFileCount = 0;
123     mUnfinishedFileCount = 0;
124 
125     mFixedBorderX = mFixedBorderY = 0.0;
126     mShapeBorder = 1.0;
127     mTotalArea = 0.0;
128 
129     m_minArea = 0.3;
130     m_outputSoFar = m_stats.shapeCount = m_stats.toDoCount = 0;
131     double minSize = m_minSize;
132     m_cfdg->hasParameter(CFG::MinimumSize, minSize, this);
133     minSize = (minSize <= 0.0) ? 0.3 : minSize;
134     m_minArea = minSize * minSize;
135 
136     mFixedBorderX = FIXED_BORDER * ((m_border <= 1.0) ? m_border : 1.0);
137     mShapeBorder = SHAPE_BORDER * ((m_border <= 1.0) ? 1.0 : m_border);
138 
139     m_cfdg->hasParameter(CFG::BorderFixed, mFixedBorderX, this);
140     m_cfdg->hasParameter(CFG::BorderDynamic, mShapeBorder, this);
141     if (2 * static_cast<int>(fabs(mFixedBorderX)) >= std::min(m_width, m_height))
142         mFixedBorderX = 0.0;
143     if (mShapeBorder <= 0.0)
144         mShapeBorder = 1.0;
145 
146     if (m_cfdg->hasParameter(CFG::MaxNatural, mMaxNatural, this) &&
147         (mMaxNatural < 1.0 || (mMaxNatural - 1.0) == mMaxNatural))
148     {
149         const ASTexpression* max = m_cfdg->hasParameter(CFG::MaxNatural);
150         throw CfdgError(max->where, (mMaxNatural < 1.0) ?
151                             "CF::MaxNatural must be >= 1" :
152                             "CF::MaxNatural must be < 9007199254740992");
153     }
154 
155     mCurrentPath = std::make_unique<AST::ASTcompiledPath>();
156 
157     m_cfdg->getSymmetry(mSymmetryOps, this);
158     m_cfdg->setBackgroundColor(this);
159 }
160 
161 void
initBounds()162 RendererImpl::initBounds()
163 {
164     init();
165     double tile_x, tile_y;
166     m_tiled = m_cfdg->isTiled(nullptr, &tile_x, &tile_y);
167     m_frieze = m_cfdg->isFrieze(nullptr, &tile_x, &tile_y);
168     m_sized = m_cfdg->isSized(&tile_x, &tile_y);
169     m_timed = m_cfdg->isTimed(&mTimeBounds);
170 
171     if (m_tiled || m_sized) {
172         mFixedBorderX = mShapeBorder = 0.0;
173         mBounds.mMin_X = -(mBounds.mMax_X = tile_x / 2.0);
174         mBounds.mMin_Y = -(mBounds.mMax_Y = tile_y / 2.0);
175         rescaleOutput(m_width, m_height, true);
176         mScaleArea = m_currArea;
177     }
178     if (m_frieze == CFDG::frieze_x)
179         m_frieze_size = tile_x / 2.0;
180     if (m_frieze == CFDG::frieze_y)
181         m_frieze_size = tile_y / 2.0;
182     if (m_frieze != CFDG::frieze_y)
183         mFixedBorderY = mFixedBorderX;
184     if (m_frieze == CFDG::frieze_x)
185         mFixedBorderX = 0.0;
186 }
187 
188 void
resetSize(int x,int y)189 RendererImpl::resetSize(int x, int y)
190 {
191     m_width = x;
192     m_height = y;
193     if (m_tiled || m_sized) {
194         m_currScale = m_currArea = 0.0;
195         rescaleOutput(m_width, m_height, true);
196         mScaleArea = m_currArea;
197     }
198 }
199 
~RendererImpl()200 RendererImpl::~RendererImpl()
201 {
202     cleanup();
203 }
204 
205 class Stopped { };
206 
207 void
cleanup()208 RendererImpl::cleanup()
209 {
210     // delete temp files before checking for abort
211     m_finishedFiles.clear();
212     m_unfinishedFiles.clear();
213 
214     // Delete all shapes and parameters (except those in the AST)
215     mUnfinishedShapes.clear();
216     mFinishedShapes.clear();
217 
218     // Delete the global definitions
219     unwindStack(0, m_cfdg->mCFDGcontents.mParameters);
220 
221     mCurrentPath.reset();
222     m_cfdg->resetCachedPaths();
223 }
224 
225 void
setMaxShapes(int n)226 RendererImpl::setMaxShapes(int n)
227 {
228     m_maxShapes = n ? n : 400000000;
229 }
230 
231 void
resetBounds()232 RendererImpl::resetBounds()
233 {
234     mBounds = Bounds();
235 }
236 
237 
238 void
outputPrep(Canvas * canvas)239 RendererImpl::outputPrep(Canvas* canvas)
240 {
241     m_canvas = canvas;
242 
243     if (canvas) {
244         m_width = canvas->mWidth;
245         m_height = canvas->mHeight;
246         if (m_tiled || m_frieze) {
247             agg::trans_affine tr;
248             m_cfdg->isTiled(&tr);
249             m_cfdg->isFrieze(&tr);
250             m_tiledCanvas = std::make_unique<tiledCanvas>(canvas, tr, m_frieze);
251             m_tiledCanvas->scale(m_currScale);
252             m_canvas = m_tiledCanvas.get();
253         }
254 
255         mFrameTimeBounds.load_from(1.0, -Renderer::Infinity, Renderer::Infinity);
256     }
257 
258     requestStop = false;
259     requestFinishUp = false;
260     requestUpdate = false;
261 
262     m_stats.inOutput = false;
263     m_stats.animating = false;
264     m_stats.finalOutput = false;
265 }
266 
267 
268 double
run(Canvas * canvas,bool partialDraw)269 RendererImpl::run(Canvas * canvas, bool partialDraw)
270 {
271     if (!m_stats.animating)
272         outputPrep(canvas);
273 
274     int reportAt = 250;
275 
276     {
277         Shape initShape = m_cfdg->getInitialShape(this);
278         initShape.mWorldState.mRand64Seed = mCurrentSeed;
279         if (!m_timed)
280             mTimeBounds = initShape.mWorldState.m_time;
281 
282         try {
283             processShape(initShape);
284         } catch (CfdgError& e) {
285             requestStop = true;
286             system()->error();
287             system()->syntaxError(e);
288         } catch (std::exception& e) {
289             requestStop = true;
290             system()->catastrophicError(e.what());
291         }
292     }
293 
294     for (;;) {
295         fileIfNecessary();
296 
297         if (requestStop) break;
298         if (requestFinishUp) break;
299 
300         if (mUnfinishedShapes.empty()) break;
301         if (std::max(m_stats.shapeCount, m_stats.toDoCount) >= m_maxShapes)
302             break;
303 
304         // Get the largest unfinished shape
305         Shape s(std::move(mUnfinishedShapes.front()));
306         std::pop_heap(mUnfinishedShapes.begin(), mUnfinishedShapes.end());
307         mUnfinishedShapes.pop_back();
308         m_stats.toDoCount--;
309 
310         try {
311             const ASTrule* rule = m_cfdg->findRule(s.mShapeType, s.mWorldState.mRand64Seed.getDouble());
312             m_drawingMode = false;      // shouldn't matter
313             rule->traverseRule(s, this);
314         } catch (CfdgError& e) {
315             requestStop = true;
316             system()->error();
317             system()->syntaxError(e);
318             break;
319         } catch (std::exception& e) {
320             requestStop = true;
321             system()->catastrophicError(e.what());
322             break;
323         }
324 
325         if (requestUpdate || (m_stats.shapeCount > reportAt)) {
326             if (partialDraw)
327               outputPartial();
328             outputStats();
329             reportAt = 2 * m_stats.shapeCount;
330         }
331     }
332 
333     if (!m_cfdg->usesTime && !m_timed)
334         mTimeBounds.load_from(1.0, 0.0, mTotalArea);
335 
336     if (!requestStop) {
337         outputFinal();
338     }
339 
340     outputStats();
341     if (m_canvas)
342         system()->message("Done.");
343 
344     if (!m_canvas && m_frieze)
345         rescaleOutput(m_width, m_height, true);
346 
347     return m_currScale;
348 }
349 
350 void
draw(Canvas * canvas)351 RendererImpl::draw(Canvas* canvas)
352 {
353     mFrameTimeBounds.load_from(1.0, -Renderer::Infinity, Renderer::Infinity);
354     outputPrep(canvas);
355     outputFinal();
356     outputStats();
357 }
358 
359 class OutputBounds
360 {
361 public:
362     OutputBounds(int frames, const agg::trans_affine_time& timeBounds,
363                  int width, int height, RendererImpl& renderer);
364     void apply(const FinishedShape&);
365 
frameBounds(int frame)366     const Bounds& frameBounds(int frame) { return mFrameBounds[frame]; }
frameCount(int frame)367     int           frameCount(int frame) { return mFrameCounts[frame]; }
368 
369     void finalAccumulate();
370     // call after all the frames to compute the bounds at each frame
371 
372     void backwardFilter(double framesToHalf);
373     void smooth(int window);
374 
375 private:
376     agg::trans_affine_time mTimeBounds;
377     double              mFrameScale;
378     std::vector<Bounds> mFrameBounds;
379     std::vector<int>    mFrameCounts;
380     double              mScale;
381     int                 mWidth;
382     int                 mHeight;
383     int                 mFrames;
384     RendererImpl&       mRenderer;
385 
386     OutputBounds& operator=(const OutputBounds&);   // not defined
387 };
388 
OutputBounds(int frames,const agg::trans_affine_time & timeBounds,int width,int height,RendererImpl & renderer)389 OutputBounds::OutputBounds(int frames, const agg::trans_affine_time& timeBounds,
390                            int width, int height, RendererImpl& renderer)
391 : mTimeBounds(timeBounds), mScale(0.0),
392   mWidth(width), mHeight(height), mFrames(frames), mRenderer(renderer)
393 {
394     mFrameScale = static_cast<double>(frames) / (timeBounds.tend - timeBounds.tbegin);
395     mFrameBounds.resize(frames);
396     mFrameCounts.resize(frames, 0);
397 }
398 
399 void
apply(const FinishedShape & s)400 OutputBounds::apply(const FinishedShape& s)
401 {
402     if (mRenderer.requestStop ||  mRenderer.requestFinishUp) throw Stopped();
403 
404     if (mScale == 0.0) {
405         // If we don't know the approximate scale yet then just
406         // make an educated guess.
407         mScale = (mWidth + mHeight) / sqrt(fabs(s.mWorldState.m_transform.determinant()));
408     }
409 
410     agg::trans_affine_time frameTime(s.mWorldState.m_time);
411     frameTime.translate(-mTimeBounds.tbegin);
412     frameTime.scale(mFrameScale);
413     int begin = (frameTime.tbegin < mFrames) ? static_cast<int>(std::floor(frameTime.tbegin)) : (mFrames - 1);
414     int end = (frameTime.tend < mFrames) ? static_cast<int>(std::floor(frameTime.tend)) : (mFrames - 1);
415     if (begin < 0) begin = 0;
416     if (end < 0) end = 0;
417     for (int frame = begin; frame <= end; ++frame) {
418         mFrameBounds[frame] += s.mBounds;
419     }
420     mFrameCounts[begin] += 1;
421 }
422 
423 void
finalAccumulate()424 OutputBounds::finalAccumulate()
425 {
426     return;
427     // Accumulation is done in the apply method
428 #if 0
429     vector<Bounds>::iterator prev, curr, end;
430     prev = mFrameBounds.begin();
431     end = mFrameBounds.end();
432     if (prev == end) return;
433 
434     for (curr = prev + 1; curr != end; prev = curr, ++curr) {
435         *curr += *prev;
436     }
437 #endif
438 }
439 
440 void
backwardFilter(double framesToHalf)441 OutputBounds::backwardFilter(double framesToHalf)
442 {
443     double alpha = pow(0.5, 1.0 / framesToHalf);
444 
445     std::vector<Bounds>::reverse_iterator prev, curr, end;
446     prev = mFrameBounds.rbegin();
447     end = mFrameBounds.rend();
448     if (prev == end) return;
449 
450     for (curr = prev + 1; curr != end; prev = curr, ++curr) {
451         *curr = curr->interpolate(*prev, alpha);
452     }
453 }
454 
455 void
smooth(int window)456 OutputBounds::smooth(int window)
457 {
458     std::size_t frames = mFrameBounds.size();
459     if (frames == 0) return;
460 
461     mFrameBounds.resize(frames + window - 1, mFrameBounds.back());
462 
463     std::vector<Bounds>::iterator write, read, end;
464     read = mFrameBounds.begin();
465 
466     double factor = 1.0 / window;
467 
468     Bounds accum;
469     for (int i = 0; i < window; ++i)
470         accum.gather(*read++, factor);
471 
472     write = mFrameBounds.begin();
473     end = mFrameBounds.end();
474     for (;;) {
475         Bounds old = *write;
476         *write++ = accum;
477         accum.gather(old, -factor);
478 
479         if (read == end) break;
480 
481         accum.gather(*read++, factor);
482     }
483 
484     mFrameBounds.resize(frames);
485 }
486 
487 
488 void
animate(Canvas * canvas,int frames,int frame,bool zoom)489 RendererImpl::animate(Canvas* canvas, int frames, int frame, bool zoom)
490 {
491     const bool ftime = m_cfdg->usesFrameTime;
492     zoom = zoom && !ftime;
493 
494     if (!ftime){
495         system()->message("Precomputing time/space bounds");
496         run(nullptr, false);
497     }
498 
499     int curr_width = m_width;
500     int curr_height = m_height;
501     rescaleOutput(curr_width, curr_height, true);
502 
503     outputPrep(canvas);
504 
505     double frameInc = (mTimeBounds.tend - mTimeBounds.tbegin) / frames;
506 
507     OutputBounds outputBounds(frames, mTimeBounds, curr_width, curr_height, *this);
508     if (!ftime) {
509         system()->message("Computing zoom");
510 
511         try {
512             forEachShape(true, [&](const FinishedShape& s) {
513                 outputBounds.apply(s);
514             });
515             m_outputSoFar = 0;  // gets set by forEachShape, must be cleared
516             //outputBounds.finalAccumulate();
517             outputBounds.backwardFilter(10.0);
518             //outputBounds.smooth(3);
519         } catch (Stopped&) {
520             m_stats.animating = false;
521             return;
522         } catch (std::exception& e) {
523             system()->catastrophicError(e.what());
524             return;
525         }
526     }
527 
528     m_stats.shapeCount = 0;
529     m_stats.animating = true;
530     mFrameTimeBounds.tend = mTimeBounds.tbegin;
531 
532     Bounds saveBounds = mBounds;
533 
534     for (int frameCount = 1; frameCount <= frames; ++frameCount)
535     {
536         if (frame && frameCount != frame) continue;
537         system()->message("Generating frame %d of %d", frameCount, frames);
538 
539         if (zoom) mBounds = outputBounds.frameBounds(frameCount - 1);
540         m_stats.shapeCount += outputBounds.frameCount(frameCount - 1);
541         mFrameTimeBounds.tbegin = mFrameTimeBounds.tend;
542         mFrameTimeBounds.tend = mTimeBounds.tbegin + frameInc * frameCount;
543 
544         if (ftime) {
545             mCurrentTime = (mFrameTimeBounds.tbegin + mFrameTimeBounds.tend) * 0.5;
546             mCurrentFrame = (frameCount - 1.0)/(frames - 1.0);
547             try {
548                 initBounds();
549             } catch (CfdgError& err) {
550                 system()->error();
551                 system()->syntaxError(err);
552                 cleanup();
553                 mBounds = saveBounds;
554                 m_stats.animating = false;
555                 outputStats();
556                 return;
557             }
558             run(canvas, false);
559         } else {
560             outputFinal();
561             outputStats();
562         }
563 
564         if (ftime)
565             cleanup();
566 
567         if (canvas->mError) {
568             system()->message("An error occurred generating frame %d", frameCount);
569             break;
570         }
571 
572         if (requestStop || requestFinishUp) break;
573     }
574 
575     mBounds = saveBounds;
576     m_stats.animating = false;
577     outputStats();
578     if (frame == 0)
579         system()->message("Animation of %d frames complete", frames);
580 }
581 
582 void
processShape(Shape & s)583 RendererImpl::processShape(Shape& s)
584 {
585     double area = s.area();
586     if (!s.mWorldState.isFinite()) {
587         requestStop = true;
588         system()->error();
589         system()->message("A shape has undefined or infinite state: %s", m_cfdg->decodeShapeName(s.mShapeType).c_str());
590         return;
591     }
592 
593     if (s.mWorldState.m_time.tbegin > s.mWorldState.m_time.tend) {
594         return;
595     }
596 
597     if (m_cfdg->getShapeType(s.mShapeType) == CFDGImpl::ruleType &&
598         m_cfdg->shapeHasRules(s.mShapeType))
599     {
600         // only add it if it's big enough (or if there are no finished shapes yet)
601         if (!mBounds.valid() || (area * mScaleArea >= m_minArea)) {
602             m_stats.toDoCount++;
603             mUnfinishedShapes.push_back(std::move(s));
604             std::push_heap(mUnfinishedShapes.begin(), mUnfinishedShapes.end());
605         }
606     } else if (m_cfdg->getShapeType(s.mShapeType) == CFDGImpl::pathType) {
607         const ASTrule* rule = m_cfdg->findRule(s.mShapeType, 0.0);
608         processPrimShape(s, rule);
609     } else if (primShape::isPrimShape(s.mShapeType)) {
610         processPrimShape(s);
611     } else {
612         requestStop = true;
613         system()->error();
614         system()->message("Shape with no rules encountered: %s", m_cfdg->decodeShapeName(s.mShapeType).c_str());
615         return;
616     }
617 }
618 
619 void
processPrimShape(Shape & s,const ASTrule * path)620 RendererImpl::processPrimShape(Shape& s, const ASTrule* path)
621 {
622     if (mSymmetryOps.empty() || s.mShapeType == primShape::fillType) {
623         processPrimShapeSiblings(std::move(s), path);
624     } else {
625         for (auto&& xform: mSymmetryOps) {
626             Shape sym(s);
627             sym.mWorldState.m_transform.multiply(xform);
628             processPrimShapeSiblings(std::move(sym), path);
629         }
630     }
631 }
632 
633 void
processPrimShapeSiblings(Shape && s,const ASTrule * path)634 RendererImpl::processPrimShapeSiblings(Shape&& s, const ASTrule* path)
635 {
636     if (mScale == 0.0) {
637         // If we don't know the approximate scale yet then just
638         // make an educated guess.
639         mScale = (m_width + m_height) / sqrt(fabs(s.mWorldState.m_transform.determinant()));
640     }
641     if (path || s.mShapeType != primShape::fillType) {
642         mCurrentArea = 0.0;
643         mPathBounds.invalidate();
644         m_drawingMode = false;
645         if (path) {
646             mOpsOnly = false;
647             path->traversePath(s, this);
648         } else {
649             CommandInfo* attr = nullptr;
650             if (s.mShapeType < 3) attr = &(shapeMap[s.mShapeType]);
651             processPathCommand(s, attr);
652         }
653         // Drop off-canvas shapes if CF::Size is specified, or any shape where
654         // something weird happened while determining its bounds
655         if (!mPathBounds.valid() || (m_sized && !mPathBounds.overlaps(mBounds)))
656             return;
657         mTotalArea += mCurrentArea;
658         if (!m_tiled && !m_sized) {
659             mBounds.merge(mPathBounds.dilate(mShapeBorder));
660             if (m_frieze == CFDG::frieze_x)
661                 mBounds.mMin_X = -(mBounds.mMax_X = m_frieze_size);
662             if (m_frieze == CFDG::frieze_y)
663                 mBounds.mMin_Y = -(mBounds.mMax_Y = m_frieze_size);
664             mScale = mBounds.computeScale(m_width, m_height,
665                                           mFixedBorderX, mFixedBorderY, false);
666             mScaleArea = mScale * mScale;
667         }
668     } else {
669         mCurrentArea = 1.0;
670     }
671     m_stats.shapeCount++;
672     FinishedShape fs(std::move(s), m_stats.shapeCount, mPathBounds);
673     fs.mWorldState.m_Z.sz = mCurrentArea;
674     if (!m_cfdg->usesTime) {
675         fs.mWorldState.m_time.tbegin = mTotalArea;
676         fs.mWorldState.m_time.tend = Renderer::Infinity;
677     }
678     if (fs.mWorldState.m_time.tbegin < mTimeBounds.tbegin &&
679         isfinite(fs.mWorldState.m_time.tbegin) && !m_timed)
680     {
681         mTimeBounds.tbegin = fs.mWorldState.m_time.tbegin;
682     }
683     if (fs.mWorldState.m_time.tbegin > mTimeBounds.tend &&
684         isfinite(fs.mWorldState.m_time.tbegin) && !m_timed)
685     {
686         mTimeBounds.tend = fs.mWorldState.m_time.tbegin;
687     }
688     if (fs.mWorldState.m_time.tend > mTimeBounds.tend &&
689         isfinite(fs.mWorldState.m_time.tend) && !m_timed)
690     {
691         mTimeBounds.tend = fs.mWorldState.m_time.tend;
692     }
693     if (fs.mWorldState.m_time.tend < mTimeBounds.tbegin &&
694         isfinite(fs.mWorldState.m_time.tend) && !m_timed)
695     {
696         mTimeBounds.tbegin = fs.mWorldState.m_time.tend;
697     }
698     if (!fs.mWorldState.isFinite()) {
699         requestStop = true;
700         system()->error();
701         system()->message("A shape has undefined or infinite state: %s", m_cfdg->decodeShapeName(fs.mShapeType).c_str());
702         return;
703     }
704     // Drop shapes outside the current frame if we are animating and rerunning
705     // the cfdg file for every frame.
706     if (!m_cfdg->usesFrameTime || fs.mWorldState.m_time.overlaps(mFrameTimeBounds))
707         mFinishedShapes.push_back(fs);
708 }
709 
710 void
processSubpath(const Shape & s,bool tr,int expectedType)711 RendererImpl::processSubpath(const Shape& s, bool tr, int expectedType)
712 {
713     const ASTrule* rule = nullptr;
714     if (m_cfdg->getShapeType(s.mShapeType) != CFDGImpl::pathType &&
715         primShape::isPrimShape(s.mShapeType) && expectedType == ASTreplacement::op)
716     {
717         static const ASTrule PrimitivePaths[primShape::numTypes] = { { 0 }, { 1 }, { 2 }, { 3 } };
718         rule = &PrimitivePaths[s.mShapeType];
719     } else {
720         rule = m_cfdg->findRule(s.mShapeType, 0.0);
721     }
722     if (static_cast<int>(rule->mRuleBody.mRepType) != expectedType)
723         throw CfdgError(rule->mLocation, "Subpath is not of the expected type (path ops/commands)");
724     bool saveOpsOnly = mOpsOnly;
725     mOpsOnly = mOpsOnly || (expectedType == ASTreplacement::op);
726     rule->mRuleBody.traverse(s, tr, this, true);
727     mOpsOnly = saveOpsOnly;
728 }
729 
730 
731 //-------------------------------------------------------------------------////
732 
733 
734 void
fileIfNecessary()735 RendererImpl::fileIfNecessary()
736 {
737     if (mFinishedShapes.size() > MoveFinishedAt)
738         moveFinishedToFile();
739 
740     if (mUnfinishedShapes.size() > MoveUnfinishedAt)
741         moveUnfinishedToTwoFiles();
742     else if (mUnfinishedShapes.empty())
743         getUnfinishedFromFile();
744 }
745 
746 void
moveUnfinishedToTwoFiles()747 RendererImpl::moveUnfinishedToTwoFiles()
748 {
749     m_unfinishedFiles.emplace_back(system(), AbstractSystem::ExpansionTemp,
750                                    ++mUnfinishedFileCount);
751     auto f1 = m_unfinishedFiles.back().forWrite();
752     int num1 = m_unfinishedFiles.back().number();
753 
754     m_unfinishedFiles.emplace_back(system(), AbstractSystem::ExpansionTemp,
755                                    ++mUnfinishedFileCount);
756     auto f2 = m_unfinishedFiles.back().forWrite();
757     int num2 = m_unfinishedFiles.back().number();
758 
759     system()->message("Writing %s temp files %d & %d",
760                       m_unfinishedFiles.back().type().c_str(), num1, num2);
761 
762     std::size_t count = mUnfinishedShapes.size() / 3;
763 
764     UnfinishedContainer::iterator usi = mUnfinishedShapes.begin(),
765                                   use = mUnfinishedShapes.end();
766     usi += count;
767 
768     if (f1 && f1->good() && f2 && f2->good()) {
769         AbstractSystem::Stats outStats = m_stats;
770         outStats.mSystem = system();
771         outStats.outputCount = static_cast<int>(count);
772         outStats.outputDone = 0;
773         *f1 << outStats.outputCount;
774         *f2 << outStats.outputCount;
775         outStats.outputCount = static_cast<int>(count * 2);
776         outStats.showProgress = true;
777         // Split the bottom 2/3 of the heap between the two files
778         while (usi != use) {
779             usi->write(*((m_unfinishedInFilesCount & 1) ? f1 : f2));
780             ++usi;
781             ++m_unfinishedInFilesCount;
782             ++outStats.outputDone;
783             if (requestUpdate) {
784                 system()->stats(outStats);
785                 requestUpdate = false;
786             }
787             if (requestStop || requestFinishUp)
788                 return;
789         }
790     } else {
791         system()->message("Cannot open temporary file for expansions");
792         requestStop = true;
793         return;
794     }
795 
796     // Remove the written shapes, heap property remains intact
797     static const Shape neverActuallyUsed;
798     mUnfinishedShapes.resize(count, neverActuallyUsed);
799     assert(std::is_heap(mUnfinishedShapes.begin(), mUnfinishedShapes.end()));
800 }
801 
802 void
getUnfinishedFromFile()803 RendererImpl::getUnfinishedFromFile()
804 {
805     if (m_unfinishedFiles.empty()) return;
806 
807     TempFile t(std::move(m_unfinishedFiles.front()));
808     m_unfinishedFiles.pop_front();
809 
810     auto f = t.forRead();
811 
812     if (f->good()) {
813         AbstractSystem::Stats outStats = m_stats;
814         outStats.mSystem = system();
815         *f >> outStats.outputCount;
816         outStats.outputDone = 0;
817         outStats.showProgress = true;
818         std::istream_iterator<Shape> it(*f);
819         std::istream_iterator<Shape> eit;
820         std::back_insert_iterator< UnfinishedContainer > sendto(mUnfinishedShapes);
821         while (it != eit) {
822             *sendto = *it;
823             ++it;
824             ++outStats.outputDone;
825             if (requestUpdate) {
826                 system()->stats(outStats);
827                 requestUpdate = false;
828             }
829             if (requestStop || requestFinishUp)
830                 return;
831         }
832     } else {
833         system()->message("Cannot open temporary file for expansions");
834         requestStop = true;
835         return;
836     }
837     system()->message("Resorting expansions");
838     fixupHeap();
839 }
840 
841 void
fixupHeap()842 RendererImpl::fixupHeap()
843 {
844     // Restore heap property to mUnfinishedShapes
845     auto first = mUnfinishedShapes.begin();
846     auto end = mUnfinishedShapes.end();
847     auto n = mUnfinishedShapes.size();
848     if (n < 2)
849         return;
850 
851     AbstractSystem::Stats outStats = m_stats;
852     outStats.mSystem = system();
853     outStats.outputCount = static_cast<int>(n);
854     outStats.outputDone = 0;
855     outStats.showProgress = true;
856 
857     for (auto last = first + 2; last <= end; ++last) {
858         std::push_heap(first, last);
859 
860         ++outStats.outputDone;
861         if (requestUpdate) {
862             system()->stats(outStats);
863             requestUpdate = false;
864         }
865         if (requestStop || requestFinishUp)
866             return;
867     }
868     assert(std::is_heap(mUnfinishedShapes.begin(), mUnfinishedShapes.end()));
869 }
870 
871 //-------------------------------------------------------------------------////
872 
873 void
moveFinishedToFile()874 RendererImpl::moveFinishedToFile()
875 {
876     m_finishedFiles.emplace_back(system(), AbstractSystem::ShapeTemp, ++mFinishedFileCount);
877 
878     auto f = m_finishedFiles.back().forWrite();
879 
880     if (f && f->good()) {
881         if (mFinishedShapes.size() > 10000)
882             system()->message("Sorting shapes...");
883         std::sort(mFinishedShapes.begin(), mFinishedShapes.end());
884         AbstractSystem::Stats outStats = m_stats;
885         outStats.mSystem = system();
886         outStats.outputCount = static_cast<int>(mFinishedShapes.size());
887         outStats.outputDone = 0;
888         outStats.showProgress = true;
889         for (const FinishedShape& fs: mFinishedShapes) {
890             *f << fs;
891             ++outStats.outputDone;
892             if (requestUpdate) {
893                 system()->stats(outStats);
894                 requestUpdate = false;
895             }
896             if (requestStop)
897                 return;
898         }
899     } else {
900         system()->message("Cannot open temporary file for shapes");
901         requestStop = true;
902         return;
903     }
904 
905     mFinishedShapes.clear();
906 }
907 
908 //-------------------------------------------------------------------------////
909 
rescaleOutput(int & curr_width,int & curr_height,bool final)910 void RendererImpl::rescaleOutput(int& curr_width, int& curr_height, bool final)
911 {
912     agg::trans_affine trans;
913     double scale;
914 
915     if (!mBounds.valid()) return;
916 
917     scale = mBounds.computeScale(curr_width, curr_height,
918                                  mFixedBorderX, mFixedBorderY, true,
919                                  &trans, m_tiled || m_sized || m_frieze);
920 
921     if (final                       // if final output
922     || m_currScale == 0.0           // if first time, use this scale
923     || (m_currScale * 0.90) > scale)// if grew by more than 10%
924     {
925         m_currScale = scale;
926         m_currArea = scale * scale;
927         if (m_tiledCanvas)
928             m_tiledCanvas->scale(scale);
929         m_currTrans = trans;
930         m_outputSoFar = 0;
931         m_stats.fullOutput = true;
932     }
933 }
934 
935 
936 void
forEachShape(bool final,ShapeFunction op)937 RendererImpl::forEachShape(bool final, ShapeFunction op)
938 {
939     if (!final || m_finishedFiles.empty()) {
940         FinishedContainer::iterator start = mFinishedShapes.begin();
941         FinishedContainer::iterator last  = mFinishedShapes.end();
942         if (!final)
943             start += m_outputSoFar;
944         for_each(start, last, op);
945         m_outputSoFar = static_cast<int>(mFinishedShapes.size());
946     } else {
947         std::deque<TempFile>::iterator begin, last, end;
948 
949         while (m_finishedFiles.size() > MaxMergeFiles) {
950             TempFile t(system(), AbstractSystem::MergeTemp, ++mFinishedFileCount);
951 
952             {
953                 OutputMerge merger;
954 
955                 begin = m_finishedFiles.begin();
956                 last = begin + (MaxMergeFiles - 1);
957                 end = last + 1;
958 
959                 for (auto it = begin; it != end; ++it)
960                     merger.addTempFile(*it);
961 
962                 auto f = t.forWrite();
963                 if (!f) {
964                     system()->message("Cannot open temporary file for shapes");
965                     requestStop = true;
966                     return;
967                 }
968                 system()->message("Merging temp files %d through %d",
969                                   begin->number(), last->number());
970 
971                 merger.merge([&](const FinishedShape& s) {
972                     *f << s;
973                 });
974             }   // end scope for merger and f
975 
976             for (unsigned i = 0; i < MaxMergeFiles; ++i)
977                 m_finishedFiles.pop_front();
978             m_finishedFiles.push_back(std::move(t));
979         }
980 
981         OutputMerge merger;
982 
983         for (auto&& file: m_finishedFiles)
984             merger.addTempFile(file);
985 
986         merger.addShapes(mFinishedShapes.begin(), mFinishedShapes.end());
987         merger.merge(op);
988     }
989 }
990 
991 void
drawShape(const FinishedShape & s)992 RendererImpl::drawShape(const FinishedShape& s)
993 {
994     if (requestStop) throw Stopped();
995     if (!mFinal  &&  requestFinishUp) throw Stopped();
996 
997     if (requestUpdate)
998         outputStats();
999 
1000     if (!s.mWorldState.m_time.overlaps(mFrameTimeBounds))
1001         return;
1002 
1003     m_stats.outputDone += 1;
1004 
1005     agg::trans_affine tr = s.mWorldState.m_transform;
1006     tr *= m_currTrans;
1007     double a = s.mWorldState.m_Z.sz * m_currArea; //fabs(tr.determinant());
1008     if (s.mShapeType != primShape::fillType && (!isfinite(a) || a < m_minArea))
1009         return;
1010 
1011     if (m_tiledCanvas && s.mShapeType != primShape::fillType) {
1012         Bounds b = s.mBounds;
1013         m_currTrans.transform(&b.mMin_X, &b.mMin_Y);
1014         m_currTrans.transform(&b.mMax_X, &b.mMax_Y);
1015         m_tiledCanvas->tileTransform(b);
1016     }
1017 
1018     if (m_cfdg->getShapeType(s.mShapeType) == CFDGImpl::pathType) {
1019         //mRenderer.m_canvas->path(s.mColor, tr, *s.mAttributes);
1020         const ASTrule* rule = m_cfdg->findRule(s.mShapeType, 0.0);
1021         rule->traversePath(s, this);
1022     } else {
1023         RGBA8 color = m_cfdg->getColor(s.mWorldState.m_Color);
1024         agg::comp_op_e blend = (s.mWorldState.m_BlendMode & (1 << 20)) ?
1025             static_cast<agg::comp_op_e>((s.mWorldState.m_BlendMode >> 21) & 31) : agg::comp_op_e::comp_op_src_over;
1026 
1027         if (primShape::isPrimShape(s.mShapeType)) {
1028             m_canvas->primitive(s.mShapeType, color, tr, blend);
1029         } else {
1030             system()->error();
1031             system()->message("Non drawable shape with no rules: %s",
1032                               m_cfdg->decodeShapeName(s.mShapeType).c_str());
1033             requestStop = true;
1034             throw Stopped();
1035         }
1036     }
1037 }
1038 
1039 
output(bool final)1040 void RendererImpl::output(bool final)
1041 {
1042     if (!m_canvas)
1043         return;
1044 
1045     if (!final &&  !m_finishedFiles.empty())
1046         return; // don't do updates once we have temp files
1047 
1048     m_stats.inOutput = true;
1049     m_stats.fullOutput = final;
1050     m_stats.finalOutput = final;
1051     m_stats.outputCount = m_stats.shapeCount;
1052     mFinal = final;
1053 
1054     int curr_width = m_width;
1055     int curr_height = m_height;
1056     rescaleOutput(curr_width, curr_height, final);
1057 
1058     m_stats.outputDone = m_outputSoFar;
1059 
1060     if (final) {
1061         if (mFinishedShapes.size() > 10000)
1062             system()->message("Sorting shapes...");
1063         std::sort(mFinishedShapes.begin(), mFinishedShapes.end());
1064     }
1065 
1066     m_canvas->start(m_outputSoFar == 0, m_cfdg->getBackgroundColor(),
1067         curr_width, curr_height);
1068 
1069     m_drawingMode = true;
1070     //OutputDraw draw(*this, final);
1071     try {
1072         forEachShape(final, [=](const FinishedShape& s) {
1073             this->drawShape(s);
1074         });
1075     }
1076     catch (Stopped&) { }
1077     catch (std::exception& e) {
1078         system()->catastrophicError(e.what());
1079     }
1080 
1081     m_canvas->end();
1082     m_stats.inOutput = false;
1083     m_stats.outputTime = m_canvas->mTime;
1084 }
1085 
1086 
1087 void
outputStats()1088 RendererImpl::outputStats()
1089 {
1090     system()->stats(m_stats);
1091     requestUpdate = false;
1092 }
1093 
1094 void
processPathCommand(const Shape & s,const AST::CommandInfo * attr)1095 RendererImpl::processPathCommand(const Shape& s, const AST::CommandInfo* attr)
1096 {
1097     if (m_drawingMode) {
1098         if (m_canvas && attr) {
1099             RGBA8 color = m_cfdg->getColor(s.mWorldState.m_Color);
1100             agg::trans_affine tr = s.mWorldState.m_transform;
1101             tr *= m_currTrans;
1102             m_canvas->path(color, tr, *attr);
1103         }
1104     } else {
1105         if (attr) {
1106             mPathBounds.update(s.mWorldState.m_transform, m_pathIter, mScale, *attr);
1107             mCurrentArea = fabs((mPathBounds.mMax_X - mPathBounds.mMin_X) *
1108                                 (mPathBounds.mMax_Y - mPathBounds.mMin_Y));
1109         }
1110     }
1111 }
1112 
1113