 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am 20.08.2011 11:34, schrieb Orchid XP v8:
> I can still remember everybody laughing when he said that our assignment
> was to write a program to draw a straight line. But *you* try doing that
> with only integer arithmetic. It's surprisingly nontrivial.
... but can be accomplished by surprisingly elegant and (comparatively)
fast code in Assembler. (What surprised me even more was to see how a
similarly elegant and efficient algorithm could draw a circle. No
trigonometrics, not even a radix, just plain Assembler commands you'd
find on a Z80 processor.)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 20/08/2011 11:19 AM, Warp wrote:
> Orchid XP v8<voi### [at] dev null> wrote:
>> I can still remember everybody laughing when he said that our assignment
>> was to write a program to draw a straight line. But *you* try doing that
>> with only integer arithmetic. It's surprisingly nontrivial.
>
> Drawing a line with integer arithmetic is quite easy. Drawing it
> accurately is slightly more involved. Drawing it *fast* is non-trivial.
>
> And that's assuming the line has a width of 1 pixel and the drawing is
> done without antialiasing.
The assignment was basically to implement Bresenham's Algorithm,
optionally *with* antialiasing for extra marks.
I'm sure Wikipedia can probably provide the details, but essentially the
derivation is this:
1. Start with the equation of a line: P(t) = Vt + U
2. By computing each successive point from the previous one, we can
avoid the expensive multiplication step: P[0] = U, P[n+1] = P[n] + V.
3. We want to ensure that no pixels are missed, and yet no pixel is hit
more than once. Determine whether the line is longer along the X or Y
axies, and then iterate over that axis in 1-pixel incriments.
(This step radically increases the difficulty of implementing your code
correctly "in all eight octants". It's trivial in theory, and damned
fiddly in practise.)
4. If you incriment in one-pixel steps on one axis, the other axis
incriments in steps of dx/dy or dy/dx, which is the ratio of two
integers. If you multiply /the entire algorithm/ through the appropriate
integer variable, all the arithmetic comes into the integral domain.
Welcome to Bresenham's algorithm. Yes, I still remember this 10 years later.
The irony is that the lecture notes explain how to use C++ and OpenGL to
generate the graphical display of your giant "pixels"...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 20/08/2011 11:30 AM, clipka wrote:
> Am 20.08.2011 11:34, schrieb Orchid XP v8:
>
>> I can still remember everybody laughing when he said that our assignment
>> was to write a program to draw a straight line. But *you* try doing that
>> with only integer arithmetic. It's surprisingly nontrivial.
>
> ... but can be accomplished by surprisingly elegant and (comparatively)
> fast code in Assembler. (What surprised me even more was to see how a
> similarly elegant and efficient algorithm could draw a circle. No
> trigonometrics, not even a radix, just plain Assembler commands you'd
> find on a Z80 processor.)
The circle is the locus of all points equidistant from the centre. It's
not especially hard to do that with simple integer arithmetic.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 20/08/2011 11:45 AM, Orchid XP v8 wrote:
> The circle is the locus of all points equidistant from the centre. It's
> not especially hard to do that with simple integer arithmetic.
Come to think of it, you can probably do Bezier splines in integer
arithmetic without much difficulty too...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 19/08/2011 11:23 PM, Patrick Elliott wrote:
> You do realize that about half the people here, including me, read this
> and thought, "Man I really hate this guy for being able to do that
> shit!", right? lol No wonder I can't even figure out some "basic" stuff
> I need for some 3D math. The most I ever derived was some non-standard
> way of multiplying two, two digit, numbers, so it wasn't necessary to do
> all the complicatedly silly stuff the teacher insisted we screw with. :p
Uh, *which* newsgroup am I in? :-?
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. In
class, you would have a textbook the size of a small hardback
dictionary. Most pages contained 40 questions. For example, you might
have a page containing 40 sums, another page containing 40
multiplications, another contained 40 long-divisions, and so on.
At the start of the book, you get to do really easy stuff like 3+7. They
would have several pages of adding, and then a few pages of subtracting,
then a few pages explaining how multiplication works, and then some
pages of multiplication, then how long multiplication works, and then
several pages of progressively harder long multiplication questions.
Then they might get you to do sums involving multiple numbers of
increasing size. Then they have a couple of pages explaining about
negative numbers, then you do progressively more complicated sums
involving multiple negative and positive quantities. Then they might
talk about long division, and get you to do a few hundred of those. And
then division and multiplication with negative quantities as well. Then
maybe they start talking about fractions...
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! >_<
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? 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 just need to have a firm grasp of /how/ it works and /why/ it works.
Once you've got that, practising it on endless question sheets is just
an utter waste of time.
I was always quite bad at arithmetic. I still am. The difference is that
today, I use a frigging *computer* to do the work for me. :-P My job is
to figure out what the actual calculation is; the computer does the
mundane work of actually *running* it.
It wasn't until I got to college that I discovered, mainly due to DKJ,
that "mathematics" consists of something other than just doing hundreds
of identical long division calculations over and over again. Mathematics
provides a systematic way of solving puzzles and problems. It lets you
manipulate and analyse hypothetical entities who's identity (or, indeed,
existence) is as-yet unknown. Through tools like FractInt, I discovered
that mathematics can be beautiful. I spent almost all of my time at
college sat in the library, absorbing everything I could lay my hands on.
At school, fractions were about the most sophisticated topic we came
into contact with. Oh, and drawing graphs on graph paper. We a little
bit of that too. But at college, I learned how to do algebra. I learned
about complex numbers, vectors and matricies, polynomials, solving
equations, differential and integral calculus, cryptography, and so on.
By the way, it's not always easy to learn this kind of stuff from books.
You may not realise, but mathematics is a *very* old subject. It abounds
with strange vocabulary and archaic turns of phrase. For example,
instead of a third-order polymonial, a book might talk about a
polynomial "of order three". On top of that, the books frequently assume
prior knowledge that I don't have. If you're smart you can sometimes
figure out the missing pieces for yourself. But sometimes it's really
hard to follow what's happening. To this day, I /still/ can't figure out
most logic textbooks. And I guess that's simply because I have nobody to
ask.
There's some really interesting stuff out there. Like, group theory,
where you *make up* new kinds of entities which you can "add" and
"subtract" in a mannar similar to ordinary numbers. How neat is that? Or
matrix algebra, where you gain the tools necessary for doing crazy 3D
work. Complex numbers, like normal numbers but with added superpowers.
Cryptology, a battle of whits between code-maker and code-breaker. I
could go on and on.
Most people I know seem to be "afraid" of mathematics. Like "oh man,
there's no way I could ever understand that stuff". Without even
actually trying. I'm stupid, and I managed it, so how hard can it
possibly be?
I suspect it's some combination of math being taught badly, a cultural
expectation that math is impossible to understand, and a society where
stupidity is seen as desirable.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 19/08/2011 11:23 PM, Patrick Elliott wrote:
> No wonder I can't even figure out some "basic" stuff
> I need for some 3D math.
What part of
| U x V | = |U| * |V| * cos a
do you *not* understand? :-P
Only teasing. ;-)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 20/08/2011 11:49 AM, Orchid XP v8 wrote:
>
> 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! >_<
>
> 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.
> 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?
> You just need to have a firm grasp of /how/ it works and /why/ it works.
> 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. And BTW adding, subtracting,
dividing and multiplying is arithmetic not maths.
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] devnull> wrote:
> The assignment was basically to implement Bresenham's Algorithm,
> optionally *with* antialiasing for extra marks.
IIRC the algorithm in question can be used to roughly *approximate*
antialiasing of the line, but it's not mathematically accurate.
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.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] devnull> wrote:
> On 20/08/2011 11:30 AM, clipka wrote:
> > Am 20.08.2011 11:34, schrieb Orchid XP v8:
> >
> >> I can still remember everybody laughing when he said that our assignment
> >> was to write a program to draw a straight line. But *you* try doing that
> >> with only integer arithmetic. It's surprisingly nontrivial.
> >
> > ... but can be accomplished by surprisingly elegant and (comparatively)
> > fast code in Assembler. (What surprised me even more was to see how a
> > similarly elegant and efficient algorithm could draw a circle. No
> > trigonometrics, not even a radix, just plain Assembler commands you'd
> > find on a Z80 processor.)
> 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.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 20/08/2011 12:11 PM, Warp wrote:
> Orchid XP v8<voi### [at] devnull> wrote:
>> The assignment was basically to implement Bresenham's Algorithm,
>> optionally *with* antialiasing for extra marks.
>
> IIRC the algorithm in question can be used to roughly *approximate*
> antialiasing of the line, but it's not mathematically accurate.
>
> 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.
In the simple case of lines beginning and ending on pixel boundaries,
it's pretty easy. I'm not aware of any way in which Bresenham's
algorithm deviates from a perfect solution.
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.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
