Clipping de linhas e polígonos
O que é clipar?
Viewport
O que é clipar?
Cortar o excesso de modo a ficar apenas com o que interessa!
Cohen-Sutherland Clipping
1001
1000
0001
0000
0010
0101
0100
0110
1010
1º passo: Codificar cada vértice segundo sua região...
Cohen-Sutherland Clipping
Cálculo do código de um vértice:
#define
#define
#define
#define
LEFT
RIGHT
BOTTOM
TOP
1
2
4
8
//0001
//0010
//0100
//1000
unsigned char CompCode(double x, double y,
double xmin, double xmax,
double ymin, double ymax)
{
unsigned char code=0;
if (y > ymax)
code += TOP;
else
if(y < ymin)
code += BOTTOM;
if (x > xmax)
code += RIGHT;
else
if(x < xmin)
code += LEFT;
return code;
}
1001
1000
1010
0001
0000
0010
0101
0100
0110
• AND binário dos códigos dos dois vértices de uma aresta:
se diferente de zero pode ser descartado.
• OR binário dos códigos dos dois vértices de uma aresta:
se igual a zero pode ser aceito (desenhado).
• SENÃO, calcula-se interseção com borda, usando
AND binário para saber qual das bordas está sendo vazada.
void CohenSutherlandLineClipAndDraw(double x0, double y0, double x1, double y1,
double xmin, double xmax, double ymin, double ymax, int value)
{
unsigned char code0, code1, outcodeOut;
int accept = 1;
// TRUE
code0 = CompCode(x0, y0, xmin, xmax, ymin, ymax);
code1 = CompCode(x1, y1, xmin, xmax, ymin, ymax);
while ( code0 | code1 )
{
if( code0 & code1 )
{ code0 = code1 = accept = 0; }
/* trivial reject and
else
{
if ( code0 )
{
if ( code0 & TOP )
{ x0 = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y0 =
else if( code0 & BOTTOM )
{ x0 = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y0 =
else if( code0 & RIGHT )
{ y0 = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x0 =
else if( code0 & LEFT )
{ y0 = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x0 =
code0 = CompCode(x0, y0, xmin, xmax, ymin, ymax);
}
else
{
if ( code1 & TOP )
{ x1 = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y1 =
else if( code1 & BOTTOM )
{ x1 = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y1 =
else if( code1 & RIGHT )
{ y1 = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x1 =
else if( code1 & LEFT )
{ y1 = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x1 =
code1 = CompCode(x1, y1, xmin, xmax, ymin, ymax);
}
}
}
if (accept) DrawLineReal(x0, y0, x1, y1, value);
}
exit */
ymax; }
ymin; }
xmax; }
xmin; }
ymax; }
ymin; }
xmax; }
xmin; }
void CohenSutherlandLineClipAndDraw(double x0, double y0, double x1, double y1,
double xmin, double xmax, double ymin, double ymax, int value)
{
unsigned char code0, code1, outcodeOut;
int accept = 1;
// TRUE
Enquanto pelo menos um
dos vértices estiver fora
do viewport...
code0 = CompCode(x0, y0, xmin, xmax, ymin, ymax);
code1 = CompCode(x1, y1, xmin, xmax, ymin, ymax);
while ( code0 | code1 )
{
if( code0 & code1 )
{ code0 = code1 = accept = 0; }
/* trivial reject and
else
{
if ( code0 )
{
if ( code0 & TOP )
{ x0 = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y0 =
else if( code0 & BOTTOM )
{ x0 = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y0 =
else if( code0 & RIGHT )
{ y0 = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x0 =
else if( code0 & LEFT )
{ y0 = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x0 =
code0 = CompCode(x0, y0, xmin, xmax, ymin, ymax);
}
else
{
if ( code1 & TOP )
{ x1 = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y1 =
else if( code1 & BOTTOM )
{ x1 = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y1 =
else if( code1 & RIGHT )
{ y1 = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x1 =
else if( code1 & LEFT )
{ y1 = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x1 =
code1 = CompCode(x1, y1, xmin, xmax, ymin, ymax);
}
}
}
if (accept) DrawLineReal(x0, y0, x1, y1, value);
}
exit */
ymax; }
ymin; }
xmax; }
xmin; }
ymax; }
ymin; }
xmax; }
xmin; }
void CohenSutherlandLineClipAndDraw(double x0, double y0, double x1, double y1,
double xmin, double xmax, double ymin, double ymax, int value)
{
unsigned char code0, code1, outcodeOut;
int accept = 1;
// TRUE
Se os vértices tiverem um bit
em comum, significa que
ambos estão externos ao
viewport pelo mesmo lado!
code0 = CompCode(x0, y0, xmin, xmax, ymin, ymax);
code1 = CompCode(x1, y1, xmin, xmax, ymin, ymax);
while ( code0 | code1 )
{
if( code0 & code1 )
{ code0 = code1 = accept = 0; }
/* trivial reject and
else
{
if ( code0 )
{
if ( code0 & TOP )
{ x0 = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y0 =
else if( code0 & BOTTOM )
{ x0 = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y0 =
else if( code0 & RIGHT )
{ y0 = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x0 =
else if( code0 & LEFT )
{ y0 = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x0 =
code0 = CompCode(x0, y0, xmin, xmax, ymin, ymax);
}
else
{
if ( code1 & TOP )
{ x1 = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y1 =
else if( code1 & BOTTOM )
{ x1 = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y1 =
else if( code1 & RIGHT )
{ y1 = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x1 =
else if( code1 & LEFT )
{ y1 = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x1 =
code1 = CompCode(x1, y1, xmin, xmax, ymin, ymax);
}
}
}
if (accept) DrawLineReal(x0, y0, x1, y1, value);
}
exit */
ymax; }
ymin; }
xmax; }
xmin; }
ymax; }
ymin; }
xmax; }
xmin; }
void CohenSutherlandLineClipAndDraw(double x0, double y0, double x1, double y1,
double xmin, double xmax, double ymin, double ymax, int value)
{
unsigned char code0, code1, outcodeOut;
int accept = 1;
// TRUE
code0 = CompCode(x0, y0, xmin, xmax, ymin, ymax);
code1 = CompCode(x1, y1, xmin, xmax, ymin, ymax);
Se o vértice0 tem o bit TOP ligado...
while ( code0 | code1 )
{
if( code0 & code1 )
{ code0 = code1 = accept = 0; }
/* trivial reject and
else
{
if ( code0 )
{
if ( code0 & TOP )
{ x0 = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y0 =
else if( code0 & BOTTOM )
{ x0 = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y0 =
else if( code0 & RIGHT )
{ y0 = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x0 =
else if( code0 & LEFT )
{ y0 = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x0 =
code0 = CompCode(x0, y0, xmin, xmax, ymin, ymax);
}
else
{
if ( code1 & TOP )
{ x1 = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y1 =
else if( code1 & BOTTOM )
{ x1 = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y1 =
else if( code1 & RIGHT )
{ y1 = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x1 =
else if( code1 & LEFT )
{ y1 = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x1 =
code1 = CompCode(x1, y1, xmin, xmax, ymin, ymax);
}
}
}
if (accept) DrawLineReal(x0, y0, x1, y1, value);
}
exit */
ymax; }
ymin; }
xmax; }
xmin; }
ymax; }
ymin; }
xmax; }
xmin; }
void CohenSutherlandLineClipAndDraw(double x0, double y0, double x1, double y1,
double xmin, double xmax, double ymin, double ymax, int value)
{
unsigned char code0, code1, outcodeOut;
int accept = 1;
// TRUE
code0 = CompCode(x0, y0, xmin, xmax, ymin, ymax);
code1 = CompCode(x1, y1, xmin, xmax, ymin, ymax);
while ( code0 | code1 )
{
if( code0 & code1 )
{ code0 = code1 = accept = 0; }
/* trivial reject and
else
{
if ( code0 )
{
if ( code0 & TOP )
{ x0 = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y0 =
else if( code0 & BOTTOM )
{ x0 = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y0 =
else if( code0 & RIGHT )
{ y0 = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x0 =
else if( code0 & LEFT )
{ y0 = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x0 =
code0 = CompCode(x0, y0, xmin, xmax, ymin, ymax);
}
else
{
if ( code1 & TOP )
{ x1 = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y1 =
else if( code1 & BOTTOM )
{ x1 = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y1 =
else if( code1 & RIGHT )
{ y1 = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x1 =
else if( code1 & LEFT )
{ y1 = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x1 =
code1 = CompCode(x1, y1, xmin, xmax, ymin, ymax);
}
}
}
if (accept) DrawLineReal(x0, y0, x1, y1, value);
}
exit */
ymax; }
ymin; }
xmax; }
xmin; }
Desloca o ponto para a interseção
da reta com o lado vazado.
ymax; }
ymin; }
xmax; }
xmin; }
void CohenSutherlandLineClipAndDraw(double x0, double y0, double x1, double y1,
double xmin, double xmax, double ymin, double ymax, int value)
{
unsigned char code0, code1, outcodeOut;
int accept = 1;
// TRUE
code0 = CompCode(x0, y0, xmin, xmax, ymin, ymax);
code1 = CompCode(x1, y1, xmin, xmax, ymin, ymax);
while ( code0 | code1 )
{
if( code0 & code1 )
{ code0 = code1 = accept = 0; }
/* trivial reject and
else
{
if ( code0 )
{
if ( code0 & TOP )
{ x0 = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y0 =
else if( code0 & BOTTOM )
{ x0 = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y0 =
else if( code0 & RIGHT )
{ y0 = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x0 =
else if( code0 & LEFT )
{ y0 = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x0 =
code0 = CompCode(x0, y0, xmin, xmax, ymin, ymax);
}
else
{
if ( code1 & TOP )
{ x1 = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y1 =
else if( code1 & BOTTOM )
{ x1 = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y1 =
else if( code1 & RIGHT )
{ y1 = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x1 =
else if( code1 & LEFT )
{ y1 = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x1 =
code1 = CompCode(x1, y1, xmin, xmax, ymin, ymax);
}
}
}
if (accept) DrawLineReal(x0, y0, x1, y1, value);
}
exit */
ymax; }
ymin; }
xmax; }
xmin; }
ymax; }
ymin; }
xmax; }
xmin; }
A codificação deve ser
recalculada, uma vez que
um novo bit pode ser aceso.
Algoritimo de Cyrus-Beck
(Liang-Barsky)
Para qualquer
polígono convexo!
N Ei
P0
N Ei  Pt   PEi   0
P1
N Ei   Pt   PEi   0
N Ei   Pt   PEi   0
PEi
Pt   P0  ( P1  P0 ) t
N Ei   P  t   PEi   0
t
N Ei   P0  PEi 
 N Ei   P1  P0 
