Coding - the implementation of Phong Bump Mapping on the Speccy.

<b>Coding</b> - the implementation of Phong Bump Mapping on the Speccy.

 Implementation of Phong Bump Mapping on Speccy.


              0. Entry

 The material presented in this paper on
Currently, unfortunately already lost the
relevance, which he had at the time
his writing (fall of 1997:)).
However, perhaps this is still someone
interesting ... More so that before
Publication I thoroughly worked over
section relating to the improvements.

 Watching in the past few
years for the development of Spectrum scene, I
come to the conclusion that the development process
Art demomaking'a on Speccy is
almost the same rate as in
"Large" platforms (Amiga, PC), though
that the hardware on which it works
not undergo any changes: all those
is 128kb and 3.5 MHz. And the level of effects in
demo is constantly growing, new
programming techniques to the screen,
sound and drive ... As a result,
effect appears similar to (almost)
that are implemented on the Amiga and PC. For
examples not far to seek -
just look at the demos, which occupied
first place at ENLiGHT'97 and Funtop'98. AND
This is great!
 Many novice coders come in
delight of watching another
supernavorochennoy demos of some
well-known teams and a desire to illuminate
implement something similar. But here
there is a problem - most
modern effects - aerobatics
arts programming and poking around in
their code is usually difficult
and describe algorithms for their work to find
hard enough. Therefore, this section
magazine is designed, at least in part, to help
so you need to get information about
algorithms work effects in modern
demo.
 And in this issue as a "primer" I
algorithm is presented for effect known
as Phong Bump Mapping. This effect
first appeared somewhere in the year 1995 at
Amiga and PC, and soon gained wide
popularity due to its simplicity and
effectively. On the Speccy (as far as I
known) was first implemented in 1997
year demah presented at ENLiGHT'97:
Binary Love, Shit 4 Brainz (algorithmically
there really is not bump mapping, but
looks similar), Power UP (only in the final
release).

 As an illustration,
looks like this effect
(So you have an idea,
what the actual question) -
bring the screen from our demo
Binary Love.
 The visual effect is a spot of light moving along a certain 
trajectory and illuminating a certain image, and this

an image in relief, ie, like
"Stamped" on the screen.

   Let's start ...


            1.Algoritm work

 Oddly, but all ingenious is simple.
So here - with all its glamor
algorithm is very simple. But for
First, a little math for a better
understanding (to whom mathematics is
throat - can not read).
 Yes, I should say that I am not special in
mathematics, and I have to err on the
accuracy of the determinations. I beg for it
forgiveness from the pros.


        1.1 Mathematical model


   First, we introduce the concept of the normal to
surface (if you already know that
is normal - skip this paragraph).
 For the rest I will explain that
normal to the surface in
This point is called
vector with origin in this
points and direction
perpendicular to the plane.
 If you do not know what
is a vector, then try
see the textbook on geometry:) For
better understanding of what is normal
Look at Figure 1.
 Now imagine a kind of rough
surface "in the section.
 For each point of the
surface can be constructed
normal (Fig. 2).
1 - surface.
2 - the point at which we construct

    normal.
3 - the tangent at this

    point.
4 - normal at this point.
5 - the plane on which the "sprinkled" all

    surface roughness.
6 - angle between the plane (5) and the normal

    (4).
7 - normal to the plane (5).
8 - angle between the normals (4) and (7).
 From all this it is important to us is the angle (8)
since in our case, it characterizes
"Degree of light" of a given point
light source located directly above
surface. Ie the smaller the angle,
the larger the lightness of this point.
 Naturally, the case of 2-dimensional
plane we need to know 2 of these
angle - the X and Y, so that
determine the orientation of the normal.
 Well, this seems to be sorted out.
Just want to see that all the foregoing
above do not claim to absolute
correct in terms of physics and
mathematics, but rather just explains
crux of the problem in terms of implementation
effect.
 2. The same is true in terms of computer

 Here, everything is much simpler and easier. We
there is a certain image, to which we want
force to move the spot light. Immediately
I want to note here that the picture
given no flowers, but as it powers
convexity points (height) is point with
"Color" to 7, with the work of the effect will be
appear more "convex" than, for example
point with the "color" 3. Although quite Speccy
fit and a 2-htsvetnaya picture
drawn, for example in Art Studio.
True, we need a picture with
resolution of 1 byte per pixel (as if
we have drawn its attributes). But the problems
such a conversion is no longer relevant.
We believe that we have this picture
there.
 Then the brightness of each point of the output
image is as follows:

x, y - coordinates of the point for which

        is calculated.
lx, ly - the coordinates of the "light source"

 First, find the vector constructed from
