Level of detail algorithm not functioning correctly

Question

I have been working on this problem for months; I have been creating Planet Generator of sorts, after more than 6 months of work I am no closer to finishing it then I was 4 months ago. My problem; The terrain does not subdivide in the correct locations properly, it almost seems as if there is a ghost camera next to me, and the quads subdivide based on the position of this "ghost camera".

Here is a video of the broken program: http://www.youtube.com/watch?v=NF_pHeMOju8 The best example of the problem occurs around 0:36.

For detail limiting, I am going for a chunked LOD approach, which subdivides the terrain based on how far you are away from it. I use a "depth table" to determine how many subdivisions should take place.

void PQuad::construct_depth_table(float distance)  {
    tree[0] = -1;

    for (int i = 1; i < MAX_DEPTH; i++)  {
        tree[i] = distance;

        distance /= 2.0f;
    }
}

The chuncked LOD relies on the child/parent structure of quads, the depth is determined by a constant e.g: if the constant is 6, there are six levels of detail. The quads which should be drawn go through a distance test from the player to the centre of the quad.

void PQuad::get_recursive(glm::vec3 player_pos, std::vector<PQuad*>& out_children)  {
    for (size_t i = 0; i < children.size(); i++)  {
        children[i].get_recursive(player_pos, out_children);
    }

    if (this->should_draw(player_pos) ||
        this->depth == 0)  {
        out_children.emplace_back(this);
    }
}

bool PQuad::should_draw(glm::vec3 player_position)  {
    float distance = distance3(player_position, centre);

    if (distance < tree[depth])  {
        return true;
    }

    return false;
}

The root quad has four children which could be visualized like the following:

[] []
[] []

Where each [] is a child. Each child has the same amount of children up until the detail limit, the quads which have are 6 iterations deep are leaf nodes, these nodes have no children. Each node has a corresponding Mesh, each Mesh structure has 16x16 Quad-shapes, each Mesh's Quad-shapes halves in size each detail level deeper - creating more detail.

void PQuad::construct_children()  {
    // Calculate the position of the Quad based on the parent's location
    calculate_position();

    if (depth < (int)MAX_DEPTH)  {
        children.reserve((int)NUM_OF_CHILDREN);

        for (int i = 0; i < (int)NUM_OF_CHILDREN; i++)  {
            children.emplace_back(PQuad(this->face_direction, this->radius));
            PQuad *child = &children.back();

            child->set_depth(depth + 1);
            child->set_child_index(i);
            child->set_parent(this);

            child->construct_children();
        }
    } else {
        leaf = true;
    }
}

The following function creates the vertices for each quad, I feel that it may play a role in the problem - I just can't determine what is causing the problem.

void PQuad::construct_vertices(std::vector<glm::vec3> *vertices, std::vector<Color3> *colors)  {
    vertices->reserve(quad_width * quad_height);

    for (int y = 0; y < quad_height; y++)  {
        for (int x = 0; x < quad_width; x++)  {
            switch (face_direction)  {
                case YIncreasing:
                    vertices->emplace_back(glm::vec3(position.x + x * element_width, quad_height - 1.0f, -(position.y + y * element_width)));
                    break;
                case YDecreasing:
                    vertices->emplace_back(glm::vec3(position.x + x * element_width, 0.0f, -(position.y + y * element_width)));
                    break;
                case XIncreasing:
                    vertices->emplace_back(glm::vec3(quad_width - 1.0f, position.y + y * element_width, -(position.x + x * element_width)));
                    break;
                case XDecreasing:
                    vertices->emplace_back(glm::vec3(0.0f, position.y + y * element_width, -(position.x + x * element_width)));
                    break;
                case ZIncreasing:
                    vertices->emplace_back(glm::vec3(position.x + x * element_width, position.y + y * element_width, 0.0f));
                    break;
                case ZDecreasing:
                    vertices->emplace_back(glm::vec3(position.x + x * element_width, position.y + y * element_width, -(quad_width - 1.0f)));
                    break;
            }

            // Position the bottom, right, front vertex of the cube from being (0,0,0) to (-16, -16, 16)
            (*vertices)[vertices->size() - 1] -= glm::vec3(quad_width / 2.0f, quad_width  / 2.0f, -(quad_width / 2.0f));

            colors->emplace_back(Color3(255.0f, 255.0f, 255.0f, false));
        }
    }

    switch (face_direction)  {
        case YIncreasing:
            this->centre = glm::vec3(position.x + quad_width / 2.0f, quad_height - 1.0f, -(position.y + quad_height / 2.0f));
            break;
        case YDecreasing:
            this->centre = glm::vec3(position.x + quad_width / 2.0f, 0.0f, -(position.y + quad_height / 2.0f));
            break;
        case XIncreasing:
            this->centre = glm::vec3(quad_width - 1.0f, position.y + quad_height / 2.0f, -(position.x + quad_width / 2.0f));
            break;
        case XDecreasing:
            this->centre = glm::vec3(0.0f, position.y + quad_height / 2.0f, -(position.x + quad_width / 2.0f));
            break;
        case ZIncreasing:
            this->centre = glm::vec3(position.x + quad_width / 2.0f, position.y + quad_height / 2.0f, 0.0f);
            break;
        case ZDecreasing:
            this->centre = glm::vec3(position.x + quad_width / 2.0f, position.y + quad_height / 2.0f, -(quad_height - 1.0f));
            break;
    }

    this->centre -= glm::vec3(quad_width / 2.0f, quad_width  / 2.0f, -(quad_width / 2.0f));
}

Any help in discovering what is causing this "subdivding in the wrong place" would be greatly appreciated.

Edit

I've checked, and checked again and am almost certain that this is not an issue to do with my Camera code.

Answer 1

It's not easy to debug recursive structures, particularly when you're relying on a potentially bugged renderer to inform you. So the question is, Is this a bug in your rendering code, or somewhere else?

Suggestions:

• Ensure that when a larger, parent quad subdivides, you stop rendering it. In other words, render only what are considered to be its leaves. This helps you to know what is going on (at least from the renderer's PoV), because I see a lot of overlap in your link, and if that isn't the actual problem, then it's potentially obscuring the problem.
• Minimise your LoD levels down to 2; or even implement a simpler, 2-level dummy LoD for now to see what impact this has.
• Reduce the problem to 2D if possible, and see if you can render a simple view of the 2D version (a single plane of your cube). Then work it back up from there.

I don't like to be the guy that states the obvious, but you'll need minimal test cases to make headway. When all is said and done, break down and simplify each part as much as you can to see where the bug comes in. That means turning off bits of code where you can, or else swapping other, newly-written dummy code in.

I think it will be very hard for anyone to give you a solid answer on what's wrong with your code without executing it, so I (apologetically) provide this as an (interim) answer. I hope I won't be downvoted for trying to help.

Answer 2

I had some similar problems. Maybe the camera is in model space instead of worldspace? That was causing the problem in may project...

Does something like that helps?

// Calculate the position of the vertex in the world.
   worldPosition = mul(input.position, worldMatrix);

// Determine the viewing direction based on the position of the camera and the position of the vertex in the world.
   output.viewDirection = cameraPosition.xyz - worldPosition.xyz;

// Normalize the viewing direction vector.
   output.viewDirection = normalize(output.viewDirection);