Converting 3D brushes to triangles
Before I jump into the heart of this problem, a few definitions are needed.
Brush - A collection of infinite 3d planes that define a volume. That means that a valid brush has at least 4 planes, but most have 6 to form cubes. It's impossible to define a concave shape in this way, so all brushes are convex.
Infinite Plane - This is basically just an equation of the form Ax + By + Cz + D = 0. By taking any point (x,y,z) and substituting in that equation we get a number, that is either greater, less then or equal to 0. If the number is 0 then the point is on the plane. A number less than 0 means that the point is "outside" the plane, and a number greater than 0 means that the point is on the "inside".
Converting BSP brushes into triangles isn't actually as hard as it sounds. The problem is to basically, take a brush, and graphically represent the set of points that lie on the inside of all the planes in that brush. This article describes my approach used in the libPortal library.
PolyList pL = emptyList;
//Create a list of polygons
For each plane p in brush b
Polygon poly = p.createHugeSquare(); //Create a huge square polygon to represent p
pL.append(poly);
for each polygon p in pL
for each polygon o in pL
if o != p //Cut each polygon with each other plane.
p->cut(o)
//Once this loop has completed each polygon in pL will be "cut down to size" Basically, the polygons will only exist within the inside of all the other planes in that brush.
for each polygon p in pL
p->triangleDecomposition();
//save these triangles.
Generating texture coordinates with the triangle verticies will be discussed later.
By rendering all the triangles of each polygon together you get the shape of all the points inside all the planes.
There are some tricky parts to this algorithm, and the rest of this article will present the solution to each one.
Representing and manipulating 3d polygons
For BSP brushes all points in a polygon lie on the same plane, so it makes most sense to store only 2d points and a plane equation. The hardest thing here is that once you want to get the final vertex positions, you need to be able to turn those 2d points into 3d points. So basically, you need a 4x4 transformation matrix that takes the points in the 2d points in the xz (by arbitrary choice) into world space on the plane equation. Here is a copy-paste of my polygon constructor.
|
Polygon3D::Polygon3D(vmml::Vector4d plane) { orientation.setIdentity(); vmml::Vector3d up(0.0, 1.0, 0.0); //the plane that we store 2d points in. vmml::Vector3d direction(plane.x, plane.y, plane.z); //The direction we want the polygon to face direction.normalize(); vmml::Vector3d tan(direction.cross(up)); //a tangent, to form a basis. //This block checks to make sure that up cross dir isn't a near 0 vector. //If it isn't, we can assume tan and bitan are the regular basis vectors, //of the current world space. if(tan.lengthSquared()<0.01) { orientation.setIdentity(); //Since the direction and up vectors are the same, the I matrix // should represent the orientation. } else { tan.normalize(); vmml::Vector3d bitan(direction.cross(tan)); bitan.normalize(); orientation.setColumn(0, tan); orientation.setColumn(1, direction); orientation.setColumn(2, bitan); } double d = -plane.w; orientation.setTranslation(direction*d); } |
These lines
orientation.setColumn(0, tan);
orientation.setColumn(1, direction);
orientation.setColumn(2, bitan);
are the important ones. By putting the tangent, normals, and bi-tangent vectors into the rotation part of a transformation matrix, we get the matrix that transforms points from world space into the space defined by those vectors. The last lines
double d = -plane.w;
orientation.setTranslation(direction*d);
simply set how far each point has to move along that direction vector to reach the polygon plane.
There is also the matter of cutting polygons. I'm going to assume you know how to intersect planes and vectors for this part. Basically, for every adjacent pair of verticies along the outside of the polygon, test each vertex in each pair to made sure they are on the same side of the plane. If not, create a vertex on the plane along the vector between the two points. Cycle though the polygon again removing all verticies on the wrong side of the polygon.
All brushes are convex, that means that every polygon that makes up a face of a brush is a convex polygon. This makes decomposing the polygons into tiangles for rendering very easy. If there are 3 verticies in the polygon, leave it as is. If there are 4 split it in two. If there are more than 4 verticies average their positions and connect that center vertex to all the pointer verticies to create flower pattern. There is also the fan pattern, but this makes long skinny triangles and isn't so great for physics engines and some lighting calculations. (Per vertex)