poligon dan kurva

7/25/2019 Poligon Dan Kurva

1/19

GrafikaKomputerPertemuanKe-10

BAB-9POLIGON

dan

KURVA

Poligonadalahbentukyangdisusundariserangkiangaris.Kurva

Bezier

digunakan

untuk

membentuk

garis

lengkung

menggunakanalgoritmaBiezer.

By:IGustiNgurahSuryantara,S.Kom.,M.Kom

9.1.PENDAHUUANPoligonadalahbentukyangdisusundariserangkaiangaris.Gam!ar9.1memperlihatkanbeberapabentukpoligon.Titiksudutdaripoligondisebutvertexsedangkangar

ispenyusunpoligondisebutedge.

Gam!ar9.1.Gambarsebuahpoligon.

DariGam!ar9.1.dapatdisimpulkanbahwasebuahpoligonselalumempunyaidasar:1.Jumlahvertex.

2.Koordinatvertex.

3.Datalokasitiapvertex.

11


2/19


Poligondigambardenganmenggambarkanmasing!masingedgedengansetiapedge

merupakanpasangandarivertexi"vertexi#1ke$ualiuntukedgeterakhirmerupaka

n

pasangandarivertexn"vertex1.

%perasi

yang

dapat

dikenakan

pada

sebuah

poligon

antara

lain:1.

&enginisialisasi

poligon.

'nisialisasi

terhadap

poligon

perlu

dilakukan

untu

kmengaturagarfieldvertnumberisi(.

2.&enyisipkanvertex.&enyimpanin)ormasitentangvertexdanmenyesuaikan

in)ormasitentang*umlahvertexdenganmenambahkansatukevertnum.

3.&enggambarpoligon.&engun*ungivertexsatupersatudanmenggambaredge

dengankoordinat+vertexi.x,vertexi.y-"+vertexi#1.x"vertexi#1.y-darivertexnomorsatusampaivertnum!1.khususuntukedgeterakhirmempunyaikoordinat

+vertexvertnum.x,vertexvertnum.y-"+vertex1.x"vertex1.y-..mewarnaipoligon.&engisiareayangdibatasiolehedgepoligondenganwarna

tertentu.

9.".

MENGISI

P#IG#N/dabeberapaalgoritmayangdapatdigunakanuntukmengisiareadidalamsebuahpoligon./lgoritmatersebutantaralain:

1./lgoritmaFloodFill.

2./lgoritmaScanLineFill.3.nside!"utside#est.

.$lgoritmaBoundray!Fill.

Pada

materi

ini

akan

dibahas

0lood

0ill

dan

oundray

0ill.

9.".1.A$goritmaFloodFill/lgoritmayangpalingmudahuntukmengisipoligonadalahalgoritmaFloodfill./lgoritma inibeker*adengan$arapemakaimenentukanwarnapoligonserta lokasi titik

yangmen*adititikawaldankemudianalgoritmaakanmemeriksatitik!titiktetangga

,

apabilawarnatitiktetanggatidaksamadenganwarnaisipoligonmakatitiktersebutakandiubahwarnanya,prosestersebutdilan*utkansampaiseluruhtitikyangberadadidalam

poligonselesaidiproses.Penentuan titik tetanggadapatmenggunakanmetode!koneksi

atau

!koneksi

seperti

pada

gam!ar

9.".

+a-.!Koneksi +b-.!Koneksi


3/19

Gam!ar9.".%!koneksidan&!koneksi

11


/lgoritma mengisi poligon menggunakan )lood )ill dengan koneksi yang

diimplementasikan

se$ara

rekursi)

diperlihatkan

pada

listing

berikut.

VoidFloodFill(intx,inty,intfillColor,intoldColor)

{

If(getPixel(x,y)==oldColor)

{

setColor(fillColor);

setPixel(x,y);

FloodFill(x+1,y,fillColor,oldColor);

FloodFill(x-1,y,fillColor,oldColor);

FloodFill(x,y+1,fillColor,oldColor);

FloodFill(x,y-1,fillColor,oldColor);

}

}

Ketepatanalgoritma)loo)0illditentukanolehtitikawaldanapakahpoligonya

ng

diwarnaimerupakanpoligontertutup./pabilatidaktertutup,meskipunhanyasatutitik

yangterbukamakapengisianakanmelebarkeareadiluarpoligon.

9.".".A$goritmaS%anin&'i$$

Void

BoundaryFill(

int

x,

int

y,

int

fill,

int

Boundray)

{

Int

current

Current=getPixel(x,y);

If

((current

!=Boundray)

&&

(current

!=

fill))

{

setColor(fill);

setPixel(x,y);

Boundray

(x+1,y,fill,

Boundray);

Boundray

(x-1,y,fill,

Boundray);

Boundray

(x,y+1,fill,

Boundray);

Boundray(x,y-1,fill,Boundray);

}

}


4/19

11


9.(.

KU)*AKali

ini

kita

akan

mempela*ari

bagaimana

membuat

kurva

menggunakan

algoritmae4ier./lgoritmamembuatkurvabe4ierdiusulkanolehseorangahlimesindariperan$is

