Graphics rendering

I know about the various algorithms to draw lines, circles, etc.  All of
these pretty much rely on painting onto a frame buffer that is later used to
scan out to a CRT.

Does anyone know of any algorithms to draw primitives that work without the
intermediate frame buffer step.  In other words, the algorithm's input would
be the current x,y pixel being painted on the screen and the desired shape's
parameters.  Horizontal and vertical lines (and rectangles), of course, are
easy.  But, how do you do curves or diagonal lines?

It seems to me that you'd take y and solve for x, which could produce
multiple results (say, a line near 0 degrees).  You'd have to save the
results for that y coordinate in a temporary buffer that would then be used
to compare to x.  That's as simple as I can come up with.


-- 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Martin Euredjian

To send private email:
0_0_0_0_@pacbell.net
where
"0_0_0_0_"  =  "martineu"

Your comments after your question do not make sense to me.

Usaually a frame buffer is where you render. And then it goes through a DAC
and several video timing control units and reaches a CRT via a VGA or 13w3
connector.

Bypassing this path means a direct electron beam control on CRT. Yeah, you
can do anything if you can control that beam.

---Bob
"Martin Euredjian" <0_0_0_0_@pacbell.net> wrote in message
news:XPBcb.6059$ju4.2633@newssvr27.news.prodigy.com...
> I know about the various algorithms to draw lines, circles, etc.  All of
> these pretty much rely on painting onto a frame buffer that is later used
to
> scan out to a CRT.
>
> Does anyone know of any algorithms to draw primitives that work without
the
> intermediate frame buffer step.  In other words, the algorithm's input
would
> be the current x,y pixel being painted on the screen and the desired
shape's
> parameters.  Horizontal and vertical lines (and rectangles), of course,
are
> easy.  But, how do you do curves or diagonal lines?
>
> It seems to me that you'd take y and solve for x, which could produce
> multiple results (say, a line near 0 degrees).  You'd have to save the
> results for that y coordinate in a temporary buffer that would then be
used
> to compare to x.  That's as simple as I can come up with.
>
>
> --
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> Martin Euredjian
>
> To send private email:
> 0_0_0_0_@pacbell.net
> where
> "0_0_0_0_"  =  "martineu"
>
>

On Fri, 26 Sep 2003 04:53:29 GMT, "Bob Feng" <yi.feng@sbcglobal.net>
wrote:

>Your comments after your question do not make sense to me.
>
>Usaually a frame buffer is where you render. And then it goes through a DAC
>and several video timing control units and reaches a CRT via a VGA or 13w3
>connector.
>
>Bypassing this path means a direct electron beam control on CRT. Yeah, you
>can do anything if you can control that beam.

ISTR that one of the early personal computers, perhaps the Sinclair
ZX81, generated video on the fly in software.  This was done in groups
of eight pixels with an external eight bit shift register (& I think
there was an external character generator rom as well).
This meant that the software had to render a byte of display every two
microseconds or so.

Regards,
Allan.

"Bob Feng" wrote:
> Your comments after your question do not make sense to me.

You are thinking computers.  I'm thinking video.

Here's one possible scenario.  You are required to overlay graphics
(primitives: lines, circles, etc.) and text onto an incoming video feed,
which is then output in the same format.  The allowable input to output
delay is in the order of just a few clocks --if that much at all-- not
frames, not lines, a few clocks at best.

Frame buffers are out of the question, of course.  In addition to this, due
to cost constraints, you are not allowed to have rendering memory for the
graphics overlay.  You, therefore, must render text and graphics on the fly,
in real time, as the signal flows through.

Text and horizontal/vertical lines are pretty easy to deal with.  You start
getting into circles and rotated lines or polygons and it gets interesting
real fast.  In contrast to this, rendering these primitives to a frame
buffer (in a "traditional" computer-type application) is a no-brainer.

> Usaually a frame buffer is where you render. And then it goes through a
DAC
> and several video timing control units and reaches a CRT via a VGA or 13w3
> connector.

So, in the above context, nothing goes through a DAC.  The video feed
(assume analog) simply goes through some analog switches that, under FPGA
control, select, on a pixel-by-pixel basis, from among the incoming video
signal and a set of pre-established analog values (say white, to keep it
simple).


