Compile CFDG to postscript?

[futrelle]

Am I missing something, or would it be trivial to compile CFDG into postscript? Postscript is a procedural language with recursion and conditionals; in fact it's Turing-complete. So the resulting postscript file would closely resemble the CFDG code.

The issue I can see is that typical postscript renderers are probably not optimized for highly recursive code. But there are tricks for dealing with that problem that work fairly well.

Compiling into postscript would give CDFG typesetting and lots of graphic primitives for free. As well as arbitrary-resolution rendering.

[mtnviewmark]

Not so fast....

It may surprise you to learn that the implementation of CFDG isn't recursive at all! Honest! The recursive grammars are expanded using a purely iterative function. So, recursion in PostScript isn't the issue.

The real issue is that the infinite recursions in a grammar (which would translate into iterations that never end) only end because we are rendering to a pixel map and we decided to give up when things get to less than 0.3 of a pixel. So, even when rendered with PostScript, the result wouldn't be resolution independent.

There are two possible paths here:

One, we expand on the computer, and generate a large set of PostScript primitives that match what you see on the screen. In this mode, we'd have to ask you what size paper and what resolution printer, and then stop when we hit 0.3 pixel in that environment. Clearly, the result, while could be printed on different printers, would only be optimized for one configuration.

On the other hand, we could translate the grammar into a bit of PostScript and tack on a CFDG PostScript library, and perhaps some code so that one could reliably recreate a particular variation. Then the grammar expansion would be run in the printer. In this case, the expansion would proceed to match the resolution of the printer. The down side of this is that expansions of this sort (say 8 x 10 at 600 dpi) could require tremendous memory for processing that most printers don't have. (Have you ever see Context Free use temporary files? We have images that use 30 files, each at a million shapes!)

Even if either of these solutions is acceptable, there are still a big barrier to PostScript being a useful output medium for Context Free: PostScript interpreters aren't optimized for doing sub-pixel shapes - which is what Context Free almost always ends up with. These shapes only look good if properly anti-aliased. However - PostScript in printers generally doesn't anti-alias structured graphics (Honest!). Hence, it actually wouldn't look as good as rendering on the computer (where we use a library that does sub-pixel rendering and anti-aliasing) and shipping the PNG to the printer.

Some people would like to have output to EPSF so that they could then take the images into Illustrator and manipulate the graphics primitives. But I'm not sure Illustrator could handle 200,000 sub-pixel sized circles, or really how effective one could manipulate such a beast.

Now, despite all this "why we can't do it", I actually like the idea of structured graphics output. I just don't know how to do it so the result is useful yet.

[futrelle]

Got it, I think most of your concerns can be addressed but I'm not sure.

1. Iterative vs. recursive implementation. The iterative implementation requires lots of memory to hold the entire expanded tree but the recursive implementation only requires a large stack to hold one path at a time; so I think the appropriate way to compile CFDG to postscript *is* to generate a recursive ps script. The only information you would need to keep on the stack is the current rule and the current coordinate transformation.

2. Recursion depth can be controlled with conditionals that inspect the current coordinate transformation and halt at some given scaling factor. The result will be resolution-independent in terms of the rendering of the shapes, but the depth at which it expands the tree wouldn't depend on the resolution--in high-resolution images, you would be able to see where the expansion stops. No big deal.

I'm not sure how to deal with the correct handling of sub-pixel shapes--that seems like the show-stopper to me. It would be very easy to evaluate various postscript interpreters to see if they generate reasonable-looking output for fractals with tiny shapes in them.

Writing the CFDG to ps interpreter seems like a fun experiment to try. Is there a language spec available for CFDG?

[mtnviewmark]

The recursive solution doesn't eliminate the memory factor entirely:

First, the recursion depth for a path can often be hundreds if not thousands deep. Consider a rule that starts out 10 pixels wide and proceeds by a size factor of 0.997. It will take a depth of 1,132 to hit 0.3 pixels. This is kind of thing is common. You might be able to mitigate this somewhat by handling tail-recursion efficiently, though doing that in the presence of the non-deterministic rule selection (where some branch) would be a good challenge.

Second, CFDG is defined in such a way that you have to generate ALL the final shapes before drawing any of them as you don't know the proper scaling factor until its done. (This is why the program does those nice animations: it is recomputing the scale factor.) This feature is by design: It is really nice that you don't have to tell CFDG what the bounding box is in the design.

As for specifications - the only spec is the code itself. There is a yacc/lex grammar in the source code. See: the directory src-common.

[MtnViewJohn]

I think that sub-pixel rendering is a by-product of rendering to screens, which have big pixels with lots of gray-scale. An implementation that renders to a device with tiny, monochrome pixels would not sub-pixel render. It would stop expanding shapes once the shapes had gotten smaller than can be rendered well in that regime, probably at 4 to 8 pixels. Anti-aliasing and sub-pixel rendering are not needed when rendering directly to a printer frame buffer.

One problem with switching from iterative to recursive shape expansion is that it will change the way things look. Context Free/CFDG are not really context free. The brightness parameter creates a global dependence on the order of shape rendering. We would have to change Context Free so that shape designers could see how their rules render with recursive shape expansion.

[futrelle]

So is it correct that CF does a breadth-first traversal of the CFDG in order to expand it? In that case, the recursive implementation would produce different results than the iterative version if the brightness parameter ever changed and shapes of different brightness drawn by different rules collided. But if the drawing order is depth-first, then it won't matter.

I doubt large stack sizes are a problem for most postscript interpreters.

