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

Vlad7 · Post by **Vlad7** » 26 Dec 2001 22:29

В конце 80х - начале 90х очень остро стояла проблема быстрого преобразования векторного изображения в растровое с произвольным коэффициентом масштабирования. Суть проблемы заключалась в том, что каждую координату при масштабировании необходимо было умножать на число с плавающей запятой, а операция умножения выполнялась на процессорах того времени в несколько раз медленнее, чем простые операции сложения, сдвига, обращения в память и т.д. Большинство разработчиков ПО по этой причине при выводе изображения использовали только масштаб, кратный 2. Это хотя и создавало неудобства пользователю, но обеспечивало быстрый вывод. Или использовали медленный вывод изображения при произвольном коэффициенте умножения.

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

Попробуйте решить эту задачу и Вы.

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

MaxSt · Post by **MaxSt** » 27 Dec 2001 00:47

<blockquote>quote:<hr>Originally posted by Vlad7:
Попробуйте решить эту задачу и Вы.
<hr></blockquote>

Может для начала стоит ее [b:a083942e45]сформулировать[/b:a083942e45]? [img:a083942e45]images/smiles/icon_smile.gif[/img:a083942e45]

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

Уверен, это не то, что вы имели в виду.

MaxSt.

Andy77 · Post by **Andy77** » 27 Dec 2001 01:38

Я думаю, что Vlad7 признает чьё-то решение решением только после того, как кандидат предоставит работающую программу, выполняющую отрисовку в 600 раз быстрее чем AutoCad [img:d91ef492ce]images/smiles/icon_biggrin.gif[/img:d91ef492ce]

(навеяно соседним топиком "про верёвку"... извините за такой переход на личность, не смог упустить возможности постебаться [img:d91ef492ce]images/smiles/icon_smile.gif[/img:d91ef492ce] )

Vlad7 · Post by **Vlad7** » 27 Dec 2001 10:28

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


Vlad7, будьте любезны, формализуйте задачу?
Что на что умножается?
Fixed-point to floating-point?
Floating-point to floating-point?
Fixed-point to fixed-point?

Типы данных? Более четкая постановка задачи?

<hr></blockquote>

Пока составлял ответ, пришло Ваше новое сообщение.

В конце 80х загрузка чертежа средней сложности в AutoCAD занимала несколько минут, а сборочные иногда грузились и по полчаса.

Мне необходимо было обеспечить быстрый вывод больших машиностроительных чертежей на экран дисплея. Причем должен быть скроллинг и зуммирование с произвольным коэффициентом. Так основная операция, которая тормозила вывод – это умножение floating-point to floating-point. Я писал свои программы на ассемблере. MS Windows не использовал – очень медленно было. Использовал VESA, запись напрямую в порты. Использовал свою многооконную графическую оболочку а ля Windows, свой файловый эксплорер. Т.е. это был Windows, но без Microsoft. Несколько позже я пытался договориться о разработке OC с графическим интерфейсом с ф. Физтехсофт, но переговоры не получились. Самое интересное, что некоторые найденные мною решения отсутствовали в последней на то время версии Windows3.0 и аналогичные решения появились только в Windows95. Один из таких приемов – когда курсор оказывался над иконкой или пунктом меню, в статусной строке появлялась подробная информация об элементе управления. Я пробовал писать сообщение под курсором, но немного не хватало скорости моей PS/2-16Мгц.

Иногда доходило до анекдотичных случаев. Из-за ошибок в hardware видеорегистры не успевали переключится, и рисования изображения продолжалось прежним цветом. Никакого сигнала, подтверждающего выполнения операции переключения не было, по видимому предполагалось, что видеорегистр успеет переключиться до следующего обращения к видеоконтроллеру. По шагам проходишь – переключается. Приходилось пустые команды вводить для задержки.

GGH · Post by **GGH** » 27 Dec 2001 16:46

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

Kisena · Post by **Kisena** » 27 Dec 2001 18:39

Влад7:

Киньте, пожалуйста, ссылку на дистрибутив Вашей оконной системы.

Vlad7 · Post by **Vlad7** » 27 Dec 2001 20:20

<blockquote>quote:<hr>Originally posted by GGH:
To Vlad7:
А вот про векторно-растровое преобразование не надо! Я этим занимался именно в те самые годы, и, в отличие от Вас, весьма успешно.<hr></blockquote>

Не могли бы Вы ответить, почему Вы так считаете? У Вас имеется точный подсчет проданного мной копий ПО, у Вас имеется доступ к моим финансовым документам?

Если Вы знаток по преобразованиям векторного изображения в растровое, то не могли бы Вы ответить, почему в AutoCAD R.9 (R10, R11) чертежи загружались по несколько минут, а у меня за 1 сек?

Решение задачи занимает около 20 строк на ассемблере. Если Вы профи, то написать, как обойтись без умножения для Вас очень легко. ЖДУ несколько строчек описания.

Не могли бы Вы любезнейший убрать свой сарказм? У меня есть программы, которые обеспечивают заявляемые характеристики. Моя программа быстрого вывода изображения работала в 600 раз быстрее, чем аналогичная у AutoDesk’a. Если кто сумел сделать подобное раньше меня, значит не судьба быть первым. Но это не повод для оскорблений.

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

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

Andy77 · Post by **Andy77** » 27 Dec 2001 20:24

<blockquote>quote:<hr>Originally posted by Vlad7:
Самое интересное, что некоторые найденные мною решения отсутствовали в последней на то время версии Windows3.0 и аналогичные решения появились только в Windows95. Один из таких приемов – когда курсор оказывался над иконкой или пунктом меню, в статусной строке появлялась подробная информация об элементе управления. Я пробовал писать сообщение под курсором, но немного не хватало скорости моей PS/2-16Мгц.<hr></blockquote>

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

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

SuperMax · Post by **SuperMax** » 27 Dec 2001 21:05

<blockquote>quote:<hr>Originally posted by Vlad7:
В конце 80х - начале 90х очень остро стояла проблема быстрого преобразования векторного изображения в растровое с произвольным коэффициентом масштабирования. Суть проблемы заключалась в том, что каждую координату при масштабировании необходимо было умножать на число с плавающей запятой, а операция умножения выполнялась на процессорах того времени в несколько раз медленнее, чем простые операции сложения, сдвига, обращения в память и т.д. Большинство разработчиков ПО по этой причине при выводе изображения использовали только масштаб, кратный 2. Это хотя и создавало неудобства пользователю, но обеспечивало быстрый вывод. Или использовали медленный вывод изображения при произвольном коэффициенте умножения.

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

Попробуйте решить эту задачу и Вы.

В качестве исходных условия можно принять количество тактов, необходимых для выполнения операции умножения, равным 33, а количество тактов, затрачиваемое для выполнения простых операций (сложения, сдвига, обращения в память и т.д) равным 2, что близко к реальным соотношениям для процессоров того времени<hr></blockquote>

Vlad7, будьте любезны, формализуйте задачу?
Что на что умножается?
Fixed-point to floating-point?
Floating-point to floating-point?
Fixed-point to fixed-point?

Типы данных? Более четкая постановка задачи?

(Мне когда-то приходилось решать задачу вывода изображения звукового сигнала ("сигналограмма"), на 286-х компах, которое должно было скроллиться без разрывов... использовать можно было только 16-битный WinAPI того времени под Windows 3.0. Я использовал арифметику рациональных чисел... Много пришлось писать на ассемблере...

Или была задача приближенного логарифмирования в целых числах для вывода VU-метра (столбик с уровнем сигнала). Мне интересно... )

Vlad7 · Post by **Vlad7** » 27 Dec 2001 21:37

<blockquote>quote:<hr>Originally posted by Andy77:
Я думаю, что Vlad7 признает чьё-то решение решением только после того, как кандидат предоставит работающую программу, выполняющую отрисовку в 600 раз быстрее чем AutoCad [img:3aff5f970e]images/smiles/icon_biggrin.gif[/img:3aff5f970e]

(навеяно соседним топиком "про верёвку"... извините за такой переход на личность, не смог упустить возможности постебаться [img:3aff5f970e]images/smiles/icon_smile.gif[/img:3aff5f970e] )<hr></blockquote>

