- Имбирная Ведьмочка
- Постоялец
}:+()___ [Smile]
> Это плохо — ускоряющие структуры на основе регулярной сетки (в т. ч.
> растеризация) будут неэффектинвыми.
Так двухуровневую сетку предложили, она как раз подойдёт - пустые области обозначатся на первом же уровне, а второй аллоцируется только для непустых областей.
lookid
> Разбиваешь поле на 5x5 ячеек.
А почему не 6*6?
Delfigamer
Потомучто 5 это оценка в школе, а 6 это шестерка. Можно еще 7 - счастливое число. А 13 не нужно.
Delfigamer
> Так двухуровневую сетку предложили, она как раз подойдёт - пустые области обозначатся на первом же уровне, а второй аллоцируется только для непустых областей.
Если пустые области действительно большие (а раз поле 16k×16k и прямоугольники 4×4, то, скорее всего, так и есть), то двух уровней будет мало. Собственно, квадтри — это древообразная структура с нодами 2×2, если хочется меньше прыжков по памяти и больше SIMD, то можно попробовать ноды 4×4 и выше, будет обобщение идеи двухуровневой сетки.
}:+()___ [Smile]
> Если пустые области действительно большие (а раз поле 16k×16k и прямоугольники
> 4×4, то, скорее всего, так и есть), то двух уровней будет мало.
128*128 ячеек по 128*128 для полной растеризации - это слишком плохо? 🤔
Вроде же в самый раз под кэш.
Delfigamer
> 128*128 ячеек по 128*128 для полной растеризации - это слишком плохо?
Зависит. Если, например, прямоугольники расставлены достаточно равномерно, так что почти в каждый нижний 128×128 попадает хотя бы один, то уровни, по сути, работать не будут.
AlexeyLarin
> рямоугольники не пересекаются. В каждой точке либо 1 прямоугольник либо 0.
> Максимальный размер сетки 16К x 16К. Большая часть поля будет пустой. В
> основном все прямоугольники меньше 4x4, но могут быть и до 16x16.
ну тогда 100% тайловый растр: делаешь грубую сетку, скажем, 1k x 1k и далее каждый пиксель этой сетки называешь тайлом. если в тайле есть хоть один занятый пиксель, то аллоцируешь его, иначе не выделяешь даже для него память. и дальше растеризуешь свои прямоугольники как душе угодно, выделяя память для тайлов, на которые они попадают. это гораздо быстрее чем quadtree, потому что ты сам определяешь свой memory layout и память в каждом тайле будет находиться локально.
кстати, такую структуру данных даже графические редакторы вроде фотошопа используют, потому что на CPU работать с мелкими тайлами — гораздо эффективнее, чем с гигантским растром.
Пока сделал через aabb-tree, потом может попробую что-то еще. Спасибо за советы.
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 её юзает, и на КРИ она звучала.
}:+()___ [Smile]
> Зависит. Если, например, прямоугольники расставлены достаточно равномерно, так
> что почти в каждый нижний 128×128 попадает хотя бы один, то уровни, по сути,
> работать не будут.
Идея - если тайл "достаточно пустой" (в нём мало прямоугольников, или они покрывают малую площадь), то можно вместо полной растеризации хранить только список входящих прямоугольников.
То есть, структура всё ещё двухуровневая, но на каждый тайл предусмотрено три состояния - пустой, со списоком и с растром.
Если я правильно понял "пустые пространства" ОПа как большие пустоты между плотными регионами - то списочные тайлы как раз сэкономят память на границах и островах.
Delfigamer
Размер списка вроде можно вполне внятно ограничить 1.
https://rextester.com/WSSHM13484
Тема в архиве.