yangbeker*adiperusahaan5enaultdandigunakanuntukmeran$angbadanmobil.

9.(.1.Kur+aB&i&rKitasudahmempela*aribagaimanamembentukgarislurus,sepertidenganmenggunakanalgoritmaDD/danalgoritmaresenham.Padabab inikitaakanmembahaspembuatan

kurva.Pembuatankurvayangakandibahasdenganmenggunakanalgoritmayan

g

diusulkan

oleh

e4ier.Pierre

e4ier

seorang

ahli

mesin

peran$is

yang

beker*

a

diperusahaanrenult.e4ierlahirpadatanggal16eptember171(danmeninggalpadatgl289ovmber1777.e4ie

r

memperolehgelardalambidangmekanikaldari'cole

(ationaleSuperieured)Seniet*etierstahun173(.elar

keduadibidangelektropadatahun1731di'coleSuperieured)'lectricite,dandoktorpadatahun17bidang

matematik

dari

+niversitas

Paris.

'a

beker*a

untuk

renult

dari

1733!178,di

mana

dia

mengembangkan

;9'6;50

;6D


5/19

Dank0

n

xk

Bk/n

,u-

y,u- >ykBk/n,u-k0

rumus

!

6alahsatukelemahankurvae4ieradalahkurvayangdihasilkantidakdapatse$araketatmengikutibentukdarititikkontrolsehinggadapatmerepotkanbilakitainginmembuat

bentukkurvatertentukarenamembutuhkantitikkontrolyanglokasinyaber*auhan.

A/IHAN=itung+x,y-koordinatkurvabe4ieryangmemiliki titikkontrolyaitup(+(,(-,p1+1,2-,p2++3,3-danp3+,(-.

0AAB;ntukempatpointkontrol,n@3

Aangkahpertamahitungseluruh)ungsiblending,knuntukk!(,...,nmenggunaka

nrumus:

n?k

k?.+n!k-?

3?

(3+u-@!!!!!!!!u(+1!u-

[email protected]

(+1!u-

3@213u4

(

(?.3?

3?

13+u-@!!!!!!!!u1+1!u-

[email protected]

1+1!u-

2@(u.213u4

"

1?.2?

3?

kn+u-@


6/19

23+u-@!!!!!!!!u2+1!u-

[email protected]

2+1!u-

1@(u

"213u4

2?.1?

3?

33+u-@!!!!!!!!u3+1!u-

(@1.u

3+1!u-

(@u

(

3?.(?

12(


Kitadapatmelihatbahwa)ungsi!)ungsiinisangatsederhana.6emuanyainiidentikuntuksemuabelokanpadakurvabe4ierdenganptitikkontrol.6ekarangkitasiapunt

uk

menghitungpadapointmelengkung.Parameteruselalumengalamiperubahandari(

sampaidengan1.u@(berkitandengantitikawallengkungan+titikkontrolpertama-Bu1

berkaitan

dengan

titik

akhir

lengkungan

+titik

kontrol

terakhir-.

Kita

hanya

memutuskanpada*umlahlangkah!langkahanaranilai(samapi1,dandarinilaiuntukmenghitun

gpeningkatanDu,

yang1C+*umlahlangkah"1-.&akinbesar+banyak-*umlahlangkah!

langkahyangdiker*akankurvamakinhalusakantetapisemakinlambatdalamproses

perhitungan+menggambar-.

Pada$ontohini*umlahlangkahyangharusdiker*akansebanyak,makadu@1C+!1-@

1C8@(,2.(,2sebaginilaistepsyangbergerakdai(.(,(.2,(.sCd1.Denganlangkahbelokan

+lengkung-

akanmemiliki

koordinat.Kordinat!kordinatyang

dihasilkan

akan

digabungdengansegmengaris.

&arikitamenghitungtitikkontrolberdasarkanalgoritmayangsederhanaini.


7/19

121



8/19

122


Mo5u$Untu6Kur+aB&i&rD&ngan*BPublic

Type

POINTAPIX

As

Long

YAsLong

EndType

PublicDeclareFunctionPolyBezierLib"gdi32"(ByValhdcAsLong,lppt

As

POINTAPI,

ByVal

cPoints

As

Long)

As

Long

Public

P(0

To

3)

As

POINTAPI

'draws

a

single

Bezier

curve

segment

with

4

control

points

FunctionDrawBezierCurve(CanvasAsPictureBox,P()AsPOINTAPI,Steps

AsInteger)

Dim

i

As

Integer

Dim

j

As

Integer


9/19

DimuAsSingle

Dim

B(0

To

3)

As

Single

Dim

Q()

As

POINTAPI

'calculateBeziercurve'Steps=Form1.SlidNilaiU.Value

ReDimQ(0ToSteps)

Fori=0ToSteps

u

=

i

/

Steps

'Bernstein

cubic

polynomials

123


B(0)

=

(1

-

u)

^

3

B(1)=3*u*(1-u)^2

B(2)

=

3

*

u

^

2

*

(1

-

u)

B(3)

=

u

^

3

For

j

=

0

To

3

Q(i).X

=

Q(i).X

+

P(j).X

*

B(j)Q(i).Y

=

Q(i).Y

+

P(j).Y

*

B(j)

Next

j

Form1.ListView2.ListItems.Add

,

,

Format(u,

"0.##")

Form1.ListView2.ListItems(Form1.ListView2.ListItems.Count).SubItems(1)=

Q(i).X

Form1.ListView2.ListItems(Form1.ListView2.ListItems.Count).SubItems(2)=Q(i).Y

Next

i

'draw

Bezier

curveCanvas.CurrentX

=

Q(0).X

Canvas.CurrentY=Q(0).Y

Fori=0ToSteps

Canvas.Line(Canvas.CurrentX,Canvas.CurrentY)-(Q(i).X,Q(i).Y)

Next

i

End

Function

LAMPIRAN

PROGRAM

MENGISI

POLIGON

Dengan

Visual

C#include

#include

//for

random

numbers

rand();

#include

#include"QuickCG.h"

#include"Q3Dmath.h"

using

namespace

std;

template

inline

T0

pow(T0

a,

T1

b){return

pow(a,

T0(b));}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~//

// PUTCODEBELOWHERE

//

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~//


10/19

//thefloodfillalgorithmsvoid

floodFill4(int

x,

int

y,

Uint32

newColor,

Uint32

oldColor);

voidfloodFill8(intx,inty,Uint32newColor,Uint32oldColor);

voidfloodFill4Stack(intx,inty,Uint32newColor,Uint32oldColor);

voidfloodFill8Stack(intx,inty,Uint32newColor,Uint32oldColor);

void

floodFillScanline(int

x,

int

y,

Uint32

newColor,

Uint32

oldColor);

void

floodFillScanlineStack(int

x,

int

y,

Uint32

newColor,

Uint32

oldColor);

12


//the

stack

#definestackSize16777216

intstack[stackSize];

intstackPointer;

//theauxiliaryfunctionsbool

paint_drawLine(int

x1,

int

y1,

int

x2,

int

y2,

ColorRGB

color);

void

clearScreenBuffer(ColorRGB

color);

//the

graphics

buffer

#definescreenW256

#define

screenH

256

Uint32screenBuffer[screenW][screenH];

int

main(int

argc,

char

*argv[])

{

screen(screenW,

screenH,

0,

"Flood

Fill");

clearScreenBuffer(RGB_White);

int

mouseX,

mouseY;

intoldMouseX,oldMouseY;

bool

LMB,

RMB;

while(!done())

{

oldMouseX

=

mouseX;

oldMouseY

=

mouseY;

getMouseState(mouseX,mouseY,LMB,RMB);

//3differentmouseinputactionsif(LMB)

paint_drawLine(oldMouseX,

oldMouseY,

mouseX,

mouseY,

RGB_Black);

if(RMB)

{

Uint32color=RGBtoINT(ColorRGB((mouseX%3+1)*64,

(mouseY

%

8)

*

32,

(mouseX

+

mouseY)

%

256));

floodFillScanlineStack(mouseX,

mouseY,

color,

screenBuffer[mouseX][mouseY]);

}

if(RMB&&LMB)clearScreenBuffer(RGB_White);

//benchmarkreadKeys();

if(inkeys[SDLK_SPACE])

{

floatstartTime=getTime();

for(inti=1;i


11/19

float

startTime2

=

getTime();

for(inti=1;i0)

{

intp=stack[stackPointer];

x

=

p

/

h;y

=

p

%

h;

stackPointer--;

return1;

}

else

{

return

0;

}

}

boolpush(intx,inty){

if(stackPointer


12/19

while(pop(x,y));

}

/////////////////////////////////////////////////////////////////////////VariantsoftheFloodfillAlgorithm

///////////////////////////////////////////////////////////////////////

12GrafikaKomputerPertemuanKe-10

//Recursive4-wayfloodfill,crashesifrecursionstackisfull

voidfloodFill4(intx,inty,Uint32newColor,Uint32oldColor){

if(x>=0&&x=0&&y=

0

&&

x

=

0

&&

y

=denominator

yinc2

=

0;

//

Don't

change

the

y

for

every

iteration


17/19

den=deltax;

num=deltax/2;

numadd

=

deltay;

numpixels

=

deltax;

//

There

are

more

x-values

than

y-values

}

131


else//Thereisatleastoney-valueforeveryx-value{

xinc2=0;//Don'tchangethexforeveryiteration

yinc1=0;//Don'tchangetheywhennumerator>=denominator

den=deltay;

num=deltay/2;

numadd

=

deltax;

numpixels

=

deltay;

//

There

are

more

y-values

than

x-values

}

for(curpixel=0;curpixel=

den)

//

Check

if

numerator

>=

denominator

{

num

-=

den;

//

Calculate

the

new

numerator

value

x

+=

xinc1;

//

Change

the

x

as

appropriate

y

+=

yinc1;

//

Change

the

y

as

appropriate

}

x+=xinc2;//Changethexasappropriate

y+=yinc2;//Changetheyasappropriate

}

return

1;}


18/19


19/19

132

poligon dan kurva

Documents