Instituto Superior Técnico Computação Gráfica 2009/2010 · Algoritmo de Cohen-Sutherland ... Calcular os 4 valores de t ... verificar se ponto ∈aresta de recorte Ni.D = 0 Segmento

Recorte

Instituto Superior Técnico

Edward Angel, Cap. 7

Instituto Superior Técnico Computação Gráfica

2009/2010

1

Na última aula...

� Remoção de Faces Traseiras

� Back-face Culling

©2010, CG&M/IST e Figuras Addison Wesley

� Recorte

� Cohen-Sutherland

Sumário

� Recorte 2D

� Paramétrico


� Paramétrico

� Cyrus-Beck e Liang-Barsky

� Sutherland-Hodgman

� Recorte 3D

Computação Gráfica

Recorte 2DRecorte 2D

Recorte de Linhas� Contra um rectângulo de recorte

� Extremos dentro [AB] ⇒ manter segmento� Um fora outro dentro [CD] ⇒ manter sub-segmento� Ambos fora [GH ou IJ] ⇒ rejeitar se não houver pts interscção; manter sub-segmento

� Abordagem “Força Bruta” não é eficiente� Usam-se algoritmos desenvolvidos para o efeito


� Usam-se algoritmos desenvolvidos para o efeito

5

Rectângulode Recorte

A

B C

D

E

F

G

H

I

J

G´

D´F´

H´

I´

J´

Recorte

A

B C

G´

D´

H´

(na última aula)

Recorte de Linhas� Algoritmo de Cohen-Sutherland

� Divide o plano em nove regiões� Atribui OUTCODE a cada uma dessas regiões� Aceita ou rejeita segmentos trivialmente

� De acordo com outcode

� Restantes segmentos são divididos� Intersecção com limites das regiões


� Intersecção com limites das regiões� Aceitação ou rejeição de sub-segmentos será então trivial

6

0000

1000 10101001

0010

0100

0001

0101 0110

Algoritmo de Cohen -Sutherland

� Especialmente eficiente em duas situações:� Janelas rectangulares “grandes”

� Rectângulo abrange quase toda as linhas� Grande parte dos segmentos trivialmente aceites


� “Pick” (selecção de objectos), � Rectângulo de recorte pequeno� Centrado na posição do cursor � Muitos segmentos trivialmente rejeitados



Algoritmo Paramétrico

Algoritmo de Cyrus -Beck (1/5)

(Algoritmo de Recorte Paramétrico)� Recorte por qualquer polígono convexo 2D� Generalizável a Recorte 3D por poliedros convexos.� Baseia-se na equação paramétrica da recta


t=t1

t=t2

t=t3

t=t4

P(t) = P0 + (P1 - P0) t


� Para segmentos trivais (polígono rectangular)� Aplicar Cohen Sutherland

� Para segmentos não triviais� Usar equações paramétricas da recta� Calcular os 4 valores de t

� Intersecção com rectas definidas pela aresta da janela


� Por comparação descobrir quais dos 4 são intersecções � Calcular (x, y) para esses (2 máx)

t=t1

t=t2

t=t3

t=t4


Lado E

PeiNi

P0

P1

Ni . [P(t) - Pei] < 0

Ni . [P(t) - Pei] = 0

Ni . [P(t) - Pei] > 0

Ei: Aresta do polígono

Pei: Ponto sobre Ei

Ni: Normal exterior a Ei

P(t): intersecção entre segmento e polígono


Lado Ei segmento e polígono

P(t) = P0 + (P1 - P0).t

Condição de intersecção: Ni . [P(t) - Pei] = 0Ni . [P0 + (P1 - P0).t - Pei] = 0Ni . [P0 - Pei] + Ni . [P1 - P0].t = 0

Sendo D = [P1 - P0],t =

Ni . [P0 - Pei]

- Ni . D


� Ni . D não pode ser nulo!t =

Ni . [P0 - Pei]

- Ni . D

Ni = 0 Só por engano (o polígono de recorte seja degenerado)

D = 0 Só se P0 = P1 (segmento nulo: inválido)


� Ignoramos t ∉ [0, 1] � fora do segmento P0-P1

� Para t ∈ [0, 1], � verificar se ponto ∈ aresta de recorte

Ni.D = 0 Segmento paralelo à aresta de recorte, logonão se intersectam (ver aresta seguinte)


Tabela de Cálculo para Polígonos Rectangulares

Lado de Recorte Ei Ni Pei P0 - Pei t =

left: X = Xmin [-1 0] (Xmin, Y) (X0 - Xmin, Y0 - Y) - (X0 - Xmin)

Ni . (P0 - Pei)

- Ni . D

(X1 - X0)


right: X = Xmax [1 0] (Xmax, Y) (X0 - Xmax, Y0 - Y) (X0 - Xmax)

