Есть ли эффективный\простой способ нарисовать вогнутый многоугольник в Direct3d

Direct3D может рисовать только треугольники (ну, он может рисовать и линии, и точки, но это не главное). Поэтому, если вы хотите нарисовать любую фигуру, которая сложнее треугольника, вам нужно нарисовать кучу соприкасающихся треугольников, равных этой фигуре.

В вашем случае это проблема триангуляции вогнутого многоугольника. Учитывая кучу вершин, вы можете оставить их как есть, вам просто нужно вычислить «индексный буфер» (в простейшем случае три индекса на треугольник, которые говорят, какие вершины использует треугольник). Затем нарисуйте это, поместив в буферы вершин/индексов или используя DrawUserPrimitives.

Некоторые алгоритмы триангуляции простых (выпуклых или вогнутых, но без самопересечений и отверстий) многоугольников находятся по адресу сайт VTerrain.

Я использовал код Ratcliff в прошлом; очень просто и хорошо работает. VTerrain имеет мертвую ссылку на него; код можно найти здесь. Это C++, но перенос его на C# должен быть простым.

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

Триангуляция — это очевидный ответ, но сложно написать надежный триангулятор. Если у вас нет двух месяцев времени, чтобы тратить его впустую, даже не пытайтесь.

Есть пара кодов, которые могут вам помочь:

Библиотека ГПК. Очень прост в использовании, но вам может не понравиться его лицензия:

http://www.cs.man.ac.uk/~toby/alan/software/gpc.html

Есть еще треугольник:

http://www.cs.cmu.edu/~quake/triangle.html< /а>

http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html

Другим (и моим предпочтительным) вариантом было бы использование тесселятора GLU. Вы можете без проблем загружать и использовать библиотеку GLU из программ DirectX. Для его использования не требуется контекст OpenGL, и он предустановлен на всех компьютерах с Windows. Если вам нужен исходный код, вы можете взять код триангуляции из эталонной реализации SGI. Я сделал это один раз, и это заняло у меня всего пару часов.

Пока что для триангуляции. Есть и другой способ: вы можете использовать трюки с трафаретами.

Общий алгоритм выглядит так:

1. Отключите запись цвета и глубины. Включите запись трафарета и настройте буфер трафарета, чтобы он инвертировал текущее значение трафарета. Достаточно одного кусочка трафарета. О, ваш буфер трафарета также должен быть очищен.

2. Выберите случайную точку на экране. Подойдет любой. Назовите эту точку своим Якорем.

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

4. После того, как вы нарисовали все эти треугольники, выключите трафаретную запись, включите проверку трафарета и цветную запись и нарисуйте полноэкранный четырехугольник в выбранном вами цвете. Это заполнит только пиксели внутри вашего выпуклого многоугольника.

Рекомендуется поместить якорь в середину многоугольника и просто нарисовать прямоугольник размером с граничную рамку вашего многоугольника. Это экономит немного скорости заполнения.

Кстати, метод трафарета работает и для самопересекающихся многоугольников.

Надеюсь, это поможет, Нильс

Если вы можете использовать буфер трафарета, это не составит труда. Вот общий алгоритм:

Clear the stencil buffer to 1.
Pick an arbitrary vertex v0, probably somewhere near the polygon to reduce floating-point errors.
For each vertex v[i] of the polygon in clockwise order:
    let s be the segment v[i]->v[i+1] (where i+1 will wrap to 0 when the last vertex is reached)
    if v0 is to the "right" of s:
        draw a triangle defined by s, v[i], v[i+1] that adds 1 to the stencil buffer
    else
        draw a triangle defined by s, v[i], v[i+1] that subtracts 1 from the stencil buffer
end for
fill the screen with the desired color/texture, testing for stencil buffer values >= 2.

Под «справа от s» я подразумеваю точку зрения человека, стоящего на v[i] лицом к v[i+1]. Это можно проверить с помощью перекрестного произведения:

крест(v0 - v[i], v[i+1] - v[i]) > 0

Я просто должен был сделать это для проекта. Самый простой алгоритм, который я нашел, называется «Отсечение ушей». Отличный документ по этому вопросу находится здесь: TriangulationByEarClipping.pdf

Мне потребовалось около 250 строк кода на С++ и 4 часа, чтобы реализовать его версию методом грубой силы. Другие алгоритмы имеют лучшую производительность, но их было просто реализовать и понять.