INF 1366 – Computação Gráfica Interativa
Clipping (Recorte)
Alberto B. Raposo e Marcelo Gattass
[email protected]
http://www.tecgraf.puc-rio.br/~abraposo/INF1366/index.htm
Alberto Raposo – PUC-Rio
Pipeline Gráfico
Cluter & Durand, MIT
Modeling
Transformations
Illumination
(Shading)
Viewing Transformation
(Perspective / Orthographic)
Clipping
Projection
(to Screen Space)
Scan Conversion
(Rasterization)
Visibility / Display
Alberto Raposo – PUC-Rio
Clipping (Recorte)
Cluter & Durand, MIT

Modeling
Transformations
Illumination
(Shading)

Viewing Transformation
(Perspective / Orthographic)
Clipping
Projection
(to Screen Space)
Scan Conversion
(Rasterization)
Visibility / Display
Alberto Raposo – PUC-Rio
• Partes do objeto
fora do volume de
visualização
(view frustum)
são removidas
Por que o recorte?
• Não perder tempo rasterizando objetos fora
da janela de visualização!
• Classes de algoritmos:
– Pontos
– Linhas
– Polígonos
Alberto Raposo – PUC-Rio
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) );
}
Alberto Raposo – PUC-Rio
Casos de clipping de linhas
E
(x2, y2)
A
C
(x’2, y’2)
(x’1, y’1)
D
(x1, y1)
Alberto Raposo – PUC-Rio
B
Casos Triviais
D. Brogan, Univ. of Virginia
• Grande otimização: aceitar/rejeitar casos
triviais
• Testar extremidades do segmento de reta
Alberto Raposo – PUC-Rio
Aceitação Trivial
• Como saber se uma linha está totalmente dentro
de uma janela?
• R: se ambas as extremidades estão dentro de todas
as arestas da janela, a linha está totalmente
dentro da janela
Essa linha está
trivialmente dentro
Alberto Raposo – PUC-Rio
Rejeição Trivial
• Como saber se uma linha está totalmente fora de
uma janela?
• R: se ambas as extremidades estão do mesmo lado
(de fora) de uma aresta da janela, a linha pode
ser rejeitada
Essa linha está
trivialmente fora
Alberto Raposo – PUC-Rio
Essa linha está fora, mas não
cai no caso trivial, pois as
extremidades não estão do
mesmo “lado“ de uma
mesma aresta
Recorte de Linhas em Relação ao Viewport
• Combinando casos triviais
D. Brogan, Univ. of Virginia
– Aceitar (desenhar) linhas com ambos os pontos extremos
dentro de todas as arestas da janela de visualização
– Rejeitar linhas com ambos extremos fora de uma mesma
aresta da janela de visualização
– Reduzir outros casos aos casos triviais, encontrando
intrerseções e dividindo os segmentos
Alberto Raposo – PUC-Rio
Cohen-Sutherland Line Clipping
– Dividir janela de visualização em regiões definidas pelas arestas da janela
– Atribuir código (outcode) de 4 bits para cada região:
• Bit 1 indica que valor y dos pontos está acima de ymax
• Outros bits indicam relação com outros vértices da janela
ymax
1001
1000
1010
0001
0000
0010
0101
0100
0110
Alberto Raposo – PUC-Rio
xmax
D. Brogan, Univ. of Virginia
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;
code.all += 4;
}
if (x > xmax) {
1001
1000
1010
code.right = 1;
code.all += 2;
} else if(x < xmin) {
0001
0000
0010
code.left = 1;
code.all += 1;
}
0101
0100
0110
return code;
}
Alberto Raposo – PUC-Rio
Cohen-Sutherland Line Clipping
• Para cada segmento de reta
– Atribua o outcode para cada extremo
– Se ambos outcodes = 0, aceitação trivial
• if (bitwise OR = 0)
– Caso Contrário
• bitwise AND para os outcodes dos vértices
• if result  0, rejeição trivial
Alberto Raposo – PUC-Rio
Cohen-Sutherland Line Clipping
– Se a linha não cai nos casos triviais, subdividi-la de
forma que um ou os dois segmentos possam ser
descartados
• Selecione uma aresta da janela de visualização que a linha
cruza
• Ache a interseção da linha com a aresta
• Descarte a parte do segmento do lado de fora da aresta e
atribua novo outcode ao novo vértice
• Aplique os testes triviais; repetidamente se necessário
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
Cohen-Sutherland Line Clipping
D. Brogan, Univ. of Virginia
• Se a linha não cai nos casos triviais, subdividi-la de forma
que um ou os dois segmentos possam ser descartados
• Selecione uma aresta da janela de visualização que a linha
cruza
– Cheque as arestas na mesma ordem sempre
• Ex: top, bottom, right, left
D
C
B
A
Alberto Raposo – PUC-Rio
E
Cohen-Sutherland Line Clipping
D. Brogan, Univ. of Virginia
• Ache a interseção da linha com a aresta
D
C
B
A
Alberto Raposo – PUC-Rio
E
Cohen-Sutherland Line Clipping
D. Brogan, Univ. of Virginia
• Descarte a parte do segmento do lado de fora da aresta e
atribua novo outcode ao novo vértice
• Aplique os testes triviais; repetidamente se necessário
D
C
B
A
Alberto Raposo – PUC-Rio
Cohen-Sutherland Line Clipping
D. Brogan, Univ. of Virginia
• Descarte a parte do segmento do lado de fora da aresta e
atribua novo outcode ao novo vértice
• Aplique os testes triviais; repetidamente se necessário
C
B
A
Alberto Raposo – PUC-Rio
Interseção com Janela de
Visualização
– (x1, y1), (x2, y2): interseção com aresta vertical
direita: xright
• yintersect = y1 + m(xright – x1)
– onde m=(y2-y1)/(x2-x1)
– (x1, y1), (x2, y2): interseção com aresta horizontal
de baixo: ybottom
• xintersect = x1 + (ybottom – y1)/m
– onde m=(y2-y1)/(x2-x1)
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
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);
}
Alberto Raposo – PUC-Rio
Cohen-Sutherland
– Outcodes facilitam descoberta de casos triviais
• Melhor algoritmo quando casos triviais são comuns
– Os casos não triviais, por outro lado:
• Têm custo elevado
• Geram às vezes recortes redundantes
• Existem algoritmos mais eficientes
Alberto Raposo – PUC-Rio
Equações Paramétricas
• Equações de reta
– Explícita: y = mx + b
– Implícita: Ax + By + C = 0
– Paramétrica: linha definida por 2 pontos, P0 e P1
• P(t) = P0 + (P1 - P0) t, onde P é vetor [x, y]T
• x(t) = x0 + (x1 - x0) t
• y(t) = y0 + (y1 - y0) t
Alberto Raposo – PUC-Rio
Equação Paramétrica da Reta
• Descreve segmento (linha finita)
– 0 <=t <= 1
• Define linha entre P0 e P1
–t<0
• Define linha antes de P0
–t>1
• Define linha depois de P1
Alberto Raposo – PUC-Rio
Linhas Paramétricas e Clipping
• Definir cada linha na forma paramétrica:
– P0(t)…Pn-1(t)
• Definir cada aresta da janela de visualização na
forma paramétrica:
– PL(t), PR(t), PT(t), PB(t)
• Realiza testes de interseção de CohenSutherland usando linhas e arestas apropriadas
Alberto Raposo – PUC-Rio
Equações: Line / Edge Clipping
• Equações paramétricas permitem recortes mais eficientes
• Linha 0:
– x0 = x00 + (x01 - x00) t0
– y0 = y00 + (y01 - y00) t0
• View Window Edge L:
– xL = xL0 + (xL1 - xL0) tL
– yL = yL0 + (yL1 - yL0) tL
• x00 + (x01 - x00) t0 = xL0 + (xL1 - xL0) tL
• y00 + (y01 - y00) t0 = yL0 + (yL1 - yL0) tL
– Resolver para t0 e/ou tL
Alberto Raposo – PUC-Rio
D. Brogan, Univ. of Virginia
Limitações de Cohen-Sutherland
• Só funciona para janelas de visualização
retangulares
• Algoritmo para recorte em janelas convexas
arbitrárias:
– Cyrus-Beck
Alberto Raposo – PUC-Rio
Algoritmo de Cyrus-Beck
• Queremos otimizar o cálculo das
interseções linha/linha
– Começa com equação paramétrica da linha:
• P(t) = P0 + (P1 - P0) t
– E um ponto e a normal de cada aresta da janela
• PL, NL
Alberto Raposo – PUC-Rio
Algoritmo de Cyrus-Beck
• Encontre t tal que:
• NL [P(t) - PL] = 0
P1
PL
P(t)
Inside
P0
NL
• Substitua P(t) pela equação da linha:
– NL [P0 + (P1 - P0) t - PL] = 0
• Encontre t
– t = NL [PL – P0] / -NL [P1 - P0]
Alberto Raposo – PUC-Rio
D. Brogan, Univ. of Virginia
Algoritimo de Cyrus-Beck
N Ei
P0
P(t )
P1
PEi
P  t   P0  ( P1  P0 ) t
N Ei   P  t   PEi   0
Alberto Raposo – PUC-Rio
Produto escalar de 2 vetores
Algoritimo de Cyrus-Beck
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
Alberto Raposo – PUC-Rio
N Ei   P0  PEi 
t
 N Ei   P1  P0 
