Graphics rendering

[Hal Murray]

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

[Serious old-fart alert.]

In the old days, they made vector displays. The beam had X and Y addresses
that you could control rather than a raster scan. You could draw
individual points. To make a line, you could draw a sequence of points,
or use the line drawing hardware assist.

Typically, you fed the displa a "display list" which was just a list
of commands with an op code set like move absolute, move relative,
draw dot, draw line... subroutine call/return. ...

There were some amazing ideas discovered back then. If you like
clever tricks in this area, feed "hackmem" to google and look in
the index under "display". (HACKMEM is a collection of tricks
and hacks (in the old meaning of the word) from the PDP-6 days
at the MIT AI lab.)

Back in those days, the display technology was reasonably well matched
to the hardware for processing the display list. I don't remember
any hardware to do curves but it seems reasonable.

The CTSS machine (modified IBM 7094) at project MAC had a display
list that drew lines in 3 dimensions and did the projection to the two
dimensional screen in hardware. All you had to do for a 3D rotate
was tweak the parameters in a rotation matrix.

That technology was OK for wire stick models. If your picture got
too complicated the refresh time was slow and you got lots of flicker.
(The refresh time was the time to process the whole display list.)

I think some of the vector displays may have used electrostatic
deflection rather than magnetic.

If you think about high quality displays, it's hard to do better than
a frame buffer. You get to piggyback on the technology and economics
of TV displays.

If you don't like frame buffers, you can use an LCD displays
where the buffer is included as part of the display.


Other old display technologies without frame buffers:

Early glass TTYs stored the "picture" as ASCII (rather than raw
frame buffer bits) and did the translation to pixels on the fly.
You could get TTL chips that were ROMs for 5x7 dot matrix fonts.
Some of the address bits were the character. Some were the row
within the character that the display was processing now. It might
be fun to build a VT-100 in an FPGA.

I think Tektronix made a family of displays using storage tubes.
No frame buffer needed. Hard to turn a pixel off though. You had
to erase the screen (blink, flash) and repaint what you wanted to
remain.

--
The suespammers.org mail server is located in California. So are all my
other mailboxes. Please do not send unsolicited bulk e-mail or unsolicited
commercial e-mail to my suespammers.org address or any of my other addresses.
These are my opinions, not necessarily my employer's. I hate spam.

 

[Vinh Pham]

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

Yes I do get quite sarcastic at times don't I?

You orignally posted your question to the group expecting a straight forward
responses. I and others couldn't get past the mental block of not using a
frame buffer and were trying to convince you to do things the way we thought
it should be done.

You got frustrated (very understandable) and you quickly fired off a
scenario. I suspect what you were trying to tell us in an indirect way,
"Okay guys, I know you don't think it can be done without a frame buffer,
but let's pretend." Unfortunately within your scenario you made the
statement: "In addition to this, due to cost constraints, you are not
allowed to have rendering memory for the graphics overlay." Engineers are
so anal about little details, we often miss the main point, and like pit
bulls we latched onto the claim that memory was too expensive and started to
argue with you about that, thinking to ourselves, "Poor misguided soul, the
reason he's not using a frame buffer is because he thinks memory is too
expensive. Needless to say this increased your frustration further.

Dealing with engineers is like playing with a long piece of masking tape.
If you're not very careful a part of it will stick to you, and your
struggles to free yourself will get you into more of a mess. I know when
people misunderstand me my first response to respond quickly and in great
length, but that usually leads to more miswording and misunderstanding.

Perhaps one approach would have been to state from the outset: "I have
already built a device that overlays horizontal and verticle lines without
using a frame buffer. I'm trying to add diagonals and curves now." This
might have helped us avoid the mental block because you've "proven" it's
possible to not use a buffer. Heh of course we probably would have said,
"Well switch over to a buffer."

Well I better stop before I start getting more long winded. Anyways, just
some random thoughts on the situation. My apologies for responding to your
frustration with sarcasm, and for not reading some of your words carefully
enough, and reading others too carefully. May you have better luck in the
future.


Regards,
Vinh

 

[Vinh Pham]

LOL. Thanks for the interesting trivia Hal :_) Did you work with any of
those particular technologies?

Hey, did you hear about the progress they're making in electronic ink?
http://www.nature.com/nsu/030922/030922-10.html


--Vinh

 

[Martin Euredjian]

