¿Cómo se renderiza líneas gruesas en 2D como polígonos?

Question

Tengo un camino formado por una lista de puntos 2D. Quiero convertirlas en una tira de triángulos con el fin de hacer que una línea texturizada con un espesor especificado (y otras cosas). Así que, esencialmente la lista de puntos 2D necesita para convertirse en una lista de vértices que especifican el contorno de un polígono que se dicten haría que la línea. El problema es el manejo de la esquina se une, ingletes, casquillos, etc. El polígono resultante tiene que ser "perfecto" en el sentido de no overdraw, limpio une, etc. de manera que sea factible podría ser extruido o jugó con lo contrario.

¿Hay algún sencilla recursos en torno a que puede dar una idea de algoritmo, código o cualquier más información sobre cómo hacer esto de manera eficiente?

Me absolutamente NO QUIERO que una biblioteca de pleno derecho 2D vectorial (El Cairo, antigrain, OpenVG, etc.) con las curvas, arcos, guiones y todas las campanas y silbatos. He estado cavando en múltiples árboles de origen para las implementaciones OpenVG y otras cosas para encontrar una idea, pero es terriblemente complicado.

definitivamente estoy dispuesto a codificar yo mismo, pero hay muchos casos degenerados (pequeños segmentos anchos + + gruesas esquinas agudas) que crean todo tipo de problemas de combinación. Incluso un poco de ayuda me ahorraría horas de tratar de hacer frente a todos ellos.

EDIT: He aquí un ejemplo de uno de esos casos degenerados que causa la fealdad si estuviera simplemente para ir de vértice a vértice. El rojo es el camino original. Los bloques de color naranja son rectángulos dibujados en un ancho especificado alineados y centrados en cada segmento.

Answer 1

Oh, bueno - He tratado de resolver el problema mismo. Me tirado de dos mes en una solución que trató de resolver el problema de descubierto por cero. Como ya has descubierto que no puede hacer frente a todos los casos degenerados y tienen cero de descubierto al mismo tiempo.

Sin embargo, puede utilizar un enfoque híbrido:

Escribir a sí mismo una rutina que comprueba si las uniones pueden construirse a partir de geometría sencilla y sin problemas. Para ello hay que comprobar el ángulo de unirse, la anchura de la línea y la longitud de los segmentos lineales unidas (segmentos de línea que son más cortas que su anchura son un PITA). Con algunas heurísticas que debe ser capaz de resolver todos los casos triviales.

No sé cómo su línea media de los datos se parece, pero en mi caso más del 90% de las líneas de ancho tenido casos degenerados.

Para todas las demás líneas:

Has muy probablemente ya ha encontrado que si se tolera girar en descubierto, la generación de la geometría es mucho más fácil. Hacerlo, y dejar un algoritmo polígono CSG y un algoritmo tesselation hacer el trabajo duro.

Me he evaluado la mayoría de los paquetes Tesselation disponibles, y que terminó con la tesselator GLU. Fue rápido, robusto, nunca se estrelló (a diferencia de la mayoría de los otros algoritmos). Era libre y la licencia me ha permitido incluirlo en un programa comercial. La calidad y la velocidad de la teselación está bien. Usted no recibirá la calidad Delaunay triangulación, pero ya que sólo tiene los triángulos para representar eso no es un problema.

Desde que disgustaba el API tesselator Levanté el código tesselation de la implementación de referencia libre de SGI OpenGL, volvió a escribir la totalidad de front-end y añadido agrupaciones de memoria para obtener el número de las asignaciones de abajo. Se necesitaron dos días para hacer esto, pero valió la pena (como factor de mejora del rendimiento de cinco). La solución terminó en una aplicación comercial OpenVG por cierto: -)

Si estás reproduciendo con OpenGL en un PC, es posible que desee mover el tesselation / CSG puesto de trabajo de la CPU a la GPU y el uso-stencil buffer o tampón Z trucos para eliminar el sobregiro. Eso es mucho más fácil y puede ser incluso más rápido que tesselation CPU.

Answer 2

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

Biseccionar el ángulo de cada Vertex 2d, esto creará una línea agradable de inglete. A continuación, pasar a lo largo de esa línea, tanto hacia adentro y hacia afuera, la cantidad de su "espesor" (o grosor dividido por dos?), Ahora tiene sus puntos del polígono interior y exterior. Pasar al siguiente punto, repetir el mismo proceso, la construcción de sus nuevos puntos de polígonos a lo largo del camino. A continuación, aplicar una triangualtion para obtener sus vértices render listo.

