%--------------------------------------------------------------------------
% EPS109, Fall 2009, UC Berkeley
% Author: Vu Chiem
% Description: Final Project, Sierpinski Carpet Movie
% Reference URL: http://en.wikipedia.org/wiki/Sierpinski_carpet
% File: sierpinski.m
%--------------------------------------------------------------------------


%
% Returns a gray-scale image of the Sierpinski Carpet (in |grid|)
%
% Logically, this function takes in a square with k x k. Then, it makes
% white the middle smaller square (size k/3) and calls itself on smaller
% regions.
%
% i: starting index (inclusive)
% j: ending index (inclusive)
% k: number of pixels in the region (should be multiple of 3)
%
function sierpinski(x1, x2, y1, y2, size)
    global grid
    
    if size == 1
        return
    end
    
    s = round(size / 3);
    
    % Make white the middle square
    for i = x1 + s: x2 - s
        for j = y1 + s: y2 - s
           grid(i, j) = 0; 
        end
    end
    
    % Recurse on the remaining 8 squares
    
    % Top squares
    sierpinski(x1, x1 + s - 1, y1, y1 + s - 1, s);
    sierpinski(x1 + s, x2 - s, y1, y1 + s - 1, s);
    sierpinski(x2 - s + 1, x2, y1, y1 + s - 1, s);
    
    % Middle squares
    sierpinski(x1, x1 + s - 1, y1 + s, y2 - s, s);
    sierpinski(x2 - s + 1, x2, y1 + s, y2 - s, s);
    
    % Bottom squares
    sierpinski(x1, x1 + s - 1, y2 - s + 1, y2, s);
    sierpinski(x1 + s, x2 - s, y2 - s + 1, y2, s);
    sierpinski(x2 - s + 1, x2, y2 - s + 1, y2, s);
end