Graphics rendering revisited

Since I was responsible for de-railling the original thread, let me be the
one to beat the horse back to life, since it has interesting potential.

The orignal question was: What algorithms can you use to generate live
video, that contains only line art (lines, rectangles, curves, circles,
etc.), if you can't use a frame buffer.

The benefit of using a frame buffer is flexibility. Namely you get random
access to any pixel on the screen. This opens up a wide range of algorithms
you can use to play the performance-area-complexity tradeoff game.

Without a frame buffer, you only have sequential access to your pixels. No
going back, no going forward. Quite Zen I suppose. Anyways, you lose access
to a lot of frame buffer algorithms, but some can still be used.

The conceptually easy ones to understand are math based algorithms, but
often they're expensive hardware wise. In the first section, I'll go over
implementation issues of the ideas that other people gave. Nothing super
complex.

The second section contains a more novel (maybe) approach based on pixel
spacing. It's conceptually harder to get a handle on, but has the potential
to require less resources. Unfortunately there are problems with the idea
that I haven't flushed out. Perhaps someone will have some ideas, or maybe
it'll inspire something better.

Oh yeah, I was too lazy to double check what I wrote, so there might be
problems. I also left things unfinished towards the end, I've got other
things to think about. Hopefully it gets the ball rolling though.

Regards,
Vinh


MATH ALGORITHMS
================

Lines
-----
There was a math based algorithm mentioned by Peter Wallace, where you use
y - (mx + c) = 0 and minx<x<maxx to decide whether to light up a pixel or
not. This algorithm works on a per-pixel basis, so it doesn't need random
access.

I like how Peter formatted the equation as y - (mx + c) = 0 rather than y =
(mx + c) since a compare against zero uses less logic than a compare against
any arbitrary number. On the other hand, y = (mx + c) might produce a design
that can be clocked faster, since you only have one adder. But Xilinx (and I
would assume the other vendors also) have pretty fast carry chains, so it
might not be an issue.

I would recommend using the form x - (my + c) = 0 instead. The reason is
because we're scanning through the pixels left-right, top-bottom. x is
always changing while y takes many clock cycles to change. Therefore you can
use a multicycle multiplier that trades off time for area savings. Also the
(my) term can be implemented with a constant-multiplier (a * K) which uses
less area than a regular multiplier (a * b).

Also because y changes slowly, it's better to use miny<y<maxy. But I guess
if you have a horizontal line, you'll need to use minx<x<maxx.

Oh yeah, (x) and (y) are integers, but (m) and (c) have a fractional part.
I'm not sure if this thinking is correct, but if we assume the resolution of
a TV screen is 512x512 (yes I know it's never that good), then (m) could be
as small as 1/512 and as large as 512, so we'd need 9 bits of integer and 9
bits of fraction (9.9). I suppose (c) would need the same thing. Cool,
that's 18-bits, just right for the dedicated multipliers in Xilinx and
Altera.

Curves
------
Instead of thinking of curves as smooth lines, you can imagine them being a
string of straight lines connected together (piece-wise linear). So
theoretically you can draw any curve "just" by varying (m) and (c) over
time. Of course the prospect of doing this inside the FPGA doesn't look
promising. You could use embedded RAMs to contain a table of these values,
but that could be a large table. Don't forget you would need a table for
each curve in your image. Also, you have to calculate those tables
somewhere. Naturally you'd use an external processor/host computer but
depending on the application, you might not have that luxary.

So that's probably a bad idea, and it might be better to use a math based
solution to curves.

Circles
-------
Roger Larsson's idea for a circle is also math based:

    (x - x0)^2 + (y - y0)^2 - r^2 = 0

We can expand this to:

    x^2 -2x0(x) + x0^2 + y^2 -2y0(y) + y0^2 - r^2 = 0

x0^2, y0^2, and r^2 are constants so they can be combined into one big
constant K:

    x^2 -2x0(x) + y^2 -2y0(y) + K = 0

(x^2 + y^2) is independent of x0,y0, and r, so it can be pre-computed into a
table K(x,y), that's can be used for all circles:

    -2x0(x) + -2y0(y) + K(x,y) + K = 0

Of course if you don't have the ram for it, you can break up K(x,y) into two
seperate, smaller tables and do K(x) + K(y). But do keep in mind that K(x,y)
can be used for all circles, so it might be a worthwhile use of RAM.

    -2y0(y) can use a multicycle-constant-multiplier while -2x0(x) would
need a pipelined-constant-multiplier.

Now if you got more ram to spare, you could take advantage of the fact
that -2x0(x) is independent of y, and vice versa for -2y0(y). Therefore you
could pre-compute them into their own tables and get:

    X0(x) + Y0(y) + K(x,y) + K = 0

Unfortunately you'd need a pair of those tables for every circle in your
image, and more importantly you'd also have to recompute them whenever your
parameters change.

So you can save some logic and improve performance if your parameters don't
change often. If they're pretty dynamic, you'll have to bite the bullet and
use up a lot of logic.

Dealing With Rational Numbers
-----------------------------
Our x and y values are integer only, but the lines and circles described by
the math formulas exist in a rational number space. I haven't given it much
thought, but you might have to be a little careful when comparing values
against zero. Close enough to zero would be more like it. But it might not
be a big problem.


PIXEL SPACING ALGORITHM
=======================

So far we've viewed things as a 2D array. If we think of things in as a 1D
vector, an alternative algorithm presents itself, though I'm not sure how
fruitful it may be in the long run.

BTW, 0 degrees = East, 90 = South, 180 = West, 270 = North.

If you drew a verticle line on the screen, and "rolled out" the pixels into
a vector, what you would see is a bunch of black pixels, evenly spaced. The
spacing would be equal to the width of the screen. Advanced apologies for
the clumsy notation.

Position of line-pixel i, p[i], is equal to:

    p[i] = p[i-1] + W

    W = width of screen

To relate the value of p to the x,y space:

    p = y*W + x
    x = p%W
    y = (p - x)/W

If you drew a 45 degrees diagonal, you would notice that the spacing was W +
1:

    p[i] = p[i-1] + W + 1

A 135 degrees diagonal would be:

    p[i] = p[i-1] + W - 1

So you would think you can draw a line of arbitrary angle simply by
following the formula:

    p[0] = starting point of line
    p[i] = p[i-1] + W + m
    m = function of x/y slope

Unfortunately you run into problems when abs(m)>1. I'll go into it later.
For now, let's assume this algorithm works perfectly for all occasions.

The nice thing about this is there's no multiplication involved, just
addition. You use a down counter and when it reaches zero, you create a
pixel and put a new value in the down counter. You'll need to take into
consideration that (m) can have a fractional part though.

Also, as I said earlier, you can think of a curve as a straight line whose
slope changes as you draw it. The nice thing here is we only have (m) to
worry about, and no (c). To create a circular arc, you'd only need to
increment (m) by a constant. The constant would control the radius of the
circle that the arc belongs to.

But alas, this algorithm doesn't work for all (m). Actually angles from 0 to
45 degrees isn't so bad. 135 to 180 is trickier. I also have a feeling it'd
be difficult to get "pretty" visual results with this.

Lot's of good stuff.  I'll have to read it later tonight.  I just wanted to
modify one assumption you made.  Resolution.  I'll be working at 4K x 2.5K
and maybe as high as 4K x 4K and 60 frames per second soon.  My current work
is at 2K x 1.5K, 60 fps though.

Here's a product I finished recently that's working at 1920 x 1200 and
60fps.
http://www.ecinemasys.com/products/display/edp100/pdf/edp100_preliminary.pdf

The design is 100% mine, electrical, board layout, mechanical, FPGA,
firmware, GUI, etc.

Some of the highlights: Two 1.485GHz inputs,  two 1.485GHz outputs,  165MHz
DVI output,  USB, lots of interesting real-time processing going on.

Yes, it has a frame buffer (four frames actually).  No, it shouldn't be used
to render graphics primitives.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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:a_2fb.40558$5z.28069@twister.socal.rr.com...
> Since I was responsible for de-railling the original thread, let me be the
> one to beat the horse back to life, since it has interesting potential.
>
> The orignal question was: What algorithms can you use to generate live
> video, that contains only line art (lines, rectangles, curves, circles,
> etc.), if you can't use a frame buffer.
>
> The benefit of using a frame buffer is flexibility. Namely you get random
> access to any pixel on the screen. This opens up a wide range of
algorithms
> you can use to play the performance-area-complexity tradeoff game.
>
> Without a frame buffer, you only have sequential access to your pixels. No
> going back, no going forward. Quite Zen I suppose. Anyways, you lose
access
> to a lot of frame buffer algorithms, but some can still be used.
>
> The conceptually easy ones to understand are math based algorithms, but
> often they're expensive hardware wise. In the first section, I'll go over
> implementation issues of the ideas that other people gave. Nothing super
> complex.
>
> The second section contains a more novel (maybe) approach based on pixel
> spacing. It's conceptually harder to get a handle on, but has the
potential
> to require less resources. Unfortunately there are problems with the idea
> that I haven't flushed out. Perhaps someone will have some ideas, or maybe
> it'll inspire something better.
>
> Oh yeah, I was too lazy to double check what I wrote, so there might be
> problems. I also left things unfinished towards the end, I've got other
> things to think about. Hopefully it gets the ball rolling though.
>
> Regards,
> Vinh
>
>
> MATH ALGORITHMS
> ================
>
> Lines
> -----
> There was a math based algorithm mentioned by Peter Wallace, where you use
> y - (mx + c) = 0 and minx<x<maxx to decide whether to light up a pixel or
> not. This algorithm works on a per-pixel basis, so it doesn't need random
> access.
>
> I like how Peter formatted the equation as y - (mx + c) = 0 rather than y
=
> (mx + c) since a compare against zero uses less logic than a compare
against
> any arbitrary number. On the other hand, y = (mx + c) might produce a
design
> that can be clocked faster, since you only have one adder. But Xilinx (and
I
> would assume the other vendors also) have pretty fast carry chains, so it
> might not be an issue.
>
> I would recommend using the form x - (my + c) = 0 instead. The reason is
> because we're scanning through the pixels left-right, top-bottom. x is
> always changing while y takes many clock cycles to change. Therefore you
can
> use a multicycle multiplier that trades off time for area savings. Also
the
> (my) term can be implemented with a constant-multiplier (a * K) which uses
> less area than a regular multiplier (a * b).
>
> Also because y changes slowly, it's better to use miny<y<maxy. But I guess
> if you have a horizontal line, you'll need to use minx<x<maxx.
>
> Oh yeah, (x) and (y) are integers, but (m) and (c) have a fractional part.
> I'm not sure if this thinking is correct, but if we assume the resolution
of
> a TV screen is 512x512 (yes I know it's never that good), then (m) could
be
> as small as 1/512 and as large as 512, so we'd need 9 bits of integer and
9
> bits of fraction (9.9). I suppose (c) would need the same thing. Cool,
> that's 18-bits, just right for the dedicated multipliers in Xilinx and
> Altera.
>
> Curves
> ------
> Instead of thinking of curves as smooth lines, you can imagine them being
a
> string of straight lines connected together (piece-wise linear). So
> theoretically you can draw any curve "just" by varying (m) and (c) over
> time. Of course the prospect of doing this inside the FPGA doesn't look
> promising. You could use embedded RAMs to contain a table of these values,
> but that could be a large table. Don't forget you would need a table for
> each curve in your image. Also, you have to calculate those tables
> somewhere. Naturally you'd use an external processor/host computer but
> depending on the application, you might not have that luxary.
>
> So that's probably a bad idea, and it might be better to use a math based
> solution to curves.
>
> Circles
> -------
> Roger Larsson's idea for a circle is also math based:
>
>     (x - x0)^2 + (y - y0)^2 - r^2 = 0
>
> We can expand this to:
>
>     x^2 -2x0(x) + x0^2 + y^2 -2y0(y) + y0^2 - r^2 = 0
>
> x0^2, y0^2, and r^2 are constants so they can be combined into one big
> constant K:
>
>     x^2 -2x0(x) + y^2 -2y0(y) + K = 0
>
> (x^2 + y^2) is independent of x0,y0, and r, so it can be pre-computed into
a
> table K(x,y), that's can be used for all circles:
>
>     -2x0(x) + -2y0(y) + K(x,y) + K = 0
>
> Of course if you don't have the ram for it, you can break up K(x,y) into
two
> seperate, smaller tables and do K(x) + K(y). But do keep in mind that
K(x,y)
> can be used for all circles, so it might be a worthwhile use of RAM.
>
>     -2y0(y) can use a multicycle-constant-multiplier while -2x0(x) would
> need a pipelined-constant-multiplier.
>
> Now if you got more ram to spare, you could take advantage of the fact
> that -2x0(x) is independent of y, and vice versa for -2y0(y). Therefore
you
> could pre-compute them into their own tables and get:
>
>     X0(x) + Y0(y) + K(x,y) + K = 0
>
> Unfortunately you'd need a pair of those tables for every circle in your
> image, and more importantly you'd also have to recompute them whenever
your
> parameters change.
>
> So you can save some logic and improve performance if your parameters
don't
> change often. If they're pretty dynamic, you'll have to bite the bullet
and
> use up a lot of logic.
>
> Dealing With Rational Numbers
> -----------------------------
> Our x and y values are integer only, but the lines and circles described
by
> the math formulas exist in a rational number space. I haven't given it
much
> thought, but you might have to be a little careful when comparing values
> against zero. Close enough to zero would be more like it. But it might not
> be a big problem.
>
>
> PIXEL SPACING ALGORITHM
> =======================
>
> So far we've viewed things as a 2D array. If we think of things in as a 1D
> vector, an alternative algorithm presents itself, though I'm not sure how
> fruitful it may be in the long run.
>
> BTW, 0 degrees = East, 90 = South, 180 = West, 270 = North.
>
> If you drew a verticle line on the screen, and "rolled out" the pixels
into
> a vector, what you would see is a bunch of black pixels, evenly spaced.
The
> spacing would be equal to the width of the screen. Advanced apologies for
> the clumsy notation.
>
> Position of line-pixel i, p[i], is equal to:
>
>     p[i] = p[i-1] + W
>
>     W = width of screen
>
> To relate the value of p to the x,y space:
>
>     p = y*W + x
>     x = p%W
>     y = (p - x)/W
>
> If you drew a 45 degrees diagonal, you would notice that the spacing was W
+
> 1:
>
>     p[i] = p[i-1] + W + 1
>
> A 135 degrees diagonal would be:
>
>     p[i] = p[i-1] + W - 1
>
> So you would think you can draw a line of arbitrary angle simply by
> following the formula:
>
>     p[0] = starting point of line
>     p[i] = p[i-1] + W + m
>     m = function of x/y slope
>
> Unfortunately you run into problems when abs(m)>1. I'll go into it later.
> For now, let's assume this algorithm works perfectly for all occasions.
>
> The nice thing about this is there's no multiplication involved, just
> addition. You use a down counter and when it reaches zero, you create a
> pixel and put a new value in the down counter. You'll need to take into
> consideration that (m) can have a fractional part though.
>
> Also, as I said earlier, you can think of a curve as a straight line whose
> slope changes as you draw it. The nice thing here is we only have (m) to
> worry about, and no (c). To create a circular arc, you'd only need to
> increment (m) by a constant. The constant would control the radius of the
> circle that the arc belongs to.
>
> But alas, this algorithm doesn't work for all (m). Actually angles from 0
to
> 45 degrees isn't so bad. 135 to 180 is trickier. I also have a feeling
it'd
> be difficult to get "pretty" visual results with this.
>
>
>

Just about the circle: <BR>
Another approach for circle drawing is using trignometry. <p>The inputs for circle drawing macro are of course the circle Center(X0,Y0), Radius R, and the real time scanning index (x,y), assume active pixel matrix is 512x512. <p>First we need to check if vertical   index is within the drawn circle by compare |y-Y0| &lt;= R, if yes then scale |y-Y0| to radius R. Let say  <BR>
yy = |y-Y0|/R.  For this we may use LUT for 1/R, L1(R) = 1/R. <p> yy = |y-Y0| * L1(R)  (1) <p>Notes that yy = sin(teta), teta is an angle in first quadrant,  <BR>
0&lt;= yy &lt;= 1 <p>Known sin(teta) one can find cos(teta) by another LUT, let say <p> L2(yy)=xx, where xx=cos(teta) <BR>
or <BR>
&nbsp;L2(|y-Y0| * L1(R)) = xx (2) <p>Notes: sin^2(teta) + cos^2(teta)=1 <p>Perform multiplying to find out <BR>
|x-X0| = R*xx <p>or <p>|x-X0| = R*L2(|y-Y0| * L1(R)) (3) <p>solve for x from (3) : <p>x = X0 +- R*L2(|y-Y0| * L1(R)) (4) <p>From equation (4), one can see x is a function of X0, Y0, R, and y.  Note that (4) can be computed during  horizontal blank time (take several clock cycles), register results, and perform another calculation... <BR>
That means for a pair of LUTs L1, L2, it can  draw more than one circle. <p><p><p><p><p><p><p><p><p>use LUT to figure out |x-X0|, where LUT imply function F(S) = C where S=sin(teta) and C = cos(teta) in the first quadrant.  <p><p><p><p>We can use RAM LUT for this function <BR>
F(S)= C, where S=sin(theta) and C=cos(theta) in the first quadrant circle.  The inputs to this circle macro function are of course the Center(X0,Y0) and Radius R.

Just about circle: <BR>
Another approach for circle drawing is using trignometry. <p>The inputs for circle drawing macro are of course the circle Center(X0,Y0), Radius R, and the real time scanning index (x,y), assume active pixel matrix is 512x512. <p>First we need to check if vertical index is within the drawn circle by compare |y-Y0| &lt;= R, if yes then scale |y-Y0| to radius R. Let say <BR>
yy = |y-Y0|/R. For this we may use LUT for 1/R, L1(R) = 1/R. <p>yy = |y-Y0| * L1(R) (1) <p>Notes that yy = sin(teta), teta is an angle in first quadrant, <BR>
0&lt;= yy &lt;= 1 <p>Known sin(teta) one can find cos(teta) by another LUT, let say <p>L2(yy)=xx, where xx=cos(teta) <BR>
or <BR>
&nbsp;L2(|y-Y0| * L1(R)) = xx (2) <p>Notes: sin^2(teta) + cos^2(teta)=1 <p>Perform multiplying to find out <BR>
|x-X0| = R*xx <p>or <p>|x-X0| = R*L2(|y-Y0| * L1(R)) (3) <p>solve for x from (3) : <p>x = X0 +- R*L2(|y-Y0| * L1(R)) (4) <p>From equation (4), one can see x is a function of X0, Y0, R, and y. Note that (4) can be computed during horizontal blank time (take several clock cycles), register results, and perform another calculation... <BR>
That means for a pair of LUTs L1, L2, it can draw more than one circle.

Vinh Pham wrote:

>The orignal question was: What algorithms can you use to generate live
>video, that contains only line art (lines, rectangles, curves, circles,
>etc.), if you can't use a frame buffer.
>
>The benefit of using a frame buffer is flexibility. Namely you get random
>access to any pixel on the screen. This opens up a wide range of algorithms
>you can use to play the performance-area-complexity tradeoff game.
>
>Without a frame buffer, you only have sequential access to your pixels. No
>going back, no going forward. Quite Zen I suppose. Anyways, you lose access
>to a lot of frame buffer algorithms, but some can still be used.
>
>  
>
I guess you are talking about raster-scan displays without a pixel to pixel
frame buffer behind it, and not about vector-drawing displays (like an
oscilloscope in X-Y mode).

Interesting theoretical enterprise, but I really don't see the point.  I 
remember quite
some years ago talking to a guy who had invested millions of $ in developing
software for Evans&Sutherland color vector displays for the drug design
industry.  I just casually threw out the comment that in 5 years the E&S 
gear
would be in the dumpster, and everybody would have switched to pixel/raster
scan systems.  They were doing stuff with up to 100,000 simulated spheres
on the screen, and he essentially told me I was so nuts that he couldn't 
even
begin to explain how impossible it would be for a frame buffer to ever 
handle
such a task.  Well, of course, all that is history now, and his company 
had to
invest a BUNDLE in converting all their software to adapt to the frame
buffer mode of doing things.

Jon

> Lot's of good stuff.  I'll have to read it later tonight.  I just wanted
to

Don't worry about it, there's nothing profound in it, I just carried away
when I start writing :_)

> modify one assumption you made.  Resolution.  I'll be working at 4K x 2.5K
> and maybe as high as 4K x 4K and 60 frames per second soon.  My current
work
> is at 2K x 1.5K, 60 fps though.

Jeeze that's quite a bit of bandwidth there.

>
http://www.ecinemasys.com/products/display/edp100/pdf/edp100_preliminary.pdf

Cool way to expand the use of a Cinema Display.  I bet HD sized CRTs are
awfully heavy and delicate.  So with your product someone could view live HD
footage from inside a small helecoptor, for instance?  Looks like it'll
change the way people think of and us HD displays.  Pretty cool to make a
product that can affect the way people do their work.

> The design is 100% mine, electrical, board layout, mechanical, FPGA,
> firmware, GUI, etc.

Must be fun having a hand in every aspect of a product, it's your baby.
Like the olden days of hand crafted cars, before Ford turned it into an
assembly line.

> Some of the highlights: Two 1.485GHz inputs,  two 1.485GHz outputs,
165MHz
> DVI output,  USB, lots of interesting real-time processing going on.

Is PCB layout particulary challenging?  Heh everything probably is when
you're processing that much data.  Doesn't seem like it needs much
ventilation, so heat's not much of a problem?

:> Yes, it has a frame buffer (four frames actually).  No, it shouldn't be
used
> to render graphics primitives.

But...but...;_)

