Marching Squares Implementation

Übersicht

BlitzMax, BlitzMax NG

Codearchiv & Module

	n-Halbleiter Betreff: Marching Squares Implementation	So, Okt 09, 2011 23:40 Antworten mit Zitat
Guten Abend Forum! Ich möchte gerne mal etwas präsentieren, von dem ich hoffe, dass es nicht nur mir nutzt: Eine Implementation von Marching Squares. Was ist Marching Squares? Marching Squares ist ein Algorithmus, um implizite Funktionen darzustellen. Marching Squares ist ein Algorithmus, um Höhenlinien darzustellen. "Marching Squares [...] ist ein Algorithmus aus der Computergrafik zur Berechnung von Isolinien aus einer Datenquelle. Isolinien sind Linien, die Datenpunkte mit gleichen Werten verbinden." (So sagt Herr Wikipedia) Über die Module: Warum "Module"? Weil ich zwei Module hochgeladen habe, die beide das gleiche machen. Allerdings ist eines der Module auf das Nutzen von Pixmaps optimiert, das andere ist allgemeiner gehalten. An sich ist die Handhabung gleich, wobei es beim allgemeineren Modul ein, zwei zusätzliche Punkte zu beachten gibt. Aber vorher: Downloadlinks: Marchingsquares.mod Marchingsquarespixmap.mod Der untere Link führt zum für Pixmaps optimierten Modul. Handhabung: Den Algorithmus nutzt man, indem man ein Objekt des Types "TCurvePlotter" erstellt (für die einzelnen Methoden bitte die beigelegte Dokumentation konsultieren). Diesem Objekt müssen jetzt allerdings noch die einzelnen Daten mitgegeben werden (ebenjene Methoden). Wenn alle Daten gesetzt sind, muss nur noch die "Plot"-Methode aufgerufen werden (bei der Pixmap-Variante gibt sie die Pixmap zurück, sonst nichts). Die nicht-Pixmap-Variante benötigt eine Information mehr als die Pixmap-Variante: Eine Funktion, die die Linien zeichnet (in der Pixmap-Variante habe ich dazu einen Linien-Bresenham auf eine Pixmap genutzt, was ihr schlussendlich macht, bleibt euch überlassen). Diese wird als Funktionspointer übergeben. Die Funktion hat die folgende Signatur: LineFnc(Target:Object,X1:Int,Y1:Int,X2:Int,Y2:Int,ARGB:Int) Die Parameter stehen für: Target: Ein Rendertarget (kann natürlich auch leergelassen werden (=Null), wie es eben benötigt wird) X1,Y1: Die Koordinaten des Startpunktes der Linie X2,Y2: Die Koordinaten des Endpunktes der Linie ARGB: Die Farbe der Linie Ein Beispiel, dass sich der sog. "Cassinischen Kurve" (in diesem Beispiel mit a=0.49 und b=0.5, im Bild des Wikipediaeintrages entspricht das der hellgrauen Kurve, die direkt um die blaue Kurve liegt) bedient. Wie man an der Form erkennen kann, handelt es sich nicht um eine "gebräuchlichere" Funktion der Form y=f(x), sondern um eine Funktion der Form z=f(x,y) (<- implizite Funktion, man kann so bspw. auch schön Kreise darstellen; für einen Einheitskreis um (0,0): f(x,y)=x²+y²-1 =0). Das Beispiel ist nicht viel kommentiert, sollte aber selbsterklärend sein:BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] SuperStrict Import Leiter.Marchingsquarespixmap SetGraphicsDriver GLMax2DDriver() Global G_Width:Int=400,G_Height:Int=300 Graphics(G_Width,G_Height,0) Local Time1:Int,Time2:Int Global rgSample:Float[][]=GetSample(G_Width,G_Height,1) Local Plotter:TCurvePlotter=New TCurvePlotter Plotter.SetSampleFnc(Sample) Plotter.SetSampleSize(G_Width,G_Height) Plotter.SetColorARGB($FFFFFFFF) Plotter.SetCellNum(20) Plotter.SetInterpolation(True) Time1=MilliSecs() Local Pixmap:TPixmap=Plotter.Plot(G_Width,G_Height) Time2=MilliSecs() DebugLog (Time2-Time1) Time1=MilliSecs() DrawPixmap(Pixmap,0,0) Time2=MilliSecs() DebugLog (Time2-Time1) Flip WaitKey() End Function Sample:Float(X:Int,Y:Int) If (X<0) Then X=0 If (Y<0) Then Y=0 If (X>=G_Width) Then X=G_Width-1 If (Y>=G_Height) Then Y=G_Height-1 Return rgSample[X][Y] End Function Function GetSample:Float[][](Width:Int,Height:Int,StepSize:Int) Local a:Float=0.49,b:Float=0.5 Local Sample:Float[][] Sample=Sample[..Width] For Local i:Int=0 Until Width Sample[i]=New Float[Height] Next For Local X:Int=0 Until Width For Local Y:Int=0 Until Height Local X2:Float,Y2:Float 'Cassinische Kurve (Koordinaten mussten umgerechnet werden, da die Kurve normalerweise um den Punkt (0,0) geht). X2=Float(X-(G_Width Shr 1))/Float(G_Width) Y2=Float(Y-(G_Height Shr 1))/Float(G_Height) Sample[X][Y]=(X2^2+Y2^2+a^2)^2-4(a^2)(X2^2)-(b^4) Next Next Return Sample End Function Und noch ein Beispiel für eine Linienfunktion, die Max2Ds DrawLine-Funktion nutzt (ohne mit einem Rendertarget zu arbeiten): BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Function MarchingSquaresLine(Target:Object,X1:Int,Y1:Int,X2:Int,Y2:Int,ARGB:Int) 'Die einzelnen Werte aus dem Farbinteger auslesen Local A:Float,R:Int,G:Int,B:Int A=Float((ARGB&$FF000000) Shr 6)/255.0 R=(ARGB&$FF0000) Shr 4 G=(ARGB&$FF00) Shr 2 B=(ARGB&$FF) 'Farb- und Alphawerte setzen SetAlpha(A) SetColor(R,G,B) 'Linie zeichnen DrawLine(X1,Y1,X2,Y2) End Function Ich hoffe, dass jemand diese Module sinnvoll nutzen kann (mir ist bisher noch nicht wirklich etwas in den Sinn gekommen - außer Spielereien -, aber das kommt sicher noch ). Und nun: Viel Spaß! P.S.: Falls sich Fragen ergeben, im Quelltext habe ich meine Quelle für die Beschreibung des Algorithmus' angegeben, ansonsten gibt es am Ende des geposteten Wikipedialinks einige Hilfen. Und im schlimmsten Fall gibt's noch mich. EDIT (10.10.2011, 12:57): Korrektur einiger Fehler im Text, Hinzufügen des Funktionsbeispiels und Korrektur der Archive. EDIT (01.01.2012, 12:56): Korrektur des Moduls Leiter.MarchingSquares: mir sind da zwei große Fehler unterlaufen, auf die ich gerade beim Arbeiten an meinem BCC #58 Beitrag gestoßen bin.. Peinlich, dass mir das so spät aufgefallen ist.

