Recorte e seleção
de linhas e polígonos
Motivações
Ambiguidade na seleção
Classes de Algoritmos
• Pontos
• Linhas
• Polígonos
Ponto em retângulo
y
yp
2.tol
2.tol
ym
xm
int
xp
x
pontInRect(int xm, int ym, float xp, float yp, float tol) {
return ( (xp>=xm-tol) && (xp<=xm+tol) ) && ( (yp>=ym-tol) && (yp<=ym+tol) );
}
Casos de clipping de linhas
E
(x2, y2)
A
C
(x’2, y’2)
(x’1, y’1)
D
(x1, y1)
B
Códigos das regiões
1001
1000
1010
0001
0000
0010
0101
0100
0110
tbrl
typedef struct {
unsigned char
unsigned char
unsigned char
unsigned char
unsigned char
} Outcode;
all;
left;
right;
bottom;
top;
Cálculo do código de um vértice
Outcode compOutCode(double x, double y,
double xmin, double xmax, double ymin, double ymax)
{
Outcode code;
code.top = 0, code.bottom = 0, code.right = 0,
code.left = 0, code.all = 0;
if (y > ymax) {
code.top = 1;
code.all += 8;
} else if(y < ymin) {
code.bottom = 1;
1001
1000
1010
code.all += 4;
}
if (x > xmax) {
0001
0000
0010
code.right = 1;
code.all += 2;
} else if(x < xmin) {
0101
0100
0110
code.left = 1;
code.all += 1;
}
return code;
}
Algoritmo de Cohen-Sutherland
void CohenSutherlandLineClipAndDraw(double x0, double y0, double x1, double y1,
double xmin, double xmax, double ymin, double ymax, int value)
{
outcode outcode0, outcode1, outcodeOut, CompOutCode();
double x, y;
boolean accept = FALSE, done = FALSE;
outcode0 = CompOutCode(x0, y0, xmin, xmax, ymin, ymax);
outcode1 = CompOutCode(x1, y1, xmin, xmax, ymin, ymax);
do {
if (outcode0.all == 0 && outcode1.all == 0) {
accept = TRUE; done = TRUE;
/* trivial draw and exit */
} else if((outcode0.all & outcode1.all) != 0) {
done = TRUE;
/* trivial reject and exit */
} else {
if (outcode0.all != 0) outcodeOut = outcode0; else outcodeOut = outcode1;
if (outcodeOut.top) {
x = x0 + (x1 - x0) * (ymax } else if(outcodeOut.bottom) {
x = x0 + (x1 - x0) * (ymin } else if(outcodeOut.right) {
y = y0 + (y1 - y0) * (xmax } else if(outcodeOut.left) {
y = y0 + (y1 - y0) * (xmin }
y0) / (y1 - y0);
y = ymax;
y0) / (y1 - y0); y = ymin;
x0) / (x1 - x0);
x = xmax;
x0) / (x1 - x0); x = xmin;
if (outcodeOut.all == outcode0.all) {
x0 = x; y0 = y;
outcode0 = CompOutCode(x0, y0, xmin, xmax, ymin, ymax);
} else {
x1 = x; y1 = y;
outcode1 = CompOutCode(x1, y1, xmin, xmax, ymin, ymax);
}
} /* Subdivide */
} while (!done);
if (accept) DrawLineReal(x0, y0, x1, y1, value);
}
Algoritimo de Cyrus-Beck
(Liang-Barsky)
N Ei
P0
P(t )
PEi
Pt   P0  ( P1  P0 ) t
N Ei   P  t   PEi   0
P1
Algoritimo de Cyrus-Beck
(Liang-Barsky)
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
NEi  Pt   PEi   0
N Ei   P0  PEi 
t
 N Ei   P1  P0 
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
PL
PE
PL
PE
PE
PE
PL
PE
PE
PL
PL
Cyrus-Beck - caso geral
{
Calcule Ni e escolha um PEi para cada aresta
if(P1 = = P0)
o segmento é degenerado e deve ser recortado como um ponto;
else {
tE = 0;
tL = 1;
for( cada aresta ){
if (Ni.(P1-P0)!=0 ){ /* aresta não é paralela ao segmento */
calcule t;
use sign of Ni.(P1-P0) para categorizar como PE ou PL;
if( PE ) tE = max(tE, t);
if( PL ) tL = min(tL, t);
} else {
/* aresta paralela ao segmento */
if (Ni.(P0-PEi) > 0) /* está fora */
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
xmax
x
NEi
PEi
t
left: x = xmin
(-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)
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 */
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;
if (Clipt(dx,xmin-*x0,&tE,&tL) )
if (Clipt(-dx,*x0-max,&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;
}
Clipping de polígonos
(Hodgman - Sutherland)
• Clip contra uma aresta (plano) de cada vez




Clipping de polígonos
(Hodgman & Suterland)
• Para cada aresta (plano) teste um segmento de cada vez
• Existem quatro casos possiveis para um vértice e
seu antessessor
interno
saindo
guarde P
(a)
P
I S
I
P
S
guarde I
(b)
entrando
S
P
S
P
externo
guarde I, P
(c)
(d)
Cálculo de interseção pela distância
y
n
(x1 , y1 )
d1
ymax
d0
ymin
xmin
d 0  x 0  x max
d1  x1  x max
t
d0
d 0  d1
xmax
(x0 , y0 )
x
x  x0  t  ( x1  x0 )
y  y0  t  ( y1  y0 )
Clipping de polígonos
(Exemplo 1)

2
A
3
1
6
4
B
5
S
P
Ação
1
2
x
2
3
3
4
store A,3
store 4
4
5
5
6
store 5
store B
6
1
x
Clipping de polígonos
(Exemplo 2)

2
3
Ax 6x x
x
B
S
1
2
3
4
5
6
D C
1
4
5
B
A D C
1
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
x
D C
1
B
xE
x
5
F
4
S
A
B
4
5
C
D
1
B, E, F, 5, C, D, 1, A
P
B
4
5
C
D
1
A
Ação
store B
store E
store F,5
store C
store D
store 1
store A
Clipping de polígonos
(Concatenação de planos)
2
3
Ax 6x x
x
3 4
B
D C
1
Ax
4
5
x x
x
B
D C
x
E
x
1
5
F
4
1
D
C
5
4
B
A
1
Ax
x x
x
D C
1
B
x
5
6
2
first[0]
S[0]
P[0]
first[1]
S[1]
P[1]
E
x
5
F
1, A, B, E, F, 5, C, D
APIs para definição de polígonos
int npoints;
double x[MAXPOINTS], y[MAXPOINTS];
FillPoly(npoints, x, y);
Point vertex[MAXPOINT]
FillPoly(npoints, vertex)
Begin(FILL);
Vertex(30.,20.);
Vertex(15.,18.);
…
End( );

Distâncias as bordas das janelas
y
ymax
ymin
xmin
xmax
x
double Distance( double x, double y, int plane)
{
switch( plane )
{
case 0: return( -x + xmin );
case 1: return( x - xmax );
case 2: return( -y + ymin );
case 3: return( y - ymax );
}
return( 0.0 );
}
Teste de interseção com uma fronteira
void Intersect(double x, double y,
int plane, double d1, double d2)
{
double t = d1 / (d1 - d2);
double xi = sx[plane] + t * (x - sx[plane]);
double yi = sy[plane] + t * (y - sy[plane]);
if( plane == LAST_PLANE )
SaveVertex( xi, yi);
else
ClipAtPlane( xi, yi, plane+1 );
}
Clipping de polígonos de
Sutherland-Hodgman
void ClipAtPlane( double x, double y, int plane )
{
double d = Distance(x, y, plane);
/* Check whether it is the first point */
if( first[plane] ) {
fx[plane] = x;
fy[plane] = y;
fd[plane] = d;
first[plane] = 0;
}
else if ((sd[plane] < 0) ^ (d < 0))
Intersect( x, y, plane, sd[plane], d );
/* Save as previous */
sx[plane] = x; sy[plane] = y;
/* Check whether it is a visible point */
if( d <= 0.0 ) {
if( plane == LAST_PLANE )
SaveVertex( x, y);
else
ClipAtPlane( x, y, plane+1 );
}
}
Ligando com a API
void Vertex( double x, double y)
{
if (clip_on_off)
ClipAtPlane( x, y, 0 );
else
SaveVertex(x, y);
}
void ClipClose( int plane )
{
if ((sd[plane] < 0) ^ (fd[plane] < 0))
Intersect( fx[plane], fy[plane], plane,
sd[plane], fd[plane] );
first[plane] = 1;
if( plane == LAST_PLANE )
FillSavedPolygon();
else
ClipClose( plane+1 );
}
Em coordenadas homogêneas
/* ===================== Distance ======================
**
** This function computes and returns the distance between a
** point and a plane. Normal points toward out.
*/
double Distance(double x, double y, double z, double w, int plane )
{
switch( plane )
{
case 0: return( -w - x );
case 1: return( -w + x );
case 2: return( -w - y );
case 3: return( -w + y );
case 4: return( -w - z );
case 5: return( -w + z );
}
return( 0.0 );
}