DGL • Thema anzeigen - Punkt auf Linie

Punkt auf Linie

Moderator: DGL-Team

Seite 1 von 1

[ 8 Beiträge ]

Vorheriges Thema | Nächstes Thema

Autor

Nachricht

j0hnnie

Betreff des Beitrags: Punkt auf Linie

Verfasst: Mo Jun 27, 2011 13:24

DGL Member

Registriert: Fr Mai 14, 2010 08:34
Beiträge: 54

Hallo Forum!

Ich render eine Vielzahl an Liniensegmenten und wollte nun herausfinden, auf welche Position auf der Linie der User geklickt hat.
Dafür wird erstmal mit der Vorhandenen Picking Prozedur das angeklickte Segment zurückgegeben. Dann projeziere ich das Segment mit den aktuellen OpenGL Matrizen mittel gluproject in den 2D Raum, berechne dann in 2D welcher Punkt auf der Linie den Mauskoordinaten am nächste kommt. Bzw. berechne ich eine Zahl u im Intervall 0...1, wobei 0=Startpunkt vom Segment und 1=Endpunkt vom Segment. Dann rechne ich mir mit diesem u einen Schnittpunkt auf dem Segment in 3D aus.
Hier mein Code:

Code:

function NearestPointOnSegment(Segment : TSegment) : TVertex;
var
  S, E : TVertexD;
  u : Double;
  Y_new : Integer;
begin
  Y_new := Viewport[3] - OGLFrame.YS;
  glGetDoublev(GL_MODELVIEW_MATRIX, @ModelMatrix);
  gluProject(Segment.S[0],Segment.S[1],Segment.S[2],ModelMatrix,ProjMatrix,Viewport,@S[0],@S[1],@S[2]);
  gluProject(Segment.E[0],Segment.E[1],Segment.E[2],ModelMatrix,ProjMatrix,Viewport,@E[0],@E[1],@E[2]);
  u:=((XS-S[0])*(E[0]-S[0])+(Y_new-S[1])*(E[1]-S[1]))/(sqr(E[0]-S[0])+sqr(E[1]-S[1]));
  if (u>0) and (u<1) then begin
    Result[0]:=Segment.S[0]+u*(Segment.E[0]-Segment.S[0]);
    Result[1]:=Segment.S[1]+u*(Segment.E[1]-Segment.S[1]);
    Result[2]:=Segment.S[2]+u*(Segment.E[2]-Segment.S[2]);
  end else begin
    Result[0]:=(Segment.S[0]+Segment.E[0])/2;
    Result[1]:=(Segment.S[1]+Segment.E[1])/2;
    Result[2]:=(Segment.S[2]+Segment.E[2])/2;
  end;
end;

Aber irgendwie funktioniert der Code nur machmal

Ich kriege irgendwie nicht raus, wo der Fehler liegt. Bitte helft mir

Nach oben

Coolcat

Betreff des Beitrags: Re: Punkt auf Linie

Verfasst: Mo Jun 27, 2011 15:12

DGL Member

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java

Du solltest u clampen. Es kann passieren das durch Rundungsfehler z.B. u = 1.001. In dem Fall würdest du dann plötzlich die Mitte des Liniensegmentes nehmen, das ist natürlich dann falsch.
Also:

Code:

u := max(min(u,1), 0);

_________________
Yeah! :mrgreen:

Nach oben

j0hnnie

Betreff des Beitrags: Re: Punkt auf Linie

Verfasst: Di Jun 28, 2011 10:19

DGL Member

Registriert: Fr Mai 14, 2010 08:34
Beiträge: 54

Danke für die Antwort. Das u trimme ich ja bereits, bzw. wenn 0<u<1, dann wird einfach der Mittelpunkt des Segments genommen.
Ich denke auch, dass das u korrekt berechnet wird und sich das u vielleicht garnicht 1 zu 1 in den 3D-Raum übertragen lässt. Vielleicht ist aber auch doch ein Fehler im Code.

Nach oben

Coolcat

Betreff des Beitrags: Re: Punkt auf Linie

Verfasst: Di Jun 28, 2011 10:29

DGL Member

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java

Zitat:

Das u trimme ich ja bereits, bzw. wenn 0<u<1, dann wird einfach der Mittelpunkt des Segments genommen.

Das ist ja genau das Problem. Nicht den Mittelpunkt nehmen sondern den jeweils näher gelegenen Endpunkt!

Zitat:

Ich denke auch, dass das u korrekt berechnet wird und sich das u vielleicht garnicht 1 zu 1 in den 3D-Raum übertragen lässt.

Streng genommen musst du die Projektion rückgängig machen. Z.B. via gluUnProject.

_________________
Yeah! :mrgreen:

Nach oben

SDH.Prod

Betreff des Beitrags: Re: Punkt auf Linie

Verfasst: Di Jun 28, 2011 10:36

DGL Member

Registriert: Sa Okt 18, 2008 11:59
Beiträge: 180

Ich versteh jetzt nur teilweise was du genau willst aber:

