Of Curves and Buffers
I’ve been talking a lot about patches from the Quake 3 BSP format for curved surfaces lately, so I thought I’d delve into some of the inner workings, including the math for generating them from control points. One resource that I have found to be very helpful in all things relating to the Q3BSP file format is Kekoa Proudfoot’s Unofficial Quake 3 Map Specs. Gold mine. The exact math for calculating vertices from the control points is not in there, but quadratic Bezier calculations can be Google’d.
Each patch has a set of subpatches, and each subpatch is represented by 3×3 control points. In the file, points are stored such that adjacent sets share a row of control points. Of course, it is also necessary to allocate enough memory for the number of vertices you want, depending on your target level of detail. When we have the subpatch and control points that we want, now comes the magical math. Cycling through the grid of vertices, calculate the points in the subcurve based on where you are across the 3×3 control points during the loops. First calculate three temporary vertexes using three control points each, then calculate the final vertex based on those three. The math for calculating a bezier value from three others goes something like this:
out = a*(1.0-frac)*(1.0-frac) + b*2.0*frac*(1.0-frac) + c*frac*frac;
‘frac’ would be a floating point value from 0.0 to 1.0 representing how far along the curve to end up – for example, if given 0.0, it would just return the value given by a, and given 1.0, it would return the value of c. These calculations would be repeated for all three values for a point, and the same calculations are used for position, texture coordinates, normals, and colors.
As an added bonus, I’ll say a little something about vertex buffer objects (VBOs) in OpenGL. Basically, VBOs allow you to save vertex information on the GPU, so that you don’t have to send it from the CPU every time you want to render something, which often affords a nice increase in speed. I recently implemented these for world rendering in Scorch Marks. At least in OpenGL, they are wonderfully easy to implement into an existing codebase. Basically just load the information into the buffers, change the targets for your vertex arrays, and you’re done. Of course, this could easily be tied into an implementation of Q3BSP patches.