// Fractal Subdivision
// David Bollinger, May 2006
// http://www.davebollinger.com
// for Processing 0115 Beta
//

Subdivider subdiv = new Subdivider(4,4);
int seed = 0;
int nextdelay = 0;

// start the demo with a few seeds considered more interesting
// (then just do sequential seeds once this list is exhausted)
int[] demoseeds = { 17,28, 8,24,32,45,51,62,67,71,78,88,97,104,108,117,
  122,126,135,141,147,154,158,163,170,174,175,176,180,181,184,193,199 };
int demoindex = 0;

boolean bOverlayPattern = false;

void setup() {
  size(512,512);
  framerate(30);
  colorMode(HSB);
  next();
}

void mousePressed() {
  next();
}

void keyPressed() {
  if (key=='p')
    bOverlayPattern = !bOverlayPattern;
}

void next() {
  // use a predefined seed?
  if (demoindex<demoseeds.length) {
    seed = demoseeds[demoindex++];
  }
  // make the subdivision pattern
  do {
    subdiv.make(seed++);
  } while (!subdiv.valid);
  // prime the to-do-list
  subdiv.todoli.add(new Subdiv(0,0,width,height,false));  
  // clear screen
  background(subdiv.hue,40,240);
  // reset delay
  nextdelay = 0;
}

void draw() {
  subdiv.driver();
  if (bOverlayPattern)
    subdiv.overlay();
  // if nothing left to subdivide then do next after time out
  if (subdiv.todoli.size()==0)
    if (++nextdelay > 100)
      next();
}

class Subdivider {
  // cols,rows - the size of the pattern grid.
  // this app makes patterns confined to a 4x4 grid.
  // these are arbitrary values - it is perfectly valid to
  // subdivide other sizes (square aspect is preferred, 2x2, 
  // 3x3, 5x5, 6x6, et cetera, but not required)  if changing
  // the grid size you should ideally set the image resolution
  // such that it is an even power of the grid size.  for
  // example a 5x5 grid would work well with an image size of
  // 5^4x5^4 (625x625)
  int cols = 4;
  int rows = 4;  
  // TWEAK_* - how to invert the grid pattern.
  // this app supports inversion (horizontal, vertical or both)
  // but not rotation.  it toggles back and forth between normal
  // and inverted version on alternate depths.  so for further
  // exploration, add rotations (90-degrees CW and CCW) and allow
  // deeper specification of tweaks.  for example: normal, then
  // flip horizontal, then rotate clockwise, then flip vertical,
  // repeat.  very complex patterns resembling l-systems could be
  //  formed in that manner.
  static final int TWEAK_NONE = 0;
  static final int TWEAK_MIRROR = 1;
  static final int TWEAK_FLIP = 2;
  static final int TWEAK_MIRRORFLIP = 3;
  // WORK_* - what to do when processing this grid cell
  // 0 - do nothing, this cell is part of a larger area already processed
  // 1 - this area is done subdividing, go ahead and draw it
  // 2 - subdivide this area
  static final int WORK_NONE = 0;
  static final int WORK_DONE = 1;
  static final int WORK_DIVIDE = 2;
  // cells stores a grid pattern of work to be done
  // each cell is byte-encoded as follows:
  // (cell>>16)&0xff - the work to be done (see above)
  // (cell>>8)&0xff  - the height of the area specified
  // (cell)&0xff     - the width of the area specified
  int[][] cells;
  // the recursive subdivision routine is not in fact called recursively.
  // instead a "to do list" is built up and processed on each iteration.
  // this is done solely for the purpose of animating the process in
  // discrete steps (otherwise the entire recursion occurs with one call
  // and there's nothing fun left to animate!)
  Vector todoli = new Vector();
  // the random number seed used to generate this pattern
  int seed;
  // the type of tweak specified for this pattern (see TWEAK_* above)
  int tweaktype;
  // the toggle between normal and tweaked states
  boolean tweakflag;
  // a flag to indicate if a valid pattern was generated with given seed
  boolean valid;
  // the hue of the color used to fill areas
  int hue;
  // constructor
  Subdivider(int c, int r) {
    cols = c;
    rows = r;
    cells = new int[rows][cols];
    seed = 0;
    tweaktype = 0;
    tweakflag = false;
    valid = false;
    hue = 0;
  }
  
