Fantasm list to 31 Dec. 1996.

Date: Fri, 15 Nov 1996 11:17:41 -0800

From: Allan Jensen <2811aj@fiol.brock.dk>

To: Multiple recipients of <list-fantasm@mail.tau.it>

Subject: Want some source?

Hello everybody

I=92m not 100% sure this is the correct place for this kind of thing, as it isn=92t really a question about Fantasm or assembly in general. So if someone from Lightsoft could tell me if this is a big no-no, or okay, I=92d appreciate it. Anyway ...

During a very bad hangover I suddenly felt a need to code (I also felt the need to use the bathroom, but that=92s a different story). Having once been warned not to reinvent the wheel, I took a stab at reinventing fire instead. And before the weekend was over I ended up with a =91hot=92 (snigger!) little demo.

Then, after feeling somewhat like my old self again, I discovered I had absolutely no use for it. Dumping it in the wastebasket didn=92t feel right, so I thought I=92d ask if any of you guys wanted to have a look. I have also taken the time to write a short (well, quite big actually) doc on how it works.

What it is:

- 800*600 256 colours executable of the fire demo (lots of pixels looking slightly like fire)

- the commented sourcecode (680x0, mind you)

- text explaining how it's done and how to improve

If you=92re just finishing your latest Marathon-clone this probably wont get you too excited. If you=92re just starting out with assembler it might contain something vaguely interesting.

Even if you haven=92t got the slightest interest in this, you might consider getting it anyway so you wont hurt my feelings :-). You can always trash it when you get it.

If after seeing it you have any questions or suggestions you are very welcome to mail me.

Want it? Mail me with the subject header as: "Oh, alright, give me the bloody demo ... since you insist". Or anything else really. I have to send it by hand anyway, so if you feel more comfortable with "I=92ll pay tuppence, Uncle Harry, and no mistake", you=92re welcome to use that too.=

Remember to include your E-mail address.

Sorry to disturb. Must be off. Bye bye.

Allan (2811aj@fiol.brock.dk)

rts

P.S.If you've already read this once:sorry. I think something went wrong the first time, that's why I send it again.

Date: Sun, 17 Nov 1996 15:07:53 -0500 (EST)

From: Tim Humphrey <humphret@lurch.winthrop.edu>

To: Multiple recipients of <list-fantasm@mail.tau.it>

Subject: _MenuKey Weirdness

In Inside Macintosh, it says to push the character pressed for the command-key equivalent as a byte; that is what a char is right, a byte?

But when I did that _MenuKey didn't do anything, it returned a 0 meaning there wasn't a menu item associated with that key. But when I looked at LightSoft's Edit Example and passed the char as a word it worked! Why is this, is a char a word and not a byte?

While I'm at it, is the data type str255 256 bytes, the beginning length byte plus 255 characters?

..._Tim_...

--=[Email signatures are stupid, that's why I don't put anything in mine]=--

http://www.winthrop.edu/~humphret

Date: Mon, 18 Nov 1996 08:14:30 -0500 (EST)

From: Tim Humphrey <humphret@lurch.winthrop.edu>

To: Multiple recipients of <list-fantasm@mail.tau.it>

Subject: Re: _MenuKey Weirdness

On Mon, 18 Nov 1996, Harvey Hirst wrote:

> Tim,
>
> When you push a byte onto the stack the computer automatically adds a byte
> of padding to make a word since the stack can't have odd addresses. The
> character you push ends up in the high byte of the word. _MenuKey expects
> your character in the low byte. The answer: push your character as a word.

Okay that makes since, but now I have another question. Why does passing other data as a byte get interpreted okay? The only other data that I can think of are boolean data types, and even then it's mostly the return data type, so it can have any value when you push it; maybe this is why I never had a problem with passing bytes. Are bytes sign-extended automatically when you push them--I should probably look in the 68K manual but I'm at work now:)

..._Tim_...

--=[Email signatures are stupid, that's why I don't put anything in mine]=--

http://www.winthrop.edu/~humphret

Date: Mon, 2 Dec 1996 19:47:23 -0500 (EST)

From: Tim Humphrey <humphret@lurch.winthrop.edu>

To: Multiple recipients of <list-fantasm@mail.tau.it>

Subject: Re: Fantasm Question

On Mon, 2 Dec 1996, Kevin Avila wrote:

> Well, I never noticed any scewing with my SIZE resource when I was using
> 3.22 so I can't help ya there, but instead of Stu telling you to upgrade,
> I'm going to. :) You really need to upgrade, having used 3.22 for a long
> time, then switching to 4.1 I would never go back to 3.22. The new version
> are so mutch faster, have more features, etc. I just can't wait for version
> 5 because it sounds like it's really going to kick ass. :)
>
> -----End Sales Pitch-----
>
> Kev

