OpenGL really needs direct scan conversion of biparametric rational curved surfaces of at least order 4 instead of approximating them with polygon meshes. Here’s why:
-
To get a good approximation of many simple curves sometimes requires more polygons than current systems can render in real time.
-
The increased expense of scan converting curves as compared to scan converting lines is frequently used as a justification for not diplaying them directly but instead approximating them with lines. A similar argument is used for approximating curved surfaces with polygon meshes. However these arguments ignore the fact that the curve or curved surface is scan converted just once, whereas many lines or polygons are often needed for a close to reasonable approximation of a curve, and each of the lines is scan converted individually. So even though scan converting a curve is a harder problem than scan converting a line, directly scan converting a curve could turn out to be easier than scan converting the same curve which has been approximated with lines (see below for an analysis), and the same goes for curved surfaces and polygon meshes.
-
It eliminates the need for recursive subdivision, flatess tests, level of detail handling and crack removal, and other potentially complex codes, all of which might be necessary for good performance and reasonable accuracy with a large number of curved surfaces.
-
Order 3 rational curves can represent exactly any quadric or conic surface. Important for modelling common objects like spheres, ellipsoids, cones, cylinders, as well as objects less common but important to some applications like molecular modelling and astronomy.
-
Order 4 rational curves can represent NURBS and other bicubic surfaces, useful for approximating general curved surfaces and many natural objects (eg. the human body).
-
Control points could be represented as just another sort of vertex, subject to the same projective transforms as other vertices. Correct scan conversion is possible in this case if the curves are rational.
-
If a curves and surfaces with the convex hull property were chosen for the internel representation, trivial accept/reject clipping would be easy, and would consist of accepting/rejecting the convex hull of the control points. Nontrivial clipping could be accomplished analytically using parametric subdivision, or it could be carried out after rasterization using simple scissor tests.
I will show direct rasterization of a parametric cubic curve in 2 space using forward differences is frequently as efficient as scan converting the large number of lines needed for a good approximation. Result should generalize for non rational bicubic surfaces in 4 space which with the division by w that is carried out by OpenGL are equivalent to rational bicubic surfaces in 3 space.
Here’s some numbers:
Scan converting a line using the efficient midpoint algorithm will need 4 integer subtractions and 3 integer multiplies by 2 (shifts?) for setup per line, and a further 2 comparisions (integer subtractions), 1 integer addition and 1 or 2 increments of an integer by 1 per fragment that intersects the line (Foley, et al, 1997).
If we assume that on average each curve is approximated by 8 line segments and that each line covers on average 8 fragments the cost of scan converting the approximated curve will be 32 integer subtractions and 24 integer multiplies by 2 for setup and a further 192 integer subtractions/additions and on average 96 increments of an integer by 1. This gives an average total of 224 integer additions/subtractions, 24 integer multiplies and 96 increments of an integer by 1 for scan converting the lines.
Before the lines are scan converted however, we must subdivide the curve to give the line segments. We can use the forward difference subdivision algorithm from Foley, et al. I will ignore the per curve setup cost of this algorithm because it is small (a few adds and multiplies), and because I will use the same algorithm for direct scan conversion, it is constant for both approaches. The per point cost of this algorithm is given as 9 additions for the case of a curve in 3 space, which reduces to 6 integer additions for our curve in 2 space, for a grand total of 230 integer additions/subtractions, 24 integer multiplies by 2 and 96 increments of an integer by 1, plus a small setup cost which it shares with the direct scan conversion method.
And the approximation is far from perfect. Even if we assume that there are 4 fragments per pixel (unlikely?), the curve will still be seen as being made up of small lines. Even if there are 8 fragments per pixel there will still be sampling errors, because the sample rate is lower than the Nyquist frequency (Foley, et al, 1997).
The same curve can be directly scan converted using the same curve subdivion algorithm if instead of line segments we draw fragments. The cost per curve is then equal to the number of fragments intersected the curve (approximately 8*8=64) times number of operations per fragment (6 integer additions, as above) which is 384 integer additions, plus the small constant setup, comparible in complexity to scan converting the linear approximation, but the curve is drawn exactly and is completely smooth!
for the underlying representation I would suggest a curve with a uniform basis as well as the convex hull property, for ease of computation and clipping. As suggested in Foley et al, curves and surfaces with a non uniform basis like NURBS could be subdivided into Bezier curves using the Bohm or Oslo algorithms and then the control points multiplied by a basis conversion matrix before being handed to the implementation to display. In OpenGL the most appropriate place for this conversion of forms would be the utility library.
Bibliography:
James D. Foley, Andries van Dam, Steven K. Feiner, John F Hughes, 1997, “Computer Graphics: Principles and Practice”, 2ed (in C), Addison Wesley Publishing Company.