>> The circle is the locus of all points equidistant from the centre. It's
>> not especially hard to do that with simple integer arithmetic.
>
>    Doing it *fast* is not all that trivial.
>
>    Also, don't confuse the length of the implementation with its complexity.
> A fast circle drawing algorithm using integer math only (and only additions
> and subtractions at that, no multiplications or divisions) is a relatively
> short algorithm in terms of lines of code, but *understanding* it is a bit
> more difficult. (Coming up with it on your own is even more difficult, but
> not impossible, if you think about it long enough.)

Our graphics lecturer asserted that it's a minor modification of 
Bresenham's algorithm, and Wikipedia concurs. It would take a while with 
pencil and paper to figure out the math, and there's probably a few 
tricky special cases, but it doesn't look intractible.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

>> Seriously. If you know how it works, do you really need to do it 200
>> times over just to *prove* that you know how it works?
>
> Wrong, it's not to prove that it works. It is to drum into your "thick
> little head" how to do it with out thinking. Compare it to repeating a
> dance step until your body does not think of the individual moves. Then
> you can build on it.

Doing arithmetic "without thinking" is how we ended up with Verizon Math 
Fail.

>> It's not even
>> like it's particularly important to be able to *do* long division; it
>> isn't something you're going to need to do every day of your adult life.
>
> You don't know how to do mental arithmetic, then?