The screwing around that I was talking about was that everytime I assemble something it reset the SIZE resource to its default settings, 768K for the size, no high-level events...Since I'm writing code to test for high-level events and low-memory situations it's a pain to have to go to ResEdit to change the settings back.

I kinda figured I would have to upgrade, guess I didn't want to face the grim news:) I tried the demo of PowerFantasm 4.15 and it looked cool, especially the color editing! I guess my last question is: was there ever a free upgrade from 3.22? I would upgrade now but it seems that local labels still aren't implemented, personally I love local labels and it's hard writing code without 'em...oh well.

On the color thing, has anybody tried using Kaleidoscope yet? It's basically an Aaron replacement except that you can have all kinds of funky looking windows! I'm using a purpleish color scheme and I have jewels for my close box! Really cool and *highly* recommended!
Check out this URL for a link to it and other color schemes, the one I mentioned above is "Amethyst Real".
<http://www.novaproj.org/~kobe/interface/kaleidoscope/>

-----End My Sales Pitch!-----

..._Tim_...

--=[Something is impossible only until someone does it]=--

http://www.winthrop.edu/~humphret

From: twi@pac.com.au
To: Multiple recipients of <list-fantasm@mail.tau.it>
Subject: (No subject)

I know it's probably really simple....and I guess I am too,but couldsomeone please help me with how to set up a basic dialog box.Alert boxes were simple enough but I'm having trouble with dialogs.Thanks in advance.

Paul

From: kevinm@kci.wayne.edu (Kevin McEnhill)
To: Multiple recipients of <list-fantasm@mail.tau.it>
Subject: Re: Re[2]: News from the Tower - 18 Dec 96

> A new OS for the mac!!!
<snip>
> Anyway, it brought back to mind a question I've had for a while. Is there any
> reference material out there as to how to write code which talks directly to
> macintosh hardware? It is easy enough to draw directly to the screen by writing
> to the VRAM, but how (for example) can you read input from the keyboard using
> PowerPC assembly _without_ calling the mac toolbox routines? Is there any
> documentation on the internals of the mac hardware, controller chips etc, or
> does anyone have any pointers as to how I could do this? Thanks.
>

Howdy,

I don't know if this is going to help you write directly to the processor or not (I've been told that is a very bad thing unless you are writing your own OS), but you might want to talk to the people on the mklinux team. They are in the process of porting linux (a really cool Unix-like OS that is being developed around the world) to run on a micro-kernel like MacOS was supposed to. They might have some info for you or they might be able to point you in the right direction.

You can find out more about mklinux at <http://www.mklinux.apple.com>

If you have a 386 or better PC laying around collecting dust and would like to run linux on it go to <http://www.linux.org>. I have to run a PC at work and have been running the Debian distribution of linux for a year and a half and I love it. You can find Debian at <http://www.debian.org>

How is that for advertisement?
#include <std_disclaimer.h>

From: Rob Probin <rob@zedworld.demon.co.uk>
To: Multiple recipients of <list-fantasm@mail.tau.it>
Subject: Re: Line drawing
>Hi Stu
>
>I'm trying to make some polygons, but I've run into a little problem.
>
>Let's say we have two sets of 2d coordinates (X1,Y1) and (X2,Y2). I need
>to calculate the stepvalue, so I know which coordinates to draw between
>to make the polygon.
>I calculate the stepvalue by saying (X2-X1)/(Y2/Y1). This works fine,
>except I don't get enough decimals to draw the line properly.
>When you need to travel down the y-coordinate twice or more before
>increasing the xvalue, the stepvalue must have a decimal-point (fx we
>could have a stepvalue of 0.5).
>What I'm doing now, is multiplying the (x2-x1) with ten to get the extra
>decimal point. It leads to some rather messy calculations which I think
>might be a bit too time-consuming.
>I've been thinking that it might make sense to use the FPU, but
>unfortunately the FPU doesn't make sense to me :-)
>I also suspect there might be some 'clever' way to do all this, by
>shifting some numbers instead of multiplying, but I'm not sure how.
>Any ideas?
>
>Allan
>
>Oh, and merry xmas

As you have basically said - fpu maths is not the way to go. FPU maths has been a luxury on most machines, even some of the big beasties.

This is the standard solution - and as far as I know the fastest. It's called Bresenham's algorithm, after its inventor - Jack Bresenham.

BASICS
You only need to step in two directions when moving across a line:-

(a) one step in either the horizontal or vertical axis.

(b) one step in a diagonal direction.

The direction of both of these is fixed for a particular line.

There is number of type a steps per type b steps. This WOULD be the floating point bit. Notice that the proportion of dx (=x2-x1) to dy (=y2-y1) is FIXED.

