Drawing a brush which represented by planes

I need to draw a brush which is represented by n planes. Therefore I need to create polygons from the planes.

I would like to know that the method I am going to use is good enough, because rewriting will take too much time. So…

First I need to find the vertices and then sort them into polygons. To find the vertices I need to find the intersection of the planes (3 planes = 1 vertex). This mean 3^n tests for n planes(!!). I don’t think so…

So I have to sort them in some way. I found out that if I could sort them I would reduce the number of test.

Please list your ideas.


Here is method with n^2 time.

vector vertexes[];

for i in planes{
polygon = HugePolygonOnThePlane(plane_i);
for j in planes{
assume normal points outside of the brush.
polygon is ready.

What do you mean by front and back polygons?


Your algorithm is n^3 if you want the entire set of polygons, not just one polygon.

Intersecting planes is a very direct visualization of what goes on inside a BSP tree, I think, so if you haven’t already, put these planes into a BSP tree. Then, at data prepare time, you can calculate these polygons from the planes and store them in the same tree. This has the benefit of giving you the polygon to draw after you’ve used the BSP tree for visibility data.

Another way of doing it is storing information about which planes actually form the outline of the polygon or polygons on each plane, and for each polygon, walk that list.

If my limited knowlege on this subject is correct, then the front polygon would be on one side of the plane, and the back polygon would be on the other side of the plane. In other words, if a single polygon spans accross a plane, it’s cut into front and back polygons.

Actually, the way you were going to do it should be fine. There are in fact nC3 intersections to perform to find all potential vertices. Some of those can usually be skipped quite early since if the normals of two of the planes to be intersected are parallel, the intersection can be skipped. After all potential points are found, then test each point to see if it is behind or on all the planes of the brush, if so keep it, else discard it. The points that remain are the real vertices. Next for each plane in the brush, use it to select the vertices in that plane, and if there are more than 2 vertices found in the plane, find an ordered winding among those vertices to make the face in that plane.

DFrey, that the exact way I meant to do that. But I meant to use a BSP tree in order to test each point if it inside or on the brush or outside of it.