/************************************************************/
/*												*/
/*		ANG LEE Nov, 2005							*/
/*		Computer Vision Term Project					*/
/*		Implement Dual Photography from SIGGRAPH 2005	*/
/*												*/
/************************************************************/

******* Note to run this excutable you need to have a camera connected to the computer.

//========================================================================================
You can find the high level details of this code following the
link below
http://www.cc.gatech.edu/~coolpix/7495/fin/

The original paper is available at:
http://graphics.stanford.edu/papers/dual_photography/

Overall abstract:

	This algorithm is the Adaptive Multiplexed Illumination method described in sec 3 of 
	the original paper.

	The algorithm aims at saving time by projecting rays which do not affect each other
	in the same round. Since they don't affect, their contribution to the camera image could
	be separated. With the information of this relationship (who contributes what) we can fill
	the entries in the T matrix where T is a big matrix (M*N) describing the mapping of M pixels 
	of the projector and N pixels of the camera image.

	Basically, this algorithm start projecting blocks with big area, if two blocks do not affect, 
	nor will their children, and thus their children could be considered in the same group in 
	the next light iteration.

	
//========================================================================================
In this read me file, I provide the corresponding mapping between
the pseudo code and my implementation. My code also has annotations
which shold be easy to understand.


Main Flow:
Initialization();
Repeat{

	//construct a conflict-free lists of blocks that could be processed in parallel
	ConstructConflictFreeLists();

	//illuminate scenes with patterns constructed from each list and acquire with camera
	AcquireImages();

	//process images, store results, generate new lists of blocks for next iteration
	ProcessResults();

} until lowest level is reached.



Sub-functions:

1. Initialization() {
	for each camera pixel k {
		//Initially assume every camera pixel is affected by block 0; the floodlit image
		Bk = {b0}				// take the example above, say pixel 256 has been affect by lit 2 and 4 in level 2, i.e. 
								//that pixel has value > 0 (or some threshold) in the camera image of lit 2 and 4, then in 
								//level 3 (current level) B256 = {b0, b1, b4, b5, b10, b11, b14, b15}; 
		// this is done by the for loop in Manager::Initialise()
	}
	C = empty;	// initialize set of conflicts to empty
				// C is a List of Pairs of blocks which can not be lit at the same time.
	// this is done by 	CEELength = 0;
}

2. ConstructConflictFreeLists(){

	//from graph structure
	B = Union(Bk)//Nodes B, edge C, 

	/* What I did is:
    2.1.1 links all the Bk to be a very long link list.
    2.1.2 Dynamically declare a array of size equals to the link list and put the nodes into this array.
    2.1.3 Merge sort the array members and combine the repeated terms.
	and these can be found in Manager::ConstructConflictFreeLists() -- B = Union(Bk) */

	(L[0], …, L[N-1]) = GraphColor(graph(B,C));//N Lists of node returned
	/* What I did is:
    2.2.1 put the result of Union(Bk) into an array. Prepare another array as a buffer.
	2.2.2 use two for loops to go through all the pairs in the array and to check C at the same time. If the pair appears in C. Remove one of them and put it into the buffer. The result is that all the nodes in the array do not conflict. Put the nodes left in the array into a lit link list, thus the array becomes empty, and we have a lit list that all it¡¦s members do not conflict.
	2.2.3 if the buffer is not empty. Move all the nodes in the buffer to the array. And repeat 2.2 until the buffer is empty.
	and these can be found in Manager::ConstructConflictFreeLists() -- Create lit lists */

}

3. AcquireImages(){

	//We now have N conflict-free lists L[]’s
	for i = 0 to N-1 {
		generate patten P[i] from L[i];//light pixels from all blocks in L[i]
		illuminate pattern P[i];
		capture HDR image I[i];
	}
	/* This part is done using OpenCV
	In Manager::Render(), after the pattern is lit, the camera takes a picture and save it. */
}


 
4. ProcessResults(){
/* ProcessResults() is implemented in void Manager::ProcessResults() 
the pointer to the images correspond to each lit is stored in an array of pointers.
*/
 
	C = empty;

	for each camera pixel k {

		new_Bk = empty;

		for i=0 to N-1{

			// find block (if any) that affects current pixel
			current_block = intersect(Bk, L[i]); // because L[i] was conflict free.

			// This can be at most one block (per L[i])
			// for example in lit #6, the blocks 0, 2, 8 are lit
			// if a pixel is lit in the camera image is lit by one // and exactly one ofthese three.

			if (current_block= empty)
				continue;

			// pixel k not affected by L[i];
			if (pixel k in I[i] = 0)
				continue;// no value measured, do nothing

			if (pixel k in I[i] < threshold) or last iteration {
				// below the threshold so store the energy here.
				// T() is the hierarchical representation of the matrix
				// indexed by block in the subdivision tree and camera pixel k
				T (current pixel, k) = pixel k in I[i];
				Continue;// no futther subdivision
			else
				//request subdivision for this block
				insert 4 children of current_block into new_Bk 
				/* What I have done: 
				4.1.1 I adopt the naming rule of the original paper, i.e. clockwise name the four blocks starting from the top-left one. And in each level the first block is numbered 0.
				4.1.2 The size of block can be determined once one knows what level currently is. The function DivideSquareToFourBlocks () take the coordinates of left, right, up, and bottom of a block, and recursively divide it into four blocks by calling itself four times.
				4.1.3 Note that number the block this way is good because, if the parent block ID is X, its four children will simply be 4*X, 4*X+1, 4*X+2, 4*X+3 respectively. When processing result. The Bk list could be create easily:
				*/
		}

		// set Bk for the next iteration
		Bk = new_Bk;
		// collect conflicts and add to C for the next iteration
		for each pair (s, t) where s and t are in Bk and s != t {
			insert (s,t) into C;// see the example in Initialization above
		}
		/* What I did is:
		4.2.1 Go through bk and put all the possible combination of pairs of node into C.
		4.2.2 keep adding entries of Bk into C make the size of C explode very quickly. And all these are store in an array. The program checks the number of nodes being added as compared to the max length of the array. Once this exceeds the threshold, say 80% of the max length, do a merge sort and combine the common terms to reduce the consumption. Since among Bk¡¦s the nodes contained usually have a lot of portion overlapped, this could usually reduce the consumption of memory significantly.
		*/
	}
}