Быстрое преобразование векторного изображения.

tengiz · Post by **tengiz** » 27 Dec 2001 23:35

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

Наивный алгоритм отрисовки прямой (y = a*x + b), например, заключающийся в том при a < 1 для каждого x в растре тупо вычислялся у, можно немного улучшить заменой вычислений с плавающей точкой целочисленным умножением, возможно, сдвигом и сложением. Однако, существует намного лучший способ, в котором используется пара сложений и одно сравнение на каждую точку растра, плюс ещё некоторые вычисления при инициализации цикла. Есть алгоритм отрисовки дуг окружностей и эллипсов, базирующийся на тех же принципах. Я не стану приводить подробности, чтобы не портить кайф тем, кто этого никогда не проделывал – до отрисовки прямых линий совсем несложно додуматься.

Если речь идёт именно об этом, то такие алгоритмы были придуманы ещё в 70 годы и есть в учебниках по компьютерной графике.

MaxSt · Post by **MaxSt** » 28 Dec 2001 00:09

<blockquote>quote:<hr>Originally posted by tengiz:
Vlad7, Вы возможно имеете в виду то, что называется быстрыми алгоритмами отрисовки графических примитивов.
...
Есть алгоритм отрисовки дуг окружностей и эллипсов, базирующийся на тех же принципах.<hr></blockquote>

Я думаю, он не об этом.
Обратите внимание на эту фразу:

<blockquote>quote:<hr>Originally posted by Vlad7:
Мне кажется, что Вы перепутали уже решенную к тому времени задачу целочисленных преобразований векторных объектов типа прямая, окружность, эллипс в растровую форму с масштабирование координат объекта.<hr></blockquote>

MaxSt.

Vlad7 · Post by **Vlad7** » 28 Dec 2001 00:38

<blockquote>quote:<hr>Originally posted by Kisena:
Нет, мы не посещали выставки в то время. Нам было еще очень мало лет. Нельзя ли впрочем вместо уверений, что программы существуют, глянуть хотя бы на одну?<hr></blockquote>

Я недавно питался запустить досовский вариант программы, сразу возникло несколько проблем – нужно в SIMOS установить старый адрес начала видеобуфера, при записи в видеорегистры происходят сбои, возможно, из-за использования недокументированных функций, а возможно потому, что используются две видеокарты. Будет время – поищу вариант программы, работающий под VGA. Он должен быть поустойчивей.

Сам я выдел относительно недавно (два или три года назад) многооконную графическую программу, работающую под DOS’ом - CADDy NT4.0. В этой программе внешний вид напоминает полностью Windows, но работает она под DOS. Взгляните на сайт компании – может еще остались следы программы.

Vlad7 · Post by **Vlad7** » 28 Dec 2001 01:00

<blockquote>quote:<hr>Originally posted by MaxSt:

Например, я могу сказать - а давайте все координаты точек этого изображения кранить как фиксированную точку. И еще я могу сказать - 8 бит хватит. Отсюда - элементарно следует, как можно заменить каждое умножение 8-ю сложениями. Ну чем не решение?

Только не знаю я, не заругается ли заказчик на 8 бит точности...

Получается - ты нам найди оптимум функции, но в каких пределах (область определения этой функции) мы тебе пока говорить не будем, а то слишком просто решить будет.
MaxSt.
<hr></blockquote>

Почему 8 бит? Размер экрана 1024*1280. А для 1280 восьми бит недостаточно. Да и восемь сложений – это много.

Диапазон значений координат в векторном файле от 0 до 820. Точность - два знака после запятой. Растровый файл должен отображаться с точностью до 1 пикселя. Наверное все.

Vlad7 · Post by **Vlad7** » 28 Dec 2001 01:02

<blockquote>quote:<hr>Originally posted by tengiz:
Vlad7, Вы возможно имеете в виду то, что называется быстрыми алгоритмами отрисовки графических примитивов. В те времена, когда операции целочисленного сложения и умножения по времени выполнения отличались на порядок, а операции с плавающей точкой были либо эмулировались (ещё порядок) или просто в разы были медленнее целочисленной арифметики, родился целый класс алгоритмов, учитывавших эту особенность аппаратуры.
Наивный алгоритм отрисовки прямой (y = a*x + b), например, заключающийся в том при a < 1 для каждого x в растре тупо вычислялся у, можно немного улучшить заменой вычислений с плавающей точкой целочисленным умножением, возможно, сдвигом и сложением. Однако, существует намного лучший способ, в котором используется пара сложений и одно сравнение на каждую точку растра, плюс ещё некоторые вычисления при инициализации цикла. Есть алгоритм отрисовки дуг окружностей и эллипсов, базирующийся на тех же принципах. Я не стану приводить подробности, чтобы не портить кайф тем, кто этого никогда не проделывал – до отрисовки прямых линий совсем несложно додуматься.

