@PEN1
     *****************************************************************
     ***    Demonstration of Line Clipping in STOS Basic.          ***
     *****************************************************************

@PEN2
               by Jason J. Railton, for ICTARI User Group.




@PEN3
  This file is not intended to be read from the Desktop, but it may be
printed from there.  Run the program 'CLIPPING.PRG' or 'CLIPPING.BAS' with
this file ('CLIPPING.TXT') in the current directory.  The demonstration
program will display this file page by page, and insert graphical displays
at appropriate points.
@PEN1

@PAGE
  I hope you all saw last month's demonstration of calculating relative
positions from a moving, turning viewpoint.  Note that that was only for
points on a simple 2-D map.  3-D games such as flight simulators use those
same principles in three axes (X and Y for position on a map, and Z for
height), not just two.  They also have three angles of rotation for roll,
pitch (angle of elevation of the aircraft's nose) and yaw (heading, or
compass bearing), so three sets of those rotation formulae are combined
into some large equations.

  What I didn't have time to describe in detail before was the system of
angles I was using.

@PAGE
  When drawing a map, compass bearings are given going round clockwise,
strating from zero at due North (straight up the map).  When talking
geometry, we have the X-axis to the right (East on a map) and the Y-axis
straight up (North on a map).  Angles are then given (in degrees or radians)
as going round anti-clockwise, from zero on the X-axis.

  So, a horizontal line running to the right has an angle of 0 degrees.
A 30 degree line would run to the right and up a bit, and a line straight
up would have an angle of 90 degrees.  180 degrees is to the left, and
270 degrees is down.

@PAGE
  Now the position of the viewer on the map was given in X and Y co-
ordinates and a rotation angle.  The viewer would be looking due East along
the X-axis when this angle is zero.

  When I want to display 3-D graphics, I need to have three values.  One
is how far across the view a point is, from left to right.  The second
is how high above or below the viewer it is, and the third is how far
dead ahead of the viewer it is.

  The second point, height, is constant in my maze program.  The floor and
ceiling are always at the same height.  As for the first and third, these
are what I get from the rotation formulae.  I want these as simple X and Y
co-ordinates.  X being left to right across the view, and Y being distance
into the view.  For this reason my formulae must give me an extra 90 degrees
of rotation.

@PAGE
  This means that for a viewer looking along the X-axis, at zero degrees,
any points along the X-axis of the map are directly in front of the viewer.
So, points on the X-axis are turned 90 degrees so as to lie along the
view's Y-axis, into the screen.  Points lying on the Y-axis of the original
map, to the left of the viewer, get turned around to the view's negative
X-axis, so that they are drawn to the left of the screen.

  Points on the map's negative Y-axis (downward on the map) are turned
round to the view's positive X-axis, so that they appear to te right on the
final view.

  Imagine yourself standing on the map, looking East, and then think
where things placed on the compass points would appear to you.

@PAGE
  Now, I know I said last month that I'd go on to describe how to turn
relative co-ordinates into 3-D views, but there is one important step to go
before you can start drawing mazes in 3-D.  Small objects on the screen
aren't much of a problem, but when you start drawing an environment which
surrounds the viewer, some problems start to arise.

  When working in 3-D, most objects consist of straight lines, or polygons
(shapes with straight-line edges) which are described mathematically by
sets of co-ordinates.  The whole idea of a 3-D object is that it can be
viewed from any angle at any distance.  The drawback is that if you allow
the viewer complete freedom of movement, you don't know how big your objects
will appear on screen, and where they will be drawn.

  Let us assume for the moment that you just wish to draw the outline of
a cube on screen.  If the cube is small, and in the middle of the screen,
it doesn't present much of a problem to draw.  If the viewer moves in closer
to the cube, it will appear larger and larger, until it fills the screen.
If it gets too large, it may not entirely fit on the screen.

@PAGE
  So, sometimes lines can lie partly or wholly off the edge of the
screen, or outside the screen window in which the graphics are to
appear.  In the case of graphics in a window, this can spoil the
display.  With graphics being drawn off the edge of the screen by your
own code, you risk corrupting memory outside the screen memory area,
and crashing the computer.

  The following demo shows this happenning with a simple rectangular
shape, supposed to be drawn within a window on screen.


N.B. STOS Basic will actually stop with an error report if you try and draw
a line off screen.

@PAGE
Demonstration #1: '...sometimes lines can lie partly or wholly off the edge
of the screen, or outside the screen window in which the graphics are to
appear...'

@DEMO1
@PEN1
  So, before we can start drawing 3-D objects, we need to have a line
drawing routine that will allow for lines going off the edge of the screen.
The way to do this is simply to add a piece of code at the start of your
line drawing routine to cut off any part of the line which lies off the
screen, and only hand over to the drawing routine parts of lines which are
within the screen area.  This process is called 'clipping' the lines.

  This has to be working perfectly before you can start asking it to draw
