"""Rasterização de linhas: DDA e Bresenham em uma grade de "pixels". Aula 03 — Visualização 2D: rasterização. Exemplo em Python com PySide6 e PyOpenGL (pipeline fixed-function). Execute com: python raster_linhas.py A janela do mundo é uma **grade grossa de pixels**: ``gluOrtho2D`` vai de 0 a ``COLUNAS`` em X e de 0 a ``LINHAS`` em Y, de modo que uma unidade do mundo é exatamente um pixel do dispositivo imaginário. O pixel de coordenadas inteiras ``(i, j)`` tem centro em ``(i + 0.5, j + 0.5)``. "Acender um pixel" é desenhar um ``GL_POINTS`` no centro da célula, com ``glPointSize`` do tamanho da célula — o mesmo ponto quadrado da Aula 02, agora usado de propósito. Teclas: 1 DDA 2 Bresenham 3 os dois sobrepostos, com as diferenças em destaque I mostra ou esconde a reta ideal G mostra ou esconde a grade Esc fecha Clique com o mouse para mover o segundo extremo do segmento. Ideias para experimentar: aumente ``COLUNAS``/``LINHAS`` até a escada sumir (é o que uma tela de verdade faz); compare os dois algoritmos em retas quase horizontais e quase verticais; conte quantas operações de ponto flutuante cada um usa por pixel. """ from __future__ import annotations import sys from PySide6.QtCore import Qt from PySide6.QtGui import QSurfaceFormat from PySide6.QtWidgets import QApplication from PySide6.QtOpenGLWidgets import QOpenGLWidget from OpenGL.GL import * from OpenGL.GLU import gluOrtho2D COLUNAS = 32 # largura da grade, em "pixels" LINHAS = 24 # altura da grade, em "pixels" P1 = (3, 4) # primeiro extremo do segmento, em coordenadas da grade P2_INICIAL = (29, 17) # escolhido por produzir diferença visível entre DDA e Bresenham COR_DDA = (0.35, 0.55, 0.95) COR_BRESENHAM = (0.95, 0.70, 0.25) COR_DIFERENCA = (0.95, 0.35, 0.35) # --------------------------------------------------------------------------- # Os algoritmos # --------------------------------------------------------------------------- def dda(x0: int, y0: int, x1: int, y1: int) -> list[tuple[int, int]]: """*Digital Differential Analyzer*. Avança em passos constantes ao longo do eixo de maior variação e **arredonda** a outra coordenada. Direto de escrever, mas usa ponto flutuante e um arredondamento por pixel. """ dx, dy = x1 - x0, y1 - y0 passos = max(abs(dx), abs(dy)) if passos == 0: return [(x0, y0)] incremento_x = dx / passos incremento_y = dy / passos pixels = [] x, y = float(x0), float(y0) for _ in range(passos + 1): pixels.append((round(x), round(y))) x += incremento_x y += incremento_y return pixels def bresenham(x0: int, y0: int, x1: int, y1: int) -> list[tuple[int, int]]: """Algoritmo de Bresenham, na forma que vale para os oito octantes. Só usa inteiros: soma, subtração e deslocamento. A variável ``erro`` acumula a distância entre a reta ideal e o centro do pixel escolhido, e é o sinal dela que decide se a coordenada secundária avança. """ dx, dy = abs(x1 - x0), abs(y1 - y0) passo_x = 1 if x0 < x1 else -1 passo_y = 1 if y0 < y1 else -1 erro = dx - dy pixels = [] x, y = x0, y0 while True: pixels.append((x, y)) if x == x1 and y == y1: return pixels erro_dobrado = 2 * erro if erro_dobrado > -dy: erro -= dy x += passo_x if erro_dobrado < dx: erro += dx y += passo_y # --------------------------------------------------------------------------- class RasterLinhas(QOpenGLWidget): """Grade de pixels com os dois algoritmos desenhados sobre ela.""" def __init__(self, parent=None): super().__init__(parent) self.modo = 2 # 1 = DDA, 2 = Bresenham, 3 = ambos self.p2 = P2_INICIAL self.mostrar_ideal = True self.mostrar_grade = True self.viewport = (0, 0, 1, 1) # x, y, largura, altura — em pixels self.setFocusPolicy(Qt.FocusPolicy.StrongFocus) # -- ciclo de vida ----------------------------------------------------- def initializeGL(self) -> None: glClearColor(0.10, 0.11, 0.13, 1.0) def resizeGL(self, w: int, h: int) -> None: w, h = max(1, w), max(1, h) # Em vez de esticar a window para caber na janela (a correção de # aspecto da Aula 02), aqui fazemos o contrário: encolhemos o # VIEWPORT até ele ter a mesma proporção da grade. Assim cada célula # sai quadrada, custe o que custar em área desperdiçada. largura = min(w, h * COLUNAS // LINHAS) altura = largura * LINHAS // COLUNAS self.viewport = ((w - largura) // 2, (h - altura) // 2, largura, altura) glViewport(*self.viewport) glMatrixMode(GL_PROJECTION) glLoadIdentity() gluOrtho2D(0.0, float(COLUNAS), 0.0, float(LINHAS)) glMatrixMode(GL_MODELVIEW) glLoadIdentity() # -- desenho ----------------------------------------------------------- def paintGL(self) -> None: # glClear varre o framebuffer inteiro, e não apenas o viewport — só o # teste de tesoura (glScissor) o restringiria. Por isso a área ao # redor da grade também é limpa, mesmo estando fora do viewport. glClear(GL_COLOR_BUFFER_BIT) if self.mostrar_grade: self._desenhar_grade() pixels_dda = dda(*P1, *self.p2) pixels_bre = bresenham(*P1, *self.p2) if self.modo == 1: self._acender(pixels_dda, COR_DDA) elif self.modo == 2: self._acender(pixels_bre, COR_BRESENHAM) else: conjunto_dda = set(pixels_dda) conjunto_bre = set(pixels_bre) self._acender(conjunto_dda & conjunto_bre, COR_BRESENHAM) self._acender(conjunto_dda ^ conjunto_bre, COR_DIFERENCA) if self.mostrar_ideal: self._desenhar_reta_ideal() self._marcar_extremos() def _tamanho_celula(self) -> float: """Lado da célula em pixels do dispositivo. ``glPointSize`` é medido em pixels, não em unidades do mundo — a mesma distinção da Aula 02. Para que o ponto cubra exatamente uma célula, o tamanho tem de ser calculado a partir do viewport. """ return max(1.0, self.viewport[2] / COLUNAS) def _acender(self, pixels, cor: tuple[float, float, float]) -> None: glColor3f(*cor) glPointSize(self._tamanho_celula()) glBegin(GL_POINTS) for i, j in pixels: glVertex2f(i + 0.5, j + 0.5) # centro da célula glEnd() @staticmethod def _desenhar_grade() -> None: glColor3f(0.18, 0.20, 0.25) glLineWidth(1.0) glBegin(GL_LINES) for i in range(COLUNAS + 1): glVertex2f(float(i), 0.0) glVertex2f(float(i), float(LINHAS)) for j in range(LINHAS + 1): glVertex2f(0.0, float(j)) glVertex2f(float(COLUNAS), float(j)) glEnd() def _desenhar_reta_ideal(self) -> None: """A geometria contínua, antes da conversão para pixels. É contra ela que se compara a escada: a reta ideal passa pelos centros dos pixels extremos e por nenhum outro, em geral. """ glColor3f(0.92, 0.92, 0.95) glLineWidth(1.5) glBegin(GL_LINES) glVertex2f(P1[0] + 0.5, P1[1] + 0.5) glVertex2f(self.p2[0] + 0.5, self.p2[1] + 0.5) glEnd() def _marcar_extremos(self) -> None: glColor3f(0.95, 0.95, 0.98) glPointSize(max(4.0, self._tamanho_celula() / 3.0)) glBegin(GL_POINTS) glVertex2f(P1[0] + 0.5, P1[1] + 0.5) glVertex2f(self.p2[0] + 0.5, self.p2[1] + 0.5) glEnd() # -- interação --------------------------------------------------------- def mousePressEvent(self, event) -> None: vx, vy, largura, altura = self.viewport # Qt entrega Y crescendo para baixo; o viewport é medido a partir do # canto inferior esquerdo. Converter antes de dividir pela célula. x_gl = event.position().x() - vx y_gl = (self.height() - event.position().y()) - vy i = int(x_gl / (largura / COLUNAS)) j = int(y_gl / (altura / LINHAS)) if 0 <= i < COLUNAS and 0 <= j < LINHAS: self.p2 = (i, j) self.update() def keyPressEvent(self, event) -> None: tecla = event.key() if tecla == Qt.Key.Key_Escape: self.close() return elif tecla in (Qt.Key.Key_1, Qt.Key.Key_2, Qt.Key.Key_3): self.modo = tecla - Qt.Key.Key_0 elif tecla == Qt.Key.Key_I: self.mostrar_ideal = not self.mostrar_ideal elif tecla == Qt.Key.Key_G: self.mostrar_grade = not self.mostrar_grade else: return nomes = {1: "DDA", 2: "Bresenham", 3: "DDA × Bresenham"} self.setWindowTitle(f"Rasterização de linhas — {nomes[self.modo]}") self.update() def main() -> int: print(__doc__) fmt = QSurfaceFormat() fmt.setVersion(2, 1) fmt.setProfile(QSurfaceFormat.OpenGLContextProfile.NoProfile) fmt.setDepthBufferSize(0) QSurfaceFormat.setDefaultFormat(fmt) app = QApplication(sys.argv) janela = RasterLinhas() janela.setWindowTitle("Rasterização de linhas — Bresenham") janela.resize(800, 620) janela.show() return app.exec() if __name__ == "__main__": raise SystemExit(main())