BSP Demo

User Interface

To insert a segment, press RIGHT mouse button on canvas. Drag out the desired segment and release.
Left click on E to drag the eye point to a different location.
Press RESET to clear all segments and begin with one BSPCell, which is the bounding box of the canvas.

E - eye point
The BSP cell containing E is highlighted in cyan
The number in the center of a segment represents the rendering order with respect to E's current position. The number starts at 1, indicating the first segment being drawn on the canvas.
One or more collinear vertex in between two end points indicates a subdivided segment. There is a rendering order number for each subdivided segment.

A simplified version of the DCEL is implemented to represent the counterclockwise segments of a Face. It is simply a non-circular, doubly linked list of Segments called SegmentList.
Segment.clip() is implemented by set-intersecting the Segment with the HalfSpace h induced by p'q'. First, find the intersection n with h. If such an intersection exists, we need to clip either subsegment pn or nq, depending which is to the right of h induced by segment p'q'. This is done by applying the Segment.rightOf() operation to see if the segment p'q' lies to the right of either node p or q.
BSPCell.split(S) splits a face by the half space induced by S. Two new Faces (and BSPCells) and two new directed edges (pointing opposite directions) representing the splitting segment are created. Each directed edge is inserted into the DCEL of one of the newly created Faces. The Face that is on the positive HalfSpace is identified by testing one of the vertices in one of the Faces to see which half it belongs to.
BSPCell.Locate(P) recursively finds the half of a given BSPCell that contains P and simply returns the leaf cell containing P. The process starts at the root of the BSPCell tree. Hence the BSPCell tree is a convenient data structure for point location as well.
BSPCell.Traverse(P) is similar to BSPCell, except that it recurses down the half of the cell that does not contain P first, then draws the splitting segment, and then recurses down the other half plane.