So what we are saying is that dy/dx is the slope of the line. But since we don't want to do an actual divide, can we get around this? Well, without going all maths techie (you can look it up in n^100000 books - the all look like they don't REALLY know what going on) ... look at it this way:

When I was in the first few years of school they taught me about sharing. (In maths class - not just generally). They said if adam has 9 apples and he wants to share them equally with three friends how many would each have?

What I'm getting at (very badly) is that by making a sharing variable (we will call it e) and by adding dy if e is negative BUT subtracting dx if e is positive we naturally get the slope of the line. The fractional part if taken care of by an integer method.

A example: if dx is 5 and dy is 2...

e initially action e after

0 -dx -5 step current position in y axis

-5 +dy -3 step current position in x axis

-3 +dy -1 step current position in x axis

-1 +dy 1 step current position in x axis

1 -dx -4 step current position in y axis

-4 +dy -2 step current position in x axis

-2 +dy 0 step current position in x axis

0 -dx -5 step current position in y axis

There are between 2 and 3 x-steps per y-step, which is logical since the line is longer in the x direction than the y direction.

--PLEASE NOTE THIS ALGORITHM DOES NOT USE A DIAGONAL STEP (CURRENTLY)--

THE ALGORITHM

dx = x2 - x1
dy = y2 - y1
current_x = x1
current_y = y1

if dx<0
dx = -dx
xstep = -1
else
xstep = 1
if dy<0
dy = -dy

ystep = -1
else
ystep = 1

if dy=0 (this is special case code for dy=0=horizontal line)
e = -1
else
e = 0

OPTIMISATION

This is a SIMPLIFIED ALGORITHM which justs give you the idea.

The first thing that strikes me is the end conditions look like a bug about to happen. What if they never equal? Even if you can mathematically prove they always will, I still won't code it like that. Surely there much be an easier, safer way? (number of steps is fixed to the bigger of dx and dy??).

Secondly, it draws effectively two points when it 'turns'. This is an optimisation effectively to put the diagonals we talked about originally back in.

As a final note (which in some ways relates to the second optimisation point), I see the loop as not one unified routine, but eight special cases.
But then the faster my routine runs, the better.

There are standard ways of making Bresenham's algorithm do anti-aliasing (which is why it annoys me that 3d games writers can't smooth off those near horizontals!).

Regards
Rob

From: slur@world.std.com (Scott Lahteine)
To: Multiple recipients of <list-fantasm@mail.tau.it>
Subject: Re: Line drawing (in 68K)

This is the ancient line-drawing algorithm, which I learned 10
years ago by hacking Star Raiders on the Atari 400. Of course here I've
written it in 68K, not 6502. You'll have to supply your own INTPLOT
routine, which draws a point at D1=X, D2=Y in the color passed in D0.

There are no special cases, and all lines will be drawn
symmetrically. That is, if there's an odd pixel to be placed - it'll
always be in the middle of the line.

*** *** *** LINEC- DRAW A LINE IN A PASSED COLOR *** *** *** *** PASS EXTRA- D0 = COLOR *** *** *** *** LINE- DRAW A LINE FROM THE LAST POINT TO A NEW POINT *** *** *** *** PASS- D1 = X *** *** D2 = Y *** *** *** *** RETURNS- NOTHING *** *** *** *** KILLS- NOTHING *** *** ***