n-Halbleiter

Betreff: Marching Squares Implementation

So, Okt 09, 2011 23:40
Antworten mit Zitat

Guten Abend Forum!

Ich möchte gerne mal etwas präsentieren, von dem ich hoffe, dass es nicht nur mir nutzt: Eine Implementation von Marching Squares.

Was ist Marching Squares?
Marching Squares ist ein Algorithmus, um implizite Funktionen darzustellen.
Marching Squares ist ein Algorithmus, um Höhenlinien darzustellen.
"Marching Squares [...] ist ein Algorithmus aus der Computergrafik zur Berechnung von Isolinien aus einer Datenquelle. Isolinien sind Linien, die Datenpunkte mit gleichen Werten verbinden." (So sagt Herr Wikipedia)

Über die Module:
Warum "Module"? Weil ich zwei Module hochgeladen habe, die beide das gleiche machen. Allerdings ist eines der Module auf das Nutzen von Pixmaps optimiert, das andere ist allgemeiner gehalten. An sich ist die Handhabung gleich, wobei es beim allgemeineren Modul ein, zwei zusätzliche Punkte zu beachten gibt.

Aber vorher: Downloadlinks:
Marchingsquares.mod
Marchingsquarespixmap.mod
Der untere Link führt zum für Pixmaps optimierten Modul.

Handhabung:
Den Algorithmus nutzt man, indem man ein Objekt des Types "TCurvePlotter" erstellt (für die einzelnen Methoden bitte die beigelegte Dokumentation konsultieren). Diesem Objekt müssen jetzt allerdings noch die einzelnen Daten mitgegeben werden (ebenjene Methoden). Wenn alle Daten gesetzt sind, muss nur noch die "Plot"-Methode aufgerufen werden (bei der Pixmap-Variante gibt sie die Pixmap zurück, sonst nichts). Die nicht-Pixmap-Variante benötigt eine Information mehr als die Pixmap-Variante: Eine Funktion, die die Linien zeichnet (in der Pixmap-Variante habe ich dazu einen Linien-Bresenham auf eine Pixmap genutzt, was ihr schlussendlich macht, bleibt euch überlassen). Diese wird als Funktionspointer übergeben. Die Funktion hat die folgende Signatur:
LineFnc(Target:Object,X1:Int,Y1:Int,X2:Int,Y2:Int,ARGB:Int)
Die Parameter stehen für:

Target: Ein Rendertarget (kann natürlich auch leergelassen werden (=Null), wie es eben benötigt wird)

X1,Y1: Die Koordinaten des Startpunktes der Linie

X2,Y2: Die Koordinaten des Endpunktes der Linie

