Implement a simple octree editor

[IAmNotHanni]

TODO

Issues which must be resolved before starting with octree editor:

• Clean up clang-tidy warnings #209: Clean up clang-tidy warnings
• Do not pass data which is already contained in wrapper::Device #238: Do not pass data which is already contained in wrapper::Device
• Use or don't use const consistently for function parameters #239: Use or don't use const consistently for function parameters
• Complete the documentation with doxygen comments for every existing feature until next release. #81: Complete the documentation with doxygen comments for every existing feature until next release

---

It's time to implement a first generation of the octree editor. This will be a major new feature in our engine. Since it will probably be a challenging task, it's important to discuss the scope of the this first implementation. We should start simple and add more complex features later.

Here's the scope I have in mind:

Camera

• Implement a freely moving camera which is controlled by WASD keys

Octree rendering

• Implement wireframe rendering
• Implement vertex outline rendering

Octree selections

• Always render the selection grid on the octree surface where the camera is pointing at
• Render the selected cube highlighted
• Render the side of the selected cube which the camera is facing highlighted
• Render the edge of the selected face which the camera is facing highlighted
• Make only one cube selectable for now, no area or volume selection
• Keep the grid size constant for now
• Allow for movement of the selection along an axis (x,y,z) or in a plane (xy, xz, yz)
• Implement a way to find collisions between the camera ray and the octree geometry

Octree editing

• Delete the entire cube
• Fill the entire cube
• How to update vertices? We should not recreate the entire mesh buffer but only update necessary parts
• Edit the octree edge indentation by pressing Q + mouse scroll

Textures

• Implement texture rendering
• How to update textures on a cube dynamically?
• Render available textures using imgui
• Set the texture of one face of the octree
• Set the texture on all faces of the octree

Copy/Paste

• Implement copy+paste of cubes

---

Related: #190

[yeetari]

Implement wireframe rendering

Will work on adding this to the frame graph.

Render the selected cube highlighted

I will do some experimenting with different shaders, I think for now we can just pass in a different colour for highlighted cubes.

Implement a way to find collisions between the camera ray and the octree geometry

Firing a ray out of the camera using glm should be pretty easy, not sure about collision between the ray and the world though.

How to update vertices? We should not recreate the entire mesh buffer but only update necessary parts

From the vulkan side of things, it should be as simple as calling memcpy (since we always keep the vertex buffer mapped into RAM).

How to update textures on a cube dynamically?

It's just as simple as setting a different sampler in a uniform buffer. Although, since it's all one mesh, it might be tricky.

[IceflowRE]

Keep the grid size constant for now

A variable grid size should be very easy to do.

[IAmNotHanni]

A variable grid size should be very easy to do.

I agree now that I think about it again.

[IAmNotHanni]

There are 2 points on the list which I think might be difficult to do:

• How can we detect collisions of the camera ray with octree geometry efficiently?
• How can we render the selection?

[coornio]

G + scroll to change the grid power. You could try to keep 12 levels, but I'd recommend to make the player "bigger" than sauer's equivalent of gridpower 4 so as to make it possible to use smaller cubes for better details at places. So long as the lighting's precision is not an issue at big distances due to double precision (I think that's what's used in tesseract, thus misaligned shadows in large maps above size 12).

F + scroll for pushing the entire face of a selection (doesn't work past the first layer you're facing)

R + scroll to rotate the selection on the chosen axis. Might be a good idea to have a guideline of sorts to show how the available rotation positions might intersect with existing geometry to avoid mistakes. If selection outlines could also be changed in rotation instead of merely "extending" to encompass rotated geometry, even better.

X to flip selected geometry/entities on selected axis. Entities that can be rotated should likewise be adjusted accordingly.

C/V for copy/paste - applies for both geometry and entities in selection, supposing the latter are highlighted. Use along with CTRL key to copy/paste entities only.

SHIFT to move selected geometry around on the chosen axis.

Rt-click to extend selection if pressed while aim is outside of existing selection. If on existing selection, change selected axis for operations. If on existing selection and held to drag out with camera movement, moves the selection only without touching underlying geometry/entities.

CTRL + scroll to teleport to entities from those that are selected. No effect (yet) otherwise.

Space to deselect geometry, Ctrl+Space to deselect entities.

Y + scroll to change textures through the texture MRU list.

Z + scroll to change floatspeed incrementally. Default should be at 250 (supposing player scale is at sauer standard). Increments of 10 from 10-100, increments of 50 from 100-500, increments of 250 from 500+

L toggles flat color rendering (similar to how texreduce 12 looks), Ctrl+L toggles fullbright rendering. The two could be used in parallel but apply only in editmode.

Ctrl+Q toggles follow mode to other players, effective in and out of editmode but not during gameplay. Very convenient when you need to go to someone's location.

Shift+Space to teleport to where your crosshair is pointing, effective in and out of editmode but not during gameplay. Useful for instantly traveling long distances in editmode instead of flying there.

[MartinMuzatko]

Here are some of my ideas combined with ideas of a future vision of an octree editor.
Maybe some of these ideas are easy enough (a simple transformation applied to a set of cubes) to get implemented sooner than later.

Moving Cubes:
How do we solve the problem of moving one selection of geometry through another set of cubes/geometry, without replacing or removing the other one?
Sauerbaten solves this by temporarily hiding the selected cubes, but the selection cube stays visible.
I would like to be able to see the selected cubes as it gets moved. The concept of layers and layer attributes play well together with the concept of moving stuff around. To avoid z-fighting while moving on a grid, I would recommend to temporarily move the selection to a temporary layer, that has opacity (0.8) and scale (0.95 or 1.05 or alternating) applied so you can intuitively see where you are going, how the selection fits on new places and you avoid z-fighting.

Selection origin:
Sauerbraten has a red cube in the lower left corner of a cube to indicate its origin. This is important to know, in which direction pasting a larger selection will go. For now we can skip this, as we only focus on moving, rotating, selecting one cube.

In the future, I would love to see a preview of a paste, either on a new layer to guard off the existing geometry (extra keybinding) or before merging with existing geometry. Maybe we can borrow from the same features we have from moving cubes.

Grid sizes:
Infinite grid would be awesome. Combined with level of detail, we could easily optimize for close to infinite cube size. We probably want to simplify hitboxes, raytracing, PVS at some level then. But we are not so far anyway yet ;)

Being able to scale up or down entire selections or layers would be great.
When I remember correctly in Sauerbraten, it was painful to edit on smaller levels. This is because the selection cube was always off by a few pixels. If this could scale together with the grid levels, that would be fine.

This is everything for now. I am sure I have plenty of other user experience details once we get there.

[coornio]

Moving Cubes:
How do we solve the problem of moving one selection of geometry through another set of cubes/geometry, without replacing or removing the other one?
Sauerbaten solves this by temporarily hiding the selected cubes, but the selection cube stays visible.
I would like to be able to see the selected cubes as it gets moved. The concept of layers and layer attributes play well together with the concept of moving stuff around. To avoid z-fighting while moving on a grid, I would recommend to temporarily move the selection to a temporary layer, that has opacity (0.8) and scale (0.95 or 1.05 or alternating) applied so you can intuitively see where you are going, how the selection fits on new places and you avoid z-fighting.

It doesn't really hide it afaik. The name of the command is literally editcut. It stores the selection in a buffer for as long as the key is held down and you move your selection along with the mouse, then when the key is released the stuff saved in that buffer is pasted back in the selection's new location. Rendering the geometry as you move it along may introduce complexity but ghosting it WILL be useful so you can better see the end location before you release the selection back in the wild.

Selection origin:
Sauerbraten has a red cube in the lower left corner of a cube to indicate its origin. This is important to know, in which direction pasting a larger selection will go. For now we can skip this, as we only focus on moving, rotating, selecting one cube.

I have honestly never understood how the origin actually works and while it can be useful, the existing implementation is basic at best and requires the user to calculate relative position of any pastes or, following the lack of patience for that, just experiment by pasting in an emptier spot on the map. I'd rather consider the possibility of a paste preview as you said, and a directional compass.

In the future, I would love to see a preview of a paste, either on a new layer to guard off the existing geometry (extra keybinding) or before merging with existing geometry. Maybe we can borrow from the same features we have from moving cubes.

Grid sizes:
Infinite grid would be awesome. Combined with level of detail, we could easily optimize for close to infinite cube size. We probably want to simplify hitboxes, raytracing, PVS at some level then. But we are not so far anyway yet ;)

You can't exactly have infinite grid powers. After a certain point camera collision and precision of calculations becomes an issue. The code will potentially be a mess as well. We can upscale the player to a bigger grid power so that it's possible to edit smaller stuff. No one really ever used any cubes of size 8 and above seriously in a map you see.

Being able to scale up or down entire selections or layers would be great.
When I remember correctly in Sauerbraten, it was painful to edit on smaller levels. This is because the selection cube was always off by a few pixels. If this could scale together with the grid levels, that would be fine.

True, that IS still a very annoying thing. It's why I always upscale geometry by 2 or 3 sizes when I need to work on something that is gridpower 0 or 1, because of that stupid damn selection outline floating ABOVE the outlines when they're turned on. They have a fixed distance which is super annoying in the smallest sizes.

[IAmNotHanni]

If we're going to implement the update mechanism for vertex buffers, we could wrap this into the RAII wrapper directly, so we have some sort of update_vertices() methods.

[IAmNotHanni]

@coornio

(...) lighting's precision is not an issue at big distances (...)

Currently I think we won't be using lightmaps any time soon, so this is probably no issue.

[IAmNotHanni]

For the future: If moving a piece of octree geometry into another piece and there's no collision, we don't have to overwrite the target but could do a merge instead.

[IAmNotHanni]

For the future: Look for "encapsulated" pieces of octree geometry. This allows us to find incorrectly mapped geometry automatically.

[MartinMuzatko]

merge sounds good!

On the topic of "infinite grid levels"
Suppose we use the layering method. You would scale the grid system together with the layer. Which still allows you to align it with the main grid of the main layer.
So for details, you would use the same amount of say ~8 levels, but just scaled to smaller.

About your concern for precision: I have no fix for that. My hope is that details are repeated either way, so they can be optimized once and then re-used via prefabs

[IAmNotHanni]

Before we will implement the octree editor, we should resolve the following issues:

#209: Clean up clang-tidy warnings
#238: Do not pass data which is already contained in wrapper::Device
#239: Use or don't use const consistently for function parameters

[IceflowRE]

Added the list to the initial post.

[IAmNotHanni]

Also I added this issue to the TODO list before writing the octree editor: #81.
Good documentation is important.

[IAmNotHanni]

https://jslee02.github.io/awesome-collision-detection/

[IAmNotHanni]

In order to write the octree editor, we need to update the vertices somehow. We could pre-calculate the vertex cache and upload the entire cache (or only the parts which were updated?). Another option would be to use a vertex shader which takes care of octree indentation.