Если речь идёт именно об этом, то такие алгоритмы были придуманы ещё в 70 годы и есть в учебниках по компьютерной графике.<hr></blockquote>

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

Kisena · Post by **Kisena** » 28 Dec 2001 01:12

<blockquote>quote:<hr>Originally posted by Vlad7:


Я недавно питался запустить досовский вариант программы, сразу возникло несколько проблем – нужно в SIMOS установить старый адрес начала видеобуфера, при записи в видеорегистры происходят сбои, возможно, из-за использования недокументированных функций, а возможно потому, что используются две видеокарты. Будет время – поищу вариант программы, работающий под VGA. Он должен быть поустойчивей.

Сам я выдел относительно недавно (два или три года назад) многооконную графическую программу, работающую под DOS’ом - CADDy NT4.0. В этой программе внешний вид напоминает полностью Windows, но работает она под DOS. Взгляните на сайт компании – может еще остались следы программы.<hr></blockquote>

Правильно ли мы поняли, что на сегодняшний день не существует ни одной Вашей работающей программы?

dimach · Post by **dimach** » 28 Dec 2001 01:23

<blockquote>quote:<hr>Originally posted by Vlad7:


Взгляните на сайт компании – может еще остались следы программы.<hr></blockquote>

нету [img:806712013d]images/smiles/icon_sad.gif[/img:806712013d]

точнее, оно не runs

[ 27-12-2001: Message edited by: dimach ]

Andy77 · Post by **Andy77** » 28 Dec 2001 02:43

<blockquote>quote:<hr>Originally posted by Vlad7:
Диапазон значений координат в векторном файле от 0 до 820. Точность - два знака после запятой. Растровый файл должен отображаться с точностью до 1 пикселя. Наверное все.<hr></blockquote>

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

Извините, Влад, что занудствую, но Вы мне так и не ответили, как это получается - "Я пробовал писать сообщение под курсором, но немного не хватало скорости моей PS/2-16Мгц"? Признайтесь, что для красного словца ввернули, и я отстану [img:282b4fa779]images/smiles/icon_smile.gif[/img:282b4fa779]

Vlad7 · Post by **Vlad7** » 28 Dec 2001 09:15

<blockquote>quote:<hr>Originally posted by Kisena:
Влад7:
Киньте, пожалуйста, ссылку на дистрибутив Вашей оконной системы.<hr></blockquote>

Программа для быстрого просмотра чертежных файлов QuickView с многооконным пользовательским интерфейсом под DOS выставлялась почти на всех компьютерных выставках в Москве в 1989-1991 годах. Если Вы в это время посещали выставки, то наверняка ее видели.

Продажу программы QuickView мы закончили продавать лет семь назад. Резко увеличилась скорость вычислений, и чертежи можно было просматривать в системе AutoCAD за приемлемое время. Да и проблемы совместимости с новыми видеокартами стали возникать чаще. Необходимость отпала в нашей программе. Также как и необходимость в многооконной оболочке для DOS. Кое что пришлось использовать и в новых программах под Windows, но при нынешней производительности компьютеров это не производит впечатление (1.6Ггц против 16Мгц).

Vlad7 · Post by **Vlad7** » 28 Dec 2001 09:17

<blockquote>quote:<hr>Originally posted by Andy77:


Ой, вспомнил, я, учась в лицее в 10-м или 11-м классе, тоже написал "многооконную систему" [img:42399b1f2b]images/smiles/icon_smile.gif[/img:42399b1f2b] Файловые диалоги, кнопочки, иконки, всё как у вас [img:42399b1f2b]images/smiles/icon_smile.gif[/img:42399b1f2b] Даже сообщение под курсором писал, странно, точно такая же машина была, но почему-то скорости хватало (расскажите, кстати, как это может не хватать на это скорости?) [img:42399b1f2b]images/smiles/icon_smile.gif[/img:42399b1f2b] Прощелкал я своё счастье, надо было на Microsoft в суд подавать когда Win95 вышла [img:42399b1f2b]images/smiles/icon_smile.gif[/img:42399b1f2b]