LINE: MOVE.W D0,-(SP) ; save d0 MOVE.W COLOR(`bss),D0 ; get color as set BSR.S LINEC ; do a line MOVE.W (SP)+,D0 ; restore RTS ; return

LINEC: PUSH.L D0-D7 ; save regs MOVE.W PIXX(`bss),D3 ; get old X MOVE.W D1,D4 ; d4 = newx BSR.S GETHVD ; get a delta MOVE.W D4,D7 ; d7 = delta SWAP D4 ; and do a swap SWAP D5 MOVE.W PIXY(`bss),D3 ; d3 = oldy MOVE.W D2,D4 ; d4 = newy PEA SETDLT(PC) ; set return address

GETHVD MOVE.W #0,D5 ; d5 = 0 SUB.W D3,D4 ; d4 = new - old BEQ.S X0 ; if 0, then done BMI.S X1 ; if >0 ... MOVE.W #1,D5 ; ... set our add to 1 X0 RTS

X1 NEG.W D4 ; if <0 then negate d4 MOVE.W #-1,D5 ; set add to -1 RTS ; return (maybe to SETDLT)

SETDLT CMP.W D4,D7 ; get the larger delta BHI.S GOTDT MOVE.W D4,D7 ; into d7

GOTDT MOVE.W D7,D6 ; d6 = delttop MOVE.W D6,D3 ; set d6 hi = lo SWAP D6 MOVE.W D3,D6 ADDQ.W #1,D7 ; d7 = (delttop + 1) / 2 LSR.W #1,D7 ; [ makes our line symmetrical ] MOVE.W D7,D3 ; duplicate lo / hi SWAP D7 MOVE.W D3,D7 MOVE.W PIXX(`bss),D1 ; prepare our loop MOVE.W PIXY(`bss),D2 ; with the start X Y BRA.S NLINE

LLINE SWAP D6 ; d6 = delttop SWAP D4 ; d4 = deltax SWAP D5 ; d5 = dirx SWAP D7 ; d7 = countx ADD.W D4,D7 ; countx += deltax CMP.W D7,D6 ; is countx > top ? BHI.S NOH ADD.W D5,D1 ; yes, change x SUB.W D6,D7 ; and reset countx

NOH SWAP D4 ; d4 = deltay SWAP D5 ; d5 = diry SWAP D7 ; d7 = county ADD.W D4,D7 ; county += deltay CMP.W D7,D6 ; is county > top ? BHI.S NOV ADD.W D5,D2 ; yes, update y SUB.W D6,D7 ; reset county NOV BSR.S INTPLOT ; plot point at d1 , d2 SWAP D6 ; d6 = loop count NLINE DBF D6,LLINE ; loop!

MOVE.W D1,PIXX(`bss) ; new x, y MOVE.W D2,PIXY(`bss) PULL.L D0-D7 ; restore RTS ; return

-------------------------------------------------

Scott Lahteine (slur@world.std.com)

"No Universe is perfect which leaves no room for improvement."

-------------------------------------------------

From: Rob Probin <rob@zedworld.demon.co.uk>
To: Multiple recipients of <list-fantasm@mail.tau.it>
Subject: Re: Line drawing (in 68K)

> This is the ancient line-drawing algorithm, which I learned 10
>years ago by hacking Star Raiders on the Atari 400. Of course here I've
>written it in 68K, not 6502. You'll have to supply your own INTPLOT
>routine, which draws a point at D1=X, D2=Y in the color passed in D0.
>
> There are no special cases, and all lines will be drawn
>symmetrically. That is, if there's an odd pixel to be placed - it'll
>always be in the middle of the line.
>
> Register swapping is used to minimize memory-accesses.
>

Thanks Scott. I could have pasted my code, but this one does it all as one
(which mine doesn't).

This is a modified Bresenham's algorithm.

I've included some comments through the code for those comparing the
algorithm in my previous email, to this, for those mildly interested.

>
>*** ***
>*** LINEC- DRAW A LINE IN A PASSED COLOR ***
>*** ***
>*** PASS EXTRA- D0 = COLOR ***
>*** ***
>*** LINE- DRAW A LINE FROM THE LAST POINT TO A NEW POINT ***
>*** ***
>*** PASS- D1 = X ***
>*** D2 = Y ***
>*** ***|
>*** RETURNS- NOTHING ***
>*** ***
>*** KILLS- NOTHING ***
>*** ***
>
>LINE: MOVE.W D0,-(SP) ; save d0
> MOVE.W COLOR(`bss),D0 ; get color as set
> BSR.S LINEC ; do a line
> MOVE.W (SP)+,D0 ; restore
> RTS ; return
>

; the main routine

>LINEC: PUSH.L D0-D7 ; save regs
> MOVE.W PIXX(`bss),D3 ; get old X
> MOVE.W D1,D4 ; d4 = newx
> BSR.S GETHVD ; get a delta
>
> MOVE.W D4,D7 ; d7 = delta
> SWAP D4 ; and do a swap
> SWAP D5
>
> MOVE.W PIXY(`bss),D3 ; d3 = oldy
> MOVE.W D2,D4 ; d4 = newy
> PEA SETDLT(PC) ; set return address
>

; this routine effectively decides both xstep (1 or -1) and ystep (1 or -1),
; and also makes the deltas. It's used by the above code twice.

>GETHVD MOVE.W #0,D5 ; d5 = 0
> SUB.W D3,D4 ; d4 = new - old
> BEQ.S X0 ; if 0, then done
> BMI.S X1 ; if >0 ...
> MOVE.W #1,D5 ; ... set our add to 1
>X0 RTS
>X1 NEG.W D4 ; if <0 then negate d4
> MOVE.W #-1,D5 ; set add to -1
> RTS ; return (maybe to SETDLT)
>

; this is the LOOP COUNTER optimisation that basically is the larger of the
; two directions... (the largest delta).
; as an interesting aside, the smaller delta is the number of diagonal steps.

>SETDLT CMP.W D4,D7 ; get the larger delta
> BHI.S GOTDT
> MOVE.W D4,D7 ; into d7
>

; initialise loop counter (d6 - lower word)
>GOTDT MOVE.W D7,D6 ; d6 = delttop
> MOVE.W D6,D3 ; set d6 hi = lo
> SWAP D6
> MOVE.W D3,D6
>

