# 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.

## Legend

- 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.

## Implementation Notes

- 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.

## Sources

(tar bundle)

bspapplet.java

BSPCell.java

Controls.java

CustomFrame.java

DrawingArea.java

Face.java

HalfSpace.java

main.java

Node.java

Segment.java

SegmentList.java

Util.java