Как визуализировать толстые 2D-линии в виде многоугольников?

Question

У меня есть путь, состоящий из списка 2D-точек.Я хочу превратить их в полосу треугольников, чтобы визуализировать текстурированную линию заданной толщины (и другие подобные вещи).Таким образом, по сути, список 2D-точек должен стать списком вершин, определяющих контур многоугольника, который при визуализации будет отображать линию.Проблема заключается в обработке угловых соединений, углов, колпачков и т. д.Полученный многоугольник должен быть «идеальным» в смысле отсутствия перерисовки, чистых соединений и т. д.так, чтобы его можно было выдавить или иным образом поиграть с ним.

Есть ли какие-нибудь простой ресурсы вокруг, которые могут предоставить понимание алгоритма, код или любую другую информацию о том, как сделать это эффективно?

Мне категорически НЕ нужна полноценная 2D векторная библиотека (cairo, antigrain, OpenVG и т.д.) с кривыми, дугами, штрихами и всеми наворотами.Я копался в нескольких деревьях исходных кодов для реализаций OpenVG и других вещей, чтобы найти хоть какое-то понимание, но все это ужасно запутанно.

Я определенно готов написать это сам, но есть много вырожденных случаев (маленькие сегменты + толстая ширина + острые углы), которые создают всевозможные проблемы с объединением.Даже небольшая помощь сэкономила бы мне часы, потраченные на попытки разобраться со всеми ними.

РЕДАКТИРОВАТЬ:Вот пример одного из тех вырожденных случаев, который вызывает уродство, если вы просто переходите от вершины к вершине.Красный — исходный путь.Оранжевые блоки представляют собой прямоугольники, нарисованные определенной ширины, выровненные и центрированные по каждому сегменту.

Answer 1

Ну ладно, я пытался решить эту проблему сам.Я потратил два месяца на решение проблемы нулевой перерисовки.Как вы уже поняли, вы не можете справиться со всеми ухудшенными случаями и в то же время иметь нулевую перерисовку.

Однако вы можете использовать гибридный подход:

Напишите себе программу, которая проверяет, можно ли без проблем построить соединения из простой геометрии.Для этого вам необходимо проверить угол соединения, ширину линии и длину соединенных сегментов линии (сегменты линии, которые короче их ширины, являются PITA).С помощью некоторых эвристик вы сможете разобраться во всех тривиальных случаях.

Я не знаю, как выглядят ваши средние линейные данные, но в моем случае более 90% широких линий не имели вырожденных случаев.

Для всех остальных строк:

Вы, скорее всего, уже поняли, что если вы допускаете перерисовку, создание геометрии становится намного проще.Сделайте это, и пусть алгоритм полигонального CSG и алгоритм тесселяции сделают тяжелую работу.

Я оценил большинство доступных пакетов тесселяции и остановился на тесселяторе GLU.Он был быстрым, надежным и никогда не давал сбоев (в отличие от большинства других алгоритмов).Он был бесплатным, и лицензия позволяла мне включить его в коммерческую программу.Качество и скорость тесселяции в порядке.Вы не получите качества триангуляции Делоне, но поскольку для рендеринга вам нужны просто треугольники, это не проблема.

Поскольку мне не нравился API тесселятора, я взял код тесселяции из бесплатной эталонной реализации SGI OpenGL, переписал весь интерфейс и добавил пулы памяти, чтобы уменьшить количество выделений.На это ушло два дня, но оно того стоило (например, повышение производительности в пять раз).Кстати, решение оказалось в коммерческой реализации OpenVG :-)

Если вы выполняете рендеринг с помощью OpenGL на ПК, вы можете переместить задание тесселяции/CSG с ЦП на графический процессор и использовать приемы с трафаретным буфером или z-буфером, чтобы удалить перерисовку.Это намного проще и может быть даже быстрее, чем тесселяция процессора.

Answer 2

Простой метод, который пришел мне в голову.

Разделите угол каждой 2d вершины пополам, это создаст красивую линию среза.Затем переместите вдоль этой линии, как внутрь, так и наружу, на величину вашей «толщины» (или толщины, разделенной на два?), теперь у вас есть внутренние и внешние точки многоугольника.Перейдите к следующей точке, повторите тот же процесс, по пути создавая новые точки полигона.Затем примените триангуляцию, чтобы получить готовые к рендерингу вершины.

Answer 3

