Всем привет.

Пишу класс для хранения трехмерного массива в линейном и реализации всех возможных операций.

Странно, что мне не помог ни гугл ни stackoverflow.

Есть множество объектов в трехмерном пространстве. У каждого объекта целочисленные координаты, хранятся в Vector3(x,y,z).
Множество объектов мы получаем постепенно, т.е. сначала 0 объектов, потом 1, потом еще 1...

Допустим, все объекты будем хранить в трехмерном массиве.
Индексы массива начинаются с 0, значит будем сохранять минимальные координаты и максимальные. По этой паре векторов будет определяться размер массива и смещение координат в нем.

Иногда массив нужно будет ресайзить. Но увеличиваться он будет до определенного размера.

Элемент с определенным индексом в массиве имеет координаты зависящие от индекса и сохраненных Min Max векторов.

И теперь, самое сложное. Множество объектов "скроллится". Т.е. данные, например по -x,-y,z становятся неактуальными их нужно удалить, сместив все элементы внутри массива по этим осям на 1.
А в x,y,-z тут же будут записаны новые, актуальные элементы. И Min Max векторы нужно будет пересчитывать.


И наконец, ожидается огромное количество итераций, значит, ради экономии времени, хранить всё будем в одномерном массиве.

Начал писать класс, но уже есть проблемы. Несколько элементов, занесенных в массив в самом начале методом AddOrReplace когда еще Size == (1,1,1), после самого первого ресайза, "теряются".
Кроме того, иногда вылетает OutOfBounds на T val = oldArr[(...

Очень прошу помощи, любой, от кода до совета. И подскажите, есть ли готовые классы для решения моей задачи.

public class Arr3D<T> {

private T[] arr;
private Vector3 min, max;
private Vector3 size;

public Arr3D() 
{
    arr = new T[0];
}

public void AddOrReplace(T obj, Vector3 pos) 
{
    Vector3 newMin = Vector3.Min(min, pos); // ( Min(x1,x2), Min(y1,y2), ...
    Vector3 newMax = Vector3.Max(max, pos+Vector3.one); // +(1,1,1)

    if(newMin != min || newMax != max) 
    {
        Resize(newMin, newMax);
    }

    Set(obj, pos);
}

public void Set(T obj, Vector3 pos) 
{
    Set(obj, pos.x, pos.y, pos.z);
}

public void Set(T obj, int x, int y, int z) 
{
    arr[ (y-min.y)*size.x*size.y  +  (z-min.z)*size.x + (x-min.x) ] = obj;
}

private void Resize(Vector3 newMin, Vector3 newMax) 
{
    Vector3 oldMin = min;
    Vector3 oldMax = max;
    T[] oldArr = arr;
    Vector3 oldSize = size;

    min = newMin;
    max = newMax;
    size = newMax - newMin;
    arr = new T[size.z*size.y*size.x];

    for(int x=oldMin.x; x<oldMax.x; x++) 
    {
        for(int y=oldMin.y; y<oldMax.y; y++) 
        {
            for(int z=oldMin.z; z<oldMax.z; z++) 
            {
                T val = oldArr[(y-oldMin.y)*oldSize.x*oldSize.y  +  (z-oldMin.z)*oldSize.x + (x-oldMin.x)];
                Set(val, x, y, z);
            }
        }
    }

}

public T Get(int x, int y, int z) 
{
    return arr[(y-min.y)*size.x*size.y  +  (z-min.z)*size.x + (x-min.x)];
}
}

Здравствуйте, Javaec, Вы писали:

J>Есть множество объектов в трехмерном пространстве. У каждого объекта целочисленные координаты, хранятся в Vector3(x,y,z).
J>Множество объектов мы получаем постепенно, т.е. сначала 0 объектов, потом 1, потом еще 1...

J>Допустим, все объекты будем хранить в трехмерном массиве.
А зачем в трехмерном? Почему-бы не сделать простой массив строк, с возможностью фильтрации/сортировки по значению одного или нескольких полей? Сколько объектов будет существовать одновременно?

Здравствуйте, Nikolay_Ch, Вы писали:

N_C>А зачем в трехмерном? Почему-бы не сделать простой массив строк, с возможностью фильтрации/сортировки по значению одного или нескольких полей? Сколько объектов будет существовать одновременно?

Размер пространства примерно 15x15x15 (3375). Но добавление новых элементов и "скроллинг" с удалением выходящих за границу — операции очень частые.
Не думаю, что есть смысл сортировать, если можно обращаться прямо к элементу по индексу. Производительность очень важна тут.

Здравствуйте, Javaec, Вы писали:
J>Очень прошу помощи, любой, от кода до совета.

Есть противоречие. При скроллинге теряется смысл доступа к элементу по индексу (координатам) и наоборот. Можно реальную задачу?

Здравствуйте, Ромашка, Вы писали:

Р>Есть противоречие. При скроллинге теряется смысл доступа к элементу по индексу (координатам) и наоборот. Можно реальную задачу?

Задача в рамках разработки компьютерной игры. Игрок двигается — пространство скроллится.

Скорость одного обращения приоритетна. Никаких ссылочных типов. Никаких произвольных обращений к памяти.

А по индексу можно же обращаться, т.к. мы храним min и max векторы и благодаря им можем вызвать Get(-4, 3, 7) и взять его по какому-нибудь, 27му индексу в одномерном массиве.
Всякая математика по вычислению индекса выполняется на порядок быстрее, чем само обращение к памяти.

Здравствуйте, Javaec, Вы писали:

Одномерный массив из компоненнтов с тремя координатами эмулирующий трёхмерный строил так:
float* mass=(float*)malloc(sizeof(float)*size1*size2*size3*3);
int a=size2*size3*3;
int b=size3*3;
for(x1=0;x1<size1;x1++){
for(x2=0;x2<size2;x2++){
for(x3=0;x3<size3*3;x3+=3){
mass[x1*a+x2*b+x3]=value_x
mass[x1*a+x2*b+x3+1]=value_y
mass[x1*a+x2*b+x3+2]=value_z

Правда доступ вида mass[a1][a2][a3][a4] превращается в mass[a1*size2*size3*3+a2*size3*3+a3*3+a4]
но в C++ это можно обернуть в объекты и методы класса так, что доступ будет в стиле Vector(a1,a2,a3).a4
И ещё у меня прокатывало весь mass скидывать glDrawArrays(GL_POINTS,0,size1*size2*size3);
и потом в геометрическом шейдере каждую вершину генерировать в полигон.

Здравствуйте, Javaec, Вы писали:

J>Здравствуйте, Nikolay_Ch, Вы писали:

N_C>>А зачем в трехмерном? Почему-бы не сделать простой массив строк, с возможностью фильтрации/сортировки по значению одного или нескольких полей? Сколько объектов будет существовать одновременно?

J>Размер пространства примерно 15x15x15 (3375). Но добавление новых элементов и "скроллинг" с удалением выходящих за границу — операции очень частые.
J>Не думаю, что есть смысл сортировать, если можно обращаться прямо к элементу по индексу. Производительность очень важна тут.
Меня слабо интересует размер пространства. Меня интересует количество объектов в этом пространстве. Не в каждой-же точке пространства висит по объекту? Если не в каждой — Вам все равно надо пробегать во всему списку объектов, чтобы определить, какие надо скрыть. Если в каждой, то я-бы подумал про списки, индексированные по одной из координат (три словаря на каждую плоскость). Тогда для отсечения нужных, Вам просто нужно будет фильтровать нужную плоскость. Объекты будут присутствовать одновременно во всех трех списках.

Здравствуйте, smeeld, Вы писали:

S>Здравствуйте, Javaec, Вы писали:

S>Одномерный массив из компоненнтов с тремя координатами эмулирующий трёхмерный строил так:
S>float* mass=(float*)malloc(sizeof(float)*size1*size2*size3*3);

Но это же массив для хранения точек. У вас каждая координата — отдельный элемент массива.

Мне не нужно хранить точки, т.к. координаты целочисленные. В моем случае, набор из трех координат — аргумент для обращения к элементу массива.
Элементом массива может быть int, если я буду хранить, например, температуру или радиоактивность.

Здравствуйте, Nikolay_Ch, Вы писали:

N_C>Меня слабо интересует размер пространства. Меня интересует количество объектов в этом пространстве. Не в каждой-же точке пространства висит по объекту? Если не в каждой — Вам все равно надо пробегать во всему списку объектов, чтобы определить, какие надо скрыть. Если в каждой, то я-бы подумал про списки, индексированные по одной из координат (три словаря на каждую плоскость). Тогда для отсечения нужных, Вам просто нужно будет фильтровать нужную плоскость. Объекты будут присутствовать одновременно во всех трех списках.

Не обязательно пробегать по всему списку объектов. Игрок переместился на (2,0,3) — передаем этот вектор массиву в метод скролла. И каждый элемент массива нужно сдвинуть на 2 по X и на 3 по Z. В отрицательную сторону.
Все, что не поместились — отбрасываем, т.к. не актуальны.

Здравствуйте, Javaec, Вы писали:


J>И теперь, самое сложное. Множество объектов "скроллится". Т.е. данные, например по -x,-y,z становятся неактуальными их нужно удалить, сместив все элементы внутри массива по этим осям на 1.
J>А в x,y,-z тут же будут записаны новые, актуальные элементы. И Min Max векторы нужно будет пересчитывать.

Насколько я понимаю тебе нужен "зацикленный массив". Поясню для линейного. Пусть в нем N элементов. Введем понятие логического номера элемента — это номер в твоей модели, не в массиве как таковом. Например, нулевой элемент модели при скроллинге влево должен исчезнуть, первый — стать нулевым и т.д. Правильно я понял ?


Изначально

логический 0-й хранится в a[0]
логический 1-й хранится в a[1]
...
логический N-1 хранится в a[N-1]

то есть логические и физические номера совпадают.


Когда делается скроллинг влево, полагаем, что

логический 0-й хранится в a[1] // т.е. бывший логический 0-й исчез, а бывший логический 1-й стал нулевым

логический 1-й хранится в a[2]
...
логический N-1 хранится в a[0]

Еще один скроллинг вправо и имеем

логический 0-й хранится в a[2]
логический 1-й хранится в a[3]
...
логический N-2 хранится в a[0]
логический N-1 хранится в a[1]

и т.д.

При этом подходе ничего вообще сдвигать не надо.

PD>Еще один скроллинг вправо и имеем

Влево, конечно.

Здравствуйте, Pavel Dvorkin, Вы писали:


PD>Насколько я понимаю тебе нужен "зацикленный массив". Поясню для линейного. Пусть в нем N элементов. Введем понятие логического номера элемента — это номер в твоей модели, не в массиве как таковом. Например, нулевой элемент модели при скроллинге влево должен исчезнуть, первый — стать нулевым и т.д. Правильно я понял ?
PD>...
PD>Когда делается скроллинг влево, полагаем, что
PD>логический 0-й хранится в a[1] // т.е. бывший логический 0-й исчез, а бывший логический 1-й стал нулевым

Всё верно. Только вот последние элементы на место первых в моей задаче ставить не нужно.
За вариант формулировки спасибо, теперь будет проще описывать задачу.

Не понятно только, почему в интернете так мало материала по вопросу представления многомерного массива одномерным.
У меня, например, обращение к элементу одномерного массива выполняется в 2-4 раза быстрее (в зависимости от кол-ва итераций), чем к элементу "развернутого" трехмерного.

Здравствуйте, Javaec, Вы писали:

J>Не понятно только, почему в интернете так мало материала по вопросу представления многомерного массива одномерным.
J>У меня, например, обращение к элементу одномерного массива выполняется в 2-4 раза быстрее (в зависимости от кол-ва итераций), чем к элементу "развернутого" трехмерного.

А что тут писать-то ? Элемент a[i][j][k] при размерах N,M,L есть

b[i*M*L + j*M + k]

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>А что тут писать-то ? Элемент a[i][j][k] при размерах N,M,L есть

PD>b[i*M*L + j*M + k]

Это и так понятно. Написал уже, вот в resize есть баг. Отладкой найти пока не получается, выглядит код годно.
Где же проблема

А потом скроллинг как писать, чтобы шустренько работал? Nikolay_Ch предлагал использовать списки. Это конечно огромное расточительство по времени обращения к одному элементу.
Но для скроллинга быстрее работать со ссылками, чем поэлементно переписывать данные в массиве.

Здравствуйте, Javaec, Вы писали:


J>А потом скроллинг как писать, чтобы шустренько работал?

Еще раз прочти, что я написал. Там весь алгоритм скроллинга изложен. Грубо говоря, весь скроллинг сводится к операции ++ или -- — переносим логическое начало в массиве.


>Nikolay_Ch предлагал использовать списки. Это конечно огромное расточительство по времени обращения к одному элементу.

Списки — смотря какие. Если на базе массива — этот то же массив, в общем-то. Если на базе ссылочной реализации — это чудовищно.

J>Но для скроллинга быстрее работать со ссылками, чем поэлементно переписывать данные в массиве.

Ничего вообще переписывать не надо. Скроллинг — смещение логического начала в массиве, и ничего больше.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Ничего вообще переписывать не надо. Скроллинг — смещение логического начала в массиве, и ничего больше.


Вот например одномерный массив температур:
{15,16,16,17}
чтобы его заскроллить нужно пройтись по всей его длине и переприсваивать элементы.

Получим:
{16,16,17,0}

Может есть какой-то другой способ, который быстрее? Буду благодарен, если опишите.

Здравствуйте, Pavel Dvorkin, Вы писали:

>>Nikolay_Ch предлагал использовать списки. Это конечно огромное расточительство по времени обращения к одному элементу.
PD>Списки — смотря какие. Если на базе массива — этот то же массив, в общем-то. Если на базе ссылочной реализации — это чудовищно.
Пока мне вообще непонятно, что автор топика хранит внутри массива, более того, я не понял, заполнен ли массив целиком или только частично.
Ссылочные типы не всегда чудовищны, особенно, когда надо делать кластеризацию. Или в случае, если массив слабо заполнен.

Здравствуйте, Javaec, Вы писали:

J>Вот например одномерный массив температур:
J>{15,16,16,17}
J>чтобы его заскроллить нужно пройтись по всей его длине и переприсваивать элементы.
А не лучше ли Вам подумать насчет использования "скользящего окна", которое определяет, что отображается в данный момент на экране? Тогда скроллирование сведется к изменению начала координат, как написал Павел? Никаких переприсваиваний не нужно будет.

Здравствуйте, Nikolay_Ch, Вы писали:

N_C>А не лучше ли Вам подумать насчет использования "скользящего окна", которое определяет, что отображается в данный момент на экране? Тогда скроллирование сведется к изменению начала координат, как написал Павел? Никаких переприсваиваний не нужно будет.

Да, но тогда нужно будет сразу выделять память под всё.
Т.е. делать массив, размер которого будет полностью соответствовать количеству зон в игровом мире.
Надо подумать, сколько потребуется памяти.

Здравствуйте, Javaec, Вы писали:


J>Вот например одномерный массив температур:
J>{15,16,16,17}
J>чтобы его заскроллить нужно пройтись по всей его длине и переприсваивать элементы.

J>Получим:
J>{16,16,17,0}

J>Может есть какой-то другой способ, который быстрее? Буду благодарен, если опишите.

Да зачем его надо скроллить заменой элементов?
Есть два указателя — голова и хвост. В терминах C# — два индекса. Для трёхмерного массива будет 6 индексов. Дальше манипуляции с ними: скроллинг — это инкремент/декремент индексов голов. И отсечение по индексу хвостов, если надо нули выдавать или некое значение-по-молчанию. Сам массив будет фиксированного размера, элементы значениями переписывать дорого и только по исключительной необходимости.

Здравствуйте, Javaec, Вы писали:

J>Надо подумать, сколько потребуется памяти.
Интересно... А для какой платформы Вы пишете, что накладывает жесткие ограничения по памяти?