Algoritmo de Cyrus-Beck
• Compute t para a interseção da linha com todos as
arestas da janela
• Descarte todos (t < 0) e (t > 1)
• Classifique as interseções restantes em
– Potentially Entering (PE)
– Potentially Leaving (PL)
• NL [P1 - P0] > 0 implica PL
• NL [P1 - P0] < 0 implica PE
Alberto Raposo – PUC-Rio
Entrando ou Saindo ?
Ei
P0
P1
N Ei
N Ei   P1  P0   0

PE
Ei
P1
P0
N Ei
N Ei   P1  P0   0
Alberto Raposo – PUC-Rio

PL
Cálculo das interseções
PL
PL
PL
PE
PE
PE
PE
PL
PE
PE
Alberto Raposo – PUC-Rio
PL
PL
Algoritmo de Cyrus-Beck
• Para cada reta:
D. Brogan, Univ. of Virginia
– Ache o PE com maior t
– Ache o PL com menor t
• Recorte nesses 2 pontos
PL
PL
PE
PE
Alberto Raposo – PUC-Rio
P0
P1
Cyrus-Beck - caso geral
{
Calcule Ni e escolha um PEi para cada aresta
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;
}
}
}
Alberto Raposo – PUC-Rio
Caso particular: Liang e Barsky
• Janela retangular: linhas de recorte horizontais e
verticais:
– Normais: (-1, 0), (1, 0), (0, -1), (0, 1)
• Soluções para t:




-(x0 - xleft) / (x1 - x0)
(x0 - xright) / -(x1 - x0)
-(y0 - ybottom) / (y1 - y0)
(y0 - ytop) / -(y1 - y0)
Alberto Raposo – PUC-Rio
Liang e Barsky
y
ymax
ymin
xmin
xmax
Ei
x
NEi
PEi
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)
Alberto Raposo – PUC-Rio
t
Comparação
• Cohen-Sutherland
– Clipping repetitivo é caro
– Melhor utilizado quando a maioria das linhas se encaixam nos casos
de aceitação e rejeição triviais
• Cyrus-Beck
–
–
–
–
Cálculo de t para as interseções é barato
Computação dos pontos (x,y) de corte é feita apenas uma vez
Algoritmo não considera os casos triviais
Melhor usado quando a maioria das linhas precisa ser recortada
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
Recorte de Polígonos
• Mais complicado
• Ainda mais quando
polígono é côncavo
Alberto Raposo – PUC-Rio
Cluter & Durand, MIT
Recorte de Polígonos
• Mais complexo que corte de linhas
– Input: polígono
– Output: polígono original, novo(s) polígono(s), ou
nada
• A melhor otimização são os casos de aceitação ou
rejeição trivial…
Alberto Raposo – PUC-Rio
Tarefa complicada!!!
• O que pode acontecer com um triângulo?
• Possibilidades:
triângulo  triângulo
triângulo  quad
triângulo  5-gon
• Quantos lados pode ter um triângulo
D. Brogan, Univ. of Virginia
recortado?
Alberto Raposo – PUC-Rio
Quantos lados?
•Sete…
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
Tarefa complicada!!!
Polígono côncavo  múltiplos polígonos
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
Algoritmo de Sutherland-Hodgman
• Idéia básica:
– Considerar cada aresta da janela de visualização
individualmente
– Recortar o poligono pela equação de cada
aresta
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
Sutherland-Hodgman Clipping
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
Sutherland-Hodgman Clipping
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
Sutherland-Hodgman Clipping
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
Sutherland-Hodgman Clipping
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
Sutherland-Hodgman Clipping
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
Sutherland-Hodgman Clipping
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
Sutherland-Hodgman Clipping
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
Sutherland-Hodgman Clipping
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
Sutherland-Hodgman Clipping
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
Sutherland-Hodgman Clipping
• Idéia básica:
– Considerar cada aresta da janela de visualização
individualmente
– Recortar o poligono pela equação de cada aresta
– Depois de fazer isso para todas as arestas, o polígono está
completamente recortado
Alberto Raposo – PUC-Rio
D. Brogan, Univ. of Virginia
Sutherland - Hodgman
• Clip contra uma aresta (plano) de cada vez