Hope this example clarifies it for you.

-- 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Martin Euredjian

To send private email:
0_0_0_0_@pacbell.net
where
"0_0_0_0_"  =  "martineu"

You've got quite a set of challenging constraints there.  So you're saying
an FPGA is cheaper than using a frame buffer and a micro-controller?
Another thing to think about is you'll need memory for each drawing
primitive in your overlay graphics, which might be a problem if you're going
to have a lot of primitives.

Unfortunately I've never tinkered with analog video signals, so I've got no
real advice.  By the way, how are you planning to sync to the incoming video
signal?

Well if you pull this off, it'll be quite impressive.  Please let us know of
your progress.


Regards,
Vinh

On Fri, 26 Sep 2003 07:15:44 GMT, "Martin Euredjian"
<0_0_0_0_@pacbell.net> wrote:

>"Bob Feng" wrote:
>> Your comments after your question do not make sense to me.
>
>You are thinking computers.  I'm thinking video.
>
>Here's one possible scenario.  You are required to overlay graphics
>(primitives: lines, circles, etc.) and text onto an incoming video feed,
>which is then output in the same format.  The allowable input to output
>delay is in the order of just a few clocks --if that much at all-- not
>frames, not lines, a few clocks at best.
>

>Frame buffers are out of the question, of course.  

I don't see how this follows from your constraints.

You say that the input to output video delay is at most a few clocks,
however you don't indicate that this constraint applies to the
overlay, e.g. the overlay could come from a frame buffer and then be
combined with the incoming video using some low latency method (either
digital or analog, using e.g. the analog switch method you mentioned).
You would need to genlock the FPGA generated video to the incoming
video, but that's not too hard.

>In addition to this, due
>to cost constraints, you are not allowed to have rendering memory for the
>graphics overlay.  You, therefore, must render text and graphics on the fly,
>in real time, as the signal flows through.

I would expect that the cost of a cheap FPGA + cheap memory + simple
design would be much less than the cost of a larger FPGA + complex
design.
(Actually, I think the cost of the ram will be less than the cost of
fitting the heatsink you'll need if you don't have a ram. :)

IOW, due to cost constraints, you should have rendering memory for the
graphics overlay.  Of course, you'll need to do a detailed costing to
be sure, but I'd be surprised if the version with ram doesn't end up
being cheaper and get to market sooner.

Note that larger FPGAs may be able to hold the frame buffer in
internal ram (but this depends on your resolution and pixel depth).

Regards,
Allan.

I guess I'm doing a lousy job of explaining what I'm looking for.

The example I provided is hypothetical.  Of course a frame buffer approach
would be preferred and not too expensive to implement.  No question about
it.  That's a no brainer.   I know how to do that (Bresenham).  In fact, I
am doing that on a current project.  But, that's not what I'm looking for.

I'm looking for are algorithms that can render graphic primitives from real
time screen x,y counter data (as well as the corresponding primitive
parameters).

Example:  Draw a line, 1 pixel wide, at a 32 degree angle, from screen edge
to screen edge.

The input data would be real-time screen x and y coordinates as the pixels
are being painted on screen.  On a clock-by-clock basis you get to decide
whether or not the pixel in question should be video or a white dot for your
line.

If this were a vertical or horizontal line (or 45 degrees, actually) it's a
simple comparison:

Vertical line:   if x is equal to desired x position, light the pixel
Horizontal line: if y is equal to the desired y position, light the pixel
Diagonal line:   if x and y are equal to a dedicated line x,y counter
values, light the pixel.

Line length is easily handled by means of limit registers.

All of this happens in real time, without using any frame buffers whatsoever
and with relatively minimal hardware resources (very small FPGA will do the
job nicely).

You could probably do arbitrary-angle diagonal lines in real time by simply
having an algoritm increment/decrement a set of line x,y counters.  Inputs
would be screen pixel x,y coordinates and line parameters.  That's one
algorithm I'm interested in learning about.  I'm working on my own, but if
there's something out there I should consider I don't mind stopping wheel
re-invention cold in its tracks.

