amarao_san

Category:

скорость

Собственно, возвращаемся к нашим попугаям (т.е. рисованию уравнений).

Итог: 25 fps на нормальном разрешении экрана, при размере окна снизу — честные 59 fps.

It's a sine! It's insane!
It's a sine! It's insane!

Скорость довольно грубого брутфорса (4 опорные точки для поиска смены знака или нуля) в 4 треда дают по ~5.5 Mpxps (т.е. около 22 Mpxps на всех). Понятно, что фактическая скорость будет сильно меньше, как только у меня там окажется больше одного синуса, да и «поиск корней» — та ещё штука. Из бонусов по сравнению со старой версией, поддержка ресайза (с некоторыми артефактами), поддержка тредов, готовность это всё выгружать в картинку, рендеринг в реальном времени (т.е. если функция будет медленной, то рисоваться будет по чуть-чуть, но если затупит, то что-то рисоваться всё-таки будет no matter what). Ещё есть полная готовность обрабатывать нажатия кнопок.

Ключевое изменение: float point window фиксирован при запуске программы, а вот его scale в пикселы динамический. Меняется разрешение окна — меняется размер «фиксела» (т.е. размер в float'е, который описывает размер пиксела).

Дальнейшее todo:

1) Кеширование найденных корней.
2) Ресайз float area (для поиска интересного в интерактивном режиме)
3) усиленный поиск корней в районе курсора мыши (чтобы не делать гигантский поиск всех корней ради подозрительных 30 пикселей).

Теоретическая проблема — это ресайз при наличии кеша. Предположим, у вас дана область [-1;1] — [1;1]. Допустим (для удобства), что она поделена на 4 пиксела (по штуке на квадрант). Допустим, мы теперь делаем апскейл на 16 пикселов (т.е. каждый пиксел режется на 4). Сфокусируемся на пикселе [0;0]-[1;1]. Нам известно, что там есть корень. На старой картинке он был чёрный. Теперь пикселов 4. Какие пикселы должны остаться чёрными?

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

Варианты:

1) Ничего не кешировать при апскейле. Если есть апскейл — считать дальше.

2) Кешировать только негативные результаты (для апскейла) и только позитивные для даунскейла. 

3) Кешировать точки, которые привели к нахождению корня (т.е. имеют смену знака). После апскейла перекладывать найденные ранее значения в новые пикселы и использовать для поиска смены знака. Проблем две: апскейл не обязательно делит пиксел на новые (может быть смена разрешения с 1024x768 на 1028x770), и очень большой объём памяти для хранения посчитанных значений. (100 ресайзов и у вас почти гарантированно новый набор точек на каждом ресайзе, даже при 4х сэмплинге это 400x разрешения, т.е. 6Гб памяти).

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

С этой оговоркой становится интереснее. Получается, мы для каждого пиксела храним произвольный список посчитанных значений с координатами (т.е. сэмплов). При ресайзе мы перераспределяем найденные сэмплы между новыми пискелами и пересчитываем sign change (это быстро), и получаем относительно быстро «уточнённое» изображение, по которому уже можно пробегаться снова для переуточнения.

Excitement!

Более того, мне не нужно хранить «значения» в сэмплах, достаточно хранить только знак. Особую интересную боль доставляют истинные корни (т.е. нули). В принципе, если мы признаем nan/inf как валидный случай, как раз 4 варианта на 2 бита. Но! Зачем мне эти биты, если можно наборот?

Допустим, у нас будет такая структура для пиксела:

type Point = (f64;f64);

{

root: Vec<Point>,

positive: Vec<Point>,

nan: Vec<Point>,

negative: Vec<Point>

}

При переразбитии плоскости на новые пикселы мы можем иметь итератор по всем 4м типам (это не сильно отличается от целого списка). Зато подсчёт «цвета» тривиальный. roots or (positive and negative) — пискел чёрный.

Фактически, переразбитие выглядит как «вычитывание всех типов сэмплов по всем старым пикселам» и раскладывание найденного в новые пикселы.

После этого можно шуршать по пикселам и думать «хотим мы докинуть новых точек для текущего уровня детализации или нет». 

... И хранить желаемый уровень детализации в пикселе. Во-первых он наследуется в большую сторону при апскейлинге во-вторых всякие «соседи корней» просто накидывают +1 к окружающим пикселам при их нахождении. А отдельный тредик (или async) бегает по пикселам и досчитывает им новые точки.

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

Короче, жизнь прям налаживается.


Error

default userpic

Your IP address will be recorded 

When you submit the form an invisible reCAPTCHA check will be performed.
You must follow the Privacy Policy and Google Terms of use.