  // clear grid pattern
  void wipe() {
    for (int r=0; r<rows; r++)
      for (int c=0; c<cols; c++)
        cells[r][c] = 0;
    todoli.removeAllElements();
  }
  
  // determines if cells already contain defined area(s)
  boolean isOccupied(int col, int row, int wid, int hei) {
    for (int r=row; r<row+hei; r++) {
      for (int c=col; c<col+wid; c++) {
        if (cells[r][c] != 0) {
          return true;
        }
      }
    }
    return false;
  }
  
  // marks cells as containing an area
  void doOccupy(int col, int row, int wid, int hei, int val) {
    for (int r=row; r<row+hei; r++) {
      for (int c=col; c<col+wid; c++) {
        cells[r][c] = val;
      }
    }
  }
  
  // generate a new grid pattern with specified seed
  void make(int s) {
    int count1=0, count2=0;
    seed = s;
    randomSeed(seed);
    wipe();
    for (int r=0; r<rows; r++) {
      for (int c=0; c<cols; c++) {
        int cell = cells[r][c];
        if (cell != 0) continue;
        // determine dimensions of area
        // have to verify that selected dimensions do not
        // cross into already occupied areas
        // (in particular, early "vertical" areas tend to
        //  get in the way of later "horizontal" areas)
        int wid,hei;
        do {
          wid = int(random(cols-1-c))+1;
          hei = int(random(rows-1-r))+1;
        } while(isOccupied(c,r,wid,hei));
        // flag all cells as occupied by width x height area
        doOccupy(c,r,wid,hei, ((hei<<8)|wid) );
        // flag first cell with type of work to perform
        int work = int(random(2))+1;
        cells[r][c] |= (work<<16);
        // keep track of work done to later determine validity of pattern
        if (work==1) count1++;
        if (work==2) count2++;
      } // for c
    } // for r
    tweaktype = int(random(4));
    // A "VALID" SUBDIVISION MUST HAVE AT LEAST ONE
    // EACH OF A "DONE" AREA AND A "SUBDIVIDE" AREA
    // (if it's all "done" areas then not fractal at all, boring)
    // (if it's all "subdivide" areas then infinitely fractal with no usable "done" area, boring)
    valid = ((count1>0) && (count2>0));
    // finally, pick a random hue
    hue = int(random(256));
  }
  
  // draw an area
  void drawarea(float x1, float y1, float wid, float hei) {
    if ((wid < 1) || (hei < 1)) return;
    // fill
    float area = wid * hei;
    float sat = 40 + log(area) * 8;
    float bri = 255 - log(area) * 16;
    fill(color(hue,sat,bri));
    stroke(hue,sat/2,bri/2);     
    rect(x1,y1,wid,hei);
  }
  
  // the driver for the recursive routine that processes the to-do-list
  void driver() {
    if (todoli.size()==0) return;
    // get all current items in todoli
    Vector donow = (Vector)todoli.clone();
    // we'd like to process the entire list each frame, but some of the
    // patterns "explode" and make too much work to keep up the frame rate,
    // so the amount of work-per-frame is capped
    int perframelimit = 100;
    // process the items
    for (int i=0; i<donow.size(); i++) {
      Subdiv s = (Subdiv)donow.elementAt(i);
      todoli.remove(s);
      recurse(s.x1, s.y1, s.xscaler, s.yscaler, s.tweaker);
      if (--perframelimit <= 0) return;
    }
  }
  
