скорость

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

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

Скорость довольно грубого брутфорса (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) бегает по пикселам и досчитывает им новые точки.

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

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