Alguns Algoritmos Clássicos

Computação Gráfica
Walderson Shimokawa
46
4 Alguns Algoritmos Clássicos
Embora a programação seja uma atividade muito criativa, quase sempre requerendo que
(pequenos) problemas inteiramente novos sejam resolvidos, às vezes podemos nos beneficiar de
algoritmos bem conhecidos, publicados por outros e que geralmente fornecem soluções mais eficientes ou
mais elegantes do que aquelas que teríamos sido capazes de inventar nós mesmos. Com a computação
gráfica isso não é diferente. Esse capítulo é sobre alguns algoritmos gráficos bem conhecidos para (a)
calcular as coordenadas dos pixels que constituem retas e círculos, (b) recortar retas e polígonos e (c)
desenhar curvas suaves. Essas são as operações mais primitivas em computação gráfica e devem ser
executadas com a maior rapidez possível. Portanto, os algoritmos neste capítulo são otimizados para evitar
execuções demoradas, como multiplicações, divisões e cálculos de ponto flutuante.
4.1 O Algoritmo de Bresenham para o Desenho de Retas
Discutiremos agora como desenhar retas colocando pixels na tela. Apesar de, em Java, podermos
simplesmente usar o método drawLine sem nos preocuparmos com pixels, isso seria insatisfatório se não
soubéssemos como esse método funciona. Infelizmente, Java não possui um método com o único
propósito de colocar um pixel na tela, de modo que definimos o seguinte método, um tanto estranho, para
obtermos isso:
void putPixel(Graphics g, int x, int y)
{ g.drawLine(g, x, y, x, y);
}
Agora desenvolvemos um método drawLine da forma
void drawLine(Graphics g, int xP, int yP, int xQ, int yQ)
{ ...
}
que só usa o método putPixel anterior para a saída gráfica.
A Figura 30 mostra um segmento de reta com pontos extremos P(1, 1) e Q(12, 5), assim como os
pixels que temos que calcular para aproximar essa reta.
Figura 30: Pontos de grade aproximando um segmento de reta
A primeira versão a seguir do método drawLine é baseada no arredondamento do pixel mais
próximo, sendo 0,5 a margem de erro aceitável:
void drawLine1(Graphics g, int xP, int yP, int xQ, int yQ)
{ int x = xP, y = yP;
float d = 0, m = (float)(yQ - yP)/(float)(xQ - xP);
for (;;)
{ putPixel(g, x, y);
Computação Gráfica
Walderson Shimokawa
47
if (x == xQ) break;
x++;
d += m;
if (d >= 0.5) {y++; d--;};
}
}
A taxa de inclinação m e o erro d, presentes no código-fonte acima pode ser verificada na Figura 32, abaixo,
pois os pixels possuem endereçamento inteiro em vez de endereços baseados em números de ponto
flutuante (Figura 31).
Figura 31: Algoritmo incremental para definir a posição do próximo ponto
Figura 32: Inclinação m e erro d
Podemos melhorar o algoritmo do método drawLine trabalhando apenas com expressões inteiras:
void drawLine2(Graphics g, int xP, int yP, int xQ, int yQ)
{ int x = xP, y = yP, d = 0, dx = xQ – xP, c = 2 * dx,
m = 2 * (yQ - yP);
for (;;)
{ putPixel(g, x, y);
if (x == xQ) break;
x++;
d += m;
if (d >= dx) {y++; d -= c;};
}
}
Para retas que possuem ângulo de inclinação superior a 45, existe a necessidade de se trocar os
papéis de x e y para evitar que os pixels selecionados fiquem muito longes. Estas situações estão incluídas
no método geral de desenho de retas drawLine a seguir:
Computação Gráfica
Walderson Shimokawa
48
void drawLine(Graphics g, int xP, int yP, int xQ, int yQ)
{ int x = xP, y = yP, d = 0, dx = xQ – xP, dy = yQ – yP,
c, m, xInc = 1, yInc = 1;
if (dx < 0){xInc = -1; dx = -dx;}
if (dy < 0){yInc = -1; dy = -dy;}
if (dy <= dx)
{ c = 2 * dx; m = 2 * dy;
if (xInc < 0) dx++;
for (;;)
{ putPixel(g, x, y);
if (x == xQ) break;
x += xInc;
d += m;
if (d >= dx) {y += yInc; d -= c;};
}
}
else
{ c = 2 * dy; m = 2 * dx;
if (yInc < 0) dy++;
for (;;)
{ putPixel(g, x, y);
if (y == yQ) break;
y += yInc;
d += m;
if (d >= dy) {x += xInc; d -= c;};
}
}
}
A ideia de desenhar retas apenas usando variáveis inteiras foi primeiramente concebida por
Bresenham; seu nome é portanto associado a esse algoritmo.
4.2 Dobrando a Velocidade do Desenho de Retas
Como uma das operações gráficas básicas, o desenho de retas deve ser executado tão rapidamente
quanto possível. Na verdade, o hardware gráfico geralmente é avaliado pela velocidade na qual gera retas.
O algoritmo de retas de Bresenham é simples e eficiente na geração de retas, pois trabalha de forma
incremental calculando a posição do primeiro pixel a ser desenhado. Assim, ele itera tantas vezes quanto o
número de pixels a serem desenhados. O algoritmo de desenhos de retas em passo duplo de Rokne, Wyvill
e Wu (1990) objetiva a redução do número de iterações pela metade, calculando as posições dos próximos
dois pixels. Os quatro padrões de passo duplo possíveis são ilustrados na Figura 33:
Figura 33: Quatro padrões de passo duplo quando 0  inclinação  1
Os padrões 1 e 4 não podem ocorrer na mesma linha, como mostra a figura 34:
Figura 34: Escolha de padrões baseada no erro inicial d e na inclinação m
Computação Gráfica
Walderson Shimokawa
49
Como na seção anterior, ao discutirmos o algoritmo de Bresenham, começamos com um método
preliminar que ainda usa variáveis de ponto flutuante para torná-lo mais fácil de ser entendido, ainda que
não esteja otimizado tendo em vista a velocidade. Essa versão também funciona com retas desenhadas da
direita para a esquerda, ou seja, quando xQ < xP, assim como para retas com inclinação negativa. Todavia, o
valor absoluto da inclinação não deve ser maior que 1.
void doubleStep1(Graphics g, int xP, int yP, int xQ, int yQ)
{ int dx, dy, x, y, yInc;
if (xP >= xQ)
{ if (xP == xQ) // Não permitido porque dividimos por (dx = xQ - xP)
return;
// xP > xQ, então permute os pontos P e Q
int t;
t = xP; xP = xQ; xQ = t;
t = yP; yP = yQ; yQ = t;
}
// Agora xP < xQ
if (yQ >= yP){yInc = 1; dy = yQ - yP;} // Caso normal, yP < yQ
else
{yInc = -1; dy = yP - yQ;}
dx = xQ - xP; // dx > 0, dy > 0
float d = 0,
// Erro d = yexact - y
m = (float)dy/(float)dx; // m <= 1, m = |inclinação|
putPixel(g, xP, yP);
y = yP;
for (x=xP; x<xQ-1;)
{ if (d + 2 * m < 0.5) // Padrão 1:
{ putPixel(g, ++x, y);
putPixel(g, ++x, y);
d += 2 * m; // O erro aumenta em 2m, já que y permanece
// inalterado e yexact aumenta em 2m
}
else
if (d + 2 * m < 1.5) // Padrão 2 ou 3
{ if (d + m < 0.5) // Padrão 2
{ putPixel(g, ++x, y);
putPixel(g, ++x, y += yInc);
d += 2 * m - 1; // Devido a ++y, o erro é agora
// 1 a menos que com padrão 1
}
else // Padrão 3
{ putPixel(g, ++x, y += yInc);
putPixel(g, ++x, y);
d += 2 * m - 1; // Mesmo do padrão 2
}
}
else // Padrão 4:
{ putPixel(g, ++x, y += yInc);
putPixel(g, ++x, y += yInc);
d += 2 * m - 2; // Devido a y += 2, o erro é agora
// 2 a menos que com o padrão 1
}
}
if (x < xQ)
// x = xQ - 1
putPixel(g, xQ, yQ);
}
Uma versão mais eficiente da implementação para desenhar retas com padrões de passo duplo,
utilizando números inteiros em vez de ponto flutuante é apresentado a seguir, no método doubleStep2:
void doubleStep2(Graphics g, int xP, int yP, int xQ, int yQ)
{ int dx, dy, x, y, yInc;
Computação Gráfica
Walderson Shimokawa
50
if (xP >= xQ)
{ if (xP == xQ) // Não permitido porque dividimos por (dx = xQ - xP)
return;
int t;
// xP > xQ, então permute os pontos P e Q
t = xP; xP = xQ; xQ = t;
t = yP; yP = yQ; yQ = t;
}
// Agora xP < xQ
if (yQ >= yP){yInc = 1; dy = yQ - yP;}
else
{yInc = -1; dy = yP - yQ;}
dx = xQ - xP;
int dy4 = dy * 4, v = dy4 - dx, dx2 = 2 * dx, dy2 = 2 * dy,
dy4Minusdx2 = dy4 - dx2, dy4Minusdx4 = dy4Minusdx2 - dx2;
putPixel(g, xP, yP);
y = yP;
for (x=xP; x<xQ-1;)
{ if (v < 0)
// Equivalente a d + 2 * m < 0.5
{ putPixel(g, ++x, y);
// Padrão 1
putPixel(g, ++x, y);
v += dy4;
// Equivalente a d += 2 * m
}
else
if (v < dx2)
// Equivalente a d + 2 * m < 1.5
{ // Padrão 2 ou 3
if (v < dy2)
// Equivalente a d + m < 0.5
{ putPixel(g, ++x, y);
// Padrão 2
putPixel(g, ++x, y += yInc);
v += dy4Minusdx2;
// Equivalente a d += 2 * m - 1
}
else
{ putPixel(g, ++x, y += yInc); // Padrão 3
putPixel(g, ++x, y);
v += dy4Minusdx2;
// Equivalente a d += 2 * m - 1
}
}
else
{ putPixel(g, ++x, y += yInc); // Padrão 4
putPixel(g, ++x, y += yInc);
v += dy4Minusdx4;
// Equivalente a d += 2 * m - 2
}
}
if (x < xQ)
putPixel(g, xQ, yQ);
}
O método doubleStep2 acima só funciona se
−
≤
−
. Se desejar, o método acima
pode ser generalizado para trabalhar com qualquer reta, como foi feito com o algoritmo de Bresenham.
Da mesma forma que o algoritmo de Bresenham, o algoritmo passo duplo calcula apenas com
inteiros. Para retas longas ele tem um desempenho quase duas vezes melhor que o algoritmo de
Bresenham. Pode-se otimizá-lo ainda mais para se obter uma outra duplicação de velocidade aproveitandose da simetria em torno do ponto central de uma determinada reta.
4.3 Círculos
Nesta seção iremos ignorar a forma usual de se desenhar um círculo em Java por meio de
chamadas como
g.drawOval(xC – r, yC – r, 2 * r, 2 * r);
Computação Gráfica
Walderson Shimokawa
51
já que é nosso objetivo construirmos nós mesmos tal círculo, com centro C(xC, yC) e raio r, em que as
coordenadas de C e do raio são dadas como inteiros. Desenvolveremos um método na forma de:
void drawCircle(Graphics g, int xC, int yC, int r)
{ ...
}
que só usa o método putPixel da seção anterior como “primitiva gráfica” e que é uma implementação do
algoritmo de Bresenham para círculos. O círculo desenhado dessa forma será exatamente o mesmo
produzido pela chamada anterior drawOval. Em ambos os casos, x varia de xC – r a xC + r, incluindo esses
dois valores, de modo que 2r + 1 valores de r serão usados.
Assim como nas seções anteriores, começamos com um caso simples: usamos a origem do sistema
de coordenadas como o centro do círculo, e, dividindo o círculo em oito arcos de comprimento igual, nos
restringimos a um deles, o arco PQ. A equação deste círculo é:
x2 + y2 = r2
A Figura 35 mostra a situação, incluindo a grade de pixels, para o caso de r = 8. Começando pelo
topo no ponto P, com x = 0 e y = r, usaremos um laço no qual incrementamos x em 1 a cada passo; como na
seção anterior, precisamos de um teste para decidir se podemos deixar y sem alteração. Se esse não for o
caso, temos que decrementar y em 1.
Figura 35: Pixels que aproximam o arco PQ
Para tornar nosso algoritmo mais rápido, evitaremos calcular os quadrados x2 e y2, introduzindo
três novas variáveis inteiras não negativas u, v e E denotando as diferenças entre dois quadrados sucessivos
e o ‘erro’:
= ( − 1) −
=2 +1
=
− ( − 1) = 2 + 1
=
+
−
Agora podemos escrever o seguinte método para desenhar o arco PQ:
void arc8(Graphics g, int r)
{ int x = 0, y = r, u = 1, v = 2 * r - 1, e = 0;
while (x <= y)
{ putPixel(g, x, y);
x++; e += u; u += 2;
if (v < 2 * e) {y--; e -= v; v -= 2;}
}
}
Computação Gráfica
Walderson Shimokawa
52
O método arc8 é a base do nosso método final, drawCircle, listado a seguir. Além de desenhar um
círculo completo, ele também é mais geral do que arc8 por permitir que um ponto C arbitrário seja
especificado como o centro do círculo.
void drawCircle(Graphics g, int xC, int yC, int r)
{ int x = 0, y = r, u = 1, v = 2 * r - 1, E = 0;
while (x < y)
{ putPixel(g, xC + x, yC + y); // NNE
putPixel(g, xC + y, yC - x); // ESE
putPixel(g, xC - x, yC - y); // SSW
putPixel(g, xC - y, yC + x); // WNW
x++; E += u; u += 2;
if (v < 2 * E){y--; E -= v; v -= 2;}
if (x > y) break;
putPixel(g, xC + y, yC + x); // ENE
putPixel(g, xC + x, yC - y); // SSE
putPixel(g, xC - y, yC - x); // WSW
putPixel(g, xC - x, yC + y); // NNW
}
}
4.4 Recorte de Retas Cohen-Sutherland
Nesta seção discutiremos como desenhar segmentos de retas apenas quando estiverem dentro de
um determinado retângulo. As decisões lógicas necessárias para se descobrir que ações tomar tornam o
recorte de retas um tópico interessante do ponto de vista algorítmico. O algoritmo Cohen-Sutherland
resolve esse problema de uma forma elegante e eficiente. Expressaremos esse algoritmo em Java (classe
ClipLine):
import java.awt.*;
import java.awt.event.*;
import java.util.*;
public class ClipLine extends Frame
{ public static void main(String[] args){new ClipLine();}
ClipLine()
{ super("Clique em dois vértices opostos de um retângulo");
addWindowListener(new WindowAdapter()
{public void windowClosing(WindowEvent e){System.exit(0);}});
setSize(500, 300);
add("Center", new CvClipLine());
setCursor(Cursor.getPredefinedCursor(Cursor.CROSSHAIR_CURSOR));
show();
}
}
class CvClipLine extends Canvas
{ float xmin, xmax, ymin, ymax,
rWidth = 10.0F, rHeight = 7.5F, pixelSize;
int maxX, maxY, centerX, centerY, np=0;
CvClipLine()
{ addMouseListener(new MouseAdapter()
{ public void mousePressed(MouseEvent evt)
{ float x = fx(evt.getX()), y = fy(evt.getY());
if (np == 2) np = 0;
if (np == 0){xmin = x; ymin = y;}
else
{ xmax = x; ymax = y;
if (xmax < xmin)
Computação Gráfica
Walderson Shimokawa
53
{ float t = xmax; xmax = xmin; xmin = t;
}
if (ymax < ymin)
{ float t = ymax; ymax = ymin; ymin = t;
}
}
np++;
repaint();
}
});
}
void initgr()
{ Dimension d = getSize();
maxX = d.width - 1; maxY = d.height - 1;
pixelSize = Math.max(rWidth/maxX, rHeight/maxY);
centerX = maxX/2; centerY = maxY/2;
}
int iX(float
int iY(float
float fx(int
float fy(int
x){return
y){return
x){return
y){return
Math.round(centerX + x/pixelSize);}
Math.round(centerY - y/pixelSize);}
(x - centerX) * pixelSize;}
(centerY - y) * pixelSize;}
void drawLine(Graphics g, float xP, float yP,
float xQ, float yQ)
{ g.drawLine(iX(xP), iY(yP), iX(xQ), iY(yQ));
}
int clipCode(float x, float y)
{ return
(x < xmin ? 8 : 0) | (x > xmax ? 4 : 0) |
(y < ymin ? 2 : 0) | (y > ymax ? 1 : 0);
}
void clipLine(Graphics g,
float xP, float yP, float xQ, float yQ,
float xmin, float ymin, float xmax, float ymax)
{ int cP = clipCode(xP, yP), cQ = clipCode(xQ, yQ);
float dx, dy;
while ((cP | cQ) != 0)
{ if ((cP & cQ) != 0) return;
dx = xQ - xP; dy = yQ - yP;
if (cP != 0)
{ if ((cP & 8) == 8){yP += (xmin-xP) * dy / dx;
else
if ((cP & 4) == 4){yP += (xmax-xP) * dy / dx;
else
if ((cP & 2) == 2){xP += (ymin-yP) * dx / dy;
else
if ((cP & 1) == 1){xP += (ymax-yP) * dx / dy;
cP = clipCode(xP, yP);
}
else
if (cQ != 0)
{ if ((cQ & 8) == 8){yQ += (xmin-xQ) * dy / dx;
else
if ((cQ & 4) == 4){yQ += (xmax-xQ) * dy / dx;
else
if ((cQ & 2) == 2){xQ += (ymin-yQ) * dx / dy;
else
if ((cQ & 1) == 1){xQ += (ymax-yQ) * dx / dy;
cQ = clipCode(xQ, yQ);
}
xP = xmin;}
xP = xmax;}
yP = ymin;}
yP = ymax;}
xQ = xmin;}
xQ = xmax;}
yQ = ymin;}
yQ = ymax;}
Computação Gráfica
Walderson Shimokawa
54
}
drawLine(g, xP, yP, xQ, yQ);
}
public void paint(Graphics g)
{ initgr();
if (np == 1)
{ // Desenha linhas horizontais e verticais através
// do primeiro ponto definido:
drawLine(g, fx(0), ymin, fx(maxX), ymin);
drawLine(g, xmin, fy(0), xmin, fy(maxY));
} else
if (np == 2)
{ // Desenha retângulo:
drawLine(g, xmin, ymin, xmax, ymin);
drawLine(g, xmax, ymin, xmax, ymax);
drawLine(g, xmax, ymax, xmin, ymax);
drawLine(g, xmin, ymax, xmin, ymin);
// Desenha 20 pentágonos regulares concêntricos,
// desde que eles estejam localizados dentro do retângulo:
float rMax = Math.min(rWidth, rHeight)/2,
deltaR = rMax/20, dPhi = (float)(0.4 * Math.PI);
for (int j=1; j<=20; j++)
{ float r = j * deltaR;
// Desenha um pentágono:
float xA, yA, xB = r, yB = 0;
for (int i=1; i<=5; i++)
{ float phi = i * dPhi;
xA = xB; yA = yB;
xB = (float)(r * Math.cos(phi));
yB = (float)(r * Math.sin(phi));
clipLine(g, xA, yA, xB, yB, xmin, ymin, xmax, ymax);
}
}
}
}
}
O programa desenha 20 pentágonos concêntricos (regulares), desde que se localizem dentro de um
retângulo, que o usuário pode definir clicando em quaisquer dois vértices opostos. Quando ele clica pela
terceira vez, a situação é a mesma do início: a tela é limpa e um novo retângulo pode ser definido, no qual
novamente partes de 20 pentágonos aparecem, e assim por diante. Como de costume, se o usuário alterar
as dimensões da janela, o tamanho do desenho é alterado apropriadamente. A Figura 36 mostra a situação
logo após os pentágonos terem sido desenhados.
Figura 36: Demonstração do programa ClipLine.java
Computação Gráfica
Walderson Shimokawa
55
4.5 Recorde de Polígonos de Sutherland-Hodgman
Em contraste com o recorte de retas, discutido na seção anterior, agora lidaremos com o recorte de
polígonos, que é diferente pelo fato de converter um polígono em outro dentro de um determinado
retângulo, como as Figuras 37 e 38 ilustram.
Figura 37: Nove vértices do polígono definidos; o lado final ainda não está desenhado
Figura 38: Polígono completo e recortado
O programa que discutiremos desenha um retângulo fixo e permite ao usuário especificar os
vértices de um polígono clicando na mesma forma discutida na seção 1.5. Desde que o primeiro vértice, na
Figura 37 acima, não seja selecionado pela segunda vez, sucessivos vértices são conectados pelos lados do
polígono. Assim que o primeiro vértice é selecionado novamente, o polígono é recortado, como a Figura 38
mostra. Alguns vértices do polígono original não pertencem ao polígono recortado. Por outro lado, este
último polígono possui alguns vértices novos, que são todos pontos de interseção dos lados do polígono
original com os do retângulo. De modo geral, o número de vértices do polígono recortado pode ser maior,
igual ou menor que o do original. Na Figura 38 há cinco novos lados do polígono, que são parte dos lados
do retângulo.
Computação Gráfica
Walderson Shimokawa
56
O programa que produziu a Figura 38 é baseado no algoritmo de Sutherland-Hodgman, que
primeiro recorta todos os lados do polígono contra um lado do retângulo, ou melhor, a reta infinita através
de tal lado. Isso resulta em um novo polígono, que é então recortado contra o próximo lado do retângulo, e
assim por diante. A Figura 39 ilustra este processo. A Figura 40 mostra um retângulo e um polígono,
ABCDEF, gerando um novo polígono de saída IJKLFA.
Figura 39: Recorta o polígono dado contra um lado do retângulo por vez
Figura 40: Polígono ABCDEF recortado para IJKLFA
O programa a seguir (ClipPoly.java) mostra uma implementação em Java para executar o corte de
polígonos fora da área de desenho.
import java.awt.*;
import java.awt.event.*;
import java.util.*;
public class ClipPoly extends Frame
{ public static void main(String[] args){new ClipPoly();}
ClipPoly()
{ super("Defina os vértices do polígono clicando");
addWindowListener(new WindowAdapter()
{public void windowClosing(WindowEvent e){System.exit(0);}});
setSize(500, 300);
add("Center", new CvClipPoly());
setCursor(Cursor.getPredefinedCursor(Cursor.CROSSHAIR_CURSOR));
show();
}
}
Computação Gráfica
Walderson Shimokawa
class CvClipPoly extends Canvas
{ Poly poly = null;
float rWidth = 10.0F, rHeight = 7.5F, pixelSize;
int x0, y0, centerX, centerY;
boolean ready = true;
CvClipPoly()
{ addMouseListener(new MouseAdapter()
{ public void mousePressed(MouseEvent evt)
{ int x = evt.getX(), y = evt.getY();
if (ready)
{ poly = new Poly();
x0 = x; y0 = y;
ready = false;
}
if (poly.size() > 0 &&
Math.abs(x - x0) < 3 && Math.abs(y - y0) < 3)
ready = true;
else
poly.addVertex(new Point2D(fx(x), fy(y)));
repaint();
}
});
}
void initgr()
{ Dimension d = getSize();
int maxX = d.width - 1, maxY = d.height - 1;
pixelSize = Math.max(rWidth/maxX, rHeight/maxY);
centerX = maxX/2; centerY = maxY/2;
}
int iX(float
int iY(float
float fx(int
float fy(int
x){return
y){return
x){return
y){return
Math.round(centerX + x/pixelSize);}
Math.round(centerY - y/pixelSize);}
(x - centerX) * pixelSize;}
(centerY - y) * pixelSize;}
void drawLine(Graphics g, float xP, float yP, float xQ, float yQ)
{ g.drawLine(iX(xP), iY(yP), iX(xQ), iY(yQ));
}
void drawPoly(Graphics g, Poly poly)
{ int n = poly.size();
if (n == 0) return;
Point2D a = poly.vertexAt(n - 1);
for (int i=0; i<n; i++)
{ Point2D b = poly.vertexAt(i);
drawLine(g, a.x, a.y, b.x, b.y);
a = b;
}
}
public void paint(Graphics g)
{ initgr();
float xmin = -rWidth/3, xmax = rWidth/3,
ymin = -rHeight/3, ymax = rHeight/3;
// Desenha o retângulo de corte:
g.setColor(Color.blue);
drawLine(g, xmin, ymin, xmax, ymin);
drawLine(g, xmax, ymin, xmax, ymax);
drawLine(g, xmax, ymax, xmin, ymax);
drawLine(g, xmin, ymax, xmin, ymin);
g.setColor(Color.black);
if (poly == null) return;
57
Computação Gráfica
Walderson Shimokawa
int n = poly.size();
if (n == 0) return;
Point2D a = poly.vertexAt(0);
if (!ready)
{ // Mostra um pequeno retângulo em torno do primeiro vértice:
g.drawRect(iX(a.x)-2, iY(a.y)-2, 4, 4);
// Desenha polígono incompleto:
for (int i=1; i<n; i++)
{ Point2D b = poly.vertexAt(i);
drawLine(g, a.x, a.y, b.x, b.y);
a = b;
}
} else
{ poly.clip(xmin, ymin, xmax, ymax);
drawPoly(g, poly);
}
}
}
class Poly
{ Vector v = new Vector();
void addVertex(Point2D p){v.addElement(p);}
int size(){return v.size();}
Point2D vertexAt(int i)
{ return (Point2D)v.elementAt(i);
}
void clip(float xmin, float ymin, float xmax, float ymax)
{ // Recorte de polígono de Sutherland-Hodgman:
Poly poly1 = new Poly();
int n;
Point2D a, b;
boolean aIns, bIns; // se A ou B estiver no mesmo
//
lado que o retângulo
// Corte contra x == xmax:
if ((n = size()) == 0) return;
b = vertexAt(n-1);
for (int i=0; i<n; i++)
{ a = b; b = vertexAt(i);
aIns = a.x <= xmax; bIns = b.x <= xmax;
if (aIns != bIns)
poly1.addVertex(new Point2D(xmax, a.y +
(b.y - a.y) * (xmax - a.x)/(b.x - a.x)));
if (bIns) poly1.addVertex(b);
}
v = poly1.v; poly1 = new Poly();
// Corte contra x == xmin:
if ((n = size()) == 0) return;
b = vertexAt(n-1);
for (int i=0; i<n; i++)
{ a = b; b = vertexAt(i);
aIns = a.x >= xmin; bIns = b.x >= xmin;
if (aIns != bIns)
poly1.addVertex(new Point2D(xmin, a.y +
(b.y - a.y) * (xmin - a.x)/(b.x - a.x)));
if (bIns) poly1.addVertex(b);
}
v = poly1.v; poly1 = new Poly();
// Corte contra y == ymax:
if ((n = size()) == 0) return;
b = vertexAt(n-1);
58
Computação Gráfica
Walderson Shimokawa
59
for (int i=0; i<n; i++)
{ a = b; b = vertexAt(i);
aIns = a.y <= ymax; bIns = b.y <= ymax;
if (aIns != bIns)
poly1.addVertex(new Point2D(a.x +
(b.x - a.x) * (ymax - a.y)/(b.y - a.y), ymax));
if (bIns) poly1.addVertex(b);
}
v = poly1.v; poly1 = new Poly();
// Corte contra y == ymin:
if ((n = size()) == 0) return;
b = vertexAt(n-1);
for (int i=0; i<n; i++)
{ a = b; b = vertexAt(i);
aIns = a.y >= ymin;
bIns = b.y >= ymin;
if (aIns != bIns)
poly1.addVertex(new Point2D(a.x +
(b.x - a.x) * (ymin - a.y)/(b.y - a.y), ymin));
if (bIns) poly1.addVertex(b);
}
v = poly1.v; poly1 = new Poly();
}
}
O algoritmo de Sutherland-Hodgman pode ser adaptado para o recorte de outras áreas que não
retângulos e para aplicações tridimensionais.
4.6 Curvas de Bézier
Há muitos algoritmos para desenhar curvas. Um especialmente elegante e prático é baseado na
especificação de quatro pontos que determinam totalmente um segmento de curva: dois pontos extremos
e dois pontos de controle. Curvas desenhadas dessa forma são chamadas de curvas (cúbicas) de Bézier. Na
Figura 41, temos os pontos extremos P0 e P3, os pontos de controle P1 e P2, e a curva desenhada com base
nesses quatro pontos.
Figura 41: Curva de Bézier baseada em quatro pontos
Escrever um método para desenhar essa curva é surpreendentemente fácil, desde que usemos
recursão. Como mostra a Figura 42, calculamos seis pontos médios, a saber:




A, o ponto médio de P0P1
B, o ponto médio de P2P3
C, o ponto médio de P1P2
A1, o ponto médio de AC
Computação Gráfica


Walderson Shimokawa
60
B1, o ponto médio de BC
C1, o ponto médio de A1B1
Figura 42: Definindo os pontos para dois segmentos de curva menores
Após isso, podemos dividir a tarefa original de desenhar a curva de Bézier P0P3 (com pontos de
controle P1 e P2) em duas tarefas mais simples:


Desenhar a curva de Bézier P0C1, com pontos de controle A e A1
Desenhar a curva de Bézier C1P3, com pontos de controle B1 e B
O método recursivo bezier no programa a seguir mostra uma implementação desse algoritmo. O
programa espera que o usuário especifique quatro pontos P0, P1, P2 e P3, nessa ordem, clicando com o
mouse. Após o quarto ponto, P3, ter sido especificado, a curva é desenhada. Qualquer novo clique do
mouse é interpretado como o primeiro ponto P0 de uma nova curva; a curva anterior simplesmente
desaparece e outra curva pode ser construída da mesma maneira que a primeira, e assim por diante.
import java.awt.*;
import java.awt.event.*;
import java.util.*;
public class Bezier extends Frame
{ public static void main(String[] args){new Bezier();}
Bezier()
{ super("Defina os pontos extremos e de controle do segmento");
addWindowListener(new WindowAdapter()
{public void windowClosing(WindowEvent e){System.exit(0);}});
setSize(500, 300);
add("Center", new CvBezier());
setCursor(Cursor.getPredefinedCursor(Cursor.CROSSHAIR_CURSOR));
show();
}
}
class CvBezier extends Canvas
{ Point2D[] p = new Point2D[4];
int np = 0, centerX, centerY;
float rWidth = 10.0F, rHeight = 7.5F, eps = rWidth/100F, pixelSize;
CvBezier()
{ addMouseListener(new MouseAdapter()
{ public void mousePressed(MouseEvent evt)
{ float x = fx(evt.getX()), y = fy(evt.getY());
if (np == 4) np = 0;
p[np++] = new Point2D(x, y);
repaint();
}
Computação Gráfica
Walderson Shimokawa
61
});
}
void initgr()
{ Dimension d = getSize();
int maxX = d.width - 1, maxY = d.height - 1;
pixelSize = Math.max(rWidth/maxX, rHeight/maxY);
centerX = maxX/2; centerY = maxY/2;
}
int iX(float x){return Math.round(centerX + x/pixelSize);}
int iY(float y){return Math.round(centerY - y/pixelSize);}
float fx(int x){return (x - centerX) * pixelSize;}
float fy(int y){return (centerY - y) * pixelSize;}
Point2D middle(Point2D a, Point2D b)
{ return new Point2D((a.x + b.x)/2, (a.y + b.y)/2);
}
void bezier(Graphics g, Point2D p0, Point2D p1,
Point2D p2, Point2D p3)
{ int x0 = iX(p0.x), y0 = iY(p0.y),
x3 = iX(p3.x), y3 = iY(p3.y);
if (Math.abs(x0 - x3) <= 1 && Math.abs(y0 - y3) <= 1)
g.drawLine(x0, y0, x3, y3);
else
{ Point2D a = middle(p0, p1), b = middle(p3, p2),
c = middle(p1, p2), a1 = middle(a, c),
b1 = middle(b, c), c1 = middle(a1, b1);
bezier(g, p0, a, a1, c1);
bezier(g, c1, b1, b, p3);
}
}
public void paint(Graphics g)
{ initgr();
int left = iX(-rWidth/2), right = iX(rWidth/2),
bottom = iY(-rHeight/2), top = iY(rHeight/2);
g.drawRect(left, top, right - left, bottom - top);
for (int i=0; i<np; i++)
{ // Mostra pequeno retângulo em torno do ponto:
g.drawRect(iX(p[i].x)-2, iY(p[i].y)-2, 4, 4);
if (i > 0)
// Desenha reta p[i-1]p[i]:
g.drawLine(iX(p[i-1].x), iY(p[i-1].y),
iX(p[i].x), iY(p[i].y));
}
if (np == 4) bezier(g, p[0], p[1], p[2], p[3]);
}
}
Como esse programa usa o modo de mapeamento isotrópico com intervalo de coordenadas lógicas
0-10,0 para x e 0-7,5 para y, só devemos usar um retângulo cuja altura seja 75% de sua largura. Como nas
seções 1.4 e 1.5, colocamos esse retângulo no centro da tela e o tornamos o maior possível. Ele é mostrado
na Figura 43; se os quatro pontos para a curva forem escolhidos dentro desse retângulo, eles serão visíveis
independentemente de como o tamanho da janela é alterado pelo usuário. O mesmo se aplica à curva, que
é automaticamente escalada, da mesma forma que fizemos nas seções 1.4 e 1.5.
Computação Gráfica
Walderson Shimokawa
62
Figura 43: Uma curva de Bézier desenhada
Como métodos recursivos podem gastar muitos recursos computacionais, podemos substituir o
método recursivo bezier, do programa apresentado acima, pelo seguinte método não-recursivo:
void bezier1(Graphics g, Point2D[] p)
{ int n = 200;
float dt = 1.0F/n, x = p[0].x, y = p[0].y, x0, y0;
for (int i=1; i<=n; i++)
{ float t = i * dt, u = 1 - t,
tuTriple = 3 * t * u,
c0 = u * u * u,
c1 = tuTriple * u,
c2 = tuTriple * t,
c3 = t * t * t;
x0 = x; y0 = y;
x = c0*p[0].x + c1*p[1].x + c2*p[2].x + c3*p[3].x;
y = c0*p[0].y + c1*p[1].y + c2*p[2].y + c3*p[3].y;
g.drawLine(iX(x0), iY(y0), iX(x), iY(y));
}
}
Este método produz a mesma curva que a produzida por bezier, desde que também substituamos a
chamada a bezier por esta:
bezier1(g, p);
Considerando que B(t) denota a posição no tempo t, a derivada B’(t) dessa função (que também é
um vetor coluna em t) pode ser considerada a velocidade. Após alguma manipulação algébrica, a derivação
resulta em:
B’(t) = -3(t - 1)2P0 + 3(3t - 1)(t - 1)P1 – 3t(3t - 2)(t -1)P2 + 3t2P3
o que dá:
B’(0) = 3(P1 – P0)
B’(1) = 3(P3 – P2)
Esses dois resultados são os vetores de velocidade no ponto inicial P0 e no ponto final P3. Eles mostram que
a direção do movimento nesses pontos é a mesma que a dos vetores P0P1 e P2P3, como a Figura 44 ilustra.
Computação Gráfica
Walderson Shimokawa
63
Figura 44: Velocidade nos pontos P0 e P3
Discutimos duas formas inteiramente diferentes de desenhar uma curva entre os pontos P0 e P3, e
sem um experimento não fica claro que essas curvas são idênticas. Por enquanto, faremos distinção entre
as duas curvas e as chamaremos de:


Curva do ponto médio: desenhada por um processo recursivo de cálculo dos pontos médios e
implementada no método bezier;
Curva analítica: Dara pela equação considerando o tempo, calculando a velocidade dos vetores,
implementada no método bezier1.
4.6.1
Desenhando Curvas Suaves a Partir de Segmentos de Curvas
Suponha que queiramos combinar dois segmentos de curvas de Bézier, um baseado nos quatro
pontos P0, P1, P2 e P3 e o outro nos pontos Q0, Q1, Q2 e Q3, de forma que o ponto final P3 do primeiro
segmento coincida com o ponto inicial Q0 do segundo. A curva resultante será mais suave se a velocidade
final B’(1) (veja a Figura 44) do primeiro segmento for igual à velocidade inicial B’(0) do segundo. Esse será
o caso se o ponto P3 (=Q0) estiver exatamente no meio do segmento de reta P2Q1. O alto grau de suavidade
obtido dessa forma é chamado de continuidade de segunda ordem. Isso implica não apenas que os dois
segmentos possuem a mesma tangente no seu ponto comum P3 = Q0, mas também que a curvatura é
contínua nesse ponto. Em contraste, temos continuidade de primeira ordem se P3 se localizar no segmento
de reta P2Q1 mas não no meio dele. Nesse caso, embora a curva pareça razoavelmente suave porque
ambos os segmentos possuem a mesma tangente no ponto comum P3 = Q0, há uma descontinuidade na
curvatura nesse ponto. A Figura 45 ilustra esta a suavização de curvas discutidas aqui.
Figura 45: Curvas suaves através de segmentos de curva
4.6.2
Notação Matricial
A equação apresentada e discutida anteriormente pode ser reduzida para:
( ) = (−
+3
+3
+
)
+ 3(
−2
+
)
− 3(
−
) +
Isso é interessante porque nos fornece uma forma muito eficiente de desenhar um segmento de
curva de Bézier, como nos mostra o seguinte método melhorado:
Computação Gráfica
Walderson Shimokawa
64
void bezier2(Graphics g, Point2D[] p)
{ int n = 200;
float dt = 1.0F/n,
cx3 = -p[0].x + 3 * (p[1].x - p[2].x) + p[3].x,
cy3 = -p[0].y + 3 * (p[1].y - p[2].y) + p[3].y,
cx2 = 3 * (p[0].x - 2 * p[1].x + p[2].x),
cy2 = 3 * (p[0].y - 2 * p[1].y + p[2].y),
cx1 = 3 * (p[1].x - p[0].x),
cy1 = 3 * (p[1].y - p[0].y),
cx0 = p[0].x, cy0 = p[0].y,
x = p[0].x, y = p[0].y, x0, y0;
for (int i=1; i<=n; i++)
{ float t = i * dt;
x0 = x; y0 = y;
x = ((cx3 * t + cx2) * t + cx1) * t + cx0;
y = ((cy3 * t + cy2) * t + cy1) * t + cy0;
g.drawLine(iX(x0), iY(y0), iX(x), iY(y));
}
}
Embora bezier2 não pareça mais simples que bezier1, é muito mais eficiente devido ao número
reduzido de operações aritméticas no laço for. Com um grande número de passos, como n = 200 nessas
versões de bezier1 e bezier2, é o número de operações dentro do laço que conta, e não as ações
preparatórias que precedem o laço.
4.6.3
Curvas 3D
Embora as curvas discutidas aqui sejam bidimensionais, curvas tridimensionais podem ser geradas
da mesma forma. Simplesmente adicionamos um componente z a B(t) e aos pontos de controle, que será
calculado da mesma forma que os componentes x e y.
4.7 Ajuste de Curvas B-Spline
Além das técnicas discutidas na seção anterior, há outras formas de gerar curvas x = f(t) e y = g(t),
em que f e g são polinômios de terceiro grau em t. Uma técnica popular, conhecida como B-Splines, possui
a característica de que a curva gerada normalmente não passa pelos pontos dados. Chamaremos todos
esses pontos de pontos de controle. Um único segmento de tal curva, baseado em quatro pontos de
controle A, B, C e D, parece bastante desapontador pois dá a impressão de estar relacionado apenas a B e
C. Isso é mostrado na Figura 46, na qual, da esquerda para a direita, os pontos A, B, C e D estão marcados
novamente com pequenos quadrados.
Figura 46: Segmento B-Spline único, baseado em quatro pontos
Computação Gráfica
Walderson Shimokawa
65
Todavia, um ponto forte a favor de B-Splines é que essa técnica facilita o desenho de curvas muito
suaves que consistem em muitos segmentos de curva. Como você pode ver na Figura 47, a curva é de fato
bastante suave: temos continuidade de segunda ordem, conforme discutido na seção anterior. Lembre-se
de que isso implica que até a curvatura é contínua nos pontos em que dois segmentos de curva adjacentes
se encontram. Como mostra a parte da curva próxima do vértice inferior direito, podemos tornar a
distância entre uma curva e os pontos dados muito pequena ao fornecer diversos pontos próximos uns dos
outros. A Figura 47 abaixo teve o seu primeiro ponto de controle iniciado na parte inferior esquerda,
seguindo para a parte superior esquerda, continuando nos pontos seguintes, no sentido horário, voltando
ao primeiro e segundo pontos marcados novamente (note que o segmento de reta à esquerda parece estar
mais grossa).
Figura 47: Curva B-Spline consistindo em cinco segmentos de curva
A equação abaixo serve para definir as curvas B-Spline:
( ) = (−
+3
−3
+
)
+ (
−2
+
)
+ (−
+
) + (
+4
+
)
O programa a seguir se baseia nessa equação. O usuário pode clicar qualquer número de pontos,
que são usados como os pontos P0, P1, ..., Pn-1. O primeiro segmento de curva aparece imediatamente após
o quarto ponto de controle, P3, ter sido definido, e cada ponto de controle adicional faz com que um novo
segmento de curva apareça. Para mostrar apenas a curva, o usuário pode pressionar qualquer tecla, o que
também termina o processo de entrada. Após isso, podemos gerar outra curva clicando o mouse
novamente. As Figuras 46 e 47 foram produzidas por este programa:
import java.awt.*;
import java.awt.event.*;
import java.util.*;
public class Bspline extends Frame
{ public static void main(String[] args){new Bspline();}
Bspline()
{ super("Defina pontos: pressione qualquer tecla após o final");
addWindowListener(new WindowAdapter()
{public void windowClosing(WindowEvent e){System.exit(0);}});
setSize(500, 300);
add("Center", new CvBspline());
Computação Gráfica
Walderson Shimokawa
setCursor(Cursor.getPredefinedCursor(Cursor.CROSSHAIR_CURSOR));
show();
}
}
class CvBspline extends Canvas
{ Vector V = new Vector();
int np = 0, centerX, centerY;
float rWidth = 10.0F, rHeight = 7.5F, eps = rWidth/100F, pixelSize;
boolean ready = false;
CvBspline()
{ addMouseListener(new MouseAdapter()
{ public void mousePressed(MouseEvent evt)
{ float x = fx(evt.getX()), y = fy(evt.getY());
if (ready)
{ V.removeAllElements();
np = 0;
ready = false;
}
V.addElement(new Point2D(x, y));
np++;
repaint();
}
});
addKeyListener(new KeyAdapter()
{ public void keyTyped(KeyEvent evt)
{ evt.getKeyChar();
if (np >= 4) ready = true;
repaint();
}
});
}
void initgr()
{ Dimension d = getSize();
int maxX = d.width - 1, maxY = d.height - 1;
pixelSize = Math.max(rWidth/maxX, rHeight/maxY);
centerX = maxX/2; centerY = maxY/2;
}
int iX(float x){return Math.round(centerX + x/pixelSize);}
int iY(float y){return Math.round(centerY - y/pixelSize);}
float fx(int x){return (x - centerX) * pixelSize;}
float fy(int y){return (centerY - y) * pixelSize;}
void bspline(Graphics g, Point2D[] p)
{ int m = 50, n = p.length;
float xA, yA, xB, yB, xC, yC, xD, yD,
a0, a1, a2, a3, b0, b1, b2, b3, x=0, y=0, x0, y0;
boolean first = true;
for (int i=1; i<n-2; i++)
{ xA=p[i-1].x; xB=p[i].x; xC=p[i+1].x; xD=p[i+2].x;
yA=p[i-1].y; yB=p[i].y; yC=p[i+1].y; yD=p[i+2].y;
a3=(-xA+3*(xB-xC)+xD)/6; b3=(-yA+3*(yB-yC)+yD)/6;
a2=(xA-2*xB+xC)/2;
b2=(yA-2*yB+yC)/2;
a1=(xC-xA)/2;
b1=(yC-yA)/2;
a0=(xA+4*xB+xC)/6;
b0=(yA+4*yB+yC)/6;
for (int j=0; j<=m; j++)
{ x0 = x;
y0 = y;
float t = (float)j/(float)m;
x = ((a3*t+a2)*t+a1)*t+a0;
y = ((b3*t+b2)*t+b1)*t+b0;
66
Computação Gráfica
Walderson Shimokawa
67
if (first) first = false;
else
g.drawLine(iX(x0), iY(y0), iX(x), iY(y));
}
}
}
public void paint(Graphics g)
{ initgr();
int left = iX(-rWidth/2), right = iX(rWidth/2),
bottom = iY(-rHeight/2), top = iY(rHeight/2);
g.drawRect(left, top, right - left, bottom - top);
Point2D[] p = new Point2D[np];
V.copyInto(p);
if (!ready)
{ for (int i=0; i<np; i++)
{ // Mostra pequeno retângulo em torno do ponto:
g.drawRect(iX(p[i].x)-2, iY(p[i].y)-2, 4, 4);
if (i > 0)
// Desenha reta p[i-1]p[i]:
g.drawLine(iX(p[i-1].x), iY(p[i-1].y),
iX(p[i].x), iY(p[i].y));
}
}
if (np >= 4) bspline(g, p);
}
}
Para ver porque B-Splines são tão suaves, você deve derivar B(t) duas vezes e verificar que, para
qualquer segmento que não seja o final, os valores de B(1), B’(1) e B’’(1) no ponto final desses segmentos
são iguais aos valores B(0), B’(0) e B’’(0) no ponto inicial do próximo segmento de curva. Por exemplo, para
a continuidade da própria curva, encontramos
(1) = (−
+3
−3
= (
+4
+
+
)
+ (
−2
+
)
+ (−
+
) + (
+4
+
)
)
para o primeiro segmento, baseado em P0, P1, P2 e P3, enquanto podemos ver imediatamente que obtemos
exatamente esse valor se calcularmos B(0) para o segundo segmento de curva, baseado em P1, P2, P3 e P4.
4.8 Exercício
Como pixels normais são muito pequenos, eles não mostram muito claramente quais deles são
selecionados pelos algoritmos de Bresenham. Use uma grade de pontos para simular uma tela com
resolução muito baixa e demonstrar tanto o método drawLine da seção 4.1 (com g como seu primeiro
argumento) quanto o método drawCircle da seção 4.3. Apenas os pontos da grade devem ser usados como
centros dos “superpixels”. Codifique um novo método putPixel para desenhar um pequeno círculo como tal
centro, tendo como diâmetro a distância dGrid entre dois pontos vizinhos da grade.
Não altere os métodos drawLine e drawCircle que desenvolvemos, mas use a distância dGrid, entre
dois pontos vizinhos da grade, no novo método putPixel diferente do mostrado no início da seção 4.1. A
Figura 48 mostra uma grade (com dGrid = 10) e uma reta e um círculo desenhados dessa forma. Assim
como na Figura 30, a reta mostrada aqui tem pontos extremos P(1, 1) e Q(12, 5), mas dessa vez o eixo y
positivo aponta para baixo e a origem é o vértice superior esquerdo do retângulo de desenho. O círculo
possui raio r = 8 e é aproximado pelos mesmos pixels que os mostrados na figura 35 para um oitavo desse
círculo. A reta e o círculo foram produzidos pelos seguintes chamadas aos métodos drawLine e drawCircle
das seções 4.1 e 4.3 (mas com um método putPixel diferente):
Computação Gráfica
Walderson Shimokawa
68
drawLine(g, 1, 1, 12, 5); //g, xP, yP, xQ, yQ
drawCircle(g, 23, 10, 8); //g, xC, yC, r
Figura 48: Algoritmos de Bresenham para uma reta e para um círculo
4.9 Resposta do Exercício
O programa a seguir produz apenas a Figura 48. Você deve estendê-lo, permitindo ao usuário
especificar os dois pontos extremos de um segmento de reta e tanto o centro quanto o raio do círculo.
import java.awt.*;
import java.awt.event.*;
import java.util.*;
public class Bresenham extends Frame
{ public static void main(String[] args){new Bresenham();}
Bresenham()
{ super("Bresenham");
addWindowListener(new WindowAdapter()
{public void windowClosing(WindowEvent e){System.exit(0);}});
setSize(340, 230);
add("Center", new CvBresenham());
show();
}
}
class CvBresenham extends Canvas
{ float rWidth = 10.0F, rHeight = 7.5F, pixelSize;
int centerX, centerY, dGrid = 10, maxX, maxY;
void initgr()
{ Dimension d;
d = getSize();
maxX = d.width - 1;
maxY = d.height - 1;
pixelSize = Math.max(rWidth/maxX, rHeight/maxY);
centerX = maxX/2; centerY = maxY/2;
}
int iX(float x){return Math.round(centerX + x/pixelSize);}
int iY(float y){return Math.round(centerY - y/pixelSize);}
void putPixel(Graphics g, int x, int y)
{ int x1 = x * dGrid, y1 = y * dGrid, h = dGrid/2;
g.drawOval(x1 - h, y1 - h, dGrid, dGrid);
}
void drawLine(Graphics g, int xP, int yP, int xQ, int yQ)
Computação Gráfica
{
Walderson Shimokawa
int x = xP, y = yP, D = 0, HX = xQ - xP, HY = yQ - yP,
c, M, xInc = 1, yInc = 1;
if (HX < 0){xInc = -1; HX = -HX;}
if (HY < 0){yInc = -1; HY = -HY;}
if (HY <= HX)
{ c = 2 * HX; M = 2 * HY;
for (;;)
{ putPixel(g, x, y);
if (x == xQ) break;
x += xInc;
D += M;
if (D > HX){y += yInc; D -= c;}
}
}
else
{ c = 2 * HY; M = 2 * HX;
for (;;)
{ putPixel(g, x, y);
if (y == yQ) break;
y += yInc;
D += M;
if (D > HY){x += xInc; D -= c;}
}
}
}
void drawCircle(Graphics g, int xC, int yC, int r)
{ int x = 0, y = r, u = 1, v = 2 * r - 1, E = 0;
while (x < y)
{ putPixel(g, xC + x, yC + y); // NNE
putPixel(g, xC + y, yC - x); // ESE
putPixel(g, xC - x, yC - y); // SSW
putPixel(g, xC - y, yC + x); // WNW
x++; E += u; u += 2;
if (v < 2 * E){y--; E -= v; v -= 2;}
if (x > y) break;
putPixel(g, xC + y, yC + x); // ENE
putPixel(g, xC + x, yC - y); // SSE
putPixel(g, xC - y, yC - x); // WSW
putPixel(g, xC - x, yC + y); // NNW
}
}
void showGrid(Graphics g)
{ for (int x=dGrid; x<=maxX; x+=dGrid)
for (int y=dGrid; y<=maxY; y+=dGrid)
g.drawLine(x, y, x, y);
}
public void paint(Graphics g)
{ initgr();
showGrid(g);
drawLine(g, 1, 1, 12, 5);
drawCircle(g, 23, 10, 8);
}
}
69