I worked with PDP11-34's and Tek storage displays back a few (let's leave it
at that) years ago.


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

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


"Hal Murray" <hmurray@suespammers.org> wrote in message
news:vn9qqgroj34s6d@corp.supernews.com...

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

[Serious old-fart alert.]

In the old days, they made vector displays. The beam had X and Y
addresses
that you could control rather than a raster scan. You could draw
individual points. To make a line, you could draw a sequence of points,
or use the line drawing hardware assist.

Typically, you fed the displa a "display list" which was just a list
of commands with an op code set like move absolute, move relative,
draw dot, draw line... subroutine call/return. ...

There were some amazing ideas discovered back then. If you like
clever tricks in this area, feed "hackmem" to google and look in
the index under "display". (HACKMEM is a collection of tricks
and hacks (in the old meaning of the word) from the PDP-6 days
at the MIT AI lab.)

Back in those days, the display technology was reasonably well matched
to the hardware for processing the display list. I don't remember
any hardware to do curves but it seems reasonable.

The CTSS machine (modified IBM 7094) at project MAC had a display
list that drew lines in 3 dimensions and did the projection to the two
dimensional screen in hardware. All you had to do for a 3D rotate
was tweak the parameters in a rotation matrix.

That technology was OK for wire stick models. If your picture got
too complicated the refresh time was slow and you got lots of flicker.
(The refresh time was the time to process the whole display list.)

I think some of the vector displays may have used electrostatic
deflection rather than magnetic.

If you think about high quality displays, it's hard to do better than
a frame buffer. You get to piggyback on the technology and economics
of TV displays.

If you don't like frame buffers, you can use an LCD displays
where the buffer is included as part of the display.


Other old display technologies without frame buffers:

Early glass TTYs stored the "picture" as ASCII (rather than raw
frame buffer bits) and did the translation to pixels on the fly.
You could get TTL chips that were ROMs for 5x7 dot matrix fonts.
Some of the address bits were the character. Some were the row
within the character that the display was processing now. It might
be fun to build a VT-100 in an FPGA.

I think Tektronix made a family of displays using storage tubes.
No frame buffer needed. Hard to turn a pixel off though. You had
to erase the screen (blink, flash) and repaint what you wanted to
remain.

--
The suespammers.org mail server is located in California. So are all my
other mailboxes. Please do not send unsolicited bulk e-mail or
unsolicited
commercial e-mail to my suespammers.org address or any of my other
addresses.
These are my opinions, not necessarily my employer's. I hate spam.

 

[Vinh Pham]

It was all there buddy.

I am bested, I concede you the field.

Dead topic. Move on. Have a great weekend.

Why thank you :_)

 

[Tim]

Martin Euredjian wrote:

I finished.

Isn't design work is like writing a book. You cannot
finish, you can only abandon.

 

[Martin Euredjian]

A good friend in aerospace tells me a that a common saying in those circles
goes something like this: "At one point you'll need to shoot the engineers
and fly the darn thing or it'll never be fininshed"


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

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


"Tim" <tim@rockylogic.com.nooospam.com> wrote in message
news:bl3k40$m5e$1$8300dec7@news.demon.co.uk...

Martin Euredjian wrote:
I finished.

Isn't design work is like writing a book. You cannot
finish, you can only abandon.

 

[Sander Vesik]

Martin Euredjian <0_0_0_0_@pacbell.net> wrote:

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

Just buy a NVIDIA GPU. It might just about be able to do it.

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.

But in the similar vein, hard AI is just a small matter of programming.

--
Sander

+++ Out of cheese error +++

 

[Roger Larsson]

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.

Use the function of the shape.

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?

For a circle:
(x - x0)^2 + (y - y0)^2 = r^2
Test for equality (or close to equality) for each pixel position (x,y)
Circle center = (x0, y0).
Circle radius = r.

Lines:
kx*x + ky*y = y0

In addition you vould need some limiter.

kx*x + ky*y = y0 when 20<x<52

I have not checked the functions, but they should be close enough.

/RogerL

--
Roger Larsson
Skellefteĺ
Sweden

 

[Jan Gray]

