Recently, I stumbled upon a "bubble-breaker" Flash toy (see the original here) and was inspired to use the same concept to show off an old project of mine. The basic gist is that the pixel data of the image is stored in a quadtree, and averaged together to create the larger bubbles.

How It Works:

Quadtrees are useful for compressing image data and performing collision detection in 2D space. Each depth level of the quadtree represents the number of subdivisions from zero (no subdivisions: the highest level, or root node) on down to the pixel level. The number of depth levels ultimately depends on the size of the image. Note: in order for this technique to work, the source image must satisfy two conditions: the image must be square, AND the image dimension must be a power of two. This ensures that the image can be subdivided evenly all the way down to the pixel level. The following diagram illustrates the quadtree hierarchy. The empty boxes represent the parent nodes, or nodes that are subdivided. The filled-in boxes represent the leaf (or child) nodes, nodes that are not subdivided and store color information. The top level is the image with no subdivisions (the root node). The next level down is the image subdivided once--in other words, split into four quadrants. The bottom level illustrates two levels of subdivisions, in which each of the former quadrants has in turn been split into four smaller quadrants. This process continues until the pixel level is reached. The maximum depth can be calculated by width (or height, since both must be the same) divided by log 2. Because the color of each node is determined by the average of its children, a recursive loop is used to iterate down to the pixel level and then work its way back up, calculating the averages as it goes.

The Results:

The source image has dimensions 512 pixels X 512 pixels. This indicates a maximum depth of 512 / (log 2), or 9. A depth of nine produces an image analagous to the original source image. Shown below is output created by my original C++ program at varying depth levels. For depth levels less than the original image quality (9), the pixels that comprise each leaf node are averaged together. For the Flash demo, the big starting bubble is the color of the root node, or the average of the colors of its four children. On rollover, the root node separates into its children nodes (at a depth of one). Since each parent node is the average of the colors of its children, the root node is essentially the average color of all the pixels in the image. In my opinion, the dirty gray of the root node really doesn't do the image justice.

Original Image	Level 7	Level 6	Level 5
Level 4	Level 3	Level 2	Level 1

The Code:

The following is a snippet of code from the original C++ program, before I ported it to ActionScript. Shown is the function that recurses the quadtree and stores the data in a vector array so that it can be written to an image format. To download the entire source code, click here.

/* Recurse the quadtree and store the image data in the vector QTarray. */
void buildArray(Node* current_node, unsigned startSize, unsigned size, unsigned index){
	//if at the pixel level, store the color data
	if (size == 1)
		QTarray[index] = current_node->_data;
	else{
		//otherwise, divide area into fourths (size is the length of one side)
		unsigned n = size / 2;
		//check to make sure that the current node has children before recursing deeper		
		// If the NW node exists, all four child nodes exist
		if(current_node->NW != NULL){
			buildArray(current_node->NW, startSize, n, index);
			buildArray(current_node->NE, startSize, n, index + n);
			buildArray(current_node->SW, startSize, n, index + n * startSize);
			buildArray(current_node->SE, startSize, n, index + n * startSize + n);
		}
		//if the current node does not have children and we are not at the pixel level,
		//all pixels in the current area are the same color
		else{
			for(int i = 0; i < size; ++i){
				for(int j = 0; j < size; ++j){
					QTarray[index + j + i * startSize] = current_node->_data;
				}
			}
		}
	}
}