Subject: spectrum faster in 3D

From: sentilius <[email-masked]>
Date: Fri, 20 Jun 1997 03:29:43 +0200

Why was the 16bit game 'CARRIER COMMAND' converted to the

C64 in 2D.

And why was the spectrum version in full 3D.

Answer: Because the 6502 was slower than a Z80 when it came to real

maths.

Speccy forever...

---

From: [email-masked] (Stephen Judd)
Date: 25 Jun 1997 14:42:31 GMT

>Answer: Because the 6502 was slower than a Z80 when it came to real

That's a strong claim, and one that has been made many times.  In my
experience to date it is made by people who do not understand any of
the issues involved in 3D graphics, let alone the underlying mathematics,
and how they are implemented computationally, so maybe you can help
me out:

If you would like to test the merits of the claim, feel free to contribute
some code to the coding challenges.  Specifically, a fast multiply routine
needs to be demonstrated, and a fast line routine would help the Spectrum
cause out quite a bit.

	evetS-

---

From: "Alvin R. Albrecht" <[email-masked]>
Date: Sat, 5 Jul 1997 17:38:43 -0600

On Tue, 1 Jul 1997, rjfm2 wrote:

> [email-masked] (Stephen Judd) wrote:
  
> >Well, again, the test of any theory is experiment, so feel free to post
> >your Z80 code for doing fast multiplies ('ol Alvin is taking a 'mite 
> >long time to get his done :) and fast lines.  I would be happy to send
> >you the fast multiply algorithm if you missed it, and you can see it on
> >my web page too.  Otherwise, these kinds of declarative comments are just
> >so much more balloon juice.
 
> Well it takes time..still waiting for Stonkers to be debugged..

:-) Sorry, it's been a busy couple of weeks.  I'll start by seeing what I
can do in the next hour or so:

1.  Fast Draw

To answer Stephen's question:  how would one quickly calculate the next y
address in the display file, given its wacky layout?  Answer:  pop it off
the stack.

The draw routines below are a DRAW dx,dy variety where a line is drawn
>from  the current pixel position (x0,y0) to (x0+dx,y0+dy).  Neither of them
plot the initial point which is assumed to have been either drawn by the
last draw or plotted by an initial PLOT command.

Example:  to draw a square of 50 pixels starting at (0,0):
   PLOT 0,0     ; move to initial pixel position
   DRAW 50,0
   DRAW 0,50
   DRAW -50,0
   DRAW 0,-50

OK, first a straightforward implementation of Bresenham's algorithm:

BRESENHAM
---------

Restrictions:

dy>=0, dx>0, dy/dx<=1, dy<128, |dy-dx|<128, line lies in screen
If necessary, break the line into two parts which can be drawn without
repeat of the overhead and without a slope discontinuity.

enter:  B=dx, C=dy
        HL=current screen address
        B'=current pixel position within screen byte (eg: 00100000)
	SP=sitting in table of y screen addresses (see PLOT)

DRAW1	LD A,C		4	; A=dy
	SUB B		4	; A=dy-dx
	SLA A		8	; A=2*(dy-dx)
	LD D,A		4	; D="incrNE"
	LD A,C		4	; A=dy
	SLA A		8	; A=2*dy
	LD E,A		4	; E="incrE"
	SUB B		4	; A=2*dy-dx="d"

; now: E=incrE, D=incrNE, A=d

forlp	JP M,east	10/10	; if d<0 goto east

neast	ADD A,D		4	; d=d+incrNE
	EX AF,AF'	4	; save d and sign
	LD A,L		4	; current x coordinate in bits 0-5 of L
	AND #1F		6	; save bits 0-5
	POP HL		10	; get address of next y coordinate, x=0
	OR L		4	; or in x coordinate
	LD L,A		4
	JP cont		10

east	ADD A,E		4	; d=d+incrE
	EX AF,AF'	4	; save d and sign

