Mysteriously misbehaving CFD

[David Spitzley]

Ok, this has me puzzled. I'm fooling around with creating geometric shapes, and I can't understand why the bottom line of this one (composed of circles for clarity) isn't strictly horizontal:

Code: Select all

startshape TRIANGLE

rule TRIANGLE{
	CIRCLE{}
	TRIANGLE {x 1 }
	TRIANGLE2 {x 1 y 1 }
}

rule TRIANGLE2{
	SQUARE {}
	TRIANGLE {x 1 }
	TRIANGLE2 {x 1 y 1 }
}

Is there a rounding error of some sort?

[chris]

Your grammar branches quickly AND the sizes never get smaller. This creates a special situation because it loops infinitely and never stops. Actually, it has no reason to ever stop rendering. (I haven't played with the new releases enough yet to see how they handle this, but my guess is they just stop at some point.)

I think you can generate a triangle with a recursive generation where the shapes inside get smaller. Generally growing them up by distance rather than scale is slower.

For example, you could grow a spiral by starting with a square and growing progressively larger, OR by growing progressively smaller. (Once again, this is crucial to the idea of context free). In your case you have something that branches infinitely while never rescaling. The software has to make guesses about how to bound that. In theory it stops when reaching a bounding box that makes all previously drawn shapes too small, but with yours there are so many shapes to deal with it might stop early.

I'll look at this some more.

cc

[mtnviewmark]

It is strictly horizontal... you just haven't waited long enough! Alas, long enough is actually forever.

Let's look at what was probably your original code:

Code: Select all

startshape TRIANGLE 

rule TRIANGLE{ 
   CIRCLE{} 
   TRIANGLE {x 1  }
   TRIANGLE {x 1 y 1 } 
} 

The problem is that at each step of the expansion, you create two new expansions to do. At each step of the way, only one expansion takes place (we are running on finite computers, after all), so some of the expansions are left to do later. If you stop at some point, you are only going to see some of the expansions.

Now, which expansion it is going to do on each step isn't under your control. So what is happenning is that when you stop the render, all the expansions for the bottom row are still waiting to be done and have been overshadowed by the exponential many expansions in the top part of the triangle - those are being done first.

Normally, the order doesn't matter a wit (a direct consequence of it being context free in the mathematical sense). But that is because eventually all expansions are done (or dropped because they are too small to be seen).

Incidentally, if you modify your version to be just linear, the bottom edge gets a reasonable chance of being expanded before stop, and the raggedness displays along the right edge:

Code: Select all

startshape TRIANGLE 

rule TRIANGLE{ 
   CIRCLE{} 
   LINE {x 1 } 
   TRIANGLE {x 1 y 1  }
} 

rule LINE {
  CIRCLE{ }
  LINE {x 1 }
}

[David Spitzley]

I think you can generate a triangle with a recursive generation where the shapes inside get smaller. Generally growing them up by distance rather than scale is slower.

Yeah, I've tried that, but I've run into other problems regarding fuzzy boundaries prior to objects reaching a sufficiently small size; I still plan to try some other strategies. Nevertheless, given that the non-linear behavior crops up within a few iterations (only about six or seven columns over), it seems likely something is off. If it's a necessary consequence of keeping the system from blowing up, that's fine, but I think this may be a limiting case of something which affects a large category of less extreme designs. Even so, it's pretty darn cool

[David Spitzley]

Normally, the order doesn't matter a wit (a direct consequence of it being context free in the mathematical sense). But that is because eventually all expansions are done (or dropped because they are too small to be seen).

Incidentally, if you modify your version to be just linear, the bottom edge gets a reasonable chance of being expanded before stop, and the raggedness displays along the right edge.

Aha, that makes sense; I hadn't considered that the branches were getting processed differently, which is kind of obvious now that you point it out. I will note, however, that order of commands can matter aesthetically even though it doesn't structurally: if a series of commands is performed after a SQUARE{} call, for example, they get dropped on top of it, whereas calling the SQUARE{} afterwards places the square "in front", a difference which becomes obvious when the square is a different brightness than the other commands.

[mtnviewmark]

(I haven't played with the new releases enough yet to see how they handle this, but my guess is they just stop at some point.)
cc

They will happily render 'til the cows come home! Actually, in either the original construction, or my linear version, the Context Free will stop rendering when the unit size becomes less than 0.3 of a pixel. So, if you are rendering into a 500x500 pixel image, you have to wait until the triangle has more than 1666 columns. With my linear version you can actually wait it out and see the result. With the original exponential version, I don't thing there is enough time in the universe to wait for the 2^1666 expansions!

[chris]

here's a way for making a pretty quickly converging equilateral triangle. It generates lots of shapes, though.

startshape TRIANGLE

rule TRIANGLE {
TRIANGLE_PART {}
TRIANGLE_PART {r 120}
TRIANGLE_PART {r 240}
}

rule TRIANGLE_PART{
SQUARE {}
TRIANGLE {s 0.6 y 0.75}
}

[David Spitzley]

Well, aside from the fact that it's non-terminating, like the one I posted, it's definitely an improvement. Still, I think if there's going to be a serious attempt at making triangles, it will need somebody to dive into the source code and create RTRIANGLE and EQTRIANGLE objects. I want to go look, but I don't have any way of opening a .tgz file, and don't want to screw up Windows XP's handling of zip files by installing PowerArchiver.

[MtnViewJohn]

I will put up a Zipped version of the sources. WinZip 9.0 handles .tgz files (which is really shorthand for .tar.gz). If you can't get WinZip 9.0 then try renaming it to foo.tar.gz and see if you can open that.