Сетка на сфере (решено)

[Igors]

Добрый день

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

Код

C++ (Qt)
QPoint GetCell( const QRectF & R, const QPointF & pt, float step )
{
  return QPoint((pt.x() - R.left()) / step, (pt.y() - R.top()) / step); 
}

Полученный "индекс" ячейки используем для вычисления координат 4-x углов. Также мы знаем какая ячейка слева (справа, снизу и.т.п.) и, если надо, можем взять и ее координаты углов. Обычно это все делается для интерполяции значения в точке на основании значений в узлах сетки.

Как сделать то же самое для сферы? Теперь уже вместо точки вектор (направление)

Код

C++ (Qt)
QPoint GetCell( const QVector3D & vec, float step )
{
  ????
}

Индекс ячейки нам не очень нужен. но цель та же - найти значения в 4-х углах, а возможно и в соседних ячейках. Обычная "меридианная" сетка не годится, клеточки в ней разного размера

Спасибо

[m_ax]

Обычная "меридианная" сетка не годится, клеточки в ней разного размера

Какие две координаты (криволинейные) вы предлагаете использовать? Меридианная - это я полагаю сферическая СК с углами theta, phi?

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

 
А с чего вы взяли, что возможно замостить 3D сферу одинаковыми четырёхугольниками? Почему не треугольниками или шестиугольниками? И что такое step в этом контексте - расстояние между двумя ближайшими узлами рещётки?