ARGB: Die Farbe der Linie

Ein Beispiel, dass sich der sog. "Cassinischen Kurve" (in diesem Beispiel mit a=0.49 und b=0.5, im Bild des Wikipediaeintrages entspricht das der hellgrauen Kurve, die direkt um die blaue Kurve liegt) bedient. Wie man an der Form erkennen kann, handelt es sich nicht um eine "gebräuchlichere" Funktion der Form y=f(x), sondern um eine Funktion der Form z=f(x,y) (<- implizite Funktion, man kann so bspw. auch schön Kreise darstellen; für einen Einheitskreis um (0,0): f(x,y)=x²+y²-1 =0). Das Beispiel ist nicht viel kommentiert, sollte aber selbsterklärend sein:BlitzMax: [AUSKLAPPEN]

SuperStrict

Import Leiter.Marchingsquarespixmap

SetGraphicsDriver GLMax2DDriver()

Global G_Width:Int=400,G_Height:Int=300

Graphics(G_Width,G_Height,0)

Local Time1:Int,Time2:Int

Global rgSample:Float[][]=GetSample(G_Width,G_Height,1)

Local Plotter:TCurvePlotter=New TCurvePlotter
Plotter.SetSampleFnc(Sample)
Plotter.SetSampleSize(G_Width,G_Height)
Plotter.SetColorARGB($FFFFFFFF)

Plotter.SetCellNum(20)
Plotter.SetInterpolation(True)
Time1=MilliSecs()
Local Pixmap:TPixmap=Plotter.Plot(G_Width,G_Height)
Time2=MilliSecs()

DebugLog (Time2-Time1)

Time1=MilliSecs()
DrawPixmap(Pixmap,0,0)
Time2=MilliSecs()

DebugLog (Time2-Time1)
Flip
WaitKey()
End

Function Sample:Float(X:Int,Y:Int)
	If (X<0) Then X=0
	If (Y<0) Then Y=0
	If (X>=G_Width) Then X=G_Width-1
	If (Y>=G_Height) Then Y=G_Height-1
	Return rgSample[X][Y]
End Function
Function GetSample:Float[][](Width:Int,Height:Int,StepSize:Int)
	Local a:Float=0.49,b:Float=0.5
	
	Local Sample:Float[][]
	Sample=Sample[..Width]
	For Local i:Int=0 Until Width
		Sample[i]=New Float[Height]
	Next
	
	For Local X:Int=0 Until Width
		For Local Y:Int=0 Until Height
			Local X2:Float,Y2:Float
			'Cassinische Kurve (Koordinaten mussten umgerechnet werden, da die Kurve normalerweise um den Punkt (0,0) geht).
			X2=Float(X-(G_Width Shr 1))/Float(G_Width)
			Y2=Float(Y-(G_Height Shr 1))/Float(G_Height)
			Sample[X][Y]=(X2^2+Y2^2+a^2)^2-4*(a^2)*(X2^2)-(b^4)
		Next
	Next
	
	Return Sample
End Function

Und noch ein Beispiel für eine Linienfunktion, die Max2Ds DrawLine-Funktion nutzt (ohne mit einem Rendertarget zu arbeiten): BlitzMax: [AUSKLAPPEN]

Function MarchingSquaresLine(Target:Object,X1:Int,Y1:Int,X2:Int,Y2:Int,ARGB:Int)
	'Die einzelnen Werte aus dem Farbinteger auslesen
	Local A:Float,R:Int,G:Int,B:Int
	A=Float((ARGB&$FF000000) Shr 6)/255.0
	R=(ARGB&$FF0000) Shr 4
	G=(ARGB&$FF00) Shr 2
	B=(ARGB&$FF)
	'Farb- und Alphawerte setzen
	SetAlpha(A)
	SetColor(R,G,B)
	
	'Linie zeichnen
	DrawLine(X1,Y1,X2,Y2)
End Function

Ich hoffe, dass jemand diese Module sinnvoll nutzen kann (mir ist bisher noch nicht wirklich etwas in den Sinn gekommen - außer Spielereien -, aber das kommt sicher noch Smile

). Und nun: Viel Spaß!

P.S.: Falls sich Fragen ergeben, im Quelltext habe ich meine Quelle für die Beschreibung des Algorithmus' angegeben, ansonsten gibt es am Ende des geposteten Wikipedialinks einige Hilfen. Und im schlimmsten Fall gibt's noch mich. Wink

EDIT (10.10.2011, 12:57): Korrektur einiger Fehler im Text, Hinzufügen des Funktionsbeispiels und Korrektur der Archive.
EDIT (01.01.2012, 12:56): Korrektur des Moduls Leiter.MarchingSquares: mir sind da zwei große Fehler unterlaufen, auf die ich gerade beim Arbeiten an meinem BCC #58 Beitrag gestoßen bin.. Peinlich, dass mir das so spät aufgefallen ist.