Drawing circular arcs might take a similar approach, but it would be a bit
(or a lot) more complex.  Maybe a LUT would be used to translate the graphic
primitive's x,y counters into a circular arc.  Of course, for a circle you
have to deal with two or more points per scan line.

Things get a bit more interesting if you need to add width to the graphic
primitives.

I hope I did a better job on this post.


-- 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Martin Euredjian

To send private email:
0_0_0_0_@pacbell.net
where
"0_0_0_0_"  =  "martineu"





"Allan Herriman" <allan.herriman.hates.spam@ctam.com.au.invalid> wrote in
message news:av28nv4njnt0ps2c23qoipe2nm1s5s98c9@4ax.com...
> On Fri, 26 Sep 2003 07:15:44 GMT, "Martin Euredjian"
> <0_0_0_0_@pacbell.net> wrote:
>
> >"Bob Feng" wrote:
> >> Your comments after your question do not make sense to me.
> >
> >You are thinking computers.  I'm thinking video.
> >
> >Here's one possible scenario.  You are required to overlay graphics
> >(primitives: lines, circles, etc.) and text onto an incoming video feed,
> >which is then output in the same format.  The allowable input to output
> >delay is in the order of just a few clocks --if that much at all-- not
> >frames, not lines, a few clocks at best.
> >
>
> >Frame buffers are out of the question, of course.
>
> I don't see how this follows from your constraints.
>
> You say that the input to output video delay is at most a few clocks,
> however you don't indicate that this constraint applies to the
> overlay, e.g. the overlay could come from a frame buffer and then be
> combined with the incoming video using some low latency method (either
> digital or analog, using e.g. the analog switch method you mentioned).
> You would need to genlock the FPGA generated video to the incoming
> video, but that's not too hard.
>
> >In addition to this, due
> >to cost constraints, you are not allowed to have rendering memory for the
> >graphics overlay.  You, therefore, must render text and graphics on the
fly,
> >in real time, as the signal flows through.
>
> I would expect that the cost of a cheap FPGA + cheap memory + simple
> design would be much less than the cost of a larger FPGA + complex
> design.
> (Actually, I think the cost of the ram will be less than the cost of
> fitting the heatsink you'll need if you don't have a ram. :)
>
> IOW, due to cost constraints, you should have rendering memory for the
> graphics overlay.  Of course, you'll need to do a detailed costing to
> be sure, but I'd be surprised if the version with ram doesn't end up
> being cheaper and get to market sooner.
>
> Note that larger FPGAs may be able to hold the frame buffer in
> internal ram (but this depends on your resolution and pixel depth).
>
> Regards,
> Allan.

"Vinh Pham" wrote:

> You've got quite a set of challenging constraints there.  So you're saying
> an FPGA is cheaper than using a frame buffer and a micro-controller?

Well, yes.  I have to process half a billion pixels per second.  Kinda hard
to do with a microprocessor.

> Another thing to think about is you'll need memory for each drawing
> primitive in your overlay graphics, which might be a problem if you're
going
> to have a lot of primitives.

I'm looking for an approach that would essentially evaluate equations for
these primitives in real time.  Therefore, no storage other than a few
registes and counters would be required.

It's relatively easy if you go to first principles, but probably not very
efficient hardware-wise.  I mean, look at Bresenham when compared to
evaluating the equation of a line in real time.

> By the way, how are you planning to sync to the incoming video
> signal?

That's easy.  We call it "genlock", for "(sync) generator lock".  A PLL does
it.  In the old days you had to design your own.  Today there are many very
nice canned solutions.

> Well if you pull this off, it'll be quite impressive.  Please let us know
of
> your progress.

It's nothing to warrant being impressed.  Seriously.  It's just a matter of
implementation.


-- 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Martin Euredjian

To send private email:
0_0_0_0_@pacbell.net
where
"0_0_0_0_"  =  "martineu"

Martin Euredjian wrote:
> "Bob Feng" wrote:
> 
>>Your comments after your question do not make sense to me.
> 
> 
> You are thinking computers.  I'm thinking video.
> 
> Here's one possible scenario.  You are required to overlay graphics
> (primitives: lines, circles, etc.) and text onto an incoming video feed,
> which is then output in the same format.  The allowable input to output
> delay is in the order of just a few clocks --if that much at all-- not
> frames, not lines, a few clocks at best.
> 
> Frame buffers are out of the question, of course.  In addition to this, due
> to cost constraints, you are not allowed to have rendering memory for the
> graphics overlay.  You, therefore, must render text and graphics on the fly,
> in real time, as the signal flows through.
> 
> Text and horizontal/vertical lines are pretty easy to deal with.  You start
> getting into circles and rotated lines or polygons and it gets interesting
> real fast.  In contrast to this, rendering these primitives to a frame
> buffer (in a "traditional" computer-type application) is a no-brainer.
> 
> 
>>Usaually a frame buffer is where you render. And then it goes through a
> 
> DAC
> 
>>and several video timing control units and reaches a CRT via a VGA or 13w3
>>connector.
> 
> 
> So, in the above context, nothing goes through a DAC.  The video feed
> (assume analog) simply goes through some analog switches that, under FPGA
> control, select, on a pixel-by-pixel basis, from among the incoming video
> signal and a set of pre-established analog values (say white, to keep it
> simple).
> 
> 
> Hope this example clarifies it for you.
> 

A frame buffer is simply a huge LUT(sort of) in which every pixel is 
corresponding to the one on the screen. The reason to have it is simply 
because of the huge effort to generate them in the front end.

Bypassing the frame buffer means you need to have some fast algorithm to 
do some fast drawing. Correct?

If you only do lines or individual pixels, I agree with you they are 
simple. You may also get away with circles or ovels. But for real 
graphics(I am talking about geometry+rasterization+texture), you have no 
way to do so.

Circles and Ovels may be done via LUT. But your VTC design in FPGA maybe 
chanllenge. It should be fun though.

---Bob

A frame buffer is simply a huge LUT(sort of) in which every pixel is
corresponding to the one on the screen. The reason to have it is simply
because of the huge effort to generate them in the front end.

Bypassing the frame buffer means you need to have some fast algorithm to do
some fast drawing. Correct?

If you only do lines or individual pixels, I agree with you they are simple.
You may also get away with circles or ovels. But for real graphics(I am
talking about geometry+rasterization+texture), you have no way to do so.

Circles and Ovels may be done via LUT. But your VTC design in FPGA maybe
chanllenge. It should be fun though.

---Bob

"Martin Euredjian" <0_0_0_0_@pacbell.net> wrote in message
news:AIRcb.6331$0K3.502@newssvr27.news.prodigy.com...
> "Bob Feng" wrote:
> > Your comments after your question do not make sense to me.
>
> You are thinking computers.  I'm thinking video.
>
> Here's one possible scenario.  You are required to overlay graphics
> (primitives: lines, circles, etc.) and text onto an incoming video feed,
> which is then output in the same format.  The allowable input to output
> delay is in the order of just a few clocks --if that much at all-- not
> frames, not lines, a few clocks at best.
>
> Frame buffers are out of the question, of course.  In addition to this,
due
> to cost constraints, you are not allowed to have rendering memory for the
> graphics overlay.  You, therefore, must render text and graphics on the
fly,
> in real time, as the signal flows through.
>
> Text and horizontal/vertical lines are pretty easy to deal with.  You
start
> getting into circles and rotated lines or polygons and it gets interesting
> real fast.  In contrast to this, rendering these primitives to a frame
> buffer (in a "traditional" computer-type application) is a no-brainer.
>
> > Usaually a frame buffer is where you render. And then it goes through a
> DAC
> > and several video timing control units and reaches a CRT via a VGA or
13w3
> > connector.
>
> So, in the above context, nothing goes through a DAC.  The video feed
> (assume analog) simply goes through some analog switches that, under FPGA
> control, select, on a pixel-by-pixel basis, from among the incoming video
> signal and a set of pre-established analog values (say white, to keep it
> simple).
>
>
> Hope this example clarifies it for you.
>
> --
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> Martin Euredjian
>
> To send private email:
> 0_0_0_0_@pacbell.net
> where
> "0_0_0_0_"  =  "martineu"
>
>