; this trick alters the value of what I call 'e' to ensure the line is
; straight at the beginning. 1/2 largest delta.

> ADDQ.W #1,D7 ; d7 = (delttop + 1) / 2
> LSR.W #1,D7 ; [ makes our line symmetrical ]
> MOVE.W D7,D3 ; duplicate lo / hi
> SWAP D7
> MOVE.W D3,D7
>
> MOVE.W PIXX(`bss),D1 ; prepare our loop
> MOVE.W PIXY(`bss),D2 ; with the start X Y
> BRA.S NLINE
>

; this is the core of the code.
; instead of deciding which one to do based on a sign change, we do a
; calculation for both halves.

; We add the delta for this direction to a counter, and see whether it is
; greater than the largest delta. If it is, then we step in that direction
; and reset the counter by subtracting the largest delta (probably leaving A
; REMANDER in the case of the smaller delta.

; One direction will always step, therefore, and the other will take several to
; do so (unless the line is at 45 degrees).

; So is this the same as Bresenham's?? Yes. Since in Bresenham's we are also
; adding the smaller delta to a counter then subtracting the larger delta.

; We rely on the addition of the remanders to cope with the fraction part on a
; cumulative basis.

>LLINE SWAP D6 ; d6 = delttop
> SWAP D4 ; d4 = deltax
> SWAP D5 ; d5 = dirx
> SWAP D7 ; d7 = countx

; add on the delta for this side
> ADD.W D4,D7 ; countx += deltax
> CMP.W D7,D6 ; is countx > top ?
> BHI.S NOH

; reset the counter (by subtracting the largest delta) and update the x
; position information
> ADD.W D5,D1 ; yes, change x
> SUB.W D6,D7 ; and reset countx

; get the other register set :-)
>
>NOH SWAP D4 ; d4 = deltay
> SWAP D5 ; d5 = diry
> SWAP D7 ; d7 = county

; add on the delta for this side
> ADD.W D4,D7 ; county += deltay
> CMP.W D7,D6 ; is county > top ?
> BHI.S NOV

; reset the counter (by subtracting the largest delta) and update the y
; poisition information

> ADD.W D5,D2 ; yes, update y
> SUB.W D6,D7 ; reset county

; the actual PLOT !!!!!
>NOV BSR.S INTPLOT ; plot point at d1 , d2

; the loop counter....
> SWAP D6 ; d6 = loop count
>NLINE DBF D6,LLINE ; loop!
>

; reset the previous line coordinates
> MOVE.W D1,PIXX(`bss) ; new x, y
> MOVE.W D2,PIXY(`bss)

; restore the register set
> PULL.L D0-D7 ; restore
> RTS ; return>
> -------------------------------------------------
> Scott Lahteine (slur@world.std.com)
>
>"No Universe is perfect which leaves no room for improvement."
> -------------------------------------------------
>
>

From: Tim_Humphrey@atlmug.org (Tim Humphrey)
To: Multiple recipients of <list-fantasm@mail.tau.it>
Subject: Re Line Drawing

Just thought I'd enter the fray of line drawing, hope nothing I say is too redundant.

An algorithm that I came up with for drawing lines is to use the formulas for lines:

formula1: y=mx+b
formula2: x=(y-b)/m
formula3: b=y1-(m*x1)
formula4: m=(y-y1)/(x-x1)

Formulas 2 and 3 are just rearrangments of #1; and #4 is just the slope formula. I refer to (x1,y1) as the starting point, but it really doesn't matter which point you start with as long as you're consistent.

You start by getting your slope, formula4. Instead of actually dividing the slope though you store it as a rational number. I prefer to store the numerator in the low-word of a long, and the denominator as the high-word of a long, as long as you don't have screens that exceed 65535 pixels in either dimension then you're okay:). (By keeping rationals instead of decimals you retain accuracy until you actually have to produce an answer, a pixel.) Your dy and dx are your numerator and denominator respectively.

Next you want to get your y-intercept, formula3. In case you've forgotten how to deal with fractions, you multiply the numerator and denominator together to multiply; however, when you're multiplying m and x1 you can skip the denominator and just copy it over since x1 is an integer and its denominator will always be 1. To subtract the slope&x1 product, b, from y1 you first have to multiply y1's numerator and denominator by b's denominator, again you can just copy the denominator since y1 is an integer. You can then subtract the numerators, storing the entire answer for #3 as one rational.

Something you'll notice is that the denominator for the rationals in this algorithm are derived from the same source, dx, this being the case you shouldn't reduce the rationals since it'll make the arithmetic harder.

