Russian Qt Forum

Добрый день

Есть прямоугольник (для простоты квадрат) покрытый регулярной сеткой с шагом 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-х углах, а возможно и в соседних ячейках. Обычная "меридианная" сетка не годится, клеточки в ней разного размера

Спасибо

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

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

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

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

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

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

Посмотрите здесь 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;
}

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

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

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

Нет, получить "все клетки сразу" нельзя, на сфере они будут иметь разные площади. Вот последовательно - да
Так этот комок if'oв найдет всего лишь грань кубика на которую проецируется точка (cubic map или best normal)

Находим максимальную по модулю координату, это и есть грань, потом делим на эту координату весь вектор(оставшиеся координаты и будут координатами на грани, для них применить ваш QPoint GetCell( const QRectF & R, const QPointF & pt, float step ) с учетом направления. для простоты я оперирую в системе координат сферы.
А что делать(6 if не так и страшно, прямоугольник найти вообще легко и по скорости и по алгоритму), зато на прямоугольники текстура очень легко ложиться без обрезок(в SpaceEngine так сделали например планеты), и размер максимальных прямоугольников не превышает размер минимальных в 2 раза. Т.е. нет запредельной детализации льда на севере и никакой на экваторе.

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

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

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

Т.е. алгоритм:
сохранили радиус
нашли максимальную величину по модулю (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 после математики невелики.

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

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

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

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

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

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

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

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

Всё) 

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

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

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

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

Да пожалуйста.. Но о каком kd-tree и.т.п. сейчас может идти речь, если мы ещё до сих пор не знаем/не представляем (ну лично я) как Вы хотите параметризовывать, строить сетку на сфере? Когда это будет понято, тогда уже можно будет говорить о модели представления этих узлов. Т.е. где то отображение, которое переводит какие-либо 2 обобщённые координаты (например в случае ССК это углы theta и phi) в координаты конкретного узла сетки?

Я себе сейчас представляю следующую ситуацию: предположим у меня есть массив из N векторов узлов на сфере. Т.е. мне его предоставляют по моему требованию. Я могу запросить скажем: хочу сетку из 1000 узлов - мне вернули массив из этих 1000 векторов. Всё.. Я имею random access к нему, могу этот массив сортировать и т.д. Но я не знаю по какому принципу он строится, я имею дело только по факту..
Какова потановка вопроса в таком случае? Для любой точки на сфере найти все ближайшие к ней узлы, нах. внутри заданного телесного угла (из центра сферы).
Я правильно понимаю?


   
Я не совсем понимаю, что Вы имеете в виду под "мы умеем строить сферу из куба"..
   

Дан куб с центром в (0, 0, 0) и стороной 2 / sqrt(3) (чтобы половинка диагонали =  радиуc, удобнее считать ) Для каждой из его 6 граней берем 4 новых вертекса на середине каждого ребра + центр грани, итого 5. Нормируем эти вертексы (теперь они лежат на поверхности сферы). Теперь каждая грань разбита на 4 новых 4-угольника, повторяем все для них. См картинку выше.

Рассмотрим требуемый алгоритм на плоскости (это случай параллельного источника). Есть квадрат напр QRectF(-1, -1, 2, 2). Никаких узлов еще нет. Приходит запрос - посчитать данные напр в точке QPointF(0.27, 0.33) с точностью напр 0.1. Наши действия

- находим шаг сетки < требуемого, step = 0.0625

- находим индексы
  index_x = int((0.27 + 1) / step) 
  index_y = int((0.33 + 1) / step)

- тогда координаты 4 близлежащих узлов
  left_top_x = index_x * step - 1 
  left_top_y = index_y * step - 1
  и.т.д

- смотрим есть ли они в хеше (считались ли уже эти узлы). Ключ = пара индексов. Если нет, то считаем и пополняем хеш.

- интерполируем значение в заданной точке используя значения в узлах

Да, с квадратом-то все хорошо, но что делать для сферы? 

Это я знаю, но если вам принципиально нужны равные углы(мне с нормализованным квадратом проще работать было, а то что в центре квадратик чуть больше мне было неважно), то алгоритм нужно слегка изменить:
floor( xyz / step)*step или ceil ( xyz / step )*step нужно заменить, на что то типа atg( floor ( tg(xyz) / step2 ) * step2 ) это если в лоб (step2 = step*90).
Если не в лоб, то для каждого step создать массив( for(float a=-90; a<90; a+=180/step) array << atg(a)  ) и потом округлять xyz используя полученный массив std::lower_bound и предыдущий элемент.

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

p.s.s. А зачем вам это выравнивание? Кубик из равномерной сетки проще получить и работать с ним проще, а выигрыша в детализации с гулькин нос.

Можно организовать таблицу, с поиском ближайших узлов за O(ln(N)). Смотри схему ниже..

Как у Вас все легко и просто :) Но это не дает клеточек равного размера. По существу Вы предложили обычную полярную систему координат. Смотрим на глобус с нарисованными меридианами и параллелями - клетки там ну никак не равны

"Сетка" предполагает клеточки равного размера (ну хотя бы примерно). А если использовать сетку куба, то на сфере площадь "угловой" клетки будет в 4 раза меньше площади "центральной". Ничего себе гулькин "нос" :) Хуже того, клетки перестают быть квадратными, из пропорции теперь до 2:1. И что это за сетка такая?

Хранить саму сетку (в любом виде) = немедленная гибель по памяти. Хранятся только обсчитанные узлы, их обычно доли %

Нет у меня не полярная система, у меня куб в котором сетка не равномерная, а полученная через atg(формируется углом с одинаковым шагом). Потом нормализация этого куба до сферы. имхо площади будут одинаковые для всех кусочков.

Опишите алгоритм и формулу как вы получаете сферу? От этой формулы и будем плясать. мне кажеться через atg ресурсоемко слишком.
есть еще формулы https://math.stackexchange.com/questions/118760/can-someone-please-explain-the-cube-to-sphere-mapping-formula-to-me (https://math.stackexchange.com/questions/118760/can-someone-please-explain-the-cube-to-sphere-mapping-formula-to-me) может в них можно получить сферу с равными углами из куба с равномерной сеткой. ( у меня нормализация координат кусочков, это разделить на длину )

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

Давайте определимся как нарисовать сферу для заданного step, а потом и точки ближайшие найдем без перебора.

если найти обратную формулу(думаю не сложно) мы сможем ваш вектор на сферу превратить в вектор на куб с равномерной сеткой

https://stackoverflow.com/questions/2656899/mapping-a-sphere-to-a-cube (https://stackoverflow.com/questions/2656899/mapping-a-sphere-to-a-cube)
походу не совсем просто, ждем от вас работающую сборку этого ужаса... мне это тоже пригодиться чуть позже, наверное.

p.s. Есть ли исходники аналогов google earth? (детализация минимум до домов и ландшафт)

тут статейка появилась https://habrahabr.ru/post/335588/ (https://habrahabr.ru/post/335588/), может пригодиться

Так, ну вроде все есть, вот примерная ссылка (http://alexcpeterson.com/2010/04/23/sphere-to-cube-mapping/) где вся нужная математика. Итого

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

Ну с 6 гранями все-таки возиться придется. Ладно, не умрем, распишем свитчем. Конечно все это надо отладить и убедиться что формулы верные

deMax, спасибо за энтузиазм и толчок в нужном направлении