cont	EXX		4	; get at alternate set
	RRC B		8	; rotate pixel position
	JP NC,noincx	10/10	; if passed through carry, need to INC L
	INC L		4
noincx	LD A,B		4	; A=pixel
	EXX		4	; get back to set holding screen address
	OR (HL)		7	; or in screen contents
	LD (HL),A	7	; write pixel
	EX AF,AF'	4	; A=d, with sign flag recovered
	DJNZ forlp	13/8	; keep going until dx=0

There is a 40 cycle overhead and it takes 117 cycles to plot a NE pixel
and 79 cycles to plot an east pixel.

It occurred to me that a different version may be quicker:

DDA Version
-----------

This one calculates the fraction part of dy/dx and adds it to a running
variable as the x coordinate is increased by one.  If a carry is set, it's
time to move to the next y coordinate.  Max error is 2^(-9)*256=0.5 pixel
when line is drawn across the entire screen.

Restrictions:

dy>=0, dy/dx<1, line lies on screen

enter:  B=dx, C=dy/dx (8 bits of fraction part)
        E=current pixel position in byte (eg 01000000)
        HL=current screen memory address
        SP=sitting in table of y screen addresses

**** The overhead in calculating the fraction part of dy/dx (a special
case division) is not shown here - I'll figure this out and post it
tomorrow.

	XOR A		(part of overhead)
forlp	ADD A,C		4	; A=A+dy/dx
	LD D,A		4	; save A in D
	JP NC,noincy	10/10	; if carry, have moved to next y coord

	LD A,L		4	; bits 0-5 of L hold current x coord
	AND #1F		6	; get x coord
	POP HL		10	; pop address of next y coord, x=0
	OR L		4	; or in x coord
	LD L,A		4

noincy	RRC E		8	; rotate pixel position
	JP NC,noincx	10/10	; if through carry, need next x byte coord
	INC L		4
noincx	LD A,E		4	; A=pixel
	OR (HL)		7	; or in screen
	LD (HL),A	7	; write pixel to screen
	LD A,D		4	; recover A
	DJNZ forlp	13/8	; do until dx=0

This one takes 71 cycles to plot if y coordinate not changed and
99 cycles per pixel otherwise.

Either way, tough for you to beat I think.

2.  The PLOT

The plot needs to initialize SP so that it lies in a table of screen
addresses for each y coordinate (x=0), pops first screen address into HL,
finds first pixel position in byte.

The following is very quickly written, so may not be the fastest way.  It
should also be tweaked for each line draw routine above so that the
correct registers end up with the correct variables.

 enter:  HL=y coordinate
         C=x coordinate
 exit:   A=pixel position in byte (eg 10000000)
         HL=screen address
         SP=points to next y screen address

PLOT	ADD HL,HL	11	; HL=2*y
	LD SP,addrtbl	10	; bottom of screen address table
	ADD HL,SP	11	; calculate index
	LD SP,HL	6	; SP points to current screen address
	POP HL		10	; get current screen address, x=0
	LD A,#07	7	; get bits 0..2 of x coord
	AND C		4	; they identify pixel position in byte
	LD B,A		4	; B=pixel position in byte (0-7)
	LD A,C		4	; get bits 3..7 into bits 0..5
	RRCA		4	; they identify 8 bit pixel group
	RRCA		4
	RRCA		4
	AND #1F		7	; keep bits 0..5 (column)
	OR L		4	; OR into screen address
	LD L,A		4
	INC B		4	; B=pixel position=1..8
	LD A,#01	7	; rotate pixel bit into correct position
loop	RLA		4
	DJNZ loop	13/8

*** POP causes SP to move upward in memory so when next y coord is
popped off stack, assuming dy>0, requires top of table to correspond
to screen addresses at top of screen.  So y=0 refers to bottom of screen.

addrtbl	DEFW bottom screen address, x=0
        DEFW next to bottom, x=0
        DEFW .... for each y coord

Time's up!

Alvin