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
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)