Контекст: у меня есть механизм трассировки лучей на базе ЦП, написанный на Pygame. Он работает, заставляя лучи перемещаться на 1 единицу за цикл в направлении их скорости и обнаруживая любой воксел в этой целочисленной позиции. Недавно я добавил фрагменты для повышения производительности: вокселы в каждой области хранятся в контейнере фиксированного размера, который считывается в первую очередь. Например: если размер чанка равен 16, чанк в позиции (0, -16, 32) сохранит все данные из него в позицию (16, 0, 48). Допустимые фрагменты хранятся в словаре, индексированном по их кортежу начального угла, а конечный угол можно получить, добавив к нему размер. Вот пример структуры данных, в данном случае фрагменты имеют значение None, поскольку их данные и то, как они используются, не имеют отношения к моему вопросу.
Код: Выделить всё
chunks = {
(0, 0, 0): None,
(64, 0, 32): None,
(-96, 48, 16): None,
(-128, -96, 0): None,
}
Я заметил, что сканирование фрагментов обходится дороже, чем могло бы быть. Большая часть задержек возникает из-за проверки положения и привязки его к размеру фрагмента для получения соответствующего индекса: каждый раз, когда луч перемещается, мне нужно проверить, находится ли он в области другого фрагмента, и получить его данные. Например, если луч переместился из позиции (-0,5, 0,25, 0) в (0,5, 1,25, 1) с заданной скоростью (1, 1, 1), мне теперь нужно получить данные чанка (0, 0, 0). Это представление моего цикла лучей:
Код: Выделить всё
pos = (0, 0, 0)
chunk_min = (0, 0, 0)
chunk_max = (0, 0, 0)
chunk_size = 16
chunk = None
while True:
if pos[0] < chunk_min[0] or pos[1] < chunk_min[1] or pos[2] < chunk_min[2] or pos[0] > chunk_max[0] or pos[1] > chunk_max[1] or pos[2] > chunk_max[2]:
pos_min = ((self[0] // chunk_size) * chunk_size, (self[1] // chunk_size) * chunk_size, (self[2] // chunk_size) * chunk_size)
pos_max = (pos_min[0] + chunk_size, pos_min[1] + chunk_size, pos_min[2] + chunk_size)
chunk = chunks[pos_min] if pos_min in chunks else None
# Do things with the data in chunk, advance pos by -1 or +1 on at least one axis, and break out of the loop when tracing is over
Этот цикл выполняется десятки раз на пиксель, то есть в общей сложности тысячи раз. Каждая проверка должна быть очень эффективной, иначе FPS резко упадет. Я получаю повышение производительности, кэшируя границы последнего фрагмента, а затем проверяя, когда положение луча больше не находится в этих границах, чтобы изменить фрагмент только один раз, но эта проверка сама по себе является дорогостоящей, а привязка позиции к размеру фрагмента еще дороже. . Как это сделать наиболее оптимально, какие операции по обнаружению входа в новую кубическую область наиболее дешевы?
Подробнее здесь:
https://stackoverflow.com/questions/787 ... ered-a-new
Мобильная версия