würde es nicht auch gehen die Fensterkoordinaten der Maus und den Tiefenwert (dürftest du mit glGet... bekommen) zu nutzen um mit Hilfe von gluUnProject (http://wiki.delphigl.com/index.php/gluUnProject) die Objektkoordinaten zu erhalten und dann zu prüfen wo die Linie diesen Punkt durchläuft / wo der Abstand von dem Punkt zur Linie am niedrigsten ist?

Nach oben

j0hnnie

Betreff des Beitrags: Re: Punkt auf Linie

Verfasst: Di Jun 28, 2011 12:00

DGL Member

Registriert: Fr Mai 14, 2010 08:34
Beiträge: 54

Es geht darum, dass ich erstmal mittels Selection das angeklickte Segment erhalte. Nur dieses überprüfe ich auf den Schnittpunkt. Dieses Segment soll durch den Klick aufgespalten werden. Wenn 0<u<1 ist, dann nehme ich die Mitte, damit ich auch Segmente, die auf dem Bildschirm sehr klein erscheinen, aufschneiden kann.

Wo und wie soll ich denn das glunproject verwenden? Dann würde ich doch wieder einen Punkt in 3D bekommen, der aber auch nicht exakt auf der Linie liegt, oder?

Nach oben

SDH.Prod

Betreff des Beitrags: Re: Punkt auf Linie

Verfasst: Di Jun 28, 2011 12:48

DGL Member

Registriert: Sa Okt 18, 2008 11:59
Beiträge: 180

Du erhältst einen 3D-Punkt, richtig. Aber deine Linie befindet sich ja auch im 3D-Raum.
Selbst wenn deine Linie den Z-Wert "1" hat, hat er trotzdem einen Z-Wert.
Indem Falle nutzt du als winZ (3. Parameter bei gluUnProject) den Wert "1".

Herausbekommen solltest du dann wie gesagt einen Punkt auf dieser Linie (bzw. durch leichte Rundungsfehler einen der SEHR NAHE an der Linie ist (das löst du dann wie bereits beschrieben mit Lotfußpunktverfahren (oder so ähnlich))).
--> Dieser sollte dann deinem Mauszeiger auch am nächsten liegen.

"0<u<1"
Sollte es nicht "0<=u<=1" heißen?

Nach oben

Coolcat

Betreff des Beitrags: Re: Punkt auf Linie

Verfasst: Di Jun 28, 2011 12:57

DGL Member

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java

Zitat:

Wo und wie soll ich denn das glunproject verwenden? Dann würde ich doch wieder einen Punkt in 3D bekommen, der aber auch nicht exakt auf der Linie liegt, oder?

gluUnProject funktioniert wie gluProject nur rückwärts. In dem Fall würdest du eben zwischen deinem S und E interpolieren und diese Koordinaten da wieder rein stecken. Wichtig ist das du die Z-Koordinate nicht vergisst und ebenfalls interpolierst, sonst funktioniert die Rückprojektion nicht richtig. ich war davon ausgegangen das du genau diesen Punkt in 3D haben wolltest

Zitat:

Dieses Segment soll durch den Klick aufgespalten werden.

Entscheidendes Detail, ein spalten an den Endpunkten macht natürlich keinen Sinn

Auf Grund dieser Info....völlig neuer Lösungsvorschlag der perspektivisch korrekt arbeitet:
Führe deine Berechnung in 3D durch Schneide deine Linie und den Cursor-Strahl der in den Bildschirm zeigt. Hier etwas Code...sorry, das eine ist C++, das andere Java....hatte auf die schnelle gerade nichts besseres.

Code:

/** finds an least squares solution for ao + s*ar = bo + t*br.
* @return Vector2(s,t) */
template<class T> inline Vector2<T> rayIntersect3D(const Vector3<T>& ao, const Vector3<T>& ar,
const Vector3<T>& bo, const Vector3<T>& br)
{
// ao + s*ar = bo + t*br
// <=> s*ar - t*br = bo - ao
// <=> A*X = B
// solve: A^T * A * X = A^T*B
// <=> AN * X = BN
// <=> X = AN^-1 * BN
Vector3<T> A0 = ar;
Vector3<T> A1 = -br;
Vector3<T> B = bo - ao;
// normal equations
Vector2<T> AN0(A0*A0, A1*A0); // *-operator ist dot-Produkt
Vector2<T> AN1(A0*A1, A1*A1);
Vector2<T> BN(A0*B, A1*B);
// check determinant of AN
T det = AN0.x*AN1.y - AN1.x*AN0.y;
if (-EPSILON < det && det < EPSILON) {
// both rays are nearly parallel
return Vector2<T>(B*ar / ar.lengthSq(), 0);
}
else {
// compute inverse(AN)^T
// used peusdocode from http://www.dr-lex.be/random/matrix_inv.html
det = 1.0f/det;
Vector2<T> iAN0T( AN1.y*det, -AN1.x*det);
Vector2<T> iAN1T(-AN0.y*det, AN0.x*det);
return Vector2<T>(iAN0T*BN, iAN1T*BN);
}
}

Code:

    public Ray getCursorRay(Matrix44d proj, Matrix44d view, Vector2i cursor) {
        Vector2i viewport = WebGL.getInstance().getFramebufferSize();
        Vector2i revcur = viewport.sub(cursor);
        Vector3d v = new Vector3d(
            -(2*revcur.x/(double)viewport.x - 1.0) / proj._00,
             (2*revcur.y/(double)viewport.y - 1.0) / proj._11,
             -1
        );
        Matrix44d invView = view.getOrthonormalInverse();
        Ray ray = new Ray();
        ray.dir.x = v.x*invView._00 + v.y*invView._10 + v.z*invView._20;
        ray.dir.y = v.x*invView._01 + v.y*invView._11 + v.z*invView._21;
        ray.dir.z = v.x*invView._02 + v.y*invView._12 + v.z*invView._22;
        ray.dir.normalize();
        ray.origin = invView.getW();
        return ray;
    }

_________________
Yeah! :mrgreen:

Nach oben

Seite 1 von 1

[ 8 Beiträge ]

Foren-Übersicht » Programmierung » Allgemein

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 8 Gäste

Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.