Hey!

It's me again haha.

I recently changed from Monogame to XNA as for several reasons (including ContentPipeline and Shaders) and

decided to redo my Icosphere-Project a little.

Heck a little is not quite it, I'm going from scratch, as I got to the edge, where the compiler is telling me, that no more Primitives can be hold for one TriangleLine and I do need quite more for nice Terrain on a Sphere.

So I looked up some concepts of others, including the QuadTree, which seems logic to me as I need more Primitives but don't want to get limited by XNA or to calculate the mass of Data if I could hold the required amount of vertices.

As I am learning quite in a different way than other would recommend, I want to come up with own Ideas to create such a thing and after that, read what others did or what the "official solution" is.

I'll keep it short to not more you (haha).

My concept is to have a struct Quad which contains its 4 Positions and 6 Indices (as made from triangles) and its 4 Child-Quads

(It is like a linked List with 4 Nexts haha).

public struct Quad
        {
            VertexPositionColorNormal[] positions;
            Quad[] children;
            int[] indices;
            public Quad(Vector3 p1,Vector3 p2,Vector3 p3,Vector3 p4)
            {
                positions = new VertexPositionColorNormal[4];
                positions[0].Position = p1;
                positions[1].Position = p2;
                positions[2].Position = p3;
                positions[3].Position = p4;
                indices = new int[6];
                indices[0] = 0;
                indices[1] = 1;
                indices[2] = 2;
                indices[3] = 0;
                indices[4] = 2;
                indices[5] = 3;
                children = new Quad[4];
            }
            public void addChildren(Quad c1,Quad c2,Quad c3,Quad c4)
            {
                children[0] = c1;
                children[0] = c2;
                children[0] = c3;
                children[0] = c4;
            }

This is wrapped by another struct as I want to have 6 Root-Squares forming a Cube.

public struct QuadContainer
        {
            public List<Quad> quadList;
            public QuadContainer()
            {
                quadList = new List<Quad>();
            }
            public void AddQuad(Vector3 p1,Vector3 p2,Vector3 p3,Vector3 p4)
            {
                if (quadList.Count < 6)
                {
                    quadList.Add(new Quad(p1, p2, p3, p4));
                }
            }
        }

This is, what I made so far.

Now my further Thoughts:

• I'll have a function which creates the Quads and it's childs to an extend, that I want, so every of the 6 Roots have n^n childs.
  I do not care about double Indices , which happens when calcing the halves for a new vertex, at this point ,as it would require a global List of Indices which would make things rather complicated.
• I normalize each vector and multiply it by a given scale to have the desired size and a sphere at all.
• I'll have a function which takes the view's position, look at, Up-Vector and angle to Calculate the distance to the Construct and which of the vectors are seen at all to built a a list which contains only the seen Vertices and Indices. Further it calculates the distance to the Quads to see which resolution it should have.
  
  Problem here: This would require to go through all Parental Quads and see if they are close enough and run through each child as it proves true (recoursive spoken). This might have an inpact on Calculation-Time needed. I do reduce it by not regard those quads not seen but either way this should be consuming. Any Ideas here?
  
• As Filling the Index-Buffer and VertexBuffer, I'll check for any double Vertex and sort them out to replace the index in the IndexBuffer with the index of the first Vertex occured.
  
  Promlem here: Same as above but can be done in the calculation of Distance and Frustum, so it won't consume any extra time

Is that acceptable till here?

Cuz now there is my little problem I didn't think quite enough of yet.

When adding terrain, should I do it in the Step where the vectors are normalized and scaled? Like adding up the height?
This would result in a If(terrainWished) case, so I still can make Spheres without Terrain.

The other case, namely adding the terrain at the end of creation would give me problems with runtime again, as

it would go through all quads again (and this truly sucks even though I tried this with the max limit of Primitives per Buffer and with 10 Spheres with just a little delay on first draw. But I need to keep in mind that I want whole Solar-Systems with dynamic shaders for Atmospheres etc)

What do you think?

Edit:

Totally forgot to ask:

Which Noise Generator should I implement?

Perlin or fbm or ridged multifractal?

Additional Note:

As I am still planning, I've come to a little Problem to solve.

When Transforming/Rotating/Scaling the Sphere, I'll have the the issue that the calculations won't fit.

As it is a poor solution to first manipulate the Planet and than call a function to update the internal calculation-variables.

It seems the most elegant solution is to give the class a Draw-Methode on it's own which usually takes the projection, view and position-Matrix and first calculates the distances. This would encapsule the whole process pretty good.

Meaning, that the Index Buffer as well as the Vertex Buffer will also be intern. Further the Class needs to get public variables so the colors and/or

Textures can be set properly to the needs of the user.

I wonder which effect this will give in regards of the shader, meaning if it will give problems with implementing there, as it is encapsuled, one can't

affect the Draw-Methode directly. More "research" needs to be done here.

Maybe I just spend the Class an own Update methode for the Rotation/Translation/Scaling - Act and let the User call the Calculation-Methode to get the Buffers and then just

let the Users Draw-Methode do the rest?

Well another problem here: The Useres Draw-Methode also needs the Translation-Matrix. This could be also public.

Edit:

It seems like my final solution will be a mix of the poor and elegant solution. I'll have interne Translation-Matrix the user can set via getter setter methodes.

I need to give the option to let the given Matrix multiply the internal Matrix or replace it. This means, instead doing somthing like this: "world *=" or "world =" the user gets

"Planet.SetWorld(bool multiply, Matrix matrix)".

Another approach which seems doable is to make the internal Matrix public and get set by the user directly and just call the internal Update Methode within the Users Update-Methode.

About the Quad-Tree-Structure:

As said before, I need to verfiy the existence of double or triple (or whatever) Vectors and eliminate them in the final step where I choose the Vertices to be drawn.

I must Identify them by their position which can be messy due to floating-point-precision. I could give them a tolerance, but that would lead to a limit of resolution and minimal size.

Maybe I'll give all Vertices an own ID which will be stored in the Quad and it's direct Childs. That way I could store the "done Child-Vertices" in a Dictionary and get the doubles out. Maybe even in the Roots as they could have user settted Parents which would lead that the methode "thinks" these are childs and have the same Parents (Maybe with negative Values).

Alright.

I did some improvements.

Some of the Old Ideas got obsolet.

I DO use direct compare between two vectors as Microsoft overloaded the == for them.

The Dictionary also is gone, as I simply go through the existing Lists of Values and compare each of them with the current.

As I needed a Methode, that translates the Quadtree into a List (which is a lot simpler than using the array directly) I came to a problem, that the indices stored in each quad won't work, when eliminating multiple vetrices with the same values. Offsets won't work as if one Vector gets eliminated and the index pointing to the first one that existed with that values the following won't fit anymore.

Knowing this, I just got rid of the indices stored in the Quad, as they are all the same anyways.

First of all: This is the Quad-Struct now.

public struct Quad
        {
            public VertexPositionColorNormal[] positions;
            public Quad[] children;
            public Quad(Vector3 p1,Vector3 p2,Vector3 p3,Vector3 p4)
            {
                positions = new VertexPositionColorNormal[4];
                positions[0].Position = p1;
                positions[1].Position = p2;
                positions[2].Position = p3;
                positions[3].Position = p4;
                children = new Quad[4];
            }
        }

And the Container-Struct stays the same like this:

public struct QuadContainer
        {
            public List<Quad> quadList;
            
            public void AddQuad(Vector3 p1,Vector3 p2,Vector3 p3,Vector3 p4)
            {
                if (quadList.Count < 6)
                {
                    quadList.Add(new Quad(p1, p2, p3, p4));
                }
            }
        }

First of all, I needed some global Variables as they need to be accessed by many Methodes (they will change in its privacy property during the writing process)

        QuadContainer quadContainer;
        int steps;
        VertexBuffer vertexBuffer;
        IndexBuffer indexBuffer;
        List<VertexPositionColorNormal> vertexList;
        List<int> indexList;

That are all of them for now (at this point I do not even need the buffers as I am in an early stage of simply creating and translating the tree)

BTW steps is the depth of the Tree (which will be renamed soon)

Also I needed an entry-point (which later surely will be the Konstruktor, but for now its just a Methode)

It initialize the Lists and gets the desiredn depth, as well as it creates the 8 Vectors for the Cube.

After that it calls the function to create a Tree of each Quad.

public void initQuadTree(int depth)
        {
            vertexList = new List<VertexPositionColorNormal>();
            indexList = new List<int>();
            quadContainer = new QuadContainer();
            quadContainer.quadList = new List<Quad>();
            steps = depth;

            Vector3 p1 = new Vector3(-1,1,-1); Vector3 p2 = new Vector3(-1,1,1); Vector3 p3 = new Vector3(1,1,1); Vector3 p4 = new Vector3(1,1,-1);
            Vector3 p5 = new Vector3(-1,-1,-1); Vector3 p6 = new Vector3(-1,-1,1); Vector3 p7 = new Vector3(1,-1,1); Vector3 p8 = new Vector3(1,-1,-1);

            quadContainer.quadList.Add(new Quad(p1,p2,p3,p4));
            quadContainer.quadList.Add(new Quad(p7,p6,p5,p8));
            quadContainer.quadList.Add(new Quad(p6,p2,p1,p5));
            quadContainer.quadList.Add(new Quad(p5,p1,p4,p8));
            quadContainer.quadList.Add(new Quad(p3,p2,p6,p7));
            quadContainer.quadList.Add(new Quad(p8,p4,p3,p7));

            buildTree(quadContainer.quadList[0], steps); buildTree(quadContainer.quadList[1], steps);
            buildTree(quadContainer.quadList[2], steps); buildTree(quadContainer.quadList[3], steps);
            buildTree(quadContainer.quadList[4], steps); buildTree(quadContainer.quadList[5], steps);
            
            copyToBuffers(steps, quadContainer.quadList[0]);
            
        }

buildTree is a simple Recursive Methode which init all Children of the Roots to have valid values

public void buildTree(Quad current,int steps)
        {
            if(steps == 0)
            {
                return;
            }
            else
            {
                Vector3 p1; Vector3 p2; Vector3 p3; Vector3 p4;
                
                p1 = current.positions[0].Position;
                p2 = (current.positions[0].Position+current.positions[1].Position) / 2f;
                p3 = (current.positions[0].Position+current.positions[2].Position) / 2f;
                p4 = (current.positions[0].Position+current.positions[3].Position) / 2f;
                current.children[0] = new Quad(p1, p2, p3, p4);
                buildTree(current.children[0], steps - 1);
                
                p1 = (current.positions[0].Position + current.positions[1].Position) / 2f;
                p2 = current.positions[1].Position;
                p3 = (current.positions[1].Position + current.positions[2].Position) / 2f;
                p4 = (current.positions[0].Position + current.positions[2].Position) / 2f;
                current.children[1] = new Quad(p1, p2, p3, p4);
                buildTree(current.children[1], steps - 1);
                
                p1 = (current.positions[0].Position + current.positions[2].Position) / 2f;
                p2 = (current.positions[1].Position + current.positions[2].Position) / 2f;
                p3 = current.positions[2].Position;
                p4 = (current.positions[2].Position + current.positions[3].Position) / 2f;
                current.children[2] = new Quad(p1, p2, p3, p4);
                buildTree(current.children[2], steps - 1);
                
                p1 = (current.positions[0].Position + current.positions[3].Position) / 2f;
                p2 = (current.positions[0].Position + current.positions[2].Position) / 2f;
                p3 = (current.positions[2].Position + current.positions[3].Position) / 2f;
                p4 = current.positions[3].Position;
                current.children[3] = new Quad(p1, p2, p3, p4);
                buildTree(current.children[3], steps - 1);
            }
        }

Here I need some improvements to keep it a reader-friendy haha.

The Last New Methode is the translation of the Tree into the List. Its still a TODO as it needs improvements of performance but for now it works just fine.

It is also recursive, but other than the buildTree, it goes straight to the end of each Tree and get the leaves. Then it checks the List if the Vector already exists and decides if the Vertex gets submited or the Index just points to a previous one.

public void copyToBuffers(int depth, Quad currentQuad)
        {
            if(depth != 0)
            {
                for (int i = 0; i < 4; i++)
                    copyToBuffers(depth - 1, currentQuad.children[i]);
            }
            else
            {
                bool[] exists = new bool[4];
                int[] index = new int[4];
                for (int i = 0; i < 4; i++)
                {
                    
                    for (int j = 0; j < vertexList.Count; j++)
                    {
                        if (vertexList.Count != 0 && currentQuad.positions[i].Position == vertexList[j].Position && i!=j)
                        {
                            index[i] = j;
                            exists[i] = true;
                        }
                    }
                    if (!exists[i])
                    {
                        index[i] = vertexList.Count;
                        vertexList.Add(currentQuad.positions[i]);
                    }
                }
                indexList.Add(index[0]);
                indexList.Add(index[1]);
                indexList.Add(index[2]);
                indexList.Add(index[0]);
                indexList.Add(index[2]);
                indexList.Add(index[3]);
            }
        }

What needs to be done here is:

• Calculate which of the Quads is in View-Angle + Security-Angle (as I don't want to have holes haha) so I can leave out as much as possible
• Calculate the distance to the the Quads to see which depth it should go to.

I need to think about those two a lot because of some Problems I assume there are.

Maybe I solve the depth-Calculation like this:

I calculate the distance to each left-over Quad, the one which are far away gets a low depth

the ones near gets a higher one.

As it goes deeper and deeper, the depth changes depending on how near the next smaller Quads are. So only a couple of Quads gets the Maximum Resolution

Any other Ideas how to solve this?

Any thoughts about the code so it would work better?

Next Update:

To improve the speed of calculation (which was reaaaally slow because of the doubled for-loop when looking for doppelganger-vertices) I decided to

change the search back to a dictionary-search as this would speed up the hell out of the program.

But I'm stucking. How do I get a unique Key from the combination from X Y Z - Values?

Something like

float key = (normal.Position.X*640000000) + (normal.Position.Z * 320000) + normal.Position.Y*100;

I don't get it.

Anyone got tipps?

alright. I got the solution now.

I use the Vector3 as an Index for the Dictionary.

So I create something like that:

private Dictionary<Vector3, int> middlePointIndexCache;

Init it in the Init-Methode:

this.middlePointIndexCache = new Dictionary<Vector3, int>();

And ask it for help like that:

VertexPositionColorNormal normal = new VertexPositionColorNormal();
normal.Position = currentQuad.positions[i].Position;
normal.Position.Normalize();

Vector3 key = normal.Position;
int ret;
if (this.middlePointIndexCache.TryGetValue(key, out ret))
{
     index[i] = ret;
     exists[i] = true;
}

Giving me a huge speedboost of even a couple of minutes on highest depth possible, which, in my case, is 8 Childs for each Root,

making it to 6*4^8 before it gives me error cuz of MemoryOut or Too Much Primitives.

Well okay for Primitives it is 2*(6*4^8) as each Quad is made of 2 Triangles.

Impressive results.

Next step is to only load the Visible Vertices and only the depth I need for a neat look from a given distance.

This will reduce the actual amount of needed Vertices dramatically (in worst-case almost half, as only half a Planet can be seen at a time)

which means, even if i go into full detail for all Quads, I can go even deeper!

I start to realize the might of this system.

Anyways. Here is a Pic of a Sphere with highest resolution:

[attachment=23562:Result3.png]

The crazy thing about this is: The size of this thing is scaled up to 1000 times and still has a more smooth surface than the previous version.

Today is a little planning again:

There are still 3 Points missing before going to the advanced stuff (which are Atmosphere/Atmospheric Scattering, Sky, Textures, Water, etc)

• Exculde Vertices which are not in View
• Subdivide near Quads more than far Quads
• Generate Terrain

To Point 1)

For the excluding Vertices I need to compare if the Angel of View to the Position of the Vertices. This won't affect those, that are

behind other Vertices, but only those which are "not in the Window".

For excluding those behind other Quads, I need to Calculate something like the Z-Buffer.

My Plan for this is to calculate the distance to the Camera and load the Vertices into the Buffer. If there is anyone which got the same Position but

another Depth (depending on View-Position, which gives me heads for the formular) it must decide wether its nearer than the one before.

The Vector pointing to (or from) the Camera to a Vertex is a simple addition of Vertex-Vector and Camera-Vector. Maybe I just need to check

if any of those Vectors is a scaled Form of another Vector. That would mean, I just have to use a Cross-Product and compare it to Zero.

I just didn't figure out how to do this an efficient way as I would need to compare this Vector to ALL other Vectors, which would be a huge Amount.

Another Approach would be to just calculate the Vectors to the Camera and eliminate those which are further away than half of the sphere.

For That I just have the Value of the Distance from Camera to MiddlePoint of the Sphere.

After that I would need to calculate each Vector from the Vertices parallel to the first one.

An much easier approach would be to have the angle between Vector From Middle of Sphere to Vertex and Vector from Middel of Sphere to CameraPos

The Further away the Vertex, the bigger the angle, at the Half, the Angle is 90°/270°, and at the frontMost Point the angle is 0°.

So each Vertex with an Angle biggeer than 90 and smaller than 270 won't be loaded at all. Half of Vertices means more Detail possible without overloading the Lists.

To Point 2)

