Relleno de un polígono: rendimiento de la regla de bobinado frente a la regla par impar

Question

Para un polígono complejo (es decir, auto intersectante), la elección entre las reglas de relleno Sinuoso o Par impar marca la diferencia en la forma en que se rellena el polígono.

Pero para los polígonos que no se intersectan, ¿hay alguna diferencia de rendimiento entre las reglas de relleno Winding o Even Odd? Entiendo que sería específico de la implementación, pero cuál de los algoritmos es más eficaz para los polígonos no complejos.

Una pregunta de seguimiento ¿cuál es la complejidad (es decir, O (¿qué?)) de cada uno de estos algoritmos. Quiero saber si vale la pena deshacerse de algunos puntos en el polígono (principalmente duplicados o que están en la misma línea) para mejorar el rendimiento.

PD: si es importante, estoy usando xlib

PPS: puedo confirmar que el problema no está relacionado con el hardware, ya que el uso de una tarjeta gráfica diferente no cambia el rendimiento

Answer 1

Hoy en día, la mayoría de las implementaciones de X utilizan el hardware 2D de su tarjeta gráfica, por lo que la diferencia entre ambas probablemente sea insignificante.

Dado que esta es una pregunta de rendimiento, las posibilidades de que mi respuesta sea correcta es de aproximadamente el 10% (sin embargo, con el rendimiento, tiene un 90% de posibilidades de equivocarse sin medir). Si quieres estar seguro, no hay otra forma que escribir una pequeña prueba de rendimiento y ver por ti mismo.

x11perf podría ayudar.

Puede encontrar el algoritmo para el relleno de polígono independiente del hardware aquí: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolygen.c?rev=HEAD

Hay una segunda versión que es mucho más rápida si está seguro de que su polígono es convexo: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolycon.c?rev=HEAD

La segunda versión ignora la regla de relleno (que no se aplica a los polígonos convexos). Comentarios sobre el algoritmo: http: // cvsweb .xfree86.org / cvsweb / xc / programas / Xserver / mi / mipoly.h? rev = HEAD

El algoritmo funciona de esta manera: calcula el contorno, luego crea objetos span (que son solo una coordenada x, y y un ancho) entre los bordes. Si usa la regla EvenOdd, se crearán más objetos span si hay intersecciones. Si no hay ninguno (por ejemplo, cuando el polígono es convexo), no notará una diferencia de tiempo de ejecución porque la regla de relleno equivale a una variable booleana en el bucle principal de miFillPolygon (es decir, la mayor parte del código es el mismo para ambos llenar las reglas).

Intentar mejorar el rendimiento mediante la optimización del contorno del polígono no le comprará mucho en el caso común, excepto si sabe que sus polígonos contienen un número muy elevado de puntos innecesarios (por ejemplo, puede deshacerse de la mitad del número de puntos en el caso común). Optimizando un polígono con & Lt; 10 puntos probablemente costarán más de lo que alcanza.

Pero de nuevo: todo esto se basa en la intuición o el conocimiento de un artículo antiguo. Si desea saber si los errores en el controlador de su tarjeta gfx confunden con el resultado, debe ensuciarse las manos y escribir una prueba que mida cuánto tiempo lleva cada caso. No hay forma de determinar el tiempo de ejecución de un algoritmo complejo simplemente mirándolo debido a factores externos: velocidad de las rutinas de asignación de memoria, cantidad de memoria libre (cuándo comienza el intercambio), número de núcleos de CPU que puede usar, cuántos otros procesos lucharán por la CPU, el recorte del polígono final en la pantalla, detalles de implementación y optimizaciones, errores, etc.