Obs: Produto Escalar de Vetores
Entrando ou Saindo ?
Ei
P0
P1
N Ei
N Ei   P1  P0   0

PE
Ei
P1
P0
N Ei
N Ei   P1  P0   0

PL
Cálculo das interseções
PL
PE
PE
PE
PL
PL
PL
PE
Cyrus-Beck - caso geral
{
precalculate Ni and select a PEi for each edge
Ambos os vértices estão
fora do polígono pelo lado
da aresta corrente!
for( each line segment to be clipped ){
if(P1 = P0)
line is degenerate so clip as a point;
else{
tE = 0;
tL = 1;
for( each candidate intersection with a clip edge ){
if( Ni . (P1-P0) !=0 ){ /* edges not parallel to line */
calculate t;
use sign of Ni . (P1-P0) to categorize as PE or PL;
if( PE )tE = max(tE, t);
if( PL )tL = min(tL, t);
}
else
if(Ni . (P0-PEi) > 0)
return nil;
}
if(tE > tL)
return nil;
else
return P(tE) and P(tL) as true clip intersections;
}
}
}
Liang e Barsky
- caso particular -
y
ymax
ymin
xmin
Ei
left: x = xmin
xmax
x
NEi
PEi
t
(-1, 0)
(xmin, y)
-(x0-xmin)
(x1-x0)
right: x = xmax
(1, 0)
(xmax, y)
(x0-xmax)
-(x1-x0)
bottom: y = ymin
(0,-1)
(x, ymin)
-(y0-ymin)
(y1-y0)
top: y = ymax
(0, 1)
(x, ymax)
(y0-ymax)
-(y1-y0)
Observe que sempre
que o denominador
for positivo, trata-se
de um ponto de
entrada (se negativo,
ponto de saída)
Algoritimo de Liang e Barsky
boolean Clip2D(double *x0, double *y0, double *x1, double *y1,
double xmin, double max, double ymin, double ymax)
{
double dx = *x1 - *x0;
double dy = *y1 - *y0;
boolean visible = FALSE;
if (dx==0)&&(dy==0)&&ClipPoint(*x0,*y0,xmin,xmax,ymin,ymax)
visible=TRUE;
else
{
double tE=0.0, tL=1.0;
O teste será feito para cada um dos 4 lados,
sempre atualizando TE e TL
if (Clipt(dx,xmin-*x0,&tE,&tL) )
if (Clipt(-dx,*x0-xmax,&tE,&tL) )
if (Clipt(dy,ymin-*y0,&tE,&tL) )
if (Clipt(-dy,*y0-ymax,&tE,&tL) )
{
visible=TRUE;
if (tL<1.0) { (*x1)=(*x0)+tL*dx; (*y1)=(*y0)+tE*dy; }
if (tE>0.0) { (*x0)=(*x0)+tE*dx; (*y0)=(*y0)+tE*dy; }
}
}
return visible;
}
Atualiza os valores
dos vértices
Liang e Barsky
Cálculo da interseção em uma fronteira
boolean Clipt(double den, double num, double *tE, double *tL)
{
double t;
if (den > 0)
{
t = num/den;
if (t > *tL)
return FALSE;
else
if (t > *tE) *tE = t;
}
else if (den < 0)
{
t=num/den;
if (t < *tE)
return FALSE;
else
if (t < *tL) *tL = t;
}
else
if (num > 0)
return FALSE;
return TRUE;
}
/* intersecao PE */
/* tE > tL */
/* intersecao PL */
/* tL < tE */
/* linha esta fora */
Clipping de polígonos
(Hodgman & Suterland)
• Clip contra uma aresta (plano) de cada vez
Clipping de polígonos
(Hodgman & Suterland)
• Para cada aresta (plano) teste um segmento de cada vez
• Quatro situações diferentes mostradas abaixo
(dados o vértice de origem S e o vértice destino D de cada aresta do polígono)
D
S
D
S
S
store D
D
I
store I
I
S
store I, D
D
Clipping de polígonos
(Exemplo 1)
2
A
3
1
6
4
B
5
S
P
Ação
1
2
3
4
5
6
2
3
4
5
6
1
x
store A,3
store 4
store 5
store B
x
Clipping de polígonos
(Exemplo 2)
2
Ax
3
6
x x
D
1
x
B
S
1
2
3
4
5
6
C
4
5
B
A
D
1
C
5
4
P
2
3
4
5
6
1
Ação
store A
x
store B,4
store 5
store C
store D,1
Clipping de polígonos
(Exemplo 2)
Ax
x x
D
1
x
C
B
x
E
x
5
F
4
B, E, F, 5, C, D, 1, A
S
A
B
4
5
C
D
1
P
B
4
5
C
D
1
A
Ação
store B
store E
store F,5
store C
store D
x
store 1, A
2
Ax
3
6
x
x
B
3
C
D
1
Ax
x
Clipping de polígonos
(Concatenação de planos)
6
5
4
4
5
x
x
D
x
B
C
x
E
x
1
5
F
4
1
D
C
5
4
B
A
1
Ax
x x
D
1
x
C
B
x
E
2
first[0]
S[0]
P[0]
first[1]
S[1]
P[1]
x
5
F
1, A, B, E, F, 5, C, D
Produto Escalar de Vetores
• Dados dois vetores, v1[x1,y1] e v2[x2,y2] definidos no 2,
o produto escalar v1•v2 é:
v1•v2 = x1x2 + y1y2
• Podemos afirmar também a seguinte identidade:
v1•v2 = |v1| |v2| cos ,
onde  é o ângulo formado pelos vetores.
• Se o resultado for positivo, o ângulo é agúdo, senão é obtuso.
• Portanto o ângulo entre dois vetores pode ser calculado por:
ângulo (v1,v2) = arc cos (v1•v2 / |v1| |v2|)
• O ângulo retornado é um valor entre [0,].
• Se forem vetores unitários não é necessária a divisão pelo módulo
• Em inglês se chama Dot Product