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

Question

Я пытаюсь нарисовать многоугольник, используя c # и directx

Все, что я получаю, - это упорядоченный список точек из файла, и мне нужно нарисовать плоский многоугольник в трехмерном мире.

Я могу загрузить точки и нарисовать выпуклую форму, используя треугольник-вентилятор и drawuserprimitives.

Это, очевидно, приводит к неверным результатам, когда многоугольник очень вогнут (что может быть).

Я не могу себе представить, что я единственный, кто решает эту проблему (хотя я новичок gfx / directx - мой опыт работы в разработке приложений для gui \ windows).

Может ли кто-нибудь указать мне на простой для следования ресурс \ учебник \ алгоритм, который может мне помочь?

Answer 1

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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. После того, как вы нарисовали все эти треугольники, выключите запись трафарета, включите тестирование трафарета и цветную запись и нарисуйте полноэкранный четырехугольник в выбранном цвете. Это заполнит только пиксели внутри вашего выпуклого многоугольника.

Хорошей идеей будет поместить якорь в середину многоугольника и просто нарисовать прямоугольник размером с границу вашего многоугольника. Это немного экономит.

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

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

Answer 4

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

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