Statische Lichter - Ein Versuch und ein Problem

Übersicht BlitzMax, BlitzMax NG Allgemein

Neue Antwort erstellen

M0rgenstern

Betreff: Statische Lichter - Ein Versuch und ein Problem

 BeitragSo, Feb 26, 2012 23:16
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo liebe Community,
Nach langem hatte ich mal wieder Lust was mit Blitzmax zu machen.
Da wollte ich mich ein wenig an statischen Lichtern versuchen und hab das mal nach Gutdünken getan.

Heraus kamen Lichter, die eigentlich ganz ansehnlich sind, also ein ordentlicher, sanfter Übergang von hell nach Dunkel und so weiter. Echtzeitfähig ist es nicht, die Lightmap wird einfach am Anfang einmal erstellt.

Jetzt wollte ich das ganze ein wenig erweitern, so dass die Lichter nicht durch so direkt durch ihren Radius beschränkt sind, sondern einfach irgendwann "auslaufen". Das ist mein erstes Problem.
Außerdem wollte ich einen Schattenwurf einbauen, also dass bestimmte Objekte kein Licht durchlassen.
Dazu habe ich alle so umgeschrieben, dass von dem Licht ausgehend die Strahlen in der Länge des Lichtradius geworfen werden. Das Problem jetzt: Die Übergänge sind nicht mehr vorhanden. Ich habe nur noch helle, Runde Flächen.
Ich weiß auch, woran das liegt: Das ganze funktioniert so: Für jeden Pixel wird der momentane Farbwert (mit Helligkeit) ausgelesen und zum aktuellen Wert (der sich durch den Abstand zur Lichtquelle errechnet) hinzuaddiert. Das heißt, anfangs, wenn das komplette Bild noch schwarz ist, wird einfach nur der aktuelle Wert eingesetzt. Wenn ich nun aber von einem Licht ausgehend alle umliegenden Pixel anspreche (ich mache das mit Sin/Cos), dann sind einige Pixel darunter, die doppelt angesprochen werden. Das heißt, der Helligkeitswert wird öfter als nötig nochmal addiert. Dadurch sind alle Pixel die in dem Lichtradius liegen gleich hell und alle außerhalb einfach schwarz.
Klar, das ganze würde sich ganz einfach lösen lassen, indem ich einfach nicht den aktuellen Helligkeitswert des Pixels addiere. Aber: Dann habe ich das Problem, dass sich überschneidende Lichter nicht mehr korrekt angezeigt werden. Dann entsteht innerhalb der Schnittstelle ein dunkler Rand, da der Helligkeitswert der Pixel dort ja nicht betrachtet wird.

Kurz zusammengefasst also. Ich habe zwei Probleme:
1. Ich weiß nicht, wie ich die Lichter nicht so sehr auf ihren Radius beschränken soll, sondern einfach von hell nach dunkel auslaufen lassen soll.
2. Ich weiß nicht, wie ich das Problem lösen soll, dass die Übergänge an den Rändern weich sind, Schnittstellen von Lichtern jedoch korrekt dargestellt werden.

Zu 2. habe ich schon folgendes versucht: Ich habe ein Array erstellt, in der Größe der Pixmap erstellt und überall eine 0 reingeschrieben. Wenn dann der Pixel an einer Stelle verändert wurde, dann habe ich eine 1 hereingeschrieben und erst ab dann den aktuellen Helligkeitswert beachtet, solange eine 0 drin stand habe ich das nicht getan. Aber leider hat das dann doch nicht so funktioniert, wie ich es mir vorgestellt habe.

Nach dem ganzen Gelaber ist hier mal der Code für die Funktion:

BlitzMax: [AUSKLAPPEN] 
Function DrawCircLights()
		Local iNow:Int = MilliSecs() 'Nur zum prüfen der Dauer der Funktion
		
		SetBlend(LIGHTBLEND) 'Lightblend, für die Helligkeit

                'Bild erstellen
		imgLights = New TImage
		imgLights = CreateImage(GraphicsWidth(), GraphicsHeight())
		Local pix:TPixmap = LockImage(imgLights)
		pix.ClearPixels((128 Shl 24) | (0 Shl 16) | (0 Shl 8) | 0) 'Bild schwärzen
		
		For Local li:TLight = EachIn tlAllLights 'Alle Lichter durchgehen
			For Local iRound:Float = 0 To 360 Step 0.0 'Einmal im Uhrzeigersinn
				For Local iDist:Float = 0 To li.fRange 'Den ganzen Bereich durchgehen
					Local x:Int = Sin(iRound) * iDist + li.fX 'XPosition berechnen
					Local y:Int = Cos(iRound) * iDist + li.fy 'YPosition berechnen
					Local rgb:Int = ((128 Shl 24) | (0 Shl 16) | (0 Shl 8) | 0)

					If((x >= 0 And x < pix.width) And(y >= 0and y < pix.height)) Then
						rgb = pix.ReadPixel(x, y) 'Farbe auslesen
					EndIf
					
                                        'ARGB aufspalten
					Local a:Int = (rgb Shr 24)
					Local r:Int = (rgb & $FF0000) / $10000
					Local g:Int = (rgb & $FF00) / $100
					Local b:Int = rgb & $FF
					
      
					TColorSpaceHSV.ConvertRGBtoHSV(r, g, b) 'Zu HSV konvertieren
					
					Local fDist:Float = Pythagoras(li.fX, li.fY, x, y) 'Distanz zu Lichtquelle berechnen
					
					Local fStrength:Float = 0.0 'Helligkeit
					
					If (fDist <= li.fRange) Then 'Wenn der Pixel innerhalb des Lichtkreises liegt
						fStrength = 1.0 - (fDist / li.fRange) 'Helligkeit zwischen 0.0 und 1.0
						fStrength = fStrength + TColorSpaceHSV.Value 'Alten Helligkeitswert verrechnen
					Else
						fStrength = TColorSpaceHSV.Value 'Alten Helligkeitswert übernehmen
					EndIf
					
					Local r2:Int, g2:Int, b2:Int
					
					
					If(fStrength > 1.0) Then
						fStrength = 1.0
					EndIf
					
					'HSV mit neuem Helligkeitswert setzen	
					TColorSpaceHSV.SetHSV(TColorSpaceHSV.Hue, TColorSpaceHSV.Saturation, fStrength)
					TColorSpaceHSV.ConvertHSVtoRGB(r2, g2, b2) 'HSV zu RGB konvertieren
					
					Local col:Int = (a Shl 24) | (r2 Shl 16) | (g2 Shl 8) | b2 'RGB umrechnen
					
					If((x >= 0 And x < pix.width) And(y >= 0and y < pix.height)) Then
						pix.WritePixel(x, y, col) 'Pixel malen
					EndIf
				Next
			Next
		Next

		SavePixmapPNG(pix, "Lichter.jpg", 5) 'Bild zum Test speichern
		UnlockImage(imgLights) 'Bild freigeben
		imgLights = LoadImage(pix) 'Bild aus Pixmap laden
		
		SetBlend(ALPHABLEND)
		
                'Wie lange hat die Funktion gebraucht?
		Local iAfter:Int = MilliSecs()
		Print("Function needed: " + ((iAfter - iNow) / 1000) + " seconds or " + (iAfter - iNow) + " milliseconds!") 
		Cls
	End Function


Kurz zu dem Typ TLight: Das ist eigentlich nur ein Typ, der eine x und y Position hat und eine Range, also wie weit das Licht reicht.
(Die HSV Funktionen habe ich hier im Forum gefunden. Wollte ich aber selbst nochmal neu schreiben, um zu wissen wie das genau geht.)

Ich hoffe, jemand versteht was ich meine und kann mir helfen.
Das wäre wirklich super.

Lg, M0rgenstern

BladeRunner

Moderator

BeitragMo, Feb 27, 2012 10:00
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich würde auf sin/cos verzichten uns stattdessen mittels Bresenham (siehe Wikipedia)arbeiten, da es dann eben nicht zu solchen Mehrfach-Aufrufen eines Pixels kommt.
Um zu sehen ob der Pixel noch beleuchtet werden muss, einfach vom Pixel zum Start eine Sichtlinie ziehen und Prüfen ob ein blockendes Feld drauf liegt.
Das mit dem Ausufern verstehe ich nicht ganz- du hast nur die Möglichkeit einen Radius zu nehmen, auch wenn er sich vielleicht indirekt ergibt weil du die Helligkeit pro Distanz um eine Konstante reduzierst.
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

M0rgenstern

 BeitragMo, Feb 27, 2012 11:25
Antworten mit Zitat
Benutzer-Profile anzeigen
Hey Bladerunner,
vielen Dank für die Antwort.
Habe es grade 5 Minuten vor deiner Antwort gelöst. Das war sone Sache, wo die Lösung mal wieder im Halbschlaf kam.
Zur Lösung: Habe es jetzt doch mit einem Array gemacht. Ich prüfe einfach ob es im momentanen Pixel noch auf 0 steht. Wenn ja, erst dann mache ich alles was benötigt wird, also Farbe auslesen, Stärke berechnen und Pixel zeichnen. Dadurch ist die Funktion auch um einiges schneller. Für 50 Lichter benötige ich jetzt anstatt 80 Sekunden nur noch 8 (im Debugmodus) und ohne Debugmodus sind es nur 2.

Zu deinem Vorschlag wegen dem Bresenham Algorithmus: Den habe ich mir schon angesehen. Aber dann müsste ich doch eigentlich für jedes Licht nochmal jeden Pixel in der Pixmap durchgehen, oder sehe ich das falsch?
Also das wäre dann ja wieder um einiges langsamer. Denn so wie du sagst, muss ich ja den Endpunkt kennen und dann eine Linie von dort zur Lichtquelle ziehen.

