Programming - 3D on Spectrum: fast method of calculating vertices, outputting 3D objects with fill.

                                        
Spectrum + 3D #2              
                              
(c)1998 Dark/X-Trade and -STS-/VolgaSoft
                                        
---------------------------------------
                                        
 The second issue of our magazine is here.
and, accordingly, the second part came out of
series about 3D graphics on the Spectrum.        
                                        
 The previous article turned out to be very
voluminous, and, unfortunately,
after the publication of the magazine, white
ly malicious inaccuracies and nasty
typos, also not everything that was promised would be
was implemented (due to objective reasons)
rank).                                   
 However, it is not very good to start a new one
an article describing the shortcomings of the old one,
therefore, the complete list of detected glu-
Those who wish can find them at the very end. 
                                        
---------------------------------------
                                        
 So, from the last article you learned about
how to rotate 3D objects and display
them on the screen in the form of lines.  But you also
made sure thatmiscalculation of vertices is for-
The concept is very time-consuming, especially when
a large number of them in the object.  Well
what can you do?  It would seem necessary
somehow speed up the multiplication/de-
leniya, but it’s hardly possible yet
speed up. Even using approximate
multiplication and division (8-bit tables)
The increase in speed is not the same
big as I would like.               
 This is where one interesting thing awaits us.
resin method of processing vertices. In the past
article it was stated that "... there will be a description
san method that allows you to easily
process objects consisting of hundreds
peaks." Strictly speaking, not everything is so simple -
that, but, in principle, this is the honest truth.  
 Like everything in this world, this method was
invented by Spectrum developers
toys in 3D. He saves us from the need
the need to do 12 multiplications by the exact
ku (although divisions will still come -
xia) and, thus, allows radically
increase calculation productivity, in
once again proving the truth: everything is
nial - simple.                      
                                        
 Midpoint method.                   
                                        
-------------------------------------   
                                        
 Let's omitthe fact that the name is like
usually invented by us, because it is real
the name is unknown, and let's move on
to the description of this method.     
 First, it is calculated in the usual way
