MiniBCC #24 - Lief oder Rerelief

Übersicht Sonstiges Projekte

Neue Antwort erstellen

Holzchopf

Meisterpacker

Betreff: MiniBCC #24 - Lief oder Rerelief

BeitragFr, Dez 05, 2014 21:46
Antworten mit Zitat
Benutzer-Profile anzeigen
Sicher wartet ihr gespannt auf den neuen MiniBCC. Also, los geht's:

MiniBCC #24 - Lief oder Rerelief

In der Kartographie wird bei einem Relief die dritte Dimension oft vereinfacht als Schattenbild dargestellt. Solche Schattenbilder (oder -karten) werden aus 3D-Datensätzen generiert. Und ihr macht jetzt genau das umgekehrte: aus einem gegebenen Schattenbild generiert ihr einen möglichen 3D-Datensatz in Form einer Höhenkarte.

Aufgabe
Schreibt ein einfaches Programm, dass aus diesem Bild eine Heightmap macht. Die Ausgabe erfolgt aus Speicherplatz-Gründen nur auf dem Bildschirm.
user posted image

Quelle: map.geo.admin.ch
Lichtquelle: Azimut 135°, Elevation 45°

Damit ihr das Bild überhaupt laden dürft, kriegt ihr das Bonus-Element Grafik
user posted image
Insgesamt 256KiB Speicher für Grafiken, wobei die Vorlage schon 132KiB weg frisst Twisted Evil

Ihr dürft selbstverständlich auch andere Schattenkarten verwenden, die kleiner sind. Die Vorlage ist nur als Muster zu verstehen Exclamation

Code-Limit
6KiB

Termin
Sonntag, 07.12.2014, 23:59

Startschuss
*peng* Jetzt

PS: Ich weiss, dass Lief/Rerelief Wortkreationen und eine Heightmap lediglich eine andere Form der Darstellung von Reliefs sind. Aber hey, die Wortkreation bot sich halt an Wink

Edit
Ihr dürft auch dieses Bild verwenden. Bei dem sind die Ränder auf einem Level, was die Rechnung einfacher macht.
Erledige alles Schritt um Schritt - erledige alles. - Holzchopf
CC BYBinaryBorn - Yogurt ♫ (31.10.2018)
Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm
  • Zuletzt bearbeitet von Holzchopf am Do, Dez 25, 2014 20:36, insgesamt 2-mal bearbeitet

DAK

BeitragSa, Dez 06, 2014 0:08
Antworten mit Zitat
Benutzer-Profile anzeigen
Ist das denn überhaupt ganz so möglich? Ich mein, ich habe eine Idee wie es geht, wenn es rund um die Karte einen Rand mit Höhe 0 geben würde.
Gewinner der 6. und der 68. BlitzCodeCompo

Holzchopf

Meisterpacker

BeitragSa, Dez 06, 2014 0:19
Antworten mit Zitat
Benutzer-Profile anzeigen
Ja, ich sage, es ist möglich. Aber ich sage nicht, dass du nicht am Rand anfangen musst, um das herauszufinden Wink
Erledige alles Schritt um Schritt - erledige alles. - Holzchopf
CC BYBinaryBorn - Yogurt ♫ (31.10.2018)
Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm

DAK

BeitragSa, Dez 06, 2014 0:57
Antworten mit Zitat
Benutzer-Profile anzeigen
Klar, man kann eine Lösung schreiben, die genau für dieses Bild funktioniert, indem man den Fluss als Basis nimmt. Ist das die Aufgabe?
Eine generelle Lösung für jedes Bild wäre ziemlich schwierig.
Gewinner der 6. und der 68. BlitzCodeCompo

Holzchopf

Meisterpacker

BeitragSa, Dez 06, 2014 13:13
Antworten mit Zitat
Benutzer-Profile anzeigen
Eine generelle Lösung ist tricky. Eine generelle Lösung, die auch möglichst genau abbildet, sogar sehr. Aber das Ergebnis wird ja wohl auch von niemandem auf Richtigkeit geprüft. Es gibt verschiedene/ verschieden-schwierige Möglichkeiten, die gescannten Linien in der Höhe so zu einander anzupassen, dass die generierte "Fläche" in etwa realistisch herauskommt.

Wer ohne diese Tricks weiterkommen will, verwendet dieses Bild:
user posted image

Quelle: map.geo.admin.ch

MfG
Erledige alles Schritt um Schritt - erledige alles. - Holzchopf
CC BYBinaryBorn - Yogurt ♫ (31.10.2018)
Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm

Holzchopf

Meisterpacker

