I need a *fast* integer sqrt()

songdog!roman@eskimo.com writes:

>I offer these even though I'm not sure why you need to do square roots to
>fill a circle. Have you heard of Bresenham's algorithm? Algorithms,
>actually - there are ways to draw straight lines and circles/ellipses with
>no more powerful operations than addition and shifting, no multiplication,
>division, or square roots. I'll try to come up with a citation of a good
>book which describes the algorithms (I have a bad book, but I wouldn't
>recommend it to anyone).

Well, I use bresham for lines, and I use a variation of it to draw
normal circles/ellipses. The reason why I need a square root for
filled circles is that, given a y coordinate, I'd like to be able to
calculate the x coordinate in one quadrant (doesn't matter which), and
then draw a scan line from the left to right. The algorithms I use to
draw circles now tend to work by drawing octants, and using symmetry
to reflect the other points (for patterned-line circles, the algorthim
I use draws pixel by pixel, but it doesn't always start in the right
position, and I need that to calculate the tile to use).

I thought I could use the formula (from high school geometry):

          n n
     (x/a) + (y/b) = 1

because I know a,b and y. So I can reorganise the formula to calculate
x.

I should note that I've never done much graphics programming before
so it's quite possible I'm doing things wrong. I don't have any
graphics programming books around here either... (this is one reason
why it's taking so long to write bitblt). Anyway, the initial
version of bitblt is bound to be sub-optimal. Hopefully it will
improve with age.

The name for the windowing system is probably going to be MADO.
(Multiplexed Architecture Display Organiser). In Japanese, this has
the meaning "Window(s)" :-)

Andy, I like the proposed source tree structure!

nick
Received on Wed Sep 29 16:26:17 1993