Вообщем как всегда - постановка никакая(   

[Igors]

Какие две координаты (криволинейные) вы предлагаете использовать? Меридианная - это я полагаю сферическая СК с углами theta, phi?

Да, но она не годится, поэтому пока ничего не предлагаю

А с чего вы взяли, что возможно замостить 3D сферу одинаковыми четырёхугольниками?

С того что многие алгоритмы это делают. См аттач. Кубик можно рассматривать как сферу разбитую на 6 (равных) частей. Повторяя этот процесс для каждой части - уверенно приближаемся к сфере.

Почему не треугольниками или шестиугольниками? И что такое step в этом контексте - расстояние между двумя ближайшими узлами рещётки?

Это непринципиальные подробности. Мне нужно определить в какую ячейку попал заданный вектор (он же точка на поверхности сферы) чтобы использовать значения в углах для интерполяции. Размер ячейки можно задавать хоть углом хоть расстоянием - они однозначно переводятся друг в друга.

Вообщем как всегда - постановка никакая(    

Как всегда - ни идей, ни техники, только пустопорожние претензии  

[ssoft]

Посмотрите здесь http://gis-lab.info/qa/triangular-mesh-sphere.html.
Скорее всего хотелось бы что-то типа такого.

[Igors]

Посмотрите здесь http://gis-lab.info/qa/triangular-mesh-sphere.html.
Скорее всего хотелось бы что-то типа такого.

C "построением" проблем нет, помню кучу исходников, да и сам не раз писал. Но мне нужен "прямой доступ", т.е. найти ячейку в которую попал вектор.

Если такой возможности для сферы нет, то устроит "спуск по дереву". Напр для пр-ка на плоскости это простая структура данных (псевдокод)

Код

C++ (Qt)
struct Node {
 QRect mRect;         // bounding box
 Node * mChild[4];   // child nodes
 Data * data;           // data values   
};
 

Сам спуск, просто рекурсия (подробности опускаем)

Код

C++ (Qt)
Node * FindNode( Node * root, const QPointF & pt )
{
  if (!mRect.contains(pt))  return 0;
// Находим в какой из child нодов попала точка
// Node * child = ...   
  return child ? FindNode(child, pt) : this;
}

Как реализовать то же для сферы?

[deMax]

Можно получить сферу из куба, разбив грани регулярной сеткой, а потом выровняв длину до центра для всех пикселей.
Тогда и координаты грани просто находятся. (например превращаем координаты на сферу координатами на "исходный куб" для которого поиск аналогичен поиску на прямоугольнике):

для превращения координат к сфере мы делаем нормализацию и умножаем на радиус, обратно ищем большую координату и делим все координаты на ее значение(чтобы она стала 1, а остальные пропорционально уменьшаться).

[Igors]

Можно получить сферу из куба, разбив грани регулярной сеткой, а потом выровняв длину до центра для всех пикселей.

Нет, получить "все клетки сразу" нельзя, на сфере они будут иметь разные площади. Вот последовательно - да

..обратно ищем большую координату и делим все координаты на ее значение(чтобы она стала 1, а остальные пропорционально уменьшаться).

Так этот комок if'oв найдет всего лишь грань кубика на которую проецируется точка (cubic map или best normal)

[deMax]

Так этот комок if'oв найдет всего лишь грань кубика на которую проецируется точка (cubic map или best normal)

Находим максимальную по модулю координату, это и есть грань, потом делим на эту координату весь вектор(оставшиеся координаты и будут координатами на грани, для них применить ваш QPoint GetCell( const QRectF & R, const QPointF & pt, float step ) с учетом направления. для простоты я оперирую в системе координат сферы.

комок if'oв

А что делать(6 if не так и страшно, прямоугольник найти вообще легко и по скорости и по алгоритму), зато на прямоугольники текстура очень легко ложиться без обрезок(в SpaceEngine так сделали например планеты), и размер максимальных прямоугольников не превышает размер минимальных в 2 раза. Т.е. нет запредельной детализации льда на севере и никакой на экваторе.

p.s. Предложите удобный для вас способ разбиения, рассмотрим для него как координаты найти.

[m_ax]

Мне нужно определить в какую ячейку попал заданный вектор (он же точка на поверхности сферы) чтобы использовать значения в углах для интерполяции.

А координаты узлов сетки в принципе известны (их можно получить, перебрать, сортировать и т.д.)?  Т.е. фактически тогда нужно построить такую модель данных (для узлов), чтоб по заданному направлению получить координаты 4-ёх вершин?   

[deMax]

С того что многие алгоритмы это делают. См аттач. Кубик можно рассматривать как сферу разбитую на 6 (равных) частей. Повторяя этот процесс для каждой части - уверенно приближаемся к сфере.

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

QPoint GetCell( const QVector3D & vec, float step )
{
  float radius = vec.lenght();
  int maxXYZ = getMaxNum(vec); // 0 для X, 1 для Y, 2 для Z (находит максимальное значение по модулю, если несколько нужно возвращать -1, т.к. попали на грань ....)

  auto vecNew = vec / abs(vec[maxXYZ]); // делим на максимальное значение
  QVector3D returnPoints[4] = {vecNew,vecNew,vecNew,vecNew};

  for(int i=0; i<3; ++i) {
  for(int j=0; j<4; ++j) {
  if(i == maxXYZ) continue;
  returnPoint[j] = тут логика типа i+j & 1? ceil(returnPoint[0]/step)*step: floor(returnPoint[0]/step)*step;
  }

  for(auto &returnPoint: returnPoints) {
    returnpoint = returnpoint.normalize() * radius; }
}

[deMax]

Т.е. алгоритм:
сохранили радиус
нашли максимальную величину по модулю (x,y или z) int numMax = 0, 1 или 2 (-1 если несколько, выходим из алгоритма, это грань)
на эту величину уменьшили вектор(теперь он ссылается на оригинальный куб из которого сделали сферу)
создали 4 одинаковых вектора равные новому вектору
потом в цикле округляем точки вверх и вниз(std::ceil и std::floor) пропуская numMax. (p[0] = ceil,ceil, p[1]=ceil,floor, p[2]=floor,ceil, p[3]=floor,floor)
и потом 4 вектора нормализуем и умножаем на радиус, это и есть ответ

p.s. если в результате округления значение не меняется - это грань, впрочем шансы что float == float после математики невелики.

это если сфера получается нормализацией куба покрытого равномерной сеткой, а если сетка неравномерная(сплюснута к центру граней, чтобы при натягивании на сферу компенсировать увеличение этих граней) придется усложнить алгоритм. Можно сохранить в массив позиции сетки на кубе и округлять до них....

[Igors]

deMax, сетка что "равномерна на кубе" не будет "равномерна на сфере" и наоборот (см. вттвч). Др словами медиана не равна биссектрисе

[Igors]

А координаты узлов сетки в принципе известны (их можно получить, перебрать, сортировать и т.д.)?  Т.е. фактически тогда нужно построить такую модель данных (для узлов), чтоб по заданному направлению получить координаты 4-ёх вершин?   

Нет, координаты узлов "априорно" неизвестны, они тоже должны получаться из построения.

Общий алгоритм:
- для заданной точки находим "достаточно малую" ячейку (оценка "малости" задается вместе с точкой)
- берем данные в углах, если они еще не готовы - считаем их (на основании координат углов)
- интерполируем значение для точки на основании данных углов

Ну и там много еще всякого, в основном участие в осреднении более дальних соседей (а не только ближайшиx углов). Ну то ладно, так по сути - просто "adaptive grid"

[m_ax]

Нет, координаты узлов "априорно" неизвестны, они тоже должны получаться из построения.

Которое ещё тоже не понятно какое?

Общий алгоритм:

У меня такой алгоритм:
1) У меня есть метод/алгоритм который на сфере (для определённости единичного радиуса) строит сетку в зависимости от числа N узлов (вершин) этой сетки. Чем больше узлов, тем меньше растояние между ними и тем меньше ячейки. Т.е. на выходе я имею N единичных векторов, определяющих положение узлов.

2) Для любой точки на поверхности сферы, простым перебором (самое простое) находим ближайшие к этой точке узлы (просто оценивая скалярное произведение вектора узла на вектор точки - что для единичной сферы сведётся к косинусу угла между ними).

Всё) 

[Igors]

2) Для любой точки на поверхности сферы, простым перебором (самое простое) находим ближайшие к этой точке узлы (просто оценивая скалярное произведение вектора узла на вектор точки - что для единичной сферы сведётся к косинусу угла между ними).

Всё)  

Решение достойное знатока std/boost Какие-то там kd-tree и.т.п. - это ж все "велики", перебор - вот наш метод! К сожалению(?) такая святая простота мне недоступна, робкая попытка создать хоть простенький регулярный буфер сразу сожрала > 1Gb.

Откуда берется шаг. Для точки известна ее проекция на экране, расстояние до соседней на экране, а значит расстояние в 3D - это и есть требуемый шаг. Для точек далеко от центра сферы (наверное Вы уже поняли что это источник света) угол между лучами-углами может быть очень мал (лучи-то расходятся). Поэтому необходимо хранить только те узлы что нужны (к которым было обращение), а для этого нужно как-то получать их точки на основании запросной.  

Если мы умеем строить сферу из куба (а мы умеем), то очевидно мы сумеем и "спуститься по дереву", построив/найдя только точки вокруг заданной. Но как это сделать? (учитывая что кратность вызова этой операции огромна). Или, может, есть др способ? (не исключено хотя я лично его не вижу).

Да, чуть не забыл! А может это просто есть а boost'e? Нет, серьезно - Вы даже не представляете с каким огромным энтузиазмом я буду это место изучать