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)
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.
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.
Si con el formato map te refieres a los de los quakes,
este tutorial es exactamente lo que andas buscando :D.
Saludos
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.
¿No viste ese capítulo de Barrio Sésamo?
._.
|_| <- esto es convexo
|V| <- y esto es cóncavo. Supercocoooooooooooooooo
¨¨
gracias berserker, pero Jedive se te adelantó (irc) xD
(nooo) :D
Supongo que intentaras hacer lo mismo que hace el TrueForm de las Radeon pero por software, no?
: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...
Hola:
Las GLU tienen unas funciones para tesselar, creo. Supongo que D3DX tambien tendra las suyas.
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.pptPodeis usar el MS PowerPoint viewer para ver los .ppt:
Download PPview97¡Que aproveche! :)
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 )?
: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
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 ).
Debo de estar algo aturdido por los exámenes, pq sigo sin ver la conexión ¿?
Se supone que el algoritmo de pathfinding buscaba una ruta alrededor de tríangulos.. ¿? dont get it
Ahora no me voy a poner a explicarlo... espero que me entiendas : )
Pero vendria a ser mas o menos lo que dices, pero en vez de triangulos, zonas convexas ( y digo convexo, no concavo )
Vale, ya entiendo lo que dices... :P
Me alegro : )
Esto es interesante:
triangular un poligono es facil, al reves NO. Por facil me refiero computacionalmente.
Para triangular un poligono debes dividirlo recursivamente mediante "diagonales internas". Una diagonal interna es un segmento entre dos vertices no consecutivos que no se cruza con otro segmento. Al dividir un poligono con una diagonal interna te quedan dos poligonos que se van a dividir de nuevo; asi hasta llegar a un triangulo simple.
Crear un poligono CONCAVO a partir de un conjunto de triangulos es trivial y no se me ocurre para que puede servir.
Pero para formar un conjunto de poligonos CONVEXOS a partir de un conjunto de triangulos no se ningun algoritmo eficiente. Se podria construir un modelo de fronteras y formar subconjuntos de triangulos de manera sistematica ( N contra N ) y realizar un test de convexidad para cada uno. Pero te queda el problema de saber si es la solucion mas eficiente, ya que hay multiples soluciones. Se parace al problema de crear strips a partir de un conjunto de triangulos.
:)
Ei TurMach! Cuanto tiempo!! ; )
Te acuerdas de mis ralladas con el tema? jejejeje ai la leche, que dificil es la vida del programador ;bb