Searching \ for '[EE] 2D graphics: Drawing thick lines?' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: massmind.org/techref/index.htm?key=drawing+thick+lines
Search entire site for: '2D graphics: Drawing thick lines?'.

Exact match. Not showing close matches.
PICList Thread
'[EE] 2D graphics: Drawing thick lines?'
2007\10\16@222145 by M. Adam Davis

face picon face
So I've implemented a line drawing algorithm, and even understand how
to draw anti-aliased lines

But I haven't seen anything about drawing lines of varying width.

I suspect that simply drawing several single pixel wide lines adjacent
to each other will leave unmarked pixels interior to the overall line
in many cases with the default bresenham line algorithm.

I suspect that the "correct" method is to draw a filled polygon (or
filled rectangle).

But I'm hoping there's an easier answer.

Any pointers or clues?

This is going on an ARM processor with an LCD controller, but no
graphics accelerator.  It is running Linux, and I've looked at a
variety of graphics libraries, but the majority appear to target X
(which I'm not running), and the others don't appear to do what I need
or are poorly supported to the point where implementing my own
primitives appears to be speedier than trying to get their code
working on this embedded platform.  This is going straight to a frame
buffer, but I've already got the pixel routines (including alpha
blending).

Ultimately I want to be able to draw semi-transparent open polygons
(non filled) with borders that are more than one pixel wide.