Wegen dem "auslaufen": Momentan berechne ich die Stärke des Lichts folgendermaßen:
BlitzMax: [AUSKLAPPEN] 
Local fDist:Float = Pythagoras(li.fX, li.fY, x, y)
								
							Local fStrength:Float = 0.0
									
							If (fDist <= li.fRange) Then
								fStrength = 1.0 - (fDist / li.fRange)
								fStrength = fStrength + TColorSpaceHSV.Value
							Else
								fStrength = TColorSpaceHSV.Value
							EndIf

Also im Prinzip Code: [AUSKLAPPEN]
1.0 - (fDist / li.fRange)
.
Das Problem ist nur: Das ganze wird (meiner Meinug nach) nicht gleichmäßig genug ausgeblendet.
Es kann auch sein, dass das nur mein Gefühl ist, aber ich finde, der Kreis indem die Helligkeit zwischen 100 und 80 Prozent (geschätzt) liegt, ist um einiges größer als die Fläche, bei der nur noch geschätzt 50 - 0 Prozent Helligkeit sind.
Hier ist mal ein eine Lightmap, die mit der Funktion erstellt wurde, ich denke, da erkennt man das ganz gut. Ansonsten kann ich auch noch einen Screenshot hochladen, wo die Lichter über Bilder drübergelegt werden (mit Shadeblend).

user posted image

Lg, M0rgenstern

Noobody

 BeitragMo, Feb 27, 2012 11:47
Antworten mit Zitat
Benutzer-Profile anzeigen
Die Lichter stimmen so schon, nur sehen sie mit linearem Farbverlauf halt nicht besonders gut aus (besonders, wenn sich mehrere Lichter überlappen). Viel besser sieht eine quadratische Abnahme aus, die auch viel öfter benutzt wird.

Quadratische Abnahme ist extrem einfach und auch sehr günstig zu berechnen, da man im Prinzip nur die quadratische Distanz des Pixels vom Licht braucht. Hier ein kleiner Beispielcode: BlitzMax: [AUSKLAPPEN] 
SuperStrict

Graphics 512, 512

Local Pixmap:TPixmap = CreatePixmap(512, 512, PF_RGBA8888)

Local LightStrength:Float = 2000.0

For Local Y:Int = 0 Until 512
	Local Pixel:Int Ptr = Int Ptr Pixmap.PixelPtr(0, Y)
	
	For Local X:Int = 0 Until 512
		Local Dist:Float = (X - 255.0)*(X - 255.0) + (Y - 255.0)*(Y - 255.0) 'Quadratische Distanz
		
		Local Ratio:Float = LightStrength/Dist 'Lichtberechnung
		Ratio = Min(Ratio, 1.0) 'Zu grosse Werte abschneiden
		
		Local Value:Byte = Byte(Ratio*255.0)
		
		Pixel[X] = Value*$01010101
	Next
Next

DrawPixmap Pixmap, 0, 0
Flip 0

WaitKey
End

Einziges Problem bei der Methode ist halt natürlich, dass Lichter keinen definierten Radius haben, sondern auf beliebig lange Distanz noch Licht verteilen. In der Praxis werden diese Werte nach einer gewissen Distanz aber so klein, dass man die Lichtberechnung guten Gewissens auf ein kleines Rechteck um das Licht beschränken kann, ohne dass der Benutzer etwas mitbekommt.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

BladeRunner

Moderator

BeitragMo, Feb 27, 2012 11:51
Antworten mit Zitat
Benutzer-Profile anzeigen
Ja, bei Bresenham würdest Du für jedes Licht jeden Pixel einmal angehen- allerdings nur im Radius der effektiv ausgeleuchtet wird.
Noch einfacher kannst Du es machen wenn Du keine Lichtbrechung/ Reflexion etc. drin hast: Gehe einmal alle Pixel der Pixmap durch und berechne die Distanzen (Pythagoras) der Pixel zu allen Lichtquellen und setze die Helligkeit als Summe der einzelnen Entfernungshelligkeiten. Occlusion erreichst du auch hier mit einem Raycast von Zielpixel zu den einzelnen Lichtquellen.

Realtimetauglich ist das alles natürlich nicht, aber darum geht es dir ja auch nicht.
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

M0rgenstern

 BeitragMo, Feb 27, 2012 14:29
Antworten mit Zitat
Benutzer-Profile anzeigen
Hey ihr beiden.
Danke für die Hilfe.
Leider muss ich sagen, dass ich jetzt mehr Probleme habe als vorher.

@Noobody:
Die Ränder der Lichter sind in der Tat viel besser, aber ich finde die Mitte viel zu hell.
Und dann ist die Abstufung von der Mitte zu der nächstdunkleren Stufe ziemlich extrem. Ich habe auch schon ein wenig mit den Werten rumgespielt, aber das hat nichts an dem Problem geändert.

