Real Curved Surfaces, NOT polygon tesselation

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.

Can you give a reference where it describes an algorithm to directly scan convert a surface, even something as simple as a bezier tensor-product surface in 3d? I have studied curved surfaces a bit, and have never run into one (albeit, my NURBS experience is a bit lacking).

The complexity of the problem for directly scan converting surfaces accurately would be intractible I think. Now approximations are fine, but I think you’d get a much poorer one out of a direct scanline approximation. As far as I can think of it would amount to root finding (or ray-tracing essentially)… and if my knowledge surves me correctly a cubic tensor product surface gives a 26 or so degree implicit polynomial, which would be near hell to root find (some guy at Maya said they just use subdivision instead to detect ray-surface intersections… warning: 3rd hand info.).

Another big reason to render curves using subdivision is that it’s WAY more numerically stable compared to algorithms like forward differencing.

EDIT: Also, in math books, there are equations for directly calculating the number of subdivisions needed to stay pixel perfect (anti-aliasing is a more complicated procedure, and is much more difficult when attempted directly… basically requires a completely different paradigm).

All things considered it seems like it would be more efficient to tesselate it, and then for any future tesselations, optimize them to reuse already generated points, etc.

By all means, if I’m missing something let me know, but in my experience, that’s just the way it is.

for the reasons adruab mentioned it’s better to subdivide than to use some kind of true nurs thingy.
infact there should be some kind of a programable subdivition shader after the vertex shader. you should be able to subdivide stuff efficiently down to pixel level, it should allso be able to create new polygons and even disregard to render some of them.

infact there should be some kind of a programable subdivition shader after the vertex shader. you should be able to subdivide stuff efficiently down to pixel level, it should allso be able to create new polygons and even disregard to render some of them.
There isn’t enough information after the vertex shader to accomplish this. Normals may or may not exist anymore, so PN-triangles may not be possible. If normals exist, they my not even be in screen space.

Also, to do subidivision surfaces from just points, you need to have both connectivitiy informaiton and a fairly large sub-section of the mesh. The modified-butterfly algorithm, for example, needs something like 12 vertices to generate the position of 1. This is just not available in the setup unit.

Yeah current vertex shaders cannot generate new vertices, so people wanting programmable subdivision on the gpu, will have to wait for the topology processing stuff (proposed for next version of DirectX and for the original pure OGL2.0 spec).

Subdivision in the modeling sense does require connectivity information (fairly complicated actually). However, the curved surfaces and subdivision I was referring to, was just for explicit surfaces, which basically amounts to just normal cubic curve subdivision in 2 dimensions. You could try to hack it with PN triangles (though the normals would be only for curve shape and the actual normals for lighting could be different).

But yeah, I can’t wait for the topology processing. I certainly hope they do incorporate all, or at least most, of the things that were in the original GL2.0 spec.

Actuarly, the only extra information you need for subdivition is how many times to subdivide the folowing edge.
If the triangles connected to that edge is subdivided the same amount of times, the subdivition should not produce different results.

You actuarly don’t need all that curved stuff, just subdivition and a way to displace the resulting vertics in texture space.

You actuarly don’t need all that curved stuff, just subdivition and a way to displace the resulting vertics in texture space.
Yes, and all curved surface mechansims of displacement either require normals or more points than just the edge.

If you’re just wanting to turn one triangle into 4 coplaner ones, that’s trivial; it’s the part where you turn that into a representation of a curved surface of the mesh that is difficult.

Originally posted by Adruab:
Can you give a reference where it describes an algorithm to directly scan convert a surface, even something as simple as a bezier tensor-product surface in 3d? I have studied curved surfaces a bit, and have never run into one (albeit, my NURBS experience is a bit lacking).

No, sorry, I don’t have a reference because this is my own unpublished work, but I can (try to) make my meaning a bit clearer.

The algorithm I have in mind is object order, not image order, so there is no need to find the root of the surface or curve along each scan line.

Basically it is just the same iterative, constant interval, forward differece subdivion algorithm given in Foley, Feiner & van Dam, 2002, with the following modification: subdivide to the fineness of a fragment and draw a point instead of a polygon (for a curved surface) or a point instead of a line segment (for a curve).

This is not as easy as it sounds for 2 reasons:
[ul][li] We have to apply the viewing transform to find out how many fragment lines in each direction the curve or surface crosses, and so how many subdivisions to use.[*] The algorithms given are for nonrational curves, and the most straight forward generalization to 3D rational curves would be in homogenous coordinates, giving 4 independant functions of s & t, giving {X, Y, Z, W}.[/li]The final normalized {x, y, z, 1} coordinates are found, as always, by {X/W, Y/W, Z/W, W/W}. This represents the rational curve or surface exactly, and can also exactly represent any conic or quadric curve or surface.

The problem is we can’t find out how many fragment lines in each direction the curve or surface crosses just by looking at {X, Y, Z}. I’m sure this problem is tractible, I just have’nt figured it out yet. Maybe someone has got some ideas?[/ul]
To enable hardware to scan convert them easily, GL (& the hardware implementation) could provide just a single rational curve primitive and a single rational curved surface primitive, with GLU converting other more complicated curves and surfaces like NURBS to this native form.

To make clipping and scan conversion easy I suggest primitive curves & surfaces with an explicit basis and the convex hull property.

Rational Bezier curves and patchs have these properties and are also the output when using the Oslo or Bohm algorithms to subdivide NURBS into curves/curved surfaces with an explicit basis, so would save one multiplication of a 4 vector by a 4*4 matrix per control point for NURBS.

Perhaps the curves and surfaces could pretend to be in GLU, and have the same interface as the currently available curve & curved surface approximations, with direct scan coversion being available as an option, maybe available with a glEnable()?

Also I have’nt considered lighting yet. Normals if needed would have to be generated (per fragment) by OpenGL. This is a bit of a departure from normal OpenGL practice as I understand it, where the programmer or the utility libraries, not GL itself, calculates the normals if needed. Perhaps we could hide behind GLU again and have the hardware only generate normals if glEnable(GL_AUTO_NORMAL) or some such has been called.

According to Foley, Feiner & van Dam, the normal is given by an order 5 polynomial, which could be cast as a forward difference algorithm as well (presumably with 1 extra addition/subtraction per fragment compared to the order 4 for the curve itself).

Ops. Make that Foley, Feiner & van Dam, 1997, NOT 2002. And add Hughes to the authors as well. I’ve Been reading Angel, 2002 and must have got a bit confused. Sorry.

References:

Edward Angel, OpenGL™: A Primer, Addison-Wesly, 2002

James D. Foley, Andries van Dam, Steven K. Feiner, John F. Hughes, Computer Graphics: Principles and Practice, 2ed (in C), Addison-Wesly, 1997

Originally posted by Cian:
[b]

  • Order 3 rational curves can represent exactly any quadric or conic surface.
    [/b]
    The bit about the quadrics is not true. An order 4 non rational curve can represent a quadric, hence the name.

Sorry, I don’t know how this little chestnut slipped past me. Must have been tired.

Ok, so you’re saying subdivide and draw the pixel eh? I’m not sure how that differs from the ray-tracing example I gave, but ok.

As for performance, it seems to me like you wouldn’t get better performance out of pixel perfect version when compared to the OpenGL evaluators. This, of course, is assuming they are optimized for optimal vertex cache reuse… You could statically optimize better if it truly does use direct quad-strips (as it describes in the spec), but that would be MUCH more expensive to reevaluate (if you need to retesselate for example).

As such, I have no idea how pixel perfect calculation could be done faster than hardware accelerated polygon approximation. Especially if some sort of adaptive subdivision were used (which would get around the seeming problems you mentioned). How would you deal with determining which part of a subdivided surface is inside a pixel (especially using forward differencing, as it’s not built for subdivision)? And how would all the CPU overhead deal with a GPU’s pipelined architecture? It seems to me that until something like this is done completely in hardware, polygonal approximation would be much better.

An alternative (since it would be done in software), is to have a library similar to GLU that was focused on software rasterization using OpenGL as its base. But I don’t think that would necessarily fit into the opengl paradigm (hardware focus), and thus not into the library. If I’m misunderstanding your intent, feel free to let me know.

However, I’m sure there are ways to optimize polygonal processes.

For one, you could pretransform the control points before you start interpolating (in order to save on the vertex transformation overhead). The other thing is the lighting would have to be done entirely inside the pixel shader and you couldn’t use a complicated vertex shader (but that’s basically what you were proposing anyways). I don’t know if this is possible when trying to bypass the vertex stage or not (you can do that with primitives in D3D at least…), but it’s worth a try.

The other thing you could do is generalize the idea of figuring how many subdivision steps would be required [1] to make each quad an area smaller than a pixel (which would get you to the pixel perfect level).

[1] Gallier, Jean. Curves and Surfaces in Geometric Modeling. pg. 145-146