Почему линейный алгоритм Брезенхэма эффективнее наивного алгоритма

Question

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

1. Если предположить, что оптимизация на уровне программного обеспечения не проводится, верно ли это для современного процессора с mmx и другими наборами команд?Как я уже видел в Intel-64-ia-32-architectures-optimisation-manual.pdf, и задержка для умножения сложения-вычитания такая же или лучше для float по сравнению с int для mmx.* Если алгоритм выполняется в GPU, должно ли это иметь значение?Как и при проверке Руководство по программированию NVIDIA CUDA 1.0 (pdf) , стр. 41, тактовые циклы для int и float одинаковы.

2. Что такое снижение эффективности приведения типа float к int?действительно ли проблема с загрузкой-хранилищем для нас реальная проблема?

3. Насколько эффективны функции, округляющие числа вверх / вниз?(мы можем думать о реализации в c ++ stl)

4. Эффективность, полученная от алгоритма Брезенхэма, благодаря добавлению вместо умножения, используемого во внутреннем цикле?

Answer 1

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

Что касается ваших конкретных вопросов:

1. Поскольку для доступа к памяти необходимо использовать регистры общего назначения, использование SSE или FPU для вычисления смещений памяти (указателей) все равно будет сопряжено с перегрузкой данных из этих регистров в регистры общего назначения. Таким образом, это зависит от того, превышают ли накладные расходы на передачу из одного набора регистров в другой производительность выполнения определенного набора команд.
2. У графических процессоров, как правило, установлен унифицированный регистр, поэтому это не должно иметь большого значения.
3. Бросание числа типа int само по себе не дорого. Издержки возникают из-за передачи данных из одного набора регистров в другой. Обычно это должно быть сделано через память, и если ваш процессор имеет штрафы за попадание в хранилище, этот перенос является их большим источником.
4. Производительность округления вверх или вниз зависит от процессора и компилятора. На медленном конце MSVC использовал функцию округления до нуля, которая отбрасывалась с помощью управляющего слова FPU. На быстром конце у вас есть специальные инструкции процессора, которые обрабатывают округление напрямую.
5. Алгоритм рисования линий Брезенхэма быстр, потому что он уменьшает определение, где рисовать точки на линии от простой формулы y= m*x + b до сложения плюс ветвь (и ветвь можно устранить с помощью хорошо известных целочисленных методов без ветвей). Версия алгоритма рисования линий с использованием фрагмента прогона может быть даже быстрее, поскольку она определяет «прогоны» пикселей с одним и тем же компонентом напрямую, а не итерацию.