Alberto Raposo – PUC-Rio
Sutherland-Hodgman Clipping
• Input/output do algoritmo
– Input: lista ordenada dos vértices do polígono
– Output: lista dos vértices recortados, com alguns
vértices originais (possivelmente) e outros
novos (possivelmente)
D. Brogan, Univ. of Virginia
Alberto Raposo – PUC-Rio
Sutherland-Hodgman Clipping
• Aresta de s a p se enquadra em um dos 4 casos:
(Linha azul pode ser reta ou plano)
inside
outside
inside
outside
inside
outside
p
s
p
s
p output
i output
p
inside
p
outside
s
s
no output
i output
p output
Alberto Raposo – PUC-Rio
D. Brogan, Univ. of Virginia
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
externo
P
guarde P
(a)
Alberto Raposo – PUC-Rio
S
P
S
P
I
S
I
P
S
guarde I
(b)
entrando
guarde I, P
(c)
(d)
Sutherland-Hodgman Clipping
• 4 casos:
– s e p dentro do plano
• Coloque p para output (guarde p)
• Nota: s já estaria no output pela aresta anterior
– s dentro do plano e p fora
• Ache ponto de interseção i
• guarde i
– s e p fora do plano
• Não coloque nada no output
– s fora do plano e p dentro
• Ache ponto de interseção i
• guarde i, e também p
Alberto Raposo – PUC-Rio
D. Brogan, Univ. of Virginia