@BladeRunner:
Ich habe jetzt mal (dank Wikipedia) den Bresenham implementiert.
Nur habe ich jetzt folgendes Problem (und ich weiß ansolut nicht, wo das herkommt): Wenn ich die alten Werte der Pixel beachte, so damit keine schwarzen Ränder entstehen wenn zwei Lichter sich schneiden, dann habe ich absolut keine Abstufungen mehr. Ich habe mir auch schon den Helligkeitswert der Pixel ausgeben lassen. Selbst bei einem Licht sind da von Anfang an Pixel dabei, die nicht schwarz sondern komplett weiß (bzw hell) sind.
Ich lese die Pixel genauso aus wie vorher und erstelle auch das Bild so. Ich weiß nicht, woher es kommt.
Kann es sein, dass der Bresenham doch einige Pixel doppelt besucht?

Der Code dazu sieht so aus:
BlitzMax: [AUSKLAPPEN] 
	Function DrawLightBresen()
		Local iNow:Int = MilliSecs()
		
		SetBlend(LIGHTBLEND)
		imgLights = New TImage
		imgLights = CreateImage(GraphicsWidth(), GraphicsHeight())
		Local pix:TPixmap = LockImage(imgLights)
		pix.ClearPixels((128 Shl 24) | (0 Shl 16) | (0 Shl 8) | 0)
		
		For Local iX:Int = 0 Until pix.width
			For Local iY:Int = 0 Until pix.height
				For Local li:TLight = EachIn tlAllLights
					Local LightStrength:Float = li.frange * 10
					Local fD:Float = Pythagoras(ix, iy, li.fX, li.fY)
					If(fD <= li.fRange) Then
						Local dx:Int = ix - li.fX
						Local dy:Int = iy - li.fY
						
						Local adx:Int = Abs(dx)
						Local ady:Int = Abs(dy) ' Absolutbeträge Distanzen
						Local sdx:Int = Sgn(dx)
						Local sdy:Int = Sgn(dy) ' Signum Distanzen
						 
						Local pdx:Int, pdy:Int, ddx:Int, ddy:Int, es:Int, el:Int
						
						If adx > ady Then
						  ' x ist schnelle Richtung
						  pdx = sdx
						  pdy = 0   ' pd. ist Parallelschritt
						  ddx = sdx
						  ddy = sdy ' dd. ist Diagonalschritt
						  es = ady
						  el = adx ' Fehlerschritte schnell, langsam
						Else
						  ' y ist schnelle Richtung
						  pdx = 0
						  pdy = sdy ' pd. ist Parallelschritt
						  ddx = sdx
						  ddy = sdy ' dd. ist Diagonalschritt
						  es = adx
						  el = ady ' Fehlerschritte schnell, langsam
						End If
					
						Local x:Int = li.fx
						Local y:Int = li.fy
						Local col2:Int = (128 Shl 24) | (255 Shl 16) | (255 Shl 8) | 255
						pix.WritePixel(x, y, col2)
						Local fehler:Int = el / 2
						
						For Local i:Int = 1 To el ' el gibt auch Anzahl der zu zeichnenden Pixel an						
							fehler = fehler - es
						    If fehler < 0 Then
						       fehler = fehler + el ' Fehlerterm wieder positiv (>=0) machen
						       x = x + ddx
							   y = y + ddy ' Diagonalschritt
						    Else
						       x = x + pdx
							   y = y + pdy ' Parallelschritt
						    End If
								
							Local rgb:Int = ((128 Shl 24) | (0 Shl 16) | (0 Shl 8) | 0)
					
							rgb = pix.ReadPixel(x, y) 'Pixel auslesen
									
							Local a:Int = (rgb Shr 24)
							Local r:Int = (rgb & $FF0000) / $10000
							Local g:Int = (rgb & $FF00) / $100
							Local b:Int = rgb & $FF
							
							TColorSpaceHSV.ConvertRGBtoHSV(r, g, b) 'Zu HSV konvertieren
							
							Local Dist:Float = (X - li.fx) * (X - li.fx) + (Y - li.fy) * (Y - li.fy) 'Quadratische Distanz
							Local Ratio:Float = LightStrength / Dist 'Lichtberechnung
							Ratio = Ratio + TColorSpaceHSV.Value 'alte Werte beachten
							Ratio = Min(Ratio, 1.0) 'Zu grosse Werte abschneiden							
								
							TColorSpaceHSV.SetHSV(TColorSpaceHSV.Hue, TColorSpaceHSV.Saturation, Ratio) 'Werte in HSV einsetzen
							
							Local r2:Int, g2:Int, b2:Int
							TColorSpaceHSV.ConvertHSVtoRGB(r2, g2, b2) 'HSV zu RGB konvertieren
									
							Local col:Int = (a Shl 24) | (r2 Shl 16) | (g2 Shl 8) | b2
							
						    pix.WritePixel(x, y, col)
						Next
					EndIf
				Next
			Next
		Next
		
		SavePixmapPNG(pix, "Lichter.jpg", 5)
		UnlockImage(imgLights)
		imgLights = LoadImage(pix)
		
		SetBlend(ALPHABLEND)
		
		Local iAfter:Int = MilliSecs()
		Print("Function needed: " + ((iAfter - iNow) / 1000) + " seconds or " + (iAfter - iNow) + " milliseconds!")
		Cls
	End Function


