# Level of detail algorithm not functioning correctly

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.

• Any attempts to log the relevant values? Oct 27 '12 at 14:13

## 2 Answers

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.

• Thanks for the suggestions, I've implemented your first two. I've previously tried your last suggestion in "Stage 2" of the project, where I originally had just a single quad that subdivided - I had the same issue there as well, but I think I'll take your advice and attempt to fix the issue on there first... Here's your changes implemented: youtube.com/watch?v=h8MyAFYtVMc&feature=plcp I'm confused in regards to why one quad subdivided to the third level. Strange. I think I'll debug the renderer first since it's a lot simpler than the other code. Oct 28 '12 at 5:01
• @Darestium, I could be wrong, but having noticed the glitch you mention, I get the feeling that it's not the renderer -- that it's in the quad / mesh / LoD code that you've done your best not to disturb ;) (I'm not sure if your LoD is more tightly tied to your renderer or the data structure being rendered). Let us know either way... Oct 28 '12 at 6:02
• To add to what Nick said: if you can unit test it, somehow, that usually helps you isolate and automate testing for specific issues. Oct 28 '12 at 9:45
• @NickWiggil It seems that I've got the single quad version to work, but when I try to apply the fix to the full cube, it doesn't work properly - I'll report back when I fix it... The thing is when I got the centre point of the quad I didn't take into account the scaling that each quad-element had applied to it. www.youtube.com/watch?v=Ra8ECiNY0Ys&feature=youtu.be Oct 28 '12 at 10:26
• @Darestium Good news!.. As my comment, "work it back up (to 3D) from there" Hope you're closing in, now. Oct 28 '12 at 10:51

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);