Triangulating Non Convex Polygons

[Zaelsius]

 He estando buscando algoritmos para dividir poligonos NO convexos en triángulos. Hay bastante información, pero casi toda bastante mala y no es concisa sobre el tema porque la mezcla con otras cosas... bueno si alguien sabe algun enlace sobre el tema se lo agradecería.

PD. había 2 tutos en gamedev.net pero han perdido las imágenes y el código fuente :angry: , en el texto no aparece el algoritmo en sí.

Quiero hacer un pequeño editor de niveles tipo Doom1/2, por sectores, y necesito devidir los sectores(poligonos) en triangulos a la hora de dibujarlos.

Un ejemplo de lo que quiero (con la opcion "triangulate" activada)

[Zaelsius]

 Ya he resuelto el problema  B) . No era difícil, pero leer enfocados para matemáticos es un tostón - y encima en inglés.

[CoLSoN2]

 Supongo ke me encuentro en tu mismo problema. Digo supongo porque no tengo ni idea de qué es un polígono convexo, pero estoy intentando hacer un conversor .map -> .mesh, y seguramente sabrás que .map guarda la geometria en brushes creados por planos, en vez de vertices y demás. Y esto es lo que necesito exportar.

[BeRSeRKeR]

 Si con el formato map te refieres a los de los quakes, este tutorial es exactamente lo que andas buscando :D.

Saludos

[MChiz]

 En un poligono convexo puedes trazar una linea escogiendo dos puntos al azar, que esten dentro de este, y la linea NO intersectara con ninguno de los lados del poligono. Si intersectase, este seria un poligono concavo.

[Mars Attacks]

 ¿No viste ese capítulo de Barrio Sésamo?
._.
|_| <- esto es convexo

|V| <- y esto es cóncavo. Supercocoooooooooooooooo
¨¨

[CoLSoN2]

 gracias berserker, pero Jedive se te adelantó (irc) xD

[BeRSeRKeR]

  (nooo)  :D  

[tamat]

 Supongo que intentaras hacer lo mismo que hace el TrueForm de las Radeon pero por software, no?

[Zaelsius]

  :huh:  no, sólo quiero dividir un polígono 2D en triángulos. Lo que tu dices ya tiene mucho más curro... hay algo sobre eso en el libro "Advanced 3d game programming with DirectX 8.0" por si a alguien le interesa. No conozco las características de TrueForm, pero supongo k será mas o menos la implementación de ATI de los patches de DX9, con algun extra...

[MChiz]

 Hola:

Las GLU tienen unas funciones para tesselar, creo. Supongo que D3DX tambien tendra las suyas.

[Zaelsius]

 Una página de una universidad americana donde encontré información del tema:
http://www.cis.ohio-state.edu/~crawfis/cis781/

Unas presentaciones sobre gráficos 3d:
http://www.cis.ohio-state.edu/~crawfis/cis781/Slides/

Y la presentación concreta sobre los poligonos convexos y su triangulación:
http://www.cis.ohio-state.edu/~crawfis/cis...angulations.ppt

Podeis usar el MS PowerPoint viewer para ver los .ppt:
Download PPview97

¡Que aproveche!  :)  

[MChiz]

 Ya que se habla del tema... alguien sabe de algun algoritmo bonito para hacer, a partir de triangulos, un poligono convexo ( convexo en el sentido 2D )?

[Zaelsius]

  :D Jaja, ¿para que necesitas hacer eso? normalmente es al revés...  pero no sé,  a ver cuentanos tu caso tras la pausa de publicidad. :P  

[MChiz]

 Normalmente al reves? Yo creo que no. No hace mucho tiempo programe un algoritmo que me hacia esto. Lo utilice para un experimento de pathfinding y funciono a la perfeccion, pero no estaba contento con el metodo que utilizaba ( era muy lento ). Un colega mio tambien lo queria utilizar para hacer unos lightmaps bien rapidos y bonitos ( tecnicamente hablando ).