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.
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.
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.
DAC
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.
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.
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).
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 snipped-for-privacy@pacbell.net where "0_0_0_0_" = "martineu"
Well, yes. I have to process half a billion pixels per second. Kinda hard to do with a microprocessor.
going
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.
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.
of
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"
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.
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.
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?
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" 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?
>
>
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 snipped-for-privacy@pacbell.net where "0_0_0_0_" = "martineu"
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.
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 =MINY) and (Y
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).
Hello Martin, 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. For curve and circle, I think a sin()/cos() LUT (or coregen) is needed, no big deal isn't it?
That's quite an old product. What is the application?
Were you self employed or working for someone else? I assume someone else.
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.
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.