An array of boolean flags where each either takes the value or .
Integer variables and , initialised to zero.
Variables , and making up a point in space.
Another array of boolean flags .
The variables , , , , and array are used to keep track of the best fit as the algorithm proceeds.
Set all the to .
For each disparity point :
Calculate the normalised perpendicular distance
from the plane to the centre of the root cube:
If the plane passes through the root cube's circumscribing sphere: set to .
Call the procedure with arguments as follows:
Procedure ( array of flags , array of normalised distances , subdivision level , accumulator value , line of descent list ):
Eight arrays of normalised distances.
Accumulators for each , initialised to zero.
Boolean flag , initialised to .
Set flag to .
Subdivide child cubes receiving greater than or equal to votes: If :
Call with arguments , , , and extended line of descent.
Set flag to .
If is still (i.e. no further subdivision of this cube), test for best fit so far:
Set to .
Calculate centre of cube in space by calling procedure with the line of descent as argument. The results are copied into , and .
Copy array of flags into array .
Procedure ( line of descent list ): begin
Set , and to zero.
While line of descent not traversed (i.e. root cube not yet reached):
Replace old values of , and :
Add centre -coordinate of root cube to ( and
coordinates of root are zero):
At the end of the algorithm is the highest level of subdivision reached. This must be greater than or equal to for the fit to be used. is the highest accumulator value of a cube at subdivision level , the cube has centre and these are the best fit plane parameters. The flags are if the 'th disparity point voted for the winning cube, and those disparity points constitute the subset of all the points which best fit a plane, given that the total weight of the points must exceed . They and the values of and can stored for use. More precise estimates of the plane parameters can be calculated using orthogonal regression.