Was mir auch aufgefallen ist (und mich irgendwie wundert), obwohls egal ist: Der Bresenham ist um einiges langsamer als das, was ich davor gebaut habe mit Sin/Cos.

Eine Frage ist jetzt auch noch aufgekommen:
Was genau meinst du, BladeRunner, wenn du meinst ich muss nochmal einen Raycast vom Zielpixel machen? Der Bresenham macht doch eigentlich genau das, oder seh ich das falsch?

Lg, M0rgenstern

Edit: Also das mit den doppelten Pixeln (scheint wirklich daran zu liegen) habe ich jetzt mal vorläufig mit nem Array gelöst. (Das Problem besteht also eigentlich noch weiterhin, das ist jetzt nur mal ein dreckiger Hack damits überhaupt mal so aussieht wies aussehen könnte.)
Eine Lightmap sieht dann zum Beispiel so aus:
user posted image
Prinzipiell stimmt das ja, aber ich finde trotzdem, dass es irgendwie komisch aussieht.
Was meint ihr dazu?

ChaosCoder

 BeitragMo, Feb 27, 2012 15:39
Antworten mit Zitat
Benutzer-Profile anzeigen
Geh doch den weniger physikalischen Weg: Den Weg des Ray-Tracings.

Für jeden Pixel des Bildes berechnest du, wie viele Lichtquellen von dort aus erreicht werden können und wie weit sie entfernt sind. Optimierungen können sogar schnell dafür sorgen, dass das ganze flüssig in real time berechnet werden kann.

Damit berechnest du nie zweimal den selben Pixel. Smile
Projekte: Geolaria | aNemy
Webseite: chaosspace.de

M0rgenstern

 BeitragMo, Feb 27, 2012 20:49
Antworten mit Zitat
Benutzer-Profile anzeigen
@ChaosCoder: Wo genau liegt der Unterschied zwischen den Bresenham und einem Ray-Tracing Verfahren? So wie ich das sehe, macht der Bresenham ja nichts anderes als einen Strahl von einem Punkt zum anderen schrittweise zu berechnen.


Lg, M0rgenstern

BladeRunner

Moderator

BeitragMo, Feb 27, 2012 20:58
Antworten mit Zitat
Benutzer-Profile anzeigen
Also bei meinen bisherigen Implementierungen hatte ich keine Probleme mit doppelt berechneten Pixeln, und ich habe Bresenham schon mehrfach benutzt. Ich hab leider derzeit kaum die Zeit deinen Code ausführlich zu testen, sorry.
Mir geht es mit dem erneuten Abfragen per Line eigentlich nur um den Fall der Ermittlung ob denn nicht die Sicht zur Lichtquelle schon verdeckt ist, denn das leistet Bresenham ja nicht.
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

Noobody

 BeitragMo, Feb 27, 2012 23:57
Antworten mit Zitat
Benutzer-Profile anzeigen
@M0rgenstern: Wenn dir das nicht gefällt, kannst du dir auch mal überlegen, deine Lichter als 3D-Punkte aufzufassen, die auf eine flache Ebene scheinen. Dann wendest du einfach die normale Lichtberechnung mit Skalarprodukt an und erhältst sowas wie das hier: BlitzMax: [AUSKLAPPEN] 
SuperStrict

Graphics 1024, 768

TLight.Init(1024, 768)

New TLight.Create(100.0, 100.0, 30.0, 0.3, 0.4, 0.7)
New TLight.Create(500.0, 400.0, 50.0, 0.7, 0.4, 0.3)
New TLight.Create(600.0, 600.0, 20.0, 0.7, 0.6, 0.7)

DrawPixmap TLight.RenderLights(), 0, 0
Flip 0

WaitKey()
End

Type TLight
	Global LightMap:Float[,,]
	Global SizeX:Int, SizeY:Int
	
	Global Lights:TList
	
	Field Radius:Float
	
	Field PosX:Float, PosY:Float, PosZ:Float
	Field R:Float, G:Float, B:Float
	
	Function Init(Width:Int, Height:Int)
		LightMap = New Float[Width, Height, 3]
		SizeX = Width
		SizeY = Height
		
		Lights = New TList
	End Function
	
	Function RenderLights:TPixmap()
		For Local X:Int = 0 Until SizeX
			For Local Y:Int = 0 Until SizeY
				LightMap[X, Y, 0] = 0.0
				LightMap[X, Y, 1] = 0.0
				LightMap[X, Y, 2] = 0.0
			Next
		Next
		
		For Local Light:TLight = EachIn Lights
			Light.Render()
		Next
		
		Local Pixmap:TPixmap = CreatePixmap(SizeX, SizeY, PF_RGBA8888)
		
		For Local X:Int = 0 Until SizeX
			For Local Y:Int = 0 Until SizeY
				Local ARGB:Int
				
				ARGB = (ARGB Shl 8) | Int(Min(LightMap[X, Y, 0], 1.0)*255.0)
				ARGB = (ARGB Shl 8) | Int(Min(LightMap[X, Y, 1], 1.0)*255.0)
				ARGB = (ARGB Shl 8) | Int(Min(LightMap[X, Y, 2], 1.0)*255.0)
				
				Pixmap.WritePixel(X, Y, ARGB)
			Next
		Next
		
		Return Pixmap
	End Function
	
	Method New()
		Lights.AddLast(Self)
	End Method
	
	Method Create:TLight(PosX:Float, PosY:Float, PosZ:Float, R:Float, G:Float, B:Float, Radius:Int = 10000)
		Self.PosX = PosX
		Self.PosY = PosY
		Self.PosZ = PosZ
		Self.R = R
		Self.G = G
		Self.B = B
		Self.Radius = Radius
		
		Return Self
	End Method
	
	Method Render()
		Local MinX:Float = Max(PosX - Radius, 0)
		Local MinY:Float = Max(PosY - Radius, 0)
		Local MaxX:Float = Min(PosX + Radius, SizeX - 1)
		Local MaxY:Float = Min(PosY + Radius, SizeY - 1)
		
		For Local X:Float = MinX To MaxX
			For Local Y:Float = MinY To MaxY
				Local DX:Float = X - PosX
				Local DY:Float = Y - PosY
				
				Local InvSqrt:Float = 1.0/Sqr(DX*DX + DY*DY + PosZ*PosZ)
				
				Local Ratio:Float = PosZ*InvSqrt
				
				LightMap[X, Y, 0] :+ R*Ratio
				LightMap[X, Y, 1] :+ G*Ratio
				LightMap[X, Y, 2] :+ B*Ratio
			Next
		Next
	End Method
End Type


ChaosCoder hat Folgendes geschrieben:
Damit berechnest du nie zweimal den selben Pixel.

Zwar nicht im Sinne der Lichtberechnung, aber die Arbeit, um festzustellen, ob ein Pixel von einer Lichtquelle aus sichtbar ist oder nicht, wird sehr wohl viel zu oft gemacht, wenn man sie für jeden Pixel aufs neue ausführt. Zeichnet man einen Pixel weiter aussen und führt die Schattenberechnung durch, weiss man ja nicht nur, ob der Pixel im Schatten liegt oder nicht - man weiss es für jeden Pixel auf der Linie vom aktuellen Pixel zur Lichtquelle. Von da her wäre es ja nicht sinnvoll, für diese Pixel die Schattenberechnung aufs neue auszuführen.

Eine Idee für eine effizientere Methode wäre, die Pixel am Rand der Bounding Box der Lichtquelle abzutasten. Für jeden dieser Randpunkte schickt man einen Strahl von Lichtquelle zum Punkt und wandert Pixel für Pixel nach aussen. Ist der aktuelle Pixel leer (= kein Hindernis), setzt man ein Flag, dass der Pixel sichtbar ist, und wandert zum nächsten Pixel auf dem Strahl. Ist der Pixel hingegen Teil eines Hindernisses, bricht man den aktuellen Strahl ab, da alle Pixel weiter aussen auf dem Strahl ja im Schatten liegen.

Nach diesem Schritt hat man jeden von der Lichtquelle sichtbaren Pixel mit einem Flag versehen - jetzt muss man nur noch diese Pixel abarbeiten und die Lichtberechnung durchführen.

@BladeRunner: Bresenham ist nur begrenzt geeignet, da er für das zeichnen von Linien optimiert ist. Da die Linien gut aussehen sollen, macht er oft diagonale Schritte, was aber im Fall von Lichtberechnung unerwünscht ist - hat man ein diagonales Hindernis, das nur ein Feld breit ist, schreitet der Bresenham je nach Lichtposition fröhlich durch das Hindernis und markiert Felder als sichtbar, die es eigentlich gar nicht sind. Noch schlimmer ist es, wenn das Licht sich bewegt, da dann die Beleuchtung anfängt zu flackern (manchmal geht der Bresenham durch das Hindernis, manchmal nicht). Ich verwendete Bresenham damals für ein Spiel, aber er lieferte leider keine besonders schönen Ergebnisse. In einer Umgebung mit pixelgrossen Hindernissen (d.h. relativ kleinen Feldern) wird ein Hindernis mit nur einem Feld Breite weniger oft auftreten, aber im Kontext einer Tilemap ist Bresenham definitiv ungeeignet.