Я только что нашел эту замечательную работу:

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

Кажется, он делает именно то, что вам нужно, а его лицензия позволяет использовать его даже в коммерческих приложениях.Плюс автор проделал действительно большую работу по детализации своего метода.Вероятно, в какой-то момент я попробую заменить мою собственную, не столь совершенную реализацию.

Answer 4

В итоге мне пришлось запачкать руки и написать небольшой ленточник для решения аналогичной проблемы.

Для меня проблема заключалась в том, что мне нужны были жирные линии в OpenGL, не имеющие тех артефактов, которые я видел в OpenGL на iPhone.Посмотрев различные решения;кривые Безье и тому подобное — я решил, что, наверное, проще всего сделать самому.Есть несколько разных подходов.

Один из подходов состоит в том, чтобы найти угол пересечения двух сегментов, а затем переместиться вдоль этой линии пересечения на определенное расстояние от поверхности и рассматривать ее как вершину ленты.Я попробовал это, и это не выглядело интуитивно понятным;ширина ленты будет разной.

Другой подход заключается в том, чтобы фактически вычислить нормаль к поверхности сегментов линии и использовать ее для вычисления идеального края ленты для этого сегмента, а также выполнить фактические тесты пересечения между сегментами ленты.Это работало хорошо, за исключением того, что для острых углов пересечения сегментов линии ленты были слишком далеко (если угол между сегментами приближался к 180 ').

Я решил проблему острого угла двумя способами.Алгоритм пересечения линий Пола Бурка (который я использовал неоптимизированным способом) предлагал определять, находится ли пересечение внутри сегментов.Поскольку оба сегмента идентичны, мне нужно было проверить только один из сегментов на пересечение.Тогда я мог бы решить, как решить эту проблему;либо путем подделки лучшей точки между двумя концами, либо путем установки торцевой заглушки - оба подхода выглядят хорошо - подход с торцевой заглушкой может нарушить порядок расположения лицевой и обратной сторон многоугольника для opengl.

Видеть http://paulbourke.net/geometry/lineline2d/

Смотрите мой исходный код здесь: https://gist.github.com/1474156

Answer 5

Меня это тоже интересует, так как я хочу усовершенствовать свое картографическое приложение (Космос) рисование дорог.Один из обходных путей, который я использовал, — нарисовать полилинию дважды: один раз более толстой линией, а другой раз более тонкой и другим цветом.Но на самом деле это не многоугольник, а просто быстрый способ его моделирования.Посмотрите некоторые образцы здесь: http://wiki.openstreetmap.org/wiki/Kosmos_Rendering_Help#Rendering_Options

Я не уверен, что это то, что вам нужно.

Answer 6

Я думаю, что я бы обратился к алгоритму тесселяции.Это правда, что в большинстве случаев, когда они используются, цель состоит в том, чтобы уменьшить количество вершин для оптимизации рендеринга, но в вашем случае вы можете параметризовать, чтобы сохранить все детали - и возможность оптимизации может оказаться полезной.

В сети существует множество алгоритмов тесселяции и кода - несколько лет назад я включил чистый C в DLL для использования с ландшафтным рендерером Delphi, и они не являются редкостью в учебниках по продвинутому графическому кодированию и тому подобном.

Answer 7

Видишь ли, если Триангуляция Делоне может помочь.

Answer 8

В моем случае я мог позволить себе перерисовку.Я просто рисую круги с радиусом = ширина/2, центрированные по каждой вершине полилинии.

Таким образом маскируются артефакты, и это очень легко реализовать, если вы можете жить со «закругленными» углами и некоторой перерисовкой.

Answer 9

Судя по вашему изображению, вы рисуете рамку вокруг сегментов линий с включенной ЗАПОЛНЕНИЕМ и используете оранжевый цвет.Это наверняка приведет к плохим перерисовкам.Поэтому первое, что нужно сделать, — не отображать черную рамку, а цвет заливки может быть непрозрачным.

Почему вы не можете использовать примитив GL_LINES, чтобы сделать то, что вы намереваетесь сделать?Вы можете указать ширину, фильтрацию, плавность, текстуру, что угодно.Вы можете визуализировать все вершины, используя glDrawArrays().Я знаю, что вы имеете в виду не это, но, поскольку вы сосредоточены на 2D-рисовании, этот подход может оказаться более простым.(поиск Текстурированных линий и т. д.)