The easiest and probably least efficient way to solve the scaling problem is to do two passes over the CFDG grammar, with the first pass just used to compute the scaling factor.

[futrelle]

Check this out:
http://www.cs.unh.edu/~charpov/Programming/L-systems/

pretty pictures!

[futrelle]

Here's a hand-translation of a simple CFDG file into postscript. The postscript code uses scaling factor, rather than a pre-set recursion depth, to determine when to stop expanding the rule. This captures I think everything that needs to be done to translate CFDG into postscript except the random selection of alternative rules, which should be pretty straightforward unless I'm forgetting something. Note: *do not* just double-click on the ps file under MacOS, because that will attempt to convert the doc to PDF and it'll fail. Use a real ps interpreter like MacGhostView or gs under most Linuxes.

Here's the CFDG file:

startshape main

rule main {
SQUARE { }
main { r 20 x 1.5 s 0.96 }
main { y -0.95 r -145 s 0.2 }
}

and here's the postscript code:

%!
%%

/unit {50 mul} bind def % arbitrary scaling

/box {
newpath
-0.5 unit -0.5 unit moveto
1 unit 0 rlineto
0 1 unit rlineto
-1 unit 0 rlineto
closepath
} def

3 unit 3 unit translate

/boxes {
dup 0.005 gt { % s
box fill
gsave
1.5 unit 0 translate
0.96 0.96 scale
20 rotate
dup 0.96 mul % s s'
boxes
grestore
% s
gsave
0 -0.95 unit translate
0.2 0.2 scale
-145 rotate
0.2 mul % s''
boxes
grestore
} { pop } ifelse
} def

1.0 boxes

showpage % We're done... eject the page

[mtnviewmark]

Note: *do not* just double-click on the ps file under MacOS, because that will attempt to convert the doc to PDF and it'll fail. Use a real ps interpreter like MacGhostView or gs under most Linuxes.

Clicking under MacOS to convert to PDF is using a real PostScript interpreter, and the reason it fails shows the problem with the approach: It fails because the gsave stack is exceeded. (Check the console log.)

The PostScript Language Reference, 3rd Edition doesn't specify either minimum or maximum gsave stack depths available. But, it does state that PostScript interpreters (meaning by Adobe) have an architectural limit on the gsave nesting level of 31. (Table B.1, p. 739).

Ghostscript has no such limit, which is why it works there. (See Ghostscript Architectural Limits.) However, note that gsave is not a cheap operation. I don't know if you'll find interpreters in printers quite so forgiving.

Be aware that Ghostscript doesn't equal PostScript and one must be careful when producing things that are intended for printers. See Ghostscript and the PostScript language

Did I mention that I worked on the Mac port of Ghostscript many years ago?

Again - don't take this the wrong way - I'd love to see some form of structured output from Context Free - though I still don't understand how it would be used, so I'm not sure what form it would take. But in any event, your experiments with conversion to PostScript will certainly help us all understand how to go about doing it!

[futrelle]

31 gsave levels is a pittance, so the idea of compiling CFDG to more-or-less equivalent, yet portable, ps code looks doomed. I naiively assumed that there were no significant memory limits in typical ps interpreters, and that the ps->pdf in MacOS just had some kind of limit setting that I didn't know how to adjust.

That said, Ghostscript can generate a perfectly usable pdf of my example above, so compiling CFDG to postscript and using Ghostscript to convert it into a pdf will likely work very nicely. I'm hoping that CFDG->ps is good for *something*, just because it sounds like fun to write.

[MtnViewJohn]

I think you can do it. But you would have to maintain an explicit stack in an array. Each array element would contain the current coordinate transform, an index to the shape being expanded, and an index for where you are in the expansion of that shape. Postscript interpreters typically have a virtual memory limit of 240K, which is more than adequate for any CFDG.

[futrelle]

Yeah, that would totally work; I need to familiarize myself with ps's matrix and array operators.

In the meantime, I've got the gsave/grestore version of my compiler almost complete; the two features that are missing are rule weights and intensity.

Can you briefly describe the algorithm for randomly selecting a rule variant based on the weights? (I could read the Context Free code, but I'm lazy)

Here's a pdf of "quadcity"--I had to remove the rule weights before compiling it. Some other examples aren't working yet, like demo1. Not sure what the problem is, but hey, debugging is even more fun than writing code

[mtnviewmark]

Can you briefly describe the algorithm for randomly selecting a rule variant based on the weights?

Precompute rule limits via:

1. Put the alternatives for a rule in some fixed order: R = { r0, r1 ... rn }
2. Compute S = sum(R.weight-as-written, i = 0..n)
   
3. Set T = 0
   
4. For each i in 0..n in turn:
   
5. -- T = T + R.weight-as-written
   
6. -- R.limit = T / S

Note that R[n].limit should be 1.0

When you need to select a rule:

1. Pick a number, N, from [0.0..1.0)
2. For each i in 0..n in turn:
3. -- if R.limit > N, pick R

Note carefully the half open range in the first step, and that the test in step 3 is >, not >=.

This is not exactly how the code does it, and upon reflection, the code gets the test type wrong (it is using >=, which it shouldn't)

[futrelle]

Thanks, I assume that the default rule weight is 1.0?

[futrelle]

I didn't get to rule weights yet but just about everything else seems to be working. I'm noticing slight scaling differences between the pdf and Context Free renderings, possibly because I need to adjust the initial postscript graphics state or fill the paths differently. Or maybe just add a fudge factor. Some example renderings are here.