Есть задачка.
У меня есть obj файл
формат:
http://en.wikipedia.org/wiki/Wavefront_.obj_fileКоторый содержит некую более-менее симметричную модель (в данном, конкретном случае - голову)
Надо восстановить симметрию (чтоб было не "более менее").
Дополнительные условия:
Obj подготовлен для трансляции на directx, т.е.
-все полигоны - треугольные,
-количество пространственных и УВ координат совпадают.
-Файл содержит только один объект
Это все упрощения, если удасться довести всю эту фигню до ума - можно будет накручивать.
Под все это дело заготовлены следующие классы (конструкторы/ деструкторы опущены)
//используется для хранения координат вертекса. Все равно каких - UV или пространственных
class class_triple_float
{
public:
float f1,f2,f3;
} ;
//описывает полигон.Соответственно v - индекс пространственной координаты, vn - нормали, uv - UV координаты
class class_face
{
public:
int v[3];
int vn[3];
int uv[3];
};
//сам файл на всякий случай храню и текстовое и числовое представление вершин
class class_obj
{
public:
AnsiString o_name; // имя объекта
vector<AnsiString> v; // пространственные координаты - текстовое представление
vector<class_triple_float> tr_v; // пространственные координаты - численное представление
vector<AnsiString> vt; // UV координаты - текстовое представление
vector<class_triple_float> tr_vt; // UV координаты - численное представление
vector<AnsiString> f; // полигоны
vector<class_face> tr_f;
vector<int> v_vt; // соответствие индексов пространственных и текстурных координат v_vt[i] хранит номер индекс текстурных координат для i-ого вертекса.
};
Далее мы бежим по всему вектору tr_v, для каждой вершины инвертируем значение f1 (ось х) и ищем ближайшую точку в трехмерном пространстве
align_obj - объект класса class_obj, который мы правим
math_vector - считает длину вектора между двумя точками в трехмерном пространстве
align_index - вектор хранящий соответствующие индексы вершин, которые вроде-бы могут быть симметричны.
for (int i=0; i<align_obj.tr_v.size();i++)
{
int temp_index=0;
float temp_vector_lenght=math_vector(align_obj.tr_v[i].f1,align_obj.tr_v[i].f2,align_obj.tr_v[i].f3,align_obj.tr_v[0].f1,align_obj.tr_v[0].f2,align_obj.tr_v[0].f3);
for(int j=0; j<align_obj.tr_v.size();j++)
{
{
//if(i!=j) ***********************************************âîçìîæíî íàäî áóäåò âåðíóòü
//{
float temp_vector_lenght2;
temp_vector_lenght2=math_vector(align_obj.tr_v[i].f1,align_obj.tr_v[i].f2,align_obj.tr_v[i].f3,align_obj.tr_v[j].f1,align_obj.tr_v[j].f2,align_obj.tr_v[j].f3);
if (temp_vector_lenght>temp_vector_lenght2)
{
temp_vector_lenght=temp_vector_lenght2;
temp_index=j;
}
//}
}
}
vector_lenght[i]=temp_vector_lenght;
align_index[i]=temp_index;
}
Это грубо, и дает большую погрешность.
Затем мы проходим по массиву align_index и соответственно
if (i!=align_index[align_index[i]])
{
align_index[i]=-1;
align_index[align_index[i]]=-1;
}
Т.е. две вроде-бы симметричные точки, ссылаются не друг на друга. Значит определили неверно. Записываем им в align_index -1, (-1 используется как признак того, что симметрия для этой точке не определена).
Пока все понятно. А вот дальше начинается свистопляска - у нас есть вектор align_index, часть вершин в котором вообще непонятно на что ссылаются.
Я решил построить массив родственников - т.е. вершин, имеющих с ней общие ребра
family_v [i] .vert_ar[k]
- точка i связана с точками из массива vert_ar
for (int i=0; i<align_obj.tr_v.size();i++)
{
{
vector<int>temp_family_v; //временный список родственников
temp_family_v.clear();
for(int j=0; j<align_obj.tr_f.size();j++) //бежим по вектору полигонов
{
if((align_obj.tr_f[j].v[0]==i)||(align_obj.tr_f[j].v[1]==i)||(align_obj.tr_f[j].v[2]==i))
{
if(align_obj.tr_f[j].v[0]!=i) temp_family_v.push_back(align_obj.tr_f[j].v[0]);
if(align_obj.tr_f[j].v[1]!=i) temp_family_v.push_back(align_obj.tr_f[j].v[1]);
if(align_obj.tr_f[j].v[2]!=i) temp_family_v.push_back(align_obj.tr_f[j].v[2]);
}
}
for(int j=0;j<temp_family_v.size();j++) //выбираем повторяющиеся вершины (если два вертекса принадлежат одновременно нескольким полигонам)
{
bool sort_flag=true;
for(int k=0;k<family_v[i].vert_ar.size();k++) //
{
if (family_v[i].vert_ar[k]==temp_family_v[j]) sort_flag=false;
}
if (sort_flag)
{
family_v[i].vert_ar.push_back(temp_family_v[j]);
}
}
bool puzir_flag=false;
//сортировка пузырьком
do
{
puzir_flag=false ;
if(family_v[i].vert_ar.size()>1)
{
for(int j=0;j<family_v[i].vert_ar.size()-1;j++)
{
if(family_v[i].vert_ar[j]>family_v[i].vert_ar[j+1])
{
int temp_ver_ind=family_v[i].vert_ar[j];
family_v[i].vert_ar[j]=family_v[i].vert_ar[j+1];
family_v[i].vert_ar[j+1]=temp_ver_ind;
puzir_flag++;
}
}
}
}
while(puzir_flag);
}
}
Далее еще раз проходим по нашему align_index, и если i вершина имеет меньше кокого-то порогового значения родственников (3) ссылающихся на соответствующих родственников вершины align_index
тоже считаем что симметрию определили неверно.
Потом начинаем бегать по массиву и считать ссылки
do
{
int vertex_found=0;
do
{
vertex_found=0;
for(int i=0;i<align_index.size();i++)
{
if (align_index[i]==-1)
{
for(int j=0;j<align_index.size();j++)
{
if((align_index[j]==-1))//&&(i!=j))
{
int family_found=0;
for(int ik=0; ik<family_v[i].vert_ar.size();ik++)
{
for(int jk=0; jk<family_v[j].vert_ar.size();jk++)
{
if(family_v[i].vert_ar[ik]==align_index[family_v[j].vert_ar[jk]])
{
family_found++;
}
}
}
if(family_found>=family_max)
{
align_index[i]=j;
align_index[j]=i;
vertex_found++;
align_vector[i]=family_found;
align_vector[j]=family_found;
family_v[i].vert_ar.push_back(family_found);
family_v[j].vert_ar.push_back(family_found);
family_max=base_family_max;
}
}
}
}
}
}
while(vertex_found>0) ;
family_max--;
}
while(family_max>=min_family_max) ;
Т.е. если две вершины имеют достаточно большое число ссылающихся друг на друга родственников - считаем их симметричными.
Алгоритм сложный и косячный, часть вершин ошибочно ссылаются на вершины с теми-же пространственными координатами, (швы) себя самих, и непонятно что еще.
Что посоветуете?