Programming by Example

 

A BB4W Compendium

freeman69@gmx.com

IDIC BBC_Owl2 M&P

Linked List & Sorting

Solid 3D objects need to be sorted by distance before drawing, otherwise the illusion of depth can be destroyed. However, sorting takes time.

 

One compromise solution involves the use of a linked list. A linked list is very similar to the design of this website, where each page has a link to the previous page and the next page. If we want to change the order in which the pages are presented (when using the arrow buttons) then instead of moving the contents of the page, we change the links that point to the page, and to the neighbouring pages.

 

    Benefits of a linked list:

 

Increased speed of processing. A program may be required to handle large volumes of 3D objects at peak periods, but only small amounts on average. By using a linked list, we can reserve a very large array, but we only access/process the array rows that are currently in use.

 

A linked list can be sorted by changing the pointers of the relevant rows, removing the need to move the entire contents of individual rows.

 

    All sorted?

 

This program uses the simplest method of sorting: effectively comparing two rows at a time and swapping their positions in the list, if necessary. However, we don't repeat the usual cycle i.e. processing until the array is perfectly sorted. Instead, we rely on the fact that objects won't change position radically and the list will be sorted gradually, one animation frame at a time. It's a never ending process and a compromise solution that works reasonably well.

This compromise solution can be enhanced because we are able to insert objects into the list at specific points e.g. when a diamond explodes, a number of tetrahedrons are inserted immediately after the diamond in the list (because they appear in the same region of space). This gives the process of sorting a head start.

 

  10 MODE 9:OFF

  20 ORIGIN 640,512

  30 *REFRESH OFF

  40

  50 DIM nd{(9) xt,yt,zt,xr,yr,zr,x2,y2}:REM Nodes

  60 DIM link{(16) type,n1,n2,n3}:REM Links (colours & triangles)

  70 DIM td{(1) np,lp,nc,lc}:REM Net pointers

  80 FOR a=0 TO 9

  90   READ nd{(a)}.xt,nd{(a)}.yt,nd{(a)}.zt

 100 NEXT

 110 FOR a=0 TO 16

 120   READ link{(a)}.type,link{(a)}.n1,link{(a)}.n2,link{(a)}.n3

 130 NEXT

 140 FOR a=0 TO 1

 150   READ td{(a)}.np,td{(a)}.lp,td{(a)}.nc,td{(a)}.lc

 160 NEXT

 170

 180 MAXobj=99:REM Linked list

 190 DIM obj{(MAXobj) net,x,y,z,za,xa,ya,dist,life,vx,vy,vz,rvz,rvx,rvy,prv,nxt}

 200 DIM stack(MAXobj):PROCresetobjstack

 210 obj{(0)}.prv=-1:REM Linked list anchor

 220

 230 REM Create a unit vector pointing towards a light source

 240 lightx=100:lighty=100:lightz=10

 250 lm=SQR(lightx^2+lighty^2+lightz^2)

 260 lightx/=lm:lighty/=lm:lightz/=lm

 270 vX=0:vY=0:vZ=0:REM View point (calculating distances)

 280

 290 REM Create 10 Diamonds for display

 300 FOR a=1 TO 10

 310   r=FNinslot(0)

 320   IF r<>-1 THEN

 330     z=RND(150)+50:x=RND(z)-z/2:y=RND(z)-z/2:z*=-1:ya=RND(360)

 340     PROCinitobj(r,1,x,y,z,0,0,ya,RND(50)+25,0,0,0,0,0,RND(5)-3)

 350   ENDIF

 360 NEXT

 370

 380 REPEAT

 390   TIME=0:CLS

 400  

 410   PROCsortlist

 420  

 430   REM Process contents of linked list in order

 440   a=obj{(0)}.nxt

 450   WHILE a>-1

 460     REM Update position & orientation

 470     obj{(a)}.x+=obj{(a)}.vx:REM Velocity

 480     obj{(a)}.y+=obj{(a)}.vy

 490     obj{(a)}.z+=obj{(a)}.vz

 500     obj{(a)}.za+=obj{(a)}.rvz:REM Spin

 510     obj{(a)}.xa+=obj{(a)}.rvx

 520     obj{(a)}.ya+=obj{(a)}.rvy

 530    

 540     x=obj{(a)}.x

 550     y=obj{(a)}.y

 560     z=obj{(a)}.z

 570     za=obj{(a)}.za

 580     xa=obj{(a)}.xa

 590     ya=obj{(a)}.ya

 600    

 610     obj{(a)}.life-=1

 620     IF obj{(a)}.life<=0 THEN

 630       REM Diamonds explode at end of life before relocating

 640       IF obj{(a)}.net=1 THEN

 650         REM Create tetrahedrons

 660         FOR b=1 TO 10

 670           r=FNinslot(a):REM Insert after this object

 680           IF r<>-1 THEN

 690             vx=RND(5)-3:vy=RND(5)-3:vz=RND(5)-3:REM Random velocity

 700             rvz=RND(19)-10:rvx=RND(19)-10:rvy=RND(19)-10:REM Random spin

 710             PROCinitobj(r,0,x,y,z,0,0,0,RND(20)+5,vx,vy,vz,rvz,rvx,rvy)

 720           ENDIF

 730         NEXT

 740         REM Relocate diamond

 750         z=RND(150)+50:x=RND(z)-z/2:y=RND(z)-z/2:z*=-1:ya=RND(360)

 760         PROCinitobj(a,1,x,y,z,0,0,ya,RND(50)+25,0,0,0,0,0,RND(5)-3)

 770       ELSE

 780         PROCrmvslot(a):REM Remove tetrahedron from list at end of life

 790       ENDIF

 800     ENDIF

 810    

 820     PROCdraw(obj{(a)}.net,x,y,z,za,xa,ya)

 830     a=obj{(a)}.nxt

 840   ENDWHILE

 850  

 860   PRINTTAB(0,0);"Active objects: ";stkptr-1

 870   *REFRESH

 880   WAIT 4-TIME

 890 UNTIL 0

 900 END

 910

 920 DEF PROCinitobj(slot,net,x,y,z,za,xa,ya,life,vx,vy,vz,rvz,rvx,rvy)

 930 obj{(slot)}.net=net

 940 obj{(slot)}.x=x

 950 obj{(slot)}.y=y

 960 obj{(slot)}.z=z

 970 obj{(slot)}.za=za

 980 obj{(slot)}.xa=xa

 990 obj{(slot)}.ya=ya