Gute Erfahrungen habe ich mit diesem Algorithmus gemacht, da er simpel und sehr schnell ist, aber trotzdem alle Pixel entlang eines Strahls in der richtigen Reihenfolge findet.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

M0rgenstern

 BeitragDi, Feb 28, 2012 4:34
Antworten mit Zitat
Benutzer-Profile anzeigen
Vielen Dank für eure Hilfe.

Ich habe jetzt nochmal ein gutes Stück an dem ganzen gearbeitet.
Undzwar: Ich habe BladeRunners Rat befolgt:
Zitat:
Gehe einmal alle Pixel der Pixmap durch und berechne die Distanzen (Pythagoras) der Pixel zu allen Lichtquellen und setze die Helligkeit als Summe der einzelnen Entfernungshelligkeiten. Occlusion erreichst du auch hier mit einem Raycast von Zielpixel zu den einzelnen Lichtquellen.


Die Stärke des Lichts wird dann wie beschrieben berechnet, mit quadratischer Abnahme, wobei die Lichtstärke auf dem Lichtradius und der aktuelle Distanz beruht (sptäer im Code zu sehen).
Das ganze geht ziemlich flott (~3 Sekunden für ein Bild mit der Auflösung 1024*768, die Anzahl der Lichter macht nicht so viel aus).

Das größte Problem war und ist immer noch das Raycasting: Ich habe mir einen ganzen Ecken von Algorithmen um Strahlen/Linien zu erstellen angesehen (auch den DDA den @Noobody vorgeschlagen hat).
Aber entweder stelle ich mich zu blöd an, oder es ist wirklich so: Alle Algorithmen die ich ausprobiert habe, waren um einiges langsamer als einfach wieder einen Kreis aus Linien mit Sinus/Cosinus zu berechnen.
Ich kam dann damit bei ungefähr einer Minute Rechenzeit für etwa 5 Lichter und gleich viele Objekte raus.
Konnte das ganze dann aber noch extrem optimieren (für die gleiche Menge sind es jetzt circa 15 Sekunden).
Undzwar folgendermaßen:
Für jedes Licht wird ein Array in der Größe der Pixmap erstellt. Dort wird dann mit dem oben beschriebenen Raycasting Verfahren geprüft, welcher Pixel überhaupt von dem Licht aus erreichbar ist. Ist er nicht erreichbar, so wird das Array an dieser Stelle auf 1 gesetzt.
Die Hauptarbeit, also dort wo die eigentliche Pixmap dann beschrieben wird, wird dadurch ziemlich beschleunigt:
Wenn das Licht den momentanen Pixel nicht erreichen kann, dann wird einfach die aktuelle Helligkeit des Pixels genommen.

Also, wie gesagt: Die Hauptschleife für die Berechnung benötigt nur noch ungefähr 3 Sekunden.
Das größte Problem ist momentan noch der Raycaster: Jedes Licht benötigt mindestens (auch bei nur einem Objekt) 2 Sekunden um das Array zu erstellen.
Ich habe versucht das noch weiter zu optimieren, aber leider bekomme ich das nicht hin.
Habe auch alle Ansätze die ich hatte ausgeschöpft und ausprobiert (zum Beispiel für die komplette Lightmap ein Array wie oben beschrieben zu erstellen, so dass man dann später noch weniger auf die Lichter zugreifen muss, aber dadurch wird der Raycaster nur noch langsamer).

