Triangulation / lin. 2D-Interpolation

[ghostcrab]

MoinMoin,

ich suche einen Algorithmus, mit dem ich auf einer Oberfläche interpolieren kann.
Die Fläche isst durch n Stützvektoren (x,y,z) definiert. Ich möchte jetzt für beliebige (x,y)-Wertepaare den Zugehörigen z-Wert berechnen. Ich habe mir das so vorgestellt, dass man zunächst trianguliert, dh aus den Stützvektoren ein Netz aus Dreiecken generiert, dann das Dreieck sucht, in dem der gesuchte x,y-Punkt liegt und auf dieser Dreiecksfläche linear interpoliert.
Sowei ih weiss ist das ein Standardverfahren, dass bei jeder 3D-Grafik gebraucht wird, daher habe ich eigentlich keine Lust, das nochmal neu zu programmieren.
Hat hier jemand ein Snippet dafür oder einen Link?
Grazias!

[TGGC]

Sowas geht nicht eindeutig in 3D. Angenommen deine Stützstellen sind (0,0,z); (1,0,z); (1,1,z); (0,1,z) mit z= 0,1,2,3. Dann könnte man daraus zwei Würfel machen aber auch einen länglichen Quader.

Benutze also die Lösung für 2D, in dem du nur x und y von deinen Stützstellen beachtest, wenn du triangulierst.


Bye, TGGC

[Blue Cobold]

Wie kann eine Fläche durch EINEN Stützvektor definiert sein?

[Diogenes]

Vielleicht durch eine Funktion f: z = f(x, y)

Man kann so z.b. Kugelachteln definieren: z = sqrt( r^2 - x^2 - y^2) mit der üblichen Einschränkung, daß der Radiant und r >= 0 sind. r ist der Radius

[Blue Cobold]

Na ich glaub nicht, dass er das triangulieren und interpolieren will... das ginge einfacher.

[TGGC]

Wie kann eine Fläche durch EINEN Stützvektor definiert sein?Eine Ebene senkrecht zum Vektor und mit Abstand v*v von 0 kann man so problemlos definieren. Oder geht es dir garnicht um das "einen"?


Bye, TGGC

[ghostcrab]

?? Wie kommt Ihr denn auf das Zitat "EINEN" Stützvektor? Ich habe geschrieben "n" (beliebige Anzahl) an Stützvektoren.
Beispiel habe ich angehängt.

Ich habe also die Vektoren (0,0,17), (0,80,5), (200,60,33), (400,0,87) usw...
Ich möchte jetzt den Z-Wert an der Stelle (320,43) berechnen.
Jetzt muss ich also zunächst das Dreieck bestimmen, in dem (320,43) liegt. Das sieht in diewem Beispiel ziemlich einfach aus, ist es aber in der Praxis nicht. Aber dafür gibts wohl den Delauny-Alorithmus, damit hat man schonmal die Dreiecke. Auf dieser Dreiecksfläche kann man dann linear interpolieren.

Das ist, wie schon gesagt, ein häufig verwendetes Verfahren, deshalb habe ich eigentlich keine Lust, das nochmal zu programmieren. Daher auch die Frage, ob irgendjemand weiss, wo es da ein Code-Snippet gibt.
(In Matlab zB würde ich erst mit der MeshGrid-Funktion auf ein equidistantes Gitter interpolieren und daraus dann 2D-linear interpolieren. Ich brauche aber C-Code, nicht Matlab-Funktionen)

Alles unklar??

[Blue Cobold]

Hmmm, joar, ich hab das "n" vor 2 Tagen noch als Anzahl gelesen, aber gestern war wohl Aussetzer und habs als " 'n " gelesen als Abkürzung für "einen". :P
Sorry wegen der Verwirrung.
Also die Polygone hast du schon? Na dann is doch wunderbar, dann biete ich dir diesen meinen Code an, in der Hoffnung, dass er dir was nützt:

