Graphics rendering

[Martin Euredjian]

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"

 

[Bob Feng]

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"

 

[Allan Herriman]

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.

 

[Martin Euredjian]

"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"

 

[Vinh Pham]

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

 

[Allan Herriman]

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.

 

[Martin Euredjian]

"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"

 

[bfeng]

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

 

[Bob Feng]

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"

 

[Vinh Pham]

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.

I agree with Allan here. A simple design has the best chance of succeeding
and will probably be cheaper. It's hard to imagine memory being that cost
prohibitive. What prices do you have for your FPGA, memory, and other
components?

 

[Martin Euredjian]

Vinh,

Please re-read my original post. This isn't complicated, really. This is
NOT a question of evaluating the best hardware configuration to be used in
drawing lines/circles on screen. It is one of the most basic engineering
concepts: given a constraint, look for a solution.

The constraint here is simple: No frame buffering. Only a few clocks's
delay allowed. Simple drawing primitives: lines, circles, rectangles,
triangles. Nothing else. No shading or lighting effects, plain white pixels
would do.

Given the above, any frame buffer based solution is simply irrelevant.
Continuing to insist that a frame buffer would be a "better" approach is
missing the point. That solution is simply not an option. Cost has nothing
to do with it.

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

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



"Vinh Pham" <a@a.a> wrote in message
news:75%cb.5818$Ak3.3455@twister.socal.rr.com...

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.

I agree with Allan here. A simple design has the best chance of
succeeding
and will probably be cheaper. It's hard to imagine memory being that cost
prohibitive. What prices do you have for your FPGA, memory, and other
components?

 

[Martin Euredjian]

Only the most primitive shapes: lines, circles, rectangles, triangles
(connected lines, really). No shading, no geometry, rasterization or
texture.

I have my own algorithms that, for the most part, work well. I was just
trying to figure out if there was something interesting out there that I
should be considering. I guess this is esoteric enough that it simply isn't
out there.

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

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


"Bob Feng" <bfeng@sgi.com> wrote in message
news:bl1spf$9osjs$1@fido.engr.sgi.com...

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"

 

[Vinh Pham]

Please re-read my original post. This isn't complicated, really. This is
NOT a question of evaluating the best hardware configuration to be used in
drawing lines/circles on screen. It is one of the most basic engineering
concepts: given a constraint, look for a solution.

The constraint here is simple: No frame buffering. Only a few clocks's
delay allowed. Simple drawing primitives: lines, circles, rectangles,
triangles. Nothing else. No shading or lighting effects, plain white
pixels
would do.

Given the above, any frame buffer based solution is simply irrelevant.
Continuing to insist that a frame buffer would be a "better" approach is
missing the point. That solution is simply not an option. Cost has
nothing
to do with it.

I fear my lack of experience in video applications prevents me from seeing
your point. And history is full of examples of people saying something is
impossible until a brave soul proves them wrong. With that you have my best
wishes and I hope you succeed in your endeavors. I am sorry I cannot be of
help.

Do you have a working protype yet? If not, I hope you let us know when you
succeed at drawing a simple line on the screen and tell us about what parts
of your design were challenging and how you solved your problems.


Regards,
Vinh

 

[Peter C. Wallace]

On Thu, 25 Sep 2003 06:11:19 -0700, Martin Euredjian wrote:

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.

Diagonal lines are easy, assuming you have genlock and X and Y Pixel address
counters, just check that Y -(MX+B) = 0 and (X >=MINX) and (X <= MAXX) or
(Y >=MINY) and (Y <= MAXY)
and draw your pixel if so...

Peter Wallace

 

[Martin Euredjian]

Do you have a working protype yet?

Product. Shipping.

If not, I hope you let us know when you
succeed at drawing a simple line on the screen

I think that was back in 1978, maybe '77. Don't remember exactly.

and tell us about what parts of your design were challenging

Working 16 hours a day, seven days a week for nearly two years.

and how you solved your problems.

I finished.


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

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

 

[Jake Janovetz]

Martin-

From your constraints I still don't see why frame buffers are out of
the question (genlock devices do overlay all the time -- with frame
buffers), but for the sake of argument this basically means that you
need a hit/miss engine for every graphics primitive that exists.

It would basically be a subroutine that operates on the coordinate and
returns a boolean -- pixel on or off. But I can't see how to do this
without one engine per primitive (or multiplexing a single engine).

Jake



"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.

 

[Long Nguyen]

Hello Martin, <p>How do you do it? Must be an interesting project. In the past I had something similar, an animation video generator for digital video system test, but I deal with lines, text, and rectangle only. <p>For curve and circle, I think a sin()/cos() LUT (or coregen) is <BR>
needed, no big deal isn't it?

 

[Vinh Pham]

Do you have a working protype yet?

Product. Shipping.

Do you have a URL to that product?

If not, I hope you let us know when you
succeed at drawing a simple line on the screen

I think that was back in 1978, maybe '77. Don't remember exactly.

That's quite an old product. What is the application?

and tell us about what parts of your design were challenging

Working 16 hours a day, seven days a week for nearly two years.

Were you self employed or working for someone else? I assume someone else.

and how you solved your problems.

I finished.

So for some ~20 years your product was fine with rectangles and now needs to
be upgraded to diagonals and curves? What a nice, slow moving market you
opperate in.

In keeping with the theme of poor communication skills:

After giving up figuring out how to do it without a frame buffer, the mental
block lifted while I was driving. The 45 degree diagonals are pretty easy
to generate. Given a starting point you can easily draw a line SW (south
west), S, SE, or E. With that you have the basic building blocks to build a
diagonal line of arbitrary angle. Working out the algorithm for that will
take a bit more work, but hopefully will only involve accumilating an
increment with a fractional part. I'm guessing a curve won't be so bad
because it's merely a diagonal line whose slope changes over time. If the
slope change is a constant, you have an arc of a circle. If the slope
change varies over time also, then you have an arc of a oval or something
like that. To draw a full circle you can break it into two curves.

But unfortunately there's one gotcha. I can't figure out how to draw a
diagonal line that lies between W and SW, which is a shame since the idea
I'm playing with seems pretty elegant for the time being. It could get ugly
fast.


Regards,
Vinh

 

[Martin Euredjian]

I think that was back in 1978, maybe '77. Don't remember exactly.

That's quite an old product. What is the application?

....

So for some ~20 years your product was fine with rectangles and now needs
to
be upgraded to diagonals and curves? What a nice, slow moving market you
opperate in.

We are squarely in the real of commedy at this point. Thanks for a good
laugh. I hope that was your intention.


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

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

 

[Martin Euredjian]

The problem is not insurmountable. LUT's are one possible solution. And
some of these solutions consume quite a bit of FPGA resources and might be
quite complex.

The original reason for my post (which got lost pretty quickly) is to sort
of do a survey of available (or well-known) techniques. Based on the
response, I gather that this is so rare that very little, if any publicly
available literature might exist.


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

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