Здорово, мужики. Ща я расскажу вам небольшую предысторию.
Я пишу программку — простенький рендерер для множества вокселей в пространстве. Над множеством вокселей я строю вспомогательную структуру — дерево, где у узла 8 дочерних узлов, а в листьях хранятся данные (т.е., непосредственно воксели). Извините, мальчики, я плохо владею терминологией, но вроде это называется октодеревья. Далее у меня есть функция поиска пересечения луча и вокселя в множестве, такого, чтобы оно было ближайшим к точке, из который луч исходит.
Далее, сам рендерер может быть такой:
1) Для каждого пикселя на экране пускаем луч, который обходит это дерево с корня до листов, и, если есть пересечение, ставим точку на экран (я использую SDL и пишу в surface->pixels)
2) Подмечаем, что для близких лучей (мало отклоняющихся) путь от корня дерева до листа с данными почти одинаков (например root->a->b->c->d и root->a->b->c->e) и начинаем поиск с листа, возвращаесь, если надо, к корню.
И вот вопрос: для второго случая надо записывать в surface->pixels элементы не один за другим, как в таком коде:
int i,j;
int p = 0;
for (i=0; i<surface->w; i++)
{
for (j=0; j<surface->h; j++)
{
*((Uint32*)surface->pixels+p) = calc_color();
p++;
}
}
а, скажем, разбивая экран на квадратики, где такая путь обхода меняется лишь незначительно. Но с другой стороны, к элементам pixels придется обращаться не один за другим, а как-то так:
int i,j,k,l;
for (i=0; i<surface->w/SQUARE_LEN; i+=SQUARE_LEN)
{
for (j=0; j<surface->h/SQUARE_LEN; j+=SQUARE_LEN)
{
for (k=0; k<SQUARE_LEN; k++)
{
for (l=0; l<SQUARE_LEN; l++)
{
*((Uint32*)surface->pixels+(i+k)*width+j+l) = calc_color();
}
}
}
}
Сильно ли это скажется на производительности из-за промахов в кеше? Или какие варианты могут быть, чтобы локальность и в смысле обхода дерева (в двухмерном пространстве) сохранить, и в смысле записи в pixels.
Мальчики, выручайте, ога?
