Capítulo 7 - Recorte

Siguiendo nuestro modelado en dos dimensiones, hablaremos de una operación importante acerca de líneas y polígonos. El recorte (o clipping, en inglés) modifica las líneas y polígonos a visualizar debidos a una región que los limita. Técnicamente, se trata de una intersección de dos entidades geométricas. Típicamente, la región de recorte es un rectángulo vertical, cuyos lados son paralelos a los ejes del sistema de coordenadas, que suele representar la vista de nuestra escena o la pantalla en sí.

Existen varios algoritmos y métodos para hacer el recorte. Por ahora, sólo miraremos aquellas técnicas analíticas. Esto significa que aplicaremos la operación de recorte a nuestro modelo en nuestro sistema de coordenadas matemático de nuestro mundo y escena. Existen otros métodos de recorte que se pueden aplicar en la etapa de conversión del modelo a píxeles. Trataremos estas técnicas en posteriores capítulos.

Veremos varios métodos para varios casos de recorte, como son el recorte de líneas y polígonos en un rectángulo vertical, al igual que en una región de recorte descrita por un polígono.

Recortando Líneas

Realmente, no pretendemos recortar líneas sino más bien segmentos. Como un segmento se describe por sus puntos extremos, no tenemos que consultar la infinidad de puntos que componen tal segmento.

De la misma manera que analizamos el recorte de puntos individuales, podemos aplicar la misma lógica para los puntos extremos de un segmento. El resultado es cuatro casos diferentes. Si ambos extremos están dentro del rectángulo de recorte, entonces no tenemos que hacer nada más que aceptar el segmento. Si un extremo está dentro y el otro fuera del rectángulo, entonces el segmento cruza uno de los lados de la región de recorte. Tenemos que calcular el punto de intersección lo cual modificará el extremo del segmento externo para que sea interno al rectángulo de recorte. Si ambos extremos están fuera del rectángulo de recorte, entonces el segmento puede estar completamente fuera del rectángulo, por lo que es rechazado inmediatamente. Sin embargo, tal segmento podría cruzar dos lados del rectángulo. En este caso, tenemos que realizar dos cálculos de intersección, modificando ambos extremos del segmento para que éste sea interior al rectángulo de recorte.

Veremos varios algoritmos para solucionar este problema: Algoritmo Exhaustivo, Algoritmo de Cohen-Sutherland, Algoritmo de Cyrus-Beck, Algoritmo de Liang-Barsky, y Algoritmo de Nicholl-Lee-Nicholl.

Recortando Polígonos

Lo normal es que nuestra escena contenga varios polígonos y no segmentos sueltos. Como nuestra vista limita el contenido de la escena que podemos mostrar, tendremos que recortar los polígonos de la escena para eliminarlos de la vista o dibujarlos parcial o completamente. Como representamos los polígonos mediante los segmentos que forman sus aristas, al recortar los polígonos en un rectángulo, acabaremos eliminando, aceptando, o recortando las aristas existentes y posiblemente añadiendo nuevas. Los diferentes resultados dependen del tipo de polígono a recortar.

Un polígono convexo que intersecta un rectángulo dará lugar a un polígono convexo. Un polígono cóncavo recortado por un rectángulo puede resultar en uno o varios polígonos cóncavos o convexos.

Veremos varios algoritmos para recortar polígonos: Algoritmo de Sutherland-Hodgman, Algoritmo de Liang-Barsky, y Algoritmo de Weiler-Atherton.