Построение фигуры по координатам

[alex_alv]

В первом приближении порылся в своем бардаке, и диска не нашел. Может быть найдется еще. Самому жалко будет, если пропал.

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

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

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

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

 

[C'mon]

Спасибо огромное за помощь! Буду дальше разбираться.

 

[fm4]

А может вы выложите пример где нибудь? ИМХО, все равно снимались координаты в ручную или каким либо автоматическим методом.
Мне кажется что по облаку точек уже можно строить предположения. На пример можно построить граф расстояний от каждой точки до всех остальных. А по нему уже искать четыре ближайшие точки.

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

 

[C'mon]

В файле более 67000 строк, могу скинуть файл не полностью, а где-нибудь треть от общего количества строк, но смысл из них думаю будет понятен.

 

[alex_alv]

Скрипт и картинка, что полчилось. Описание - следом.


string $FileName="e:\\test\\test\\test.asc";
global float $maxdistance=2.0,$minsin=0.2,$minfaceangle=2.0;
global int $moveCam=1;


int $Handle;
int $i,$j,$k;
string $nextLine,$scoords[];
global float $verts[];
global int $edgescount[],$edgeslinks[],$edges[],$facescount[],$faces[],$faceslink[],$newverticies[],$filledverts[];
global int $vcount,$enum,$facenum,$nvcount;

proc addNewVert(int $vn)
{
global int $edgescount[],$edgeslinks[],$edges[],$facescount[],$faces[],$faceslink[],$newverticies[];
global int $vcount,$enum,$facenum,$nvcount;

$newverticies[$nvcount]=$vn;
$nvcount++;
}

proc int GetSecondVirtex(int $fv)
{
global float $verts[];
global int $edgescount[],$edgeslinks[],$edges[],$facescount[],$filledverts[];
global int $vcount,$enum;
global float $maxdistance;
int $i,$sv,$j,$k;
float $dist,$mindist,$x,$y,$z;

$sv=-1;
for($i=0;$i<$vcount;$i++)
if(($i!=$fv)&&($filledverts[$i]==0))
{
$k=1;
for($j=0;($k)&&($j<$edgescount[$fv]);$j++)
if(($edges[$edgeslinks[$j*$vcount+$fv]*2]==$i)||($edges[$edgeslinks[$j*$vcount+$fv]*2+1]==$i))
if($facescount[$edgeslinks[$j*$vcount+$fv]]>1)$k=0;
if($k)
{
$x=$verts[$fv*3]-$verts[$i*3];
$y=$verts[$fv*3+1]-$verts[$i*3+1];
$z=$verts[$fv*3+2]-$verts[$i*3+2];
$dist=sqrt($x*$x+$y*$y+$z*$z);
if($dist<=$maxdistance)
{
if(($sv<0)||($dist<$mindist))
{
$mindist=$dist;
$sv=$i;
}
}
}
}
return $sv;
}

proc int GetThirdVirtex(int $fv, int $sv, int $exept, int $prefv)
{
global float $verts[];
global int $edgescount[],$edgeslinks[],$edges[],$facescount[],$filledverts[],$faces[],$faceslink[];
global int $vcount,$enum,$facenum;
global float $maxdistance,$minsin,$minfaceangle;
int $i,$tv,$j,$k,$come,$comf;
float $dist,$mindist,$x,$y,$z,$la,$ca;
vector $v1,$v2,$v3,$v4,$v5,$vt1,$vt2,$vt3;

$v1=<<$verts[$fv*3],$verts[$fv*3+1],$verts[$fv*3+2]>>;
$v2=<<$verts[$sv*3],$verts[$sv*3+1],$verts[$sv*3+2]>>-$v1;
if($prefv>=0)
{
$v5=<<$verts[$prefv*3],$verts[$prefv*3+1],$verts[$prefv*3+2]>>-$v1;
}
if($exept>=0)
{
$v3=<<$verts[$exept*3],$verts[$exept*3+1],$verts[$exept*3+2]>>-$v1;
$v3=cross($v2,$v3);
}

$tv=-1;
for($i=0;$i<$vcount;$i++)
if(($i!=$fv)&&($i!=$sv)&&($i!=$exept)&&($filledverts[$i]==0))
{
$v4=<<$verts[$i*3],$verts[$i*3+1],$verts[$i*3+2]>>-$v1;
$k=1;
for($j=0;($k)&&($j<$edgescount[$fv]);$j++)
if(($edges[$edgeslinks[$j*$vcount+$fv]*2]==$i)||($edges[$edgeslinks[$j*$vcount+$fv]*2+1]==$i))
if($facescount[$edgeslinks[$j*$vcount+$fv]]>1){$k=0;if($i==$prefv)print("Disabled because 2 faces at fv\n");}
else if($facescount[$edgeslinks[$j*$vcount+$fv]])
{
$come=$edgeslinks[$j*$vcount+$fv];
$vt1=-$v4;
$vt2=<<$verts[$sv*3],$verts[$sv*3+1],$verts[$sv*3+2]>>-<<$verts[$i*3],$verts[$i*3+1],$verts[$i*3+2]>>;
$comf=$faceslink[$come*2];
if( ($faces[$comf*3]!=$come) && ( ($edges[2*$faces[$comf*3]]==$i) || ($edges[2*$faces[$comf*3]+1]==$i) ) )$come=$faces[$comf*3];
else if( ($faces[$comf*3+1]!=$come) && ( ($edges[2*$faces[$comf*3+1]]==$i) || ($edges[2*$faces[$comf*3+1]+1]==$i) ) )$come=$faces[$comf*3+1];
else $come=$faces[$comf*3+2];
if($edges[2*$come]==$i)$come=$edges[2*$come+1];
else $come=$edges[2*$come];
$vt3=<<$verts[$come*3],$verts[$come*3+1],$verts[$come*3+2]>>-<<$verts[$i*3],$verts[$i*3+1],$verts[$i*3+2]>>;
if(dot(cross($vt1,$vt2),cross($vt1,$vt3))>=0){$k=0;if($i==$prefv)print("Disabled because wrong direction at fv: "+$vt1+", "+$vt2+", "+$vt3+"\n");}
}
for($j=0;($k)&&($j<$edgescount[$sv]);$j++)
if(($edges[$edgeslinks[$j*$vcount+$sv]*2]==$i)||($edges[$edgeslinks[$j*$vcount+$sv]*2+1]==$i))
if($facescount[$edgeslinks[$j*$vcount+$sv]]>1){$k=0;if($i==$prefv)print("Disabled because 2 faces at sv\n");}
else if($facescount[$edgeslinks[$j*$vcount+$sv]])
{
$come=$edgeslinks[$j*$vcount+$sv];
$vt1=<<$verts[$sv*3],$verts[$sv*3+1],$verts[$sv*3+2]>>-<<$verts[$i*3],$verts[$i*3+1],$verts[$i*3+2]>>;
$vt2=-$v4;
$comf=$faceslink[$come*2];
if( ($faces[$comf*3]!=$come) && ( ($edges[2*$faces[$comf*3]]==$i) || ($edges[2*$faces[$comf*3]+1]==$i) ) )$come=$faces[$comf*3];
else if( ($faces[$comf*3+1]!=$come) && ( ($edges[2*$faces[$comf*3+1]]==$i) || ($edges[2*$faces[$comf*3+1]+1]==$i) ) )$come=$faces[$comf*3+1];
else $come=$faces[$comf*3+2];
if($edges[2*$come]==$i)$come=$edges[2*$come+1];
else $come=$edges[2*$come];
$vt3=<<$verts[$come*3],$verts[$come*3+1],$verts[$come*3+2]>>-<<$verts[$i*3],$verts[$i*3+1],$verts[$i*3+2]>>;
if(dot(cross($vt1,$vt2),cross($vt1,$vt3))>=0){$k=0;if($i==$prefv)print("Disabled because wrong direction at sv\n");}
}
if($k)
{
$x=$verts[$fv*3]-$verts[$i*3];
$y=$verts[$fv*3+1]-$verts[$i*3+1];
$z=$verts[$fv*3+2]-$verts[$i*3+2];
$dist=sqrt($x*$x+$y*$y+$z*$z);
$x=$verts[$sv*3]-$verts[$i*3];
$y=$verts[$sv*3+1]-$verts[$i*3+1];
$z=$verts[$sv*3+2]-$verts[$i*3+2];
$dist+=sqrt($x*$x+$y*$y+$z*$z);
if($prefv==$i)
{
// $dist*=0.6;
print("Pref distance = "+($dist/0.6)+", scaled = "+$dist+"\n");
}
if($dist<=($maxdistance*1.9))
{
if(($tv<0)||($dist<$mindist))
{
$ca=sin(angle($v4,$v2));
if(($prefv>=0)&&($k)&&($prefv!=$i))
{
if(dot(cross($v2,$v5),cross($v4,$v5))<=0)
if((dot($v4,$v5)>0)||(dot($v2,$v5)>0))$k=0;
}
if(($exept>=0)&&($k))
{
$v4=cross($v2,$v4);
//if(dot($v3,$v4)>=0)$k=0;
if(angle($v3,$v4)<$minfaceangle)$k=0;
}
if($k)
{
$mindist=$dist;
$tv=$i;
$la=$ca;
}
}
}
}
}
if($la<$minsin)return -1;
print("Sin angle = "+$la+", min dist = "+$mindist+"\n");
return $tv;
}

proc int AddEdge(int $fv, int $sv)
{
global float $verts[];
global int $edgescount[],$edgeslinks[],$edges[],$facescount[];
global int $vcount,$enum;
int $i,$j;

if($fv==$sv)return -1;
if($fv>$sv)
{
$i=$fv;
$fv=$sv;
$sv=$i;
}

for($j=0;$j<$edgescount[$fv];$j++)
if($edges[$edgeslinks[$j*$vcount+$fv]*2+1]==$sv)
return ($edgeslinks[$j*$vcount+$fv]);
$edges[$enum*2]=$fv;
$edges[$enum*2+1]=$sv;
$edgeslinks[$edgescount[$fv]*$vcount+$fv]=$enum;
$edgeslinks[$edgescount[$sv]*$vcount+$sv]=$enum;
$enum++;
$edgescount[$fv]=$edgescount[$fv]+1;
$edgescount[$sv]=$edgescount[$sv]+1;
return ($enum-1);
}

proc int buildFace(int $fv, int $sv, int $tv)
{
global float $verts[];
global int $edgescount[],$edgeslinks[],$edges[],$facescount[],$faces[],$faceslink[];
global int $vcount,$enum,$facenum,$moveCam;

string $fname[];

$fname=`polyCreateFacet -ch 0 -p ($verts[$fv*3]) ($verts[$fv*3+1]) ($verts[$fv*3+2]) -p ($verts[$sv*3]) ($verts[$sv*3+1]) ($verts[$sv*3+2]) -p ($verts[$tv*3]) ($verts[$tv*3+1]) ($verts[$tv*3+2])`;
//currentTime -u 1 1;
if($moveCam)fitPanel -selected;
refresh;
$faces[$facenum*3]=AddEdge($fv,$sv);
$faces[$facenum*3+1]=AddEdge($fv,$tv);
$faces[$facenum*3+2]=AddEdge($sv,$tv);
if($facescount[$faces[$facenum*3]]<2)
{
$faceslink[$facescount[$faces[$facenum*3]]+$faces[$facenum*3]*2]=$facenum;
$facescount[$faces[$facenum*3]]=$facescount[$faces[$facenum*3]]+1;
}
if($facescount[$faces[$facenum*3+1]]<2)
{
$faceslink[$facescount[$faces[$facenum*3+1]]+$faces[$facenum*3+1]*2]=$facenum;
$facescount[$faces[$facenum*3+1]]=$facescount[$faces[$facenum*3+1]]+1;
}
if($facescount[$faces[$facenum*3+2]]<2)
{
$faceslink[$facescount[$faces[$facenum*3+2]]+$faces[$facenum*3+2]*2]=$facenum;
$facescount[$faces[$facenum*3+2]]=$facescount[$faces[$facenum*3+2]]+1;
}
$facenum++;
print("Create "+$fname[0]+": "+$fv+" "+$sv+" "+$tv+"\n");
// if($facenum>38) pause -sec 5;
return ($facenum-1);
}

proc buildaround(int $fv)
{
global float $verts[];
global int $edgescount[],$edgeslinks[],$edges[],$facescount[],$faces[],$faceslink[],$filledverts[];
global int $vcount,$enum,$facenum;

int $stedge,$lastface,$nextedge,$i,$j,$lastv,$prefv,$conte;

if($filledverts[$fv])return;

move -a -ws $verts[$fv*3] $verts[$fv*3+1] $verts[$fv*3+2] locator1;

$filledverts[$fv]=1;
$stedge=$edgeslinks[($edgescount[$fv]-1)*$vcount+$fv];


if($edges[$stedge*2]==$fv) $j=$edges[$stedge*2+1];else$j=$edges[$stedge*2];
move -a -ws $verts[$j*3] $verts[$j*3+1] $verts[$j*3+2] locator2;


$lastface=$faceslink[$stedge*2];
$nextedge=$stedge;
while($lastface>=0)
{
if($edges[$nextedge*2]==$fv)$lastv=$edges[$nextedge*2+1];
else $lastv=$edges[$nextedge*2];
if(($nextedge!=$faces[$lastface*3])&&(($edges[$faces[$lastface*3]*2]==$fv)||($edges[$faces[$lastface*3]*2+1]==$fv)))$nextedge=$faces[$lastface*3];
else if(($nextedge!=$faces[$lastface*3+1])&&(($edges[$faces[$lastface*3+1]*2]==$fv)||($edges[$faces[$lastface*3+1]*2+1]==$fv)))$nextedge=$faces[$lastface*3+1];
else $nextedge=$faces[$lastface*3+2];

if($nextedge==$stedge) return;
else if($facescount[$nextedge]<2)
{
if($edges[$nextedge*2]==$fv)$prefv=$edges[$nextedge*2+1];
else $prefv=$edges[$nextedge*2];
$conte=$nextedge;
$lastface=-1;
}else
{
if($faceslink[$nextedge*2]==$lastface)$lastface=$faceslink[$nextedge*2+1];
else $lastface=$faceslink[$nextedge*2];
}
}


move -a -ws $verts[$prefv*3] $verts[$prefv*3+1] $verts[$prefv*3+2] locator3;
refresh;


// print("Found last: "+$conte+" v="+$prefv+", st="+$stedge+"\n");

$nextedge=$stedge;
if($facescount[$stedge]==1)
{
$lastface=$faceslink[$stedge*2];
if($edges[$stedge*2]==$fv)$i=$edges[$stedge*2+1];
else $i=$edges[$stedge*2];

if(($nextedge!=$faces[$lastface*3])&&(($edges[$faces[$lastface*3]*2]==$fv)||($edges[$faces[$lastface*3]*2+1]==$fv)))$nextedge=$faces[$lastface*3];
else if(($nextedge!=$faces[$lastface*3+1])&&(($edges[$faces[$lastface*3+1]*2]==$fv)||($edges[$faces[$lastface*3+1]*2+1]==$fv)))$nextedge=$faces[$lastface*3+1];
else $nextedge=$faces[$lastface*3+2];
if($edges[$nextedge*2]==$fv)$lastv=$edges[$nextedge*2+1];
else $lastv=$edges[$nextedge*2];
$nextedge=$stedge;

$j=GetThirdVirtex($fv,$i,$lastv,$prefv);
// print("V1= "+$fv+" v2="+$i+", v3="+$j+", lastv="+$lastv+",pref="+$prefv+"\n");
if($j<0)return;
$lastface=buildFace($fv,$i,$j);
addNewVert($j);
}else $lastface=$faceslink[$stedge*2+1];

while($lastface>=0)
{
if($edges[$nextedge*2]==$fv)$lastv=$edges[$nextedge*2+1];
else $lastv=$edges[$nextedge*2];
if(($nextedge!=$faces[$lastface*3])&&(($edges[$faces[$lastface*3]*2]==$fv)||($edges[$faces[$lastface*3]*2+1]==$fv)))$nextedge=$faces[$lastface*3];
else if(($nextedge!=$faces[$lastface*3+1])&&(($edges[$faces[$lastface*3+1]*2]==$fv)||($edges[$faces[$lastface*3+1]*2+1]==$fv)))$nextedge=$faces[$lastface*3+1];
else $nextedge=$faces[$lastface*3+2];

if($nextedge==$conte)return;
else if($facescount[$nextedge]<2)
{
if($edges[$nextedge*2]==$fv)$i=GetThirdVirtex($fv,$edges[$nextedge*2+1],$lastv,$prefv);
else $i=GetThirdVirtex($fv,$edges[$nextedge*2],$lastv,$prefv);
if($i<0)
{
$lastface=-1;
if($edges[$nextedge*2]==$fv)$prefv=$edges[$nextedge*2+1];
else $prefv=$edges[$nextedge*2];
$stedge=$nextedge;
}
else
{
$lastface=buildFace($edges[$nextedge*2],$edges[$nextedge*2+1],$i);
addNewVert($i);
}
}else
{
if($faceslink[$nextedge*2]==$lastface)$lastface=$faceslink[$nextedge*2+1];
else $lastface=$faceslink[$nextedge*2];
}
}


move -a -ws $verts[$prefv*3] $verts[$prefv*3+1] $verts[$prefv*3+2] locator3;
refresh;



if($facescount[$conte]>1)return;

$nextedge=$conte;
$lastface=$faceslink[$conte*2];
if($edges[$conte*2]==$fv)$i=$edges[$conte*2+1];
else $i=$edges[$conte*2];

if(($nextedge!=$faces[$lastface*3])&&(($edges[$faces[$lastface*3]*2]==$fv)||($edges[$faces[$lastface*3]*2+1]==$fv)))$nextedge=$faces[$lastface*3];
else if(($nextedge!=$faces[$lastface*3+1])&&(($edges[$faces[$lastface*3+1]*2]==$fv)||($edges[$faces[$lastface*3+1]*2+1]==$fv)))$nextedge=$faces[$lastface*3+1];
else $nextedge=$faces[$lastface*3+2];
if($edges[$nextedge*2]==$fv)$lastv=$edges[$nextedge*2+1];
else $lastv=$edges[$nextedge*2];
$nextedge=$conte;

$j=GetThirdVirtex($fv,$i,$lastv,$prefv);
if($j<0)return;
$lastface=buildFace($fv,$i,$j);
addNewVert($j);
while($lastface>=0)
{
if($edges[$nextedge*2]==$fv)$lastv=$edges[$nextedge*2+1];
else $lastv=$edges[$nextedge*2];
if(($nextedge!=$faces[$lastface*3])&&(($edges[$faces[$lastface*3]*2]==$fv)||($edges[$faces[$lastface*3]*2+1]==$fv)))$nextedge=$faces[$lastface*3];
else if(($nextedge!=$faces[$lastface*3+1])&&(($edges[$faces[$lastface*3+1]*2]==$fv)||($edges[$faces[$lastface*3+1]*2+1]==$fv)))$nextedge=$faces[$lastface*3+1];
else $nextedge=$faces[$lastface*3+2];

if($nextedge==$stedge)return;
else if($facescount[$nextedge]<2)
{
if($edges[$nextedge*2]==$fv)$i=GetThirdVirtex($fv,$edges[$nextedge*2+1],$lastv,$prefv);
else $i=GetThirdVirtex($fv,$edges[$nextedge*2],$lastv,$prefv);
if($i<0) $lastface=-1;
else
{
$lastface=buildFace($edges[$nextedge*2],$edges[$nextedge*2+1],$i);
addNewVert($i);
}
}else
{
if($faceslink[$nextedge*2]==$lastface)$lastface=$faceslink[$nextedge*2+1];
else $lastface=$faceslink[$nextedge*2];
}
}
}

if(!`objExists "locator1"`) spaceLocator -p 0 0 0 -n "locator1";
if(!`objExists "locator2"`) spaceLocator -p 0 0 0 -n "locator2";
if(!`objExists "locator3"`) spaceLocator -p 0 0 0 -n "locator3";

$Handle=`fopen $FileName "r"`;
if($Handle==0)error("Can not open file.\n");
print("Reading verticies...\n");
$vcount=0;
clear($verts);
while ( !`feof $Handle` )
{
$nextLine = `fgetline $Handle`;
while( (endsWith($nextLine,"\n")) || (endsWith($nextLine,"\r")) || (endsWith($nextLine," ")) || (endsWith($nextLine,"\t")) )
{
$i=`size($nextLine)`;
if($i<2)$nextLine="";
else $nextLine=substring($nextLine,1,$i-1);
}
while( (startsWith($nextLine,"\n")) || (startsWith($nextLine,"\r")) || (startsWith($nextLine," ")) || (startsWith($nextLine,"\t")) )
{
$i=`size($nextLine)`;
if($i<2)$nextLine="";
else $nextLine=substring($nextLine,2,$i);
}
if(size( $nextLine ) > 0 )
{
$scoords=`stringToStringArray $nextLine " "`;
if(size($scoords)!=0)
{
if(size($scoords)!=3)
{
fclose($Handle);
error("Incorrect number of vertex coordinates in the file: "+size($scoords)+"; `"+$nextLine+"`");
}
$verts[$vcount*3]=$scoords[0];
$verts[$vcount*3+1]=$scoords[1];
$verts[$vcount*3+2]=$scoords[2];
$vcount++;
}
}
}
fclose($Handle);
print($vcount+" verticies read.\n");

clear($edgescount);
clear($edgeslinks);
clear($edges);
clear($facescount);
$enum=0;
$facenum=0;
clear($newverticies);
clear($filledverts);
$nvcount=0;

for($i=0;$i<$vcount;$i++)
//for($i=5000;$i<5050;$i++)
{
print("Virtex "+$i+"\n");
move -a -ws 0 0 0 locator1;
move -a -ws 0 0 0 locator2;
move -a -ws 0 0 0 locator3;
if($edgescount[$i]==0)
{
$j=GetSecondVirtex($i);
if($j>=0)
{
$k=GetThirdVirtex($i,$j,-1,-1);
if($k>=0)
{
addNewVert($j);
addNewVert($k);
buildFace($i,$j,$k);
}
}
}
if($edgescount[$i])buildaround($i);
while($nvcount)
{
$nvcount--;
$j=$newverticies[$nvcount];
buildaround($j);
// if($facenum>500)error;
}
// if($facenum>553)error;
}

 

[alex_alv]

Этот скрипт пытается построить фэйсики по точкам, указанным в файле в текстовом виде (в каждой строке - три числа x пробел y пробел z)
Фэйсики получаются треугольными.
Каждый фэйс в виде отдельной поверхности.

Для форимрования окончательной поверхности следует выполнить combine (лучше по частям, а то мая вываливается) ПРИ ОТКЛЮЧЕННОЙ ИСТОРИИ И UNDO, затем Merge, затем Conform normals, затем Soften Edge.

Запускать скрипт лучше при отключенной истории и undo.

Работает медленно, так как вся работа визуализируется, и потому что скрипт.

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

Все парамтеры скрипта - в первых его строчках:
string $FileName="e:\\test\\test\\test.asc";
global float $maxdistance=2.0,$minsin=0.2,$minfaceangle=2.0;
global int $moveCam=1;

$FileName - имя файла с координатами
$maxdistance - максимальное расстояние между вершинами, которые могут быть соединены edge-ом
$minsin - минимальный синус угла основной вершины треугольника, меньше которого фэйс строиться не будет
$minfaceangle - минимальный угол между фэйсами.
$moveCam - перемещать камеру к строящемуся фэйсику (1) или не трогать камеру, но построение показывать (0).

Алгоритм примерно следующий:
берется вершина и обстраивается по-кругу вокруг нее треугольными фэйсиками. Это делается в функции buildaround. Требования к ней: у вершины уже должен быть минимум один фэйсик и не должно быть больше одной дырки.
При построении скрипт избегает больше двух фэйсов у одного ребра и ряд других исключений.
После обстроения, аналогичная операция применяется к каждой вершине, к которой только что были подключены новые фэйсики.

 

[alex_alv]

Кстати, скрипт написан на скорую руку и не претендует на отсутствие ошибок.
Геометрию он строит скорее всего тоже не самую качественную, но думаю руками ее до ума довести можно.

 

[C'mon]

Что я могу сказать, только огромное спасибо!
К сожалению, сейчас ухожу, но завтра обязательно посмотрю, что получилось.
Думаю придётся не мало времени потратить, чтобы в этом разобраться, но тем интереснее.
Ещё раз спасибо Вам, alex_alv.

 

[alex_alv]

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

$vcount - количество вершин.

$verts[] - считанные из файла вершины. Если за n принять номер вершины, то элемент n*3 содержит x, n*3+1 - y, n*3+2 - z. Размер массива - $vcount*3

$edgescount[] - содержит количество ребер, выходящих из каждой вершины. n-ый элемент указывает количество ребер из n-й вершины. Размер массива - $vcount.

$edgeslinks[] - содержит номера ребер , выходящих из каждой вершины. Для вершины n номер k-того ребра (k - от 0 до $edgescount[n]-1) находится в элменте n+$vcount*k (здесь k - локальный для данной вершины номер ребра , а $edgeslinks[n+$vcount*k] - глобальный для всей геометрии номер ребра .
Т. е. первые $vcount элементов содержат номера нулевых ребер, для каждой вершины, вторые $vcount элементов - номера первых и т. д. Номера ребер соответствуют массивам $edges[] и $facescount[]

$edges[] - описание всех ребер геометрии. Для глобального номера ребра m, элемент массива m*2 указывает номер первой вершины ребра, m*2+1 - номер второй вершины. Т. е. каждое ребро обозначается двумя элементами массива. Размер массива = текущее количество ребер * 2.

$facescount[] - количество фэйсиков для каждого ребра. Для глобального номера ребра m, элемент $facescount[m] указывает, сколько фэйсов касается данного ребра. Минимальное значение - 0, максимальное - 2. Размер массива равен текущему количеству ребер.

$faces[] - описание всех фэйсов. Каждый фэйс задается тремя элементами массива. В элементах указываются глобальные номера ребер, окружающих данный фэйс (каждый фэйс состоит из трех ребер). Для фэйса i, элемент i*3 - первое ребро, i*3+1 - второе, i*3+2 - третье.

$faceslink[] - содержит для каждого ребра номера фэйсов, подключенных к ребру. Каждое ребро описывается двумя элементами подряд. Для ребра m, элемент $faceslink[m*2] указывает номер первого фэйса (если $facescount[m]>=1), а элемент $faceslink[m*2+1] - номер второго фэйса (если $facescount[m]>=2)

$newverticies[] - массив, запоминающий, какие вершины были задействованы при обстроении текущей вершины (этот массив используется для того, чтобы следующими обстраивать вершины, занесенными в него). Предназначен для того, чтобы избежать рекурсии вызовов функций (чтобы не переполнить стек вызовов).

$filledverts[] - массив, который указывает, какие вершины были обстроены, а какие - нет. Если элемент n равен 0, значит вершина n еще не обстраивалась и к ней еще можно подключать новые ребра/фэйсы. Если равен 1, значит вершина уже обстроена и к ней запрещено подключение новых ребер, а кроме того, функция builaround не будет ничего делать с этой вершиной и сразу же возвращает управление.

 

[fm4]

Прикольный сканер. Он у вас точки случайно не теряет?

Я тут немного по игрался в свободное время. Алгоритм еще до конца не доведен, а потому некоторые фэйсы пропадают.
В итоге получается такой вот объект. Один и только с квадратными гранями. Работает быстро - больше всего времени уходит на парсинг, само построение граней получилось очень быстро.

Похоже на чью-то ногу

 

[C'mon]

теряет, но в основном не в той части, которую я Вам скинул.

 

[alex_alv]

Интересно (если не скерет), что это за часть, которую нам НЕ скинул?

 

[C'mon]

Такие части не скидывают ;-)

 

[Andrey83]

В Риноцеросе есть подходящая функция...

 

[Andrey83]

Хотя и не очень подходящая....

 

[C'mon]

Коллеги =)
Нужен скрипт, который будет по координатам строить выпуклый многоугольник. То есть у меня есть облако точек, я из них выбираю точки определенного сечения своей 3D-модели (точки с одинаковым значением по оси Y) и их надо соединить кривой, так чтобы они (кривые) не пересекались и обходили вершины в одном направлении (по часовой или против часовой стрелки). Может есть у кого-нибудь подобный скрипт в наличии? В интернете есть много подобных алгоритмов, но я достаточно ограничен во времени, чтобы их переделывать, поэтому буду очень благодарен за помощь.