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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 30.07.2007, 12:04
Аватар для Shveya
Новичок

Отправить личное сообщение для Shveya Посмотреть профиль Найти все сообщения от Shveya
 
Регистрация: 30.07.2007
Адрес: г. Зеленоград
Сообщений: 3

Супер быстрый поворот изображения
Прошу помощи на форуме!
Я обыскал весь Интернет и не смог найти ни одного быстрого алгоритма поворота растра (на Дельфи). Так вот я посидел и подумал, что можно сделать самому. Пришла в голову такая мысль:
Очень быстрый поворот растра (на Дельфи), в котором применяется лишь два Синуса \ косинуса + пара умножений.

Смысл такой: создаем структуру, в которой описаны координаты четырех углов прямоугольника. Поворачиваем этот прямоугольник на произвольный угол (можно обойтись одним синусом, но у меня пока 2), потом запускаем процедуру рисования линии от левого верхнего до левого нижнего угла структуры, где вместо подстановки точки в позиции x,y, запускаем процедуру с входными параметрами x,y. В этой процедуре мы математически находим точку на правой стороне прямоугольника, соответствующую входной на левой и запускаем процедуру рисования линии через эти точки. Причем процедурой постановки точки для этой линии будет процедура, считывающая цвет из входного изображения и переносящая его на выходное в соответствующие координаты.

Все это, можно сказать, работает, но рисование линии по методу Брезенхэма не подходит для переноса всех точек исходного изображения на новое: количество поставленных им точек на линии может кардинально не совпадать с шириной \ высотой изображения. Так вот, может поможете что-нибудь такое придумать с Брезенхэмом или с моим алгоритмом в общем, чтобы на выходном изображении появлялись все точки без пропусков?
Мой алгоритм вместе с тестом: http://www.ZVjnia1.narod.ru/FastRotate.zip

Последний раз редактировалось Shveya, 30.07.2007 в 12:06.
  #2  
Старый 30.07.2007, 13:41
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

http://kladovka.net.ru/delphibase/?a...iaimg&id=10186
  #3  
Старый 30.07.2007, 16:05
Аватар для Shveya
Новичок

Отправить личное сообщение для Shveya Посмотреть профиль Найти все сообщения от Shveya
 
Регистрация: 30.07.2007
Адрес: г. Зеленоград
Сообщений: 3

Да в этой ссылке куча умножений! и смысл тот же что с синусами. Я же предлагаю нечто новое...
  #4  
Старый 30.07.2007, 22:56
Аватар для CD_Eater
Пользователь

Отправить личное сообщение для CD_Eater Посмотреть профиль Найти все сообщения от CD_Eater
 
Регистрация: 21.09.2006
Адрес: Москва
Сообщений: 91

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

Правда, вылезут всякие "лесенки" без антиалиасинга. Ну, собственно, не зря же народ издавна пытался перенести эти расчёты из софта в железо. Но если ускоритель использовать нельзя, то для быстрого вращения картинки пойдёт и так.
  #5  
Старый 31.07.2007, 07:48
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>Я же предлагаю нечто новое
Такие методы известны, однако всегда полезно самому додуматься.

Я писал когда-то поворот без антиалиасинга почти без арифметики во внутреннем цикле (только пара сдвигов shr и инкрементация адреса).
Собственно говоря, на современных процессорах арифметика очень быстрая, и лимитирует уже скорость обращения к памяти (по приемнику идем хорошо, построчно-последовательно, а вот по источнику - прыгаем по разным адресам, что ухудшает скорость, и prefetch-инг радикально не спасет)
  #6  
Старый 31.07.2007, 13:26
Аватар для Shveya
Новичок

Отправить личное сообщение для Shveya Посмотреть профиль Найти все сообщения от Shveya
 
Регистрация: 30.07.2007
Адрес: г. Зеленоград
Сообщений: 3

Ок, гут. А есть ли возможность хардварного поворота в DirectDraw? Или, если запикаете, то как в DirectX сделать спрайтовую анимацию?
  #7  
Старый 08.08.2007, 18:12
Аватар для CD_Eater
Пользователь

Отправить личное сообщение для CD_Eater Посмотреть профиль Найти все сообщения от CD_Eater
 
Регистрация: 21.09.2006
Адрес: Москва
Сообщений: 91

Сообщение от MBo
Собственно говоря, на современных процессорах арифметика очень быстрая, и лимитирует уже скорость обращения к памяти (по приемнику идем хорошо, построчно-последовательно, а вот по источнику - прыгаем по разным адресам, что ухудшает скорость, и prefetch-инг радикально не спасет)
Можно обрабатывать не одну строку. а несколько (например, 8) параллельных строк. Тогда их наклонные пути по источнику будут идти рядом друг с другом и хорошо друг друга кэшировать.
  #8  
Старый 12.09.2007, 16:40
Новичок

Отправить личное сообщение для U235 Посмотреть профиль Найти все сообщения от U235
 
Регистрация: 12.09.2007
Сообщений: 6

Один из быстрых методов поворота изображения - через три последовательных сдвига.
  #9  
Старый 13.09.2007, 02:39
Аватар для CD_Eater
Пользователь

Отправить личное сообщение для CD_Eater Посмотреть профиль Найти все сообщения от CD_Eater
 
Регистрация: 21.09.2006
Адрес: Москва
Сообщений: 91

U235, расскажите, интересно. Как это?
  #10  
Старый 13.09.2007, 15:07
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

CD_Eater,
В книге Graphics Gems vol 1, есть статья Paeth "A Fast algorithm for general raster rotation"
суть (разложение матрицы вращения на произведение трех матриц shear) есть, например, здесь:
http://www.gamedev.net/reference/art...article811.asp
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
вопрос по обработке изображения в матлабе Wind Of Change Обработка изображений, звук, графика 0 13.04.2007 22:09
вопрос по обработке изображения tumanovalex Обработка изображений, звук, графика 0 10.04.2007 13:32
необходим быстрый алгоритм Spets Математические алгоритмы 0 31.01.2007 20:39
масштабирование изображения Africa Оффтопик 2 28.10.2006 16:15