Message #8631 - Amiga ProgrammiConf.
   Date: 03-19-92 20:49
   From: Lorenz Einarsson
     To: Ian Romanick
Subject: Re: Rastertime w/vex...
Hi,
 
Regarding your message about your problems with the hidden
surface removal routine, here is one solution.
 
Define three points in a surface and call them a,b and c.
This surface i either visible or not, depending where the
surface is located in your object as you have defined it in
relation to your point of view. For all surfaces seen the
points a,b,c should be clockwise, and the hidden
ones anticlockwise.
 
After all rotations the surface is to be projected to two
dimensional coordinates (your screen). Then you test if the
points a,b and c is clockwise or not. I'll provide two
routines in BASIC to clarify the flow.


FOR i=0 to numberofpoints-1
 x=surface3D(i,0):y=surface3D(i,1):z=surface3D(i,2)
 CALL Project (sx,sy,x,y,z)
 surface2D(i,0)=sx:surface2D(i,1)=sy
NEXT
 
ax=surface2D(0,0):ay=surface2D(0,1)
bx=surface2D(1,0):by=surface2D(1,1)
cx=surface2D(2,0):cy=surface2D(2,1)
CALL Face(visible,ax,ay,bx,by,cx,cy)
 
SUB Project(sx,sy,x,y,z) STATIC
  dph=256
  IF z<>0 THEN
    sx=(x*dph)/(z)
    sy=(-y*dph)/(z)
  ELSE
    sx=0
    sy=0
  END IF
END SUB
 
SUB Face(visible,ax,ay,bx,by,cx,cy) STATIC
  visible=0
  aa=(ay-by)*(cx-bx)
  bb=(cy-by)*(ax-bx)
  IF bb-aa>0 THEN visible=1 'perhaps the condition bb-aa<0
END SUB                     'is the right, can't remember...
 
This approach is much faster than just z-sort the surfaces
and display them all, although it will require some more data
in your object definitions.
 
A fast sort algorithm is also required for fast 3D. Bubble sort
is too slow, and since you need a sort algorithm anyway, here
is one for descending sort (this sort is fast, I haven't seen
any sort algorithm faster than this one!)
 
zCount = number of items to sort (unsigned long)
zList_ptr = a pointer to a list with depth values (signed words)
List2D_ptr = a pointer to a list with pointers to your 2D surfaces
 
The zList values corresponds to the 2D surfaces which pointers is
stored in the List2D, like:
 
zList:  dc.w  5,2,9
List2D: dc.l  surface1,surface2,surface3
 
and after sort the result should be:
 
zList:  dc.w  9,5,2
List2D: dc.l  surface3,surface1,surface2
 
              lea      zList(pc),a0
              lea      List2D(pc),a1
              move.l   zCount(pc),d0
              bsr.s    Sort
 
Sort:         ;Requires (zCount,zList_ptr,List2D_ptr) (d0,a0,a1)
              bsr.s    XorSignBit
              bsr.s    ubsort
              bsr.s    XorSignBit
              rts
XorSignBit:
              movem.l  d1-d2/a1,-(a7)
              move.l   d0,d1
              move.l   a0,a1
              subq.l	#1,d1		; <- bug fix
              move.w   #$8000,d2
XOLoop:
              eor.w    d2,(a1)+
              dbra     d1,XOLoop
              movem.l  (a7)+,d1-d2/a1
              rts
ubsort:       ;Entry for unsigned data
              movem.l  d0-d3/a0-a1/a4-a5,-(a7)
              move.l   a0,a4
              move.l   a1,a5
              subq.l   #1,d0
              add.l    d0,d0
              move.l   d0,a1
              add.l    a0,a1
              moveq.l  #15,d0
              bsr.s    sort
              movem.l  (a7)+,d0-d3/a0-a1/a4-a5
              rts
sort:
              movem.l  a2-a3,-(a7)
              move.l   a0,a2
              move.l   a1,a3
Loop:
              move.w   (a2),d1
              btst     d0,d1
              bne.s    CountUp ;<= Change to beq to sort
CountDown:                      ;in ascending order
              cmp.l    a2,a3
              bls.s    J2
              move.w   (a3),d2
              btst     d0,d2
              bne.s    Swap    ;<= Change to beq to sort
              subq.l   #2,a3    ;in ascending order
              bra.s    CountDown
CountUp:
              addq.l   #2,a2
              cmpa.l   a3,a2
              bls.s    Loop
              bra.s    J1
Swap:
              move.w   d1,(a3)
              move.w   d2,(a2)
              move.l   a2,d2
              sub.l    a4,d2
              add.l    d2,d2
              move.l   a3,d3
              sub.l    a4,d3
              add.l    d3,d3
              move.l   0(a5,d2.l),d1
              move.l   0(a5,d3.l),0(a5,d2.l)
              move.l   d1,0(a5,d3.l)
              addq.l   #2,a2
              subq.l   #2,a3
              cmp.l    a2,a3
              bge.s    Loop
J1:
              addq.l   #2,a3
J2:
              subq.l   #2,a2
BitSorted:
              tst.b    d0
              beq.s    Return
              subq.b   #1,d0
;* SortTheHigher
              cmp.l    a0,a2
              bls.s    SortTheLower
              exg      a1,a2
              bsr.s    sort
              exg      a1,a2
SortTheLower:
              cmp.l    a1,a3
              bge.s    RestoreD0
              move.l   a0,d1
              exg      a0,a3
              bsr.s    sort
              exg      a0,a3
RestoreD0:
              addq.b   #1,d0
Return:
              movem.l  (a7)+,a2-a3
              rts
 

To speed up your 3D a bit, try to minimize all wait loops. Do
some useful calculations instead. When you are about to calculte
a new frame, start the blitter clearing the previous displayed frame
memory. While the blitter is working, do all 3D calculations
and do the sorting.
 
One approach also is to make an interrupt driven areafill routine
which feeds itself. This enables you to calculate the blitter
values for the next surface while the blitter is working with
the previous surface. 
 
After the frame is drawn, you can test where the beam is. If this
position is larger than the screenheight, you can start the blitter
clearing the memory that is displayed and also start calculating
the next-next frame. At next vertical blank you swap the frames.
 
Hope I got it understandable enough... One more thing, can you
provide me with an example of the rotation routine you use,
the one with 9 muls and 3 divs? Thanks.
 
4E75 Lorenz

--- Star-Net v1.0z
 * Origin: The Fourth Dimension BBS (2:203/129.0)