Algoritmos de Recorte de Líneas: Cohen Sutherland, Liang-Barsky y Nichol-Lee-Nichol

Información General del Proyecto

Institución: Universidad Nacional José María Arguedas, Facultad de Ingeniería, Escuela Profesional de Ingeniería de Sistemas.
Título del Proyecto: Implantación de Algoritmos de Recorte de Líneas (Cohen Sutherland, Liang-Barsky y Nichol-Lee-Nichol).
Presentado por:
- Ccorimanya Huamán Rosmery.
- Aguila Silvera Juan David.
- Vargas Palomino Max Hover.
- Herbas De la Cruz Jhon Rogers.
Ubicación y Fecha: Andahuaylas, Perú, 2026.
Asignatura: Computación Gráfica.
Docente: Manejes Palomino Neptali.

Introducción al Recorte de Líneas (Line Clipping)

Definición: El recorte o clipping es una técnica fundamental en los gráficos por computadora empleada para determinar qué porciones de los objetos gráficos deben visualizarse dentro de una región específica llamada ventana gráfica.
Objetivo Principal: Eliminar elementos localizados fuera del área de interés para reducir el costo computacional y optimizar el proceso de renderizado.
Funcionalidad: El sistema procesa y dibuja solo las partes visibles de líneas, polígonos u otros objetos dentro de los límites establecidos. Se utiliza para extraer regiones de una escena, definir límites de objetos y gestionar múltiples áreas de visualización.
Evolución Histórica:
- Algoritmo de Cohen-Sutherland (1967): Utiliza códigos de región para clasificar segmentos.
- Algoritmo de Liang-Barsky (1984): Basado en formulaciones paramétricas para reducir cálculos.
- Algoritmo de Nicholl-Lee-Nicholl (1987): Optimiza el proceso minimizando intersecciones mediante análisis geométrico.
Naturaleza del Proyecto: Creación de una herramienta pedagógica interactiva desarrollada con JavaScript y WebGL que permite trazar segmentos en 2D, aplicar uno de los tres algoritmos y visualizar el resultado comparativo.

Objetivos del Proyecto

Objetivo General: Crear o programar una herramienta de educación interactiva que utilice WebGL y JavaScript para poner en práctica y comparar visualmente los algoritmos de recorte de líneas Cohen-Sutherland, Liang-Barsky y Nicholl-Lee-Nicholl.
Objetivos Específicos:
- Implementar una ventana de recorte con los tres algoritmos mencionados dentro de un entorno de visualización.
- Desarrollar una interfaz gráfica interactiva que permita al usuario dibujar líneas y ver resultados en tiempo real.
- Comparar el comportamiento y la eficiencia aparente de los algoritmos sobre un mismo conjunto de líneas de prueba.

Materiales y Recursos

Hardware:
- Computadoras personales con navegación web actualizada y soporte para WebGL.
- Dispositivos de entrada estándar: teclado y ratón (mouse).
Software Utilizado:
- Visual Studio Code: Editor de código abierto de Microsoft adaptado para HTML5 y JavaScript.
- HTML5: Estándar para definir la estructura, diseño y contenido de la página web (esqueleto del aplicativo).
- JavaScript: Lenguaje de programación para la lógica interactiva, animaciones 2D/3D y gestión de eventos de hardware.
- WebGL (Web Graphics Library): API de JavaScript basada en OpenGL ES 2.0 que permite el renderizado acelerado por hardware de gráficos 2D y 3D en el navegador sin plugins.

Requisitos Previos y Conocimientos Teóricos

Conocimientos Teóricos necesarios:
- Conceptos básicos de Computación Gráfica: Pipeline de renderizado, espacio de ventana, coordenadas de pantalla.
- Nociones de WebGL: Contexto de renderizado, buffers de vértices, shaders GLSL (Uniforms y Attributes).
- Programación en JavaScript (Nivel Intermedio): Manipulación del DOM, eventos de mouse, arrays y Programación Orientada a Objetos (POO).
Recursos de Software necesarios:
- Navegador con soporte WebGL (Edge, Chrome, Firefox).
- Servidor HTTP local (ej. Live Server) para pruebas.

Fundamento Teórico de los Algoritmos de Recorte