bottom: Y = Ymin [0 -1] (X, Ymin) (X0 - X, Y0 - Ymin) - (Y0 - Ymin)

top: Y = Ymax [0 1] (X, Ymax) (X0 - X, Y0 - Ymax) (Y0 - Ymax)

- (X1 - X0)

(Y1 - Y0)

- (Y1 - Y0)

Identificar Pontos de Intersecção

Algoritmo de Liang -Barsky

PL

PEP

P1PL

PE

(t=1)

P0(t=0)

P1

(t=1)

PE

PL

P0 (t=0)

P1

(t=1)PE

PL


PEP0 (t=0)

Ni . D < 0 => PE (Potentially Entering: angulo > 90º)Ni . D > 0 => PL (Potentialy Leaving: angulo < 90º)

• Identificar Te (PE com maior t) e Tl (PL com menor t) (por omissão, Te = 0 e Tl = 1) • Te > Tl ⇒ segmento de recta não intersecta polígono• Te < Tl ⇒ resultado do recorte: segmento [ P(Te) P(Tl) ]

Recorte

Recorte de PolígonosRecorte de Polígonos

Recorte de Polígonos




17

� Lados do Polígono testados com arestas de recorte� Lados iniciais podem ser:

� trivialmente aceites, rejeitados ou subdivididos

� Podem surgir novos lados � colineares com arestas de recorte

� O resultado final pode ser um ou mais polígonos



Algoritmo de Sutherland -Hodgman (1/4)

� Abordagem “Dividir para Reinar”� Recortes sucessivos do polígono por aresta infinita� Quatro passos (um para cada aresta)



� Quatro passos (um para cada aresta)� Em cada passo:

� Entrada = cadeia de vértices (V1, V2, …, Vn) � Resultado = nova cadeia de vértices (polígono recortado)� Resultado do passo N = Entrada do N+1


Passo 1: Left Clip

N N+1





N N+1

Passo 2: Top Clip





N N+1

Passo 3: Right Clip





N N+1

Passo 4 : Bottom Clip


� Executa o chamado “pipeline clipping”� Quatro andares de clipping

� Um para cada aresta

� Pode-se aplicar o Cohen-Sutherland� Aresta a aresta

©2010, CG&M/IST e Figuras Addison Wesley24

LeftClip Top Clip

RightClip

BottomClip

Inserção de pontos

Algoritmo deSutherland -Hodgman (4/4)

Interior Exterior

S

P

Interior Exterior

S

P

Interior Exterior

S

PI

Interior Exterior

S

P I


P S

Caso 1: Caso 2: Caso 3: Caso 4:Inserir ponto P Inserir ponto I Não insere pontos Insere primeiro I

Insere depois P

Pode gerar falsos lados(remover a posteriori)

Algoritmo deSutherland -Hodgman (EXEMPLO)


P0

P1

P2

P3

P


P0P5

P

P7


P4

P5

P6

P7P1

P2

P4

P6P3

LeftClip


P0P5

P

P7P0

P1

P2

P3

P


P1P2

P4

P6

Left Clip[P0 P1] ⇒ Não insere ponto

P3

P4

P5

P6

P7


P0P5

P

P7P0

P1

P2

P3

P

I0

P2


P1P2

P4

P6

Left Clip[P1 P2] ⇒ Insere pontos I0 P2

P2I0

P3

P4

P5

P6

P7


P0P5

P

P7P0

P1

P2

P3

P

I0

P2

P3


P1 P2

P4

P6

Left Clip[P2 P3] ⇒ Insere ponto P3

P2I0

P3 P3

P4

P5

P6

P7


P0P5

P

P7P0

P1

P2

P3

P

I0

P2

P3

I1


P1 P2

P4

P6

Left Clip[P3 P4] ⇒ Insere ponto I1

P2I0

P3 P3

I1P4

P5

P6

P7


P0P5

P

P7

I

P0

P1

P2

P3

P

I0

P2

P3

I1


P1 P2

P4

P6

Left Clip[P4 P5] ⇒ Não insere ponto

P2I0

I2 P3 P3

I1P4

P5

P6

P7


P0P5

P

P7P0

P1

P2

P3

P

I0

P2

P3

I1

I

I2


P1 P2

P4

P6

Left Clip[P5 P6] ⇒ Insere pontos I2 e P6

P2I0

P3 P3

I1P4

P5

P6

P7

I2

P6

P6


P0P5

P

P7P0

P1

P2

P3

P

I0

P2

P3

I1

I

I2

P7


P1 P2

P4

P6

Left Clip[P6 P7] ⇒ Insere ponto P7

P2I0

P3 P3

I1P4

P5

P6

P7

I2

P6

P7

P6


P0P5

P

P7P0

P1

P2

P3

P

I0

