Ich sitz gerade an einem einfachen Terraingenerator den ich mir für die Verwendung mit der Mogre-Engine (.Net-Wrapper für Ogre3D) schreibe. Bei der Generierung einer Höhenkarte lege ich fest, das bei Höhe = 0.1 die Wasserlinie verläuft. Nun habe ich das Problem, das durch die zufällige Höhenverteilung viele kleine "Seen" entstehen können. Die will ich raus haben. Lösungsansatz ist derzeit alle Seen zu finden, die aus weniger Punkten bestehen als eine gegebene Anzahl und die Höhen dieser Punkte anzupassen. Dadurch kann ich "Seen" in vernünftiger Größe behalten und den kleinen Fitzelkram rauswerfen. Die Höhendaten sind derzeit in einem einfachen float[] gespeichert.
Problem:
Finde alle Punkte die zu einem See gehören, und alle Seen
Lösungsansatz - Region Growing
1. Erstelle Liste aller Pixel mit Höhe ≤ 0.1 (Candidates)
2. Erstelle Liste die gefundene Seen enthält (Regions)
3. Nimm ersten Pixel (current) aus Candidates und erstelle neue Region (Reg)
4. Nachbarpixel auch in Candidates? Ja => Zu Reg hinzufügen, aus Candidates löschen
5. Nimm nächsten Pixel (current) aus Reg => gehe zu 4.
6. Wenn reg einmal durchlaufen ist und noch Kandidaten vorhanden sind => gehe zu 3.
7. Wenn Candidates leer ist => Ende
Das funktioniert soweit auch ganz gut ... läuft allerdings mit 40.000 See-Pixeln gute 60 Sekunden. X( Da ich von C# nur mässig Ahnung habe, würde ich mich sehr freuen wenn mal jemand ein Auge auf den Code werfen könnte um mir Tips hinsichtlich der Performance zu geben. Eventuell berechne ich ja noch viele Sachen doppelt und dreifach, an die man auch einfacher kommen könnte oder die verwendeten Datentypen sind der Aufgabe nicht angemessen oder falsch verwendet. Falls jemand mit sowas Erfahrung hat, würden mich natürlich auch alternative Ansätze oder Tips zu einer möglichen Vorverarbeitung interessieren. Alles was ich dazu bisher im Netz gefunden habe, war viel zu kompliziert um von mir in annehmbarer Zeit implementiert zu werden.
Hier der momentane Code:
private static List<List<int>> PerformRegionGrowing(float[] hm, float min, float max)
{
int i=0;
_map = hm;
_size = (int)System.Math.Ceiling((System.Math.Sqrt(_map.Length)));
List<int> candidates = new List<int>(); //List of points that are between min and max and have no region assigned
List<List<int>> regions = new List<List<int>>(); //List of all connected regions we found
for (i = 0; i < hm.Length; i++) //Search all candidates
if ((hm[i] ≥ min) && (hm[i] ≤ max)) candidates.Add(i);
if (candidates.Count==0) return null;
List<int> reg; //Pixel-List of current region
bool found = true;
int x,y,offs,offx,candidate;
int[] ind = new int[8];
//Every point has to belong to a region
while (candidates.Count != 0)
{
//Begin new region with the first point in candidates
reg = new List<int>();
reg.Add(candidates.ElementAt(0));
candidates.RemoveAt(0);
offs = 0;
found = true;
while (found)
{
found = false;
current = reg.ElementAt(offs); //The pixel we check next
x = current / _size; //The x-Position
y = current % _size; //The y-Position
offx = x * _size;
//get indices of the 8 direct neighbours
ind[0] = (offx - _size) + (y - 1);
ind[1] = (offx) + (y - 1);
ind[2] = (offx + _size) + (y - 1);
ind[3] = (offx - _size) + (y);
ind[4] = (offx + _size) + (y);
ind[5] = (offx - _size) + (y + 1);
ind[6] = (offx ) + (y + 1);
ind[7] = (offx + _size) + (y + 1);
foreach(int j in ind)
if (candidates.Contains(j))
{
//It is a neighbour and a candidate, so it belongs to the region
reg.Add(j);
candidates.Remove(j);
}
if (offs < reg.Count - 1) found = true; //More pixels to check in this region
offs++;
}
regions.Add(reg);
}
return regions;
}
Wie gesagt, bin ich für jeden Hinweis wie das zu optimieren wäre dankbar.
Bis dann
