Level of detail algorithm not functioning correctly
- by Darestium
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.
