V
Vinh Pham
Guest
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
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 + 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 + 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 + 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. 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 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. Therefore you
could pre-compute them into their own tables and get:
X0(x) + Y0 + 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, is equal to:
p = 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 = p[i-1] + W + 1
A 135 degrees diagonal would be:
p = 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 = 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.
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
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
+ y0^2 - r^2 = 0x0^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
+ 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
+ K(x,y) + K = 0Of 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
. 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
can use a multicycle-constant-multiplier while -2x0(x) wouldneed 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
. Therefore youcould pre-compute them into their own tables and get:
X0(x) + Y0
+ K(x,y) + K = 0Unfortunately 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, is equal to:
p = 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 = p[i-1] + W + 1
A 135 degrees diagonal would be:
p = 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 = 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.