Estoy peleandome con el Álgebra intentando hacer un algoritmo que dados dos polígonos te diga si el primero de ellos esta tapado totalmente por el segundo.
Imaginaos un triangulo muy grande y otro mas pequeño detras suyo totalmente oculto a a la cámara... la función deberia devolver 1 al compararlos.
Sinembargo, si se ve una pequeña fracción del triangulo semioculto (una esquinita) la función debería devolver 0.
No sé si me he explicado bien.
No se me ocurre cómo hacerlo, ¿a alguien se le ocurre cómo podría implementar eso?
Gracias.
Yo proyectaría los polígonos según la dirección del vector NAt de la cámara, de forma que al final el problema se resuelva en 2D.
¿Cómo de rápido sería eso? ¿Seria un coste muy alto hacer... pongamos el caso... unas 500 operaciones como esa a cada frame? ¿Puedes explicar eso de que el problema se resolvería en 2d?
No dices si los poligonos son concavos o convexos.
Una solucion seria hacer una rutina de dibujar poligonos pero sin dibujarlos, guardas dos listas (una por poligono) con los scanlines de los poligonos dibujados (las lineas horizontales) y si hay una sola linea de una lista que no este totalmente tapada por alguna linea de la otra lista pues ya sabes que el poligono no esta tapado.
Si se ve un triángulo u otro depende de tu punto de vista. Por tanto lo que tienes que hacer es proyectar (o más bien transformar) los triángulos igual que lo hace el motor 3D. Entonces tienes 3 puntos en la pantalla 2D. Y el problema ya es mucho más sencillo de resolver. Depende de si haces tu propio rasterizador o quieras usar OGL u D3D necesitarás unos datos u otros. Si es para D3D Berserker publicó en un post hace tiempo como hacerlo. Esto te dará los puntos 3D convertidos a 2D. Entonces si uno de los puntos cualquiera de un triángulo está dentro del otro, es que se tocan.
Pero no sé para que quieres hacer esto, pero me da la impresión que tu lo que quieres hacer es lo que hacen los BSP, que ordenan el espacio y después dibujan sólo lo que se ve.
Por cierto..¿porqué necesitas esto?
Veamos.. si tienes que proyectar...
;In Ecx=Number of vertex
; Edi=pointer to destination
; Esi=pointer of 3D vertex
;
;Out Action Performed!
;---------------------------------------
ProyCords Proc Near
fild ds:[Ycenter] ;World Centering on screen
fild ds:[Xcenter] ;Idem.
fild ds:[Pvi] ;Focal Distance.
c3d2d:
fld ds:[esi+8] ;Get "Z"
fld1 ;Load number "1"
fdivrp ;Calc Inverse
;and pop the not valuable
;operand
fld Dword Ptr ds:[esi+4] ;Get "Y"
fmul st,st(2) ;Multiply Y with Focal Distance
fmul st,st(1) ;Multiply with the inverse of
;the "Z"
fadd st,st(4) ;Add Y Screen centering
fistp Dword Ptr ds:[edi+4] ;Store final value
fld Dword Ptr ds:[esi] ;Get "X"
fmul st,st(2) ;Multiply X with Focal Distance
fmul st,st(1) ;Multiply with the inverse of
;the "Z"
fadd st,st(3) ;Add X Screen centering
fistp Dword Ptr ds:[edi] ;Store final value
fstp ds:[Dummy] ;Free the Z inverse
add esi,12 ;Increment pointers
add edi,8 ;12 ;Increment pointers
dec ecx ;decrement counter
jnz c3d2d ;if not 0 go to other vertex
fistp ds:[Dummy]
fistp ds:[Dummy]
fistp ds:[Dummy] ;Free all
ret
ProyCords Endp
Esto esta por uno de los pocos docs que he dejado por la red y tiene como que unos años.. pero supongo que el codigo continuara siendo muy valido a pesar de que tirando de SIMD se podria acelerar mas.
Saludos, Astharoth / TLOTB.
Arg! recuerdo haber escrito el algoritmo sobre una servilleta de papel en un bar! si lo encuentro, lo escaneo y te lo mando, no sufras..
Yo daba por sentado que eran coordenadas 2d. Pero si son 3d en DirectX o en OpenGL es facil proyectar los puntos con la matriz de proyeccion actual, hay funciones explicitas para eso.
Vaya, gracias a todos.
Bueno ya tengo varias opciones por donde empezar a probar, incluida ese codigo en ensamblador; o recorrerme los bares rebuscando en la basura a ver si encuentro la mitica servilleta :sonriendo:
En realidad, esta función (si hubiera resultado tener un coste menor; bueno aún no sé como será de rápida pero me parece que no lo suficiente) estaba destinada a evitar renderizar aquellos triangulos que estuvieran ocultos por los más cercanos a la cámara. Renderizándose así unicamente los que se ven. Junto con el fustrum culling creia que iba a convertirse en una buena forma de optimización. Evitando incluso tener que hacer octrees, bsps o portales... pero vamos parece ser que la funcioncilla tendra un coste muy alto como para ir comparando cada triangulo... pero ¿y si junto con un sistema de octrees comparara solo los de las celdas visibles?
¿Cómo veis el asunto?
Ah, otra pregunta. ¿Habrá alguna forma de hacer la comparión sin necesidad de hacer las dos proyecciones? Me refiero a comparar con coordeandas espaciales, sin necesidad de "estamparlo" en 2d. (sí, es cierto que la comparación en 2d es trivial, pero la proyección daría un coste mayor)
¿Me explico?
[ Este Mensaje fue editado por: Loover el 2002-09-05 13:40 ]
Efectivamente eso de ir mirando si un triángulo tapa a los demás sería lento...porque para cada triángulo tendrías que comprobar el resto de triángulos (por lo menos los que estuvieran dentro del frustum)...un BSP podría agilizar la tarea ya que sólo comprobarías aquellos triángulos que estuvieran detrás del triángulo "actual" pero aún así me parece poco recomendable. Lo que sí puede ser que sea lo que estés buscando es un método denominado occlusion culling que va precisamente de eso, de averiguar qué objetos tapan a otros. Busca en google sobre ello. Hay algunos papers sobre el tema aunque para mí el mejor es sin duda el manual de
dPVS que contiene un montón de información sobre occlusion culling y otros métodos de ocultación...
HTH
Saludos
Muchas gracias :sonriendo:
La verdad es que el tema de la visibilidad esta bastante jodido...
que algoritmos habeis implementado ?
yo del frustum culling todavia no he pasado...
alguien conoce algun algoritmo de oclussion culling facilito ? :riendo: