¿Cómo obtener resultados precisos con el algoritmo de Painter?

14

Hace un tiempo pregunté cómo determinar cuándo una cara se superpone a otra. El consejo era usar un Z-buffer.

Sin embargo, no puedo usar un búfer Z en mi proyecto actual y, por lo tanto, me gustaría usar el algoritmo del pintor. Sin embargo, no tengo ni idea de cuándo una superficie está detrás o delante de otra. He probado numerosos métodos, pero todos fallan en casos extremos, o fallan incluso en casos generales.

Esta es una lista de métodos de clasificación que he probado hasta ahora:

  • Distancia al punto medio de cada cara
  • Distancia promedio a cada vértice de cada cara
  • Valor z promedio de cada vértice
  • Complice el valor z de los vértices de cada cara y dibuje los primeros
  • El valor z más bajo de los vértices de cada cara y dibuja los últimos

El problema es que una cara puede tener una distancia más cercana pero aún está más lejos. Todos estos métodos parecen poco confiables.

Editar: por ejemplo, en la siguiente imagen, la superficie con el punto azul como punto medio se pinta sobre la superficie con el punto rojo como punto medio, porque el punto azul está más cerca. Sin embargo, esto se debe a que la superficie del punto rojo es más grande y el punto medio está más lejos. La superficie con el punto rojo debe pintarse sobre el azul, porque está más cerca , mientras que la distancia del punto medio dice lo contrario.

ingrese la descripción de la imagen aquí

¿Qué se usa exactamente en el algoritmo del pintor para determinar el orden en que deben dibujarse los objetos?

pimvdb
fuente
1
El algoritmo de los pintores solo está dibujando de atrás hacia adelante.
Jonathan Connell
1
@ 3nixios: Sí, obviamente, pero ¿de qué manera puedo determinar el orden de 'atrás al frente'?
pimvdb 01 de
1
Todos sus objetos, triángulos o vértices estarán a cierta distancia de la cámara cuando comience a dibujar. Implementar el algoritmo básico (¿has tenido éxito?) Sería determinar esta distancia de la cámara para cada triángulo y dibujarlos en el orden más cercano al más cercano. Una vez hecho esto, debe comenzar a buscar intersecciones y cortar sus triángulos, que es un juego de pelota completamente diferente . ¿Por qué no puedes usar Z-Buffer ya? : P
Jonathan Connell
@ 3nixios: Tienes toda la razón, pero el problema que estoy enfrentando es calcular la distancia. Como dije, probé varios métodos de distancia, pero no todos son perfectos. Este pedido resulta de la clasificación de la distancia del punto medio: i.imgur.com/AcfCm.png .
pimvdb 01 de
1
¿Están todos tus polígonos en una cuadrícula regular como esa? Si es así, puede haber cosas específicas de la cuadrícula que puede hacer para mejorar esto.
CiscoIPPhone

Respuestas:

14

Por lo general, la distancia del punto medio de un polígono a la cámara se utiliza para la ordenación z. El algoritmo del pintor no puede ser 100% exacto por su naturaleza. Siempre habrá casos en los que la clasificación fallará, sin importar el punto de referencia que utilice.

Si desea una ordenación z correcta con el algoritmo del pintor, tendrá que cortar los polígonos superpuestos en partes más pequeñas (por ejemplo, usando un árbol cuádruple) y ordenar estas partes individualmente. Sin embargo, esto puede llegar a ser bastante pesado en la CPU.

Encontré este archivo de Powerpoint que ilustra muy bien el problema ( Versión PDF ).

bummzack
fuente
Gracias por ese Powerpoint, me ayudó a resolver el problema.
pimvdb 01 de
El enlace está roto. ¿Alguien puede encontrar una copia?
Keavon
1
@Keavon Editado. Encontré un enlace de trabajo para el archivo.
bummzack
1

En tales casos, para mí siempre funcionó usando bsp-trees. Divida la escena hasta que tenga un conjunto convexo de polígonos en el nodo de bsp-tree y luego pueda ordenar fácilmente los polígonos dentro de los nodos. Tenga en cuenta que al ordenar los polígonos del nodo bsp-tree parece el mismo problema que describió anteriormente, pero hay una condición no tan obvia: después de construir el árbol bsp, todos los casos problemáticos ya están resueltos; en el nodo debe finalizar con un conjunto de polígonos desde los que debe pasar la prueba de convexidad: si elige un plano de un polígono de este conjunto, el resto de los polígonos están todos delante del plano o detrás del plano. El uso de esa información facilita la clasificación: el functor de clasificación toma 2 polígonos; compruebe en qué medio espacio está el primer polígono contra el segundo polígono y también verifique la ubicación de la cámara contra el segundo polígono.

Tenga en cuenta también que las pruebas para determinar el lado de la colocación de la cámara contra los polígonos y el desplazamiento del árbol bsp son ligeramente diferentes cuando se trata de la proyección ortográfica y en perspectiva.

Si no puede permitirse la división de los polígonos de entrada, creo que no tiene suerte.

obispo
fuente