Creative - Algorithms and code: clipping of lines and Bezier curves.

<b>Creative</b> - Algorithms and code: clipping of lines and Bezier curves.

     Glad to see you here Reader!

 If you climbed up here, then one of two things: either
you really came here for knowledge
or simply to see whether there
images ... But in any case, glad you got
see.

 To begin with, that all it is presented. I
I am not someone other than the principal and
the only coder of Energy Minds in
which I have nicknamed Priest'om. I hope
you heard about us.

 And now, what I still suggest
today for your consideration:


   1. Clipping lines.

   2. Bezier curves.


-----------------------------------------
            Clipping line
-----------------------------------------
 Maybe someone else did not think that
a clipping, and so I immediately
explain it. Word clipping occurred
from the English "to clip", which translated
our means to cut off (cut,
crop). Thus, clipping
line is cut off beyond the edge
screen all of the specified interval. At the same time
the segment can only see it
part.

 So why cut off ... As already
written in many publications, it is time
when it is very often necessary to use
vector graphics. And when writing
programs in BASIC often
need to draw an object
often leaving behind the screen,
thereby causing an error and,
respectively, stop the program. A
writing for the BASIC routine is not
meaning, it is only slow down the already his
slow calculations. And then there is one
Output: assembler.

 The following algorithm and its
implementation in assembly language, are simply
examples and criticism of it is not necessary.

 So the basis of the algorithm was based on the
Sutherland-Cohen.

 First and foremost we need to know
where each of the endpoints.
To do this, use the bit representation
of the end of the segment with respect to
the visible rectangle (we have this
rectangular screen appears), ie:


   Bit 0 - the point lies to the left pryamoug.

   bit 1 - -----//---- above pryamoug.

   bit 2 - -----//---- right pryamoug.

   Bit 3 - -----//---- pryamoug below.

 Assume that x1, y1 coordinates of the first
end of the segment, and x2, y2, respectively,
coordinates of the second end of the segment. Now
need to get two 4-bit code for both
ends. But first let us agree that
the origin is in the upper left
corner, as on all other platforms and
nearly 99% of Spectrum programs
written in assembler. So for
Spectrum screen, it looks like this:

X1 = 0, the left edge of the visible
X2 = 255; the right edge of the visible
Y1 = 0, the upper edge of the visible
Y2 = 192; the lower edge of the visible
code = 0; variable for the 4-bit code
if x <X1 then code = code +1
if y <Y1 then code = code +2
if x> X2 then code = code +4
if y> y2 then code = code +8

 With this algorithm, we obtain two
code for both ends.

 And now we make very clipping on
already known to the provisions of the endpoints.

 if bit_0 = 1; clip that left the area

    then y1 = y1 + (y2-y1) * (X1-x1) / (x2-x1)

     x1 = X1
 if bit_1 = 1; clip, then that is higher than the field

    then x1 = x1 + (x2-x1) * (Y1-y1) / (y2-y1)

    y1 = Y1
 if bit_2 = 1; clip that the right of the field

    then y1 = y1 + (y2-y1) * (X2-x1) / (x2-x1)

    x1 = X2
 if bit_3 = 1; clip, what is below the

    then x1 = x1 + (x2-x1) * (Y2-y1) / (y2-y1)

    y1 = Y2

 After this protsedurki verified
remained whether the endpoint behind the screen, if
did not go, then treat the other end,
In either case, repeat the procedure
(Such repetition in practice, I do not
met, everything should be the first
times).

 By the way as you can see, the procedure
clip only endpoint x1, y1. For
In order to otklipit second end,
sufficient to interchange the coordinates
endpoints, rather than overwrite
procedure specifically for the second end.

 In conclusion, this part I will say that
application is the source "CLIPPING" in
which implements all the above. He
written as a text file, but with
sinktasisom assembler STORM. Source
tested and works without glitches (I have already
apply in their prog:).

 And more ... In the source used in excess
slow process of division and multiplication, and
Therefore they need a good replacement
:)...

-----------------------------------------
              Bezier curves
-----------------------------------------
 I'm afraid that you have read the first few
lines of the previous part, and knew that
some simply clipping clipping
segment, immediately rushed to read this part,
with an even more obscure name. But can
be it for the better. So get down ...

 Bezier curves are used to construct