А еще я написал движок, почти такой [img:42399b1f2b]images/smiles/icon_smile.gif[/img:42399b1f2b] как в DOOMе, только работал раз в 10 быстрее [img:42399b1f2b]images/smiles/icon_smile.gif[/img:42399b1f2b] может, это из-за того, что в DOOMе уровни понавороченнее были?<hr></blockquote>

НЕОРИГИНАЛЬНО.

GGH · Post by **GGH** » 28 Dec 2001 09:41

To Vlad7:

Что же Вы агрессивно-то так? Я не хотел Вас обидеть или в чем-то усомниться. Просто большинство Ваших историй как-то все о том, что Вам не везло с внедрением. А теперь заобижались чего-то. Видимо, все же случай клинический. Увы...
Ничего я Вам не говорил, и вообще меня здесь не было.

Vlad7 · Post by **Vlad7** » 28 Dec 2001 22:42

<blockquote>quote:<hr>Originally posted by Andy77:


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

Извините, Влад, что занудствую, но Вы мне так и не ответили, как это получается - "Я пробовал писать сообщение под курсором, но немного не хватало скорости моей PS/2-16Мгц"? Признайтесь, что для красного словца ввернули, и я отстану [img:15141e1077]images/smiles/icon_smile.gif[/img:15141e1077] <hr></blockquote>

Целочисленное умножение выполняется быстрее, чем с плавающей запятой, но умножение целых чисел намного медленнее их сложения, так как умножение состоит (состояло) из нескольких операций сложений и сдвигов. Такое решение задачи я бы счел очевидным и пригодным разве что для проверки знаний студентов. Мое решение задачи как раз состояло в том, что на преобразование одной координаты среднее число команд было небольшим, операция умножения почти не применялась, а преобразование было быстрее, чем целочисленное преобразование плюс сдвиг.

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

Drom · Post by **Drom** » 29 Dec 2001 00:21

<blockquote>quote:<hr>Originally posted by Vlad7:
... Мое решение задачи как раз состояло в том, что на преобразование одной координаты среднее число команд было небольшим, операция умножения почти не применялась, а преобразование было быстрее, чем целочисленное преобразование плюс сдвиг...<hr></blockquote>

lookup tables?

tengiz · Post by **tengiz** » 29 Dec 2001 05:11

<blockquote>quote:<hr>Originally posted by Vlad7:
...Мое решение задачи как раз состояло в том, что на преобразование одной координаты среднее число команд было небольшим, операция умножения почти не применялась, а преобразование было быстрее, чем целочисленное преобразование плюс сдвиг...<hr></blockquote>Как уже сказал Drom, можно использовать разновидность lookup алгоритма: для каждой оси держим небольшой кеш интервалов значений исходных координат, которые при масштабировании точно попадают в один пиксел. Нужно только аккуратно следить за тем, чтобы кеш был достаточно компактным и чтобы на его поддержание и на поиск в нём уходило в итоге меньше времени, чем на прямой алгоритм с умножениями. Хотя, если не жалко пары сотен килобайт (это всё-таки был DOS), то тогда вообще можно было сделать массив, индексом в котором могли бы быть исходные координаты, а значениями экранные координаты, и который заполнялся бы по мере необходимости.

Drom · Post by **Drom** » 29 Dec 2001 05:50

<blockquote>quote:<hr>Originally posted by tengiz:
Как уже сказал Drom, можно использовать разновидность lookup алгоритма: для каждой оси держим небольшой кеш интервалов значений исходных координат, которые при масштабировании точно попадают в один пиксел. ... и на поиск в нём уходило в итоге меньше времени, чем на прямой алгоритм с умножениями. Хотя, если не жалко пары сотен килобайт ... сделать массив, индексом в котором могли бы быть исходные координаты, а значениями экранные координаты, и который заполнялся бы по мере необходимости.<hr></blockquote>

oops [img:ef18667f93]images/smiles/icon_wink.gif[/img:ef18667f93] , Tengiz, hash (or cash?) идея приятная, но если надо умножать (на константу или произвольные числа), то я имел в виду именно массив, что-то типа примитивной таблицы Пифагора:
для умножения произвольных байт будет 256х256 слов = 128kb, ту же таблицу можно использовать для умножения слов (4 lookup'а, 3 сложения, 2 сдвига). Умножение на константу (маштабирование) потребует только полкилобайта под таблицу - можно будет сделать 2 таблицы сразу, чтобы с"економить на сдвигах (2 lookup'а, 1 сложениe,), ну и т.д.