Closed zauberparacelsus closed 4 years ago
Interesting, I didn't know this one. How is it different from marching cubes?
It's an extended version of Marching Cubes, designed to create LOD transitions so that more distant areas use less geometry (and therefor require less resources to render).
Another option is Naive Surface Nets. If you have code for generating blocky voxel meshes, you're already halfway done. Naive Surface Nets can also be extended to have variable levels of smoothing, so that they can be used to represent both blocky and smooth geometry.
Well, I thought about LOD before, and it extends beyond rendering. The data has to have LODs too, mostly because it can take a lot of memory. Maybe it's doable with some kind of octree? Also, there could be multiple cameras looking at the same dataset from different points of views. But for now I don't feel I'll implement that. And if there is only one viewer it's possible to optimize the LOD a little bit, I guess. When I think about that, I really consider extreme cases like No Man's Sky or Star Citizen, that we could also call "LOD, the Games" :p
My current renderer is not only designed to render cubes, but any mesh indexed by type (but I lack a demo of it). If a smooth renderer has to be implemented, then it's a different interpretation of the data, and it will be a separate one, working on a separate channel. For example, using channel 1 for smooth terrain, and channel 2 for blocky buildings. I like mixing both because they have their pros and cons.
Last note: I'm not currently active on this module, because I work on other projects and I have less time now. I'll probably come back to work again in this field but can't say when.
Okay. Funny thing though, I was just about to write up a feature request for using an octree to represent the voxel data. Storing individual chunks as an Octree instead of the entire scene would be a good way to mitigate the performance overhead.
The idea I had was to add an option in the module to set the number of LOD levels. It would currently be 1 level. Level 2 would subdivide the current grid into a 1-level octree structure, and so on, so the root is still a grid and extends to the farthest the viewer can see.
But I said earlier only one viewer would be supported yet. So instead of having a deep octree, why not having indexed grids? No need for hashing, and accessing a LOD is just a matter of an index (I wonder if I am clear enough?).
When dealing with voxel data, I also found OpenVDB, which subdivides blocks by a factor of 8 instead of 2 (by block I mean "cubic chunks", if we were to use Minecraft's terminology). However I feel it's too abrupt of a transition, or maybe I miss something.
Just an update to say that I'm currently working on a Transvoxel implementation for this module. Godot 3.0 dev branch is very unstable at the moment so I can't test or show much, but it's something I would like to experiment with.
Nice! I can imagine that this type of special voxelization can be used for multiple purposes: endless high-def Voxel terrain or useful tool asset to create stages/levels and saving them to a file.
Can't wait for 3.0, its the era of modern 3D Dev Design! : )
I just pushed an update... the module is now able to polygonize smooth voxels, using a float representation of an isolevel (below zero is air, above zero is matter). It's a rough starting point, so they aren't textured or colored for now. I didn't decided yet if the API will remain as it is, sorry if it looks messy. I also updated the example project :)
Zylann, I might be able to help you out with the untextured Smooth Voxels, a while ago I asked on the Godot QA about applying a seamless texture wrap to a 3d Object and the answer was very valuable:
https://godotengine.org/qa/12952/automatic-seamless-texture-object-through-materialshader
Or if you want the code that works, here you go (Answer was provided by Mollusca BTW):
VERTEX SHADER:
VAR1 = vec4(SRC_NORMAL.x, SRC_NORMAL.y, SRC_NORMAL.z, 0.0); VAR2 = vec4(SRC_VERTEX.x, SRC_VERTEX.y, SRC_VERTEX.z, 0.0);
FRAGMENT SHADER:
uniform texture diffuse; uniform float sharpness; uniform float texture_scale;
vec2 uv_x = vec2(VAR2.z, 1.0 - VAR2.y) / texture_scale; vec2 uv_y = vec2(VAR2.z, 1.0 - VAR2.x) / texture_scale; vec2 uv_z = vec2(VAR2.x, 1.0 - VAR2.y) / texture_scale;
vec3 col_x = tex(diffuse, uv_x).xyz; vec3 col_y = tex(diffuse, uv_y).xyz; vec3 col_z = tex(diffuse, uv_z).xyz;
vec3 weights = abs(VAR1.xyz) - vec3(0.2); // the 0.2 adds additional sharpness, not necessarily needed weights.x = pow(weights.x, sharpness); weights.y = pow(weights.y, sharpness); weights.z = pow(weights.z, sharpness); weights = max(weights, vec3(0.0)); weights /= dot(weights, vec3(1.0));
DIFFUSE = (weights.x col_x + weights.y col_y + weights.z * col_z);
Also, if you really want to go crazy and apply blending a texture to a different one based on height, terrain, or biome purposes, then check out "Godot Tutorial # 6 Splatmaps": https://www.youtube.com/watch?v=RLAG4RbT-5U
P.S. Its just a matter of implementing a Material Export in Godot Voxel's Inspection tab to allow Material Shader and Material Shadergraph.
Is this triplanar mapping? Also shaders aren't working yet in 3.0, so I'll have to wait a little before trying.
It is Tri-Planar Mapping and I just wanted to point out a possible resource/idea should you have the chance to try it out, just simple heads up for good cause.
The video link is broken, but it works when I copy it instead, weird.
I know this video, the technique is quite simple, though you need to sample 5 textures at a time (including the splatmap). With voxels I intend to encode the "splatmap" into the voxels, which will end up in the mesh itself, so it gets down to 4 texture fetches. But combined with triplanar it ends up with 12 fetches, which is quite a lot for just calculating the albedo. I'll give it a try anyways.
@Zylann Is your smooth voxels implementation Transvoxel as you had planned, or did you go with another algorithm?
Yes, it is Transvoxel. It's not complete yet, for now it only does the modified marching cubes because I'm working on the design of the LOD system before going further.
Progress is progress. :)
I found two implementations of the Cubical Marching Squares algorithm, another voxel mesher algorithm. It is additionally able to generate "adaptive geometry", meaning it can generate simplified geometry for areas that need it less.
https://github.com/mkeeter/kokopelli/blob/master/libfab/asdf/cms.c https://bitbucket.org/GRassovsky/cubical-marching-squares
original paper: http://www.csie.ntu.edu.tw/~cyy/publications/papers/Ho2005CMS.pdf
I'm also interested in implementing dual contouring, so at this point I think this module could integrate different choices of algorithms, if it doesn't involve too much differences in ways of storing data^^ (I like to keep logic and data separated)
I'm working again on Transvoxel in the transvoxel
branch, and getting closer to a true implementation which includes transition cells. There are several things to note about it:
The current smooth terrain uses basic marching cubes with marching squares skirts for hiding LOD cracks (actually called DMC, but with simplification part disabled because it's not working well). Here are preview timings when the two algorithms build a 32x32x32 mesh in debug mode:
It's not release timings, but still relevant IMO. Reasons for such a speed up are mostly caused by the inclusion of vertex sharing as part of the main iteration, while DMC was using a random-access map to find vertices at the same positions.
Transition meshes are currently separate meshes to fit between the regular ones, so the number of draw calls may increase a little. I haven't got to point of testing large-scale terrains with this algorithm yet, so results from this will be checked later.
This is because Transvoxel requires the vertex shader to dynamically displace some of the vertices to make room for transition meshes at runtime, for any combination of the 6 sides being bordered by blocks of lower LOD or not.
This comes along the usage of extra vertex attributes to fit the information. I'm currently re-using COLOR
for that, where a
is a mask and rgb
are a secondary position.
It has the inconvenient of reducing room for material information... I'll probably have to use UV2
for that, unless future Godot versions expose more attributes.
This also means the node will no longer allow to assign a vanilla material, it will have to be a ShaderMaterial
. In theory it could be re-meshed as a single mesh everytime, but it would slow down LOD updates.
Another way would be to switch around index buffers somehow, but that's not an option either.
An option would also be to keep mesh data CPU-side, modify it on demand and reupload the mesh when it needs to change.
So far I followed the paper, also taking help from an existing implementation found here: https://github.com/BinaryConstruct/Transvoxel-XNA/blob/master/Transvoxel/SurfaceExtractor/ported/TransvoxelExtractor.cs, but I started to consider tweaking it since I'm now getting a better grasp on it.
Most notably, this:
Instead of placing transition meshes inside low-resolution blocks connecting to high-resolution voxels, I decided to do the opposite: placing them in high-resolution meshes, connecting to low-resolution. At the moment, I think it would be better because it allows to use the same voxel buffer, skipping half voxels for the low-resolution side. If I was doing like the paper, I would have needed high-res voxels from the neighboring blocks while only having half-res voxels from the current block. Thoughts?
An interesting solution to fix LOD aliasing is proposed in the paper, however I won't implement it for now because it assumes that we have access to all LODs, while this module only loads the data partially around the player. See https://github.com/Zylann/godot_voxel/issues/60
Even though Transvoxel comes with vertex sharing built-in, I discovered that the vertices lying on the negative sides of a block would never be connected together. I could not find a fix for this yet, not sure if I did something wrong.
This can be observed by randomly shaking vertices based on their index in a vertex shader:
Edit: confirmed by Phyronnaz, even though his implementation was independent.
To be continued.
Note: at time of writing, the transvoxel
branch on Github does not include all my local work yet.
Small update: Mostly been fixing bugs since last post, and came up with a better test scene to test LOD stitching.
https://www.youtube.com/watch?v=scNtmx2HiS0&feature=youtu.be
I still have to implement a small correction to transition vertices, they need to be adjusted according to the surface normal as described in the paper. Once I have a decent implementation, I will look into transforming it so it can support all 6 sides of the block, as it's currently implemented only for the -Z side.
The idea to fit transition meshes is to "push" normal vertices from the side of the block to insert them. So far I've done it by detecting which vertices lie on the side, and offset those towards the inside of the block. However, it may be a mistake. If a vertex is not exactly on the side, but close enough to remain in the transition area, it will not be moved, producing a sharp artifact, like seen here:
I may have a correction to do in the implementation, since I recall the paper mentions scaling the whole cell, not just moving border vertices. However it is unclear as to how I should do it near edges and corners.
What I had so far only considered side vertices. They would get their own bordering masks, which was great because I could do what the paper says with an equality test and obtain the special edge behavior seen in the middle. Meanwhile, other vertices would get a mask of 0 because they were not on a side and then could not determine a bordering mask:
With the following formula in vertex shader:
VERTEX = mix(primary_position, secondary_position, float(u_lowres_border_mask == border_mask));
Unfortunately inner vertices cause problems. We have to transform them.
What I want to achieve:
This seems more complex than just "choosing between primary and secondary" based on "a 3-component variable" like the paper says. In Phyronnaz's work, there is actually an exception coded for vertices lying exactly on edges, but then it still means other vertices remain translated as if that wasn't the case. It may work though, so that means we need two 3-component variables to bring in the vertex, which are subtly different:
Which becomes the following GLSL:
int border_mask = int(vertex_col.a);
int cell_border_mask = border_mask & 63; // Which sides the cell is touching
int vertex_border_mask = (border_mask >> 6) & 63; // Which sides the vertex is touching
// If the vertex is near a side where there is a low-resolution neighbor,
// move it to secondary position
int m = u_lowres_border_mask & (cell_border_mask & 63);
float t = float(m != 0);
// If the vertex lies on one or more sides, and at least one side has no low-resolution neighbor,
// don't move the vertex.
t *= float((vertex_border_mask & ~u_lowres_border_mask) == 0);
vec3 secondary_position = vertex_col.rgb;
return mix(vertex_pos, secondary_position, t);
Transvoxel is now implemented in the master branch.
If you try smooth terrain, it should be a bit faster. However, now there are a bit more meshes to render, which has a performance hit in Godot 3's culling system. Also, the engine has to compute transition masks to determine which seams to activate, each time a block visibility changes. This incurs a performance hit in neighbor-checking happening on the main thread that I'd like to optimize later on.
As described in previous posts, this implementation relies on a vertex shader to reposition vertices around seams to make transitions smoother, repurposing the COLOR
attribute. However, such shaders are not actually required for the terrain to render. If you don't use one, you'll get the same result as the old mesher, where seams would be perpendicular across blocks of different LOD.
If you want the vertex shader trick, your shader should include the following:
// Bitmask telling which of the 6 faces of the block are bordered by a block of lower resolution
uniform int u_transition_mask;
vec3 get_transvoxel_position(vec3 vertex_pos, vec4 vertex_col) {
int border_mask = int(vertex_col.a);
int cell_border_mask = border_mask & 63; // Which sides the cell is touching
int vertex_border_mask = (border_mask >> 6) & 63; // Which sides the vertex is touching
// If the vertex is near a side where there is a low-resolution neighbor,
// move it to secondary position
int m = u_transition_mask & (cell_border_mask & 63);
float t = float(m != 0);
// If the vertex lies on one or more sides, and at least one side has no low-resolution neighbor,
// don't move the vertex.
t *= float((vertex_border_mask & ~u_transition_mask) == 0);
// Position to use when border mask matches
vec3 secondary_position = vertex_col.rgb;
return mix(vertex_pos, secondary_position, t);
}
void vertex() {
VERTEX = get_transvoxel_position(VERTEX, COLOR);
}
I did not consider modifying meshes on the CPU because uploading meshes with Godot 3 is really slow.
A "new" mesher is available, called VoxelMesherMC
, which is actually the old code of the Transvoxel mesher, back in the day it was barely marching cubes. Because it is only marching cubes, I renamed it MC and experimented an "over-polygonizing" seam mode with it. That wasn't great due to poor Z-fighting in Godot. Since VoxelMesherTransvoxel
is much better I will probably delete MC later.
This can be improved in the upcoming versions. Notably, Transvoxel mentions a binary-search technique which could help fixing distant landscape, which will be worked on in https://github.com/Zylann/godot_voxel/issues/60#
There are also texturing techniques which would allow to use more complex shading and custom-painted surfaces, by introducing material ID and weights to voxel data (no mentions of transparency tho).
I know you worked hard on this. Good job so far. I had a chance to test it out and here's what I found using VT 716b8205, and Godot 389b7939bf.
In summary, it's 40-50% slower, produces better meshes for odd areas, and fixes the holes. The NORMAL shader fix is still required for heightmap. The provided vertex shader didn't work at all for me.
I no longer see holes in the mesh as shown in #63 .
Odd areas are meshed better.
Using my demo. FPS is from sitting in the initial starting point and looking around. Other figures with ranges are from moving around. Build out times are approximate, but definitely different.
Scene: heightmap_smooth_lod
DMC Transvoxel
Build out: 1-1.5s 3s
FPS: 275-348 200-218
Memory static: 117-123 147
Memory dynamic: 51-55 45
Objects: 14,220 29,575
Objects drawn: 234-330 420
Vertices Drawn: 2,330,820-3,055,596 2,327,361
Scene: noise_smooth_lod
DMC Transvoxel
Build out: 2-2.5 4-5
FPS: 275-300 140-180
Memory static: 108-143 153-211
Memory dynamic: 50-75 40-61
Objects: 14,342-19,034 29,789-42,133
Objects drawn: 368-450 499-550
Vertices Drawn: 5,554,269-6,723,201 (@215) 3,904,659 (@130) - 4,120,764 (@145) - 4,610,043 (@95)
When I removed the fix from my shader:
Adding the provided vertex shader code to my shader produced this. I did nothing else but add it. Here the NORMAL fix has been turned off.
I also noticed at a view distance of 4096 and LOD count of 8, the farthest LODS don't connect. NORMAL fix, no vertex shader code.
Odd areas are meshed better.
Transvoxel has a slightly modified marching cubes table so it may be better than the one in the old mesher. Also I noticed my implementation takes a very slightly lower isolevel (off-by-one likely), which contracts the resulting surface a tiny bit.
In summary, it's 40-50% slower
Slower to render I assume, because the meshing process is definitely faster. I guess this is the result of Godot culling being terrible, because transition meshes increases mesh instance count, you can tell by the number of objects drawn.
If you use VoxelTerrain
(without LOD) I would not recommend using Transvoxel with transition meshes, they should be turned off because there is no need for them.
As for noise-based terrains, they are now slower to generate but that's entirely on the generator being unoptimized.
About the spiky artifacts:
this one nagged me for a while, and I thought I fixed it for the main parts of the meshes, but for transition meshes I haven't tested the shader extensively enough, some booboo remains to be fixed.
Edit: I know why. Secondary positions (located in COLOR.rgb) are not getting scaled by LOD.
About these:
I noticed a thin crack in the middle of a mesh once, but I have no idea what to do about it. AFAIK it's occurring within a normal part of the Transvoxel algorithm. Perhaps a precision issue? Some vertex should have been shared but didnt?
I also noticed at a view distance of 4096 and LOD count of 8, the farthest LODS don't connect
This is very odd. There are several possibilities, either it's the generator reaching an edge case, or a bug in the mesher but I'd find this less likely.
Also if you ever used saving with VoxelStreamBlockFiles
or VoxelStreamRegionFiles
, depending on the generator you used, the LODs above 0 in saves should be regenerated because they will be misaligned.
I noticed a thin crack in the middle of a mesh once
Regarding the square cracks with the vertex shader, those appeared all over the landscape. Some were much bigger. Some appeared/disappeared based upon camera angle, but not position.
Slower to render I assume, because the meshing process is definitely faster. I guess this is the result of Godot culling being terrible, because transition meshes increases mesh instance count, you can tell by the number of objects drawn.
Hmm, the number of objects is twice as many. But the number drawn is not much more. And the number of vertices is significantly less in some cases. With all of that, the FPS is halved.
I would have expected the number of vertices to be the performance factor, or at least the number of drawn objects. Not the number of objects overall. If the meshing is nearly 500% faster then the number of total objects must be a ridiculous bottleneck in the renderer, and the number of vertices hardly a factor.
Some appeared/disappeared based upon camera angle, but not position.
Woah?
Hmm, the number of objects is twice as many. But the number drawn is not much more. And the number of vertices is significantly less in some cases. With all of that, the FPS is halved.
That's because Godot has to cull twice as many :p and culling is really not the biggest strength of Godot right now
If the meshing is nearly 500% faster then the number of total objects must be a ridiculous bottleneck in the renderer
It is. Been mentionned in https://github.com/godotengine/godot/issues/23998 Also: https://github.com/Zylann/godot_voxel/blob/716b820599690fdae96c751823ca89e08cfc0bbb/terrain/voxel_block.cpp#L75-L78
I fixed transition meshes in 8056f7e6798a85a4f33ebae577266416ec41cbdb, now they scale with LOD properly.
I tested a proper shader with VoxelLodTerrain
, the difference is subtle. I really need to improve VoxelStreamImage
some day.
@tinmanjuggernaut the thin cracks you found aren't actually the ones I was referring to. They have a very particular shape and are found on borders, which reminds of what a mesh looks like when its transition mask has border bits set but transition mesh is hidden. It looks like the transition mask is not being reset properly in some cases.
Fixed thin cracks in 462e453cf45c11373cfd1f60d7218df4dccd8f78
As of 3ead96f, I can now include your shader code into my shader without artifacts, but I don't see any difference in game. Taking a shot in photoshop, I do see a difference, but without the shader looks better to me. In some places they're the same, but in others, without the shader blends in more.
It depends on the situations maybe. I noticed the shading of transition meshes is sometimes a bit weird, becoming dark for no reason.
Like here, with shadows off, wtf (they are supposed to be the same normals on the two ends of the transition mesh)
But there is still a main remaining reason for them to not be 100% seamless: deep-sampling using binary search is not implemented yet, so isosurface between blocks can still vary a lot (https://github.com/Zylann/godot_voxel/issues/60).
About FPS performance: I just pushed a branch called visibility_as_being_in_world
. In this branch, instead of using the visible
property to show and hide block LODs, I directly remove them from the world, or add them back. In debug mode I went from 150 fps to 180. I may merge it to master if it turns out all right.
All my scenes and materials look good except one. This shader shows seams:
It uses vertex displacement, which pushes the vertices along their normals a minor amount to give texture to the ground. If vertex displacement is removed, the ground is sealed up again.
If I try to use the seam shader fix above, it produces all sorts of craziness because my shader also uses world_vertex_coords
. The craziness changes depending on camera angle, so it's a matrix transform issue. But I played around with all the transform matrices trying to convert VERTEX, and COLOR going into the function, or on the return value, but wasn't able to get it to convert properly.
Problem with your shader, can't really say much since the reference implementation works. Maybe it's caused by the inputs your displacement is based on, they have to match between blocks. Also remember last bit of https://github.com/Zylann/godot_voxel/issues/2#issuecomment-568832306
Ah, also there is a limitation caused by the fact every block needs its own ShaderMaterial
to convey the transition masks: modifying uniforms of your material at runtime won't work (or has to be copied in all the blocks every time it changes).
my shader also uses world_vertex_coords
If you do that I think you will need to adjust the transvoxel conversion function, because I coded it to work in local coordinates.
About FPS performance: I just pushed a branch called
visibility_as_being_in_world
.
Much faster. It's a little jerky or halting when building out, and occasionally when moving fast over the terrain as paged areas are building.
Updated performance stats:
Scene: heightmap_smooth_lod
DMC Transvoxel T2
Build out: 1-1.5s 3s 3s
FPS: 275-348 200-218 250-270
Memory static: 117-123 147 136
Memory dynamic: 51-55 45 45
Objects: 14,220 29,575 29,575
Objects drawn: 234-330 420 444
Vertices Drawn: 2,330,820 2,327,361 2,497,701
Scene: noise_smooth_lod
DMC Transvoxel T2
Build out: 2-2.5 4-5 5s
FPS: 275-300 140-180 190-220
Memory static: 108-143 153-211 141-207
Memory dynamic: 50-75 40-61 41-85
Objects: 14,342-19,034 29,789-42,133 29,789-41,728
Objects drawn: 368-450 499-550 465-772
Vertices Drawn 1: 5,554,269 3,904,659 @130 3,503,532 @228
Vertices Drawn 2: 6,723,201 @215 4,120,764 @145 4,216,845 @175
Vertices Drawn 3: 4,610,043 @95 8,786,157 @125
Do you think I should merge that approach? Eventually it may be tested again once the 4.0 renderer arrives.
Yes, transvoxel is such a big performance hit (even up to 70% on my space scene) and this approach gets some of that back. I tested it extensively today and had no issues. At worst it's no slower.
I'd expect that you'd revisit a lot of things once 4 becomes available, such as vsync being required.
My space scene is pretty heavy duty with a noise height of 1500 and shaders for sky and ground. With DMC I could get 120-150fps in complex areas. With transvoxel I might get around 1/3rd of that. The new approach had a big impact on other scenes, but doesn't do much for this one.
I ran it under the msvc profiler and found:
Still a year to go for the SimplexNoise patent. I wonder about the OpenSimplexNoise optimizations and that guy's new noise algorithm, SuperSimplexNoise. Maybe all of these variations could be put into Godot.
Next, I switched my project to multithreaded and all of a sudden my game went up to a respectable 65-80fps in heavy areas. Navigation throughout the scene was noticeably smoother. However, voxel updates were then ridiculously slow as per #48. Basically you sit there in the same spot for a good 5-10 seconds before updates happen.
I was considering giving a try at FastNoise
tbh. Or even its SIMD version.
Apparently SuperSimplexNoise and FastSimplexStyleNoise are both faster than FastNoise Simplex according to benchmarks in the readme I linked, and unencumbered. But FastNoiseSIMD seems fastest (and more complex).
I was able to create a new VoxelStream with FastNoise. It's still slow, but I'll experiment and see if I can get an optimal stream.
Here's 3D Voronoi under TransVoxel:
Since Transvoxel is mostly implemented now, I'll close this issue. Some specific areas remain to be done, such as texturing and binary-search sampling, but those have their own issues.
Might I suggest implementing a smooth voxel system? Transvoxel would be a good one to implement, as it supports Level of Detail with seamless transitions.
http://transvoxel.org/