Wednesday, April 20, 2011

[oqnifleh] Point growth tree in multiple dimensions

My point growth tree enforces a constraint that it must grow as a tree.  This is kind of a complicated constraint in two dimensions:

A new point must attach orthogonally to at least one old point.
If a new point attaches orthogonally to more than one point we Reject and restart the simulation of that point (this may not have been the correct decision; a point cannot maneuver past tight places).  If a point attaches diagonally to another old point, we also Reject, unless the new point, diagonal old point, and orthogonally attaching old point form an L.

if (xx+yy>escape_distance) {
              break;
            }
            bool xa=image.quick_pixel(x-1,y);
            bool ya=image.quick_pixel(x,y-1);
            bool xz=image.quick_pixel(x+1,y);
            bool yz=image.quick_pixel(x,y+1);
            if(xa || ya || xz || yz) {
              if(image.bad_connect(x,y,xa,ya,xz,yz)) break;
              // forcing tree structure
              success=true;
              image.set_pixel(x,y);

* * *

bool bad_connect(Uint x, Uint y, bool xa, bool ya, bool xz, bool yz){
    if (1 != xa + ya + xz + yz) return true;
    if(xa){
      if(quick_pixel(x+1,y+1))return true;
      if(quick_pixel(x+1,y-1))return true;
    } else if (xz){
      if(quick_pixel(x-1,y+1))return true;
      if(quick_pixel(x-1,y-1))return true;
    } else if (ya){
      if(quick_pixel(x+1,y+1))return true;
      if(quick_pixel(x-1,y+1))return true;
    } else {
      assert(yz);
      if(quick_pixel(x+1,y-1))return true;
      if(quick_pixel(x-1,y-1))return true;
    }
    return false;
  }

In other words, we require touching orthogonally, but we forbid touching even diagonally if it creates a loop.

Extend this decision procedure to three (or more) dimensions.  Build the three dimensional snowflake in Minecraft.

No comments :