Координаты на сфере, составленной из треугольников
Всем доброго дня!
Возник у меня такой вопрос. Пусть у нас есть сфера, составленная из треугольников:
Пытаюсь сообразить, каким образом можно задать координаты каждому отдельному треугольнику.
Основная сложность - в поиске соседей для каждого треугольника. Я думал над различными вариантами, например, можно попробовать "развернуть" сферу в один большой треугольник, подразделенный на много маленьких, и составить правила, по которым можно будет найти для каждого треугольника 3 его соседа.
Если учесть, что сфера строится итеративно, т.е. начиная с тетраэдра, каждый шаг каждый треугольник делится на 4 маленьких треугольника, можно попробовать пронумеровать эти 4 под-треугольника. Тогда можно задать каждый из конечных треугольников серией чисел, каждое из которых будет определять более крупный треугольник. Но здесь с нахождением соседей еще сложнее...
Надеюсь, что кто-нибудь сможет подсказать мне что-то дельное по данному вопросу.
Интересует также поиск пути на подобной сфере с учетом направлений движения вдоль треугольников, но если найти способ определения соседей для каждого треугольника, в этом проблем не будет.
Самый очевидный способ задания координат на сфере, неожиданно, - сферические =)
А соседей для треугольника можно определить, если в каждом треугольнике ссылки на этих соседей хранить.
Тут что-то похожее обсуждалось:
http://www.gamedev.ru/code/forum/?id=67714
Спасибо за ссылку, полезная для меня информация! :-)
А нет ли какого простого способа как раз определять этих соседей при построении сферы? То есть, написать программу итеративного разбиения треугольников - несложно, а как определить, какие треугольники соседствуют с какими?
В голову приходит только вариант "в лоб" - брать каждый треугольник, брать три луча снаружи его сторон и, рекурсивно обходя структуру сферы, определять соседей.
Наверное, так и стоит делать, если учесть, что это произойдет один раз после построения - временные затраты получатся не слишком большими.
Deirel
> А нет ли какого простого способа как раз определять этих соседей при построении
> сферы? То есть, написать программу итеративного разбиения треугольников -
> несложно, а как определить, какие треугольники соседствуют с какими?
> В голову приходит только вариант "в лоб" - брать каждый треугольник, брать три
> луча снаружи его сторон и, рекурсивно обходя структуру сферы, определять
> соседей.
> Наверное, так и стоит делать, если учесть, что это произойдет один раз после
> построения - временные затраты получатся не слишком большими.
Для каждого треугольника храни ссылку на 3-х соседей (если важен переход через вершину, то 12). Для исходного тетраэдра задай вручную. Далее для каждого треугольника: делим его на 4, задаем ссылки у порожденных треугольников исходя из ссылок разделяемого треугольника. При делении ты сам задаешь какой треугольник с каким соседствует. Нарисуй на бумажке - сразу станет понятно.
Поискал у себя, нашел древний класс для работы с координатами на сфере, сделанной из разбиения икосаэдра:
+ Код
− Скрыть
#define LEAF_MASK 0x0F
#define DOWN_TRIANGLE 0x10
struct SphereIndex
{
unsigned long leaf, up, dn;
SphereIndex();
SphereIndex(unsigned long l, unsigned long u, unsigned long d);
bool operator == (SphereIndex &index);
bool operator != (SphereIndex &index);
bool operator >= (SphereIndex &index);
bool operator <= (SphereIndex &index);
bool operator > (SphereIndex &index);
bool operator < (SphereIndex &index);
int Compare(SphereIndex &index);
unsigned long GetOrder();
int Shift(int dir, unsigned long shift);
void Triangle(int dir, unsigned long size, bool cw);
};
SphereIndex::SphereIndex()
{
}
SphereIndex::SphereIndex(unsigned long l, unsigned long u, unsigned long d) : leaf(l), up(u), dn(d)
{
}
bool SphereIndex::operator == (SphereIndex &index)
{
return leaf == index.leaf && up == index.up && dn == index.dn;
}
bool SphereIndex::operator != (SphereIndex &index)
{
return leaf != index.leaf || up != index.up || dn != index.dn;
}
bool SphereIndex::operator >= (SphereIndex &index)
{
if(leaf > index.leaf)return true;
if(leaf < index.leaf)return false;
if(up > index.up)return true;
if(up < index.up)return false;
return dn >= index.dn;
}
bool SphereIndex::operator <= (SphereIndex &index)
{
if(leaf < index.leaf)return true;
if(leaf > index.leaf)return false;
if(up < index.up)return true;
if(up > index.up)return false;
return dn <= index.dn;
}
bool SphereIndex::operator > (SphereIndex &index)
{
if(leaf > index.leaf)return true;
if(leaf < index.leaf)return false;
if(up > index.up)return true;
if(up < index.up)return false;
return dn > index.dn;
}
bool SphereIndex::operator < (SphereIndex &index)
{
if(leaf < index.leaf)return true;
if(leaf > index.leaf)return false;
if(up < index.up)return true;
if(up > index.up)return false;
return dn < index.dn;
}
int SphereIndex::Compare(SphereIndex &index)
{
if(leaf > index.leaf)return 1;
if(leaf < index.leaf)return -1;
if(up > index.up)return 1;
if(up < index.up)return -1;
if(dn > index.dn)return 1;
if(dn < index.dn)return -1;
return 0;
}
unsigned long SphereIndex::GetOrder()
{
for(unsigned long mask = 1; mask; mask <<= 1)
if((up & mask) || (dn & mask))return mask;
return 0;
}
int SphereIndex::Shift(int dir, unsigned long shift)
{
if(leaf > 10)
{
leaf = ((unsigned)dir < 5 ? (dir << 1) + 1 : 1);
dn = -(signed)shift; return 0;
}
else if(leaf == 10)
{
leaf = ((unsigned)dir < 5 ? dir << 1 : 0);
up = -(signed)shift; return 2;
}
switch(dir)
{
case 0:
dn += shift;
if(dn)return 3;
if(!(leaf & 1))
{
leaf++; return 3;
}
else if(!up)
{
int res = leaf >> 1; leaf = 11; return res;
}
else
{
leaf = (leaf < 8 ? leaf + 2 : 1);
dn = -(signed)up; up = 0; return 4;
}
case 1:
up += shift; dn += shift;
if(!up)
{
if(!dn)
{
leaf = (leaf < 8 ? leaf + 2 : leaf - 8); return 4;
}
if(leaf & 1)
{
leaf = (leaf < 9 ? leaf + 1 : 0); return 4;
}
else
{
leaf = (leaf < 8 ? leaf + 2 : 0);
up = -(signed)dn; dn = 0; return 3;
}
}
if(dn)return 4;
if(!(leaf & 1))
{
leaf++; return 4;
}
else
{
leaf = (leaf < 8 ? leaf + 2 : 1);
dn = -(signed)up; up = 0; return 5;
}
case 2:
up += shift;
if(up)return 5;
if(leaf & 1)
{
leaf = (leaf < 9 ? leaf + 1 : 0); return 5;
}
else if(!dn)
{
int res = leaf >> 1; leaf = 10; return res;
}
else
{
leaf = (leaf < 8 ? leaf + 2 : 0);
up = -(signed)dn; dn = 0; return 4;
}
case 3:
dn -= shift;
if(dn != -(signed)shift)return 0;
if(leaf & 1)
{
leaf--; return 0;
}
else
{
leaf = (leaf > 1 ? leaf - 2 : 8);
dn = -(signed)up - shift; up = -(signed)shift; return 1;
}
case 4:
up -= shift; dn -= shift;
if(up == -(signed)shift)
{
if(dn == -(signed)shift)
{
leaf = (leaf > 1 ? leaf - 2 : leaf + 8); return 1;
}
if(!(leaf & 1))
{
leaf = (leaf > 0 ? leaf - 1 : 9); return 1;
}
else
{
leaf = (leaf > 1 ? leaf - 2 : 9);
up = -(signed)dn - shift; dn = -(signed)shift; return 0;
}
}
if(dn != -(signed)shift)return 1;
if(leaf & 1)
{
leaf--; return 1;
}
else
{
leaf = (leaf > 1 ? leaf - 2 : 8);
dn = -(signed)up - shift; up = -(signed)shift; return 2;
}
default:
up -= shift;
if(up != -(signed)shift)return 2;
if(!(leaf & 1))
{
leaf = (leaf > 0 ? leaf - 1 : 9); return 2;
}
else
{
leaf = (leaf > 1 ? leaf - 2 : 9);
up = -(signed)dn - shift; dn = -(signed)shift; return 1;
}
}
}
void SphereIndex::Triangle(int dir, unsigned long size, bool cw)
{
if(leaf > 10)
{
if(!cw)dir = (dir ? dir - 1 : 4);
leaf = ((unsigned)dir < 5 ? (dir << 1) + 1 : 1) | DOWN_TRIANGLE;
dn = -(signed)size; return;
}
else if(leaf == 10)
{
if(cw)dir = (dir < 4 ? dir + 1 : 0);
leaf = ((unsigned)dir < 5 ? dir << 1 : 0);
up = -(signed)size; return;
}
if(cw)dir = (dir ? dir - 1 : 5);
switch(dir)
{
case 0:
leaf |= DOWN_TRIANGLE; return;
case 1:
return;
case 2:
dn -= size;
if(dn != -(signed)size)
{
leaf |= DOWN_TRIANGLE; return;
}
if(leaf & 1)
{
leaf = (leaf - 1) | DOWN_TRIANGLE; return;
}
else
{
leaf = (leaf > 1 ? leaf - 2 : 8);
dn = -(signed)up - size; up = -(signed)size; return;
}
case 3:
dn -= size;
if(dn == -(signed)size)
{
if(!(leaf & 1))
{
leaf = (leaf > 1 ? leaf - 2 : 8); if(!cw || up)leaf |= DOWN_TRIANGLE;
dn = -(signed)up - size; up = -(signed)size; return;
}
up -= size;
if(up == -(signed)size)leaf = (leaf > 1 ? leaf - 2 : leaf + 8);
else leaf--; return;
}
up -= size;
if(up != -(signed)size)return;
if(!(leaf & 1))
{
leaf = (leaf > 0 ? leaf - 1 : 9); return;
}
else
{
leaf = (leaf > 1 ? leaf - 2 : 9) | DOWN_TRIANGLE;
up = -(signed)dn - size; dn = -(signed)size; return;
}
case 4:
up -= size;
if(up == -(signed)size)
{
if(leaf & 1)
{
leaf = (leaf > 1 ? leaf - 2 : 9); if(!cw && !dn)leaf |= DOWN_TRIANGLE;
up = -(signed)dn - size; dn = -(signed)size; return;
}
dn -= size;
if(dn == -(signed)size)leaf = (leaf > 1 ? leaf - 2 : leaf + 8) | DOWN_TRIANGLE;
else leaf = (leaf > 0 ? leaf - 1 : 9) | DOWN_TRIANGLE; return;
}
dn -= size;
if(dn != -(signed)size)
{
leaf |= DOWN_TRIANGLE; return;
}
if(leaf & 1)
{
leaf = (leaf - 1) | DOWN_TRIANGLE; return;
}
else
{
leaf = (leaf > 1 ? leaf - 2 : 8);
dn = -(signed)up - size; up = -(signed)size; return;
}
default:
up -= size;
if(up != -(signed)size)return;
if(!(leaf & 1))
{
leaf = (leaf > 0 ? leaf - 1 : 9); return;
}
else
{
leaf = (leaf > 1 ? leaf - 2 : 9) | DOWN_TRIANGLE;
up = -(signed)dn - size; dn = -(signed)size; return;
}
}
}
Код старый, поэтому говнокода хватает, но делает что надо.
Всем спасибо, я, как всегда, все усложнил =) Теперь все понятно))
}:+()___ [Smile] спасибо отдельное, что приложил усилия, нашел класс)