P2

P3

I1

I

I2

P7I3


P1 P2

P4

P6

Left Clip[P7 P0] ⇒ Insere ponto I3

P2I0

P3 P3

I1P4

P5

P6

P7

I2

P6

P7

I3

P6


P5

P

P7I0

P2

P3

I1

I

I2

I3


P2

P6I1 P3

I2

P6

P7

I3I0

Resultado após

Left Clip

Top Clip


P5

P

P7I0

P2

P3

I1

I

P2

I2

I3


P2

P6

Top Clip[I 0 P2] ⇒ Insere ponto P2

P2

I1 P3

I2

P6

P7

I3I0


P5

P

P7I0

P2

P3

I1

I

P2

P3I2

I3


P2

P6

Top Clip[P2 P3] ⇒ Insere ponto P3

P2

I1 P3

I2

P6

P7

I3I0

P3


P5

P

P7I0

P2

P3

I1

I

P2

P3

I1

I2

I3


P2

P6

Top Clip[P3 I1] ⇒ Insere ponto I1

P2

I1 P3

I2

P6

P7

I3I0

P3

I1


P5

P

P7I0

P2

P3

I1

I

P2

P3

I1

I4

I2

I3

I4


P2

P6

Top Clip[I 1 I2] ⇒ Insere ponto I4

P2

I1 P3

I2

P6

P7

I3I0

P3

I1


P5

P

P7I0

P2

P3

I1

I

P2

P3

I1

I4

I

I2

I3

I4

I5


P2

P6

Top Clip[I 2 P6] ⇒ Insere pontos I5 e P6

P2

I1 P3

I2

P6

P7

I3

I5

P6

I0

P3

I1 P6


P5

P

P7I0

P2

P3

I1

I

P2

P3

I1

I4

I

I2

I3

I4

I5 I6


P2

P6

Top Clip[P6 P7] ⇒ Insere ponto I6

P2

I1 P3

I2

P6

P7

I3

I5

P6

I6I0

P3

I1 P6


P5

P

P7I0

P2

P3

I1

I

P2

P3

I1

I4

I

I2

I3

I4

I5 I6


P2

P6

Top Clip[P7 I3] ⇒ Não insere pontos

P2

I1 P3

I2

P6

P7

I3

I5

P6

I6I0

P3

I1 P6


P5

P

P7I0

P2

P3

I1

I

P2

P3

I1

I4

I

I2

I3

I4 = I 7I5 I6


P2

P6

Top Clip[I 3 I0] ⇒ Insere pontos I7 e I0

P2

I1 P3

I2

P6

P7

I3

I5

P6

I6

I7

I0

I0

P3

I1 P6

I0


P

I4 = I 7 I5 I6

P2

P3

I1

I4

I P

I4 = I 7 I5 I6

P3

I1

I4

I5

P


P2

P6I1 P3

I0

I5

P6

I6

I7

I0

Resultado após

Top Clip

RightClip

P2

P6I1 P3

I0

P6

I6

I7

I0

P2


P

I4 = I 7 I5 I6

P3

I1

I4

I5

P P

I4 = I 7 I5 I6

I1

I4

I5

P6

I


P2

P6I1 P3

I0

P6

I6

I7

I0

P2

Resultado após

Right Clip

BottomClip

P2

P6I1 P3

I0

I6

I7

I0

P2

P3



Recorte


Recorte em 3D (1/3)

� Extensão do algoritmo de Cohen-Sutherland

� Usar Outcode de 6 bits:� bit 1: ponto em frente VV (z < 0)


bit 1: ponto em frente VV (z < 0)� bit 2: ponto atrás VV (z > 1)� bit 3: ponto acima Volume de Visualização (y > 1)� bit 4: ponto abaixo VV (y < -1)� bit 5: ponto à direita VV (x > 1)� bit 6: ponto à esquerda VV (x < -1)

Recorte em 3D (2/3)


Volume de Visualização

Recorte em 3D (3/3)

� Extensão algortimo de Cohen-Sutherland:� Aceitação trivial: OC1 = OC2 = 0� Rejeição trivial: OC1 & OC2 ≠ 0

� Calcular 6 intersecções recta-plano VV


� Calcular 6 intersecções recta-plano VV� x = x0 + t(x1 - x0)� y = y0 + t(y1 - y0)� z = z0 + t(z1 - z0), 0 ≤ t ≤ 1

� Idêntico para recorte de polígonos� Sutherland-Hodgman


Pipeline de Visualização 3DPipeline de Visualização 3D

Pipeline de Visualização 3D






Documents

Instituto Superior Técnico Computação Gráfica 2009/2010 · Algoritmo de Cohen-Sutherland ... Calcular os 4 valores de t ... verificar se ponto ∈aresta de recorte Ni.D = 0 Segmento