¿Cómo puedo renderizar líneas 2D gruesas como polígonos?

Question

Tengo un camino formado por una lista de puntos 2D. Quiero convertirlos en una tira de triángulos para renderizar una línea texturizada con un grosor específico (y otras cosas similares). Así que, esencialmente, la lista de puntos 2D debe convertirse en una lista de vértices que especifique el contorno de un polígono que, si se representa, representará la línea. El problema es manejar las uniones de esquina, mitras, gorras, etc. El polígono resultante debe ser "perfecto" en el sentido de que no haya sobregiro, juntas limpias, etc. para que pueda ser extruido o manipulado.

¿Hay algún recurso simple que pueda proporcionar información sobre algoritmos, código o más información sobre cómo hacerlo de manera eficiente?

Absolutamente NO deseo una biblioteca de vectores en 2D completa (cairo, antigrain, OpenVG, etc.) con curvas, arcos, guiones y todas las campanas y silbatos. He estado investigando en varios árboles fuente para implementaciones OpenVG y otras cosas para encontrar algo de información, pero todo es terriblemente intrincado.

Definitivamente estoy dispuesto a codificarlo yo mismo, pero hay muchos casos degenerados (segmentos pequeños + anchuras gruesas + esquinas agudas) que crean todo tipo de problemas de unión. Incluso un poco de ayuda me ahorraría horas tratando de lidiar con todos ellos.

EDITAR: Aquí hay un ejemplo de uno de esos casos degenerados que causa fealdad si simplemente fuera de vértice a vértice. Rojo es el camino original. Los bloques de color naranja son rectángulos dibujados en un ancho específico alineado y centrado en cada segmento.

http://www.freeimagehosting.net/uploads/52dc639727.png

Answer 1

Oh bien - He intentado resolver ese problema yo mismo. Perdí dos meses en una solución que intentó resolver el problema del sobregiro cero. Como ya ha descubierto, no puede tratar todos los casos degenerados y no tiene sobregiro cero al mismo tiempo.

Sin embargo, puede utilizar un enfoque híbrido:

escribe usted mismo una rutina que comprueba si las uniones pueden construirse a partir de geometría sencilla y sin problemas. Para hacerlo, debe verificar el ángulo de unión, el ancho de la línea y la longitud de los segmentos de línea unidos (los segmentos de línea que son más cortos que su ancho son un PITA). Con algunas heurísticas deberías ser capaz de resolver todos los casos triviales.

No sé cómo se ve su línea de datos promedio, pero en mi caso más del 90% de las líneas anchas no tenían casos degenerados.

Para todas las demás líneas:

Has muy probablemente ya ha encontrado que si usted tolera un sobregiro, la generación de la geometría es mucho más fácil. Hazlo y deja que un algoritmo CSG de polígono y un algoritmo de tesselación hagan el trabajo difícil.

He evaluado la mayoría de los paquetes de teselación disponibles, y terminé con el teselador de GLU. Fue rápido, robusto, nunca se estrelló (a diferencia de la mayoría de los otros algoritmos). Era gratis y la licencia me permitió incluirlo en un programa comercial. La calidad y la velocidad de la tesselación están bien. No obtendrá la calidad de triangulación de Delaunay, pero como solo necesita los triángulos para renderizar, eso no es un problema.

Como no me gustó la API tesselator, levanté el código tesselation de la implementación gratuita de referencia SGI de OpenGL, reescribí todo el front-end y agregué pools de memoria para bajar el número de asignaciones. Tomó dos días para hacer esto, pero valió la pena (como la mejora del rendimiento del factor cinco). La solución terminó en una implementación de OpenVG comercial por cierto :-)

Si está renderizando con OpenGL en una PC, es posible que desee mover el tesselation/CSG-job de la CPU a la GPU y usar stencil-buffer o trucos de z-buffer para eliminar el sobregiro. Eso es mucho más fácil y puede ser aún más rápido que la teselación de CPU.

Answer 2

Creo que me gustaría llegar a un algoritmo de triangulación. Es cierto que en la mayoría de los casos en que se usan, el objetivo es reducir el número de vértices para optimizar el renderizado, pero en su caso se puede parametrizar para conservar todos los detalles, y la posibilidad de optimización puede ser útil.

Hay numerosos algoritmos de teselación y código por todas partes en la web - Me envolvió una C pura en un DLL hace unos años para su uso con un procesador de paisaje Delphi, y no son un tema raro que los gráficos avanzados tutoriales de codificación y similares.

