## A water drop effect ?

16 posts / 0 new
Author
Message

Hi guys :)

I'm working on a LED matrix project with 16x32 LED's. I can turn a LED on/off by calling its X,Y coordinates, and its working..
Now I want to create a water drop effect
(starting at one X,Y and then spreading out in all directions, like water circles)
But I cant figure out, how I can do this in a simple way :(
Have any one here tried this, or know what I can use as search words ? cause I can't find anything right now :(

uC's: Atmega16, 32, 64, 128 and Attiny13
Lang.: C
Interests: Small scale robots AND sensor monitoring system

Well, one simple way is to use a circle drawing algorithm. Start by drawing with minimum radius and increase it by one each time.

http://en.wikipedia.org/wiki/Mid...

I don't know if there is any more efficient way of drawing circles on such a small area, but the algorithm from Wikipedia is at least very easy to implement and use with XY coordinates.

Oh thanks a lot brow :)
why didn't I think about using the word DRAW :P

uC's: Atmega16, 32, 64, 128 and Attiny13
Lang.: C
Interests: Small scale robots AND sensor monitoring system

The key to this is basic geometry. A circle with its center at X0,Y0 satisfies the equation:

(X-X0)^2 + (Y-Y0)^2 = R^2 where "^2" means raised to the 2nd power (squared)

So, if your water drop is at coordinate X0,Y0 in your array, you simply start with R=0 and steadily increase it over time. For each new R, you compute all of the X,Y values (LED locations) that approximately satisfy this relationship.

It might well be trial and error. For example, you might scan through ALL of the LED coordinates and see which X,Y combinations are close enough to the current radius. This will avoid ugly things like trying to compute a square root.

Jim

Jim Wagner Oregon Research Electronics, Consulting Div. Tangent, OR, USA http://www.orelectronics.net

Depending on how much flash you have unused, you also might want to compute the circles on your PC and just have a read only table in the AVR. Because of the abundant symmetry, you only need a quarter (or an eighth) of it stored.

Chuck Baird

"I wish I were dumber so I could be more certain about my opinions. It looks fun." -- Scott Adams

http://www.cbaird.org

Hi zbaird
Can I do this when the circle's center changes every time the function are called ?

uC's: Atmega16, 32, 64, 128 and Attiny13
Lang.: C
Interests: Small scale robots AND sensor monitoring system

Sure - calculate offsets from the center position, not absolute coordinates. Then when you want the effect, you feed the current center (x,y values) to your output function, along with the radius which will increase for successive calls.

Worst case is you'll have the center at one edge, and want to see ripples to the other. That implies 32 radii maximum, from 0 (center spot only) to 31 (extreme opposite edge). So generate (x,y), calculate the maximum possible radius needed, then call the output function that many times, increasing the radius from 0 to max (with delays between calls for effect).

In the function the radius determines the table entries to use. The table will contain a series (with more for large radii, fewer for small radii) of x and y offsets to add to the original center values. Applying them all will generate 1/4 or 1/8 of the circle. Then you repeat and reflect those offset 4 or 8 times, depending on the symmetries you're using, to make the complete circle.

Good thing - no nasty math in the AVR, easy to adjust the circle generating algorithm because it's done on the PC - just upload a new table. Bad thing - table gets a little complex, especially with symmetry application.

On the other hand, there are a lot of integer circle drawing algorithms around, requiring very little math, and it might be easy enough to implement one of those, as timojaask pointed out.

Chuck Baird

"I wish I were dumber so I could be more certain about my opinions. It looks fun." -- Scott Adams

http://www.cbaird.org

Quote:
Worst case is you'll have the center at one edge, and want to see ripples to the other. That implies 32 radii maximum, from 0 (center spot only) to 31 (extreme opposite edge).

The worst case is when the center is in one corner, and the most far LED is in the opposite corner. This means sqrt(31*31 + 15*15) = 34.
Because there are not too many pixels, I would use a parametric way, the parameter being the angle.
The minimum angle (worst case) between two LED is atan(1/34) = 1.68 degrees. This means a table of 45/1.68 = 27 sin values and 27 cos values. To make things better, I would use 32 values for both functions. One byte is enough, so you no need floating point computation. Store the values sintable(alpha) = sin(alpha) * 256. You need to take care about the exception where sin/cos(alpha) = 1. So, just multiply your radius with your table value, and discard one byte and you are done.
X = X0 +/- R * sintable(alpha)/256
Y = Y0 +/- R * costable(alpha)/256
For large radius use small increment for the angle. For small radius, you can speed up the process using larger increment for the angle.

George.
Edit:
sorry I mixed sin with cos.
the correct formula is :
X = X0 +/- R * costable(alpha)/256
Y = Y0 +/- R * sintable(alpha)/256.

Quote:
The worst case is when the center is in one corner, and the most far LED is in the opposite corner.

Right you are, obviously. I wasn't thinking too clearly.

This sounds like a good solution to me.

Chuck Baird

"I wish I were dumber so I could be more certain about my opinions. It looks fun." -- Scott Adams

http://www.cbaird.org

I think that this is one of the shortest and clearest explanations of Bresenham's Circle Algorithm, complete with the 8 sector symmetry: KHarris Bresenham .

JC

Good old Bresenham's Algorithm.... Implemented that 20 odd years ago on a 6502 doing a raindrop style effect myself. Two circles at r and r+2 looked best if I remember correctly. Then 10 years later someone used the basic symertery of it in a question in a job interview just to check out my logical thinking. I did not let on about having implemented it till towards the end of the interview when things were clearly going well. I had just had a good argument with the interviewer about an optimisation issue where I clearly knew more than he did....

Ifor

Quote:
I think that this is one of the shortest and clearest explanations of Bresenham's Circle Algorithm

Except that it isn't Bresenham's algorithm, though it is often mistakenly called that. It was, however, inspired by Bresenham's line algorithm.

Regards,
Steve A.

The Board helps those that help themselves.

So, in summary:

Your longest diagonal, and therefore the maximum radius needed, is 36 if rounded up.

Using the algorithm, all you need to know is whether Y decrements or not as X moves through the 1/8 segment. This is half a radius, or 18 points.

Each Y decrement/no-decrement flag can be a single bit in a lookup table.

So a table of 36 values (18 bits in each, calculated on your PC) would completely define all the circles you could draw on your grid. You could actually compress this considerably (getting it down to 60 bytes is easy) since the smaller radius circles don't need 18 bits, but it might not be worth it.

No math other than additions and subtractions.

Chuck Baird

"I wish I were dumber so I could be more certain about my opinions. It looks fun." -- Scott Adams

http://www.cbaird.org

Thanks for all the good reply's
I understand the idea of using a table with the values.. but right now, I cant figure out how this would work.. I mean, let's say the radius is 3 and center is (0,0)
how would the circle routine then look when it's using tables to find the new points ?

uC's: Atmega16, 32, 64, 128 and Attiny13
Lang.: C
Interests: Small scale robots AND sensor monitoring system

Quote:
Using the algorithm, all you need to know is whether Y decrements or not as X moves through the 1/8 segment. This is half a radius, or 18 points.

This is R * 0.707 or 25 points. Since 36 was calculated with the assumption of a rectangle panel shape, you will never need this point, so three bytes should be enough for long radius.
Using one, or two or three bytes, and shifting them, it sounds good.
Sticking with three bytes for all radius, for a more code consistency, it is another choice.
George.