Oberflächenrekonstruktion

[audacia]

Ich habe eine diskrete topographische Aufnahme (d.h. zu jedem (x,y)-Wertepaar gibt es einen Höhenwert z). Darauf gibt es Vertiefungen, die ich auffinden kann und durch ihren Umriß (eine Kette von (x,y)-Werten) beschreibe. Jetzt möchte ich wissen, wie das Gelände aussähe, wenn die Vertiefung nicht da wäre.

Schön anschauliches Beispiel: ich habe das und möchte das rekonstruieren, ausgehend vom Umriß der Einbuchtung.

Dazu beabsichtige ich, ein paar Punkte zu nehmen, die weiter außen liegen, mit ihren Gradienten einen Haufen Stützpunkte zu extrapolieren und dann sowas wie eine Bézier-Fläche oder ein NURBS zu bestimmen. Das sollte eigentlich auch funktionieren.

Mein Problem ist nun, daß die Bézier-Fläche und alle verwandten Konstruktionen eine Flächenparametrisierung voraussetzen. Ich brauche aber deren Projektion in mein herkömmliches Koordinatensystem. Die Bézier-Flächenfunktion gibt mir einen (x,y,z)-Wert für Flächenkoordinaten (u,v) - aber wie komme ich von den globalen Koordinaten (x,y) zum zugehörigen Funktionswert z? (Eigentlich hat jede 3D-Graphikkarte dasselbe Problem, nur arbeitet sie mit einem bereits triangulisierten Modell.) Mir ist klar, daß es dazu keine eindeutige Lösung geben muß, da die Projektion die Dimension reduziert; bei einer Mehrdeutigkeit nähme ich einfach den Punkt mit dem kleineren z-Wert. (Das Problem sollte realiter sowieso nicht auftreten, weil es in meinen topographischen Aufnahmen naturgemäß keine Überhänge gibt.)

Was ist der effizienteste Ansatz, um für jede (x,y)-Position die z-Position des auf (x,y) projizierten Punktes meiner Bézier-Fläche zu finden?

Bisher fällt mir dazu nur der übliche Ansatz zum Zeichnen von Bézier-Kurven ein: Man bleibt im Parametersystem (u,v), schätzt eine Schrittweite ab, bestimmt dann für alle (u,v) die Projektion (x,y,z) und trägt bei (x,y) den z-Wert ein. Dann wäre die Frage, was man an den (x,y)-Positionen macht, auf die nichts projiziert wurde.

[Mups]

Guck mal unter http://www.cs.jhu.edu/~misha/ nach Poisson Surface Reconstruction
Da gibt es Paper und sogar fertigen, recht einfach zu verwendenen Code dazu.

Letztlich wird aus Punkten auf der Oberfläche und den Normalenvektoren an diesen Stellen eine glatte Oberfläche rekonstruiert. Ich meine mich zu erinnern, dass das nur für geschlossene Körper geht - dann müsstest du deine Oberfläche irgendwie nach unten hin erweitern und schliessen. Vielleicht ist das auch nicht notwendig, dann muss der Algorithmus 'raten', wie es nach unten weitergeht. Am Ende schneidest du die neue Oberfläche ab und behälst nur die neue "Bergspitze" und fügst das mit der alten Oberfläche zusammen.

Du packst alle Punkte deiner Fläche rein, aber nicht bei dem Loch, dass du ausgleichen möchtest. Die Normalen direkt an der Kante von deinem Loch musst du anpassen. Evtl. kannst du ja probieren, ob durch raten einzelner weiterer Punkte (zb das Maximum?) ein schöneres Ergebnis rauskommt. Vielleicht hilft es auch, das Verfahren nur lokal anzuwenden - das macht vielleicht auch das schliessen des Körpers nach unten hin einfacher.

Einfach spielen und schauen, ob es dir weiterhilft. Falls es weiterhilft, kannst du ja mal Bilder posten Vielleicht ist das Verfahren aber für dein Problem auch nicht ganz geeignet - einfach ausprobieren!

[audacia]

Zunächst danke für die Antwort. Auf Poisson Surface Reconstruction und speziell das Paper von Kazhdan, Bolitho und Hoppe bin ich natürlich auch gestoßen (ist ja bei den Treffern recht weit oben, wenn man nach "surface reconstruction" sucht). Aber ich glaube nicht, daß das adäquat ist: ich habe ja keine dichte Punktwolke, die möglichst in der Oberfläche liegen soll; im umrissenen Gebiet habe ich nur extrapolierte Stützstellen, und die liegen explizit nicht in der Fläche. Das fällt nicht unter "noisy". Vielleicht würde es reichen, wenn ich die Extrapolationsgeschichte weglasse und tatsächlich nur die Punkte außerhalb und ihre Gradienten nehme; aber die Poisson-Geschichte ist für gleichförmige Punktverteilungen gemacht, und obzwar sie durch Variation der Kernelbreite für ungleichförmige Verteilungen benutzbar wird, glaube ich nicht, daß sie mit so einer Extremsituation (viele Punkte außerhalb, keine Punkte innerhalb meines Umrisses) besser klarkommt als der Ansatz mit einer Bézier-Fläche.

Allerdings habe ich ja nicht nach Alternativen zur Bézier-Methode gefragt - mit der bin ich eigentlich soweit zufrieden -, sondern suche nach einem effizienten Ansatz für die Projektion.