jorice@maths.tcd.ie (Jonathan Rice) (07/17/90)
I'm writing this program to draw perspective pictures of landscapes and I could
do with some help on a couple of fronts. What I start out with is a gridded
height map and a satellite photo overlay image. To render the thing I use just
about the simplest method possible - I treat neighbouring heights in the height
map as the corners of quadrilateral surface tiles. I perspectively transform
these corner points to give me a 2-D quadrilateral in screen space, which I
fill with a colour read out of the photo overlay. Hidden surface stuff is done
with back-to-front overplotting along scan-lines of the height map as in
Coquillart and Gangnet's "The Shaded Display of Digital Maps". I've got a sort
of a prototype going in an X environment and it's okay as far as it goes, but
in order to improve image quality, I'm going to have to renounce the graphics
functions of X and do my own anti-aliased 24-bit polygon or triangle filling.
What I think I need is something along the lines of Carpenter's A-Buffer - has
this algorithm been improved on in any substantial way since it was published
in '84? One paper I've read claims better quality images by anti-aliasing on an
area greater than just the current pixel ("Efficient Alias-free Rendering by
using Bit-masks and Look-up Tables" - Abram, Westover & Whitted, '85). How
much does that matter? I'm going to be trying to put my images together into a
short video, so what I'm particularly interested in is removal of
frame-to-frame aliases rather than absolute rendering accuracy. Also, I have a
HELL of a lot of very small triangles or quadrilaterals to draw - are there any
optimisations that can be made to the scan-conversion process when no polygon
ever gets larger than about five pixels? Any information that anyone wishes to
grace me with would be appreciated. I'd particularly love some code that
implements this stuff, particularly an A-buffer or such-like. I am no
masochist.
-- Jonathan
o----------------------o----------------------------o--------------------------o
| Jonathan Rice | Email: jorice@cs.tcd.ie | He was a common fly |
|----------------------| Tel: 353.1.772941 x2156 (w)| With a taste for fashion |
|Computer Science Dept.| 353.1.6245415 (h)| They were thrown together|
| Trinity College | Fax: 353.1.772204 | In a heat of passion |
| Dublin 2, | woof /\___/ | - "Human Fly", |
| Ireland. | /| |\ | The Horseflies |
o----------------------o----------------------------o--------------------------omarkv@gauss.Princeton.EDU (Mark VandeWettering) (07/17/90)
In article <1990Jul16.225553.2623@maths.tcd.ie> jorice@maths.tcd.ie (Jonathan Rice) writes:
[ Jonathan needs to draw large numbers of small polygons quickly
and with proper antialiasing. Wants suggestions over A buffer
or Abram-Westover-Whitted's method ]
You might also examine the Reyes paper in the 86 Siggraph (I think, all
this stuff is once again, not in my office). Reyes basically just did
a scanline Z buffer at some higher resolution, and then filtered the
results apprpriately to get an nice image. I believe the aliasing
artifacts will be lessened because imformation from adjacent pixels can
be used for filtering, allowing a wider filter to be used.
Markrobert@texas.esd.sgi.com (Robert Skinner) (07/18/90)
In article <1264@idunno.Princeton.EDU>, markv@gauss.Princeton.EDU (Mark VandeWettering) writes: |> In article <1990Jul16.225553.2623@maths.tcd.ie> jorice@maths.tcd.ie (Jonathan Rice) writes: |> |> [ Jonathan needs to draw large numbers of small polygons quickly |> and with proper antialiasing. Wants suggestions over A buffer |> or Abram-Westover-Whitted's method ] |> |> You might also examine the Reyes paper in the 86 Siggraph (I think, all |> this stuff is once again, not in my office). Reyes basically just did |> a scanline Z buffer at some higher resolution, and then filtered the |> results apprpriately to get an nice image. I believe the aliasing |> artifacts will be lessened because imformation from adjacent pixels can |> be used for filtering, allowing a wider filter to be used. |> |> Mark actually, the Reyes implementation discussed in the paper divides the screen up into rectangular chunks, I expect from 16-64 pixels on a side. I thought the most interesting thing about Reyes was the way it processed primitives *before* they were scan converted (its simple and can be made object-oriented). The back-end scan conversion is independent; Pixar used a Z buffer. I implemented a renderer with a Reyes-like front end, and two scan conversion back ends: scanline Z buffer with 4x4 or 8x8 stochastically jittered subsamples, an alpha buffer with 4x4 or 8x8 masks. The back-ends were like ying and yang. The Z buffer was about 3-4 times as slow as the alpha buffer, because you have to test a group of samples for inclusion in a polygon. You can't use coherence because the subsamples are jittered (well you could use some, but its not worth it because the polygons only cover a few subsamples). The alpha buffer was optimized to convert polygon edges into alpha masks representing half spaces. These half-space alpha masks were then logically AND'ed to get the mask(s) for a single polygon. The mask was then inserted into the sorted list for the pixel it covered. Logical occlusion operations were performed on the mask as it was inserted. If the mask was found to be totally occluded before its insertion point was found, it was thrown away. All masks behind the new one were then occluded by it, and if any of them went to zero, they were thrown away. Believe it or not, doing all of those extra occlusion operations was faster than putting them off to the end, because they kept the size of the list small. (Oops, I slipped into thesis mode there. That's probably more detail than you wanted.) On the other hand, I never was able to fully debug the alpha buffer. Because of all sorts of odd boundary conditions, I occasionally created incorrect masks. The Z buffer was much simpler to code (about 1/7th the size of the alpha buffer), and worked flawlessly from the beginning. The two algorithms produced almost identical images. Robert Skinner robert@sgi.com You don't know what we could find. Why don't you come with me, little girl, on a magic carpet ride
mark@masscomp.ccur.com (Mark Thompson) (07/19/90)
Reply-To: mark@calvin.westford.ccur.com (Mark Thompson) Organization: Concurrent Computer Corp. Westford MA. In article <10491@odin.corp.sgi.com> robert@sgi.com writes: >I implemented a renderer with a Reyes-like front end, and two scan >conversion back ends: scanline Z buffer with 4x4 or 8x8 >stochastically jittered subsamples, an alpha buffer with 4x4 or >8x8 masks. > >I never was able to fully debug the alpha buffer. >Because of all sorts of odd boundary conditions, I occasionally >created incorrect masks. The Z buffer was much simpler to code (about >1/7th the size of the alpha buffer), and worked flawlessly from the beginning. > >The two algorithms produced almost identical images. I'll bet those images weren't identical when rendering piles of overlaping partially transparent objects! +--------------------------------------------------------------------------+ | Mark Thompson | | mark@westford.ccur.com | | ...!{decvax,uunet}!masscomp!mark Designing high performance graphics | | (508)392-2480 engines today for a better tomorrow. | +------------------------------------------------------------------------- +
markv@gauss.Princeton.EDU (Mark VandeWettering) (07/19/90)
>Reply-To: mark@calvin.westford.ccur.com (Mark Thompson) >In article <10491@odin.corp.sgi.com> robert@sgi.com writes: >>I never was able to fully debug the alpha buffer. >>Because of all sorts of odd boundary conditions, I occasionally >>created incorrect masks. The Z buffer was much simpler to code (about >>1/7th the size of the alpha buffer), and worked flawlessly from the beginning. >>The two algorithms produced almost identical images. This is consistent with my intuition as to the costs involved. Although I am suprised that your Z buffer was slower. I was glancing through my notes and found a fragment of code that was supplied to me by Pat Hanrahan that did "point-in-polygon" testing very efficiently for quadrilaterals. If we call this routine "sample", then rendering a micropolygon becomes something like: compute the screen bounds xmin-xmax ymin-ymax for (x = floor(xmin) ; x <= ceil(xmax) ; x++) { for (y = floor(ymin) ; y <= ceil(ymax) ; y++) { if (sample(poly, x, y)) color(x, y, color_of(poly) ; } } sample uses the Jordan Curve test to figure out if the point is in the polygon. If an odd number of edges cross the +x axis, then you are inside. This can be done with some moderately small number of instructions. Basically the idea is to recenter the polygon around the sample point. Then, check vertices 0 and 2 to see if they have different signs. If they do, then the line from 0 to 1 or the line from 1 to 2 cross the X axis, depending on the sign of 1. Similarly, the line from 0 to 3 or 3 to 2 crosses the the X axis as well. If 0 and 2 are both on the same side of zero, then the line from 0-1 or 1-2 crosses dependant on the sign of 1, with similar cases for vertex 3. For each edge that crosses the X axis, you need to ensure that the edge crosses the POSITIVE X axis, which takes two multiplies and a compare. For each edge that does cross, you set a particular bit in a mask byte. At the end, if there are an odd number of bits set, you know that you are inside and return a one. Else, you can return a zero. This can be done using a table lookup. All in all quite alot simpler than trying to clip each polygon and perform all sorts of nonsense with coverage masks. Mark
robert@texas.esd.sgi.com (Robert Skinner) (07/19/90)
In article <31667@masscomp.ccur.com>, mark@masscomp.ccur.com (Mark Thompson) writes: |> Reply-To: mark@calvin.westford.ccur.com (Mark Thompson) |> Organization: Concurrent Computer Corp. Westford MA. |> |> In article <10491@odin.corp.sgi.com> robert@sgi.com writes: |> > [my description of my alpha buffer and Z buffer renderers deleted] |> > |> >The two algorithms produced almost identical images. |> |> I'll bet those images weren't identical when rendering piles of |> overlaping partially transparent objects! right, I didn't bother to implement transparency, because I didn't need it, and I didn't know if I would end up using the Z buffer. The Z buffer algorithm can't do transparency. I stopped just short of stating (what I thought) was obvious. Robert Skinner robert@sgi.com "What can go wrong?" - Calvin & Hobbes
mark@calvin..westford.ccur.com (Mark Thompson) (07/20/90)
In article <10588@odin.corp.sgi.com> robert@sgi.com writes: > >In article <31667@masscomp.ccur.com>, mark@masscomp.ccur.com (Mark >Thompson) writes: >|> I'll bet those images weren't identical when rendering piles of >|> overlaping partially transparent objects! > >right, I didn't bother to implement transparency, because I didn't >need it, and I didn't know if I would end up using the Z buffer. > >The Z buffer algorithm can't do transparency. >I stopped just short of stating (what I thought) was obvious. Not necessarily true. If you generate an alpha value for each pixel as well as rgbZ, crude transparency can be implemented still using a standard Z buffer algorithm. This of course begins to fall apart when multiple transparent object overlap (because no linked list of pixel contributions have been maintained). The main reason we used an A buffer in the system I last worked on was to remove edge artifacts on abutting antialiased polygons (using alpha lets the background color seep through the 'cracks'). I'm still surprised that your Z buffer was slower. +--------------------------------------------------------------------------+ | Mark Thompson | | mark@westford.ccur.com | | ...!{decvax,uunet}!masscomp!mark Designing high performance graphics | | (508)392-2480 engines today for a better tomorrow. | +------------------------------------------------------------------------- +
robert@texas.esd.sgi.com (Robert Skinner) (07/21/90)
In article <31673@masscomp.ccur.com>, mark@calvin..westford.ccur.com (Mark Thompson) writes: |> In article <10588@odin.corp.sgi.com> I write: |> > |> >The Z buffer algorithm can't do transparency. I hesitated before making such an absolute statement, because I know that people are constantly improving things. |> |> Not necessarily true. If you generate an alpha value for each pixel |> as well as rgbZ, crude transparency can be implemented still using |> a standard Z buffer algorithm. This of course begins to fall apart |> when multiple transparent object overlap (because no linked list |> of pixel contributions have been maintained). ignoring the multiple overlapping transparent objects, tell me what happens at a pixel when you have this case: You have rendered an opaque object, then a transparent object in front of it. I can see how you calculate the correct color at this point. Now you render another opaque object behind the transparent one, you have one of two cases: (1) The second opaque object is behind the the very first one, so its obscured. The pixel and Z values don't change. But how do you know this without saving an additional Z value for the first obscured object. (2) The second opaque object is between the transparent one and the opaque one. To compute the correct value of the pixel, you have to recover the original color of the transparent object, so you have to save its original color somewhere too. I just can't see that this works without doing one or more of the following: A: render objects back-to-front B: save more information at each pixel C: oops, I could have sworn I thought of a third 8^) Doing A eliminates the render-any-number-of-primitives-in-any-order advantage of the Z buffer. Doing B to save just one value doubles the amount of memory the Z buffer takes, which is already considerable. If you save much more information, it starts to look like the alpha buffer. I would be interested in any references you might have on doing transparency with the Z buffer. |> The main reason we used |> an A buffer in the system I last worked on was to remove edge artifacts |> on abutting antialiased polygons (using alpha lets the background |> color seep through the 'cracks'). you *want* the color to seep through the cracks? |> I'm still surprised that your Z buffer |> was slower. I've gotten a description of an algorithm that looks faster, but it will probably be some time before I can look into it or try it. (Who knows, maybe I implemented a really fast alpha buffer, and I didn't realize how fast it really was.) Robert Skinner robert@sgi.com One pill makes you larger, and one pill makes you small, and the ones that mother gives you don't do anything at all. Go ask Alice when she's ten feet tall. -- Jefferson Airplane
cdshaw@cs.UAlberta.CA (Chris Shaw) (07/21/90)
In article <10673@odin.corp.sgi.com> robert@sgi.com writes: >In article mark@calvin..westford.ccur.com (Mark Thompson) writes: >|> In article <10588@odin.corp.sgi.com> I write: >|> >The Z buffer algorithm can't do transparency. >I hesitated before making such an absolute statement, because I know >that people are constantly improving things. Well, Z-Buffer is Z-Buffer. Z-Buffer with an Alpha channel is Duff's Alpha-compositing. Or something other than Z-buffer. >..ignoring the multiple overlapping transparent objects, tell me what >happens at a pixel when you have this case: You have rendered an opaque >object, then a transparent object in front of it. I can see how you calculate >the correct color at this point. Now you render another opaque object >behind the transparent one, you have one of two cases: > >(1) The second opaque object is behind the the very first one, No problem. Looks fine. >(2) The second opaque object is between the transparent one and the opaque one You can't beat this without extra storage. A-buffer uses a data structure in mainstore to solve this. When all first-pass rendering is done, you run through each pixel list nearest-to-farthest, adding colour and clipping area. Fournier's Ultracomputer algorithm just takes the top two contributions. Weinberg's pipeline architecture does something similar to A-buffer. Duff's algorithm trades spatial accuracy (no pixel mask) for transparency, but the fact remains that to get it right, you have to sort in depth. Fortunately, the stuff being sorted can be *objects* as opposed to *pixels*, so the sorting task is has a much smaller N in the O(N) sense. One of Prusiceiwicz's students at U of Regina came up with an algorithm that combines A-Buffer and Compositing, so you have a mask AND and an alpha channel. >I just can't see that this works without doing one or more of the >following: > A: render objects back-to-front > B: save more information at each pixel C: Punt. Ignore the problem, push it upstairs. >Doing A eliminates the render-any-number-of-primitives-in-any-order >advantage of the Z buffer. Doing B to save just one value doubles the >amount of memory the Z buffer takes, which is already considerable. >If you save much more information, it starts to look like the alpha buffer. Well, doing A means you may sort 100's of polygons as a single entity. Much better than sorting the polygons. >|> The main reason we used >|> an A buffer in the system I last worked on was to remove edge artifacts >|> on abutting antialiased polygons (using alpha lets the background >|> color seep through the 'cracks'). You can fix this by rendering common edges aliased. If you have a polygonal mesh, you know that the inner edges are each shared by two polygons, so you can treat these separately, and render the inner edges aliased, with full coverage. It's an extra check per edge, but the calculation per edge may be less. >Robert Skinner robert@sgi.com -- Chris Shaw University of Alberta cdshaw@cs.UAlberta.ca Now with new, minty Internet flavour! CatchPhrase: Bogus as HELL !
gg10@prism.gatech.EDU (Gregory L. Galloway) (07/22/90)
In article <10491@odin.corp.sgi.com>, robert@texas.esd.sgi.com (Robert Skinner) writes: > I implemented a renderer with a Reyes-like front end, and two scan > conversion back ends: scanline Z buffer with 4x4 or 8x8 > stochastically jittered subsamples, an alpha buffer with 4x4 or > 8x8 masks. > > Robert Skinner > robert@sgi.com Cook, et al., said that the Reyes system worked really well when splitting patches, but not polygons. How about just simple triangles? Has anyone tried writing a rendering system based on Reyes which just uses simple midpoint subdivision (as in fractals but w/o the random displacement)? I'm curious to know how the system performs compared to a simple Z-buffer w/ straight scan-conversion and no stochastic sampling. Thanks in advance, Greg Galloway gg10@prism.gatech.edu
mark@calvin..westford.ccur.com (Mark Thompson) (07/23/90)
In article <1990Jul20.231437.22325@cs.UAlberta.CA> cdshaw@cs.UAlberta.CA (Chris Shaw) writes: >In article <10673@odin.corp.sgi.com> robert@sgi.com writes: >>In article mark@calvin..westford.ccur.com (Mark Thompson) writes: >>|> In article <10588@odin.corp.sgi.com> I write: >>..ignoring the multiple overlapping transparent objects, tell me what >>happens at a pixel when you have this case: You have rendered an opaque >>object, then a transparent object in front of it. The second opaque object >>is between the transparent one and the opaque one > >You can't beat this without extra storage. One alternative is to separate your transparent objects from your opaque ones and render them last. This is generally much less work than sorting. >One of Prusiceiwicz's students at U of Regina came up with an algorithm >that combines A-Buffer and Compositing, so you have a mask AND and an alpha >channel. We also used both an alpha channel and A-Buffer. It allowed for crude transparency when the A-Buffer was turned off and the alpha provided the necessary info to extrernally blend to a separate image/video source. >>|> The main reason we used >>|> an A buffer in the system I last worked on was to remove edge artifacts >>|> on abutting antialiased polygons (using alpha lets the background >>|> color seep through the 'cracks'). >You can fix this by rendering common edges aliased. If you have a >polygonal mesh, you know that the inner edges are each shared by two polygons, >so you can treat these separately, and render the inner edges aliased, with >full coverage. It's an extra check per edge, but the calculation per edge >may be less. In fact we provided edge flags for selective antialiasing. The problem arises however when the shared edge becomes the 'silohette edge' (the edge of the viewable portion of the object). It is then necessary to atialias an edge you normally would not have. I imagine other checks would be feasible to detect this case also but probably at a cost that exceeds that of the A-Buffer. Any ideas? +--------------------------------------------------------------------------+ | Mark Thompson | | mark@westford.ccur.com | | ...!{decvax,uunet}!masscomp!mark Designing high performance graphics | | (508)392-2480 engines today for a better tomorrow. | +------------------------------------------------------------------------- +
robert@texas.esd.sgi.com (Robert Skinner) (07/24/90)
In article <11657@hydra.gatech.EDU>, gg10@prism.gatech.EDU (Gregory L. Galloway) writes: |> In article <10491@odin.corp.sgi.com>, robert@texas.esd.sgi.com (Robert Skinner) writes: |> > I implemented a renderer with a Reyes-like front end, and two scan |> > conversion back ends: scanline Z buffer with 4x4 or 8x8 |> > stochastically jittered subsamples, an alpha buffer with 4x4 or |> > 8x8 masks. |> > |> > Robert Skinner |> > robert@sgi.com |> |> Cook, et al., said that the Reyes system worked really well when splitting |> patches, but not polygons. that's not how I interpreted the statement: "Polygons in general do not have a natural coordinate system for dicing. This is fine in our case, because bicubic patches are our most common primitive, and we hardly ever use polygons." I think the first sentence refers to polygons with 5 or more vertices, in which case I agree. How do you split or dice a pentagon? I believe the second sentence implies that Pixar almost always uses more sophisticated primitives than polygons. I also got the *impression* that polygons didn't render much faster than bicubic patches, so why bother with polygon limitations? |> How about just simple triangles? Has anyone |> tried writing a rendering system based on Reyes which just uses simple |> midpoint subdivision (as in fractals but w/o the random displacement)? that is basically what I did. I rendered triangles and quadrilaterals and did simple midpoint subdivision (I didn't do anything special for bow-tie quads.) |> I'm |> curious to know how the system performs compared to a simple Z-buffer w/ |> straight scan-conversion and no stochastic sampling. well, you are going to pay the price for the splitting and dicing that Reyes does that a plain vanilla Z-buffer doesn't. In addition, the the straight scan-conversion algorithm could use coherency effectively on large polygons. Reyes micropolygons are much smaller, so you would lose some there too. I think Reyes is a beautiful system. Its clean and simple. I plan on re-implementing my Reyes-like renderer in C++ to take advantage of the (sort of) object-oriented style. But I think it sacrifices some speed for the great God of realism and the potential for parallelism. I think the trade-off is worth it. |> |> Thanks in advance, |> |> Greg Galloway |> gg10@prism.gatech.edu Robert Skinner robert@sgi.com You will encounter several species of small, furry animals, gathered together in a cave and grooving with a pict
coy@ssc-vax.UUCP (Stephen B Coy) (07/24/90)
In article <10673@odin.corp.sgi.com>, robert@texas.esd.sgi.com (Robert Skinner) writes: > A: render objects back-to-front > B: save more information at each pixel > C: oops, I could have sworn I thought of a third 8^) > > Doing A eliminates the render-any-number-of-primitives-in-any-order > advantage of the Z buffer. Doing B to save just one value doubles the > amount of memory the Z buffer takes, which is already considerable. > If you save much more information, it starts to look like the alpha > buffer. A compromise can be reached by rendering all the opaque objects as you get them but saving the transparent objects for last. The transparent objects can then be sorted and rendered back to front. This works best with scenes that have relatively few transparent objects. > Robert Skinner > robert@sgi.com Stephen Coy uw-beaver!ssc-vax!coy