> Interesting theoretical enterprise, but I really don't see the point.

Someone just had a rare situation where they couldn't use a frame buffer.
You can think of it as an intellectual exercise :_)

> I remember quite some years ago talking to a guy who had invested millions
of $ in developing

Hahaha no wonder he refused to believe you.  Sort of like when you buy a
crappy product, but you make yourself believe it's great, because of all the
money you spent on it.

Did E&S's vector display draw only outlines of spheres, or shaded?  Shading
with x-y vectors doesn't sound too fun.

What do you think was the main reason why people switched to pixel/raster?
Simplicity?  Scales better?

Thanks for the interesting anecdote Jon

"Jon Elson" <jmelson@artsci.wustl.edu> wrote:

> I guess you are talking about raster-scan displays without a pixel to
pixel
> frame buffer behind it, and not about vector-drawing displays (like an
> oscilloscope in X-Y mode).
>
> Interesting theoretical enterprise, but I really don't see the point.

And you wouldn't outside of a contextual reference frame that allowed you to
understand where/why this might be important.  It's a very narrow field of
application.  Not mainstream at all.


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

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

Martin,

Looked at the spec's of the EDP100. Looking very nice indeed.. So to convert
the HDSDI into DVI you would need a de�nterlacer and a frame rate converter.
Guess that's where your 4 framestores come from. If you don't mind, I'd like
to know how many fieldstores are actually used in the deinterlacer.
Normally, you'd need two stores for doing the frame rate conversion (double
buffered). So that would leave you with 2 stores left to do deinterlacing
which allows for some nice 3field algorithms.