Nobody ever needs to compute the exact quotient of two 4-figure numbers 
mentally. It's not necessary. You just need to be able to estimate the 
answer with sufficient accuracy. (Something which apparently a great 
many people can't do for some reason...)

>> Once you've got that, practising it on endless question sheets is just
>> an utter waste of time.
>
> It is if you don't want to be numerate.

Practising something you're going to need to do every single day of your 
life is worth while. Practising something which you will never, ever 
need to actually do is pointless.

Nobody computes 6-figure quotients mentally. Nobody needs to.

> And BTW adding, subtracting, dividing and multiplying is arithmetic not maths.

...which was the entire point of my rant, yes. Our "maths" class covered 
*only* arithmetic, and nothing else.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> In the simple case of lines beginning and ending on pixel boundaries, 
> it's pretty easy.

  How so?

  Ok, maybe if you assume each pixel to be a circle (instead of a square)
it would become simply calculating the distance between the (edge of the)
line and the center of the pixel. That might work as a quite accurate
approximation.

  However, since pixels are squares, not circles, and if you want a very
accurate antialiasing, you would have to calculate how much of the square
is covered by the line. I'm not aware of a very trivial way of doing that.
(I'm not saying it's *complicated*. I'm saying it's *not trivial*, like
eg. a simple one-liner.)

> On the other hand, if you want lines that begin and end at fractional 
> coordinates, or have rounded ends or whatever, the problem becames far 
> more complicated.

  The ends of the line, especially if the line is wider than one pixel
(and especially if you use antialiasing) become a quite ambiguous problem.
Should the line be essentially a rectangle? Or two circles joined by a
rectangle? What if you draw two consecutive lines, what should the joint
point look like?

-- 
                                                          - Warp

Post a reply to this message

On 20/08/2011 01:40 PM, Warp wrote:

>    However, since pixels are squares, not circles, and if you want a very
> accurate antialiasing, you would have to calculate how much of the square
> is covered by the line. I'm not aware of a very trivial way of doing that.
> (I'm not saying it's *complicated*. I'm saying it's *not trivial*, like
> eg. a simple one-liner.)

Suppose, for argument's sake, that your line is nearly horizontal. 
Assume also that pixels are square, and the line is exactly 1 pixel thick.

Now for every pixel that the line intersects, the edge of the line cuts 
the pixel into two regions: an "inside" and an "outside" region. In the 
simplest case, we want the darkness of the pixel to be proportional to 
the area that is "inside".

(In more advanced applications, people sometimes use more complicated 
methods that take into account the actual real-world fuzziness of the 
pixels and so forth. That obviously complicates things drastically.)

Bresenham's algorithm would draw a horizontal line by iterating over all 
the X-coordinates and tracking, for each one, the fractional Y 
coordinate of the center of the line. (But represented in integral 
form.) In the standard Bresenham's algorithm, this fractional-Y is 
simply rounded to the nearest integral-Y, and that is what is plotted.

Let us assume that integral coordinates correspond to the centers of 
pixels (rather than one of their corners or something). In that case, 
the fractional-Y is the Y value of the line at the center of a column of 
pixels.

The slanted area cut by the line actually has the same area as a 
rectangle with the same center hieght. (This is why the trapezoidal rule 
for numerical integration works.)

Hence, for every X-value, we colour floor(Y) according to floor(Y) - Y, 
and ceiling(Y) according to ceiling(Y) - Y (which, you'll notice, is 
equal to 1 - floor(Y) - Y). This trivial piece of math gives us 
antialisaing almost "for free".

>> On the other hand, if you want lines that begin and end at fractional
>> coordinates, or have rounded ends or whatever, the problem becames far
>> more complicated.
>
>    The ends of the line, especially if the line is wider than one pixel
> (and especially if you use antialiasing) become a quite ambiguous problem.
> Should the line be essentially a rectangle? Or two circles joined by a
> rectangle? What if you draw two consecutive lines, what should the joint
> point look like?

Most real drawing systems let you select the kind of end-caps and join 
styles you want, and so forth. Implementing this properly is highly 
non-trivial, I would expect.

A more "interesting" problem is what happens when multiple 
different-coloured lines overlap...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

On 20/08/2011 1:30 PM, Orchid XP v8 wrote:

> Doing arithmetic "without thinking" is how we ended up with Verizon Math
> Fail.
>

Straw man, straw man.


>>
>> You don't know how to do mental arithmetic, then?
>
> Nobody ever needs to compute the exact quotient of two 4-figure numbers
> mentally. It's not necessary. You just need to be able to estimate the
> answer with sufficient accuracy.

True.

> (Something which apparently a great
> many people can't do for some reason...)
>

Again true.


>
> Practising something you're going to need to do every single day of your
> life is worth while. Practising something which you will never, ever
> need to actually do is pointless.
>

Well it surprises me that you never need to calculate something when you 
are away from some form of calculator.

> Nobody computes 6-figure quotients mentally. Nobody needs to.
>

True.

>> And BTW adding, subtracting, dividing and multiplying is arithmetic
>> not maths.
>
> ....which was the entire point of my rant, yes. Our "maths" class
> covered *only* arithmetic, and nothing else.
>

You have said before that your school was not a particularly good one. 
But then I was taught arithmetic in primary school and we did not 
progress to mathematics until secondary school.

-- 
Regards
     Stephen

Post a reply to this message

On 8/20/2011 4:11, Warp wrote:
>    Drawing an accurate antialiased line (of certain width) is not a trivial
> problem. Basically for each pixel you need to calculate how much of it is
> covered by the line. Doing this accurately with integer math only can be
> complicated.

I am not sure you can do it accurately with integer math at all, given that 
there's a "portion of a pixel" involved in there somewhere. At best you'd be 
working in scaled fixed-point.

That said, the AA equivalent of bressenham is Wu:

https://secure.wikimedia.org/wikipedia/en/wiki/Xiaolin_Wu%27s_line_algorithm

-- 
Darren New, San Diego CA, USA (PST)
   How come I never get only one kudo?

Post a reply to this message

On 8/20/2011 2:45, Orchid XP v8 wrote:
>>> OK. Is that for legacy reasons, or because ATM is actually good at
>>> something?
>>
>> ATM is a lot less legacy than IP is. Yes, of course it's actually good
>> at something.
>
> Well, you know, RS232 is a pretty sucky design. But it's still here. That
> *isn't* because it's good at anything. It's because it's widely implemented,
> i.e. legacy.
>
>>> "Yeah, IP really sucks, except for being really flexible." Yes, because
>>> flexibility is a really sucky thing to have.
>>
>> I didn't say that. I said it sacrifices other things in preference to
>> being flexible. There's no resource allocation. There's no way to force
>> a particular route thru the network (well, there is, but nobody actually
>> implemented it in their switches), the addressing sucks for large
>> networks, the address space (in IPv4 at least) is exceedingly limited,
>> remote management of hardware is extremely limited, there's no access
>> control, admission control, or decent rate regulation other than
>> actually dropping packets, etc etc etc.
>
> Most of this sounds like "IP is sucky for managing network hardware". Well,
> no, that's not what IP is for. It's deliberately hardware-neutral.

Well, yes, that's what I said. IP really sucks, except for being 
hardware-neutral. You didn't seem to understand what I was saying before I 
gave the list of many things IP sucks at.

Oh, and it also sucks at things like bandwidth allocation, sophisticated 
routing, and isochronous connections, so it's not just the management part 
that sucks.

 > The idea
> is that you have some infrastructure for controlling your hardware, and then
> run IP on the top. IP is for moving data from A to B.

IP is for moving data from one port on your network to the next port on your 
network, as long as you don't care how long that takes or how quickly it 
gets there.

There's no reservation, no connection control, no access control, and no 
routing control. Even if the hardware fails, you have no way of determining 
how to route around that failure efficiently and promptly.

> If you asked me what was "sucky" about IP, the one I'd probably pick is that
> the entire design philosophy fundamentally assumes that everybody will
> follow the rules.

That too. But tell me how you tell whether the reason you lost your 
connection is whether the remote machine went down, or just some router in 
the middle is rebooting? Tell me how to ask, in IP, whether there's enough 
bandwidth to carry your 64Kbps conversation in each direction with a maximum 
of 85ms delay in each direction. OK, I'm going to start displaying a digital 
movie from the producer to a theater for the next two hours seven minutes: 
How do I pick a route that guarantees me enough bandwidth that the audience 
doesn't see stutters?

You're looking at the things IP does well, and saying "well, it's a bit 
limited here and there." You're not even looking at the stuff that ATM or 
SONET does that IP is never even asked to do.

>> Heck, it doesn't even do roaming, which cell phones have been managing
>> for 10 years.
>
> Cell phones do that by being controlled by a single central authority.

If they were controlled by a single central authority, you wouldn't need 
roaming agreements, now would you?

>> See above. Every packet has the full source and destination address, and
>> there's no information anywhere about the physical network.
>
> Ooo, 64 bits, bit deal.

Well, yes, when you're transporting voice packets a couple dozen bytes long, 
96+ bits of routing information is indeed a big deal.

> It sounds like you're basically complaining that IP isn't
> connection-oriented.

That's one of its failings, yes.

 > You know, if what you're trying to do isn't
> connection-oriented, that's an advantage, right?

Yep. How much of your networking isn't connection oriented? Here's a hint: 
all networking is connection oriented. IP layers non-connection-oriented 
networking on top of that, and then layers TCP to turn it back into 
connection-oriented, poorly. If IP wasn't connection oriented, you wouldn't 
need routing tables on each machine.

> I'm unfamiliar with the data protocols that enable this to be possible. (I
> was under the impression that everybody runs their voice data over IP now
> anyway, so they only need to maintain one big IP network for their voice
> services *and* their broadband offerings...)

In the last mile, that might be true. I'm fairly sure it isn't IP that's 
running on the undersea fibers or bouncing off satellites.  Know how I know? 
There aren't enough IP addresses.

-- 
Darren New, San Diego CA, USA (PST)
   How come I never get only one kudo?

Post a reply to this message

On 8/20/2011 3:49, Orchid XP v8 wrote:
> Seriously though. I was awful at maths when I was at school. Then again,
> when I was at school, "maths" consisted of doing endless arithmetic.

We did that in second grade. What "school" were you in when you were doing this?

> Can you imagine anything more MIND-NUMBINGLY BORING than staring at a sheet
> of 40 long division problems? YES, I GET IT! I KNOW HOW LONG DIVISION WORKS!
> STOP BUGGING ME ALREADY! >_<

You realize that most people aren't that smart, right?  I always got crap in 
school for only doing one homework problem of each type, and then I'd say 
"No, I get it, OK."  And everyone would make fun of me, and then I'd be the 
only one to ace the test.

-- 
Darren New, San Diego CA, USA (PST)
   How come I never get only one kudo?

Post a reply to this message

On 20/08/2011 03:58 PM, Darren New wrote:
> On 8/20/2011 3:49, Orchid XP v8 wrote:
>> Seriously though. I was awful at maths when I was at school. Then again,
>> when I was at school, "maths" consisted of doing endless arithmetic.
>
> We did that in second grade. What "school" were you in when you were
> doing this?

Admittedly it was a school for mentally retarded people such as myself...

>> Can you imagine anything more MIND-NUMBINGLY BORING than staring at a
>> sheet
>> of 40 long division problems? YES, I GET IT! I KNOW HOW LONG DIVISION
>> WORKS!
>> STOP BUGGING ME ALREADY! >_<
>
> You realize that most people aren't that smart, right?

Pro tip: If I can answer 20 long-division questions correctly, I can 
probably answer 2,000 long-division question correctly. It'll just take 
me 100 times longer. :-P Thus, there's no real point to actually 
*making* me answer 2,000 questions...

> I always got crap
> in school for only doing one homework problem of each type, and then I'd
> say "No, I get it, OK." And everyone would make fun of me, and then I'd
> be the only one to ace the test.

I was just having a chuckle about my science teacher whining about how I 
"don't apply myself" in class. His final comment was "more effort 
required". I notice he was the only teacher who forgot to actually fill 
out the performance ratings in the school report. MORE EFFORT REQUIRED! :-P

This amuses me, of course, because I got a B grade for my science, a 
grade which is apparently unprecedented in the history of the school. 
Yeah, I really need to "apply myself" more. :-P Self-important idiot of 
a teacher...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> The slanted area cut by the line actually has the same area as a 
> rectangle with the same center hieght. (This is why the trapezoidal rule 
> for numerical integration works.)

  That takes care of the situation where the edge of the line crosses the
opposite sides of the pixel. However, you have to take into account
separately the cases where the edge crosses two adjacent sides of the pixel
(in which case the cross-section is a triangle rather than a trapezoid).
And of course the triangle can be either the inside or the outside of the
line, so that has to be taken into account.

  Then there's the special case where *both* edges of the line cross the
*same* pixel. This can happen even if the line width is that of one pixel,
when the line crosses the pixel diagonally (but can also more obviously
happen when the width of the line is less than a pixel). In this case you
have to calculate the area covered by one edge, then the area *not* covered
by the other and subtract them.

  So no, you don't get it "almost for free". Not if you want a high degree
of accuracy.

> A more "interesting" problem is what happens when multiple 
> different-coloured lines overlap...

  What's the problem in that? Just draw them one at a time (taking the
transparency of the antialiased pixels into account).

-- 
                                                          - Warp

Post a reply to this message