
I had to do something similar at my last job, and ended up with the following. Note that this is not the simplest version, but at the time, I decided that it was the best combination of efficiency and numerical robustness I could come up with (the "make one huge poly for each plane and repeatedly clip it" version is prone to all sorts of numerical drift).
First of all, define the following data structure.
enum
{
BACK = 1,
FRONT = 2
};
struct Edge
{
Vector3 O; // line origin
Vector3 D; // line direction
int iBounded; // bitmask, see below
int iPlane[2]; // generating plane indices
int iPoly[2]; // adjacent polygons
int iClipPlane[2]; // clipping plane indices
float ClipDist[2]; // distance to last clipping plane
int iVerts[2]; // vertex indices
Edge() : iBounded(0) { }
};

If the iBounded member is 0, then the edge is an infinite line. If it's BACK or FRONT, the edge is a ray (clipped either in front or in the back, respectively). If it's 3, the edge is a line segment. Edges start out unbounded (as intersections of planes). To ensure winding consistency, you have to maintain a winding convention, eg., "an edge is wound counterclockwise wrt first generating plane".
After that first step, you clip every edge to a plane. The inner loop is as follows:
if (edge has not been clipped)
{
int whichSide = (edge_direction.Dot(plane_normal) < 0) ? FRONT : BACK;
iBounded = whichSide
clip edge to plane
set the edge origin to the intersection point
set the clip distance to the plane's distance
set clip plane index to this plane
}
else if (edge has been clipped, but not from this side)
{
clip this side, update edge structure, etc
}
else if (edge has been clipped from this side)
{
if (this plane makes the edge smaller)
{
clip this side, update edge structure
}
}

At this point, it might be a good idea to add a verification step to catch malformed brushes (and bugs): every edge should be clipped from both sides, if not then something is broken.
The next step is to fill in the iVerts fields. An edge is defined by four planes: the two planes whose intersection defines the line, and the two planes which clip the line on both sides. Vertices are defined by three planes (both of the former, and one of the latter). We need to link together the edges which share vertices. To that end, create a vertex structure which holds a list of edges connected to it, and go through the edge list. If a given combination of three planes has a vertex entry, then use its index, otherwise create a new one.
At this point, we have a list of edges (with counterclockwise winding with respect to, say, the left hand face), and a way to get from one edge to the next. This makes it easy to reconstruct polys:
for_each (edge)
{
if (edge>leftFace hasn't been created)
{
edge>leftFace = new Face
edge>leftFace>AddEdge(edge)
for_each (adjacent edge that has the same left plane index as the
current one)
{
edge>leftFace>AddEdge(adjacent edge)
adjacent_edge>leftFace = edge>leftFace
}
}
if (edge>rightFace hasn't been created)
{
...
}
}

This results in a poly mesh. Triangulate using your favorite method.
goltrpoat
EDIT: Forgot to mention this (writing from memory, haven't had to do this in a while). Obviously, not all edges generated in the first step are going to end up in the final mesh. In the second step, any edge that ends up with a negative length (i.e. the front cap is behind the back cap) is simply discarded.