Answer 3

Acabo de encontrar este sorprendente trabajo:

http://www.codeproject.com/Articles/226569/ Gráfico-polilíneas-by-teselación

Parece que hacer exactamente lo que quiere, y su licencia permite utilizarlo incluso en aplicaciones comerciales. Además, el autor ha hecho un gran trabajo de verdad a los detalles de su método. Probablemente voy a darle un tiro en algún momento para sustituir a mi propia implementación no-casi-como-perfecto.

Answer 4

Me acabé teniendo que ensuciarme las manos y escribir una pequeña ribbonizer para resolver un problema similar.

Para mí el problema era que quería líneas de grasa en OpenGL que no contaban con los tipos de artefactos que estaba viendo con OpenGL en el iPhone. Después de mirar varias soluciones; curvas de Bézier y similares - yo decidimos que era probablemente más fácil simplemente hacer mi propia. Hay un par de enfoques diferentes.

Un enfoque es encontrar el ángulo de intersección entre dos segmentos y luego pasar a lo largo de esa línea de intersección a una cierta distancia de la superficie y el tratamiento de que a medida que un vértice de la cinta. He intentado eso y que no se veía intuitiva; la anchura de la cinta podría variar.

Otro enfoque consiste en calcular en realidad una normal a la superficie de los segmentos de línea y el uso que para calcular el borde de la cinta ideal para ese segmento y hacer pruebas de intersección reales entre los segmentos de cinta. Esto funcionó bien excepto que para esquinas afiladas las intersecciones segmento de línea de cinta eran demasiado lejos (si el ángulo entre segmentos se acercó a 180' ).

He trabajado en torno al tema ángulo agudo con dos enfoques. El algoritmo de intersección línea Paul Bourke (que he utilizado de una manera no optimizado) sugirió detectando si la intersección estaba dentro de los segmentos. Dado que ambos segmentos son idénticos sólo necesitaba para probar uno de los segmentos de intersección. Entonces podría arbitrar la manera de resolver esto; ya sea por esquivar un mejor punto entre los dos extremos, o poniendo en una tapa de extremo - ambos enfoques se ven bien - el enfoque tapa de extremo puede deshacerse de la parte delantera del polígono / espalda frente a ordenar para OpenGL

.

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

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

Answer 5

Estoy interesado en esto también, ya que quiero perfeccionar de ( Kosmos ) dibujo de carreteras. Una solución que utiliza es para dibujar la polilínea dos veces, una vez con una línea más gruesa y una vez con un diluyente, con un color diferente. Pero esto no es realmente un polígono, es sólo una forma rápida de simular una. Vea aquí algunas muestras: http://wiki.openstreetmap.org/wiki/Kosmos_Rendering_Help#Rendering_Options

No estoy seguro de si esto es lo que necesita.

Answer 6

Creo que me gustaría llegar a un algoritmo de triangulación. Es cierto que en la mayoría de los casos cuando estos se utilicen el objetivo es reducir el número de vértices para optimizar la prestación, pero en su caso se podrían parametrizar para retener todos los detalles -. Y la posibilidad de optimización puede resultar muy ú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 de codificación tutoriales y similares.

Answer 7

A ver si triangulación de Delaunay puede ayudar.

Answer 8

En mi caso me podía permitir el sobregiro. I sólo círculos drow con radio = anchura / 2 centrada en cada uno de los vértices de la polilínea.

Los artefactos se enmascaran esta manera, y es muy fácil de implementar, si se puede vivir con esquinas redondeadas "" y algunos sobregirar.

Answer 9

A partir de su imagen se ve como que está caja alrededor de los segmentos del dibujo lineal con relleno de encendido y el uso del color naranja. Si lo hace, va a crear malos sobregiros a ciencia cierta. Así que lo primero que debe hacer sería no hacer borde negro y el color de relleno puede ser opaco.

¿Por qué no se puede utilizar GL_LINES primitiva para hacer lo que la intención de hacer? Puede especificar el ancho, filtrado, suavidad, textura nada. Puede hacer que todos los vértices utilizando glDrawArrays (). Sé que esto no es algo que se tiene en mente, pero a medida que se está centrando en el dibujo 2D, este enfoque podría ser más fácil. (Búsqueda de líneas de textura, etc.)