metzzo / ogl_destructible_map Goto Github PK

Currently the quad tree is generated only on loading and remains static. But during runtime the entire map might change which means that another quad tree structure might be more optimal. In general the goal should be to keep the number of triangles per leave low.

The proposed solution would be a "simplify" operation which is applied every frame that has some calculation time left:

Each leave has the following new attributes:

• positive_points: Is a set of points that consists of newly added polygons. E.g.: when drawing a circle, this would be a point cloud containing random samples of the circle. Because the point cloud should approximate the actual triangles, each point of "positive_points" must have a certain distance to each point of the points set, otherwise area is counted twice, that should not be counted twice.

• negative_points: Negative points is similarly as "positive_points" for polygons that are being removed.

This is done in order to avoid a costly triangulation and point cloud generation and instead reuse the existing information. Since the point cloud for the operation that acts on the map can either be precomputed or easily generated during runtime.

Now the simplify operation can update the quad tree:

Let x be |points| - |negative_points| + |positive_points|

If x below a certain threshold, this roughly translates to less surface area, and this again translates to that this leave is unnecessary => mark this leave as redundant
If x is above another threshold, this roughly translates to lots of surface area, and this again translates to this leave contains too much information => mark this leave as full

If a parent contains only redundant leaves these leaves must be merged into the parent.
If a leave is marked as full, split it and generate 4 new leaves and mark the original leave as parent. Assign each point (either from the points, negative_points or positive points_set) to the leave it falls into.

Finally the points, negative_points and positive_points must be merged together: Union points and positive_points. From the resulting set remove points as many as there are points in the negative_points set. The resulting set should approximate the density of vertices in the leave.

This would be my proposed solution to tackle quad-tree degeneration. Another way to do this, would be to take a big (what is big though?) chunk, that has been modified. From the triangles that are contained within these chunks, generate the point cloud. Create a new sub quadtree for the current chunk, including the clipping and triangulation. This would take much longer, but the point cloud would be more reliable. If the first approach does not work, this would need to be implemented as a fallback.

Currently each leave of the quad tree issues its own draw call. This might cause troubles on less powerful devices.

Therefore I propose a merging mechanism, based on the assumption, that a chunk that has not been changed for long time will also not be changed in the future.

• Every frame that has some calculation time left:
  • Try to merge the vertices of one of the oldest leaves together (while still keeping the old VAOs).
  • Mark it as a "render leave" and from now on when rendering just use the new VAO

This cannot be done all in one frame, since this would mean on each operation the entire map must be reorganized, which would break the purpose of the quad tree rendering system entirely.

If a child of a render leave is modifed, this merging must be reversed:

• If a child is modified, remove all render leaves that use the geometry of the modified leave
• use the "old" VAOs to render each leave
• update the milliseconds of the last modification

Texturing is very important for games. Since modifying the terrain without changing the texture is quite boring, the texture must also be editable.

The map size is too big to have one texture being spanned over the terrain, which is why a custom approach must be implemented:

The fragment shader has n base layer, which are textures that are tileable and cannot change during the course of the game. These would be for example: grass, dirt, ... basically how the map would look like at the beginning.

Additionally there are k overlay textures, which can be changed during runtime via FBO. The overlay texture is divided into x*x sized areas and each area might be assigned to a certain area of the real map, this is called a tile (keep in mind this must not be the same size of a leave, multiple leaves might be assigned to the same area). At the beginning no tile of the map is assigned to a texture area.

To do the assignment there is an assignment texture. For a (r,g,b) color at position (x,y) of the assignment texture, the (x,y) position encodes the tile position. The r component encodes the ID of the overlay texture. G encodes the tile x position and B the tile y position. Using this information it is easily possible to get the color of the overlay texture.

If the texture is changed for a tile. First it is checked if there exists an assignment for this tile, if yes, just draw into the given area into the overlay texture.
If no, which means there is no assignment yet for the tile, a new tile has to be assigned. In which case the next free area is assigned for the current tile. If there is no tile available, use the following strategy:

• find an assigned area, where the corresponding map is completely empty (in which case the overlay is not visible anyway)
• Reassign the "oldest" area to the new tile. This causes the old tile to loose its overlay though.
  This architecture can be seen as a simple Paging system.

Alternatively a downscaling approach could be implemented: if there is not enough space in the overlay textures, simply downscale existing areas. Which way is the best must be empirically verified.

Picking arbitrary positions on the map is a necessity.

• Convert 2D screen coords into 3D ray
• Implement ray <-> plane collision detection