Processing 1.0 - Processing Discourse - VICTORY! (Bresenham Algorithm scanner)

We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.

Index › Discussion › Exhibition › VICTORY! (Bresenham Algorithm scanner)

‹ Previous Topic | Next Topic ›

Pages: 1

VICTORY! (Bresenham Algorithm scanner) (Read 1857 times)

st33d

VICTORY! (Bresenham Algorithm scanner)
Oct 12^th, 2005, 4:31pm

I have conquered my nemesis, the Bresenham algorithm scanner. I attacked this subject over a year ago and failed to succeed. Building a GUI around the function helped me discover the bugs in the system. Re-writing a lot of strange and un-readable code helped too.

Breseham Algorithm Scanner (Bresen-scan)

It takes two vectors and detects any pixel obstruction between the points using the Bresenham algorithm to chart the journey from point A to point B.

If anyone notices any bugs or can think of any optimisations please respond. I shall not be defeated again!

st33d

Re: VICTORY! (Bresenham Algorithm scanner)
Reply #1 - Oct 13^th, 2005, 8:01pm

I need the scanner for another purpose (which revealed a couple of bugs but they're fixed now) but it allowed me to finish what was my first major Processing project from the days of Alpha.

The Bresenham Vecoriser

It scans for all the lines that could possibly exist within an image. eg:

Processing logo

One issue is that the scanner will draw a short line over a long line on the same path. This makes editing the product a pain. A 64x64 pixel image crashes Illustrator on my PC when vectorised (half a million lines). If anyone has a suggestion for a solution I'd be grateful.

cello

Re: VICTORY! (Bresenham Algorithm scanner)
Reply #2 - Oct 13^th, 2005, 8:57pm

Perhaps consider combining it with a marching squares algorithm to optimize what lines are used?

It seems like you're adding a lot more lines than necessary and it might be more useful to capture the 'hull' rather than every possible line?

If you want to reduce the number of lines with your existing algorithm, you could use some form of binary search tree (sort by x,y) or 2d map (x,y start pair) to keep track of overlapping/colliding lines, then when you go to insert a new line, compare to existing lines that start at that point, find overlaps, and only replace the existing one if it's shorter than the new one.

Marcello

st33d

Re: VICTORY! (Bresenham Algorithm scanner)
Reply #3 - Oct 13^th, 2005, 11:45pm

Creating a sort of crystal lattice was my intention. Capturing the hull would be a different approach altogether. I would probably adapt some edge detection code for that.

I think a point map might work. A table of vector pairs could be generated. I would have to get the bresen-scan to check for vector pairs. I would also have to be sure of a gradient match as well.

If I get time, I'll give it a go. Cheers.

st33d

Re: VICTORY! (Bresenham Algorithm scanner)
Reply #4 - Jul 23^rd, 2006, 7:42pm

I kept hitting the memory wall whilst trying to do a print today. I realised that I only need to scan one PI radians of directions, because the other radian is essentially mirrors the other. I was stuck on how to do this until I thought of this nifty conditional:
Code:


int xj = j % scan.width;
int yj = j / scan.width;
int xi = i % scan.width;
int yi = i / scan.width;
if(i != j && xj >= xi && !(xj == xi && yj < yi){

I've only just realised how to !() recently. It even allows me to inline another condition for drawing only four directions in the same if()
Code:


if(i != j && xj >= xi && !(xj == xi && yj < yi) && !(quadDraw && (xj != xi && yj != yi && (abs(xj - xi) != abs(yj - yi))))){

I will update my download soon.

Hooray for double-think!

Pages: 1

‹ Previous Topic | Next Topic ›