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?

1) What does your Prebuffer<>.Index getter look like? Does that just expose a List<> or an array? Is that an O(1) operation? Same with Triangle<>.Corners.

2) Your triangles collection might be better served by a LinkedList<> since List<>.RemoveAt() has to shift all the elements after the given index to the left to fill the gap:

Code:

            for (int i = 0; i < triangles.Count; i++)
            {
                if(!IsTriangleVisible(triangles[i]))
                    triangles.RemoveAt(i);  // Slow if many triangles are removed
            }

After that operation you can convert it back to a List<> to take advantage of Sort(), BinarySearch(), etc.

3) You can help List<> out by supplying an initial size. Wait to instantiate your Indexes and Vertices until you've figured out how many triangles are visible. Then you'll have a number to pass to the List<> for size. This will avoid memory reallocations done internally by the List<>.

Last thought: Have you run this through a profiler to see how much of that lag is actually caused by this method? It can help narrow down your efforts.

One more last thought: I'm not too familiar with XNA, but I thought it was smart enough to figure this stuff out on its own. For instance, if I draw a cube, and then another larger cube farther away after the first cube, I thought XNA automatically figured out that the first cube would obscure part of the second cube and draw them properly.

Why not put your IsTriangleVisible test inside the first loop? That way you're not adding triangles that you're simply going to remove again in a second loop.

Thanks both of you. Now my answer.
1. Nope, XNA only passes the vertices and indices to the shader, and IDK how to make HLSL calculate obscurity yet (I don't think it can since it processes one triangle at a time). Basically XNA thinks that you "may be trying to achieve some special effect", so it simply draws things in order.

2.PreBuffer<T> contains 2 arrays,
Indices and Vertices, configured in a way they can be quickly copied to actual buffers.

3. This is the method taking up all the CPU, it has been checked.

4. Triangle<>.Corners is an array with 3 slots.

5. as a side note, Vertex is my custom Vertex format that has a complex declaration that lets me use different techniques without switching vertex types. It isn't using up much CPU or memory tho.

6. IsTriangleVisible has been moved to the 1st loop.

with these new changes, it easily does 10 000 cubes. 100 000 is very laggy though, and 50x50 field of 1f sided cubes is absolute suicide...

I either have to optimize much MUCH more, find a different way to do this (maybe in the GPU, if so please throw me a hint at how, because I don't think it can be done). Possibly I don't have to call it every frame.

Just focusing on the remaining things that appear to be O(n*log n) or worse:
How are you comparing triangles for the sort?
Also what is the code for IsTriangleVisible?
I've used hashing to find the vertex when performing subdivision of a surface which is a similar problem to what you have here. It could probably provide a lot of improvement over the binary search.

This is the code for IsTriangleVisible:

Code:

private static bool IsTriangleVisible(Triangle<Vertex> check, SharpCamera camera = null)
        {
            if (camera != null)
                Camera = camera;
            Vector3 face = Vector3.Transform(AbsoluteVectors.Look, Camera.GetRotation);
            double FOVCOS = Math.Cos((double)FieldOfView);
            float Distance;
            Distance = Vector3.Distance(check.MiddlePoint, Camera.GetPosition);
            if (Distance > MaxDistance || Distance < MinDistance)
                return false;
            if (Vector3.Dot(face, Vector3.Normalize(check.MiddlePoint - Camera.GetPosition)) >= FOVCOS)
                return false;
            return true;
        }

Basically first eliminate them if they are too far, then check if inside FOV. I have no idea how to check for obstruction, if I could there would be no need for the rest of the code after this.

For the sort, I chek distance between two Triangle middle points:

Code:

private static int Closer(Triangle<Vertex> one, Triangle<Vertex> two)
        {
            float plusone = Vector3.Distance(two.MiddlePoint, Camera.GetPosition);
            float minusone = Vector3.Distance(one.MiddlePoint, Camera.GetPosition);
            if (plusone > minusone)
                return 1;
            if (minusone > plusone)
                return -1;
            return 0;
        }

Middle point is simply a Vector3 with

Code:

X=(Corners[0].X+Corners[1].X+Corners[2].X)/3

etc.

SharpCamera is a class I made that lets you rotate around relative axis and get precise view matrices without gimbal locks or quaternion related problems.

I'm quite new in graphics programming, so maybe I don't know some of the language features I should know >.<. If that's the case please do give me a hint and what kind of class I should use.

I would make a slight change to IsTriangleVisible, the idea being that if the result is going to be false you want to return as early as possible. I.e. not calculating what you don't end up using.
Move lines 5 and 6 to after the first return.

The comparison function end up subtracting the camera position for each point each time that point is compared to another point which will happen approximately log(n) times. You could try calculating that once for each point before the sort and caching the result. However it does temporarily use more memory so I'm not sure how much better it would be.
I don't have much time to take a closer look right now.

Done both, simply add a field to Triangle<T> with a float value containing the distance, this way I don't have to calculate it in IsTriangleVisible and during the sorting -> it's calced during triangle creation.
Lines 5,6 moves to after 1st return.

I'm seeing major improvements from the original... but it's still very laggy. I can't get rid of the idea that there's a better way then to calculate it every single frame but I can't put my finger on it -_-

And here we go... After more extensive searching I found the problem. I use spritebatch to draw in GUI (for now debug coords and angle values)
It turns DepthBuffer off. And DepthBuffer is the part that checks for obstuction, so all of this is no longer needed @_@. It was good algorithm practice for me though! XD Thanks again everyone!

Good to hear, a fantastic result!
Nothing lost here, you've clearly learnt a lot about optimisation in the process.
All the best!