next »

[Hedgehodg]

E.g: Chunked LOD

[rivon]

You just need to decide how many LOD levels there will be, generate them and create a "table" or something with the distances needed for each LOD level. And then when drawing just calculate the distance of each chunk and draw the right LOD level for it according to the table of distances.

[eigenbom]

This is coming along well! The LOD will be really tricky, but if you take it slowly and make it simple then you'll get there.

Although you could do something like this, you should probably keep it really simple, have a perfect quadtree (depth of all leaves the same), the leaves of the quadtree should be subdivided quads/patches of terrain (e.g., 64x64 verts), don't worry about gaps between chunks, and forget the caching for now -- you can just generate the full terrain at startup.

(I personally wouldn't want to muck around with one of those more complicated LOD algo's, they sound nightmarish. I'd just use an existing 3d engine that already has a decent one.)

[Hedgehodg]

This could prove problematic for me. I think I went about creating the quad the wrong way. Each quad only ever has two triangles, so if you want to add more triangles you'll have to create four quads in the top left, top right, bottom left and bottom right corners, each quad in this case will also only have two triangles as well. Each quad has a flag which determines if it is the root node or not. When the vertices are constructed all the vertex data is passed up to the root node. So if you want and 16x16 grid there will be 256 quads .

So now that I read your post (eigenbom), I think I'll have to rewrite parts of it.

New approach:

Each quad will have 8192 = 2(64x64) triangles. When a parent quad subdivides (lets say in the top left quarter) it will not create vertices in that spot, and will will allow the child (0,0) to create it's vertices this leaves the parent with 6144 since (the amount of triangles in the parent is 1/4 (ed). The child's total width and height will be 1/2 of it's parent and because the child is not a parent it has 8192 triangles. So there will be 14336 triangles in total.

I hope that's correct  

[eigenbom]

Hmm, actually I'm rethinking this now, but you've probably spent more time thinking about the specific problem than I have, so take this with a grain of salt ... :S

My suggestion above of having the leaves contain more detailed terrain was a bit silly, as it complicates the model, so forget that for now, and get the basic LOD system working.

So basically we want this:

A single quad of terrain is represented with a node in a tree.
The root node is a single side of the cube.
A node also contains the geometry data for the quad (i.e., the two triangles).
A node has NxN children, representing splitting the quad into NxN sub-quads (N=2 for a quadtree).
A leaf-node has no children.
All leaves are at the same depth (i.e., a proper tree).

Each render() you traverse the tree, descending into a node only if it is close enough, otherwise you just render the geometry stored in that node. It's not the most efficient method (in both space and time) but its a starting point.

Also, you should colour the vertices depending on their depth in the tree so you can more easily see when the LOD changes.

[Hedgehodg]

Should I add a "depth" variable that determines how "deep" the quad is? So I could have a maximum depth of 'x', and the current depth, which is represented with 'y'. So when "y >= x" then make the node with a depth of 'x' a leaf node - so it can have no more children ( infertile )

So the "ConstructChildren" function looks like this based on your explanation:

Code:

    public void ConstructChildren(int n, int depth, int maxDepth) {
            if (!leaf)  {
                if (children == null) {
                    children = new Quad[n, n];

                    for (int x = 0; x < children.GetLength(0); x++) {
                        for (int y = 0; y < children.GetLength(1); y++) {
                            children[x, y] = new Quad(ref device, face, this.dimensions, this.planetCentre);
                            children[x, y].Index = new Vector2(x + index.X * 2, y + index.Y * 2);
                            children[x, y].SetSize(width / 2, height / 2);

                            if (depth >= maxDepth) {
                                this.leaf = true;
                            }
                        }
                    }
                }
                else {
                    for (int x = 0; x < children.GetLength(0); x++) {
                        for (int y = 0; y < children.GetLength(1); y++) {
                            children[x, y].ConstructChildren(2, depth + 1, maxDepth);
                        }
                    }
                }
            }
        }

'

And based on what you are saying I am assuming that I keep representing my quad with the two triangles?

And so, I haven't written it yet, but I guess the render function will look a little like this:

Code:

       private void renderPlanet(Player player, Planet planet) {
            Quad[] quads = planet.Quads;

            int[] depthTable = planet.GetDepthTable();

            foreach (Quad root in quads) {
                Quad[] children = root.GetChildren().ToArray();

                traverseChildren(children, depthTable);
            }
        }

        private void traverseChildren(Quad[] children, int[,] depthTable)  {
           foreach (Quad child in children) {
                float distance = -1f;

                Vector3.Distance(player.Position, child.QuadCentre, out distance);

                for (int i = 0; i < depthTable.GetLength(0); i++) {
                    if (distance <= depthTable[i, 1]) {
                       int depthLevel = depthTable[i, 0];

                        if (depthLevel < child.Depth) {
                            traverseChildren(child.GetChildren(), depthTable);
                        } else if (depthLevel == child.Depth)  {
                            renderChild(child);
                        else {
                            break;
                        }
                    }
                }
            }

[eigenbom]

yeh, use a depth parameter to limit the recursion for sure.

the nodes can be constructed like this (which is basically equivalent to your function):

Code:

void ConstructNode(depth,maxDepth)
{
  ConstructQuad()
  if (depth>=maxDepth){
    isLeaf = true;
    return;
  }
  else {
    isLeaf = false;
    make new 2x2 children array of nodes
    foreach(child)
      child.ConstructNode(depth+1,maxDepth)
  }
}

and your render function looks about right, good luck! and btw, i would've never been able to comprehend this in year 9 so mad props to u.

[Hedgehodg]

Okay, well I've been busy for the past week or so and haven't been able to work on this so I just slapped some code together, and nothing appears to be renderering...

Setup Code:

Code:

class Planet {
        private Quad[] quads;

        private Vector3 centre;

        private float[,] depthTable;

        public Quad[] Quads {
            get { return quads; }
        }

        public float[,] DepthTable {
            get { return depthTable; }
        }

        public Planet(GraphicsDevice device) {
            Vector3 cubeDimensions = new Vector3(4120, 4120, 4120);

            centre = new Vector3(0, 0, 0);
            quads = new Quad[6];

            quads[0] = new Quad(ref device, Face.Top, cubeDimensions, centre);
            quads[1] = new Quad(ref device, Face.Bottom, cubeDimensions, centre);
            quads[2] = new Quad(ref device, Face.Front, cubeDimensions, centre);
            quads[3] = new Quad(ref device, Face.Back, cubeDimensions, centre);
            quads[4] = new Quad(ref device, Face.Left, cubeDimensions, centre);
            quads[5] = new Quad(ref device, Face.Right, cubeDimensions, centre);

            float depth = cubeDimensions.X;

            depthTable = new float[6, 2];

            for (int x = 0; x < depthTable.GetLength(0); x++) {
                depthTable[x, 0] = x + 1;
                depthTable[x, 1] = (depth /= 2f);
            }

           
            for (int i = 0; i < quads.GetLength(0); i++) {
                quads[i].ConstructNode(0, depthTable.GetLength(0));
            }
        }
    }

Quad code:

Code:

public void ConstructNode(int depth, int maxDepth) {
            this.depth = depth;
           
            ConstructQuad();

            if (depth >= maxDepth) {
                this.leaf = true;

                return;
            } else if (depth < maxDepth) {
                this.leaf = false;

                children = new Quad[2, 2];

                for (int x = 0; x < children.GetLength(0); x++) {
                    for (int y = 0; y < children.GetLength(1); y++) {
                        children[x, y] = new Quad(ref device, face, this.dimensions, this.planetCentre);
                        children[x, y].Index = new Vector2(x + index.X * 2, y + index.Y * 2);
                        children[x, y].SetSize(width / 2, height / 2);

                        children[x, y].ConstructNode(depth + 1, maxDepth);
                    }
                }
            }
        }

Rendering code:

Code:

        private void RenderPlanet(Planet planet) {
            Quad[] quads = planet.Quads;

            float[,] depthTable = planet.DepthTable;

            foreach (Quad root in quads) {
                Quad[] children = root.GetChildren().ToArray();

                TraverseChildren(children, depthTable);
            }
        }

        private void TraverseChildren(Quad[] children, float[,] depthTable) {
            if (children != null) {
                foreach (Quad child in children) {
                    Vector3 quadCentre = child.QuadCentre;
                    float distance = -1f;

                    Vector3.Distance(ref position, ref quadCentre, out distance);
                    float depthLevel = DetermineDepth(distance, depthTable);

                    if (depthLevel > child.Depth) {
                        TraverseChildren(child.GetChildren(), depthTable);
                    }
                    else if (depthLevel == child.Depth) {
                        RenderChild(child);

                    }
                    if (child.Depth == 0 && depthLevel == 0) {
                        RenderChild(child);

                        break;
                    }
                }
            }
        }

        private float DetermineDepth(float distance, float[,] depthTable) {
            float depthLevel = 0;

            for (int i = 0; i < depthTable.GetLength(0); i++) {
                if (distance < depthTable[i, 1]) {
                    depthLevel = i;
                }
            }

            return depthLevel;
        }

        private void RenderChild(Quad quad)  {
            device.Clear(ClearOptions.Target | ClearOptions.DepthBuffer, Color.Black, 1.0f, 0);

            RasterizerState rs = new RasterizerState();
            rs.CullMode = CullMode.None;
            rs.FillMode = mode;
            device.RasterizerState = rs;
            device.DepthStencilState = DepthStencilState.Default;

            Matrix world = Matrix.Identity * Matrix.CreateTranslation(new Vector3(64 / 2, 0, 64 / 2));
            effect.CurrentTechnique = effect.Techniques["Coloured"];
            effect.Parameters["View"].SetValue(view);
            effect.Parameters["Projection"].SetValue(projection);
            effect.Parameters["World"].SetValue(world);

            foreach (EffectPass pass in effect.CurrentTechnique.Passes) {
                pass.Apply();

                device.DrawUserIndexedPrimitives(PrimitiveType.TriangleList, quad.Vertices.ToArray(), 0, quad.Vertices.Count, quad.Indices.ToArray(), 0, quad.Indices.Count / 3);
            }
        }

Knowing me I've properly made a *really* stupid mistake somewhere. ATM I am also learning C++ and Open GL using SFML for windowing. The reason for this is that I am using my laptop more and more, and since I am running debian on it, I can't work on this project. Thus far I actually prefer C++ and Open GL over C# and XNA. Once I learn enough I think I rewrite this in that...

[eigenbom]

aw man, you've gotta stop posting all your code. nobody likes debugging other peoples stuff but good luck! and yeh, c++ is boss!

[Hedgehodg]

3 Months later

I've sort of stopped working on this and just recently picked it up again. I've been working on the LOD thing, it's working somewhat to 4 levels of detail (it needs alot of tuning). The child structures themselves are generated on the programs start-up, any higher detail level and the wait becomes unbearable. The vertex data and whatnot are constructed when you reach that specific LOD level for that quad (in the render function). I have yet to make it so that the children are constructed when needed and not on start-up.

@eigenbom I went with your original idea of having a fixed size for the quad (ATM it's 16x16), it seems to work well.

Here is a really bad video of it (I did it on my school laptop since I don't have any video recording software on my desktop - and for some reason the program causes windows to generate a Blue screen of Death on my desktop :O - I think it's the graphics drivers) http://www.youtube.com/watch?v=NF_pHeMOju8

[eigenbom]

Ha, good to see its not abandoned

[peous]

That's a good start man !