You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
354 lines
8.1 KiB
354 lines
8.1 KiB
Copyright (c) 1994-1999 Microsoft Corporation
|
|
|
|
ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»
|
|
ºRUNNING THE WALL OF THE TRAPEZOIDº
|
|
ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼÿ
|
|
|
|
|
|
This file contains an explanation of how to run the wall of a
|
|
trapezoid. If there are any questions please feel free to ask
|
|
|
|
Kirk
|
|
|
|
|
|
|
|
|
|
INTRODUCTION:
|
|
|
|
A FIX point number is a 28.4 representation of a real number. Thus
|
|
the real number associated with a FIX point number Q is
|
|
|
|
|
|
Q
|
|
q = ÄÄÄ
|
|
F
|
|
|
|
|
|
The radix shift factor F is has the form
|
|
|
|
|
|
F = 2^L .
|
|
|
|
|
|
In NT Windows the radix shift factor is
|
|
|
|
|
|
L = 4
|
|
|
|
|
|
and
|
|
|
|
F = 2^4 = 16 .
|
|
|
|
|
|
The real values of the endpoints of the line are:
|
|
|
|
|
|
|
|
Ú M0 N0 ¿
|
|
P0 = (x0,y0) = ³ ÄÄÄÄ , ÄÄÄÄ ³ ,
|
|
À F F Ù
|
|
|
|
|
|
Ú M1 M1 ¿
|
|
P1 = (x1,y1) = ³ ÄÄÄÄ , ÄÄÄÄ ³ .
|
|
À F F Ù
|
|
|
|
|
|
|
|
The equation of the wall line is
|
|
|
|
|
|
(x1 - x0)
|
|
x(y) = ÄÄÄÄÄÄÄÄÄ (y - y0) + x0 .
|
|
(y1 - y0)
|
|
|
|
|
|
|
|
I can use the FIX point representation of the real coordiantes to
|
|
provide an alternative expression of the equation of the wall line.
|
|
|
|
|
|
|
|
(M1 - M0) Ú N0 ¿ M0
|
|
x(y) = ÄÄÄÄÄÄÄÄÄ ³ y - ÄÄÄÄ ³ + ÄÄÄÄ .
|
|
(N1 - N0) À F Ù F
|
|
|
|
|
|
|
|
At this point I shall introduce some convenient notation.
|
|
|
|
|
|
|
|
DM = M1 - M0 ,
|
|
|
|
|
|
DN = N1 - N0 > 0 ,
|
|
|
|
|
|
m0 = floor(x0) = M0 >> L ,
|
|
|
|
|
|
n0 = floor(y0) = N0 >> L ,
|
|
|
|
|
|
qx = floor(F * frac(x0)) = M0 - (m0 << L) ,
|
|
|
|
0 <= qx < F
|
|
|
|
|
|
qy = floor(F * frac(y0)) = N0 - (n0 << L) ,
|
|
|
|
|
|
0 <= qx < F
|
|
|
|
|
|
Rsup = F DN .
|
|
|
|
|
|
|
|
Note that m0, n0, qx, and qy are integers.
|
|
|
|
This leads to the following form for the equation of the line:
|
|
|
|
|
|
|
|
DM Ú qy ¿ qx
|
|
x(y) = ÄÄÄÄ ³ y - n0 - ÄÄÄ ³ + m0 + ÄÄÄÄ
|
|
DN À F Ù F
|
|
|
|
|
|
|
|
Note that x and y are real numbers while the offsets m0 and n0 are
|
|
integers.
|
|
|
|
|
|
According to the filling conventions of Windows, the position of the
|
|
wall at y = j is given by:
|
|
|
|
|
|
|
|
i(j) = ceil ( x(j) )
|
|
|
|
|
|
Ú DM Ú qy ¿ qx ¿
|
|
= ceil ³ ÄÄÄÄ ³ j - n0 - ÄÄÄ ³ + m0 + ÄÄÄ ³
|
|
À DN À F Ù F Ù
|
|
|
|
|
|
Ú DM Ú qy ¿ qx ¿
|
|
= m0 + ceil ³ ÄÄÄÄ ³ j - n0 - ÄÄÄ ³ + ÄÄÄ ³
|
|
À DN À F Ù F Ù
|
|
|
|
|
|
Ú DM [ F(j - n0) - qy ] + DN qx ¿
|
|
= m0 + ceil ³ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ³
|
|
À F DN Ù
|
|
|
|
|
|
Ú DM [ F(j - n0) - qy ] + DN (F + qx) - 1 ¿
|
|
= m0 + floor³ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ³
|
|
À F DN Ù
|
|
|
|
|
|
|
|
|
|
The quotient and remainder is calculated just once for the initial value
|
|
of j = j0.
|
|
|
|
|
|
|
|
DM [ F(j0 - n0) - qy ] + DN (F + qx) - 1 R
|
|
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ = Q + ÄÄÄÄ ,
|
|
F DN F DN
|
|
|
|
|
|
where 0 <= R < F DN.
|
|
|
|
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
|
|
³ CAUTION ³
|
|
³ ³
|
|
³ The programer must be cautions in the case where the numerator ³
|
|
³ is negative. The C standard does not spcecify how the quotient ³
|
|
³ should be rounded in this case. Just make sure that you adjust ³
|
|
³ things so that R is positive! See Appendix I. ³
|
|
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
|
|
|
|
|
|
Having done the division properly we are left with the answer
|
|
|
|
|
|
|
|
Ú R ¿
|
|
i(j) = m0 + floor³ Q + ÄÄÄÄ ³
|
|
À F DN Ù
|
|
|
|
|
|
Ú R ¿
|
|
= m0 + Q + floor³ ÄÄÄÄ ³
|
|
À F DN Ù
|
|
|
|
|
|
|
|
= m0 + Q
|
|
|
|
|
|
|
|
Now upon traversal the value of j changes by dj = +1 or -1. This will
|
|
affect the value of i(j) as follows:
|
|
|
|
|
|
i(j+dj) =
|
|
|
|
|
|
Ú R dR ¿
|
|
= m0 + floor³ Q + ÄÄÄÄ + di + ÄÄÄÄÄij
|
|
À F DN F DN Ù
|
|
|
|
|
|
Ú R + dR ¿
|
|
= m0 + Q + di + floor³ ÄÄÄÄÄÄÄÄ ³
|
|
À F DN Ù
|
|
|
|
|
|
Ú R + dR ¿
|
|
= i(j) + di + floor³ ÄÄÄÄÄÄÄÄ ³
|
|
À F DN Ù
|
|
|
|
|
|
|
|
Where we have introduced di and dR defined as follows:
|
|
|
|
|
|
|
|
dR F DM dj
|
|
di + ÄÄÄÄÄÄ = ÄÄÄÄÄÄÄ ,
|
|
F DN F DN
|
|
|
|
|
|
|
|
where 0 <= dR < F DN . [ Be careful about negative numerators. See Appendix I].
|
|
|
|
/************************************************************************/
|
|
|
|
ALGORITHM 0: <initialize: i, di, R, dR>
|
|
|
|
INPUT:
|
|
|
|
(i) (x0,y0) = (M0/16,N0/16) and (x1,y1) = (M1/16,N1/16) with y1 > y0.
|
|
|
|
(ii) j0 such that y0 <= j0 <= y1.
|
|
|
|
(iii) dj = +1 or -1.
|
|
|
|
OUTPUT:
|
|
i, di, R, dR, Rsup
|
|
|
|
{
|
|
DM = M1 - M0;
|
|
DN = N1 - N0;
|
|
m0 = M0 >> 4; // signed shifts work for all numbers!
|
|
n0 = N0 >> 4;
|
|
qx = M0 - (m0 << 4); // 0 <= qx < 16
|
|
qy = N0 - (n0 << 4); // 0 <= qy < 16
|
|
Rsup = DN << 4;
|
|
|
|
// Find the quotient and remainder 0 <= R < Rsup.
|
|
// Be careful about using '/' and '%' they do funny things when
|
|
// the numerator is negative
|
|
|
|
// Calculating i and R
|
|
|
|
|
|
|
|
R DM*[16*(j0 - n0) - qy] + DN*(16 + qx) - 1
|
|
i + ÄÄÄÄ = ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ;
|
|
Rsup Rsup
|
|
|
|
i += m0;
|
|
|
|
|
|
|
|
// Calculating di and dR:
|
|
|
|
// Similarly, be cautious about the next step. It must satisfy
|
|
// 0 <= dR < 16 * DN
|
|
|
|
|
|
|
|
dR 16*DM*dj
|
|
di + ÄÄÄÄÄÄÄ = ÄÄÄÄÄÄÄÄ ;
|
|
Rsup Rsup
|
|
|
|
}
|
|
|
|
/*********************************************************************/
|
|
|
|
ALGORITHM 1: <Run the wall of the trapezoid>
|
|
|
|
INPUT:
|
|
|
|
(i) (x0,y0) = (M0/16,N0/16) and (x1,y1) = (M1/16,N1/16) with y1 > y0.
|
|
|
|
(ii) j0 such that y0 <= j0 <= y1.
|
|
|
|
(iii) dj = +1 or -1.
|
|
|
|
OUTPUT:
|
|
|
|
An array of integers i0, i1, i2, ... that represent the position
|
|
of the trapezoid wall at the rows with y-coordinates:
|
|
j0, j1 = j0 + dj, j2 = j1 + dj, ...
|
|
|
|
{
|
|
<initialize: i, di, R, dR, Rsup>;
|
|
<process row i>;
|
|
while (<not done>)
|
|
{
|
|
i += di;
|
|
j += dj;
|
|
R += dR;
|
|
if (R >= Rsup)
|
|
{
|
|
R -= Rsup;
|
|
i++;
|
|
}
|
|
<process row i>;
|
|
}
|
|
}
|
|
|
|
**********************************************************************
|
|
|
|
APPENDIX I
|
|
|
|
Q: How do I handle those negative numerators anyway?
|
|
|
|
A: Easy, consider the following division with a negative numerator
|
|
and positive denominator.
|
|
|
|
|
|
R -A
|
|
Q + ÄÄÄ = ÄÄÄ , A>0, B>0
|
|
B B
|
|
|
|
First we convert the problem to one with positive numerator and
|
|
denominator. Let
|
|
|
|
|
|
A-1
|
|
Q' = floor( ÄÄÄ ) ,
|
|
B
|
|
|
|
R' = A - 1 - Q'B = (A - 1) mod B .
|
|
|
|
|
|
Then the desired result is ...
|
|
|
|
|
|
Q = - (Q'+ 1) ,
|
|
|
|
|
|
R = B - R'- 1 .
|
|
|
|
|
|
It is a useful exercise to prove this result.
|