Здравствуйте, Тёмчик, Вы писали:
CC>> результат получается с прорехами, когда итерацию делают не по dest а по src.
Тё>Логичный результат. Если из src считать dst- будут "прорехи", но если из dst считать src- будут "складки". Очевидно, можно проецирующую координату оставить в double без округления, и копировать субпиксельно, т.е. раскидывать на "пятно" из покрытых координатой пикселов. Либо если reverse- брать значение пиксела с покрытого пятна из нескольких пикселов, в пропорциях покрытия. Либо почитать про билинейную фильтрацию.
Для практического применения правильный подход это итерироваться по src, а в матрицу dst складывать не пиксели, а списки коржетей (цвет, процент заполнения пикселя). То бишь берём пиксель как квадратик из src, поворачиваем его на dst и смотрим на какие квадратики он ложится и процент того, сколько этого пикселя попало на какой пиксель. А после этого уже считаем конечный dst, смешивая цвета (и там формула сложней, чем просто сложить r g b).
А если делать ещё правильней, то, возможно, надо учитывать особенности матрицы у пользователя: монитор ведь не квадратики рисует, а каждый пиксель рисуется несколькими разноцветными прямоугольниками.
Здравствуйте, vsb, Вы писали:
vsb>Для практического применения правильный подход это итерироваться по src, а в матрицу dst складывать не пиксели, а списки коржетей (цвет, процент заполнения пикселя).
Идём по матрице dst, считаем проекцию на src, какие пикселы покрыла с какими пропорциями. Накрыла один 100%- копируем. Накрыла 3 с 20, 50, 30%- складываем по отдельности (r1 * 20 + r2 * 50 + r3 * 30) / 100 и записываем r в dst. Либо если прямая проекция- накидывать в dst на точки в пропорции от покрытия, (субпиксельно).
vsb> после этого уже считаем конечный dst, смешивая цвета (и там формула сложней, чем просто сложить r g b).
В смысле разбивать на яркость и цветность? Разве просто сложить цвета в пропорции не даст нужный результат?
vsb>А если делать ещё правильней, то, возможно, надо учитывать особенности матрицы у пользователя: монитор ведь не квадратики рисует, а каждый пиксель рисуется несколькими разноцветными прямоугольниками.
Да, но разве это не оверкил?
Здравствуйте, vsb, Вы писали:
Pzz>>Разворот, это ел кашу->ушак ле
vsb>ел кашу -> ле кашу -> ле ушак -> кашу ел
vsb>Получается два разворота, но сложность остаётся O(N).
Здравствуйте, Тёмчик, Вы писали:
Pzz>>Разворот, это ел кашу->ушак ле
Тё>А теперь ушак->кашу, ле-ел. Элегантно, коротко вместо извращения с сдвигами.
Но это не один разворот, а три. И в результате получается циклический сдвиг. Не в том смысле, что кто-то N раз сдвигает массив на один шаг, а в том, что результат эквиавалентен циклическому сдвигу.
Здравствуйте, Тёмчик, Вы писали:
vsb>>Для практического применения правильный подход это итерироваться по src, а в матрицу dst складывать не пиксели, а списки коржетей (цвет, процент заполнения пикселя). Тё>Идём по матрице dst, считаем проекцию на src, какие пикселы покрыла с какими пропорциями. Накрыла один 100%- копируем. Накрыла 3 с 20, 50, 30%- складываем по отдельности (r1 * 20 + r2 * 50 + r3 * 30) / 100 и записываем r в dst. Либо если прямая проекция- накидывать в dst на точки в пропорции от покрытия, (субпиксельно).
Ну да, так лучше.
vsb>> после этого уже считаем конечный dst, смешивая цвета (и там формула сложней, чем просто сложить r g b). Тё>В смысле разбивать на яркость и цветность? Разве просто сложить цвета в пропорции не даст нужный результат?
Насколько я знаю — с научной точки зрения нет.
vsb>>А если делать ещё правильней, то, возможно, надо учитывать особенности матрицы у пользователя: монитор ведь не квадратики рисует, а каждый пиксель рисуется несколькими разноцветными прямоугольниками. Тё>Да, но разве это не оверкил?
Не знаю (: У тех же шрифтов антиалиасинг это учитывает, значит для них не оверкил.
Здравствуйте, Тёмчик, Вы писали:
Тё>Формула с синусами-косинусами- это продукт матрица вращения на вектор. Матрица вращения- частный случай аффинной матрицы.
"Забъём гвоздь по шляпку, тем самым сведём задачу к предыдущей, которую мы знаем как решать" (С)
... << RSDN@Home 1.3.110 alpha 5 rev. 62>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Здравствуйте, vsb, Вы писали:
vsb>Не знаю (: У тех же шрифтов антиалиасинг это учитывает, значит для них не оверкил.
Ты хоть раз видел как у нормального шрифтового движка оно внутри устроено? Там нефиговая такая неонка, чтоб и читаемо получалось и быстро работало.
... << RSDN@Home 1.3.110 alpha 5 rev. 62>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Здравствуйте, Nuzhny, Вы писали:
N>С такими ответами, как "применить афинное преобразование" для поворота картинки ты пролетишь, как не умеющий размышлять, а лишь применять типовые решения.
Ровно наоборот. Матрица даст надёжный результат. Когда(если) хватит производительстности — можно углубиться в тему и оптимизировать, скажем, что бы были целочисленные операции.
Незачем струячить низкоуровневый код абы похвастаться знанием редкоиспользуемых вещей.
Здравствуйте, Nuzhny, Вы писали:
N>Я не готов изобретать велосипед, потому что никакого велосипеда тут нет. Никто в здравом уме не будет поворачивать картинку аффинным преобразованием. Если это надо делать быстро на CPU, то умножение матрицы (3х3) на вектор (3х1) будет слишком медленным, когда можно сделать в несколько раз быстрее (в целых числах в том числе). Если же на GPU, то float, но тоже не умножением матриц.
Слишком медленно это непонятно. Какие требования к производительсности и насколько критична эта разница в производительности и сколько там в процентах?
N>Призываю посчитать, сколько операций надо для поворота картинки, а сколько для аффинного преобразования: в аффинном случае у тебя для каждого пикселя будет 4 лишних умножения на 0, 3 лишних умножения на 1, 4 лишних операции сложения. Не оверкилл?
На такие вещи даёт ответ профайлер. Обсуждать "быстрее или нет" без внятных требований к производительность это по моему редкий зашквар.
Здравствуйте, Skorodum, Вы писали:
I>>А если микроконтроллер? S>Тогда надо добавить в исходные условия: "есть микроконтроллеи и JIT где операция умножения дорогая и не оптимизируется...". S>Иначе такие вопросы больше говорят о квалификации того, кто их задает.
Это ты почти что ответ сообщаешь. "есть микроконтроллер ХХХ, профайлер показывает, что педалит <вот этот код>. Как оформить максимально производительный вариант?"
Ответы могут быть самыми разными — от "подкрутить <этот компилер>", "взять <вот ну либу>" до "переписать <вот этот код> <вот таким способом>"
И если товарищ хотя бы идентифицировал проблему, это уже большой плюс. А если еще и решение нашел — вообще шикарно.
Собственно, я бы такое спрашивал если работа связана со вполне конкретными вещами да на горящую позицию. В других случах стоит переключиться на что другое.
Здравствуйте, IID, Вы писали:
Pzz>>А тебе как больше понравится, strstr в цикле, или алгоритм Морисса-Пратта на пальцах объяснить?
IID>мне больше скользящий (rolling) хеш нравится. Реализация тривиальная, а по скорости не особо уступает моррису-пратту.
Я хочу сказать, что и тому и другому не место, например, при чтении конфигурационного файла. Да, программа будет стартовать не три секунды, а аж на целых 5 миллисекунд больше. Но зато код будет понятным и чистым.
Здравствуйте, Ikemefula, Вы писали:
N>>С такими ответами, как "применить афинное преобразование" для поворота картинки ты пролетишь, как не умеющий размышлять, а лишь применять типовые решения.
I>Ровно наоборот. Матрица даст надёжный результат. Когда(если) хватит производительстности — можно углубиться в тему и оптимизировать, скажем, что бы были целочисленные операции.
Дак там формула с синусами-косинусами, это как раз продукт матрицы на вектор.
I>Незачем струячить низкоуровневый код абы похвастаться знанием редкоиспользуемых вещей.
Это не низкоуровневый код, а демонстрация недружбы с линейной алгеброй.
Здравствуйте, Тёмчик, Вы писали:
N>>>С такими ответами, как "применить афинное преобразование" для поворота картинки ты пролетишь, как не умеющий размышлять, а лишь применять типовые решения.
I>>Ровно наоборот. Матрица даст надёжный результат. Когда(если) хватит производительстности — можно углубиться в тему и оптимизировать, скажем, что бы были целочисленные операции.
Тё>Дак там формула с синусами-косинусами, это как раз продукт матрицы на вектор.
Именно что синусы да косинусы. Вопрос в цене оптимизации и спросе на неё. Раз в неделю — точно хватит матрицы, а если 100 раз в секунду конскую картинку поворачивать на фиксированый угол — это совсем другое.
I>>Незачем струячить низкоуровневый код абы похвастаться знанием редкоиспользуемых вещей. Тё>Это не низкоуровневый код, а демонстрация недружбы с линейной алгеброй.
Алгебра алгеброй, но если, для примера, 100% времени только и делаешь, что поворачиваешь картинки, то надо оптимизировать вусмерть. И тогда матричное умножение мягко говоря не лучший вариант.
Здравствуйте, Pzz, Вы писали:
Pzz>Но это не один разворот, а три. И в результате получается циклический сдвиг. Не в том смысле, что кто-то N раз сдвигает массив на один шаг, а в том, что результат эквиавалентен циклическому сдвигу.
2*O(N), элегантное решение за 5 минут. Или исписанная доска и нерабочее решение через 30 минут. Или нечитабельная портянка в функции на экран. Константой в большинстве случаев можно пренебречь.
Здравствуйте, Ikemefula, Вы писали:
Тё>>Это не низкоуровневый код, а демонстрация недружбы с линейной алгеброй.
I>Алгебра алгеброй, но если, для примера, 100% времени только и делаешь, что поворачиваешь картинки, то надо оптимизировать вусмерть. И тогда матричное умножение мягко говоря не лучший вариант.
Здравствуйте, Ikemefula, Вы писали:
I>На такие вещи даёт ответ профайлер. Обсуждать "быстрее или нет" без внятных требований к производительность это по моему редкий зашквар.
Мне не нужен профайлер, чтобы понять что десятки миллионов лишних операций на картинку — это плохо.
Но мы этот вопрос уже обсудили и выяснили, что была путаница в терминах. Так что проходи мимо, читай тред, а потом отвечай.