Any ideas or suggested appreciated.  I'll probably have to implement
this next week (hey, I'm planning ahead - who'd'a thunk it?)

Of course, as usual the project is growing in complexity the further I
pursue it, so any suggestions on simple windowing libraries with
framebuffer/alpha/PNG/font support would be appreciated as well.  As
would suggestions for mailing lists and forums where such information
can more eaily be found.

-Adam

--
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - -
Moving in southeast Michigan? Buy my house: http://ubasics.com/house/

Interested in electronics? Check out the projects at http://ubasics.com

Building your own house? Check out http://ubasics.com/home/

2007\10\17@000157 by Marcel Birthelmer

picon face
Adam,
you could try going through the math for your line-drawing algorithm,
but using a virtual grid where each virtual pixel is NxN pixels of
your actual buffer. That way, the line would end up appropriately
fatter.
- Marcel

On 10/16/07, M. Adam Davis <spam_OUTstienmanTakeThisOuTspamgmail.com> wrote:
{Quote hidden}

> -

2007\10\17@041042 by Peter P.

picon face
M. Adam Davis <stienman <at> gmail.com> writes:
> So I've implemented a line drawing algorithm, and even understand how
> to draw anti-aliased lines
>
> But I haven't seen anything about drawing lines of varying width.

Almost all raster renderers use byte or word wide storage in the display section
(not last for speed reasons). So optimizing for pixel drawing will not help so
much. In most raster rendering systems the general case can be studied using a
'mini-screen' made up of 2 x 2N words of storage, where N is the number of
pixels in a word. This assumes that most lines drawn are less than sqrt(N)
pixels wide. This results in 4 cases of this 2x2N matrix for any line to be
drawn, of any length and of any thickness between 1 and sqrt(N):

1. the matrix holding the start of the line
2. the matrix holding the end of the line
3. the matrix holding any middle section(s) of the line (this one repeats)
4. in the special case where the line is short, and both start and end fir in 1
matrix.

This makes the drawing a tiling operation. Also inside the tiles drawing is done
bit-range by bit-range not bit by bit. So there are algorythms but there is no
general easy way to fit them to any word width (and bit plane depth). The matrix
looks like so:

AAAA BBBB
CCCC DDDD
EEEE FFFF
GGGG HHHH

IIII JJJJ
KKKK LLLL
MMMM NNNN
OOOO PPPP

for N=4 and scan from left to right and top to bottom. There are other possible
arrangements for other scan schemes.

Peter P.


2007\10\17@052337 by peter green

flavicon
face

>> But I'm hoping there's an easier answer.
>>    
Use bresenhams or similar but rather than plotting a single pixel at
each location plot a  cluster of pixels.

Using a larger grid is a bad idea because it will make the line far
rougher than it needs to be, you should still plot at every location you
normally would.



2007\10\17@083245 by M. Adam Davis
face picon face
On 10/17/07, Peter P. <.....plpeter2006KILLspamspam@spam@yahoo.com> wrote:
> M. Adam Davis <stienman <at> gmail.com> writes:
> > So I've implemented a line drawing algorithm, and even understand how
> > to draw anti-aliased lines
> >
> > But I haven't seen anything about drawing lines of varying width.
>
> Almost all raster renderers use byte or word wide storage in the display section
> (not last for speed reasons). So optimizing for pixel drawing will not help so
> much. In most raster rendering systems the general case can be studied using a
> 'mini-screen' made up of 2 x 2N words of storage, where N is the number of
> pixels in a word. This assumes that most lines drawn are less than sqrt(N)
> pixels wide. This results in 4 cases of this 2x2N matrix for any line to be
> drawn, of any length and of any thickness between 1 and sqrt(N):

So, my display is 15 bit (16 bit ignored), and a 32 bit processor.
Therefore N = 2 (two pixels per word).

The mini screen you mention would therefore require 8 words (32 bytes,
256 bits) of storage, and in this mini screen I could not have lines
wider that 1.414 pixels.

> 1. the matrix holding the start of the line
> 2. the matrix holding the end of the line
> 3. the matrix holding any middle section(s) of the line (this one repeats)
> 4. in the special case where the line is short, and both start and end fir in 1
> matrix.

I assume you're talking about vectors here.  I hadn't thought about
that - time to pull out my linear algebra book and see what it has.

{Quote hidden}

Is there a name or set of terms that characterize this method so I
could do more research?  I admit to being lost here...

Thanks for your time!

-Adam

--
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - -
Moving in southeast Michigan? Buy my house: http://ubasics.com/house/

Interested in electronics? Check out the projects at http://ubasics.com

Building your own house? Check out http://ubasics.com/home/

2007\10\17@083621 by M. Adam Davis

face picon face
Peter,

Thanks.  If I did this (and I'm considering it) I'd have to make
another buffer to hold the result, then overly it on top of the screen
as it needs to be alpha transparent.  If I wrote it directly to the
screen some pixels would be written more than once, falsely
multiplying the alpha effect.  Before I did this I'd probably
implement polygons and do it that way.

Unless there's some secret cluster that guarantees each pixel gets
written exactly once...

-Adam

On 10/17/07, peter green <plugwashspamKILLspamp10link.net> wrote:
{Quote hidden}

> -

2007\10\17@092351 by Peter P.

picon face
M. Adam Davis <stienman <at> gmail.com> writes:
> So, my display is 15 bit (16 bit ignored), and a 32 bit processor.
> Therefore N = 2 (two pixels per word).
>
> The mini screen you mention would therefore require 8 words (32 bytes,
> 256 bits) of storage, and in this mini screen I could not have lines
> wider that 1.414 pixels.

More like sqrt(2)*N . My mistake.

Anyway the mini matrix makes it easy to deal with chamfer and line ending
stuff that is otherwise horrible to deal with in a 'pure' math solution.

> > 1. the matrix holding the start of the line
> > 2. the matrix holding the end of the line
> > 3. the matrix holding any middle section(s) of the line (this one repeats)
> > 4. in the special case where the line is short, and both start and end
> > fit in 1
> > matrix.
>
> I assume you're talking about vectors here.  I hadn't thought about
> that - time to pull out my linear algebra book and see what it has.

Not vectors but sprites ... the mini-matrix is used to tile the scan storage
thus drawing the line. The 'middle' matrix needs to be shifted for this to
work (#3 above). If you are cheap you can use a middle matrix that is only as
tall as the y height of the thickness of the line is.

> Is there a name or set of terms that characterize this method so I
> could do more research?  I admit to being lost here...

Not that I know of. It is related to scanline raster fill algorythms and
blitting or pattern filling with sprites or textures I think. Maybe someone
else has a better name for this. In general reinventing algorythms is not
productive ... buying a book or two of graphics algorythms may help a lot more
than my message.

Peter P.


2007\10\17@092651 by Peter Bindels

picon face
On 17/10/2007, M. Adam Davis <.....stienmanKILLspamspam.....gmail.com> wrote:
> Unless there's some secret cluster that guarantees each pixel gets
> written exactly once...

Horizontal or vertical line stretched so that the resulting line is as
wide as you want it to be, at an angle of 45-135 degrees to the
direction you want to go. Everytime you skip ahead one line in
bresenham, it moves at most one pixel. Your line will be as wide as
this line is and all pixels will be drawn at most once. Make sure to
scale the width according to the angle of the line (if you go at a 45
degree angle, make it 1.4 times the desired width etc.).

Regards,
Peter

2007\10\17@101815 by M. Adam Davis

face picon face
Excellent suggestion!  I'll have to try this out.  I wonder if I can
extend this to the Wu antialiasing line algorithm...  Seems like it
would essentially be the same.

-Adam

On 10/17/07, Peter Bindels <EraseMEdascandyspam_OUTspamTakeThisOuTgmail.com> wrote:
{Quote hidden}

> -

2007\10\18@084104 by olin piclist

face picon face
M. Adam Davis wrote:
> But I haven't seen anything about drawing lines of varying width.

There is a lot I could say about this, having designed several commercial
display controllers back when I used to be a graphics guy.  But I'm not
going to do it here.  Post the question on the Microchip forums and send me
a PM to make sure I don't miss it.


********************************************************************
Embed Inc, Littleton Massachusetts, http://www.embedinc.com/products
(978) 742-9014.  Gold level PIC consultants since 2000.

2007\10\18@122924 by M. Adam Davis

face picon face
Thanks for your assistance, Olin.  I sent the PM.

For others interested in following this, apparently mobile, discussion
you can see the thread here:
http://forum.microchip.com/m.aspx?m=289560
Microcontroller Discussion Group >> Tips and Tricks >> Drawing thick lines

I'll probably summarize the outcome here later as well.

-Adam

On 10/18/07, Olin Lathrop <@spam@olin_piclistKILLspamspamembedinc.com> wrote:
{Quote hidden}

> -

2007\10\18@141726 by Peter Bindels

picon face
Hello Adam,

Knowing this and having quickly read up on Wu's algorithm, I can be
sure the Wikipedia description is either wrong or the algorithm is.
You need to interpolate the values for three pixels for a one-pixel
wide line for it to be accurate, with increasing error as the slope
goes to 45 degrees.

You determine the cosine of the slope of the line (as in bresenham)
compared to the horizontal or vertical line nearest to where you're
going. You multiply it with the distance in pixels of the pixel you're
drawing compared to the centerpoint you're drawing toward and
determine whether the outcome is within ((line width - 1) / 2). If so,
it's black. If it's larger but below ((line width + 1) / 2),
interpolate the value linearly between these values. If it's larger
than that, it's white.

For getting a "round" starting point you have to extrapolate the "line
width" to match the distance. You would also have to compensate for
that in the starting point line width as the outer most points will
deviate from the "rounded" distance.

Regards, good luck and keep us posted,
Peter

On 17/10/2007, M. Adam Davis <KILLspamstienmanKILLspamspamgmail.com> wrote:
{Quote hidden}

2007\10\20@052115 by Peter P.

picon face
Olin Lathrop <olin_piclist <at> embedinc.com> writes:
> There is a lot I could say about this, having designed several commercial
> display controllers back when I used to be a graphics guy.  But I'm not
> going to do it here.  Post the question on the Microchip forums and send me
> a PM to make sure I don't miss it.

Why are you hijacking a thread, and why are you proposing the repeated
calculation of the bresenham line for both edges of a thick line ? The equation
must be calculated only once followed by the length of the bit run to fill
across the raster. The Bresenham need not be calculated twice. However, doing it
like this will cause problems in the form of special heuristics to make the
ends, so they end up as needed (chamferred, rounded etc).

To Adam: if you have a 15 bit display and a 32 bit processor it is likely that
you  want to use a plain algorithm. There is not enough room in the word to put
more than one display pixel and its mask.

Peter P.


2007\10\20@082300 by M. Adam Davis

face picon face
On 10/20/07, Peter P. <TakeThisOuTplpeter2006EraseMEspamspam_OUTyahoo.com> wrote:
> Why are you hijacking a thread

I'm more than happy to 'travel' for information.  Rather than
hijacking, I tend to think of this as "forking" a thread.  Just
because another thread exists on microchip now doesn't take anything
away from this thread - those who are comfortable here will work with
the thread here, and those more confortable there will work with it
there.  As I'm going to be porting info from there to here then this
thread will actually be better than it would be without the fork.  As
I'm not comfortable at microchip, I won't be porting in that direction
- perhaps someone else will.

So I hope this doesn't become a heavily discussed issue, but if it is
for anyone please fork off a new [OT] thread... :-D

> and why are you proposing the repeated
> calculation of the bresenham line for both edges of a thick line ? The equation
> must be calculated only once followed by the length of the bit run to fill
> across the raster. The Bresenham need not be calculated twice. However, doing it
> like this will cause problems in the form of special heuristics to make the
> ends, so they end up as needed (chamferred, rounded etc).

Yes, I realize that.  Although any line algorithm is going to have
ending special cases.  And yes, bresenham needn't be calculated more
than once.

> To Adam: if you have a 15 bit display and a 32 bit processor it is likely that
> you  want to use a plain algorithm. There is not enough room in the word to put
> more than one display pixel and its mask.

Well the line is going to be a single color/alpha, and the end line
issue makes me think I may have to buffer the output of any good line
drawing algorithm.  Since that's the case it makes sense to pretend
that I have a 1 bit display (320x240, or 2,400 32 bit words).  Would
that give the algorithm you suggest an edge?

-Adam

--
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - -
Moving in southeast Michigan? Buy my house: http://ubasics.com/house/

Interested in electronics? Check out the projects at http://ubasics.com

Building your own house? Check out http://ubasics.com/home/

2007\10\20@094451 by M. Adam Davis

face picon face
On 10/20/07, Peter P. <RemoveMEplpeter2006spamTakeThisOuTyahoo.com> wrote:
> why are you proposing the repeated calculation of the bresenham line
> for both edges of a thick line?

Re-reading Olin's post, I believe he was suggesting two steps:
Develop a trapezoid renderer (assumes flat top and bottom).
Decompose line into a series of trapezoids.

For a thick line the sides would indeed have the same slope, so
bresenham need be run once.

However, a general trapezoid renderer would require two calculations
(unless the sides have the same slope).

I'm still working my brain through all this, but it seems that such a
method might provide opportunities for nice line ends, which are not
taken care of automatically in a simple duplication of bresenham with
vertical or horizontal lines between.

-Adam

--
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - -
Moving in southeast Michigan? Buy my house: http://ubasics.com/house/

Interested in electronics? Check out the projects at http://ubasics.com

Building your own house? Check out http://ubasics.com/home/

'[EE] 2D graphics: Drawing thick lines?'
2007\11\20@021416 by M. Adam Davis
face picon face
As a follow up, I've implemented the following algorithm:

http://www.cs.rit.edu/~icss571/filling/index.html

Polygon filling.  It's quite keen!  I really enjoyed learning about
the theory and then implementing it (no code given).  It's a fairly
quick tutorial, so even if you aren't implementing something like this
soon, I suggest going through it just for the fun of it.

I suppose I just ought to go buy a good graphics books one of these days...

-Adam

On Oct 16, 2007 9:21 PM, M. Adam Davis <stienmanEraseMEspam.....gmail.com> wrote:
{Quote hidden}

--
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - -
Moving in southeast Michigan? Buy my house: http://ubasics.com/house/

Interested in electronics? Check out the projects at http://ubasics.com

Building your own house? Check out http://ubasics.com/home/

2007\11\20@024614 by Nate Duehr

face
flavicon
face

On Nov 20, 2007, at 12:14 AM, M. Adam Davis wrote:

> As a follow up, I've implemented the following algorithm:
>
> http://www.cs.rit.edu/~icss571/filling/index.html
>
> Polygon filling.  It's quite keen!  I really enjoyed learning about
> the theory and then implementing it (no code given).  It's a fairly
> quick tutorial, so even if you aren't implementing something like this
> soon, I suggest going through it just for the fun of it.

That was kinda fun, and I hate graphics coding.  :-)

I'm by no means up to speed on anything graphics-related... but things  
like this, aren't they typically implemented in hardware these days in  
the high-end graphics cards?  I seem to recall (admittedly  from  
reading up on how various heavy-graphics games work) that the GPU  
handles most of this low-level stuff, like filling polygons, shading  
things on the screen, shadows/other effects... in most cases nowadays.

What I don't know is the "stuff" only a real graphics expert would  
know -- just how much of these features is handled by things like both  
the GPU and the software engines above it like OpenGL and DirectX...  
but I get the impression those layers make it "easy" for the graphics  
coders to ignore these low-level algorithms and implement things.

I wonder if it's like CPU's/microcontrollers though, where an intimate  
knowledge of how to do it by hand can be used (Assembly vs. HLL) to  
really make things fly, if you know what you're doing and have the  
time to implement it by hand.  (Or have the graphics engines out-paced  
the humans, where it would take the humans too long and too many man-
hours to do any of that stuff by hand?)

Wonder if there's any graphics programmers on the list who could  
answer that question simply in terms that the rest of us could  
follow?  :-)

I've always been fascinated by graphics sub-systems, but I really  
disliked writing all the repetitive 'stuff' it took to drive them to  
do anything that looked "neat".  That and I've never had much of an  
imagination for how to make something NEW that looked nice on-screen,  
but I can only recognize the style features that I like... without  
being able to always fully explain them.

--
Nate Duehr
EraseMEnatespamnatetech.com



More... (looser matching)
- Last day of these posts
- In 2007 , 2008 only
- Today
- New search...