Войти
ПрограммированиеФорумОбщее

Какой структурой можно оптимизировать? (2 стр)

Страницы: 1 2
#15
16:29, 18 ноя 2020

}:+()___ [Smile]
> Это плохо — ускоряющие структуры на основе регулярной сетки (в т. ч.
> растеризация) будут неэффектинвыми.
Так двухуровневую сетку предложили, она как раз подойдёт - пустые области обозначатся на первом же уровне, а второй аллоцируется только для непустых областей.

lookid
> Разбиваешь поле на 5x5 ячеек.
А почему не 6*6?


#16
16:37, 18 ноя 2020

Delfigamer
Потомучто 5 это оценка в школе, а 6 это шестерка. Можно еще 7 - счастливое число. А 13 не нужно.

#17
16:39, 18 ноя 2020

Delfigamer
> Так двухуровневую сетку предложили, она как раз подойдёт - пустые области обозначатся на первом же уровне, а второй аллоцируется только для непустых областей.
Если пустые области действительно большие (а раз поле 16k×16k и прямоугольники 4×4, то, скорее всего, так и есть), то двух уровней будет мало. Собственно, квадтри — это древообразная структура с нодами 2×2, если хочется меньше прыжков по памяти и больше SIMD, то можно попробовать ноды 4×4 и выше, будет обобщение идеи двухуровневой сетки.

#18
17:09, 18 ноя 2020

}:+()___ [Smile]
> Если пустые области действительно большие (а раз поле 16k×16k и прямоугольники
> 4×4, то, скорее всего, так и есть), то двух уровней будет мало.
128*128 ячеек по 128*128 для полной растеризации - это слишком плохо? 🤔
Вроде же в самый раз под кэш.

#19
20:06, 18 ноя 2020

Delfigamer
> 128*128 ячеек по 128*128 для полной растеризации - это слишком плохо?
Зависит. Если, например, прямоугольники расставлены достаточно равномерно, так что почти в каждый нижний 128×128 попадает хотя бы один, то уровни, по сути, работать не будут.

#20
4:11, 19 ноя 2020

AlexeyLarin
> рямоугольники не пересекаются. В каждой точке либо 1 прямоугольник либо 0.
> Максимальный размер сетки 16К x 16К. Большая часть поля будет пустой. В
> основном все прямоугольники меньше 4x4, но могут быть и до 16x16.
ну тогда 100% тайловый растр: делаешь грубую сетку, скажем, 1k x 1k и далее каждый пиксель этой сетки называешь тайлом. если в тайле есть хоть один занятый пиксель, то аллоцируешь его, иначе не выделяешь даже для него память. и дальше растеризуешь свои прямоугольники как душе угодно, выделяя память для тайлов, на которые они попадают. это гораздо быстрее чем quadtree, потому что ты сам определяешь свой memory layout и память в каждом тайле будет находиться локально.

кстати, такую структуру данных даже графические редакторы вроде фотошопа используют, потому что на CPU работать с мелкими тайлами — гораздо эффективнее, чем с гигантским растром.

#21
15:31, 19 ноя 2020

Пока сделал через aabb-tree, потом может попробую что-то еще. Спасибо за советы.

#22
7:01, 20 ноя 2020

Suslik
Напомнило:

Why a two-level hierarchy? Decades of experience has shown that you almost never want quadtree-esque fully-recursive hierarchies for speeding things up; you almost always want two-level hierarchies. (Maybe, maybe, if it's really big, you want three-level hierarchies. If you wanted to do a 65536x65536 map, maybe that would be better.)

(с) https://stb.handmade.network/blogs/p/1136-connected_components_algorithm

Сама идея stb_connected_components.h известная. Например, https://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf её юзает, и на КРИ она звучала.

#23
8:58, 20 ноя 2020

}:+()___ [Smile]
> Зависит. Если, например, прямоугольники расставлены достаточно равномерно, так
> что почти в каждый нижний 128×128 попадает хотя бы один, то уровни, по сути,
> работать не будут.
Идея - если тайл "достаточно пустой" (в нём мало прямоугольников, или они покрывают малую площадь), то можно вместо полной растеризации хранить только список входящих прямоугольников.
То есть, структура всё ещё двухуровневая, но на каждый тайл предусмотрено три состояния - пустой, со списоком и с растром.
Если я правильно понял "пустые пространства" ОПа как большие пустоты между плотными регионами - то списочные тайлы как раз сэкономят память на границах и островах.

#24
22:43, 20 ноя 2020

Delfigamer
Размер списка вроде можно вполне внятно ограничить 1.
https://rextester.com/WSSHM13484

Страницы: 1 2
ПрограммированиеФорумОбщее

Тема в архиве.