Russian Qt Forum
Март 28, 2024, 16:31 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1] 2   Вниз
  Печать  
Автор Тема: Сетка на сфере (решено)  (Прочитано 15693 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« : Август 17, 2017, 15:45 »

Добрый день

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

Спасибо
« Последнее редактирование: Август 22, 2017, 09:24 от Igors » Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #1 : Август 17, 2017, 16:35 »

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

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

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #2 : Август 18, 2017, 06:27 »

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

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

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

Вообщем как всегда - постановка никакая(    
Как всегда - ни идей, ни техники, только пустопорожние претензии  Плачущий
Записан
ssoft
Программист
*****
Offline Offline

Сообщений: 574


Просмотр профиля
« Ответ #3 : Август 18, 2017, 07:46 »

Посмотрите здесь http://gis-lab.info/qa/triangular-mesh-sphere.html.
Скорее всего хотелось бы что-то типа такого.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #4 : Август 18, 2017, 08:19 »

Посмотрите здесь 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
Хакер
*****
Offline Offline

Сообщений: 600



Просмотр профиля
« Ответ #5 : Август 18, 2017, 08:28 »

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

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

« Последнее редактирование: Август 18, 2017, 08:36 от deMax » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #6 : Август 18, 2017, 08:55 »

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

Сообщений: 600



Просмотр профиля
« Ответ #7 : Август 18, 2017, 09:34 »

Так этот комок 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
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #8 : Август 18, 2017, 10:24 »

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

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
deMax
Хакер
*****
Offline Offline

Сообщений: 600



Просмотр профиля
« Ответ #9 : Август 18, 2017, 12:21 »

С того что многие алгоритмы это делают. См аттач. Кубик можно рассматривать как сферу разбитую на 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
Хакер
*****
Offline Offline

Сообщений: 600



Просмотр профиля
« Ответ #10 : Август 18, 2017, 12:35 »

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

это если сфера получается нормализацией куба покрытого равномерной сеткой, а если сетка неравномерная(сплюснута к центру граней, чтобы при натягивании на сферу компенсировать увеличение этих граней) придется усложнить алгоритм. Можно сохранить в массив позиции сетки на кубе и округлять до них....
« Последнее редактирование: Август 18, 2017, 12:42 от deMax » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #11 : Август 18, 2017, 15:08 »

deMax, сетка что "равномерна на кубе" не будет "равномерна на сфере" и наоборот (см. вттвч). Др словами медиана не равна биссектрисе
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #12 : Август 18, 2017, 15:21 »

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

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

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

Сообщений: 2094



Просмотр профиля
« Ответ #13 : Август 18, 2017, 16:17 »

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

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

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

Всё) 
Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #14 : Август 19, 2017, 11:18 »

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

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

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

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

Да, чуть не забыл! А может это просто есть а boost'e? Нет, серьезно - Вы даже не представляете с каким огромным энтузиазмом я буду это место изучать  Улыбающийся
« Последнее редактирование: Август 19, 2017, 11:22 от Igors » Записан
Страниц: [1] 2   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.144 секунд. Запросов: 23.