Our point to point light source
(Call it L):


      vlx = x-lx; X coordinate of the vector

      vly = y-ly; Y coordinate of the vector

 Now we need to find the normal at this
point. In fact, if we find
normal according to the rules of mathematics, then
it would be quite difficult. However, in
this case, we only need to know
how that the normal is directed, ie know
signs of X and Y components. And this
done very simply - by finding
difference between the values of "height" in
neighboring points, respectively, X and
Y. So we get a pseudovector in the normal
given point (call it N):


       nx = Image (x +1, y)-Image (x-1, y)

       ny = Image (x, y +1)-Image (x, y-1)

nx, ny - the components of N in X and Y.
Image - Our picture (presented in

        a two-dimensional array).

 The rest is easy. We need to
obtain information about the degree illumination
our point of X and Y:


   For X:
, We find the light
col = abs (vlx-nx)
; Limit the number of brightness gradations
if col> 16 then col = 16
; Difx - degree of light our
; On X.
difx = 16-col
; Take away the opportunity to "
; Lighting:)
if difx <0 then difx = 1


   For the Y all the same:
col = abs (vly-ny)
if col> 16 then col = 16
dify = 16-col
if dify <0 then dify = 1


 Well, now we have two components
lighting our point of X and Y (difx and
dify respectively). The total illumination
obtained by averaging them:


            col = (difx + dify) / 2

 Now you only have to put an end
appropriate color - all OK!
, Limits the maximum degree of
; Light
if col> 15 then col = 15
; Take away the opportunity to "
, Lighting and set point
if col> 0 then plot x, y

 As you can see - there's nothing complicated here -
everything is simple and clear. However, there is
one "but" - the fact that he wrote his
effect on the above algorithm and
you are running, unfortunately, did not see
exactly what counts - spot
light instead of the handsome mug will be
be a diamond.
 But the point here is that the approximation
distance of the points was carried out linearly, rather than
the formula for finding the distance between the 2-I
points:


          R = sqrt (sqr (x) + sqr (y))

 For the same, to get as
spot light circle - will need to use
slightly different algorithm:

; First, all the same ...
vlx = x-lx
vly = y-ly
nx = Image (x +1, y)-Image (x-1, y)
ny = Image (x, y +1)-Image (x, y-1)
And now all of a few different ...
difx = abs (vlx-nx)
dify = abs (vly-ny)
col = 15-sqrt (sqr (difx) + sqr (dify))
if col> 15 then col = 0
plot x, y

 I hope you understand? Everything is almost the same
same, only the calculation of intensity
lighting is in accordance with the distance
between the two points above.


   3. Features of the implementation on Speccy

 I hope that any encoder on the Speccy,
looking at the above algorithm
immediately understand that to realize it in the forehead
fail because of the need
computing functions SQR and SQRT. And even
representation of these functions in tabular form
not give an acceptable speed for
result. However, looking more
carefully you will notice that and
will allow us to implement Phong Bump
Mapping on the Speccy. The fact that
limiting the number of gradations of brightness to
16 (which is quite enough), we obtain
that the entire set of values of the calculation
Light:


    col = 15-sqrt (sqr (difx) + sqr (dify))

 safely fit into the plate size
16 * 16 = 256 bytes! Ie having such a plate
we can get the value of light
just for 3-4 assembly instructions, just
taking a number of tables!

 And another possible optimization. If
be used Bump Mapping
for the static image, it can be
convert this image into a table
which each pixel source
images are stored the values of nx and ny. This
further accelerate the process of constructing
image (as an example, see
original text in Appendix).

 All the rest is naturally calculated
without much effort and overall speed
work would be quite acceptable.


        4. Further optimization

 Let's see what else we can
soptimizirovat ... To do this, carefully
look at the dump calculated tables
square root, as well as its
visual representation:
F E D C B A 9 8 7 6 5 4 3 2 1 0
E E D C B A 9 8 7 6 5 4 3 2 1 0
D D C B B A 9 8 7 6 5 4 3 2 1 0
C C B B A 9 8 7 6 6 5 4 3 2 1 0
B B B A 9 9 8 7 6 5 4 3 2 1 0 0
A A A 9 9 8 7 6 6 5 4 3 2 1 0 0
9 9 9 8 8 7 7 6 5 4 3 2 2 1 0 0
8 8 8 7 7 6 6 5 4 4 3 2 1 0 0 0
7 7 7 6 6 6 5 4 4 3 2 1 1 0 0 0
6 6 6 6 5 5 4 4 3 2 2 1 0 0 0 0
5 5 5 5 4 4 3 3 2 2 1 0 0 0 0 0
4 4 4 4 3 3 2 2 1 1 0 0 0 0 0 0
3 3 3 3 2 2 2 1 1 0 0 0 0 0 0 0
2 2 2 2 1 1 1 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 Interestingly, right? :) It turns out that it is
This table creates the appearance of our
spots of light.
 What we do for you?
 Firstly, if we have a table,