BeitragDo, Dez 25, 2014 20:55
Antworten mit Zitat
Benutzer-Profile anzeigen
Es gab zwar keine Einsendungen, aber ich weiss, dass es zumindest ein paar Leuten den Kopf zerbrochen hat. Allen voran DAK, der mich zu miniBCC-Laufzeiten per PN angeschrieben hatte. Auf sein OK hin veröffentliche ich hier mal seinen Kommentar, Zitat:
Ich hab da noch mal drüber nachgedacht, und ich denke, mehr als eine ungefähre Abschätzung ist eigentlich gar nicht möglich.

Mal zuerst, ich möchte nicht deinen BCC schlechtreden, da die Idee sehr gut ist. So ein Tool wäre sehr nützlich und sowas programmieren finde ich sehr spannend.

Ich denke aber, dass die Aufgabe nicht lösbar ist. Die Reliefkarte ist ja im Endeffekt eine Lightmap, und die Heightmap eine Bumpmap. Man muss hier also das Bumpmapping reversieren.

Um von einer Bumpmap auf eine Lightmap zu kommen muss man zwei Schritte machen, die beide verlustbehaftet sind, nämlich muss man die Bumpmap in eine Normalmap umwandeln, und die dann eine Lightmap.

Die Normalmap ist eine Umformung der ersten Ableitung der Bumpmap. Hierbei gehen die originalen Höheninformationen verloren, es bleiben nur mehr die Winkel jedes Texels übrig. Das lässt sich noch korrigieren, wenn es rund um das Bild einen Ramen mit Höhe 0 gibt (wie in deinem 2. Bild).

Von der Normalmap zur Lightmap kommt man so: (für jedes Texel)

lightmap[x,y] = dot(normalmap[x,y], lightvector)

Leider ist das Dot-Product auch verlustbehaftet. Das sieht ja so aus:

dot(v, u) = vx*ux + vy*uy + vz*uz

Das heißt, wenn der Lightvector bekannt ist, und das Ergebnis des Dot-Products (steht ja in der Lightmap), die drei Koordinaten der Normalmap aber nicht, dann gibt es hier ein Problem: man muss 3 Variablen ein einer Gleichung finden, was nicht möglich ist. Man braucht immer mindestens so viele Gleichungen in einem Gleichungssystem wie Variablen die man lösen möchte.

So gibt es einen ganzen "Ring" an möglichen Lösungsvektoren für jede dieser Gleichungen. So ist es bei einer Lichtquelle mit den Werte Azimut 135° und Elevation 45° nicht sicher, ob z.B. der Azimut des Normalvektors 130° oder 140° beträgt, oder die Elevation 40° oder 50° beträgt, da das Dot-Product nur die Abweichung der zwei Vektoren widerspiegelt. Problematischer wird es dann noch wenn es sich um eine Kombination der Abweichungen handelt, also wo sowohl Azimut und Elevation sich von der Lichtquelle unterscheiden (was leider fast immer der Fall sein wird).

Hast du eine Idee wie man da noch drum rum kommen kann?

Grüße,
Dakkaron


Worauf ich übrigens noch antwortete, Zitat:
DAK hat Folgendes geschrieben:
mehr als eine ungefähre Abschätzung ist eigentlich gar nicht möglich.


Das ist korrekt. Manch ein Praktiker oder Mathematiker mag mir da sicher widersprechen, aber wenn's um meine Meinung geht, dann sieht die so aus, dass es nicht eindeutig rekonstruierbar ist. Ist ja aber auch nicht gefragt. Es reicht eine mögliche Rekonstruktion. Die Aufgabenstellung lässt es eigentlich sogar zu, den Rand als gleichhoch zu betrachten und dann in eine Richtung zu scannen. Der Mensch wird zwar einen Fehler erkennen, weil so auf eindeutig (=scheinbar) flachen Flächen Stufen entstehen.

Selbstverständlich kann man unzählige Filter entwerfen, um solche Fehler zu kaschieren, aber zwingend notwendig ist das nicht.


Die Idee, das als miniBCC-Aufgabe zu stellen, kam damals übrigens nicht aus dem Nichts Wink Ich hatte mich zuvor auch schon daran versucht. Das Ergebnis fand ich damals eher dürftig und ich widmete mich schliesslich wieder anderem, da mir schlicht die Zeit fehlte. Eine Idee zur Verbesserung hatte ich aber schon! Shocked
Hier erst einmal mein "Zwischenstand", BlitzMax: [AUSKLAPPEN]
SuperStrict

SetGraphicsDriver GLMax2DDriver()
Graphics(512,512)

Global FACT:Double = 2

Local img:TImage = LoadImage("D:\Mitarbeit\BBP\mbcc24-Vorlage\map.png")

Local hm:TImage = Lief(img)

Local tmr:TTimer = CreateTimer(20)

While Not (KeyDown(KEY_ESCAPE) Or AppTerminate())
FACT :+ MouseZSpeed() /100.0

hm = Lief(img)