cube (although in principle this could be
this is not a cube, but, say, a dodecahedron, not in
that's the point).                             
                                        
        Figure 1. Here is a cube that    
built...                            
                                        
                
                
                
                
                
                
                
                
                
                
                
                
                
                
                
                
                
                                        
 Four vertices (0-3) of the cube in Figure 1
are calculated as usual.  Remaining
four (4-7) we get a mirror reflection
relative to the center of the cube.  Ready
We add the vertices to the beginning of the ver- buffer
tires Notice that the vertices are still three-
are measured, since before the promising transformation
the matter has not yet reached development.            
 So, the cube is ready. It's time to fuck
from it the coordinates of points 8,9,10, which,
as can be seen from the figure, make up the vertices
plane that needs drawing.    
                                        
It's very easy to do this:               
                                        
 v8=(v4+v5)/2                        
                                        
 v9=(v3+v7)/2                        
                                        
v10=(((v3+v2)/2+v3)/2+v9)/2         
                                        
 PdevN means vertex with number N, a
since the vertex is given by three coordinates -
mi, then you need to perform the appropriate
actions on each coordinate correspondingly
existing peak.                       
 In the last expression, which shows
You're probably a little clumsy,
(v3+v2)/2 are the coordinates of the vertex
11, which is shown in the figure only
for illustration purposes.                    
 Formulas are formulas, but how is this real?
call in practice? The solution is very simple -
That is, you need to write a program for each
dot the point!                              
 But not for the Z80 (that would be too much
bold), and for a virtual processor,
which we will emulate programmatically!
                                        
 Let our miniature "processor" be
have only one register and RAM size
64 24-bit words (to store 8-bit
nyh XYZ), and he will only have 4 commands
fixed length.                    
                                        
 The commands have the following format:        
                                        
aabbbbbb                                
                                        
 where and = command code                    
                                        
     b = point number (N) 6 bits          
                                        
00  Load the coordinates of a point into the register
N.                                      
                                        
01  Place the contents of the register at the point
N.                                      
                                        
10  Find the arithmetic mean between
register and dot N.                   
                                        
11  Finish program execution.     
                                        
 You can write such a program for you
the above example with a triangle.;v8=(v4+v5)/2                           
                                        
;v9=(v3+v7)/2                           
                                        
;v10=(((v3+v2)/2+v3)/2+v9)/2            
                                        
DB 4,128!5,64!8                         
                                        
DB 3,128!7,64!9                         
                                        
DB 3,128!2,128!3,128!9,64!10            
                                        
DB -1                                   
                                        
                                        
                                        
 После  обработки  всех  точек  осталось
только выполнить перспективное  преобра-
зование и нарисовать объект.            
 Вот и всё. Смотрите  исходник  MIDPNT10
(Middle Point) под  Storm1.х  (как  и  в
прошлый   раз,  в  формате   текста)and
look for the CUBE procedure there. Also on the disk
there is a fileMIDPNT12,which represents
is the above-mentioned program, but in
normal multiplication and division
replaced with approximate ones, which in
2-4 times faster than normal.            
 Speaking about speed in general, it’s easy to
note that even the rotation of four points
a very time-consuming activity, since
each point requires 12 multiplications,
and a total of 48 of them are needed... Optimization paths
several.                              
                                        
 The first - having calculated only 3 points, with
Using simple arithmetic you can add
turn the fourth one too.                       
 The second is to rotate the cube in the polar system
coordinates                              
 And now calculate the matrix for for four
dots are ineffective, so amateurs
matrices you will have to try the indicated ones
two ways to optimize, or come up with
something of your own...                        
                                        
                                        
Let's make the objects solid               
                                        
--------------------------------------- 
The lines are relatively fast, but this is still
there is no reason to obsess over them.
So now we'll look at filling
polygons and lightly touch on the problem
removing invisible surfaces.        
                                        
 Let's start with the last one. While we are
poke bulging objects because for
displaying them is sufficient only to determine
pour which edges do not need to be drawn.  B
for complex objects this is not enough, so
how there will be partially invisible
surfaces for which we will have to de-
sort by Z.                   
 To determine the visibility of a face (it is in
in turn must be a convex multi-
square) there is a simple method,
direction-based
vector of the surface normal to the observer
I love, more precisely, only its Z components.    
 Take a look at Figure 2. To get
complete satisfaction from watching
of the exhibited work of art, following
It is not possible to quickly assume the lotus position (in
headstand) and is in such
position for two to three years,
trying to find the truth and optimizing
pouring polygons (just kidding).                
                                        
    Figure 2. Статуя Венеры Мелосской в
свободной интерпретации Малевича.       
                                        
                
                
                
                
                
                
                
                
                
                
                
                
                
                
                
                                        
 Вектор нормали находится  путем  вычис-
ления векторного произведения двух любых
смежных  рёбер  грани   (например 1-2=V,
2-3=W). Please note that the edge
must be set clockwise!  
 We only need the Z component, so
Let's limit ourselves to it.                       
                                        
 Vz x Wz=VX*WY-VY*WX =                  
                                        
 = (X2-X1)*(Y3-Y2)-(X3-X2)*(Y2-Y1)      
                                        
If the result is <=0,  then the edge
invisible.                               
 As you remember, to draw an object
it is enough to have an array of lines that describe
shaping the ribs, which, in turn,
refers to specific points between
which the line should be drawn.   
 An object composed of faces is pre-  
is presented in the form of descriptions of planes,
which refer to specific points,
through which must be passed
plane. Moreover, the plane should be
set clockwise in order to
cutting off non-facial gravures worked correctly
it (we have one-sided faces).        
                                        
 For the plane in Figure 2, an array   
will look like this:                    
DB 4,0,1,2,3                            
                                        
 The first element of the array contains the number of
number of points in the polygon.                
 Convex polygons (we will use
pour them exclusively) it’s easy to fill
but, however, this action is very, very
leisurely.                            
 Filling, except in special cases,
is the process of filling 
gap between left (0-3-2) and right
(0-1-2) horizontal side of the polygon
zone lines (scanning lines
nia).                                   
 There are two ways of filling - two-
pass-through and single-pass.              
 In two-pass pouring, first
the left side is copied, and the initial co-
ordinate X  of each scan line
folds into the left side buffer.  By-
volume the right side is traced, and
final coordinate X of each scan line
folds into the right side buffer
rona.  Then, in the second pass, coordinate
the left and right sides are removed
from the buffer, and between them is drawn
line.                                  
 INsingle-pass filling are traced
both sides at once, and immediately between them
a line is drawn.                         
 From the point of view of speed optimization
Via, two-pass filling is unlikely to work
is faster than a single-pass method, since
you have to go through a bunch of extra work
movements - make two records and two
subsequent readings from memory, also
you have to process 3 counters - according to
one on each side, plus a counter in
drawing cycle. On top of everything else, no
it is also necessary to keep a buffer of one hundred in memory
ron...                                  
 After all these arguments it makes no sense
let's give an example of a two-pass here
fills, but it makes sense to tell the
more about single-pass filling, although
most points are identical for both
them.                                     
 The initial data for constructing a poly-
gona is a list of coordinates of points,
forming a polygon.  As has already been said,
but, the list is given clockwise. For
simplifying the filling procedure, we will
cast only one-sided polygons,
since if the polygon is rotated to the observation
to the giver by the other party, then changes
direction of movement according to the list.         
 Given this limitation, one can be
confident that, moving forward according to the squeak, we
we get to the right side of the training ground, walking
in the opposite direction - we end up on
left side of the landfill.As can be seen from the figure, each of the two
sides consists, in our case, of two
sections. The left side of sections A-B and B-
D. Right - from sections A-C and C-D.Left and
right sides are processed independently
from each other.                          
 Immediately before tracing the hundred-
ron need to find a point from which to
start tracing and where to
finish, i.e.  the highest and most
the bottom point of the polygon.  We have them corresponding
correspond to the points 0 and 2 respectively. 
 Starting from the highest point, we need to
to obtain the height and increment of coordi-
natyX (when moving one along Y)
for the left and right sections. If height
section is equal to zero, you need to take the following
from the list. In this case it is necessary
be careful not to miss
final point and, if reached,
you need to exit the procedure by doing as much as possible
but less unnecessary movements.             
 For example, the processing procedureright
sides will do for section A-C next
blowing things:                            
                                        
 Calculate section height...           
                                        
 RsectHgt=Y1-Y0                         
                                        
   And increment X.                      
                                        
 RdeltaX=(X1-X0)/RsectHgt               
                                        
 A procedure for processing the left side of the
children also monitor the achievement of the bottom
points.                                  
 A smooth loop looks something like this:    
                                        
 1. Draw a line between Xleftand Xright.  
                                        
 2. Go to the next line.      
                                        
 3. Xleft+=LdeltaX, Xright+=RdeltaX. 4. LsectHgt-=1.When zero is reached,
We call the procedure for processing the left side
us. If the end point is reached, exit
dem from the filling procedure.               
                                        
 5. RsectHgt-=1.When zero is reached,
We call the procedure for processing the right side
us.                                     
                                        
 6. Let's move on to step 1.                
                                        
 As you can see, all this is very simple, so
which there is no need to bring here
some code. See file for details
3DROT20.                                
 If you need to draw a lot of small
polygon sizes, it makes sense to draw
not directly on the screen (in the shadow, natural
but), but into a buffer having a simple organization
tion - changing the low byte of the address
we move along Y (0-255), and by changing
high byte of the address go to X (0-
31).                                    
 Thus speeds upaddress calculation
by coordinates, move to the next
string and fill byte selection. Buffer
whose format is thrown onto the screen
a line like this (as done in the demo
Spirius by Mayhem):                     
                                        
 LD B,(HL):DEC N                 
                                        
LD C,(HL):DEC N                 
                                        
 PUSH VS                         
                                        
 It takes 16.5 clock cycles to eject a byte (and
on Scorpio - all 18!), so think about it
- but won’t this cover the gain from acceleration?
rhenium fill?                          
 The pouring procedure given in
3DROT20,not too fast, but not
too slow. In any case, useful
but it would be nice to write your own va-
riant. This applies not only to the Gulf
ke, but also to all other code.  There
there is a huge field for all kinds of optimization
ations.                                  
---------------------------------------
 All sources are written using
STORM turbo specific syntax
assembler.  The files are written in text
form so you could see them
outside the assembler. To upload them to STORM
you should use the import function
text file - BREAK+T.             
                                        
---------------------------------------
                                        
Small list of those used in       
examples of syntactic phrases.       
                                        
                                        
                                        
 LD ВС,HL instead of LD C,L:LD В,Н          
                                        
 RL A,B,C,D instead of RL A:RL B:RL C:RL D  
                                        
 .13 PUSH HL replicates the line 13 times, 
                                        
 LD B,A,C,A loads B and C from          
 battery                          
                                        
EXA means EX AF,AF'.                                        
 NUM[ is the high byte of the number NUM.       
                                        
 NUM] is the low byte of the number NUM.       
                                        
---------------------------------------
                                        
 Finally, about the sad. Plucks of the previous one
articles.                                 
                                        
Plyuk 1.                                 
                                        
 Pde: Algorithms/Multiplication/method         
2/IXHL=IX*DE                            
                                        
 The example uses a non-existent
command ADCIX, BC.  I'm like spoiled
A Motoroll man through and through,
I often make this stupid mistake.       
                                        
                                        
                                        
 ...                                        
 JR NC,$+5                          
                                        
ADD HL,DE                          
                                        
    ADC IX,BC ;There is no such command...    
                                        
 ...                                  
                                        
                                        
Plyuk 2.                                 
                                        
 Pde: Algorithms/Compositional multiplication
      /exact method, also in the file    
      ALGORITM (where the glitch came from)    
                                        
 Admitted and reproduced in two copies
rah small typo - unsigned de-
halving instead of iconic.         
                                        
LD L,A                            
                                        
 SBC HL,BC                         
                                        
      SBC HL,DE                         
                                        
      SRL Н:RR L ; Надо SRA Н:RR L      
                                        
      RET                               
                                        
MULS1 LD A,L:SUB Е                      
                                        
       ....                             
                                        
      ЕХ DE,HL                          
                                        
      ADD HL,ВС                         
                                        
      SBC HL,DE                         
                                        
      SRL Н:RR L ;То же самое           
                                        
      RET                               
                                        
                                        
                                        
Plyuk 3.                                 
                                        
 Pde: Algorithms/Compositional division/ 
      calculation Y=Log X on basic ite- 
      rational formula.               
                                        
 Since the whole thing was written in the editor,
an identical block was copied from another
th example, but, as it turned out, not from
that.                                   
                                        
 The program should be like this:           
                                        
                                        
 LET D=0                         
                                        
 FOR X=1 TO 255                  
                                        
ROKE A+X,D-256*INT (D/256)      
                                        
ROKE A+256+X,D/256              
 LET D=D+1/((x+4606)*LN 2)       
                                        
 NEXT X                          
                                        
                                        
Plyuk 4.                                 
                                        
 Pde: Algorithms/multiplication/Note #3  
                                        
 ... Indeed, if we know that,
for example, the most significant 3 bits of the multiplier are zeros,
why check this every time?         
 Just move the multiplier to the left    
Plyuk 4.                                 
                                        
 Pde: Algorithms/multiplication/Note #3  
                                        
 ... Indeed, if we know that,
for example, the most significant 3 bits of the multiplier are zeros,
why check this every time?         
 Just move the multiplier to the left    
(for the second method) for these same 3 bi-
and do only 5 iterations of multiplication.
Obviously, the result also needs to be shifted
move 3 bits to the left...The last sentence represents
the fight is a typical jump (so-called thinko).  On
in fact, the result cannot be moved anywhere
necessary.                                   
                                        
It seems like I don’t remember anything anymore.  
It's been a long time...