Recursion depth

If you're having trouble using Context Free or don't understand the language, ask for help here.

Moderators: MtnViewJohn, chris, mtnviewmark

Post Reply
neuwirthe
Posts: 3
Joined: Wed Jul 28, 2010 6:32 am

Recursion depth

Post by neuwirthe »

How is the recursion depth of a recursive rule determined?

User avatar
MtnViewJohn
Site Admin
Posts: 882
Joined: Fri May 06, 2005 2:26 pm
Location: Mountain View, California
Contact:

Re: Recursion depth

Post by MtnViewJohn »

There is no deterministic way to control recursion depth. There are two non-deterministic ways to limit recursion: having a bail-out rule, and the too-small-to-draw rule.

Code: Select all

rule tendril 0.99 {
  CIRCLE {}
  tendril {y 0.5 s 0.99 r 1}
}

rule tendril 0.01 {}  //bail-out rule
At each recursive step of the tendril rule there is a 1% chance that the empty rule will be picked and recursion will terminate. If you remove the empty rule then the tendril rule will recurse until the circle is too small to see. By default this happens when the circle is 0.3 pixels wide. You can change the size at which the too-small-to-draw rule activates by using Render-With-Size/Render-To-Size in the render menu and changing the minimum feature size option.

neuwirthe
Posts: 3
Joined: Wed Jul 28, 2010 6:32 am

Re: Recursion depth

Post by neuwirthe »

Please look at the following code.
How does ContextFree decide it does not need to do a next iteration of ARCL


Code:

Code: Select all

startshape DOIT

rule DOIT {
     ARCL {}
}

rule ARCL {
	MARK { }
	ARCL { size 0.97 y 0.55 r 1.5 }
}

rule MARK {
  	SQUARE { }
}

neuwirthe
Posts: 3
Joined: Wed Jul 28, 2010 6:32 am

Re: Recursion depth

Post by neuwirthe »

If you remove the empty rule then the tendril rule will recurse until the circle is too small to see. By default this happens when the circle is 0.3 pixels wide. You can change the size at which the too-small-to-draw rule activates by using Render-With-Size/Render-To-Size in the render menu and changing the minimum feature size option.
Thats is the answer I was looking for. So my other post is obsolete.

User avatar
kipling
Posts: 91
Joined: Wed Jun 18, 2008 2:36 am

Re: Recursion depth

Post by kipling »

There are a few designs in the gallery that deliberately subvert the size-threshold bail-out by hiding a big object in a small object. My "thataway" was one, and there were some earlier ones (can't find them just now) where the expansion of a space-filling curve was halted at a particular point using this trick. This is very non-CF though.

User avatar
pakin
Posts: 43
Joined: Sat Apr 21, 2007 8:59 pm
Location: United States
Contact:

Re: Recursion depth

Post by pakin »

kipling wrote:There are a few designs in the gallery that deliberately subvert the size-threshold bail-out by hiding a big object in a small object. My "thataway" was one, and there were some earlier ones (can't find them just now) where the expansion of a space-filling curve was halted at a particular point using this trick. This is very non-CF though.
I'm trying to figure out your thataway, but I still don't get it. Is the idea that the {s 0.01} stops the recursion but then the {s 98} causes one last thing to be drawn? Why doesn't the recursion continue given that something was drawn that was not therefore "too small"?

User avatar
kipling
Posts: 91
Joined: Wed Jun 18, 2008 2:36 am

Re: Recursion depth

Post by kipling »

Each arrow in thataway is a stack of arrows with black "covers" alternating, terminating with one arrow left visible. Each is scaled 0.98 from the previous one, as you've probably figured.

The trick was to get these stacks to stop at the same relative size and orientation, just leaving the final object uncovered. CF will automatically stop expansion at a consistent size (scale factor) but it is usually far too small to be useful. To trick it into stopping sooner, you scale down to an intermediate object then back up to the original object. Effectively the small intermediate object is lying about the size of the other objects it generates, subverting the threshold.

So as implemented in thataway, two things can happen: if the current scale factor is 100x bigger than the threshold, CF will scale down 0.01, not bail out, then scale up 98 and continue. If the scale factor is less than 100x bigger than the threshold, it will bail out with the intermediate object.

Once I had this sort of control working, I had a bit of messing around to make sure these final objects were all at the same orientation and z-depth. I tried to use this idea to make a tree with fruit that all "hung" in the same direction but it didn't look any good.

User avatar
pakin
Posts: 43
Joined: Sat Apr 21, 2007 8:59 pm
Location: United States
Contact:

Re: Recursion depth

Post by pakin »

Thanks for the explanation. I would have expected Context Free's termination condition to be "the last primitive drawn didn't change a single pixel" instead of a particular scale factor. It's cool that you were able to exploit the current implementation like you did.

User avatar
MtnViewJohn
Site Admin
Posts: 882
Joined: Fri May 06, 2005 2:26 pm
Location: Mountain View, California
Contact:

Re: Recursion depth

Post by MtnViewJohn »

pakin wrote:Thanks for the explanation. I would have expected Context Free's termination condition to be "the last primitive drawn didn't change a single pixel" instead of a particular scale factor. It's cool that you were able to exploit the current implementation like you did.
There is a pixel check, but it is done in two steps. During rule expansion, each non-terminal shape in the rule is checked using a "this shape is not expected to change a pixel" rule. Non-terminal shapes that pass this check are stored away and get expanded later on. Non-terminal shapes that fail the check are dropped.

Then after the rules have been executed and a "sentence" of primitive shapes has been produced there is a second check that discards primitives that actually do not change a pixel.

The first check is subject to gaming like you see in thataway, which is essentially a context-sensitive design. We could make the first check smarter to prevent context-sensitive designs. But it is more fun to allow clever people to tweak the rules.

User avatar
minimaleye
Posts: 14
Joined: Sat Jan 22, 2011 1:03 am

Re: Recursion depth

Post by minimaleye »

hmm I often use other way to control it... here is how:

Code: Select all

[i]//___instate this:[/i]
rule tendril 0.99 {
  CIRCLE {}
  tendril {y 0.5 s 0.99 r 1}
}

rule tendril 0.01 {}  //bail-out rule

//___I do type this:

rule tendril {
   25 * {y 0.5 s 0.99 r 1} 
   CIRCLE {}
 }
by changing 25 you can control how far you wanna go... but its totally static that way
there is no end...
...therefore there isn't now and here

Post Reply