3-D graphics, or else your program will fail and you won't know if it's
the 3-D maths or the graphics routines at fault.  The way I worked was to
write the program in STOS, building it up bit by bit (regular readers will
have seen my earlier demonstrations of cubes before I moved onto a full
maze) and then gradually replacing more and more of the BASIC with machine
code.  First the fill routines, then the line drawing, then the maths for
rotating the map, and finally the control routines to allow the program
to run on its own.

  (Don't worry about the word 'window' on the previous page.  It's just
that, for demonstration purposes, I'm going to clip the graphics to a
rectangle which is smaller than the entire screen, so that I can show you
what happens.  You may want to do this if your 3-D view has a fancy
border).

@PAGE
  The first thing to do is define the line to be clipped.  I'll use a
line defined by two points P and Q.  Each of these has co-ordinates
(Px,Py) and (Qx,Qy).

@DEMO2
@PEN1
  This line must be clipped against each edge of the screen.  First,
I'll start with the left-hand edge of the screen, to explain the
principles in detail.


  Now, there are four possible results from checking the line against
the left hand edge of the screen/window:

  1) The entire line lies to the left of the left-hand edge.

  2) The entire line lies to the right of the left-hand edge.

  3) P is to the left, but Q is to the right, so the line crosses
     the screen edge.

  4) P is to the right, but Q is to the left, so the line again
     crosses the screen edge.

@PAGE
  To analyse this mathematically, we need to define some more points.
Let's say that the left-hand edge of the screen, where the line is to
be clipped, is a vertical line at position Cx.  The four cases are
now...

1) If both Px and Qx are less than this value Cx, the entire line lies
   off the left-hand edge, and need not be drawn at all.

2) If both Px and Qx are greater than Cx, then the line lies to the
   right of this edge, so this stage of the clipping can be skipped.

3) If Px is less than Cx, but Qx is greater than or equal to Cx, then
   part of the line (the P-end) lies off screen, and part (the Q-end)
   is on screen, and should be drawn.  This is the case I will examine
   in detail.

4) If Px is greater than Cx, but Qx is less than Cx, then the P-end
   lies on screen, but the Q-end is off the left hand side of the
   screen.  More on this later.

@PAGE
  Look at the following diagram.  The vertical line represents the
left-hand edge of the screen at position Cx.  The line P-Q crosses it
at point C (Cx,Cy).  To clip the line we need to calculate Cy.  Then
we can draw line C-Q on screen [That is, draw (Cx,Cy)-(Qx,Qy)].

@DEMO3
@PEN1
  To find point C, we are going to work out what fraction of the line
is off the left-hand edge of the screen, then move that far along the
line to reach the clipping point C.  The line to draw is then the on-
screen part C-Q, and we forget about the off-screen part P-C.

@PAGE
 This process is made possible by the fact that the fraction of part
P-C of the overall line P-C-Q is the same whether we consider:

1) Distance along the line,  =    |PC| / |PQ|
2) Distance horizontally,    = (Cx-Px) / (Qx-Px)
3) Distance vertically,      = (Cy-Py) / (Qy-Py)

  The result of all three of the above is the same (although a
horizontal line would give zero/zero for the third option, and crash,
so we won't be actually doing that sum).

  The first sum requires a square root in the Pythagorus theorem to
work out lengths along the lines (that's where you do SQR(x^2 + y^2)
to find a distance), so we'll forget about that one.

  Of equations 2 and 3, we know Px, Py, Qx, Qy and also Cx.  The only
unknown is Cy, so here's how to solve it.  First we note that 2 and 3
give the same fraction of the line's length, so 2) = 3)...

@PEN2
  (Cx-Px) / (Qx-Px)   =   (Cy-Py) / (Qy-Py)
@PEN1

@PAGE
Now, taking it slowly...

@PEN2
  (Cx-Px) / (Qx-Px)   =   (Cy-Py) / (Qy-Py)
@PEN1

I'll re-write that...

@PEN2
          (Cx - Px)       (Cy - Py)
         -----------  =  -----------
          (Qx - Px)       (Qy - Py)
@PEN1

Now to multiply each side by (Qy-Py).  Watch what happens...

@PEN2
      (Qy - Py) * (Cx - Px)        (Qy - Py) * (Cy - Py)
    -------------------------  = -------------------------
      (Qx - Px)                    (Qy - Py)

@PEN3
                                   '---.----'
                                       :
@PEN1
                              This is like saying 'a/a' or '3/3',
                            simply a value of 1.  So this side is
                            now saying '1 * (Cy-Py)'.
@PAGE
So, in effect:

@PEN2
      (Qy - Py) * (Cx - Px)        (Qy - Py) * (Cy - Py)
    -------------------------  = -------------------------
      (Qx - Px)                    (Qy - Py)
@PEN1

becomes:

@PEN2
      (Qy - Py) * (Cx - Px)
    -------------------------  =   (Cy - Py)
      (Qx - Px)
@PEN1

Adding Py to both sides...

@PEN2
           (Qy - Py) * (Cx - Px)
  Py  +  -------------------------  =  Py  +  (Cy - Py)
           (Qx - Px)
@PEN1

@PAGE
Simplifying:

@PEN2
           (Qy - Py) * (Cx - Px)
  Py  +  -------------------------  =  Py  +  (Cy - Py)
           (Qx - Px)
@PEN3
                                       '------.------'
                                              :
@PEN1
                          This part says:     Py + Cy - Py
                          Re-arrange to get:  Py - Py + Cy
                                         or:     0    + Cy
                                    or just:            Cy

This gives:

@PEN2
           (Qy - Py) * (Cx - Px)
  Py  +  -------------------------  =  Cy
           (Qx - Px)
@PEN1

So now we know how to find Cy...

@PAGE
  Now, the point C is defined by co-ordinates Cx and Cy.  We know
where Cx is (the edge of the screen, for example '0'), and we can now
work out Cy using:

@PEN2
               (Qy - Py) * (Cx - Px)
Cy  =  Py  +  -----------------------
                     (Qx - Px)
@PEN1

  To implement this, do 'Qy-Py' and 'Cx-Px' first, and multiply the
results together.  Divide the answer by the result of 'Qx-Px'.
Finally, add Py to get the value of Cy...

@PEN2
Cy = Py + [  { (Qy-Py) * (Cx-Px) }  /  (Qx-Px)  ]
@PEN1

  Now you simply replace the values of Px and Py (the off-screen end
of the line) with the values of Cx and Cy.  Your line drawing routine
will suspect nothing and simply draw the line C-Q (all on-screen)
instead of P-Q (partially off-screen).

@PAGE
  All very well, you may say, but what if it is the P-end that is on-
screen, and the Q-end that is off-screen?

  Well, in that case, you use exactly the same value of Cx, and
exactly the same formula for Cy.  You just have to replace Qx and Qy
(not Px and Py) with the values of Cx and Cy.

  This makes your line drawing routine draw line section P-C, not C-Q.

@PAGE
  As for the right-hand side of the screen, again we use exactly the
same formula.  You just put the position of the right-hand edge in as
Cx (e.g. 319 for Low res or 639 for Med/Hi res), and calculate Cy as
before.  Point C is then a point on your line just on-screen, and you
just replace the off-screen point (either P or Q) with point C as
before.

  Just remember that your line might extend from off one side of the
screen, right the way across and off the other.  To get round this,
simply clip first one edge, and then the line which results from that
process is clipped against the opposite edge.  The line resulting from
the second clipping function is the one you draw.

  In this way, the line is slowly trimmed down by each edge-clipping
function in turn, until it is ready to be drawn.

  The next demo shows this clipping in action...

@PAGE
Where a point (end of a line) extends off the right or left edge of
the defined window, that point is replaced with the calculated edge-
point C...
@PEN2
Cx = x of edge,  Cy = Py + [   { (Qy-Py) * (Cx-Px) }  /  (Qx-Px)  ]
@PEN1

@DEMO4
@PEN1
  Now we come to the clipping at the top and bottom of the screen.
This works in exactly the same way as clipping at the right and left-
hand edges, we just swap all the Xs for Ys and vice-versa.

  In this case, we know the vertical position of the screen edge, so
we know Cy, the Y-co-ordinate of point C, just on screen.  We have to
work out Cx.  We could draw the same diagram as before, but swapping
the X and Y co-ordinates, but the result is obvious.  It's just the
same formula with the Xs and Ys exchanged:

@PEN3
    Cx = Px + [   { (Qx-Px) * (Cy-Py) }  /  (Qy-Py)  ]
@PEN1

  Again, first check to see if Py and Qy are both off the top or both
off the bottom of the screen.  If they are, no part of the line need
be drawn.

  If both are within the vertical screen range (e.g. 0-199 Lo/Med res
or 0-399 in Hi res), then the whole line can be drawn.

  If one end is off screen, replace that end's X/Y co-ordinates with
the values of Cx and Cy for that line at the screen edge.

@PAGE
  This is the demonstration of the full line clipping in action, but
I've not finished yet.  Anyway:
@PEN2
Cx = x of edge,  Cy = Py + [   { (Qy-Py) * (Cx-Px) }  /  (Qx-Px)  ]
@PEN3
Cy = y of edge,  Cx = Px + [   { (Qx-Px) * (Cy-Py) }  /  (Qy-Py)  ]
@PEN1

@DEMO5
  Finally, some tips on putting all this together.

  Start with a simple line-drawing routine.  If you're using STOS,
that's simply the command:

@PEN2
DRAW Px,Py to Qx,Qy
@PEN1

  Generate Px,Py,Qx and Qy at random, or from keyboard entry, and plot
some lines within the screen area.

  If you're using machine code, look on ICTARI disk #31 for Peter Hibbs'
line-drawing code, or write your own.  (Back issues available from the
usual address, etc...)

@PAGE
  Next add some code between where you generate the values and where
you plot the lines.  This code should skip the draw command if both
points are to the left of the screen edge.

  Then add some lines to check each end of the line against the left
screen edge.  If either point is off the screen edge, calculate Cy,
and replace the point's co-ordinates with (Cx,Cy).

  Increase the range of the numbers you're generating to test the
program.  Give it some points deliberately off the left-hand edge, and
some valid points, to test it.

@PAGE
  Now add similar code to check and clip at the right-hand edge.

  Test this, then do the top, and finally the bottom of the screen.

  Save a copy of this, and then see if your code can be speeded up at
all.

@PAGE
  Bear in mind that a line just off the top of the screen may still be
clipped in line with the left and right edges, before being rejected
by the top edge test.  This is necessary, as you can not be sure the
line is completely off the top of the screen until it has been clipped
to the left and to the right.

  Do the checks and clipping for the left and right edges separately
from those for the top and bottom edges.  Do not mix the two.

  However, you could do all the top and bottom checks and clipping
first, then the left and right checks and clipping.  Pick whichever
you think will reject the most lines as early as possible, to speed
things up.

  In my maze game, the walls of the maze extend far to your left and
right, and not so much above or below.  It makes sense to do the left
and right checks first, as this rejects the most lines at the first
stage of checking and so saves time.

@PAGE
  Finally, a note on programming the formula for calculating Cx or Cy:

@PEN2
   Given Cx, Cy = Py + [   { (Qy-Py) * (Cx-Px) }  /  (Qx-Px)  ]
@PEN3
or given Cy, Cx = Px + [   { (Qx-Px) * (Cy-Py) }  /  (Qy-Py)  ]
@PEN1

  The result of either formula is required as a screen co-ordinate, an
integer value.  However, doing a division of one number by a number of
similar size using integer maths (e.g 150/200) gives a very inaccurate
result.  So, is it possible to avoid real numbers?  This would
certainly help with machine code.

  The answer is 'yes'.  By carefully ordering the formula when you
program it in, you can save the divide instruction until the end, so
it is the last operation (well, next-to-last; we still have to add Px
or Py, but by then we're back to integers).

  By performing the multiplication first, we ensure that the number
we're dividing into later is much larger than the number we're
dividing by, so that an integer result isn't too bad.

@PAGE
  Another tip - if you really want to use fractions in machine code,
but don't want to write floating-point mathematics libraries, simply
multiply all your numbers by 2, 4, 256, 65536 or whatever (shift them
left a few places I mean) and do all the maths with the larger values.

  For example, if you multiply your numbers by 256 (shift left 8
places) you can use numbers from -128.0 to +127.9961, with an accuracy
down to 1/256 (0.0039), in 16 bits.  That means you can accurately
represent numbers to two decimal places, and you can still perform the
16-bit operations add, subtract, divide and multiply on these values.

  Just remember that when you divide or multiply, the results will be
16 (not 8) bits off, and will require shifting by 8 bits to correct
this.  Also remember to shift your numbers back when you want integer
values.

@PAGE
  If you want to write 32-bit multiply and divide code, to complement
the 32-bit add and subtract functions (it's not that hard - for the
divide you just DIVS once on the top 16 bits on their own, then DIVS
the remainder from that operation with the other 16 bits stuck on, and
stick the results together), then you can use 32 bit numbers with the
top 16 bits as the integer part, and the bottom 16 bits the fraction.

  This gives you a range of -32768.0 to +32767.99998, with an accuracy
of 1/65536 (0.0000153) or slightly better than 4 decimal places (not
quite accurate enough for 5).

  Also, taking an integer value is as simple as doing the 'SWAP'
instruction, and you have all the 16-bit functions on hand for your
integer maths.

  To convert an integer into a fraction of this sort, SWAP it and
CLR.W
to clear the fractional part (the bottom 16 bits), whether it's a
positive or negative number.

  Anyay, one last look at that clipping demo...

@PAGE
The formulae for clipping to the edge of the screen are:

@PEN 2
Cx = x of left/right edge, Cy = Py + [ {(Qy-Py) * (Cx-Px)} / (Qx-Px) ]
@PEN3
Cy = y of top/bottom edge, Cx = Px + [ {(Qx-Px) * (Cy-Py)} / (Qy-Py) ]
@PEN1

@DEMO5
@PEN1
Bye for now!

@EOF