Optimization of an algorithm
Hello all, as a mod hinted me, the Game Programming forum is mainly for C/C++, so I'll post here from now on.
I'm making a game library in C#.NET for XNA, and I've encountered the problem that in order for things to be visible CORRECTLY, you have to draw whatever is closest to you LAST.
I made an algorythm here that is used to recalculate things, as well as trim the unneeded triangles (you will see a lot of structures that aren't standard, just look at what they seem to do, that is what they do.).
Code:
public static PreBuffer<Vertex> Organize(PreBuffer<Vertex> Already, SharpCamera camera)
{
#region Set Vars
Camera = camera;
List<Triangle<Vertex>> triangles = new List<Triangle<Vertex>>();
Comparison<Triangle<Vertex>> SameTriangle = new Comparison<Triangle<Vertex>>(Closer);
IComparer<Vertex> SearchVertex = new VertexBinarySearcher();
List<Vertex> Vertices = new List<Vertex>();
List<int> Indexes = new List<int>();
IEqualityComparer<Vertex> SameVertex = new VertexPositionColorEqualityComparer();
#endregion
#region Create Triangles
for (int i = 0; i < Already.Index.Count(); i += 3)
{
Triangle<Vertex> temp = new Triangle<Vertex>();
temp.Corners[0] = Already.Vertex[Already.Index[i]];
temp.Corners[1] = Already.Vertex[Already.Index[i+1]];
temp.Corners[2] = Already.Vertex[Already.Index[i+2]];
triangles.Add(temp);
}
#endregion
#region Remove non-visible triangles from collection
for (int i = 0; i < triangles.Count; i++)
{
if(!IsTriangleVisible(triangles[i]))
triangles.RemoveAt(i);
}
#endregion
triangles.Sort(SameTriangle);
#region Recreating
for (int i = 0; i < triangles.Count; i++)
{
for (int j = 0; j < 3; j++)
{
int At = Vertices.BinarySearch(triangles[i].Corners[j], SearchVertex);
if (At > 0)
{
Indexes.Add(At);
}
else
{
Vertices.Add(triangles[i].Corners[j]);
Indexes.Add(Vertices.Count - 1);
}
}
}
#endregion
#region Send Output
PreBuffer<Vertex> Res = new PreBuffer<Vertex>();
Res.Index = Indexes.ToArray();
Res.Vertex = Vertices.ToArray();
return Res;
#endregion
}
The problem I encountered though, was that calling this every frame took up ALL the cpu if you go past 1000 squares. For a 500x500 terrain you need 250000 squares, so that's a big problem.
Calling it every second makes the game laggy and some triangles don't show properly until the switch.
So my question is, how can I optimize this to take up less CPU?