Jump to content

  • Log In with Google      Sign In   
  • Create Account


Seeking variable width line drawing algorithms


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 Kylotan   Moderators   -  Reputation: 3324

Like
0Likes
Like

Posted 06 March 2013 - 08:15 AM

I have a 2D array of values that map to coordinates, and a set of lines that pass through some of those coordinates. I want to be able to change the values in the array based on their proximity to these lines. So basically I need a line-drawing algorithm, but which supports arbitrary widths.

 

An algorithm like the Bresenham line-drawing algorithm would be fine if the line had essentially zero thickness, but the thickness varies from line to line and I'm not sure how I'd extend it to handle that.

 

I'm also aware that I could treat the line as a rectangle and fill that in, but it sounds suspiciously like implementing half of a software renderer which I'm not keen on doing, unless there is some very simple code or pseudocode that I can pretty much just drop in.

 

I currently have an interesting inverted solution, where I take each point in the array and calculate the distance from that point to the nearest line, and if that distance is less than the line's thickness, then the point is filled in. This has the beneficial effect of letting me taper off the values further from the line, giving me a nice gradient at the edges and avoiding aliasing as well. It also has the detrimental effect of being very slow, even with all the square roots removed from the distance calculations. There are too many redundant distance calculations against lines which turn out not to be the nearest one and thus not contributing to the final distance. But if I could speed this up I'd be happy to stick with it.

 

Any suggestions?



Sponsor:

#2 EWClay   Members   -  Reputation: 655

Like
1Likes
Like

Posted 06 March 2013 - 11:06 AM

Some sort of spatial data structure for the lines would speed up the search. A grid would probably do fine. And I hestitate to recommend it, but a BSP tree would be an elegant solution.

#3 C0lumbo   Crossbones+   -  Reputation: 2092

Like
0Likes
Like

Posted 07 March 2013 - 11:10 AM

Slightly hacky suggestion, but should be simple to implement and may be good enough depending on your precision/speed requirements:

 

You could use something like Bresenham but 'render' a square or circle at each point along the line instead of just a single pixel. For very thick lines you would be doing a lot of overdraw, so you could modify it to only stamp a square/circle once every n steps (where n depends on thickness). If you want to maintain your nice smooth gradients you could conceptually make your sphere more transparent at the edges, and blend with a max function.


Edited by C0lumbo, 07 March 2013 - 12:43 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS