Projektion eines Splines < Interpol.+Approx. < Numerik < Hochschule < Mathe < Vorhilfe
|
Hallo zusammen!
Ich sitze jetzt schon einige Zeit an meinem Projekt und komme nicht mehr weiter... Ich habe nämlich folgendes Problem: Ich möchte gern einen 3D Spline (bisher verwende ich kubische Splines) auf die Oberfläche eines beliebigen 3D Körpers projizieren. Die Oberfläche des Körpers ist dabei als Dreiecksnetz gegeben.
Den Spline habe ich bereits berechnet und ich bin noch soweit gekommen, dass die Stützstellen des Splines auch alle auf der Oberfläche liegen. Jedoch kommt es bei meinen Versuchen immer mal wieder vor, dass der Spline ein wenig "ausschwingt" und dann in den Körper hineinragt.... das sollte natürlich vermieden werden.
Meine grobe Idee ist nun, dass ich irgendwie den Schnittpunkt von Spline und Oberfläche herausfinde und dann einen (oder mehrere) Punkt(e) aus diesem Intervall hernehme und irgendwie auf die Oberfläche projiziere.
Aber wie ihr vielleicht schon merkt, hab ich noch keine wirkliche Vorstellung wie das funktionieren soll.
Hat irgendjemand schon einmal etwas ähnliches versucht und könnte mir einen Tipp geben?
Oder gibt es irgendwelchen Source Code zu diesem Thema? Ich hab schon eine Weile gegoogelt aber nichts brauchbares gefunden.
Ich bin für jede Hilfe/Tipp dankbar!
Liebe Grüße, girlie
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo girlie0016, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
wenn Du Deinen Spline auf eine triangulierte Oberfläche projizierst (Schatten, nehme ich an?), dann kannst Du Dich ja von einem einzelnen Dreieck aus vortasten. Nimm die Ebene, in der das Dreieck liegt, und projiziere den Spline darauf. Ragt der Schatten über eine Dreieckskante, so schneide ihn dort ab und geh zum benachbarten Dreieck. Dort geht das ganze von vorn los.
Nicht ganz einfach ist es allerdings, einen sinnvollen Schleifenaufbau zu finden, so dass Du die nötigen Dreiecke vollständig und möglichst linear abschreitest. Ein Hindernis dabei ist, dass die Zahl der Dreiecke, die eine Ecke umschließen, normalerweise variabel ist (und bei guten Triangulationen mindestens fünf beträgt).
Ob es dafür fertigen Code gibt, weiß ich aber nicht, deswegen lasse ich die Frage halboffen. Dann wird sie leichter von anderen gefunden.
Grüße
reverend
|
|
|
| |
|
hallo reverend!
danke für deine antwort und die hilfe! Ich habe wirklich sehr darauf gehofft, dass mir jemand weiterhelfen kann!
Also grundsätzlich soll diese ganze projektion des splines in einem eigens implementierten viewer eingesetzt werden. zur zeit ist es möglich, dass der user einen 3d körper in den viewer lädt und danach einige punkte auf dem körper anklickt und durch diese punkte wird dann ein spline berechnet.
also meine idee wäre jetzt (nach deinem ansatz) die:
1. ich starte vom 1.stützpunkt des splines aus. für diesen punkt weiß ich bereits auf welchem dreieck der triangulierung des körpers dieser liegt.
2. ich berechne die ebene in der das dreieck liegt und nehmen einen nächsten punkt auf dem spline und projiziere diesen senkrecht auf die ebene.
ok, soweit könnte das funktionieren. was mir aber noch nicht so klar ist, ist wie ich feststellen kann, auf welches dreieck ich die weiteren punkte projizieren soll. wie kann ich feststellen, dass ich für den betrachteten punkt zum nächsten dreieck "springen" muss?
Angenommen ich wüsste wann ich zum nächsten dreieck gehen muss, wie kann ich dann das "richtige" der mind. 5 benachbarten dreiecke finden? das einzige auswahlkriterium, dass mir gerade einfällt wäre, das dreieck mit dem kürzesten abstand zum betrachteten punkt zu wählen? oder liege ich da falsch?
Ich würde mich sehr freuen, wenn du mir noch einen tipp geben könntest! danke!
Liebe Grüße, girlie
|
|
|
| |
|
Hallo girlie,
ich wundere mich gerade, warum den ganzen Tag niemand geantwortet hat. Es müsste hier eigentlich mindestens einige (wenn nicht viele) geben, die es besser können und wissen als ich. Ich habe mich mehr mit 2D-sprites als 3D-splines beschäftigt. Aber solange sonst niemand antwortet, will ichs gern weiter versuchen.
> Also grundsätzlich soll diese ganze projektion des
> splines in einem eigens implementierten viewer eingesetzt
> werden. zur zeit ist es möglich, dass der user einen 3d
> körper in den viewer lädt und danach einige punkte auf
> dem körper anklickt und durch diese punkte wird dann ein
> spline berechnet.
Der Spline ist also eigentlich ein Teilkörper, jedenfalls wenn der geladene 3D-Körper konvex ist? Aber wozu dann die Projektion?
> also meine idee wäre jetzt (nach deinem ansatz) die:
> 1. ich starte vom 1.stützpunkt des splines aus. für
> diesen punkt weiß ich bereits auf welchem dreieck der
> triangulierung des körpers dieser liegt.
> 2. ich berechne die ebene in der das dreieck liegt und
> nehmen einen nächsten punkt auf dem spline und projiziere
> diesen senkrecht auf die ebene.
> ok, soweit könnte das funktionieren. was mir aber noch
> nicht so klar ist, ist wie ich feststellen kann, auf
> welches dreieck ich die weiteren punkte projizieren soll.
> wie kann ich feststellen, dass ich für den betrachteten
> punkt zum nächsten dreieck "springen" muss?
Das ist noch einfach. Nimm eine Gerade durch den ersten betrachteten Punkt im Spline, die verschieden von der Projektionsgeraden ist. Verfolge diese Gerade, solange sie innerhalb des Splines verläuft. Dazu sind vor allem Geraden geeignet, die parallel zur Projektionsfläche (also dem Dreieck) verlaufen. Untersuche die Projektion der Geraden. Wenn sie auf eine der Dreiecksseiten trifft, ohne dass zugleich eine Grenze des Splines erreicht ist, dann musst du das benachbarte Dreieck als nächstes untersuchen. Dieses ist ja eindeutig zu bestimmen, wenn die Projektion der Geraden nicht durch eine Ecke des Dreiecks verläuft (was äußerst unwahrscheinlich ist). Sollte der Fall doch eintreten, musst Du die zu projizierende Gerade minimal drehen (und dabei möglichst parallel zur Projektionsebene, also dem Dreieck, belassen).
> Angenommen ich wüsste wann ich zum nächsten dreieck gehen
> muss, wie kann ich dann das "richtige" der mind. 5
> benachbarten dreiecke finden? das einzige auswahlkriterium,
> dass mir gerade einfällt wäre, das dreieck mit dem
> kürzesten abstand zum betrachteten punkt zu wählen? oder
> liege ich da falsch?
Nein, es ist bedeutend einfacher, das Nachbardreieck zu nehmen, das mit dem bisherigen Projektionsdreieck die Kante gemeinsam hat, die von der Projektion der Spline-Geraden geschnitten wird.
> Ich würde mich sehr freuen, wenn du mir noch einen tipp
> geben könntest! danke!
Hoffentlich ist das verständlich formuliert...
Grüße
reverend
|
|
|
| |
|
Hallo girlie,
reverend wundert sich, dass sonst noch niemand geantwortet
hat. Das liegt möglicherweise daran, dass die Aufgabe, die
du dir gestellt hast, wirklich nicht einfach ist. Ein paar
Gedanken dazu habe ich mir zwar schon gemacht, aber ich
schwankte zwischen verschiedenen Ideen und kam dabei zu
keinem klaren Schluss.
Ich reportiere kurz, wie ich mir deine Frage vorstelle:
Du hast einen Körper, der durch ein Triangulationsnetz
definiert ist, also eigentlich ein Polyeder mit (recht vielen)
Dreiecksfacetten. Auf der Oberfläche des Polyeders hast
du eine Folge [mm] [/mm] von Punkten, von
denen jeder in einer gewissen Facette des Polyeders liegt.
Nun möchtest du, ausgehend von einer Spline-Kurve s,
die durch alle Punkte [mm] P_i [/mm] (i=1 ... n) verläuft, eine Kurve k
konstruieren, die auf der Oberfläche des Polyeders ver-
läuft.
Ist meine Darstellung soweit richtig ?
Falls etwas nicht passt, bitte berichtigen !
Und falls man deine Fragestellung geometrisch ver-
einfacht darstellen kann, dann sag das bitte ebenfalls !
Nun denke ich, dass die Aufgabe wohl mit vertretbarem
Aufwand zu lösen sein sollte, falls z.B. das Polyeder konvex
und die Anzahl seiner Facetten nicht groß ist. In diesem
Fall kann man die Projektionen der Spline-Kurve s auf die
Oberfläche des Polyeders stückweise berechnen und
zusammensetzen. Sie wird dann aber aus einzelnen
Stücken bestehen, die an den Facettenkanten jeweils
in einem Knick ineinander übergehen.
Hat aber das Polyeder sehr viele Facetten (für eine
realistische und "glatte" Darstellung der gekrümmten
Fläche), dann wird wohl der Rechenaufwand astronomisch,
wenn man keine Vorkehrungen trifft, um sich nur mit
jenen Facetten beschäftigen zu müssen, die wenigstens
in der Nähe der gesuchten Kurve k liegen ...
Im Moment sehe ich also keine "raffinierte" Methode
zur Lösung deines Problems. Ich kann mir aber vor-
stellen, dass richtige Freaks der 3D-Grafik (wo man es
bestimmt auch mit dem Schattenwurf von Kurven auf
Flächen zu tun hat) weiterhelfen könnten ...
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 02:42 Sa 29.10.2011 | | Autor: | reverend |
Hallo nochmal,
Al hat (wie eigentlich immer) Recht. Das Problem, welche Dreiecke zu bearbeiten sind, lässt sich allerdings noch ziemlich vereinfachen.
Dazu projiziert man sowohl den Spline als auch den triangulierten Körper in der gewünschten Projektionsrichtung (allerdings aus entgegengesetzen Richtungen!) auf die gleiche Ebene. Dann ist es relativ einfach, einen Algorithmus zu finden, der die "äußeren" Dreiecke des "Schattens" identifiziert, nämlich gerade die, bei denen eine oder oder zwei Seiten nicht überschritten werden. Von dort kann man sich dann vorarbeiten zu den nächstgelegenen Dreiecken, die komplett im Schatten liegen. So ergibt sich ein recht enger Rand des Splineschattens auf der Körperoberfläche.
Für diesen äußeren Rand muss man die SplineProjektion genauer betrachten. Je größer der "Schatten", umso größer die Ersparnis, da die vom Schatten erfassten Dreiecke mit der Größe (im Sinne von: dem gemittelten Durchmesser oder dem Umfang) des Schattens insgesamt quadratisch wachsen, der beschriebene Rand aber nur "etwas" mehr als linear.
Grüße
reverend
PS: Nebenbei - diese Probleme sind sicher bereits alle gelöst. Gibt es dazu wirklich keine nützliche Publikation? Gerade in den letzten wenigen Jahren sind doch immer besser computeranimierte Filme bis hin zu den aktuellen 3D-Filmen entstanden. Frag doch mal bzw. mach Dich auf die Suche, wo dazu mehr steht.
Außer der rein mathematischen Lösung geht es dabei ja auch noch um Laufzeitoptimierung.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:23 Sa 29.10.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Hallo girlie0016,
falls es sich bei der Fläche um eine ganz beliebige Fläche
im Raum handelt, kann ich nicht wirklich weiter helfen.
Sollte es sich aber z.B. um eine Rotationsfläche mit
bekannter Erzeugendenfunktion handeln, so ist das
Problem deutlich einfacher. Ich habe mir dafür eine
näherungsweise Projektionsmethode gerade zurecht-
gelegt, die anscheinend recht gut funktioniert. Das hat
allerdings nichts mit einer triangulierten Fläche zu tun.
LG Al-Chw.
|
|
|
|
