if (poligono_oculo (posible_poly_oculto, otro_poly_cualquier

[Loover]

                                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.                                

[Drácula]

                                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.


                               

[Loover]

                                ¿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?                                

[samsaga2]

                                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.                                

[Drácula]

                                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?                                

[Astharoth]

                               
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.
                               

[mallrat]

                                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..
                               

[samsaga2]

                                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.                                

[Loover]

                                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 ]                                

[BeRSeRKeR]

                                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 http://www.hybrid.fi/surrender/download/dpvs_online.pdf">dPVS que contiene un montón de información sobre occlusion culling y otros métodos de ocultación...

HTH

Saludos
                               

[Loover]

                                Muchas gracias :sonriendo:                                

[Lord Trancos]

                                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: