amarao_san

Category:

Алгоритм уточнения корней

Предистория: алгоритм определения, что внутри пиксела есть корень: вычисляем внутри пиксела N значений (решётка 2х2, 111х111 — и т.д.), считаем значение уравнения в каждой точке решётки. Если есть решения с разными знаками и в решениях не было Inf/NaN — значит, корень где-то внутри пиксела.

Проблема: решётка 2х2 (4 точки на пиксел) часто не замечает корней.

Вот:

lattice 2x2, rendered in  0.43s
lattice 2x2, rendered in 0.43s

По-идее, большая часть центральной области (и вся она) должна быть чёрной. Увеличение размера решётки ситуацию улучшает ситуацию, но квадратично увеличивает время рассчёта от размера матрицы. 2х2 считается за 433 мс, а матрица 37х37 — за 110 секунд.

lattice 2x2, rendered in  110s
lattice 2x2, rendered in 110s


Моя идея:

После грубого рендеринга (матрица 2х2) мы проходимся ещё раз и для всех пикселов, которые не корни (т.е. белые), и у которых есть корни в соседях (т.е. соседние пикселы чёрные) резко задираем размер решётки (в 2x2 раза за каждого соседа с корнем, т.е. максимум 32x32) и просчитываем только их. Таких точек для большинства графиков мало (вы выкидываем точки с корнями и точки без корней далеко от корней), так что нам не надо считать 2 миллиона пикселов, а надо считать десятки тысяч.

Далее мы смотрим, сколько новых корней нашлось. Если корни нашлись, мы вносим новые корни в специальный «важный» список, вокруг которого за каждый найденный новый корень соседним пикселам удесятеряем размер lattice (причём, если пикселов с  корнями найдено несколько, то размер lattice может стать и 100x100, и даже 2265600x2265600 (но для нескольких пикселов).

Если было найдено больше одного корня, повторяем процесс (на каждую итерацию размер lattice увеличивается на чуть-чуть, плюс множители за соседей и новонайденные корни). Как только новых корней найдено 0, мы пробуем несколько раз повторить поиск, но сдаёмся и считаем, что рендеринг закончен.

0.44 for base rendering, 47s for updates.
0.44 for base rendering, 47s for updates.

Статистика улучшений выглядит так:

Updating: iteration 1  max lattice:256, 15520 additional pixels
Updating: iteration 2  max lattice:25600, 3942 additional pixels
Updating: iteration 3  max lattice:38400, 3061 additional pixels
Updating: iteration 4  max lattice:51200, 1100 additional pixels
Updating: iteration 5  max lattice:64000, 1442 additional pixels
Updating: iteration 6  max lattice:76800, 310 additional pixels
Updating: iteration 7  max lattice:89600, 267 additional pixels
Updating: iteration 8  max lattice:102400, 169 additional pixels
Updating: iteration 9  max lattice:115200, 136 additional pixels
Updating: iteration 10  max lattice:160000, 169 additional pixels
Updating: iteration 11  max lattice:193600, 54 additional pixels
Updating: iteration 12  max lattice:460800, 73 additional pixels
Updating: iteration 13  max lattice:499200, 25 additional pixels

(у меня ощущение, что где-то баг, потому что 499200x499200 должно занимать часы рассчёта...)

Что-то получается, но средне. 47 с — я за такое время могу рендерить «всё» с матрицей 23x23, и картинка получается за это время куда более солидной:

23x23
23x23


Причины: гоняться за отдельными точками интересно, но не достаточно. Идея «соседних» корней интересная, но понятие «соседний» слишком грубо (область 3х3 вокруг пиксела). Надо расширять это понятие. Более того, найденный корень должен влиять на достаточно большое пространство вокруг.

Рейт при этом не стоит задирать — от миллиарда рассчётов внутри «точно белого пиксела» он чернее не станет — а каждый проход будет норовить его снова промурыжить.

Т.е. — рейты увеличения поменьше, а вот область охвата — побольше.

Идеи для новой эвристики:

область: iteration x iteration

new_root_rate: iteration — distance (т.е. для прямого соседа — номер итерации, для остальных по убывающей).

рейт: (base + iteration + root_neighbors)* new_root_rate

Сама идея гоняться за корнями всё-таки интересна: 23x23 без гоняния (слева) и  последующим гонянием (справа):

Видно, что гоняясь за корнями, самые сложные области оказываются более «прощупаны».

UPD: Я чуть-чуть поменял алгоритм, теперь после каждой итерации, которая ощупывает «все» корни, идут итерации «глубокого ощупывания» новых корней (пока 0 новых не станет), тогда снова чуть более глубокое ощупывание всех корней (менее глубокое, чем для новых, но глубже, чем в предыдущий проход), и снова гонка за новыми корнями. Соседи теперь — это все в окрестностях 40x40.

Старт с решётки 2х2, 31 секунда, 69 итераций уточнения.
Старт с решётки 2х2, 31 секунда, 69 итераций уточнения.
Рёштка 3х3, 36 секунд, 67 итераций
Рёштка 3х3, 36 секунд, 67 итераций

Сравнение вариантов:

начальное значение 3x3: 304848 корней за 36.3с

2x2, 297865 корней за 31.8с

23x23 без уточнений, 306692 корней за 44.1s,

Получается, что 3х3 с уточнениями почти такой же хороший, как и 23x23 без уточнений.

Я, конечно, не мог пройти мимо варианта 23х23 с уточнениями: 309480 корней (аж на 2.5 тысячи больше) за 435с.

(при этом уточнения дают довольно мало корней, а считают довольно долго).

... мне не нравится идея «долго». Кажется, мне надо сводить последовательность до момента, пока корней находится много за быстро, т.е.контролировать не число корней, а скорость (корней/время нахождения корней). Минута ради 1 нового пикслея — это оверкилл.

А вот у меня есть ещё одна суперэвристика: прогонять решётку 2х2, а потом гонять более благородные решётки только по областям без корней. ...Это настолько очевидно, что надо просто в итератор по картинке засунуть.


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.