forming 1 / 4 spots of light, there is nothing to us
do not interfere with the full image
this spot. Let's say we did it. That
we now have?
 1) The image on which we are going
Let the source of light. As has been
mentioned above - each point should
be represented as a pair of values
(Nx, ny).
 2) Table (and in fact - the same image)
spots of light that will illuminate our
image.
 Now let's again carefully
analyze the algorithm for effect
described above:


                 vlx = x-lx

                 vly = y-ly

 Think, how to vary these
value? Recall that for each frame
lx and ly - constant! And the x and y will
change in 2 nested loops:


   for y = 0 to Image_YSize-1

   for x = 0 to Image_XSize-1

   ; Calculating irradiance at the point (x, y)

   end x

   end y

 Ie it turns out that if in the beginning
construction of each frame, we calculate the vlx and
vly, then later they can be simply
interpolated linearly, through the usual
INC.

 And if you look a little more, we can see
at the beginning of a frame x = 0 and y = 0, ie we
have vlx = lx and vly = ly!

 Go ahead ...


       nx = Image (x +1, y)-Image (x-1, y)

       ny = Image (x, y +1)-Image (x, y-1)

 This, as we have already agreed, is stored
directly into the picture. Ie for
each point we have a 2-hbaytnoe value.
In terms of assembly easiest
get it using POP HL.


             difx = abs (vlx-nx)

             dify = abs (vly-ny)

 Think ... Using the module
here due to the fact that will further
calculation of the root, the argument for
which is known to be
positive. But we have a root
calculated will not, instead we
Using the symmetry in both axes
table (picture a round spot).
So we can get rid of
inconvenient to us the function ABS ():


               difx = vlx-nx

               dify = vly-ny

 No 2 subtraction - is not so hot as quickly.
Can anything be done about it? Yes,
You can! Remember that the image spot
light - round, ie symmetrically on both
axes! This means that inconvenient to us
subtraction can be replaced at a much
more pleasant addition.

 And another thing: if you enter a small
additional condition, then one can
kill two birds with one stone. :) Remember
if we get the values nx and ny
via POP HL, respectively, then we have
is H = ny, and L = nx. So, if we take
that vlx vly and we will move
bytes (which is enough for the eyes even though
that is the number of sign) and vlx + nx
will not cause an overflow - then
we can by putting B = vly and C = vlx
implement both the addition of one team
ADD HL, BC!
 How cool is that? :)

 Remained little things:


     col = 15-sqrt (sqr (difx) + sqr (dify))

     if col> 15 then col = 0

 All this we have already taken into account in constructing
light spot, so we can
just ready to get out of bytes.


                 plot x, y

 ... And upihat it on the screen:)
 Everything!

 Let's see what we got:
; SP = pointer to the image
; DE = pointer on the screen
; B = vly
; C = vlx
POP HL; We got nx and ny. H = ny, L = nx
ADD HL, BC; Fold right H = vly + ny and

            ; L = vlx + nx
LD A, (HL); Take the value of illumination

            , For a given point. How does it

            , It turns out - see below.
LD (DE), A; Piha bytes on the screen.
INC E; proceed to the next byte

            ; On the screen.
INC C; Shift the vlx to calculate

            , The next byte.
 Total obtain 10 +11 +7 +7 +4 +4 = 43 clock cycles to
bytes. Not bad ... :)

 Now, how does it happen that
we just take the value of illumination of the
Table after calculating difx and dify. A
everything is simple - originally to be added vly
byte address location in memory
Table showing spots of light. A
lines of the table are the addresses
multiples of 256. Thus, every time we
after calculating difx and dify (and easier
speaking - after ADD HL, BC) is automatically
get ready indicator in the table
illumination.
 Incidentally, the reduced inner loop can be
accelerate further 6 cycles due to
use the command LDD:

      POP HL

      ADD HL, BC

      LDD
 Here, we automatically receive a correction
DE and BC. It is true that instead of INC C will
performed DEC BC, so there are 2
differences in the construction of tables:
 - The image must reside in
Memory turned the mirror on X (since
so that when DEC C we got to the next
bytes, rather than the previous).
 - Need not to release