Subdividing ones more than others should be rather simple. I'll have a distance, which is the Maximum Distance from Planet which means: After this points the

Quads stays the same size even if going further away, to keep it smooth.

Then I calculate every included Vertex with the minimum depth. If the Vertex is closer to the Camera than the Maximum Distance it gets another Subdivide and the Maximum Distance gets (for example) halved for the next iteration. that way only the nearest Quads gets the full resolution.

To Point 3)

I still didn't get to do a proper Noise-Generator so this is on ice for now.

But the Value could apply when normalizing the Vectors.

A possible Problem here: not each Corner is next to its followed drawn one, in regards of the four root-squares.

this means, I need to find a way to make them appear as such.

A much simpler idea is to just apply the noise to each Root individually having a constant level at the borders, so

it apears as they would go into another whithout a break.

The much simplest way would be to give each Vertex the middle-value of the 6 Vertices around them and then add a random value. But that

won't look nice, I think.

Any Idea to Point 3?

Well I got an answer to Point 3 now.

I'll temporary handle the sphere as its original Form: A Cube.

That way, I can create a Height-Map with the Form of an unfolded Cube.

Whe calling the Tree-Constructor, every Point in the Quad is getting a point from its corresponding Height-Map.

I'll try to get the Height Map to have its edges have the same height-values, so when overlapping, it is the same height.

That way, even when eliminating redundant Vertices, I have a smooth gapless map. Same can do with Colors or Textures.

I guess the Planning is over now.

Summary:

• Pre-Z-Buffering will be done by getting the angle between the Vector Camera To Middle and the Vector Middle To Vertice. Everything between 90° and 270° will be ignored
• Pre-Culling will be done by comparing the To-Be-Translated Tree-Entry with the Frustum.
• Detail-Depth will be calculated by getting the distance between Camera and Quad minimum depth is given, every Position closer as the Minimum-Depth Border will cause a Subdivision.
• Terrain/Texture/Color will be applied by handling the Planet as a cube and making a Hightmap, formed as an unfolded Cube. Every Rendered Quad will get a piece of this Map attached to it and thus alters the normalized Vector.

Last Point: Get a propper Noise-Function