  // here's where all the fun occurs.  it reads the pattern grid
  // to determine what to do at each location, then either draws an
  // area that is finished, or calls this function again recursively
  // to further subdivide the area.  recursion continues until area
  // specified is smaller than evenly integer divisible.
  void recurse(float x1, float y1, float xscaler, float yscaler, boolean tweaker) {
    // END RECURSION?
    if ((xscaler < 2) || (yscaler < 2)) return;
    // PROCESS LOOPS
    for (int r=0; r<rows; r++) {
      for (int c=0; c<cols; c++) {
        int cell = cells[r][c];
        // DECODE THE CELL CONTENTS
        int work = (cell>>16) & 0xff;
        if (work == WORK_NONE) continue;
        float wid = (cell) & 0xff;
        float hei = (cell>>8) & 0xff;
        // COMPUTE CELL COORDINATES
        float cellx1 = x1 + c * xscaler/cols;
        float celly1 = y1 + r * yscaler/rows;
        // TWEAK THOSE COORDINATES?
        if (tweaker) {
          if ((tweaktype&TWEAK_MIRROR)!=0)
          cellx1 = x1 + (cols-c-wid) * xscaler/cols;
          if ((tweaktype&TWEAK_FLIP)!=0)
            celly1 = y1 + (rows-r-hei) * yscaler/rows;
        }
        // DRAW "DONE" AREA OR SUBDIVIDE IT FURTHER
        if (work == WORK_DONE) {
          drawarea(cellx1, celly1, wid*xscaler/cols, hei*yscaler/rows);
        } else {
          // true recursion would just call this (which does work, by the way)...
          //recurse(cellx1, celly1, wid*xscaler/cols, hei*yscaler/rows, !tweaker);
          // and the whole screen would be created with one call
          // instead, we build up the todoli for later processing...
          todoli.add(new Subdiv(cellx1, celly1, wid*xscaler/cols, hei*yscaler/rows, !tweaker));
        }
      } // for c
    } // for r
  }
  
  // overlay the pattern grid itself onto display
  void overlay() {
    int margin=10, scaler=8, ascaler=2;
    int cx = margin + (cols*scaler) / 2;
    int cy = margin + (rows*scaler) / 2;
    color donecolor = #FFEDC1;
    color divicolor = #C1D0FF;
    stroke(#666666);
    for (int r=0; r<rows; r++) {
      int y1 = margin+r*scaler;
      for (int c=0; c<cols; c++) {
        int x1 = margin+c*scaler;
        int cell = cells[r][c];
        int work = (cell>>16) & 0xff;
        if (work==WORK_NONE) continue;
        int hei = (cell>>8) & 0xff;
        int wid = (cell) & 0xff;
        if (work==WORK_DONE) {
          fill(donecolor);
        } else { // WORK_DIVIDE
          fill(divicolor);
        }
        rect(x1,y1,wid*scaler,hei*scaler);
      }
    }
    // DRAW TWEAK MODE
    int[] arrowdxs = { -2,2,2,4,2,2,-2,-2,-4,-2 };
    int[] arrowdys = { -1,-1,-2,0,2,1,1,2,0,-2 };
    noFill();
    stroke(#000000);
    if ((tweaktype&TWEAK_MIRROR)!=0) {
      beginShape(POLYGON);
      for (int i=0; i<10; i++)
        vertex(cx+arrowdxs[i]*ascaler,cy+arrowdys[i]*ascaler);
      endShape();
    }
    if ((tweaktype&TWEAK_FLIP)!=0) {
      beginShape(POLYGON);
      for (int i=0; i<10; i++)
        vertex(cx+arrowdys[i]*ascaler,cy+arrowdxs[i]*ascaler);
      endShape();
    }
  }
  
}

// this class stores one to-do-list item
class Subdiv {
  float x1,y1,xscaler,yscaler;
  boolean tweaker;
  Subdiv (float x, float y, float xs, float ys, boolean tw) {
    x1=x; y1=y; xscaler=xs; yscaler=ys; tweaker=tw;
  }
}