overflows (or rather over-) values
in register C, as this will lead to
change in register B, which is undesirable. But
it is easy to solve - the image
light spot in the table simply shifts
by a constant and this constant
will stack to the initial value vlx
a recorded in the register C. However, this
we must not forget that you can not
prevent overflow in the calculation of
vlx + nx (in ADD HL, BC).
 Thus, all resulting in multiple
uncomfortable, but the inner loop will run
at 10 11 16 = 37 cycles / byte!
 Yes, I want to warn that this
inner loop of 37 bars I tried, but
see no reason why he should not
work.


   5. Variations on a theme bump mapping'a.

 The first thing that comes to mind after
view heap implementations bump in mapping'a
demah - "why do they all do
the same?
 Begins to want diversity. This I
and I want to tell in this section.
 The main thing I would like to
change - a form of spots of light. After
Wherever you look - everywhere circles:) And
want something new, interesting ...
Why, for example, no one will bump
mapping, which has a spot of light is
rays? But after these thoughts, I sat down
attempt to implement bump mapping
radically different in appearance and
opportunities. The results of my work you
found in the appendix to the magazine, but here I am
briefly describe the basic idea.
 So, we need to make this circle
move. To do this, each
frame to form an image spot of light.
How can we make the wrong spot
form? It is obvious that it is based on a
Two things - the formula of the circle and the table
sinus. Or rather a cyclic
function should have a radius of a circle in
each point:
10 for i = 0 to 2 * pi step pi/32
20 let x = (f (i)) * cos (2 * pi / i)
30 let y = (f (i)) * sin (2 * pi / i)
40 plot x, y
50 next i

 f (i) here - a function that specifies
radius, such as normal sinus. It is important
only function to be cyclical and
period equal to the number of iterations.
 But consider that each frame - the case
ungrateful, but in fact still have
paint an incorrect figure
gradient, diverges from the center to the edges
and decreasing at a rate proportional
radius of the circle at this point. Therefore,
simpler way:
 1) Create a table of sectors of the circle.
We need to know to point to
coordinates (x, y) sector number
circle, in which this point falls.
I'm not particularly good at math, so do not
I can tell by what formula it all
considered to be:) I went a roundabout way, and
just drew a bunch of divergent
the circle's center line, and end
each of them calculated by the formula
circle. Naturally all of this
not draw on screen and in memory and
line of dots by a byte. Taking
then the central part of the resulting
pictures, I got the desired table.
 But it's unlikely you'll have to do, because
in the source code you will find a ready table.
 2) We also need a table
gradients. It also lies in finished form
in the appendix.
 Now for a spot of light of any
shape all that we need - Apply
gradient corresponding to the radius of our
spot at a given point in the points belonging
relevant sector of the circle. As
this is done - it is better to look
directly in the code. Imho, for any
coder it would be much clearer than
verbal explanation:)


            6. Source code

 Attached you will find 2 set of source
texts.
 The first of these illustrates the effect
in the form in which it is described in
article. Source taken from our demos Binary
Love as This is the easiest to
understanding the code. Particularly fast it does not
call, but the implementation is almost
identical to that described in Article algorithm.
 Source data in a format TASM v3.0. I
I think you will not be difficult to move it
on the assembler you are using.
 The second source is illustrated in the work
effect described in the previous section. K
Unfortunately, due to the specifics of my code,
it is presented in a format TASM v4.12 (c) RST7
and compiled only in this assembly!
More precisely, theoretically it can be transferred to
ALASM and ZX-ASM, but it will require huge
work on the alteration and fitting of the source.
On transport in STORM, I just keep silence - imho
easier to write it all over again, than to move
My source in this assembly ...
 And even more sad for
users assemblers than TASM
v4.12 - such problems will arise
You are constantly trying to use
my source because I'm so used to
the opportunities offered by
TASM, that just can not write code differently.
Naturally, if a source
will be written specifically for the article - it
will compile anywhere, but if
it will be something from my job
source - you have to on any
run TASM v4.12 to compile
him.


              7. Conclusion

 I hope this article will help you
understand the principles of this
effect. You can safely use
annexed source
in their programs, study them, to expose
necessary changes. The only thing that I
forbid to do with their source code -
use them in your programs without
mention of my copyrights. This applies
all of my sources that have already been
published, as well as all those
to be published in future.
 Just want to appeal to all the coders on
Speccy. If you have something about what you
would like to tell all coders on
Spectrum - write, many will
interesting! A very welcome article
like this - with full parsing
principles of any effect
or a description of any special techniques
can improve performance
some effect.
 In addition, it would be interesting to know and
the opinions of those to whom these articles are addressed -
What else Spectrum coders
today?
 In a word - write, your opinions and
support is very important to us!