Visible Surface Algorithms - Computer Graphics and Geometric Modeling - page 271

BSPtree function BuildBSPTree ( polygon list plist)
begin
polygon list frontList, backList;
polygon

root, poly, frontPart, backPart;

if IsEmpty (plist) then return (Empty BSP tree);

frontList := nil ; backList := nil ;

root := SelectAndRemoveOne (plist);
for poly in plist do
if InFrontOf (poly,root)
then Insert (poly,frontList)
else if InBackOf (poly,root)
then Insert (poly,backList)
else

begin
SplitPolygon (poly,root,frontPart,backPart);
Insert (frontPart,frontList);
Insert (backPart,backList);
end ;

return (CreateBSPTree (BuildBSPTree (frontList),root,BuildBSPTree (backList)));
end ;

Procedure TraverseBSPTree ( BSPTree T)
{ The procedure Display is assumed to do all the necessary transformations,
clipping, shading, etc. }
begin
if IsEmpty (T) then return ;
if InFrontOf (eye,rootPolygon (T))
then
begin
TraverseBSPTree (backSubtree (T));
Display (rootPolygon (T));
TraverseBSPTree (frontSubtree (T));

end

else

begin
TraverseBSPTree (frontSubtree (T));

{ If back faces are not to be displayed, remove the next statement }
Display (rootPolygon (T));

TraverseBSPTree (backSubtree (T));

end

end ;

Algorithm 7.5.1. The BSP tree algorithm.