1000 obj{(slot)}.life=life

1010 obj{(slot)}.vx=vx

1020 obj{(slot)}.vy=vy

1030 obj{(slot)}.vz=vz

1040 obj{(slot)}.rvz=rvz

1050 obj{(slot)}.rvx=rvx

1060 obj{(slot)}.rvy=rvy

1070 ENDPROC

1080

1090 REM *******************************************************

1100 REM Linked list maintenance

1110 REM *******************************************************

1120

1130 DEF PROCresetobjstack

1140 LOCAL a

1150 FOR a=0 TO MAXobj:stack(a)=a:NEXT

1160 stkptr=1:obj{(0)}.nxt=-1:REM Reserve anchor slot

1170 ENDPROC

1180

1190 REM Insert a slot into the list, before (-ve) or after (+ve) a slot

1200 REM A returned value of -1 indicates no room in list

1210 DEF FNinslot(insert)

1220 LOCAL b,a,slot,i

1230 IF stkptr>MAXobj THEN =-1

1240 i=ABS(insert)

1250 slot=stack(stkptr):stkptr+=1:REM retrieve free slot from stack

1260 IF insert<0 THEN

1270   b=obj{(i)}.prv:a=i

1280 ELSE

1290   b=i:a=obj{(i)}.nxt

1300 ENDIF

1310 obj{(slot)}.prv=b

