Watkins algorithm
IST
code available. Please advise or send!
* Sent from AltaVista http://www.altavista.com Where you can also find related Web Pages, Images, Audios, Videos, News, and Shopping. Smart is Beautiful
Stephen H. Westin
> I need to get the best Watkins algorithm implemented in C
> code available. Please advise or send!
I would be a bit surprised to find any implementation of the Watkins
algorithm in C; by the time C became the dominant language in
graphics, the Watkins algorithm had faded from favor.
The only implementation of which I know is that in MOVIE.BYU, but a
quick Web search didn't turn up any source code. No great loss; the
implementation started out arcane, as it was designed as a functional
simulator for special-purpose hardware and FORTRAN doesn't really
express complex data sturctures well. It got worse over the years as a
series of graduate students added capabilities (transparency, shadows,
etc.).
The real reason that MOVIE.BYU doesn't exist any more is that it
basically didn't do anything you couldn't get out of, say, OpenGL. We
deal at a different level of abstraction, and at different levels of
complexity. Watkins gets slow and memory-hungry as the polygon count
increases; it was designed in the days when 500 polygons was a model
of serious complexity.
--
-Stephen H. Westin
Any information or opinions in this message are mine: they do not
represent the position of Cornell University or any of its sponsors.
Jack Mott
Stephen H. Westin <westin*nos...@graphics.cornell.edu> wrote in message
news:u9038n...@graphics.cornell.edu...
Stephen H. Westin
> what exactly is the Watkins algorithm? Just out of historical curiosity?
The Watkins algorithm was developed by Gary Watkins as the heart of
his Ph.D. at Utah around 1968, as I recall. I think of it as the
definitive scan-line algorithm. Here's my recollection of it:
o Go through all polygons and transform vertices to screen space.
o Break polygons into edges, bucket sorting according to the
scan line where they first appear. Store color and depth
information at each vertex.
o Loop through all scan lines in the image. Where there's a new
pair of edges, create a data structure spanning the space between them.
This includes information on X, Y, depth, and color at each end of the
span, and precomputed slopes for each. Where a pair of edges ends,
delete the associated span. This gets pretty yucky when you
allow non-convex polygons requiring special case code; you
may hit an edge event that requires the splitting of an existing span
or merging two spans rather than creation of a new one.
o Across each scan line, loop over each pixel. Resolve visibility
and shade the visible pixels. Visibility can be solved
span-to-span rather than at each pixel; this was considered a big
win in the days when you had hundreds of polygons (meaning dozens
of spans on a particular scan line), but hundreds of thousands of
pixels.
Watkins implemented it in hardware at Utah and then hired in at Evans
& Sutherland to build flight simulators. There are some nice things
about the algorithm; for example, it can be extended for analytical
edge antialiasing. But it's basically only of historical interest
these days.
<snip>
Samuel Paik
> I would be a bit surprised to find any implementation of the Watkins
> algorithm in C; by the time C became the dominant language in
> graphics, the Watkins algorithm had faded from favor.
>
> The only implementation of which I know is that in MOVIE.BYU, but a
> quick Web search didn't turn up any source code. No great loss; the
> implementation started out arcane, as it was designed as a functional
> simulator for special-purpose hardware and FORTRAN doesn't really
> express complex data sturctures well. It got worse over the years as a
> series of graduate students added capabilities (transparency, shadows,
> etc.).
I worked on a renderer that started out as a Watkins-style scanline
renderer. It was originally a simulator for a hardware F-18 flight
simulator, written in Pascal, and then mechanically translated into
C about 1986 (which made it somewhat grody to work with...) Somewhere
along the way, the heart that made it a Watkins-style renderer, the
span visibility resolver, was mostly replaced with a supersampled
scanline Z-buffer.
> The real reason that MOVIE.BYU doesn't exist any more is that it
> basically didn't do anything you couldn't get out of, say, OpenGL.
"Good" transparency?
Sam
--
Samuel S. Paik | http://www.webnexus.com/users/paik/
3D and multimedia, architecture and implementation
Solyent Green is kitniyos!
Alen Ladavac
Samuel Paik <pa...@webnexus.com> wrote in message
news:384C4D95...@webnexus.com...
> "Stephen H. Westin" wrote:
> > I would be a bit surprised to find any implementation of the Watkins
> > algorithm in C; by the time C became the dominant language in
> > graphics, the Watkins algorithm had faded from favor.
hm. if i recall, watkins is now usually called 'sorted edge rasterizer'.
you can find win32 source written in c by michael abrash under 'zsort.zip'
on gdmag site.
and the good old watkins is not out of favor still. i have recently done a
good extension of the algorithm for doing cell-portal occlusion culling
which can exploit fully dynamic occluders like doors etc.
--
alen
PROF D. Rogers {EAS FAC}
A software implementation of the Watkins algorithm is described
in detail in PECG where I call it a spanning scanline algorithm.
The original algorithm, described in Gary's thesis, is optimized
for hardware. There are several very useful concepts in the
algorithm which appear in later algorithms.
I actually have several student implementations
in C from several years ago.
Dave Rogers
PECG =
Procedural Elements for Computer Graphics, 2/E
David F. Rogers
McGraw-Hill Book Co, 1997
softcover: ISBN 0-07-053548-5
Your library may have it.
There is additional information on my web page at
http://www.nar-associates.com/nar-publishing/books.html
If you have to order it, check www.amazon.com
In article <uzovnn...@graphics.cornell.edu>,
Stephen H. Westin <westin*nos...@graphics.cornell.edu> wrote:
>"Jack Mott" <jm...@rice.edu> writes:
>
>> what exactly is the Watkins algorithm? Just out of historical curiosity?
>
>The Watkins algorithm was developed by Gary Watkins as the heart of
>his Ph.D. at Utah around 1968, as I recall. I think of it as the
>definitive scan-line algorithm. Here's my recollection of it:
Mickael Pointier
It's not exactly the original Watkins algorithm,
but it follows the same principles, and have been
severly optimised by many demomakers :)
Mickael
IST a écrit dans le message <09920fb9...@usw-ex0109-066.remarq.com>...
:I need to get the best Watkins algorithm implemented in C
:code available. Please advise or send!
:
:
:* Sent from AltaVista http://www.altavista.com Where you can also find