sorry to go off topic with this.. I'm just curious since I'm roughly in the
same business.

regards,
Jan

"Martin Euredjian" <0_0_0_0_@pacbell.net> schreef in bericht
news:d_3fb.8955$N67.802@newssvr27.news.prodigy.com...
> Lot's of good stuff.  I'll have to read it later tonight.  I just wanted
to
> modify one assumption you made.  Resolution.  I'll be working at 4K x 2.5K
> and maybe as high as 4K x 4K and 60 frames per second soon.  My current
work
> is at 2K x 1.5K, 60 fps though.
>
> Here's a product I finished recently that's working at 1920 x 1200 and
> 60fps.
>
http://www.ecinemasys.com/products/display/edp100/pdf/edp100_preliminary.pdf
>
> The design is 100% mine, electrical, board layout, mechanical, FPGA,
> firmware, GUI, etc.
>
> Some of the highlights: Two 1.485GHz inputs,  two 1.485GHz outputs,
165MHz
> DVI output,  USB, lots of interesting real-time processing going on.
>
> Yes, it has a frame buffer (four frames actually).  No, it shouldn't be
used
> to render graphics primitives.
>
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> 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:a_2fb.40558$5z.28069@twister.socal.rr.com...
> > Since I was responsible for de-railling the original thread, let me be
the
> > one to beat the horse back to life, since it has interesting potential.
> >
> > The orignal question was: What algorithms can you use to generate live
> > video, that contains only line art (lines, rectangles, curves, circles,
> > etc.), if you can't use a frame buffer.
> >
> > The benefit of using a frame buffer is flexibility. Namely you get
random
> > access to any pixel on the screen. This opens up a wide range of
> algorithms
> > you can use to play the performance-area-complexity tradeoff game.
> >
> > Without a frame buffer, you only have sequential access to your pixels.
No
> > going back, no going forward. Quite Zen I suppose. Anyways, you lose
> access
> > to a lot of frame buffer algorithms, but some can still be used.
> >
> > The conceptually easy ones to understand are math based algorithms, but
> > often they're expensive hardware wise. In the first section, I'll go
over
> > implementation issues of the ideas that other people gave. Nothing super
> > complex.
> >
> > The second section contains a more novel (maybe) approach based on pixel
> > spacing. It's conceptually harder to get a handle on, but has the
> potential
> > to require less resources. Unfortunately there are problems with the
idea
> > that I haven't flushed out. Perhaps someone will have some ideas, or
maybe
> > it'll inspire something better.
> >
> > Oh yeah, I was too lazy to double check what I wrote, so there might be
> > problems. I also left things unfinished towards the end, I've got other
> > things to think about. Hopefully it gets the ball rolling though.
> >
> > Regards,
> > Vinh
> >
> >
> > MATH ALGORITHMS
> > ================
> >
> > Lines
> > -----
> > There was a math based algorithm mentioned by Peter Wallace, where you
use
> > y - (mx + c) = 0 and minx<x<maxx to decide whether to light up a pixel
or
> > not. This algorithm works on a per-pixel basis, so it doesn't need
random
> > access.
> >
> > I like how Peter formatted the equation as y - (mx + c) = 0 rather than
y
> =
> > (mx + c) since a compare against zero uses less logic than a compare
> against
> > any arbitrary number. On the other hand, y = (mx + c) might produce a
> design
> > that can be clocked faster, since you only have one adder. But Xilinx
(and
> I
> > would assume the other vendors also) have pretty fast carry chains, so
it
> > might not be an issue.
> >
> > I would recommend using the form x - (my + c) = 0 instead. The reason is
> > because we're scanning through the pixels left-right, top-bottom. x is
> > always changing while y takes many clock cycles to change. Therefore you
> can
> > use a multicycle multiplier that trades off time for area savings. Also
> the
> > (my) term can be implemented with a constant-multiplier (a * K) which
uses
> > less area than a regular multiplier (a * b).
> >
> > Also because y changes slowly, it's better to use miny<y<maxy. But I
guess
> > if you have a horizontal line, you'll need to use minx<x<maxx.
> >
> > Oh yeah, (x) and (y) are integers, but (m) and (c) have a fractional
part.
> > I'm not sure if this thinking is correct, but if we assume the
resolution
> of
> > a TV screen is 512x512 (yes I know it's never that good), then (m) could
> be
> > as small as 1/512 and as large as 512, so we'd need 9 bits of integer
and
> 9
> > bits of fraction (9.9). I suppose (c) would need the same thing. Cool,
> > that's 18-bits, just right for the dedicated multipliers in Xilinx and
> > Altera.
> >
> > Curves
> > ------
> > Instead of thinking of curves as smooth lines, you can imagine them
being
> a
> > string of straight lines connected together (piece-wise linear). So
> > theoretically you can draw any curve "just" by varying (m) and (c) over
> > time. Of course the prospect of doing this inside the FPGA doesn't look
> > promising. You could use embedded RAMs to contain a table of these
values,
> > but that could be a large table. Don't forget you would need a table for
> > each curve in your image. Also, you have to calculate those tables
> > somewhere. Naturally you'd use an external processor/host computer but
> > depending on the application, you might not have that luxary.
> >
> > So that's probably a bad idea, and it might be better to use a math
based
> > solution to curves.
> >
> > Circles
> > -------
> > Roger Larsson's idea for a circle is also math based:
> >
> >     (x - x0)^2 + (y - y0)^2 - r^2 = 0
> >
> > We can expand this to:
> >
> >     x^2 -2x0(x) + x0^2 + y^2 -2y0(y) + y0^2 - r^2 = 0
> >
> > x0^2, y0^2, and r^2 are constants so they can be combined into one big
> > constant K:
> >
> >     x^2 -2x0(x) + y^2 -2y0(y) + K = 0
> >
> > (x^2 + y^2) is independent of x0,y0, and r, so it can be pre-computed
into
> a
> > table K(x,y), that's can be used for all circles:
> >
> >     -2x0(x) + -2y0(y) + K(x,y) + K = 0
> >
> > Of course if you don't have the ram for it, you can break up K(x,y) into
> two
> > seperate, smaller tables and do K(x) + K(y). But do keep in mind that
> K(x,y)
> > can be used for all circles, so it might be a worthwhile use of RAM.
> >
> >     -2y0(y) can use a multicycle-constant-multiplier while -2x0(x) would
> > need a pipelined-constant-multiplier.
> >
> > Now if you got more ram to spare, you could take advantage of the fact
> > that -2x0(x) is independent of y, and vice versa for -2y0(y). Therefore
> you
> > could pre-compute them into their own tables and get:
> >
> >     X0(x) + Y0(y) + K(x,y) + K = 0
> >
> > Unfortunately you'd need a pair of those tables for every circle in your
> > image, and more importantly you'd also have to recompute them whenever
> your
> > parameters change.
> >
> > So you can save some logic and improve performance if your parameters
> don't
> > change often. If they're pretty dynamic, you'll have to bite the bullet
> and
> > use up a lot of logic.
> >
> > Dealing With Rational Numbers
> > -----------------------------
> > Our x and y values are integer only, but the lines and circles described
> by
> > the math formulas exist in a rational number space. I haven't given it
> much
> > thought, but you might have to be a little careful when comparing values
> > against zero. Close enough to zero would be more like it. But it might
not
> > be a big problem.
> >
> >
> > PIXEL SPACING ALGORITHM
> > =======================
> >
> > So far we've viewed things as a 2D array. If we think of things in as a
1D
> > vector, an alternative algorithm presents itself, though I'm not sure
how
> > fruitful it may be in the long run.
> >
> > BTW, 0 degrees = East, 90 = South, 180 = West, 270 = North.
> >
> > If you drew a verticle line on the screen, and "rolled out" the pixels
> into
> > a vector, what you would see is a bunch of black pixels, evenly spaced.
> The
> > spacing would be equal to the width of the screen. Advanced apologies
for
> > the clumsy notation.
> >
> > Position of line-pixel i, p[i], is equal to:
> >
> >     p[i] = p[i-1] + W
> >
> >     W = width of screen
> >
> > To relate the value of p to the x,y space:
> >
> >     p = y*W + x
> >     x = p%W
> >     y = (p - x)/W
> >
> > If you drew a 45 degrees diagonal, you would notice that the spacing was
W
> +
> > 1:
> >
> >     p[i] = p[i-1] + W + 1
> >
> > A 135 degrees diagonal would be:
> >
> >     p[i] = p[i-1] + W - 1
> >
> > So you would think you can draw a line of arbitrary angle simply by
> > following the formula:
> >
> >     p[0] = starting point of line
> >     p[i] = p[i-1] + W + m
> >     m = function of x/y slope
> >
> > Unfortunately you run into problems when abs(m)>1. I'll go into it
later.
> > For now, let's assume this algorithm works perfectly for all occasions.
> >
> > The nice thing about this is there's no multiplication involved, just
> > addition. You use a down counter and when it reaches zero, you create a
> > pixel and put a new value in the down counter. You'll need to take into
> > consideration that (m) can have a fractional part though.
> >
> > Also, as I said earlier, you can think of a curve as a straight line
whose
> > slope changes as you draw it. The nice thing here is we only have (m) to
> > worry about, and no (c). To create a circular arc, you'd only need to
> > increment (m) by a constant. The constant would control the radius of
the
> > circle that the arc belongs to.
> >
> > But alas, this algorithm doesn't work for all (m). Actually angles from
0
> to
> > 45 degrees isn't so bad. 135 to 180 is trickier. I also have a feeling
> it'd
> > be difficult to get "pretty" visual results with this.
> >
> >
> >
>
>

"Jan" wrote:

> Looked at the spec's of the EDP100. Looking very nice indeed.. So to
convert
> the HDSDI into DVI you would need a de�nterlacer and a frame rate
converter.
...
> If you don't mind, I'd like
> to know how many fieldstores are actually used in the deinterlacer.

I can't get into the internals at that level as some things must remain
proprietary.  I'm sure you understand.

The de-interlacer uses some conventional algorithms and a couple of
not-so-standard techniques.  Keep in mind, this is a monitoring device, and,
as such, it tries very hard to not modify the incoming HD stream too much.
Some de-interlacing techniques produce great looking pictures that are
highly synthetic.  That's OK if you are building a deinterlacer for a system
that will then have to process the image further or for something like home
TV.  Probably no OK for professional use.  At least that's my approach.
Seems to work.


> I'm just curious since I'm roughly in the
> same business.

Can you elaborate?  Privately would be OK, of course.

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

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