DrawImage hm,0,0

'DrawText FACT, 0,0

WaitTimer(tmr)
Flip 0
Wend

Function Lief:TImage(pImg:TImage)
Local hmax:Float
Local hm:Float[512,512]
' read shadowmap
Local pms:TPixmap = LockImage(pImg)
For Local y:Int = 0 Until 512
For Local x:Int = 0 Until 512
Local tx:Int, ty:Int, th:Float
' inclination
Local f:Float = (ReadPixel(pms, x, y) & $ff) /180.0
Local h:Float = f^FACT -1
If h > 0 Then
tx = x +1
ty = y +1
th = h
ElseIf h < 0 Then
tx = x -1
ty = y -1
th = -h
EndIf
If tx >= 0 And tx < 512 And ty >= 0 And ty < 512 Then
hm[tx,ty] :+ th
If hm[tx,ty] > hmax Then
hmax = hm[tx,ty]
EndIf
EndIf
Next
Next
UnlockImage(pImg)
' write heightmap
Local imghm:TImage = CreateImage(512,512)
Local pmh:TPixmap = LockImage(imghm)
For Local y:Int = 0 Until 512
For Local x:Int = 0 Until 512
Local h:Float = hm[x,y]
Local g:Int = h *255 /hmax
WritePixel(pmh, x,y, $ff000000 | (g Shl 16) | (g Shl 8) | g)
Next
Next
UnlockImage(imghm)
Return imghm
End Function


Die weiterführende Idee war es
  • aus dem generierten Bild wieder ein Schattenbild zu generieren
  • das neue Schattenbild mit dem alten zu vergleichen
  • die Differenz daraus bilden
  • das Ergebnis um einen Faktor abschwächen
  • daraus wieder eine Heightmap zu machen
  • diese mit der letzten zu kombinieren
  • und wieder oben anfangen


Ich hab's bis jetzt noch nicht umgesetzt Embarassed

Auf jeden Fall dachte ich mir: "Hey, das geht doch sicher auch anders. Man kann bestimmt auch das Bild aus der Lichtrichtung scannen." Und schwupps war die Idee da, das euch machen zu lassen Twisted Evil natürlich gab ich hier keinerlei Hinweise, weil ich niemanden vorbelasten wollte. Rolling Eyes

Wie dem auch sei - der nächste miniBCC kommt bestimmt irgendwann Wink

mfG
Holzchopf
Erledige alles Schritt um Schritt - erledige alles. - Holzchopf
CC BYBinaryBorn - Yogurt ♫ (31.10.2018)
Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm

Holzchopf

Meisterpacker

BeitragDi, Okt 27, 2015 23:46
Antworten mit Zitat
Benutzer-Profile anzeigen
MULTIPOST! Mr. Green Hach herrlich, im Projekte-Forum ist das erlaubt und ich nutze es schamlos aus! Wink

Jetzt hört mal zu ihr Blitzer! Der Thread wäre schon fast auf Seite zwei in der Foren-Übersicht gelandet... Aber ich habe euch nicht vergessen!

Mein Ansatz (oben beschrieben) konnte ich leider nicht ganz zu Ende umsetzen... Das zeug schwingt auf und ich hatte einfach nicht mehr den Nerv, das zu ende zu führen. Stattdessen habe ich mir was anderes überlegt:
Im Prinzip handelt es sich um eine Faltung, die, je nach Steilheit des Reliefs (hier wird angenommen, dass heller als 180 = Pixel schräg rechts unten ist höher und dunkler als 180 = Pixel schräg rechts unten ist tiefer), die Pixel schräg rechts unten oder schräg links darüber erhöht oder abgesenkt werden. Die Resultate lassen sich sehen... Ich führe die Faltung im Moment noch mehrfach aus um das Ergebnis mit jedem Durchgang etwas zu verfeinern - besser wäre es wahrlich, den Faltungskern von Anfang an einfach direkt richtig zu gestalten und nur einmal zu falten! Aber je grösser der Faltungskern, umso länger die Rechenzeit, deshalb belasse ich das so.

Hier gibt's das Ergebnis mit BMax-Source und .exe
Die Faltung wird nur auf Leertastenanschlag erneut ausgeführt. Es wird schnell langsam ( Laughing ). Aber auf stdout wird der Rechnungsfortschritt ausgegeben.

Und ja, das war mein 5. Versuch. Ich geb's ja zu, die Aufgabe war überrissen. Beim nächsten Mal gebe ich mir mehr Mühe, eine umsetzbare Aufgabe zu stellen.

MfG
Holzchopf
Erledige alles Schritt um Schritt - erledige alles. - Holzchopf
CC BYBinaryBorn - Yogurt ♫ (31.10.2018)
Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm

Neue Antwort erstellen


Übersicht Sonstiges Projekte

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group