After you have the slope and y-intercept then you come to a fork in the road, the direction being decided by one of your deltas. If dy is the larger delta then you're always going to step one unit in the y direction, starting from y1 and ending at y, you calculate the corresponding x coordinate by using formula2. If dx is largest then you step in the x direction, using formula1 for the y coordinate. If the deltas are equal, a diagonal line, then you can choose either method, I personally prefer the x direction, formula1. The magnitudes of the deltas is what is important, so a dy of -7 is larger than a dx of 2. (To get the absolute value subtract the negative number from 0,

0-(-2)=2).

Whichever formula you use you always step one unit in the appropriate coordinate and you use a formula to calculate the other coordinate; sometimes you'll step in one direction and not the other and sometimes you'll step both, you just won't know.

Say your dx was larger, then you'd go into a loop where you always step x by 1, or -1, and plug x's value into formula1 to get y. When you do actually divide a rational you can use integer division to get an integer result, that result being the y coordinate. If you're using formula2 then remember to "flip" the y-intercept. When you're actually coding this you don't have to do any flipping and multiplying since (y-b)'s denominator is the same as b's denominator, so you can just make b's numerator (y-b)'s denominator; now you see why I suggested not reducing the rationals.

-------------------------Sample-------------------------

If you were drawing a line between (4,2) and (2,5) then these are the steps you would take:

1) Get slope, m=(y-y1)/(x-x1) = (5-2)/(2-4) = 3/-2

2) Get y-intercept, b=y1-(m*x1) = 5-((3/-2)*2) = 5-(6/-2) = (-10/-2)-(6/-2) =-16/-2

3) Since the magnitude of dy=3 is larger than dx=-2 we increment in the y direction and use formula2, x=(y-b)/m

4) x=(3-(-16/-2)) / (3/-2) =( (-6/-2)-(-16/-2) ) / (3/-2)
=(10/-2) / (3/-2)
=10/3 = 3 (3,3)
x=(4-(-16/-2)) / (3/-2)
=( (-8/-2)-(-16/-2) ) / (3/-2)
=(8/-2) / (3/-2)
=8/3 = 2 (2,4)

So your intermediate coordinates are (3,3) and (2,4). While the lines won't usually be symmetrical with this method they will be proportionally spaced. The calculations may seem excessive but that's because of all the parenthesis, keep in mind that you're just dealing with integers all the way until the last step, and even then you're still dealing with an integer answer. Checking for conditions like double negatives or a diagonal line is rather pointless, since you'll end up with the same answer only with the extra code that detects the conditions!

..._Tim_...
--=[Something is impossible only until someone does it]=---
http://www.winthrop.edu/~humphret

From: Stuart Ball <100625.720@compuserve.com>
To: Multiple recipients of <list-fantasm@mail.tau.it>
Subject: 415/cursors/line drawing

Tim Humphrey wrote:

>I'm still checking out the demo of PowerFantasm 4.15 and I've found something
>else that isn't supported: multiple 'CODE' resources. I know the /r build
>command will output the code as a separate resource but what if you want the
>code in the same file, just split into many resources. Is there a workaround
>for this? If not I think that should be something included in a newer
>version.
>
>Also a quick question, when you're using _SetCursor to change the cursor how
>do you set it to the standard cursor? I'm using _InitCursor right now to do
>this, is there another way? Inside Mac doesn't specify the constant for the
>standard cursor.

WRT code segments - we looked long and hard at it a long time ago and came to the conclusion (after studying Apple documentation et al.) that the only reason segmenting came into being is because the old 68000 processor was very 16 bit - i.e. no long branches etc, so Apple designed this really slow (but practical) method of creating apps bigger than 32k. with relative ease. (Do I win for the worlds longest sentence competition?)

It's unlikely that Fant will support segmenting but V5 will allow you to specify the resource type and ID for both ISA's. However I doubt there will be support for building the jump table (i.e. code 0).

--------------

The standard Mac arrow cursor is stored in the QD globals which are pointed to by a5 in 68k.

--------------

Finally, W.R.T. line drawing - I've searched through quite a few books and every single one of them describes Bresenham's algorithm - even the very old books. This leads me to the question "Is there a faster algorithm or is that it"?

Maybe Tim's method as posted earlier is faster (I would doubt it).

Perhaps we should test some algorithms - fastest (relative) plot of 1e5 random lines. Anybody game?

Stu.

From: James Hague <jhague@dadgum.com>
To: Multiple recipients of <list-fantasm@mail.tau.it>
Subject: Re: 415/cursors/line drawing

> Finally, W.R.T. line drawing - I've searched through quite a few books and
> every single one of them describes Bresenham's algorithm - even the very
> old books. This leads me to the question "Is there a faster algorithm or is
> that it"?

I've found that the "stupid" algorithm that most books introduce before
talking about Bresenham's algorithm is actually better on most processors
these days. By "stupid," I mean looping on the larger delta (X or Y) and
using a fractional step value for the other coordinate. Here's why:

1. Most of those old books use floating point math, but there's no reason
not to use simple fixed point coordinates.

2. You do need to do a division up front, but the number of instructions
in the inner loop is reduced, so the division is not a factor except for short lines.

3. Bresenham's algorithm requires a condition check and a branch in the inner loop, but the simple algorithm doesn't--i.e. no branch prediction problems.

James - jhague@dadgum.com

From: Tim Humphrey <humphret@lurch.winthrop.edu>
To: Multiple recipients of <list-fantasm@mail.tau.it>
Subject: Re: 415/cursors/line drawing

On Mon, 30 Dec 1996, Stuart Ball wrote:

> WRT code segments - we looked long and hard at it a long time ago and came
> to the conclusion (after studying Apple documentation et al.) that the only
> reason segmenting came into being is because the old 68000 processor was
> very 16 bit - i.e. no long branches etc, so Apple designed this really slow
> (but practical) method of creating apps bigger than 32k. with relative
> ease. (Do I win for the worlds longest sentence competition?)

I'm going to try one last desparate attempt to get CODE resources:)

Suppose you have this "feature" in your program that you don't want
to be in memory unless the user wants it--Word 6.0 anybody. Without
code resources it'll have to take up space even if it isn't being used.
About the only workaround I can think of is to make my own jump table!

> It's unlikely that Fant will support segmenting but V5 will allow you to
> specify the resource type and ID for both ISA's. However I doubt there will
> be support for building the jump table (i.e. code 0).

Would it be too much to ask for an option that outputs the code for an
object file into a separate resource in the same file without building a
jump table, or is this what you were describing above?

..._Tim_...
--=[Something is impossible only until someone does it]=--
http://www.winthrop.edu/~humphret

Date: Mon, 30 Dec 1996 12:09:22 +0000
From: Rob Probin <rob@zedworld.demon.co.uk>
To: Multiple recipients of <list-fantasm@mail.tau.it>
Subject: Re: Line drawing

>> Finally, W.R.T. line drawing - I've searched through quite a few books and
>> every single one of them describes Bresenham's algorithm - even the very
>> old books. This leads me to the question "Is there a faster algorithm or is
>> that it"?
>
>I've found that the "stupid" algorithm that most books introduce before
>talking about Bresenham's algorithm is actually better on most processors
>these days. By "stupid," I mean looping on the larger delta (X or Y) and
>using a fractional step value for the other coordinate. Here's why:
>
>1. Most of those old books use floating point math, but there's no reason
>not to use simple fixed point coordinates.
>
>2. You do need to do a division up front, but the number of instructions
>in the inner loop is reduced, so the division is not a factor except for
>short lines.
>
>3. Bresenham's algorithm requires a condition check and a branch in the
>inner loop, but the simple algorithm doesn't--i.e. no branch prediction
>problems.
>
>James - jhague@dadgum.com
>
>

Yeah, but as you and I know - the people who write the textbooks usually
know more than they tell - and a game and demo writers worth is judged by the fastest execution principle.

In other words, algorithms are a starting point. (?!)

I've actually not seen the Bresenham's original article. For one, I'm not sure whether it used an end-point compare rather than a outer loop count?

From my point of view the point of the Bresenham is the fact that you can use an integer-add rather than a divide-type system to determine which direction.

Effectively what you are saying do a loop count on the inner loop (most frequently stepped direction)???

But your branch prediction problem is only a branch predicition problem if you do not know the most stepped direction?? In my solution I split it up into specific variants:-

left/right pure horizontal line. (between 1-2 variant dependant upon target uP)

up/down pure vertical line (between 1-2 variant dependant upon target uP)

pure diagonal lines (between 1-4 variant dependant upon target uP)

mostly horizontal lines (between 1-4 variant dependant upon target uP)

mostly vertical lines (between 1-4 variant dependant upon target uP)

The core of the line algorithm is only a few instructions.

For a bresenham algorithm, in 68K its:-

repeat_2:

move.b d5,(a0)+ ; plot point
add.w d4,d7 ; e=e+dy
bge.s dirch_ad2 ; if e>=0 branch
dbf d3,repeat_2 ; d3 was TOTAL number of horizontal steps-1

; in PPC thats

repeat_2:
stbu r5,1(r20) ; plot - assuming we compensate for pre-increment
add. r7,r7,r4
bge dirch_ad2 ; dirch_ad2 is forward of the current PC, therefore

; assumed by the branch prediction NOT to be taken

bdnz r3,repeat_2 ; r3 is TOTAL horz steps - backwards branches assumed

; by branch prediction to be taken

Now you are saying compute inner loop, rather than branch... so the inner code would be...

repeat_2:
stbu r5,1(r20)
bdnz r21,repeat_2 ; code overhead to calculate r21 probably
; significant factor...

But what we need to do would be perform a divide previously to get r21...

