Russian Qt Forum
Март 29, 2024, 15:07
Добро пожаловать,
Гость
. Пожалуйста,
войдите
или
зарегистрируйтесь
.
Вам не пришло
письмо с кодом активации?
1 час
1 день
1 неделя
1 месяц
Навсегда
Войти
Начало
Форум
WIKI (Вики)
FAQ
Помощь
Поиск
Войти
Регистрация
Russian Qt Forum
>
Forum
>
Программирование
>
Алгоритмы
>
Прогрессия
Страниц: [
1
]
Вниз
« предыдущая тема
следующая тема »
Печать
Автор
Тема: Прогрессия (Прочитано 6395 раз)
Авварон
Джедай : наставник для всех
Offline
Сообщений: 3257
Прогрессия
«
:
Май 19, 2018, 22:25 »
Возникла для самообразования задачка. Вот, допустим, у нас есть картинка, 13*13 пикселей с мипмапами (т.е. серия картинок 13*13, 6*6, 3*3, 1*1).
И хотим мы просуммировать, допустим, ширины - 13+6+3+1 = 23. Понятно, что можно сделать это циклом за O(levels), где levels - кол-во мипмапов (4 в данном примере).
А можно ли за линейное время?
Пффф, это же убывающая
геометрическая прогрессия
, подумал я. Для неё есть формула суммы - b1*(1 - q^n) / (1 - q).
Немного мат. преобразований и получаем такую формулу:
Код:
int sum(int width, int levels)
{
return 2 * width * ((1 << levels) - 1) / (1 << levels);
}
Но вот беда sum(13, 4) = 24, а не 23. И в самом деле, int(13+6.5+3.25+1.625) = int(24,375) = 24.
Внимание вопрос, а как же получить "неточную" (с учетом округлений) сумму?
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Прогрессия
«
Ответ #1 :
Май 20, 2018, 07:30 »
Цитата: Авварон от Май 19, 2018, 22:25
И хотим мы просуммировать, допустим, ширины - 13+6+3+1 = 23.
А что это за суммирование, в чем его смысл?
Записан
Авварон
Джедай : наставник для всех
Offline
Сообщений: 3257
Re: Прогрессия
«
Ответ #2 :
Май 20, 2018, 10:20 »
Хороший вопрос, изначально я хотел высчитать offset N-й мипмапы, т.е.
Код:
Σ(level) bytesPerImage(std::max(width >> level, 1), std::max<(height >> level, 1))
где bytesPerImage:
Код:
qsizetype bytesPerImage(w, h) { h * ((w * bitsPerPixel(format) + 31) >> 5) << 2}
width, height - максимальные размеры картинки
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Прогрессия
«
Ответ #3 :
Май 21, 2018, 08:46 »
Цитата: Авварон от Май 20, 2018, 10:20
изначально я хотел высчитать offset N-й мипмапы, т.е.
Все равно не дошло. Возможно Вы хотели просто посчитать масштаб(ы) чтобы переводить x,y пикселя из оригинальной текстуры в одну из уменьшенных MIP'ов. Ну степени двойки этот масштаб никак не равен и должен быть флоат. Но он не зависит от переводимого пикселя, просчитать (в цикле) один раз и кешировать.
Записан
qate
Супер
Offline
Сообщений: 1175
Re: Прогрессия
«
Ответ #4 :
Май 21, 2018, 10:08 »
А если хранить размеры картинок степени двойки сразу ?
Записан
Авварон
Джедай : наставник для всех
Offline
Сообщений: 3257
Re: Прогрессия
«
Ответ #5 :
Май 21, 2018, 13:21 »
Цитата: Igors от Май 21, 2018, 08:46
Цитата: Авварон от Май 20, 2018, 10:20
изначально я хотел высчитать offset N-й мипмапы, т.е.
Все равно не дошло. Возможно Вы хотели просто посчитать масштаб(ы) чтобы переводить x,y пикселя из оригинальной текстуры в одну из уменьшенных MIP'ов. Ну степени двойки этот масштаб никак не равен и должен быть флоат. Но он не зависит от переводимого пикселя, просчитать (в цикле) один раз и кешировать.
мне нужно что-то типа uchar *pos = data + mipmapOffset(level) + bytesPerLine(level) * y + x;
Ну да, пока просто просчитал в цикле и закешировал результаты.
Как я понимаю, хитрую формулу написать не получится (ведь оффсет - это уже не прогрессия, а комбинация арифм и геом прогрессий)?
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Прогрессия
«
Ответ #6 :
Май 22, 2018, 13:12 »
Цитата: Авварон от Май 21, 2018, 13:21
мне нужно что-то типа uchar *pos = data + mipmapOffset(level) + bytesPerLine(level) * y + x;
Если мы мапируемся в одну из MIP, то один пиксель (куда попали) не имеет смысла, нужны его коодинаты обязательно в флотах чтобы интерполировать значение с учетом соседних пыкселей (часто bilinear)
Записан
Авварон
Джедай : наставник для всех
Offline
Сообщений: 3257
Re: Прогрессия
«
Ответ #7 :
Май 22, 2018, 14:28 »
Цитата: Igors от Май 22, 2018, 13:12
Если мы мапируемся в одну из MIP, то один пиксель (куда попали) не имеет смысла, нужны его коодинаты обязательно в флотах чтобы интерполировать значение с учетом соседних пыкселей (часто bilinear)
Это всё очень интересно, но у меня файлики с текстурами, там нет флоатов и не надо ничо "ынтерполировать". Мипмапа либо есть (и ее "пыксели" целочисленны), либо её нет, и тут уже ОГЛ будет разбираться что и как интерполировать.
Так-то да, попиксельный доступ особо не нужен, но хочется иметь метод типа scanLine(int y) для того, чтобы ворочать не здоровенным куском данных, а хотя бы построчно.
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Прогрессия
«
Ответ #8 :
Май 22, 2018, 14:36 »
Цитата: Авварон от Май 22, 2018, 14:28
и тут уже ОГЛ будет разбираться что и как интерполировать.
Кстати он умеет сам создавать MIPы на ходу
Цитата: Авварон от Май 22, 2018, 14:28
Так-то да, попиксельный доступ особо не нужен, но хочется иметь метод типа scanLine(int y) для того, чтобы ворочать не здоровенным куском данных, а хотя бы построчно.
Не знаю чего Вы хотите добиться. В софтверных реализациях текстура обычно подгружается страницами, вытесняются обычным LRU. В любом случае нужно знать "область интереса" (интересующее место в MIP)
Записан
Авварон
Джедай : наставник для всех
Offline
Сообщений: 3257
Re: Прогрессия
«
Ответ #9 :
Май 22, 2018, 14:51 »
Цитата: Igors от Май 22, 2018, 14:36
Не знаю чего Вы хотите добиться. В софтверных реализациях текстура обычно подгружается страницами, вытесняются обычным LRU. В любом случае нужно знать "область интереса" (интересующее место в MIP)
Считать текстуру из файлика. Понятно, что можно сделать типа memcpy(file.readAll().data(), buffer, file.size()) (за вычетом хедера), но хочется читать мипмапы построчно, а не загружать весь файл в память.
Записан
Авварон
Джедай : наставник для всех
Offline
Сообщений: 3257
Re: Прогрессия
«
Ответ #10 :
Май 22, 2018, 15:09 »
Да даже ладно, фиг с ним с построчным доступом, всё равно надо посчитать оффсет мипмапы, чтобы знать, куда грузить кусок данных
Записан
Страниц: [
1
]
Вверх
Печать
« предыдущая тема
следующая тема »
Перейти в:
Пожалуйста, выберите назначение:
-----------------------------
Qt
-----------------------------
=> Вопросы новичков
=> Уроки и статьи
=> Установка, сборка, отладка, тестирование
=> Общие вопросы
=> Пользовательский интерфейс (GUI)
=> Qt Quick
=> Model-View (MV)
=> Базы данных
=> Работа с сетью
=> Многопоточное программирование, процессы
=> Мультимедиа
=> 2D и 3D графика
=> OpenGL
=> Печать
=> Интернационализация, локализация
=> QSS
=> XML
=> Qt Script, QtWebKit
=> ActiveX
=> Qt Embedded
=> Дополнительные компоненты
=> Кладовая готовых решений
=> Вклад сообщества в Qt
=> Qt-инструментарий
-----------------------------
Программирование
-----------------------------
=> Общий
=> С/C++
=> Python
=> Алгоритмы
=> Базы данных
=> Разработка игр
-----------------------------
Компиляторы и платформы
-----------------------------
=> Linux
=> Windows
=> Mac OS X
=> Компиляторы
===> Visual C++
-----------------------------
Разное
-----------------------------
=> Новости
===> Новости Qt сообщества
===> Новости IT сферы
=> Говорилка
=> Юмор
=> Объявления
Загружается...