Заполнение многоугольника: выполнение правила намотки против четного нечетного правила

Question

Для сложного многоугольника (т. Е. Самопересекающегося) выбор между правилами заполнения Обмотки или Четно-Нечетного влияет на способ заполнения многоугольника.

Но для непересекающихся полигонов есть ли разница в производительности между правилами заполнения Winding или Even Odd. Я понимаю, что это будет специфично для внедрения, но какой из алгоритмов более эффективен для несложных многоугольников.

Последующий вопрос, какова сложность (т. Е. O (что?)) Каждого из этих алгоритмов. Я хочу знать, стоит ли избавляться от некоторых точек в многоугольнике (в основном, от дубликатов или от одной линии) для повышения производительности.

PS: Если это вообще имеет значение, я использую xlib

PPS: я могу подтвердить, что проблема не связана с аппаратным обеспечением, поскольку использование другой видеокарты не меняет производительность

Answer 1

Сегодня в большинстве реализаций X используется 2D-оборудование вашей видеокарты, поэтому разница между ними, вероятно, незначительна.

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

x11perf может помочь.

Вы можете найти алгоритм для аппаратно-независимой заливки полигонов здесь: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolygen.c?rev=HEAD

Существует вторая версия, которая намного быстрее, если вы уверены, что ваш многоугольник выпуклый: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolycon.c?rev=HEAD

Вторая версия игнорирует правило заполнения (которое не применяется к выпуклым полигонам). Комментарии об алгоритме: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipoly.h?rev=HEAD

Алгоритм работает следующим образом: он вычисляет контур, а затем создает объекты промежутка (которые являются просто координатами x, y и шириной) между краями. Если вы используете правило EvenOdd, при пересечении будет создано больше объектов span. Если их нет (например, когда многоугольник выпуклый), то вы не заметите разницы во время выполнения, потому что правило заполнения равно булевой переменной в главном цикле miFillPolygon (т.е. большая часть кода одинакова для обоих заполнить правила).

Попытка улучшить производительность за счет оптимизации контура многоугольника в общем случае не принесет вам большой пользы, за исключением случаев, когда вы знаете, что ваши многоугольники содержат очень большое количество ненужных точек (например, вы можете избавиться от половины числа очки в общем случае). Оптимизация полигона с <10 ​​баллами, вероятно, будет стоить больше, чем он достигает. </p>

Но опять же: все это основано на интуиции или знании старой статьи. Если вы хотите знать, не влияют ли ошибки в драйвере карты gfx на результат, вам нужно запачкать руки и написать тест, который измеряет, сколько времени занимает каждый случай. Невозможно определить время выполнения какого-либо сложного алгоритма, просто взглянув на него из-за внешних факторов: скорость процедур выделения памяти, объем свободной памяти (когда запускается замена), количество ядер ЦП, которые вы можете использовать, сколько другие процессы будут сражаться с вами за процессор, обрезку окончательного полигона на экране, детали реализации и оптимизации, ошибки и т. д.