CompleteVertex MESH_BUILDER::GetInnerVertexDatas( CompletePolygon Target,
CVector3 Point)
{
CompleteVertex Ret;
Ret.Vertex = Point;
// zuerst eine Gerade bilden von einem Eckpunkt, durch den Cut
// und in Richtung der gegenüberliegenden Kante (1-2)
float len1 = Magnitude(Target.Vertex[1]-Target.Vertex[0]);
float len2 = Magnitude(Target.Vertex[2]-Target.Vertex[0]);
if (len2>len1)
len1 = len2;
CVector3 Dir = 1.1f*len1*Normalize(Point - Target.Vertex[0]);

CVector3 PNormal = Normal(Target.Vertex);
// Ebene an der Kante (1-2) erstellen
CVector3 temp[3];
temp[0] = Target.Vertex[1]+PNormal;
temp[1] = Target.Vertex[1];
temp[2] = Target.Vertex[2];
CPlane4 EdgePlane = MakePlane(temp);
CVector3 EdgeCut;
CrossPlaneWithLine( EdgePlane, Target.Vertex[0],
Target.Vertex[0]+Dir,&EdgeCut);
// Schnittpunkt erhalten, also dessen Normale und Tex-Coord rausfinden
// und dessen Tex-Coords berechnen
float CutDist = Magnitude( EdgeCut - Target.Vertex[1]);
if (CutDist!=0)
{ // durch lineare Interpolation berechnen
float EdgeLen= Magnitude( Target.Vertex[2] - Target.Vertex[1]);
float _EdgeLen = 1/EdgeLen;
Ret.Normal = (EdgeLen-CutDist)*_EdgeLen*Target.Normal[1]
+CutDist*_EdgeLen*Target.Normal[2];
Ret.TexCoord = (EdgeLen-CutDist)*_EdgeLen*Target.TexCoord[1]
+CutDist*_EdgeLen*Target.TexCoord[2];
}
else
{ // einfach nur übernehmen
Ret.Normal = Target.Normal[1];
Ret.TexCoord = Target.TexCoord[1];
}
// ok, aber das war noch nicht ganz korrekt... das waren ja nur die Edge-Datas
CutDist = Magnitude( Target.Vertex[0] - Point);
if (CutDist!=0)
{ // durch lineare Interpolation berechnen
float EdgeLen= Magnitude( EdgeCut - Target.Vertex[0]);
float _EdgeLen = 1/EdgeLen;
Ret.Normal = (EdgeLen-CutDist)*_EdgeLen*Target.Normal[0]
+CutDist*_EdgeLen*Ret.Normal;
Ret.TexCoord = (EdgeLen-CutDist)*_EdgeLen*Target.TexCoord[0]
+CutDist*_EdgeLen*Ret.TexCoord;
}
else
{ // einfach nur übernehmen
Ret.Normal = Target.Normal[0];
Ret.TexCoord = Target.TexCoord[0];
}
// fertig, also zurück
return Ret;
}


Is etwas grausam und bestimmt nicht optimal. Zusätzlich berechnet das Ding keine dritte Koordinate, sondern die Normale und Textur-Koordinaten im gegebenen Punkt. Aber wenn du's auf 2D abänderst und die Textur-Koordinaten ersetzt durch die z-Koordinate die du suchst, dann funktioniert das Ganze natürlich genauso. Also etwas Arbeit gleibt dir wohl noch. Was wohl ebenfalls für die verwendeten Funktionen gilt... falls du noch keine Äquivalente dazu haben solltest...
Im Prinzip macht er das:
Er zeichnet eine Gerade von einer Ecke durch den gesuchten Punkt und schneidet diese Gerade mit der gegenüberliegenden Ecke. Damit können schonmal die Daten (z.B. der Z-Wert ;-) für diesen Punkt bestimmt werden (mit den Daten der anderen beiden Ecken und den Längenverhältnissen der soeben geteilten Kante). Dann wird geschaut, wie lang dieser Vektor von der Ecke bis zum Schnittpunkt ist und wie lang der Vektor zwischen Ecke und gesuchtem Punkt ist. Und dann wird mit diesem Quotienten wieder zwischen Ecke und Schnittpunkt interpoliert. Funktioniert bei mir ganz gut.

[TGGC]

Da ist so aber keine Triangtulation in 3D, sondern der bekannte 2D Fall. Und es sind auch keie Stützvektoren, sondern Stützstellen der Form z= f( x, y ). Nur so als Hinweis für die weitere Suche.


Bye, TGGC