On Being Context Free (long)

Let the developers know what you think of the software and what can be done to either improve the CFDG language or the Context Free program.

Moderators: MtnViewJohn, chris, mtnviewmark

Post Reply
User avatar
mtnviewmark
Site Admin
Posts: 81
Joined: Wed May 04, 2005 12:46 pm
Location: Mountain View, CA
Contact:

On Being Context Free (long)

Post by mtnviewmark »

A key aspect of context free grammars is that each expansion of symbol is done independently of every other. This implies two important properties for Context Free:

1) The order the shapes are drawn is undefined.

Alas, we already violate this principle: The brightness is defined in such a way that the order of drawing matters, since the shade of the shape is opaque. This is problem we should consider fixing ASAP. When we expand into the realm of color, we will face this again.

2) The choices made in one expansion cannot affect any other expansion.

Another way of saying this that no information can "leak out" from one expansion and be used in another. This rules out possible extensions like global variables, maximum rule use counts and rule return values.

Keeping to these restrictions is more than just "nerd purity". The ability for the program to process the grammar files efficiently is predicated on them.

Already, the order of rule expansion and shape drawing will vary depending on the size of the image: When we reach a million shapes or two million expansions, the program starts to write things out into temporary files, and this alters the order of operations.

Another example is that the pruning of sub-pixel rules can be done because we know that their expansion can't affect other expansions.

Lastly, John already has plans in the works to take advantage of systems with multiple CPUs and/or hyper-threading and compute parts of the image in parallel.

On the other hand, things like parameterized rules (rule arguments) don't actually violate the context free nature. They simply form a short hand for a large family of rules. Formally, this is actually what is happening with the x, y, size, rotation and brightness values at present.

So I could imagine extending CFDG to allow things like:

Code: Select all

rule curve($shape) {
    $shape { }
    curve { rotation 1 y 0.5 size 0.975 }
}
Most other things mentioned in this forum: Positioning things absolutely, declaring a specific color, and arbitrary shapes and/or polygons and/or triangles do not violate the context free nature either. Some do: adding color when drawn opaquely, or drawing with imported images, (in both cases because they will put dependencies on drawing order).

I feel like once we've seen a hundred good designs with the current CFDG, then we'll know what we'll need to add. And when we do, we should try to stick to what makes CFDG work so well: a minimal set of features that results in an astonishingly wide variety of very wonderful images.

If I really must admit to what I'm currently thinking about, it is this set of additions, in rough order:
  • fix the brightness problem
  • add something like a simple TRIANGLE(a) primitive which draws a triangle with angles a, 90-a and 90, the hypotenuse where the diameter of CIRCLE would be drawn. All the other polygons and triangles can be constructed with finite rules from this. An equilateral triangle is is composed of TRIANGLE(60) and TRIANGLE(-60).
  • dist <d> and theta<t> adjustments as shorthand for x <<d>*sin(<t>)> and y <<d>cos(<t>)>
  • some simple parameterized rule form
I'm the "m" in "mtree.cfdg"

User avatar
chris
Site Admin
Posts: 72
Joined: Wed May 04, 2005 10:57 am
Location: New York, NY
Contact:

Post by chris »

One possible solution to the brightness problem is using some overlay operator that is commutative. For example, it would yield nice results if the overlay of one color on another color simply averaged them as opposed to covering the initial shape.

There are other possibilities of course, too. That one is particularly easy to predict and understand.

CC
Current Project: I'm creative director of OKCUPID at http://www.okcupid.com

User avatar
mtnviewmark
Site Admin
Posts: 81
Joined: Wed May 04, 2005 12:46 pm
Location: Mountain View, CA
Contact:

Post by mtnviewmark »

Actually, the operator has to be associative as well. And that seems to be the harder criterion. I'm still out researching this... Find a graphic operator that meets the needs and is doable in all three graphic rendering engines we are currently using is a challenge!
I'm the "m" in "mtree.cfdg"

User avatar
chris
Site Admin
Posts: 72
Joined: Wed May 04, 2005 10:57 am
Location: New York, NY
Contact:

Post by chris »

I think, given these abstract constraints, "average" still makes the most sense. As you say, implementation is the big problem, though.

For some time, I've been tempted to write a platform-independent draw step that produces a m*n array of grayscale values and updates it with each iteration. This would solve three problems at once: (1) we could handle overlays however we want, (2) it would remove a compile step in UNIX, and (3) we could do anti-aliasing and floating point vertices so images don't need to be rescaled and shrunk to look good (also removing the step of switching from polygons to pixels). This memory could just be copied to the windows "canvas" periodically to keep an ongoing rendering.
Current Project: I'm creative director of OKCUPID at http://www.okcupid.com

User avatar
mtnviewmark
Site Admin
Posts: 81
Joined: Wed May 04, 2005 12:46 pm
Location: Mountain View, CA
Contact:

Post by mtnviewmark »

No need to write such a thing - it already exists. We've been looking into AntiGrain Graphics - which is a portable very high-quality renderer framework. It is very modular and templatized so that we'd only need to include the parts that we need.

This is definitely in the 2.0 realm, though....
I'm the "m" in "mtree.cfdg"

Post Reply