A simple and workable approach is to use one or more BRAMs as a LINE buffer
and a LINE Z buffer, perhaps double buffered for simplicity. Then by sorting
(and incrementally updating on the fly) your display list of graphics
primitives by Y coordinate and then by X coordinate, you can iterate over
them and render them into the line buffer. Works fine for Gouraud shaded
filled primitives like trapezoids too. (Textures will require more memory
ports, perhaps on-chip, perhaps not.)

So long as you can render a line worth of graphics faster than you shift out
the previously rendered line, you're looking good. No frame buffer, no high
bandwidth frame buffer memory, no frame buffer memory I/Os. Just pretty
raster graphics.

With a soft CPU core to do display list management, and a simple hardware
span-filler coprocessor on the interface to the line buffer, scenes of
limited complexity seem quite doable in even a rather spartan FPGA. For
more complexity and more performance, move the display list manager and span
edge DDAs to hardware.

See also my 1995 article on an FPGA-based rendering coprocessor:
http://fpgacpu.org/usenet/render.html.

Jan Gray, Gray Research LLC

 

[Martin Euredjian]

Thanks, I'll go look at your article.


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

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


"Jan Gray" <jsgray@acm.org> wrote in message
news:QwYeb.11170$RW4.4195@newsread4.news.pas.earthlink.net...

A simple and workable approach is to use one or more BRAMs as a LINE
buffer
and a LINE Z buffer, perhaps double buffered for simplicity. Then by
sorting
(and incrementally updating on the fly) your display list of graphics
primitives by Y coordinate and then by X coordinate, you can iterate over
them and render them into the line buffer. Works fine for Gouraud shaded
filled primitives like trapezoids too. (Textures will require more memory
ports, perhaps on-chip, perhaps not.)

So long as you can render a line worth of graphics faster than you shift
out
the previously rendered line, you're looking good. No frame buffer, no
high
bandwidth frame buffer memory, no frame buffer memory I/Os. Just pretty
raster graphics.

With a soft CPU core to do display list management, and a simple hardware
span-filler coprocessor on the interface to the line buffer, scenes of
limited complexity seem quite doable in even a rather spartan FPGA. For
more complexity and more performance, move the display list manager and
span
edge DDAs to hardware.

See also my 1995 article on an FPGA-based rendering coprocessor:
http://fpgacpu.org/usenet/render.html.

Jan Gray, Gray Research LLC

 

[Martin Euredjian]

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.

 

[Martin Euredjian]

"Vinh Pham" <a@a.a> wrote:

Perhaps one approach would have been to state from the outset: "I have
already built a device that overlays horizontal and verticle lines without
using a frame buffer. I'm trying to add diagonals and curves now."

Nope. The best approach would have been for you to have read the original
post carefully.

Let's review it:

<START REVIEW>

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

OK. This guy understands the whole frame buffer thing and knows those
algorithms.

Does anyone know of any algorithms to draw primitives that work
without the intermediate frame buffer step?

OK. The challenge is to find a solution that does not use a frame buffer.
Therefore, I should not bother to reply if I'm going to say that he should
use a frame buffer, 'cause he already knows how to do that. That is not
what he's looking for. He very clearly states that he is interested in
solutions that do not use a frame buffer.

Telling him that he's a dummy for not using a frame buffer would be missing
the point alltogether. This is not the sort of thing that's going to help
me pass my reading and comprehension test. I should stick to the
constraints as delineated and strongly suppress my urge to go off on a
tangent that has nothing to do with the question being asked. This, of
course, is not what I'll do 'cause I fully intend to have selective recall
of what he's asking. I'll give him the answer I want him to hear, whether
its applicable or not. I'm happy with my answer. He should be happy as
well.

<COMMENT> If you know George Carlin, that is what I imagine he would say.

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.

OK. He's also naililng down the input parameters, which are simple.

Horizontal and vertical lines (and rectangles), of course, are easy.

OK. Yes, he understands very well that pure H and V lines are not an issue.

But, how do you do curves or diagonal lines?

Aha! He's no dummy. He knows where things get messy. If I were to reply,
this is where I shoud concentrate my efforts. How do you draw curves or
diagonal lines in real time, without using an intermediate frame buffer and
with real-time pixel x,y coordintes and graphic entity parameters as your
sole input parameters?.

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

OK. He's also proposing one possible approach. However, the question he
posed earlier suggests that he's looking for alternative solutions or
commentary on what he is proposing.
<END REVIEW>

It was all there buddy.

Dead topic. Move on. Have a great weekend.

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

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