this should take into account reminders from previous divides to get a straight line...Whats the fastest method?

Finally, if the only way to decide the loop count for the inner loop is a 'physical' divide, then surely a very simple compare for slope could decide whether to use divide or double branch solutions?? (Since divide solution will need many divides for close to diagonal solutions?)????

Rob

P.S. bonus optimisation...

And maybe even a compare for a fixed set for simple slopes to provide inner loop step values, to avoid the divide??? Or use a floating multiply (anyone got 603e floating point instruction timings?? (the slowest ppc?))

Date: Mon, 30 Dec 1996 12:09:05 +0000
From: Rob Probin <rob@zedworld.demon.co.uk>
To: Multiple recipients of <list-fantasm@mail.tau.it>
Subject: Re: 415/cursors/line drawing

>>I'm going to try one last desparate attempt to get CODE resources:)
>>Suppose you have this "feature" in your program that you don't want
>>to be in memory unless the user wants it--Word 6.0 anybody. Without
>>code resources it'll have to take up space even if it isn't being used.
>>About the only workaround I can think of is to make my own jump table!
>
> Stu, I'm going to have to take Tim's side here. He stresses a very good
>point, and thw Word 6 example does the trick, have you ever used it, god
>it's awfull! if the PPC version.
>
>
>--------------
>Kevin Avila
>kevin@sb.net http://www.sb.net/kevin
>
>
>

I know about word 6. (What other program would have a virtual memory system built in that overrides the operating systems!!!).

However, look at the sizes of code comparing code with data. Now, ok, in the old days, (things like ZX81/Timex whatever, Sinclair Spectrum, C64, etc) code space was a significant factor compared with data - probably between 40% to 90%.

However, take an average app. created in assembler on todays 680x0 or PowerPC computers in assembler (code in compiled projects is larger) and the code size is not all that much bigger than the code size for those old computers, - about 40K (this is for projects that DO NOT embed their data in code). This is partly due to the code the O.S. contains, and partly to do with the fact that in real terms there is not a lot of extra functionality.

General program sizes of todays programs are from 500K to 3MBytes. Between 1% to 8% of total program size. Much more important, therefore this the management of initialized and uninitialized data sections pulled into application memory usually from resources and new handle calls with the lock and purgable status's, to provide most of the bulk reclaimable memory.

If I am wrong, please let me know. And are there other factors at work I am not taking into account. I know a lot of games converted from the PC contain large tracts of data embeded into their code segments. This is due, I'm sure, to the programmers hate of putting data files seperate to the *.exe - in a dos filing environment - where users are good at deleting the wrong file. The macs dual fork filing system is such an elegant solution to one file for one app, that I'm suprised that other O.S. manufacturer's haven't stolen the idea. I know I hate going and programming on systems without it.

There has been another argument for putting all data into the code - which is security. Having personnaly stripped graphics, to play with, from games (hasn't everyone?), its harder to extract data that in a seperate resource but simply encrypted than embeded in code but not encrypted. And given the effort no program is safe.

There are of course assembler programs with large sets of data in.

Typically these range from 80-150K code segments for 1-2.5M program size.

Still a fairly small proportion of the total used space. I would appreciate more data here.

Basically, I'm not sure what you are trying to do, why you are trying to do it, etc. When memory was very much at a premium, and the branch address space was limited to +/-32K, then sure, 32K segments make sense - but I don't understand why we need segments now?

This is a LOT of work - for what result? Lets discuss memory footprints!

Rob

Date: Mon, 30 Dec 1996 13:22:32 -0500 (EST)
From: Tim Humphrey <humphret@lurch.winthrop.edu>
To: Multiple recipients of <list-fantasm@mail.tau.it>
Subject: Re: 415/cursors/line drawing

On Mon, 30 Dec 1996, Rob Probin wrote:

> Basically, I'm not sure what you are trying to do, why you are trying to do
> it, etc. When memory was very much at a premium, and the branch address
> space was limited to +/-32K, then sure, 32K segments make sense - but I
> don't understand why we need segments now?
>
> This is a LOT of work - for what result? Lets discuss memory footprints!
>
>
>
> Rob

Basically I'm trying to get the smallest memory requirement possible. It's true that the code for most programs nowadays is only about 20-40% of the total program size but that doesn't mean you should load in the total code. The space that's saved by not loading in all the code can be used for larger/more documents. Just because we have tons of megabytes to spare doesn't mean we should start turning our apps into bloated overweight pigs.

If Fantasm could at least output the object code into separate resources in the same file then I could take care of the rest. I could make a table of offsets for global subroutines and store it at the end of the main code. Each of the other codes could use the table to access the subroutines in the main code.

..._Tim_...
--=[Something is impossible only until someone does it]=--
http://www.winthrop.edu/~humphret

BACK