smooth curves (sounds silly, does not it?)
on any given number of points.
And the curve is tangent to
educated segments of the data points.
It sounds dull, but now try to explain
human.

 Let's say you felt an urge to create
a scalable font. Ie at
increase in character, it retains its previous
form, rather than when the increase in pixels
are the size of a football field (to
such fonts are fonts. chr with
PCshki). So, usually, these fonts
given set of vertices that
subsequently joined by segments. This
method is acceptable for 80% of character
set. Why? And how do you specify the letter
"O"? Someone will say thought, it is possible
the distance between the peaks decrease
so much so that several such segments
will go for a smooth curve.
 Yes, I say, I agree. But this will to
As long as we do not need to increase
symbol, say, a kind of once in 10 ... And what
happen? The distance between the peaks also
increase by 10 times and it will be far
not a smooth curve, and the broken line and not
smooth. Here and can come to the rescue
these same curves. One of the advantages of these
curves, they are always smooth, begin
always in the first specified point and
ends exactly at last assigned
point. For another of the advantages can be
include the fact that the curve may intersect
itself and not once (as in
the example below, only once,
as we will have only 4 points defining
curve). By the way quite remarkable
that if we interchange any 2 (or
more) points, then changing the whole shape of the curve
(Logical nowhere:).
 Let us return to the character "O". For instance, we
need to ask the right (left)
half of the symbol. Promuchavshis half an hour we
finally succeeded in obtaining a smooth
pseudo-curve of the segments and it is us
It took on a conservative estimate, at least 10
tops (still depends on the
original character since than it is, the
more points required to represent
curve). And for our curves will be
enough, and 4 vertices.


   Thus, the curve described by the vector
equation:


        m

      _____

      \ | I i m-i
 r (t) = \ C * t * (1-t) * V

       / M i

      /____|

        i = 0


     i m!
where C =--------- and 0 
COORDS PUSH IX

        LD B, 8; count is directed. points
LAPS LD D, (IY); take counted
; Value for the point

        LD E, (IX); take one of coordination, Nat x or y (set 
caller ; Procedure)


        INC IX, IX, IY

        CALL MULT; D * E = HL

        PUSH HL; keep a sharp result

        DJNZ LAPS


        LD HL, 0, sum = 0
.8 POP DE: ADD HL, DE; sum + Save. means.

        LD A, H

        RL L; judging by the senior bat
        ADC A, 0; rounded in bolshii. or
; Downwards

        POP IX

        RET

; HL = D * E
MULT LD H, D, D, 0, L, D
.8 ADD HL, HL: JR NC, $ +3: ADD HL, DE

        RET

And the coordinates of control points
UPRAVL DB # 75, # 02

        DB # 9F, # 03

        DB # C2, # A7

        DB # D6, # 4E

        DB # 51, # 9A

        DB # C8, # B8

        DB # 02, # 33

        DB # 2F, # 05

; Constants for each curve
SPLdata INCB "SPLdata"

 The procedure for drawing a point at everyone
Therefore I did not write. Asmovy text
grabanut straight from my working prog,
which lies in the application ...

 Here at last, and all ... Who did not understand I do not
wrong :)... Joke ... Here I detail
all explained that I outdid authors
book from which I learned all this. There
All this is set out on page 1.5-2, and
such forcible figures and mathematical
notation of all preukrasheno ... Horror ...
And 90% of what I chewed mulberries,
there is no razyasnyaetsya - adopted
as for the well-known:)


  And a couple more words ... In Spekovskom version
magazine will be available the following files:
 Bezie.B - Example for Busick
 Spline.B - counting-table
 SPLdata.C - already computed table
 SPLINE.C - a text file for converting
in STORM heaped procedures splines.

 By the way is not worth spit seeing
result of the program, because accuracy
computation is very low 1 / 256. More
better results can be
using a precision 1 / 65535. Ie all
fractional numbers (in this table)
multiplied by 65535, and ACME operate
two or more byte values that
certainly entail the loss of
Performance ... Decision for you
Gentlemen ...

 If you use STE in their
prog, at least hi pass, that, if
:). Copyright It's obviously not mine, and Mr.
Bezier ... :)
__________________________________________
 In the next room is likely to be
algorithm for fast fill any closed
areas, the calculation of light
landfills and other Labuda. So
wait ... Before the meeting, gentlemen coders!


                             Bye!

                             Priest / EM / XPJ
__________________________________________
DI: HALT