Überschneidungsstrahl gegen kubisches Bezier -Dreieck erkennen und finden

Question

Während ich einen Modellredakteur schreibe, kann ich neben der Aktivierung von Raytracing über ein paar Operationen nachdenken, bei denen ich eine sehr gute Annäherung über den Schnittpunkt zwischen einem Strahl und einem dreieckigen Bezier -Patch finden möchte.

Wie macht man das? Ich kenne ein paar Möglichkeiten, aber wahrscheinlich gibt es bessere.

Genaue Anwendungsfälle: Ich möchte vielleicht einen Bezier-Dreieck-Patch als Referenzoberfläche zum Zeichnen detaillierter Formen mit Maus verwenden. Vielleicht möchte ich auch einen Spaltpunkt aus einem solchen Patch bestimmen.

Wenn es C -Quellcode dafür gibt, möchte ich das vielleicht auch sehen. Vielleicht verwenden Sie es sogar, anstatt meinen eigenen Code zu rollen.

Answer 1

Ich würde vorschlagen, dass Sie implementieren Dreiecksbezier Clipping (PDF).

Eine andere Möglichkeit wäre jedoch, Ihren dreieckigen Patch in ein Tensor-Produkt-Bezier-Patch umzuwandeln. Der Vorteil, dies zu tun, besteht darin, dass die Tensor-Produkt-Beziers viel mehr Unterstützung gibt, sodass Sie eher einen Code finden, den Sie verwenden können. Die Konvertierung ist einfach:

• Sehen Sie sich Ihren dreieckigen Patch als eine Reihe von N+1 -Zeilen von Kontrollpunkten an (wobei n der Grad ist)
  • Die erste Zeile hat 1 Kontrollpunkt und jede Zeile hat 1 mehr Kontrollpunkt als die letzte
• Behandeln Sie nun jede Reihe als Bezier -Kurve des entsprechenden Grades (Grad 0 bis Grad N)
• Grad erhöhen jede Reihe zu Grad n n
  • Jede Zeile hat nun N+1 -Steuerpunkte und bildet ein N+1 durch N+1 -Gitter von Kontrollpunkten
• Dieses Raster von Punkten, das als Grad n von n Bezier Patch genommen wird, ist eine identische Oberfläche Ihres Dreiecks

Um nur Schnittpunkte zu finden, sollte dies gut funktionieren. Ihr Tensor-Produkt-Patch ist jedoch degeneriert (Sie haben übereinstimmende Punkte an einem Ende), sodass Sie möglicherweise feststellen, dass Sie einige numerische Probleme einführen, wenn Sie sich der entarteten Ecke nähern. Die Kartierung in die dreieckige Domäne kann auch Dinge wie Texturzuordnung etwas besonders schwierig machen. Daher würde ich vorschlagen, dass Sie den direkteren dreieckigen Bezier -Clipping verwenden, wenn es Ihnen nichts ausmacht.

Answer 2

Ich bin mit einem dreieckigen Bezier -Patch nicht vertraut, aber wenn es immer in einem Dreieck enthalten sein kann, muss es auch die Kurve in sich kreuzen, wenn der Strahl das Dreieck schneidet.

Wenn das obige wahr ist, können Sie die Kurve zwischen den beiden Eckpunkten durchsuchen, deren Seite den Strahl nach einem Punkt überschneidet, der nahe genug am Strahl ist. Ich denke, Sie können eine binäre Suche nach dem Kurvenparameter in diesem Bereich durchführen, um diesen Punkt zu erhalten.