Можно просто. Если замеряемый fps около 60 то использовать указанный костыль, если видим что fps реально не успевает — выключаем костыль, действуем как обычно. Это, конечно, не идеально, но поскольку на уровне API решений нет, пока так сойдет…
Пояснения к примененным методам для функции построения кривой Гилберта:
Минимальный конструктивный элемент я обозначил для себя термином «симплекс».
Размер симплекса 2 в степени количества измерений. Например для 3D это кубик размером 2x2x2. Эмпирически мной установлено, что элементы симплекса обходятся по коду Грея, например для 3D каждому из трех бит соответствует координатная ось.
Симплексы подвергаются рекурсивным трансформациям, чтобы конец предыдущего и начало следующего составили один шаг. Эмпирически мной установлено, что из всех возможных трансформаций используется только 2 в степени измерений (для 3D случая 8 из 16 возможных). Причем если визуально упростить симплексы соединив отрезком только начало и конец, то множество возможных трансформаций заполняют кривую построенную по коду грея. Четные/нечетные отрезки будут направлены в разные стороны.
Рекурсивно трансформируемый элемент обходится по коду Грея. Эмпирически мной установлено, что индекс трансформации тоже можно получить по коду Грея, но тогда кривая замкнется. Что бы этого не происходило первый и последний элемент нужно развернуть «рогами» наружу
Ну а дальше банальная бинарная арифметика в помощь. После оптимизаций получилась функция get_Gilbert_XY(i: int)
На практике может понадобиться обойти элементы кривой Гилберта по очереди. Можно решить задачу «в лоб» как в приведенном мной примере или рекурсивными вызовами, но существуют и более оптимальные способы это сделать, правда это совсем уже другая история…
И на счет быстродействия пару замечаний:
— на фоне скорости чтения/записи памяти математические операции для процессора это раз плюнуть. Даже sin/cos вычисляются за почти за пару тактов.
— время доступа для кэшей процессора register/L1/L2/… для каждого следующего уровня отличается на порядок: 1 такт/10 тактов/100 тактов/1000 тактов. Поэтому не факт что использование предвычисленных данных будет давать значительный прирост, возможно даже и наоборот (но это не точно, практика — критерий истины).
До меня как до жирафа доходило что у вас многомерный случай, и используемая библиотека оптимизирована именно под это. Уверен что для 2D/3D/4D моя функция «уделает» hilbert_i2c() в тестах (не хотите проверить?), но:
— под бОльшие мерности пространства оптимизации меняются
— мой трехмерный мозг туго работает с N-мерностями выше трех (это усложняет визуальную отладку)
Ну возьмем для примера 3D.
Значит в наивной реализации 32 прохода по циклу. А в оптимизированном варианте можно сделать, скажем, за 4 прохода, правда нужен индекс порядка 64Mb размером.
Можно конечно и по диагонали. А можно и по окто-дереву. Кривая замыкается в кольцо и начало можно назначать произвольно. Если взять начало в середине получатся те же свойства что и у кривой Гилберта. Кстати, функцию get_GCurve_XY можно еще примерно в два раза ускорить.
private const d : int = 4;
private const dm : int = (1 << d) - 1;
private var xx_ : int;
private var yy_ : int;
public function get_GCurve_XY(i: int) : void
{
var j : int;
var v : int;
var b : int;
var f : int;
xx_ = yy_ = b = 0;
f = i;
for (j = d - 1; j >= 0; --j)
{
f += (1 << (j << 1)) >> 1;
v = ((f >> (j << 1)) + b) & 3;
b = v ^ 2;
v ^= b >> 1;
xx_ |= (v & 1) << j;
yy_ |= (v >> 1) << j;
}
}
//.............................................................................
public function DP_Curve() : void
{
var px : int;
var py : int;
var x : int;
var y : int;
var i : int;
var nn : int = (1 << (d << 1));
for (i = 0; i < nn; ++i)
{
get_GCurve_XY(i);
if (0 != i)
draw_Line(px, py, xx_, yy_);
px = xx_;
py = yy_;
}
}
Можно просто. Если замеряемый fps около 60 то использовать указанный костыль, если видим что fps реально не успевает — выключаем костыль, действуем как обычно. Это, конечно, не идеально, но поскольку на уровне API решений нет, пока так сойдет…
Ни кто не подскажет, как 64 битами закодировать 1024 объекта?
Размер симплекса 2 в степени количества измерений. Например для 3D это кубик размером 2x2x2. Эмпирически мной установлено, что элементы симплекса обходятся по коду Грея, например для 3D каждому из трех бит соответствует координатная ось.
На практике может понадобиться обойти элементы кривой Гилберта по очереди. Можно решить задачу «в лоб» как в приведенном мной примере или рекурсивными вызовами, но существуют и более оптимальные способы это сделать, правда это совсем уже другая история…
— на фоне скорости чтения/записи памяти математические операции для процессора это раз плюнуть. Даже sin/cos вычисляются за почти за пару тактов.
— время доступа для кэшей процессора register/L1/L2/… для каждого следующего уровня отличается на порядок: 1 такт/10 тактов/100 тактов/1000 тактов. Поэтому не факт что использование предвычисленных данных будет давать значительный прирост, возможно даже и наоборот (но это не точно, практика — критерий истины).
— под бОльшие мерности пространства оптимизации меняются
— мой трехмерный мозг туго работает с N-мерностями выше трех (это усложняет визуальную отладку)
Значит в наивной реализации 32 прохода по циклу. А в оптимизированном варианте можно сделать, скажем, за 4 прохода, правда нужен индекс порядка 64Mb размером.
Причем если использовать массив заранее рассчитанных значений (до любой выбранной глубины) то количество итераций в цикле можно серьезно уменьшить.
Кстати, для Z-order функция выглядит так: