Schnitt: Gerade/Rechteck

[Medium]

Den Satz vorm Edit bin ich grad dabei kaputt zu machen, indem ich nicht mehr regelmäßig unterteile, sondern in einen Quadtree

Was ich genau machen möchte ist folgendes:

Ich habe einen Satz Splines (so ca. 100-300 Stück, jeder so bestehend aus ~10 Segmenten im Schnitt). Diese Splines sind Kanten (eigentlich Kanten von Kanten...) eines Ausgangsbildes, beinhalten also auch Farbinformationen.
Aus diesen Splines will ich nun wieder ein Bitmap erzeugen, dass dem Original möglichst nahe kommt. In diesem Ansatz möchte ich also rund um jeden Pixel schauen, welches Spline ich von dort aus als erstes "sehe", und dessen Farbe an der Schnittstelle addiere ich im Verhältnis zur Entfernung auf meinen Pixel.

Zuvor habe ich das durch wiederholtes Anwenden einer modifizierten diskreten Wärmediffusionsfunktion in einem DirectX9 Pixelshader gemacht, wofür die Splines zunächst auf ein sonst leeres Bild gezeichnet wurden und dann schrittweise verbreitert und vermischt.

Als nächstes hab ich einen ähnlichen Ansatz wie jetzt, mit obigem vermischt. Ich zeichne also die Splines in mein Bitmap, und gehe dann von jedem Pixel aus in alle Richtungen Pixel für Pixel durch, bis ich auf eines treffe dass zu einem Spline gehört. Dann hab ich auch eine Farbe und eine Entfernung. Das hab ich ebenfalls in einem Shader gemacht.

Dann kam ich drauf, dass dieses pixelweise Voranschreiten ja eigentlich Käse ist, da man ja Schnitte mit Funktionen 3. Grades (was ein Spline-Segment letztlich ist) durchaus auch explizit berechnen kann, was irgendwie eleganter ist . Und genau das tu ich grad, allerdings nicht in einem Shader, da ich bisher keine Lust hatte mir auszudenken wie ich meine Spline-Daten in Form einer Textur in diesen hineinfüttern will. Das wäre dann evtl. der nächste Schritt, wenn die CPU-Version so weit wie auch nur möglich optimiert ist.

Das ganze Projekt reift schon so ein paar Monate, also so ganz unversucht hab ich andere Ansätze nicht gelassen. Für geniale Einfälle bin ich aber immer mehr als offen!

[Nikolas]

Klingt nach einem spannenden Projekt. Ich hab gerade meinen Master an der ETH begonnen und spezialisiere mich im Bereich Robotik und Bildverarbeitung, wenn du nichts dagegen hast, würde ich mir die Arbeit gerne mal anschauen, mit splines habe ich noch nie gearbeitet, da kann ich sicher was lernen. (Gerne auch eine Vorab-Version)

[Medium]

Nikolas, du gewinnst jetzt erstmal einen Blumentopf

Ich hab nun eine Lösung die einfach nur abgeht wie Schmidt's Katze (und noch mehr), und sie basiert tatsächlich quasi auf Bresenham! Was mich an dem Algo anfangs immer ein wenig gestört hat ist, dass ich damit für jedes Pixel für jeden Winkel Divisionen (zumindest aber Int-Divs und Modulos) rein bekomme, zusätzlich zu einer Reihe von Fallunterscheidungen. Ein fittes Kerlchen auf GameDev hatte dann die Wahnsinnsidee (die im Nachhinein fast schon zu simpel ist):
Statt den DDA (das ist quasi die Oberklasse von Algos zu denen auch Bresenham gehört) immer und immer wieder neu zu berechnen, macht man dies nur ein einziges Mal für nur einen einzigen Block, und baut sich daraus eine Lookup-Table die die Block-Offsets zu jedem Startpixel im Block, zu jedem Winkel in einer Liste bereit hält - da ja diese schließlich für alle Blöcke identisch aussieht, abgesehen von der Länge. Die maximale Länge in Blocks ist dann einfach sqrt((bildbreite/blocksize)²+(bildhöhe/blocksize)²)*2 (mal zwei wegen 4er Nachbarschaft, d.h. ein diagonaler Sprung ist zwei gerade Sprünge), was dann die Obergrenze in der LUT ist die man je brauchen würde.

Praktisch hab ich nun also eine List<Point>[,,] in der ich einfach nachschauen kann wo ich für den aktuellen Pixel beim aktuellen Winkel den nächsten Block finde (wobei Point halt für X bzw. Y nur -1, 0 und 1 beinhaltet). Die LUT zu bauen dauert selbst bei großer Blockzahl um 50-100ms, also praktisch garnix, so dass ich das einfach mal als strukturelles Optimum ansehe. Der Quadtree musste also letztlich doch dran glauben

Ich bin nun aber auch echt reif für reichlich