Clipping de polígonos
(Exemplo 1)
2
A
3
1
6
4
B
Alberto Raposo – PUC-Rio
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
A
D
1
Alberto Raposo – PUC-Rio
B
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
B
C
x
E
x
5
F
4
B, E, F, 5, C, D, 1, A
Alberto Raposo – PUC-Rio
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
Teste Point-to-Plane
D. Brogan, Univ. of Virginia
• Teste geral para verificar se ponto p está “dentro” de
um plano P, definido por q e n:
(p - q) • n < 0:
p “dentro” de P
(p - q) • n = 0:
p exatamente em P
(p - q) • n > 0:
p “fora” de P
Lembrar que: p • n = |p| |n| cos (q)
q = ângulo entre p e n
q
q
n
p
Alberto Raposo – PUC-Rio
q
n
p
p
P
P
P
n
Interseção Linha-Plano
• Aresta intercepta plano P onde L(t) está em P
– q é ponto em P
– n é a normal ao plano P
(L(t) - q) • n = 0
(L0 + (L1 - L0) t - q) • n = 0
t = [(q - L0) • n] / [(L1 - L0) • n]
– O ponto de interseção i = L(t) para o valor de t encontrado
acima
Alberto Raposo – PUC-Rio
D. Brogan, Univ. of Virginia
Weiler-Atherton Clipping
• Estratégia: “caminhar” pelas bordas do polígono e da
janela
• Polígonos são orientados no sentido anti-horário
(CCW)
Cluter & Durand, MIT
Alberto Raposo – PUC-Rio
Weiler-Atherton Clipping
• Encontre pontos de interseção
Cluter & Durand, MIT
Alberto Raposo – PUC-Rio
Weiler-Atherton Clipping
• Marque os pontos onde o polígono
entra na janela de recorte
Cluter & Durand, MIT
Alberto Raposo – PUC-Rio
Weiler-Atherton Clipping
• Enquanto houver interseção de entrada
não processada:
– “caminhar” pelas bordas do polígono ou da
janela
Cluter & Durand, MIT
Alberto Raposo – PUC-Rio
Regras da “caminhada”
• Par In-to-out:
– Grave o ponto de interseção
– Caminhe pela aresta do polígono (ccw)
• Par Out-to-in:
– Grave o ponto de interseção
– Caminhe pela aresta da janela (ccw)
Cluter & Durand, MIT
Alberto Raposo – PUC-Rio
Regras da “caminhada”
• Par In-to-out:
– Grave o ponto de interseção
– Caminhe pela aresta do polígono (ccw)
• Par Out-to-in:
– Grave o ponto de interseção
– Caminhe pela aresta da janela (ccw)
Alberto Raposo – PUC-Rio
Regras da “caminhada”
• Par In-to-out:
– Grave o ponto de interseção
– Caminhe pela aresta do polígono (ccw)
• Par Out-to-in:
– Grave o ponto de interseção
– Caminhe pela aresta da janela (ccw)
Cluter & Durand, MIT
Alberto Raposo – PUC-Rio
Regras da “caminhada”
• Par In-to-out:
– Grave o ponto de interseção
– Caminhe pela aresta do polígono (ccw)
• Par Out-to-in:
– Grave o ponto de interseção
– Caminhe pela aresta da janela (ccw)
Alberto Raposo – PUC-Rio
Weiler-Atherton Clipping
• Enquanto houver interseção de entrada
não processada:
– “caminhar” pelas bordas do polígono ou da
janela
Cluter & Durand, MIT
Alberto Raposo – PUC-Rio
Weiler-Atherton Clipping
• Enquanto houver interseção de entrada
não processada:
– “caminhar” pelas bordas do polígono ou da
janela
Cluter & Durand, MIT
Alberto Raposo – PUC-Rio
Weiler-Atherton Clipping
• Enquanto houver interseção de entrada
não processada:
– “caminhar” pelas bordas do polígono ou da
janela
Cluter & Durand, MIT
Alberto Raposo – PUC-Rio
Weiler-Atherton Clipping
• Enquanto houver interseção de entrada
não processada:
– “caminhar” pelas bordas do polígono ou da
janela
Cluter & Durand, MIT
Alberto Raposo – PUC-Rio
Dificuldades
• E se um vértice do polígono está na borda da
janela?
• E se estiver “quase” na borda?
– Problema de precisão
• Welcome to the real world of geometry!
Cluter & Durand, MIT
Alberto Raposo – PUC-Rio
Informações Adicionais
•
•
•
•
Peter Shirley. Fundamentals of Computer Graphics, A K
Peters, Ltd., Natick, MA, USA, 2002.
Foley, J. D., Van Dam, A., Feiner, S. K., e Huhes, J. F.,
Phlips, L. R., Introduction to Computer
Graphics, Addison-Wesley, 1995.
D. F. Rogers, Procedural Elements for Computer
Graphics, McGraw-Hill, 1988.
Marcelo Gattass: notas de aula. http://www.tecgraf.pucrio.br/~mgattass/cg.html
Alberto Raposo – PUC-Rio