1320 obj{(slot)}.nxt=a

1330 obj{(b)}.nxt=slot

1340 IF a<>-1 obj{(a)}.prv=slot

1350 =slot

1360

1370 REM Remove a freed slot from the list, returning it to the stack

1380 DEF PROCrmvslot(slot)

1390 LOCAL b,a

1400 stkptr-=1:stack(stkptr)=slot:REM return slot to stack

1410 b=obj{(slot)}.prv:REM Knit broken list together

1420 a=obj{(slot)}.nxt

1430 obj{(b)}.nxt=a

1440 IF a<>-1 obj{(a)}.prv=b

1450 ENDPROC

1460

1470 REM Partial sort (1 pass per frame) of linked list

1480 REM by object distance from viewer

1490 DEF PROCsortlist

1500 LOCAL b,a,j,i,sorting,xd,yd,zd

1510 a=obj{(0)}.nxt

1520 IF a=-1 ENDPROC

1530 IF obj{(a)}.nxt=-1 ENDPROC

1540 sorting=TRUE

1550 xd=obj{(a)}.x-vX

1560 yd=obj{(a)}.y-vY

1570 zd=obj{(a)}.z-vZ

1580 obj{(a)}.dist=SQR(xd*xd+yd*yd+zd*zd)

1590 WHILE sorting

1600   b=obj{(a)}.nxt

1610   IF b=-1 THEN

1620     sorting=FALSE

1630   ELSE

1640     xd=obj{(b)}.x-vX

1650     yd=obj{(b)}.y-vY

1660     zd=obj{(b)}.z-vZ

1670     obj{(b)}.dist=SQR(xd*xd+yd*yd+zd*zd)

1680     IF obj{(a)}.dist<obj{(b)}.dist THEN

1690       REM Swap links from i><a><b><j to form i><b><a><j

1700       i=obj{(a)}.prv

1710       j=obj{(b)}.nxt

1720       obj{(b)}.prv=i

1730       obj{(b)}.nxt=a

1740       obj{(a)}.prv=b

1750       obj{(a)}.nxt=j

1760       obj{(i)}.nxt=b

1770       IF j<>-1 obj{(j)}.prv=a

1780     ELSE

1790       a=b

1800     ENDIF

1810   ENDIF

1820 ENDWHILE

1830 ENDPROC

1840

1850 REM *******************************************************

1860 REM 3D

1870 REM *******************************************************

1880

1890 DEF PROCdraw(net,x,y,z,za,xa,ya)

1900 LOCAL f,abort,col,a,n1,n2,n3,v1x,v1y,v1z,v2x,v2y,v2z,nx,ny,nz,nm,v

1910 f=1280:abort=FALSE:col=7:GCOL 0,15

1920 FOR a=td{(net)}.np TO td{(net)}.np+td{(net)}.nc-1

1930   PROCrotzxy(a,x,y,z,za,xa,ya):REM Rotate node & add offset

1940   IF nd{(a)}.zr>-1 THEN

1950     abort=TRUE:REM Node behind viewer

1960   ELSE

1970     nd{(a)}.x2=f*nd{(a)}.xr/-nd{(a)}.zr:REM 3D to 2D

1980     nd{(a)}.y2=f*nd{(a)}.yr/-nd{(a)}.zr

1990   ENDIF

2000 NEXT

2010 IF abort ENDPROC

2020 FOR a=td{(net)}.lp TO td{(net)}.lp+td{(net)}.lc-1

2030   CASE link{(a)}.type OF

2040     WHEN 1 : col=link{(a)}.n1

2050     WHEN 7

2060       n1=link{(a)}.n1+td{(net)}.np

2070       n2=link{(a)}.n2+td{(net)}.np

2080       n3=link{(a)}.n3+td{(net)}.np

2090       REM Calc two vectors from 3 co-ords (triangle): b-a and c-a

2100       v1x=nd{(n2)}.xr-nd{(n1)}.xr

