Ordenar Los Vértices De Un Polígono

[BeRSeRKeR]

 Hola.

Estoy preparando una serie de métodos para implementar un sistema de render basado en portales para el motor C# y me he encontrado con un problemilla. Resulta que los portales los representaríamos en MAX como polígonos convexos, pero el problema es que MAX no te da los vértices de forma consecutiva, cosa necesaria a la hora crear el frustum o de recortar el portal a través del frustum.

Así que he estado pensando y he implementado un sistema para conseguir ordenar los vértices de un polígono. Lo que hago es:

- Calcular el centro de masas del polígono.
- Calcular dos vectores (v1 y v2) que van desde el origen a dos vértices cualesquiera del polígono (comprobando que no sean paralelos).
- Calcular un tercer vector (v3) resultante del producto vectorial de los dos vectores anteriores.
- Calcular otro vector (normal) resultante del producto vectorial entre v1 y v3.
- Normalizar el vector normal.
- Con esto ya tenemos lo necesario para calcular un plano de divide el polígono en dos secciones.
- Ahora se crean dos listas, una con los vértices que se encuentran en el half-space positivo (o sobre el plano) y otra con los vértices que se encuentran en el half-space negativo.
- Para cada lista recorremos los vértices y vamos calculando el ángulo con respecto al vector v1.
- Ordenamos ambas listas en base a los ángulos. La de vértices en el half-space positivo de menor a mayor y la otra de mayor a menor.
- Unimos ambas listas.

Con eso ya tenemos la lista de vértices de forma consecutiva. Al menos lo he estado probando con varios polígonos y parece funcionar.

El problema es que lo mismo se me crea en sentido clockwise que anti-clockwise y además me parece que es un método un tanto complejo (aunque el uso que le voy a dar va a ser en tiempo de exportación en MAX por lo que la velocidad no me importa).

El caso es que me gustaría saber si conocéis un método más sencillo para conseguir esto, y ya de paso poder especificar si se ordenan en sentido clockwise o anti-clockwise.

Gracias.

[Lord Trancos 2]

 Yo de maxscript no tengo mucha idea,...

He estado mirando un poco la ayuda, y.... si es un pol. convexo, tendra un único edge, no?

Código [Seleccionar] Expand


$plane01.edges[1]


Despues con

Código [Seleccionar] Expand


polyOp.getEdgeVerts

o

polyOp.getVertsUsingEdge


deberias de poder obtener los vertices de ese edge.

Quien sabe, con un poco de suerte te los devuelve en orden y todo... ^_^ (no lo he probado).

A una mala (si no te los da en orden), sabes que cada uno de esos vertices es colega de otros dos del mismo grupo; esto deberia de permitirte calcular el orden.

Lo de saber si es CW o CCW, ya no sabria como hacerlo. -_-;

En fins... perdon si estoy diciendo tonterias... como ya he dicho no se mucho de maxscript.

[Lord Trancos 2]

 kk...

se me fue la pinza  (nooo)

No tiene 1 edge. Lo que tendra será 1 border....

Código [Seleccionar] Expand


polyOp.getBorderFromEdge


Tal vez con esa funcion lo puedas obtener...

[BeRSeRKeR]

 Gracias.

Por ahí iban los tiros. Si el portal está formado por un único polígono, se puede utilizar:

polyOp.getFaceVerts

Eso te devuelve la lista de vértices que forman el polígono y aparentemente están ordenados.

En cualquier caso ya que estamos me gustaría saber si hay algún método más óptimo (y simple) que el que he propuesto anteriormente. De momento me apaño con MAXScript.

Saludos.

[Haddd]

 Como todos los vértices están en el mismo plano, podríamos buscar el pto que está más abajo a la izquierda, de forma que todos los vértices restantes queden en el plano superior derecho. De esta forma, el producto escalar estaría entre el rango 0º y 90º y se podría ordenar utilizando este valor.

Pero no lo he probado...seguro que falla algo  :P

Error, no sirve. Lo he probado con el teclado como objeto y no funciona  O_O  

[Pogacha]

  -> Convex hull ?, Algoritmo con cuello en ordenamiento, si los vectores estan en un plano sacas U y V perpendiculares, normalizados (!= 0 sobran) y pertenecientes al plano, ordenas por u y del primero al ultimo trazas una recta imaginaria, lo que este por encima en orden los metes en el arreglo final en orden acendente y lo que este debajo lo metes de atras para adelante. Si no fuese convexo debes comprobar valides antes de meterlo ...
Saludos

[Amatar]

 Un poquito de bibliografia (o googlegrafia?)

http://ma1.eii.us.es/Miembros/almar/docenc...ente/tema5.html
http://cgm.cs.mcgill.ca/~athens/cs601/

Son sobre cierres convexos, para solucionar el problema incluso si te dan los puntos sueltos sin ninguna informacion extra.

[BeRSeRKeR]

 La verdad es que no relacioné el problema con el cálculo del convex hull. :)

Gracias.