El Proceso de Recorte: Se define una ventana rectangular delimitada por las coordenadas mínimas y máximas $(x_{min}, y_{min})$ y $(x_{max}, y_{max})$ . El algoritmo analiza los extremos del segmento y determina su situación:
- Completamente visible: Ambos extremos dentro de la ventana (se acepta).
- Completamente invisible: El segmento íntegro está fuera (se rechaza).
- Parcialmente visible: Al menos un extremo está fuera (requiere cálculo de intersecciones).
Algoritmo de Cohen-Sutherland (1967):
- Divide el espacio en 9 regiones con un código de 4 bits denominado TBRL (Top, Bottom, Right, Left):
  - T (Superior): 1 si el punto está encima, 0 si no.
  - B (Inferior): 1 si el punto está debajo, 0 si no.
  - R (Derecha): 1 si el punto está a la derecha, 0 si no.
  - L (Izquierda): 1 si el punto está a la izquierda, 0 si no.
- Pruebas Triviales:
  - Si $(c1 ∣ c2) = 0$ : Visible.
  - Si (c1 & c2) \neq 0: Invisible.
  - Si no se cumple ninguna, se calculan intersecciones de forma iterativa.
Algoritmo de Liang-Barsky (1984):
- Utiliza ecuaciones paramétricas de la línea:
  - $x = x_1 + t \times dx$
  - $y = y_1 + t \times dy$
  - Donde $0 ≤ t ≤ 1$ , $dx = x_2 - x_1$ y $dy = y_2 - y_1$ .
- Emplea 4 desigualdades con parámetros $p$ y $q$ para determinar el valor de $t$ de entrada y salida, resultando más eficiente que Cohen-Sutherland.
Algoritmo de Nicholl-Lee-Nicholl (NLN) (1987):
- Característica principal: Evita cálculos innecesarios de intersección mediante más pruebas de región y menos divisiones.
- Utiliza solo tres de las nueve regiones iniciales para el análisis (esquina superior izquierda, borde izquierdo y ventana).
- Limitación: Solo se aplica a dos dimensiones (2D), a diferencia de los otros dos que son extensibles a 3D.

Procedimiento de Desarrollo e Implementación

Diseño de la Interfaz:
- Estructura HTML5 con un panel lateral de controles y un elemento <canvas> para el dibujo.
- Controles: Lista desplegable para el algoritmo, botones de limpieza y selectores de visualización.
Inicialización de WebGL:
- Creación de Shaders para procesamiento de vértices y asignación de color.
- Establecimiento del entorno WebGL2 para renderizado acelerado.
Implementación de la Ventana: Definición de una ventana fija en el centro del espacio de coordenadas normalizadas.
Captura de Eventos: Transformación de coordenadas del ratón al sistema de coordenadas de WebGL para permitir el dibujo dinámico.
Lógica de los Algoritmos:
- Cohen-Sutherland: Implementación de la función OutCode para categorizar extremos.
- Liang-Barsky: Implementación de la lógica de parámetros $p, q, t$ para intersecciones directas.
- NLN: Versión simplificada basada en criterios geométricos y funciones auxiliares.

Lógica del Renderizado (Función render)

Configuración del Canvas:
- gl.viewport(0, 0, gl.canvas.width, gl.canvas.height).
- Color de fondo definido con gl.clearColor(0.1, 0.15, 0.18, 1.0).
Dibujo de la Ventana: Se traza un cuadrado central utilizando líneas blancas (vértices definidos por X_MIN, Y_MIN, X_MAX, Y_MAX).
Procesamiento de Líneas:
- Modo "before": Renderiza líneas originales en color azul (colors.push(0.2, 0.6, 1.0)).
- Modo Recortado: Aplica el algoritmo seleccionado (cohen, liang, nln). Si el recorte es exitoso, las líneas resultantes se dibujan en color verde (0.1, 0.8, 0.4).
Transferencia a GPU: Los datos de vértices y colores se envían a los buffers (gl.ARRAY_BUFFER) y se ejecutan con gl.drawArrays(gl.LINES, 0, vertices.length / 2).

Resultados, Recomendaciones y Conclusiones

Resultados de Visualización:
- La ventana de recorte está fija en el espacio $[-0.5, 0.5]$ .
- Línea Visible: Se muestra íntegra dentro del recuadro.
- Línea Invisible: No se renderiza ningún segmento cuando se activa el modo "recortado".
- Línea Parcial: Los segmentos exteriores desaparecen, manteniendo solo el tramo interno.
Recomendaciones:
- Permitir la modificación dinámica del tamaño y posición de la ventana de recorte.
- Extender el soporte para el recorte de polígonos complejos.
- Incorporar una función de visualización "paso a paso" para fines didácticos.
Conclusiones:
- El desarrollo del visualizador permitió una comprensión práctica de la eficiencia de cada algoritmo.
- El recorte es esencial para optimizar el renderizado, identificando segmentos visibles y mejorando la eficacia de la representación gráfica.