Answer 3

Estoy interesado en esto también, ya que quiero perfeccionar el dibujo de carreteras de mi aplicación de mapeo (Kosmos). Una solución que utilicé es dibujar la polilínea dos veces, una con una línea más gruesa y otra con un diluyente, con un color diferente. Pero esto no es realmente un polígono, es solo una manera rápida de simular uno. Vea algunos ejemplos aquí: http://wiki.openstreetmap.org/wiki/Kosmos_Rendering_Help#Rendering_Options

No estoy seguro si esto es lo que necesita.

Answer 4

Ver si Delaunay triangulation puede ayudar.

Answer 5

Un método simple en la parte superior de mi cabeza.

Biseca el ángulo de cada Vertex 2d, esto creará una buena línea de inglete. Luego, mueva a lo largo de esa línea, hacia adentro y hacia afuera, la cantidad de su "espesor" (¿o el grosor dividido entre dos?), Ahora tiene sus puntos de polígono interno y externo. Vaya al siguiente punto, repita el mismo proceso, construya sus nuevos puntos de polígono en el camino. A continuación, aplique una triangulación para obtener sus vértices listos para renderizar.

Answer 6

En mi caso podría darme el lujo de sobregirar. Acabo de drow círculos con radio = ancho/2 centrado en cada uno de los vértices de la polilínea.

Los artefactos están enmascarados de esta manera, y es muy fácil de implementar, si puede vivir con esquinas "redondeadas" y algunos sobregiros.

Answer 7

De su imagen, parece que está dibujando recuadro alrededor de los segmentos de línea con FILL on y usando color naranja. Si lo hace, seguro que creará malos sobregiros. Entonces, lo primero que debe hacer es no hacer borde negro y el color de relleno puede ser opaco.

¿Por qué no puedes usar la primitiva GL_LINES para hacer lo que intentas hacer? Puede especificar el ancho, el filtrado, la suavidad y cualquier textura. Puedes renderizar todos los vértices usando glDrawArrays(). Sé que esto no es algo que tengas en mente, pero como te estás enfocando en el dibujo en 2D, este podría ser un enfoque más fácil. (búsqueda de líneas texturizadas, etc.)

Answer 8

Terminé teniendo que ensuciarme las manos y escribir un pequeño lazo para resolver un problema similar.

Para mí, el problema era que quería líneas gruesas en OpenGL que no tuvieran el tipo de artefactos que estaba viendo con OpenGL en el iPhone. Después de mirar varias soluciones; curvas de bezier y cosas por el estilo - decidí que probablemente era más fácil hacer solo el mío. Hay un par de enfoques diferentes.

Una aproximación es encontrar el ángulo de intersección entre dos segmentos y luego moverse a lo largo de esa línea de intersección a cierta distancia de la superficie y tratarlo como un vértice de cinta. Intenté eso y no parecía intuitivo; el ancho de la cinta podría variar.

Otro enfoque consiste en calcular una normal a la superficie de los segmentos de línea y usar eso para calcular el borde de cinta ideal para ese segmento y para realizar pruebas de intersección reales entre segmentos de cinta. Esto funcionó bien, excepto que para las esquinas agudas, las intersecciones del segmento de la línea de cinta estaban demasiado lejos (si el ángulo entre segmentos se acercaba a 180 ').

He trabajado alrededor del problema de ángulo agudo con dos enfoques. El algoritmo de intersección de líneas de Paul Bourke (que utilicé de forma no optimizada) sugirió detectar si la intersección estaba dentro de los segmentos. Como ambos segmentos son idénticos, solo necesitaba probar uno de los segmentos para la intersección. Entonces podría arbitrar cómo resolver esto; ya sea al mezclar el mejor punto entre los dos extremos o al colocar una tapa final - ambos enfoques se ven bien - el enfoque de la tapa final puede desprenderse del polígono frontal/posterior ordenando para opengl.

Ver http://paulbourke.net/geometry/lineline2d/

Ver mi código fuente aquí: https://gist.github.com/1474156

Answer 9

simplemente me encontré con este trabajo increíble:

http://www.codeproject.com/Articles/226569/Drawing-polylines-by-tessellation

Parece que hacer exactamente lo que quiere, y su licencia permite para usarlo incluso en aplicaciones comerciales. Además, el autor hizo un gran trabajo al detallar su método. Probablemente le daré una oportunidad en algún momento para reemplazar mi propia implementación no tan perfecta.