Thank you for writing this. I'll respond to you more carefully on Monday. There are a number of things you mention which we've dealt with. There are some which we have probably done right. And there are some which we have done differently but still conformant to OpenGL. You might want to take a look at the model and documentation and see specifically how we're already doing things.
Thanks! On Sat, 29 Jan 2005 18:41:22 -0500, Daniel Phillips <[EMAIL PROTECTED]> wrote: > Hi Timothy, > > There was a thread on rasterization back there somewhere in which a few > points were left unresolved or resolved suboptimally. I'll try to > address some of these now. Caveat: it's been ten years since I last > implemented this and both my source (in Forth) and reference material > are packed away somewhere in boxes at the moment, so this is all from > memory. > > The definition of "accurate" rasterization of a trapezoid is: > > - Every pixel whose center lies with the trapezoid is filled exactly > once > > - No pixel whose center lies outside the trapezoid is filled > > As a consequence, every pixel in a mesh of trapezoids is filled exactly > once and no pixels inside the mesh are left empty. Insideness is > defined in terms of half spaces: > > - A pixel is 'inside' a left bound if its X coordinate is greater > than the bound. > > - A pixel is 'inside' a right bound if its X coordinate is less > than or equal to the bound. > > We decide whether or not to draw a pixel based on its 'winding count', > which is the sum of left boundary insideness less the sum of right > boundary non-insideness: > > - If the current polygon mode is "winding", draw the pixel if its > winding count is nonzero > > - If the current polygon mode is "alternating", draw the pixel if > its winding count is odd > > For what it's worth, "left boundary insideness" and "right boundary > non-insideness" are the same thing. > > Y coordinate insideness is exactly analogous to X coordinate insideness, > except that the insideness result applies to entire trapezoid scans > rather than individual pixels. (Here let me plead for no departure > from the usual 2D treatment of Y coordinates, that is: increasing > device Y corresponds to increasing memory address. Any consequent Y > negation should be handled in the device coordinate transformation.) > > Above, I define insideness in terms of pixel centers, but it is better > to work with upper left pixel coordinates instead, and compensate by > biasing all geometry one half pixel to the lower right. (If we were to > implement multisampling, say by a factor of four, we would bias all > geometry by a quarter pixel.) With this simplification we can now > forget about rounding and work in terms of truncation (i.e., floor). > > I seem to recall it was decided that geometry should be processed in > fixed point, as opposed to floating point for color, texture and depth > parameters. Considering that the multipliers are 18 bit, I suggest > 14.18 fixed point format, or perhaps 12.20 on the theory that a couple > of bits of extra interpolation accuracy are worth the extra shifts. > > Now we get to the meat. To fill a pixel span from a left to a right > trapezoid boundary: > > - Truncate the interpolated X coordinate of the left edge and add one, > giving the X address of the first leftmost to fill > > - Truncate the interpolated X coordinate of the right edge, giving > the X address of the rightmost pixel to fill > > The count of pixels to fill is thus trunc(Xright) - trunc(Xleft) > which may be zero. Note that we do not use ceiling(Xleft) for the > leftmost pixel because that violates the half space conditions, causing > pixel overdraw between adjacent trapezoids if Xleft is an exact > integer. > > We can test that this is all working correctly by reducing the > calculated pixel span count by one. A horizontal single pixel gap > should appear between all triangles. We can test the handling of > vertical coordinates similarly. > > All interpolants, i.e., texture U and V, R/G/B and W or 1/W need to be > adjusted before span filling begins. Given T, an interpolant, first > calculate the per-pixel X delta as: > > Tdelta = (Tright - Tleft) / Xright - Xleft) > > then: > > Tadjusted = Tleft + Tdelta*frac(Xleft) > > This calculation is more complex for perspective interpolation because > the adjustment has to be performed on the inverse of the interpolant. > Could somebody please take the time to work out an efficient algorithm > for this? Even per-span divides have to be kept to a minimum otherwise > small triangles become too expensive. > > A number of factors determine texel rendering accuracy. The correctness > and accuracy of the above interpolant adjustment is one of the main > factors. When the job is done properly, boundaries between rows of > rendered texels will appear exactly linear no matter how near the > viewpoint is to the polygon plane, and both the jaggies in the texel > boundaries and the jaggies in the polygon edges will swim across the > screen monotonically and smoothly as we animate the viewpoint, no > matter how finely. Jaggies will never suddenly "jump backwards" from > frame to frame even if the viewpoint is rotating. > > Besides ironing out all the tricky interpolant accuracy issues, > numerical accuracy problems will also show up. Multiplier precision > problems typically manifest as short runs of single pixel "noise" in > what ought to be simple jags along texel boundaries. While it is nigh > on impossible to eliminate such noise completely except by filtering, > such artifacts can be made very rare. > > With careful attention to numerical issues much clamping of generated > texture coordinates can be eliminated, although in my experience, > eliminating all clamping is very difficult. > > Some logic can be factored out of the per-pixel pipeline by directly > interpolating addresses as opposed to coordinates. > > Again, I did all of this quite a few years ago, so it needs to be > checked over carefully. > > Regards, > > Daniel > _______________________________________________ Open-graphics mailing list [email protected] http://lists.duskglow.com/mailman/listinfo/open-graphics List service provided by Duskglow Consulting, LLC (www.duskglow.com)