В программе для быстрой отрисовки изображения использовался данный алгоритм. Но он давал увеличение скорости примерно в три раза. Оставшийся прирост скорости приходился на другие know how. В качестве примера свои программы я привожу только для того, чтобы показать, что решение существует, и существуют варианты его использования.

Vlad7 · Post by **Vlad7** » 27 Dec 2001 21:38

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


Может для начала стоит ее [b:7436d712f7]сформулировать[/b:7436d712f7]? [img:7436d712f7]images/smiles/icon_smile.gif[/img:7436d712f7]

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

Уверен, это не то, что вы имели в виду.

MaxSt.<hr></blockquote>

Существует некоторая проблема при формулировке задачи. Если я дам ее точную формулировку, то будет понятен способ ее решения. Поэтому приведу формулировку задачи в том виде, в котором мне предстояло решить. Данная формулировка не совсем строгая, но зато реалистичная.

УСЛОВИЕ ЗАДАЧИ:
Скорость преобразования векторного изображения в растровое при произвольном масштабировании сильно тормозится из-за того, что необходимо каждую координату умножать на коэффициент масштабирования, а операция умножения является очень медленной операцией по сравнению с простыми операциями типа сложения, сдвига, обращения к памяти и т.д. Необходимо было скорость преобразования с произвольным масштабом приблизить к скорости преобразования с коэффициентов масштабирования кратным 2. Время выполнения операций умножения (деления, возведения в степень) составляла более 33 тактов. Время выполнения простых операций (сложение, сдвиг, обращение в память и т.д.) была на порядок меньше. Hardware acceleration нельзя было использовать из-за дороговизны.

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

Kisena · Post by **Kisena** » 27 Dec 2001 23:07

Нет, мы не посещали выставки в то время. Нам было еще очень мало лет. Нельзя ли впрочем вместо уверений, что программы существуют, глянуть хотя бы на одну?

Andy77 · Post by **Andy77** » 27 Dec 2001 23:15

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


НЕОРИГИНАЛЬНО.<hr></blockquote>

зато правда [img:c3da6c0d03]images/smiles/icon_smile.gif[/img:c3da6c0d03]

Я прошу прощения за свой тон, но, серьёзно, Влад - что значит "Я пробовал писать сообщение под курсором, но немного не хватало скорости моей PS/2-16Мгц"???

MaxSt · Post by **MaxSt** » 27 Dec 2001 23:31

<blockquote>quote:<hr>Originally posted by Vlad7:
Если я дам ее точную формулировку, то будет понятен способ ее решения.<hr></blockquote>

Ну я так не играю... Видать задачка-то попроще теоремы Ферма, раз из формулировки уже все ясно. [img:65582eebe2]images/smiles/icon_smile.gif[/img:65582eebe2]

Ну да ладно. Очевидно, что хитрость тут - в чем то задачку упростить, пренебречь какими-то ошибками округления... Это мы все уиеем, проблема в том что не совсем ясно, какое упрощение считать дозволенным и приемлемым, а какое - нет.

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

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

Получается - ты нам найди оптимум функции, но в каких пределах (область определения этой функции) мы тебе пока говорить не будем, а то слишком просто решить будет.
Нет, так нечестно и так я не играю. [img:65582eebe2]images/smiles/icon_smile.gif[/img:65582eebe2]

MaxSt.

P.S. Хотите прогу покажу в 39 байт - синусоиду рисует на экране? [img:65582eebe2]images/smiles/icon_smile.gif[/img:65582eebe2]

Vlad7 · Post by **Vlad7** » 27 Dec 2001 23:33

<blockquote>quote:<hr>Originally posted by GGH:
To Vlad7:
Что же Вы агрессивно-то так? Я не хотел Вас обидеть или в чем-то усомниться. Просто большинство Ваших историй как-то все о том, что Вам не везло с внедрением. А теперь заобижались чего-то. Видимо, все же случай клинический. Увы...
Ничего я Вам не говорил, и вообще меня здесь не было.<hr></blockquote>

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