Giáo trình Đồ họa máy tính 1 - Phạm Tiến Sơn

ˆ.ng. Neˆ´u, cha˙ˇ’ng ha.n ca´c d¯a gia´c
la` h`ınh chieˆ´u cu˙’a ca´c d¯a gia´c trong khoˆng gian ba chie`ˆu th`ı d¯oˆ. u.u tieˆn d¯u.o.. c d¯aˇ. t tu.o.ng th´ıch vo´.i khoa˙’ng
ca´ch tu`. vi. tr´ı maˇ´t quan sa´t d¯eˆ´n chu´ng-xem [11].
159
............................................................................................................................................................................................................................................................................................................................................................................................................................................................... x....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
..........
y
...........................................................................................................................................................................................................................
......
......
......
......
......
......
......
......
......
......
......
......
......
......
......
......
......
......
......
......
......
......
......
......
.........................................................................................................................
(B)
........................................................................................................................................................................................................................................................
.......................................
.......................................
.......................................
.......................................
.......................................
...................................
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
..................................................................................
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
(A)
................................................... ............................................................................................................................
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
................................................................................................................................................................
(C)
.......................................................................................................................................................... .................................................. ................................................................................................................................................................................................................ y = c
....
..
....
...
....
...
....
...
....
...
....
...
....
...
....
...
....
...
....
...
....
...
....
...
....
...
....
...
....
...
....
..
....
...
....
...
....
...
....
...
....
...
....
..
....
...
....
...
....
...
....
...
....
...
....
...
....
...
....
...
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x7
|
x8
|
•..................................
....
....
....
....
....
....
.
....
....
....
....
....
....
.
....
....
....
....
....
....
.
•..................................
....
....
....
....
....
....
.
....
....
....
....
....
....
.
....
....
....
....
....
....
.
•..................................
....
....
....
....
....
....
.
....
....
....
....
....
....
.
....
....
....
....
....
....
.
•..................................
....
....
....
....
....
....
.
....
....
....
....
....
....
.
....
....
....
....
....
....
.
•..................................
....
....
....
....
....
....
.
....
....
....
....
....
....
.
....
....
....
....
....
....
.
•............................ ......
....
....
....
....
....
....
.
....
....
....
....
....
....
.
....
....
....
....
....
....
.
•............................ ......
....
....
....
....
....
....
.
....
....
....
....
....
....
.
....
....
....
....
....
....
.
•............................ ......
....
....
....
....
....
....
.
....
....
....
....
....
....
.
....
....
....
....
....
....
.
•............................ ......NULL
.................................................
......
............. ......
Con tro˙’
AEL
x1 3 cB x2 6 cA x3 3 cB x4 2 cC
x8 6 cA x7 2 cC x6 6 cA x5 6 cA
cA = GRAY, cB = WHITE, cC = BLUE.
Hı`nh 4.11: Toˆ ma`u ca´c d¯a gia´c cho`ˆng nhau.
160
B (la` WHITE) d¯eˆ˙’ toˆ d¯oa.n tu`
. x1 d¯eˆ´n giao d¯ieˆ˙’m keˆ´ tieˆ´p trong AEL. Ta thaˆ´y ta. i x2, do`ng
que´t d¯i va`o d¯a gia´c A neˆn Covers[A] ga´n ba`ˇng True, NumCovers baˇ`ng 2. Do d¯a gia´c A
co´ d¯oˆ. u
.u tieˆn cao ho.n cu˙’a B neˆn ta thay d¯oˆ˙’i ma`u ve˜ la` GRAY (cu˙’a d¯a gia´c A) va` taˇ´t ma`u
cu˙’a B. Vı` vaˆ.y d¯oa.n [x1, x2] se˜ d¯u
.o.. c toˆ baˇ`ng ma`u cu˙’a d¯a gia´c B. Xe´t tieˆ´p danh sa´ch AEL,
ta co´ giao d¯ieˆ˙’m x3 thuoˆ.c d¯a gia´c B va` do Covers[B] ba`ˇng True neˆn d¯ie`ˆu na`y chı˙’ ra ta. i x3
ta ra kho˙’i d¯a gia´c B. Caˆ.p nhaˆ. t Covers[B] va` NumCovers. Giao d¯ieˆ˙’m x4 la` d¯ieˆ˙’m d¯i va`o
d¯a gia´c C nhu.ng d¯oˆ. u
.u tieˆn cu˙’a no´ thaˆ´p ho.n d¯oˆ. u
.u tieˆn d¯u.o.. c tro˙’ bo
.’˙ i bieˆ´n V isPoly (la`
A) neˆn chı˙’ caˆ.p nhaˆ. t Covers[C] va` NumCovers va` tieˆ´p tu. c. Giao d¯ieˆ˙’m x5 d¯a´nh daˆ´u d¯ieˆ˙’m
ra cu˙’a d¯a gia´c A. Do d¯o´ thu.. c hieˆ.n toˆ ma`u d¯oa.n [x2, x5] vo´
.i ma`u cu˙’a A sau d¯o´ caˆ.p nhaˆ. t
la. i Covers[A], NumCovers va` V isPoly (tro˙’ d¯eˆ´n d¯a gia´c C). Ba.n d¯o.c xu
.’˙ ly´ tu.o.ng tu.. vo´
.i
nhu˜.ng pha`ˆn co`n la. i cu˙’a do`ng que´t.
No´i chung, thuaˆ. t toa´n xuaˆ´t pha´t tu`
. d¯a`ˆu danh sa´ch AEL va` thoˆng qua moˆ.t da˜y ca´c
giao d¯ieˆ˙’m d¯eˆ˙’ caˆ.p nhaˆ. t ma˙’ng Covers[] va` bieˆ´n NumCovers. Khi d¯a gia´c co´ d¯oˆ. u
.u tieˆn lo´.n
ho.n d¯oˆ. u
.u tieˆn cu˙’a d¯a gia´c tro˙’ bo.’˙ i V isPoly, thu.. c hieˆ.n toˆ ma`u va` d¯aˇ. t la. i bieˆ´n V isPoly.
Khi d¯i ra kho˙’i d¯a gia´c kha˙’ kieˆ´n hieˆ.n ha`nh, du`ng ma˙’ng Covers[] d¯eˆ˙’ xa´c d¯i.nh d¯a gia´c co´ d¯oˆ.
u.u tieˆn cao nhaˆ´t phu˙’ pixel hieˆ.n ha`nh; d¯oa.n hieˆ.n ha`nh d¯u
.o.. c toˆ ma`u (vo´
.i ma`u na`o?); va` caˆ.p
nhaˆ. t la. i NumCovers va` Covers[].
4.8 Toˆ ma`u theo maˆ˜u toˆ
Trong nhu˜.ng pha`ˆn tru.´o.c, chu´ng ta toˆ ma`u beˆn trong vu`ng d¯i.nh ngh˜ıa bo
.’˙ i ca´c nguyeˆn so.
vo´.i ca´c ma`u d¯aˇ.c (tu´
.c ca´c pixel trong vu`ng co´ cu`ng ma`u) baˇ`ng ca´ch go. i thu˙’ tu. c putpixel()
vo´.i gia´ tri. ma`u ve˜ la` V alue. Du
.´o.i d¯aˆy chu´ng ta kha˙’o sa´t toˆ ma`u vo´.i maˆ˜u toˆ cho tru.´o.c ba`ˇng
ca´ch theˆm ca´c do`ng leˆ.nh d¯ie`ˆu khieˆ˙’n trong ca´c thuaˆ. t toa´n toˆ ma`u. Vo´
.i ca´c heˆ. thoˆ´ng d¯o`ˆ ho.a
co´ nhie`ˆu bit treˆn moˆ.t pixel, tieˆ´n tr`ınh d¯ie`ˆu khieˆ˙’n d¯aˇ. t gia´ tri. ma`u d¯u
.o.. c laˆ´y moˆ.t ca´ch th´ıch
ho.. p trong maˆ˜u toˆ. Tu
.o.ng tu.. nhu
. kieˆ˙’u da´ng d¯oa.n tha˙ˇ’ng, d¯eˆ˙’ vieˆ´t ca´c maˆ˜u toˆ bitmap de˜ˆ
da`ng, chu´ng ta go. i thu˙’ tu. c putpixel() vo´
.i ma`u noˆ˙’i tu.o.ng u´.ng pixel co´ gia´ tri. moˆ. t trong maˆ˜u
va` khoˆng go. i thu˙’ tu. c na`y neˆ´u pixel co´ gia´ tri. 0. Maˇ.t kha´c, neˆ´u maˆ˜u bitmap d¯u
.o.. c a´p du.ng
trong moˆi tru.`o.ng khoˆng trong suoˆ´t, ta cho.n 1 va` 0 tu
.o.ng u´.ng ma`u noˆ˙’i va` ma`u ne`ˆn.
Vaˆ´n d¯e`ˆ ch´ınh trong toˆ ma`u theo maˆ˜u la` t`ım moˆ´i tu.o.ng quan giu˜.a vi. tr´ı cu˙’a maˆ˜u va`
nguyeˆn so.. No´i ca´ch kha´c, ta ca`ˆn xa´c d¯i.nh vi. tr´ı cu˙’a maˆ˜u d¯u
.o.. c “neo” d¯eˆ˙’ bieˆ´t pixel na`o
trong maˆ˜u se˜ tu.o.ng u´.ng vo´.i pixel hieˆ.n ha`nh trong nguyeˆn so
..
Phu.o.ng pha´p thu´. nhaˆ´t la` neo maˆ˜u ta. i moˆ. t d¯ı˙’nh cu˙’a moˆ.t d¯a gia´c ba`ˇng ca´ch d¯aˇ. t pixel
161
beˆn tra´i nhaˆ´t xuaˆ´t hieˆ.n trong ha`ng d¯a`ˆu tieˆn cu˙’a maˆ˜u. D- ie`ˆu na`y cho phe´p maˆ˜u di chuyeˆ˙’n
theo ca´c nguyeˆn so. ta.o ra moˆ.t hieˆ.u u´
.ng tru.. c quan vo´
.i nhu˜.ng maˆ˜u co´ caˆ´u tru´c h`ınh ho.c
nhu. ca´c d¯u.`o.ng khaˇ´c che´o song song thu.`o.ng d¯u.o.. c su
.’˙ du.ng trong ca´c u´
.ng du.ng thieˆ´t keˆ´. Vı`
khoˆng co´ su.. phaˆn bieˆ.t giu˜
.a ca´c d¯ieˆ˙’m treˆn d¯a gia´c vo´.i nhu˜.ng maˆ˜u na`y cu˜ng nhu. treˆn ca´c
nguyeˆn so. xa´c d¯i.nh bo
.’˙ i ca´c d¯u.`o.ng bieˆn tro.n nhu. d¯u.`o.ng tro`n va` ellipse. Do d¯o´ ngu.`o.i laˆ.p
tr`ınh ca`ˆn xa´c d¯i.nh d¯ieˆ˙’m neo na`ˇm treˆn hoaˇ.c naˇ`m trong nguyeˆn so
.. Trong moˆ.t va`i heˆ. thoˆ´ng,
d¯ieˆ˙’m neo co´ theˆ˙’ cu˙’a moˆ.t nho´m ca´c nguyeˆn so
..
Trong phu.o.ng pha´p thu´. hai, ta xem toa`n boˆ. ma`n h`ınh d¯u
.o.. c la´t vo´
.i maˆ˜u toˆ va` coi
nguyeˆn so. go`ˆm moˆ.t d¯u
.`o.ng bieˆn hoaˇ.c vu`ng d¯u
.o.. c toˆ vo´
.i nhu˜.ng bit d¯aˇ. c tru
.ng cho phe´p maˆ˜u
toˆ baˇng qua. Vi. tr´ı chuaˆ˙’n cu˙’a moˆ.t neo tuyeˆ.t d¯oˆ´i la` goˆ´c ma`n h`ınh. Ca´c pixel cu˙’a nguyeˆn
so. sau d¯o´ d¯u.o.. c xu
.’˙ ly´ ba`ˇng ca´ch AND gia´ tri. 1 vo´
.i maˆ˜u toˆ. Theo ca´ch na`y, maˆ˜u toˆ khoˆng
d¯u.o.. c “gaˇ´n d´ınh” vo´
.i nguyeˆn so. khi nguyeˆn so. ho.i di chuyeˆ˙’n. Thay va`o d¯o´, nguyeˆn so. di
chuyeˆ˙’n nhu. theˆ˙’ no´ d¯u.o.. c d¯aˇ. t treˆn moˆ.t ne`ˆn vo´
.i maˆ˜u coˆ´ d¯i.nh, va` do d¯o´ h`ınh da.ng cu˙’a no´ co´
theˆ˙’ bi. thay d¯oˆ˙’i khi di chuyeˆ˙’n; vo´
.i ca´c maˆ˜u ch´ınh quy ı´t co´ caˆ´u tru´c h`ınh ho.c ngu
.`o.i su.’˙ du.ng
thaˆ.m ch´ı khoˆng nhaˆ.n thaˆ´y a˙’nh hu
.o.’˙ ng na`y. D- eˆ˙’ t´ınh toa´n hieˆ.u qua˙’, neo tuyeˆ.t d¯oˆ´i cho phe´p
ca´c nguyeˆn so. phu˙’ leˆn nhau va` tieˆ´p gia´p kho´.p vo´.i nhau.
D- eˆ˙’ a´p du.ng maˆ˜u toˆ vo´
.i nguyeˆn so., chu´ng ta d¯a´nh chı˙’ soˆ´ to.a d¯oˆ. pixel hieˆ.n ha`nh (x, y).
Vı` ca´c maˆ˜u xa´c d¯i.nh bo
.’˙ i ca´c ma traˆ.n nho˙’ k´ıch thu
.´o.c M × N neˆn ta su.’˙ du.ng phe´p toa´n
modular d¯eˆ˙’ laˇ.p la. i maˆ˜u. Pixel co´ maˆ˜u pattern[0, 0] xem nhu
. tru`ng vo´.i goˆ´c ma`n h`ınh3, va`
chu´ng ta co´ theˆ˙’ vieˆ´t, cha˙ˇ’ng ha.n, moˆ. t maˆ˜u bitmap trong moˆi tru
.`o.ng trong suoˆ´t vo´.i do`ng
leˆ.nh
if pattern[x % M, y % N] putpixel(x, y, value);
Neˆ´u toˆ ma`u moˆ.t d¯oa.n trong cheˆ´ d¯oˆ. thay theˆ´ chu´ng ta co´ theˆ˙’ sao che´p toa`n boˆ. ha`ng
cu˙’a maˆ˜u toˆ ta. i moˆ. t tho`
.i d¯ieˆ˙’m neˆ´u thu˙’ tu. c copypixel() d¯aˇ. t d¯ieˆ˙’m ve˜ o
.’˙ mu´.c thaˆ´p cho phe´p
vieˆ´t nhie`ˆu pixel cu`ng moˆ.t lu´c. Cha˙ˇ’ng ha.n, xe´t maˆ˜u la` ma traˆ.n 8×8. Do d¯o´ no´ laˇ.p moˆ˜i d¯oa.n
8 pixel. Neˆ´u d¯ieˆ˙’m beˆn pha˙’i nhaˆ´t cu˙’a moˆ.t d¯oa.n la` byte d¯u
.o.. c ga´n-tu´
.c la`, neˆ´u hoa`nh d¯oˆ. cu˙’a
pixel d¯a`ˆu tieˆn chia heˆ´t 8-th`ı toa`n boˆ. ha`ng d¯a`ˆu tieˆn cu˙’a maˆ˜u co´ theˆ˙’ d¯u
.o.. c ve˜ ba`ˇng thu˙’ tu. c
copypixel() vieˆ´t 8 pixel; thu˙’ tu. c na`y d¯u
.o.. c go. i la. i nhie`ˆu la`ˆn d¯eˆ˙’ ve˜ toa`n boˆ. d¯oa.n. Neˆ´u pixel
cuoˆ´i cu`ng cu˙’a d¯oa.n khoˆng pha˙’i la` byte d¯u
.o.. c ga´n th`ı ca´c pixel khoˆng thuoˆ.c d¯oa.n ca`ˆn d¯u
.o.. c
d¯aˇ. t maˇ. t na. . D- eˆ˙’ thu
.
. c hieˆ.n hieˆ.u qua˙’ trong nhu˜
.ng tru.`o.ng ho.. p d¯aˇ. c bieˆ.t cu˙’a ca´c thuaˆ. t toa´n
raster, chu´ng ta co´ theˆ˙’, cha˙ˇ’ng ha.n kieˆ˙’m tra tru
.´o.c d¯eˆ˙’ khu.’˙ ca´c vo`ng laˇ.p beˆn trong va` vieˆ´t la. i
ca´c vo`ng laˇ.p na`y ba`ˇng ngoˆn ngu˜
. Assemble (xem [9]).
3Trong ca´c heˆ. thoˆ´ng cu.’˙ a soˆ˙’, maˆ˜u toˆ thu.`o.ng d¯u.o.. c neo ta. i goˆ´c cu˙’a heˆ. to.a d¯oˆ. cu.’˙ a soˆ˙’.
162
Thu. vieˆ.n graph2D.h
Trong pha`ˆn na`y, chu´ng toˆi taˆ.p ho
.
. p nhu˜
.ng kieˆ˙’u du˜. lieˆ.u quan tro.ng va` ca´c khai ba´o d¯u
.o.. c su
.’˙
du.ng trong gia´o tr`ınh. Nhu˜
.ng thu˙’ tu. c va` ha`m thu
.`o.ng xuyeˆn d¯u.o.. c su
.’˙ du.ng cu˜ng d¯u
.o.. c d¯u
.a
ra o.’˙ d¯aˆy.
#if !defined(_graph2D_h)
#define _graph2D_h
#define PI 3.141592654
#define TWOPI 6.283185308
#define MAXVVERTICES 50
#define MAXCOLUMS 639
#define MAXROWS 479
#define TILE_SIZE 16
#define TRUE 1
#define FALSE 0
#define CLIP_ON 1
#define CLIP_OFF 0
typedef unsigned char Byte;
typedef unsigned char Boolean;
typedef struct
{
float x, y;
} Point2D;
163
typedef struct
{
float dx, dy;
} Vector2D;
typedef struct
{
int x, y;
} Pixel;
typedef struct
{
Point2D First, Second;
} Segment2D;
typedef struct
{
Vector2D Normal;
float D;
} Line2D;
typedef struct
{
float xmin, xmax, ymin, ymax;
} Rectangle2D;
typedef struct
{
Point2D Center;
float Rad;
} Circle2D;
typedef struct VertNode2D *VertPtr2D;
struct VertNode2D
{
Point2D Vertex;
164
VertPtr2D Next;
};
typedef struct PolyLink *PolyPtr;
struct PolyLink
{
VertPtr2D Start;
PolyPtr Next;
};
typedef Point2D (*Function) (float);
int feoln(FILE *fp)
{
char c;
if ((c = fgetc(fp)) == 10)
{
fseek(fp, -2, 1);
return(True);
}
else
if (c == EOF) return(True);
else
{
fseek(fp, -1, 1);
return(False);
}
}
void freadln(FILE *fp)
{
char c;
while (((c = fgetc(fp)) != 10) && (c != EOF));
}
165
float min(float x, float y)
{
return((x > y) ? y : x);
}
float max(float x, float y)
{
return((x > y) ? x : y);
}
void PointToVector2D(Point2D P, Vector2D *p)
{
(*p).dx = P.x;
(*p).dy = P.y;
}
float Length2D(Vector2D v)
{
return(sqrt(v.dx*v.dx + v.dy*v.dy));
}
void Scale2D(Vector2D v, float r, Vector2D *Ans)
{
(*Ans).dx = r*v.dx;
(*Ans).dy = r*v.dy;
}
void Normalize(Vector2D v, Vector2D *Ans)
{
float Len;
Len = Length2D(v);
if (Len == 0.0)
printf("Zero vector in Normallize()");
else
{
166
(*Ans).dx = v.dx/Len;
(*Ans).dy = v.dy/Len;
}
}
float Dot2D(Vector2D a, Vector2D b)
{
return(a.dx*b.dx + a.dy*b.dy);
}
void Build_nD(Vector2D *n, float *D, Point2D F, Point2D S)
{
(*n).dx = S.y - F.y;
(*n).dy = F.x - S.x;
(*D) = F.x*S.y - F.y*S.x;
}
void CreateVert2D(VertPtr2D *Vertices)
{
(*Vertices) = NULL;
}
Boolean EmptyVert2D(VertPtr2D Vertices)
{
return((Vertices == NULL) ? True : False );
}
void PushVert2D(VertPtr2D *Vertices, Point2D Vertex)
{
VertPtr2D Tempt;
Tempt = (VertPtr2D) malloc(sizeof(struct VertNode2D));
Tempt->Vertex = Vertex;
Tempt->Next = (*Vertices);
(*Vertices) = Tempt;
}
167
void PopVert2D(VertPtr2D *Vertices, Point2D *Vertex)
{
VertPtr2D Tempt;
if (EmptyVert2D(*Vertices))
{
printf(" Thao tac con tro khong hop le ");
return;
}
else
{
Tempt = (*Vertices);
(*Vertex) = Tempt->Vertex;
(*Vertices) = Tempt->Next;
free(Tempt);
}
}
void ReadVert2D(char *FileName, VertPtr2D *Vertices)
{
Point2D Vertex;
FILE *FileData;
if ((FileData = fopen(FileName, "rt")) == NULL)
{
printf("File khong tim thay");
return;
}
CreateVert2D(Vertices);
while (!feof(FileData))
{
fscanf(FileData, "%f %f", &Vertex.x, &Vertex.y);
PushVert2D(Vertices, Vertex);
}
fclose(FileData);
168
}void FreeVertPtr2D(VertPtr2D *Vertices)
{
Point2D Vertex;
while (!EmptyVert2D(*Vertices)) PopVert2D(Vertices, &Vertex);
}
void DrawPoly(VertPtr2D Vertices)
{
VertPtr2D Tempt = Vertices;
if (Tempt == NULL) return;
moveto(Tempt->Vertex.x, Tempt->Vertex.y);
while ((Tempt = Tempt->Next) != NULL)
{
lineto(Tempt->Vertex.x, Tempt->Vertex.y);
}
}
void DrawCurve(float a, float b, int NumPoints, Function Func)
{
float Delta = (b - a)/ (float)NumPoints;
float t = a;
int i;
moveto(Func(t).x, Func(t).y);
for (i = 1; i <= NumPoints; i++)
{
t += Delta;
lineto(Func(t).x, Func(t).y);
}
}
169
#endif
170
Ta`i lieˆ.u tham kha˙’o
[1] R. H. Bartels, J. C. Beatty, B. A. Barsky, An introduction to splines for use in computer
graphics and geometry modeling, Los Altos, Calif.: Morgan Kaufman Publishers, Inc.
1987.
[2] J. E. Bresenham, Algorithm for computer control of digital plotter, IBM Syst., J. 4,
No. 1, 1965, 25-30.
[3] J. E. Bresenham, A linear algorithm incremental digital display of circular arcs, Comm.,
ACM 20, No. 2, 1977, 750-752.
[4] J. E. Bresenham, Incremental line compaction, Computer J. 25, No. 1, 1982, 116-120.
[5] M. Cyrus, J. Beck Generalized two- and three-dimensional clipping, Computers and
Graphics, Vol. 3 N. 1, 1978, 23-28.
[6] D. Da Silva, Raster algorithms for 2D primitives, Master’s Thesis, Computer Science
Departement, Brown University, Providence, RI, 1989.
[7] G. Farin, Curves and surfaces for computer-aided geometric design, Orlando, Fla. Aca-
demic Press Inc., 1990.
[8] I. D. Faux, M. J. Pratt, Computational geometry for design and manufacture, NewYork,
Horwood/Wiley, 1979.
[9] J. D. Foley, A. Van Dam, S. K. Feiner, J. F. Hughes, Computer graphics: principles and
practice, Addison-Wesley, 1991.
[10] M. R. Kappel, An ellipse drawing algorithm for raster displays, in R. Earnshaw, ed.
Fundamental algorithms for computer graphics, NATO ASI Series, Springer-Verlag,
Berlin, 1985, 257-280.
[11] F. S. Hill Jr., Computer graphics, Macmillan Publishing Company, New York 1988.
171
[12] J. Y. McLeod, M. L. Baar, Geometry and interpolation of curvex and surfaces, Cam-
bridge University, 1998.
[13] M. Levoy, Design for a real-time high-quanlity volume rendering workstation, Proceed-
ings of the Volume Visualization Workshop, Dep. Computer Science, Univ. North Car-
olina at Chapel Hill, May 18-19, 1989, 85-90.
[14] T. M. Nicholl D. T. Lee, R. A. Nicholl, An efficient new algorithm for 2-D line clipping:
Its development and analysis, SIGGRAPH 1987, 253-262.
[15] T. Pavlidis, Contour filling in raster graphics, Computer graphics, 1981.
[16] M. Pitteway, Algorithm for drawing ellipse and hyperbolae with a digital plotter, Com-
puter J. 25, Vol. 10, No. 3, 1967, 282-289.
[17] M. Pitteway, Algorithms of conic generation, in Fundamental algorithms for computer
graphics, Vol. 17, 1967, 219-237.
[18] V. Pratt, Techniques for conic splines, SIGGRAPH 1985, 151-159.
[19] F. P. Preparata, M. I. Shamos, Computational geometry: an introduction, Springer-
Verlag, New York, 1985.
[20] W. Richard, Programmer’s guide to PC & PS/2 Video systems, Microsoft Publishing
Coproration 1987.
[21] R. T. Rockafellar, Convex analysis, Princeton University Press, 1970.
[22] U. Shani, Filling regions in binary raster images: a graph-theoretic a roach, SIGGRAPH
Proceedings 1980, 321-327.
[23] A. R. Smith, Tint fill, SIGGRAPH 1979, 276-283.
[24] I. E. Sutherland, R. F. Sproull, R. A. Schumacker, A characterization of ten hidden-
surface algorithms, ACM Computing Serveys 6 (March), 1-55, 1974.
[25] I. E. Sutherland, G. W. Hodgman, Reentrant polygon clipping, CACM, 17 (1) January
1974, 32-42.
[26] J. Van Aken, An efficient ellipse-drawing algorithm, CG&A, Vol. 4, No. 9, 1984, 24-35.
[27] K. Weiler, P. Atherton, Hidden surface removal using polygon area sorting, SIGGRAPH
77, 214-222.
172
[28] X. Wu, J. G. Rokne, Double-step generation of ellipse, University of Calgary, 1989.
[29] X. Wu, J. G. Rokne, Double-step generation of line and circle, Computer Graphics and
Image Processing, Vol. 37, No. 4, 1987, 331-334.
[30] X. Wu, J. G. Rokne, On properties of discretized convex curves, IEEE Trans. on Pattern
Analysis and Machine Intelligence, Vol. 11, No. 2, 1989.
173