2110       v1y=nd{(n2)}.yr-nd{(n1)}.yr

2120       v1z=nd{(n2)}.zr-nd{(n1)}.zr

2130       v2x=nd{(n3)}.xr-nd{(n1)}.xr

2140       v2y=nd{(n3)}.yr-nd{(n1)}.yr

2150       v2z=nd{(n3)}.zr-nd{(n1)}.zr

2160       REM Find the 'normal' of a triangle, (cross product of two vectors)

2170       nx=v1y*v2z-v1z*v2y

2180       ny=v1z*v2x-v1x*v2z

2190       nz=v1x*v2y-v1y*v2x

2200       REM Vector towards viewer

2210       v1x=0-nd{(n1)}.xr

2220       v1y=0-nd{(n1)}.yr

2230       v1z=0-nd{(n1)}.zr

2240       REM Triangle faces viewer (normal points towards viewer)?

2250       IF (nx*v1x+ny*v1y+nz*v1z)>0 THEN

2260         nm=SQR(nx^2+ny^2+nz^2)

2270         REM Calc triangle shade from: A.B / |A||B|

2280         v=(nx*lightx+ny*lighty+nz*lightz)/nm

2290         if v<-1 v=0 else if v>1 v=255 else v=255-acs(v)/pi*255

2300         COLOUR 15,v*(col AND 1),v*((col AND 2)/2),v*((col AND 4)/4)

2310         MOVE nd{(n1)}.x2,nd{(n1)}.y2

2320         MOVE nd{(n2)}.x2,nd{(n2)}.y2

2330         PLOT 85,nd{(n3)}.x2,nd{(n3)}.y2

2340       ENDIF

2350   ENDCASE

2360 NEXT

2370 ENDPROC

2380

2390 REM Rotate a node about 3 axes and add any offset

2400 DEF PROCrotzxy(n,x,y,z,za,xa,ya)

2410 LOCAL ca,sa,x1,y1,z1,x2,y2,z2,x3,y3,z3,x4,y4,z4

2420 x1=nd{(n)}.xt:y1=nd{(n)}.yt:z1=nd{(n)}.zt

2430 z2=z1:ca=COS(RAD(za)):sa=SIN(RAD(za)):x2=x1*ca+y1*sa:y2=y1*ca-x1*sa

2440 x3=x2:ca=COS(RAD(xa)):sa=SIN(RAD(xa)):y3=y2*ca+z2*sa:z3=z2*ca-y2*sa

2450 y4=y3:ca=COS(RAD(ya)):sa=SIN(RAD(ya)):z4=z3*ca+x3*sa:x4=x3*ca-z3*sa

2460 nd{(n)}.xr=x4+x:nd{(n)}.yr=y4+y:nd{(n)}.zr=z4+z

2470 ENDPROC

2480

2490 REM Nodes (x,y,z)

2500 REM Tetrahedron (4 nodes, 5 links)

2510 DATA 0,-1.15,2.31,2,-1.15,-1.15,-2,-1.15,-1.15,0,2.67,0

2520 REM Diamond (6 nodes, 12 links)

2530 DATA 0,8,0,0,-8,0,4,0,-4,-4,0,-4,-4,0,4,4,0,4

2540

2550 REM Links (type,n1,n2,n3: type 1=colour, 7=triangle)

2560 REM Tetrahedron

2570 DATA 1,7,0,0,7,1,2,3,7,1,0,2,7,0,1,3,7,2,0,3

2580 REM Diamond

2590 DATA 1,6,0,0,7,0,4,5,7,0,3,4,1,4,0,0,7,2,3,0,7,0,5,2

2600 DATA 1,4,0,0,7,5,4,1,7,1,4,3,1,6,0,0,7,5,1,2,7,2,1,3

2610

2620 REM Net pointers

2630 DATA 0,0,4,5

2640 DATA 4,5,6,12

Diamonds Arrow black large Arrow black large