Der für die Funktion wichtige Code sieht so aus (alles wichtige sollte kommentiert sein):
BlitzMax: [AUSKLAPPEN] 
'Erstellt für das Licht ein Array mit allen vom Licht zu erreichenden Pixeln (1 bedeutet nicht erreichbar)
	Method CheckReacheablePixels(pix:TPixmap)
		Local iNow:Int = MilliSecs()
	
		iMap = New Int[pix.width, pix.height]
		
		For Local iRound:Float = 0 To 360 Step 0.1
			Local iHitCirc:Int = 0
			For Local iDist:Float = 0 To Max(fX, pix.width - fX)
				'Einfach einen Kreis aus Linien zu bilden geht am schnellsten.
				Local x:Int = Sin(iRound) * iDist + fX
				Local y:Int = Cos(iRound) * iDist + fy
				If(x >= 0 And x < pix.width And y >= 0 And y < pix.height) Then
					If (Not iHitCirc) Then
						For Local circ:TCircle = EachIn TCircle.tlAllCircles
							If(circ.IsInCirc(x, y)) Then
								iMap[x, y] = 1
								iHitCirc = 1
							EndIf
						Next
					Else
						iMap[x, y] = 1
					EndIf
				EndIf
			Next
		Next
		
		Local iAfter:Int = MilliSecs()
		Local milis:Int = iafter - inow
		Print("One Light needed: " + (milis / 1000) + " secs or " + milis + " milisecs")
	End Method
	
	Function DrawLightsDistFast()
		Local iNow:Int = MilliSecs()
		
		'Bild vorbereiten
		SetBlend(LIGHTBLEND)
		imgLights = New TImage
		imgLights = CreateImage(GraphicsWidth(), GraphicsHeight())
		Local pix:TPixmap = LockImage(imgLights)
		pix.ClearPixels((128 Shl 24) | (0 Shl 16) | (0 Shl 8) | 0)
		
		Local iNow2:Int = MilliSecs()
		
		'Arrays der Lichter vorbereiten
		For Local li:TLight = EachIn tlAllLights
			li.CheckReacheablePixels(pix)
		Next
		
		Local iAfter2:Int = MilliSecs()
		Local iMilis:Int = iAfter2 - iNow2
		Print("All Lights needed: " + (iMilis / 1000) + " secs or " + iMilis + " millisecs.")
		
		'Alle Pixel durchgehen
		For Local iX:Int = 0 Until pix.width
			For Local iY:Int = 0 Until pix.height
				Local rgb:Int = ((128 Shl 24) | (0 Shl 16) | (0 Shl 8) | 0)
				
				rgb = pix.ReadPixel(iX, iY) 'Pixel auslesen
							
				Local a:Int = (rgb Shr 24)
				Local r:Int = (rgb & $FF0000) / $10000
				Local g:Int = (rgb & $FF00) / $100
				Local b:Int = rgb & $FF
					
				TColorSpaceHSV.ConvertRGBtoHSV(r, g, b) 'Zu HSV konvertieren
						
				Local fRatio:Float = 0.0
				
				For Local li:TLight = EachIn tlAllLights
					Local Ratio:Float
					Local fDistance:Float = Pythagoras(ix, iy, li.fX, li.fy)
					Local LightStrength:Float = li.fRange * ((li.fRange / fDistance) * 10)
					Local fDistQuad:Float = (iX - li.fx) * (iX - li.fx) + (iY - li.fy) * (iY - li.fy) 'Quadratische Distanz
					If(li.iMap[iX, iY] = 0) Then 'Wenn der Pixel erreichbar ist
						Ratio = LightStrength / fDistQuad 'Lichtberechnung
					Else
						Ratio = TColorSpaceHSV.Value
					EndIf
					fRatio = fRatio + Ratio
				Next
				fRatio = fRatio + TColorSpaceHSV.Value 'alte Werte beachten
				fRatio = Min(fRatio, 1.0) 'Zu grosse Werte abschneiden							
								
				TColorSpaceHSV.SetHSV(TColorSpaceHSV.Hue, TColorSpaceHSV.Saturation, fRatio) 'Werte in HSV einsetzen
							
				Local r2:Int, g2:Int, b2:Int
				TColorSpaceHSV.ConvertHSVtoRGB(r2, g2, b2) 'HSV zu RGB konvertieren
									
				Local col:Int = (a Shl 24) | (r2 Shl 16) | (g2 Shl 8) | b2
				pix.WritePixel(iX, iY, col)
			Next
		Next
		
		SavePixmapPNG(pix, "LightDistLichter.jpg", 5)
		UnlockImage(imgLights)
		imgLights = LoadImage(pix)
		
		SetBlend(ALPHABLEND)
		
		Local iAfter:Int = MilliSecs()
		Print("Function 'DrawLightsDistFast' needed: " + ((iAfter - iNow) / 1000) + " seconds or " + (iAfter - iNow) + " milliseconds!")
		Cls
	End Function


@Noobody:
Vielen dank wegen den 3D-Lichtern. Aber ich muss ehrlich sagen, dass sie mir nicht richtig gefallen haben. Vor allem werden die bei Radien unter 1000 rechteckig anstatt rund.
Habe die anderen Lichter ja jetzt hübscher hinbekommen.

Hier sind nochmal zwei Bilder (einmal nur die Lightmap und einmal ein Screenshot):
user posted image
user posted image

Es wäre wirklich super, wenn ihr noch Anregungen hättet oder euch einfach zu dem bisherigen Ergebnis äußern würdet.

Lg, M0rgenstern

Edit:
Ich habe die Bilder in diesem Beitrag ersetzt.
Das ganze funktioniert jetzt mit Rechtecken und mit Kreisen, außerdem läuft es ohne Debug-Mouds mit linearer Laufzeit gemessen an der Anzahl der Objekte und Lichter. Also Dort auf den Bildern isnd jetzt 10 Lichter und 10 Objekte zu sehen, das ganze hat ungefähr 10 Sekunden gedauert. Bei 50 Lichtern und 50 Objekten sind es dann etwa 50 Sekunden.
Werde das ganze jetzt nochmal "schön" neu schreiben und auch für Tilemaps implementieren und dann ins Codearchiv stellen.

Lg, M0rgenstern

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Allgemein

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group