Hopson, So 2 years ago you made a Minecraft game in 7 days, I’m looking forward to make a game like roblox so could you please make a game like roblox in 7 days?
@@eureptus dude making a game, even in just 7 days takes a looooong time. Besides, you can't really make a basic version of roblox due to it's multiplayer aspects and creation tools
As a fellow voxel game developer, I too find the greedy meshing article to be somewhat technical. But eventually I figured it out (or so I think): First, loop through the blocks along the X axis (at Y=0), and combine each of them into a single group until you meet another type of block, increasing extend.x while doing so. (If you meet another, just create a new group.) Then, repeat the same process at Y=1 and so on. Same goes for the Z axis. So your groups have the following fields: starting position (vec3), extend (vec3i), and the block type (uint in my case). But we haven't finished yet! Now, for each group, let's say Group 1 is at (0, 0, 0). And say Group 2 is at (0, 1, 0) - one unit above Group 1. If their extend (the amount of blocks along each axis) are the same, then combine the groups together - for instance if their extends are (10, 1, 1) then after the combination the extend of the new group becomes (10, 2, 1). Essentially, a group will ALWAYS be a cuboid with 12 triangles only. That is the basic idea of greedy meshing. You can try optimising for faster grouping of blocks (I developed mine in a day so I'm pretty sure there are a lot of space for optimisations). Besides that, I believe a basic cull before the grouping can be quite beneficial too.
Ayyy the how I optimize my voxel game too! I didn't knew this was how the greedy mesh method worked. Extending on the X axis is easy but on the Z and Y is hard and costly.
The method in the linked article is quite a bit different. Instead of working with cuboids, it deals with 2D slices. First, it looks at 2 adjacent 2D slices of the voxel grid. From them it generates a mask, which tells you where you need quads. Then it picks a first quad, and tries to extend it. When this quad is maxed out, it clears the mask in that region(since we've already filled those quads), and moves onto a next quad. This process is then repeated for all slices in the current direction. When that is done, it moves onto the next direction, so you go throughthe volume 3 times total.
@@imnotstpid Indeed it does, but it only happens if you insist to use a normal dumb graphics pipeline - with shaders (hint: floor()) you can achieve the same effect easily.
its very neat, however you have to be very careful about premature optimizations if you start doing stuff like too early it can really hurt you in the long run.
@@krubbles101 yes hopson did it at the right time, the game was having a problem and he fixed it. The problem is when you do stuff like bitpacking to optimise memory before you've even fully worked the texture/lighting/... mechanics out.
@@albingrahn5576 excellent video! Crazy to think that chrome takes >500mb of ram easily. Programmers have stopped caring since "powerful" machines are so cheap these days which i find quite sad.
Hey it might not mean a lot to you but I'm really glad you've started uploading again after your bit of a hiatus. I'm not a great programmer because I've only ever worked with very high level languages and libraries, so learning about how to do all of the nitty gritty is super fascinating. And seeing the final project come together, or course :)
Happy to see you make another video on this game! (3:35) Why do you need to store the max local position of each block in a 32x32x32 subchunk as '32', while 0-31 is already a range of 32 blocks? Then you could also go from using 6 bits to 5 bits, as 2^5 = 32. :)
A chunk is 32 blocks wide, but it is 33 vertices wide. Picture a fence of posts | and segments --. There will always be one more post than there are segments, like so: |--|--|--|--| (4 segments, 5 posts). Now replace segments with blocks, and posts with vertices. So therefore 32 blocks needs 33 vertices :)
I don't know if this would make sense, but could you not store the new lighting value (2..5) in two bits instead of three by subtracting 2 and thus only needing to store 0, 1, 2 or 3 which is a two digit binary number? :)
I wonder where the line is between some neat optimisations, and code that is just full of magic numbers and offets, that noone understands 3 months after...
@@deamon6681 I feel like such an important part of a game engine might need to be as optimised as possible and therefore it's ok for the code to be harder to understand. Good variable naming and documentation is ofc important. I was more worried that my 'optimisation' might just not improve anything as there is enough room in the variable he packs all the bytes into. Then, my optimization would just add an unnecessary operation. And I also generally don't know, if saving one bit is worth one extra operation
that would be an additional operation for each vector and the extra bit in memory to save that might be the more efficient approach. The memory efficiency vs processing efficiency is always a complex argument.
This wouldn't make a difference to the resulting code since memory alignment means any struct is always packed to align to the nearest 4 byte size. So even if you go to 31 bits per block it'll still pad to 32 bits.
I am thinking of something like this: Define a 3D array of "Blocks". Each block can have an byte for it's Type. The coordinates don't need to be saved as we already have them when we index into the array. So, for the storing the blocks themselves it will only take 1 byte, and when you want to expand, you can just change the data type from "byte" to "short". You will still be using less than 4 bytes. Now, here's an explanation for how you can use the index for the coordinates. the x, y, and z index will denote where the center of the block is, simple as that.
5:50 : Why make it complicated with division? Just have a 6-entries lookup table for desired lighting values (or normal vectors in the 6 directions, incase you'll ever need them) in the shader. Perhaps such a lookup table instead of division might even improve performance, albeit very slightly.
@@oblivion_2852 Lookups are way, way, way slower. On a GPU, multiplication, division, addition, multiply-add, subtraction, inverse square roots, exp2, sin, and cos are all one clock cycle. (this does not apply for integers, only floats). A lookup may be implmented with a texture read, which is pretty much the only thing that matters for shader performance. Never use lookup textures in a GPU to replace mathematical operations.
@@gNpNct Both multiplication and division are incredibly fast on a GPU. The division is sometimes 2 clock cycles (one reciprocal and one add) and sometimes 1 clock cycle (1 divide), but either way it is very fast.
Minecraft still uses a texture atlas, it just assembles it at runtime. If you look at the console as the game is starting up, it says some stuff about texture atlases, and it even saves it to disk. I found it while playing modded at one point, and found some very strange things from some mods
a great improvement would be to use a geometry shader, and just pass a 6bit integer telling wich faces to draw.. you would reduce the whole 36 vertices to a single vertex :)
I did a voxel world some month ago, and I ran into that VRAM problem. I'm surprised I didn't thought of declaring the textures inside the shader, this is so simple yet so effective.
0:21 Donkey Kong Country 2 - David Wise - Stickerbrush Symphony 1:36 Donkey Kong Country 2 - David Wise - Aquatic Ambience oh thank you for putting music in description
man, I watched your "build minecraft in 1 week challenge" a year ago and was inspired to build a minecraft clone myself and when I got to meshing I had to make my own algorithm. But 6 months later I see this video in recommended and clicked on it because it reminded me of programming my game and watching that old video and WOAH turns out you're the same guy who made it.
Convex refers to the angle formed at the vertices. A convex shape can inhabit multiple planes so long as none of it's internal angles are greater than 180 degrees. Overall you are correct, a triangle can only exist in one plane but this is because a plane needs three points to be defined and obviously that's all a single triangle has. I believe "plane figure" would be a better choice of words there.
Just use bitmaps. 32*32*32 with visibility directions + type + light + color will usually take around 50-200 bytes. For filled chunks such as air it will just take couple of bits. You also get greedy meshing along x axis with this approach AND greedy blocks (you pass through visible blocks/bits, skipping all empty block iterations). You can also just render entire FoV 10*10*10 chunks by recombining bitmaps, optimize it, then calculate greedy mesh for entire FoV.
If I'm not mistaken, on OpenGL 3.1+ you can use glDrawArraysInstanced. You do not need to use 64 byte transformation matrices, and can use 12 byte 3D vectors because you only need to translate the block from model space to world space.
that opening threw me right back into the one and only time I worked in a studio. The lead was allergic to triangles, but I was modeling something for their Unreal Engine VR movie thing ... I didn't end up being hired. Fun job but people in this industry can be mindless frustrating.
I knew this would be first attempt at secret sauce on this. Thinking further about it that paper you highlighted is going to do this same thing algorithmically and shortcut something as this will be the middle or lower middle ground for what needs to be truely optimized. The thing is that if you are going to use bytes there are a set of secrets of just using things representationally and mapping in the code these bytes to another set of values much like base 10 or base 8 - the bits can be representational of an infinite number of values when mapped in different contexts. Going to go smoke some weed and think more on this.
You could store your whole structure into a single unsigned long and a float by using bit shifting Or just simply for the (x,y,z) those could be inside one int (1,32,16,08) (you need a 1 at the start if x < 10)
There’s actually another thing you missed. If your chunk size is 32, your relative block offset can only be 0..31, not 0..32. That means you’re okay with just 5 bits per side instead of 6.
Yes, but it's talking about vertices - the edges of the blocks - and not the blocks themselves, therefore the lowest one is at 0, and the highest one is at 32
Another thing I do is store them in quads and then use indices in the shader to convert quads to triangles, making there be only 4 vertices per block face instead of 6. I also store the 'per vertex' data separately from the 'per block face' data.
Thank you for making this kind of video, it puts my mind to rest a bit, while it would be fun to implement a voxel game, there already are plenty. The exercise to implement the renderer would be fun, probably one day I will give in and do it, but until now, it is nice to reiterate the steps while watching you, good video and thank you!
I guess people have already told you this, but... 1) If you only have 4 values for lighting, why 3 bits? Use 2. 2 bits give you 4 combinations, exactly what you need. Just shift your values by 2, and you have 0...3 instead of 2...5, which saves one more bit. 2) Why floats? Your vowels are placed in a grid, so you can use integers instead of floats for XYZ. Same goes for texture coordinates. If you are not going to have a situation when the texture is part of one and part of another, why use floats? Go for integers and save more space. 3) If you are looking for extreme optimizations, look into a geometry shader. It allows you to "unfold" vertexes into more vertexes. So, instead of providing 4 vertexes for each face, you only give it one that represents the whole face, and the geometry shader then "unfolds" the one input vertex into 4 output vertexes with math. And you can go even further. Why send each face to rendering if you can send whole blocks? You provide one vertex that represent the whole block to a geometry shader, and it "unfolds" it into 8 vertexes that are passed to other shaders and rendered. Using those, you can optimize your rendering even more.
That’s a pretty cool video and a tutorial, however that would work only for games that use purely voxels, I.e. it wouldn’t be possible to pack such data in case you would want to introduce different models per block. I still found it very informative, thanks!
@@Hopsonn no, you didnt understand what i meant, i know the music in this video, its just that all of the tracks have been posted in videos where people do a think in the comment section called a "checkpoint" example1: at 0:23 starts the track in this vid ruclips.net/video/hHKu9W_m0nc/видео.html example2: at 6:05 ruclips.net/video/Q9XTqQbuavI/видео.html it was just a comment in case someone else recognised the songs because of the checkpoint vids, but i guess its not as known as i thought :v
Oh and you could also just store 2 bits (instead of 3) for the lighting, since you only have 4 values. That would give you values from 0-3. Adding 2 to that gives you values from 2-5 which you can then divide by
It's important to note that these optimizations are only possible because you're leaving definition behind, not that it's bad, but because those are the compromises you're willing to make
I have considered this approach in my little MC-like game, but using integers for the coordinates meant that block models with fractional coordinates are not supported: things like half-slabs, glass panes, the brewing stand. To support those, a fixed-point number could be used, but I wasn't sure how to design such a structure. I didn't want to pick the number of bits for the fractional part, e.g. 4 bits for a resolution of 0.0625 blocks, only to later on find out that I want to implement a block that needs a greater resolution for its model. Now that I think about it, it's not such a big deal. Changing the number of bits for the fractional part could be as easy as just changing a constant in the CPU program and vertex shader with no changes to code, but at the time I was kinda scared to make a decision.
There's several big improvements to do. The first one would be to only use 4 vertex per face, using vertex index. The second would be (and here I'm being more hypothetical), to only use 1 vertex per block, since all the relevant data of a single voxel can be contained in a single vertex, and the the whole block can be constructed in the geometry shader or somethig
Using an index buffer as you suggest would actually increase the memory usage. My method 6 vertices *4 bytes each =24 bytes per face Index buffer 4 vertices * 4 bytes each + 6 indices * 4 bytes each = 40 bytes As for the geometry shader, I could but I never learned how use those lol
Instead of lighting value, I would use a normal index which maps to one of six possible normal vectors in de shaders that you can then use for any light sources. Since you only need to worry about 6 possible normals, 3 bits will still suffice.
3:40 I don't know if you made a mistake, but 32 binary values can fit within 5 bits, from 0 (00000) to 31 (11111). So we only need 15 bits to store position information.
There are 33 possible vertex positions from 0 to 32 Imagine chunks are 2x2, then the top verticies would be like this ._._. Where the dots represents vertex, the positions go from 0 to 2, giving 3 possible vertex positions in a given axis
0:15 Wanted to point out a mistake here. All triangles are convex. in simple terms this means that if you wrap a string or rubber band around it you'll never have points that poke inward away from the band. Triangles are also coplanar, for which the definition in the video is given as the definition of 'convex'.
Any updates on this project? Love seeing this code optimization type videos. A suggestion on the lighting though, make it 1 byte so you have all possible light intensities (0-255). Its going to make the light decay from torches or other light sources look much better
definitely late to the party, but I just wanted to point out that you could have saved an additional bit on lighting. Instead of storing 2 through 5, you could subtract 2 from each and only store 0 through 3, which can be stored in just 2 bits instead of 3. Afterwards on the unpacking method you can just add the 2 you took previously to return it in the range of 2 to 5, and divide by 5 normally. Probably too late to even mention but I just wanted to contribute somewhat.
ahh, good memories, wrote my bachelor thesis about a better greedy meshing implementation, abusing the fact that faces can overlap other same texture faces and span over occluded space. tho, with a new method, I have also proven that you can trade memory and face count, yielding at max 96 face checkerboard chunk of 32x32x32 blocks. in this usecase gpu mem might be cheaper than flops.
Also you could shave another bit off the lighting easily but seeing as it fits nicely into a 32 bit int I don't see a reason to. (You can store it as 0 to 3 and do number*0.2 + 0.2 to convert back.)
Just use a volume texture and have a bit for each voxel on the rendering side, and then maybe a byte for material. Just calculate everything else on the fly.
Greedy meshing is a sloppy approximate to the least quads or optimal coverage problem, it's very easy to implement, will more than 20x your memory efficiency and doesn't require crazy math (0fps makes everything seem complicated) just iterate slices of your chunks, as usual we will be collecting up all the instances of solid voxels which have a faces exposed to air, For greedy meshing we just place these 1x1 boxes into a 2d array and expand / combine them, the silly epsilon symbols and so forth on the 0fps page just say that he does that by growing / merging to the right and then down, it's a simple algorithm with no math involved. To get OPTIMAL meshing (side note: again you don't need any of this advanced technology to solve your basic problem of needing LOD, and besides view distance is fundamentally N*3 and so will never scale well with any (even enormous) linear performance optimizations, but since you made this great video I'll explain; Finding the least rects to cover a 2d grid is exactly the same type of task as path finding thru a 2d grid, in both cases there is some definite optimal goal (the shortest path or smallest mesh), in both cases it is possible to layout a series of steps or changes (for navigation it's movement , for meshing it's placing a piece of geometry) this task can be done OPTIMALLY if you have a heuristic or scoring system which is able to reliably return an upper-bound no better than it really is, It can be done EFFICIENTLY if your heuristic produces a tight lower-bound. Thankfully these are both trivial for the axis aligned uniformly sized uniformly distributed 2d case, you can just count the remaining corners (since you know they will eventually need a box) which is to say the optimal path thru this mesh space (note: use a branch and bound don't try to actually code this next part) is to draw a box which covers every (say top left) corner and then expand out as much as possible, there's much that can be done with texture packing and slice render fusion but again, LOD will save u. Lov ur vid, peace out
Indexed rendering works fine with voxels, with ogl just tryAdd() each vert of your chunk to a hashmap and if it succeeds then store that vert in a new list, also make an int list with each of the original verts location in this new list, then just bind your buffers and switch your glDrawArrays() to a glDrawElementsBaseVertex(), but keep both code paths, drawArray is usually a better trade off in terms of mesh build time vs need to minimize maximum memory pool usage, speaking of which, you don't need to squeeze your vert data or embrace triangle lists (although you should if you also really need great performance) you are clearly trying to load too much of the world at full detail, accept level of detail into your life S:^P Peace
What about vertex indexing? Usually you have a list of vertices, and a list of 16-bit unsigned integers to specify the sequence of how the vertices should be rendered. This means that vertices never have to be duplicated, helping a lot.
While it might be possible to do this in a voxel game that uses polygon rendering, it's incredibly awkward due to the nature of how the mesh is generated. Usually you would add individual block faces to a mesh (a quad), and keep adding more quads. Issue is its hard to predict whether the next quad will be able to share vertices or not, without looking ahead of time. And by this point, algorithms such as greedy meshing give much better results, where rather than sharing verticies, you instead share entire faces, drastically reducing the triangle count, giving a huge boost in performance. And sharing the vertices in the block faces themselves would actually use more memory than doing it this way. (I would type out the numbers to prove this, but I am on mobile atm :p) Thanks for watching!
Join my discord here if you want to :=) discordapp.com/invite/DeEhUXY
Hopson, So 2 years ago you made a Minecraft game in 7 days, I’m looking forward to make a game like roblox so could you please make a game like roblox in 7 days?
@@eureptus lol no
@@eureptus dude making a game, even in just 7 days takes a looooong time. Besides, you can't really make a basic version of roblox due to it's multiplayer aspects and creation tools
aaaand the link is dead
@@untodesu ill be making new links soon
Minecraft still uses a texture atlas, it's just stitched together dynamically at runtime now. Great video!
oh so it puts all the individual texture files into on big atlas? I'm guessing the're doing something different for the animated textures
@LapisSea holy crap they never stopped using the fixed function pipeline?
wait but i thought with 1.15 they redid their rendering stuff completely new and optimized everything (i think they called id blaze3d or something)?
@LapisSea im probably gonna look into fabric 1.15 soon when i find the time, would be really cool if mc had at least decent rendering
LapisSea Tell us your thoughts :) Pretty cool
As a fellow voxel game developer, I too find the greedy meshing article to be somewhat technical.
But eventually I figured it out (or so I think):
First, loop through the blocks along the X axis (at Y=0), and combine each of them into a single group until you meet another type of block, increasing extend.x while doing so. (If you meet another, just create a new group.) Then, repeat the same process at Y=1 and so on. Same goes for the Z axis.
So your groups have the following fields: starting position (vec3), extend (vec3i), and the block type (uint in my case).
But we haven't finished yet! Now, for each group, let's say Group 1 is at (0, 0, 0). And say Group 2 is at (0, 1, 0) - one unit above Group 1. If their extend (the amount of blocks along each axis) are the same, then combine the groups together - for instance if their extends are (10, 1, 1) then after the combination the extend of the new group becomes (10, 2, 1).
Essentially, a group will ALWAYS be a cuboid with 12 triangles only.
That is the basic idea of greedy meshing. You can try optimising for faster grouping of blocks (I developed mine in a day so I'm pretty sure there are a lot of space for optimisations). Besides that, I believe a basic cull before the grouping can be quite beneficial too.
Ayyy the how I optimize my voxel game too! I didn't knew this was how the greedy mesh method worked. Extending on the X axis is easy but on the Z and Y is hard and costly.
The method in the linked article is quite a bit different.
Instead of working with cuboids, it deals with 2D slices.
First, it looks at 2 adjacent 2D slices of the voxel grid. From them it generates a mask, which tells you where you need quads. Then it picks a first quad, and tries to extend it. When this quad is maxed out, it clears the mask in that region(since we've already filled those quads), and moves onto a next quad.
This process is then repeated for all slices in the current direction. When that is done, it moves onto the next direction, so you go throughthe volume 3 times total.
Wouldn't greedy meshing completely ruin the resolution of your lighting though since it removes a whole load of verts?
@@imnotstpid Indeed it does, but it only happens if you insist to use a normal dumb graphics pipeline - with shaders (hint: floor()) you can achieve the same effect easily.
Thank you
I love nity grity optimizations like this, especially when you have to get creative with your bit packing. Great video!
its very neat, however you have to be very careful about premature optimizations
if you start doing stuff like too early it can really hurt you in the long run.
@@k1ngjulien_ Mesh memory is the limiting factor in the view distance of a voxel game. This optimization is not premature.
@@krubbles101 yes hopson did it at the right time, the game was having a problem and he fixed it.
The problem is when you do stuff like bitpacking to optimise memory before you've even fully worked the texture/lighting/... mechanics out.
i love it too! this video comes to mind whenever i think of optimization like that: ruclips.net/video/ZWQ0591PAxM/видео.html
@@albingrahn5576 excellent video! Crazy to think that chrome takes >500mb of ram easily.
Programmers have stopped caring since "powerful" machines are so cheap these days which i find quite sad.
Hey it might not mean a lot to you but I'm really glad you've started uploading again after your bit of a hiatus. I'm not a great programmer because I've only ever worked with very high level languages and libraries, so learning about how to do all of the nitty gritty is super fascinating. And seeing the final project come together, or course :)
Happy to see you make another video on this game!
(3:35) Why do you need to store the max local position of each block in a 32x32x32 subchunk as '32', while 0-31 is already a range of 32 blocks? Then you could also go from using 6 bits to 5 bits, as 2^5 = 32. :)
A chunk is 32 blocks wide, but it is 33 vertices wide.
Picture a fence of posts | and segments --.
There will always be one more post than there are segments, like so: |--|--|--|--| (4 segments, 5 posts).
Now replace segments with blocks, and posts with vertices.
So therefore 32 blocks needs 33 vertices :)
E V E R Y T H I N G I S T R I A N G L E S
Block game is actually diagonal pyramid game
SQUARES MAKE A CIRCLE
E V E R Y T H I N G I S S Q U A R E S
all these squares make a circle
--⬛
⬛⬛
:)
I don't know if this would make sense, but could you not store the new lighting value (2..5) in two bits instead of three by subtracting 2 and thus only needing to store 0, 1, 2 or 3 which is a two digit binary number? :)
I wonder where the line is between some neat optimisations, and code that is just full of magic numbers and offets, that noone understands 3 months after...
@@deamon6681 I feel like such an important part of a game engine might need to be as optimised as possible and therefore it's ok for the code to be harder to understand. Good variable naming and documentation is ofc important. I was more worried that my 'optimisation' might just not improve anything as there is enough room in the variable he packs all the bytes into. Then, my optimization would just add an unnecessary operation. And I also generally don't know, if saving one bit is worth one extra operation
@@gumbawu4135 I guess profiling is the only way to find out!
that would be an additional operation for each vector and the extra bit in memory to save that might be the more efficient approach.
The memory efficiency vs processing efficiency is always a complex argument.
This wouldn't make a difference to the resulting code since memory alignment means any struct is always packed to align to the nearest 4 byte size. So even if you go to 31 bits per block it'll still pad to 32 bits.
What's the universe made of?
Triangles and stuff
It sad knowing that he gave up on his channel.
@@tikete really?
Cake
5:50 Just a small arithmetic error.
2 / 5 != 0.2
And 6:20 - 28 bytes = 12 bytes + 12 bytes + 4 bytes = 96 bit + 96 bit + 32 bit = 112 bits
I am thinking of something like this:
Define a 3D array of "Blocks".
Each block can have an byte for it's Type. The coordinates don't need to be saved as we already have them when we index into the array. So, for the storing the blocks themselves it will only take 1 byte, and when you want to expand, you can just change the data type from "byte" to "short". You will still be using less than 4 bytes.
Now, here's an explanation for how you can use the index for the coordinates. the x, y, and z index will denote where the center of the block is, simple as that.
When you showed terrain.png at 0:46 it gave me so much nostalgia
Not just any terrain.png, but the one from the Painterly Pack. :)
That model in the intro made every single bit of my 3D artist soul hurt.
Mouse engine
Great video! As a beginning game developer myself, this is incredibly inspiring stuff! Thanks for making videos!
How's that going now?
@@manifestbruhlol It's going. Kinda taken a back seat recently due to a bunch of life stuff, but it's going :)
5:50 : Why make it complicated with division? Just have a 6-entries lookup table for desired lighting values (or normal vectors in the 6 directions, incase you'll ever need them) in the shader. Perhaps such a lookup table instead of division might even improve performance, albeit very slightly.
A compiler that's intelligent enough will optimize it into a single division (1/5) and multiply by that reciprocal anyway.
@@gNpNct Yes but it's still a multiplication operation instead of a lookup. Lookups are faster pretty sure.
@@oblivion_2852 Multiplication operations are pretty fast. When it comes to arithmetical operations, the slow one is usually just division.
@@oblivion_2852 Lookups are way, way, way slower. On a GPU, multiplication, division, addition, multiply-add, subtraction, inverse square roots, exp2, sin, and cos are all one clock cycle. (this does not apply for integers, only floats). A lookup may be implmented with a texture read, which is pretty much the only thing that matters for shader performance. Never use lookup textures in a GPU to replace mathematical operations.
@@gNpNct Both multiplication and division are incredibly fast on a GPU. The division is sometimes 2 clock cycles (one reciprocal and one add) and sometimes 1 clock cycle (1 divide), but either way it is very fast.
Minecraft still uses a texture atlas, it just assembles it at runtime. If you look at the console as the game is starting up, it says some stuff about texture atlases, and it even saves it to disk. I found it while playing modded at one point, and found some very strange things from some mods
Oh dude! Why did I not think of this!? I am going to apply this to my project
(I also stumbled accross that unreadable article about Greedy Meshing)
a great improvement would be to use a geometry shader, and just pass a 6bit integer telling wich faces to draw..
you would reduce the whole 36 vertices to a single vertex :)
The performance of that is terrible. Lots of branching, which is bad on the GPU.
4:00 Minecraft still uses a texture atlas, however it's generated at runtime.
I did a voxel world some month ago, and I ran into that VRAM problem. I'm surprised I didn't thought of declaring the textures inside the shader, this is so simple yet so effective.
0:21 Donkey Kong Country 2 - David Wise - Stickerbrush Symphony
1:36 Donkey Kong Country 2 - David Wise - Aquatic Ambience
oh thank you for putting music in description
Come for the programming, stay for the sweet sweet chrono trigger music. :3
0:50 Good old Painterly Pack.
man, I watched your "build minecraft in 1 week challenge" a year ago and was inspired to build a minecraft clone myself and when I got to meshing I had to make my own algorithm. But 6 months later I see this video in recommended and clicked on it because it reminded me of programming my game and watching that old video and WOAH turns out you're the same guy who made it.
The SONG in the background
'Home sweet home' :Beyond Good and evil , it's an old PlayStation 2 game. Love it 😍
Nice video ... And even more beautiful you are using The Chrono trigger theme here 5:07
On the git it says you decided that this project is not for you, does this mean this series will be discontinued?
ShibeGuy oh rip
yes
Convex refers to the angle formed at the vertices. A convex shape can inhabit multiple planes so long as none of it's internal angles are greater than 180 degrees. Overall you are correct, a triangle can only exist in one plane but this is because a plane needs three points to be defined and obviously that's all a single triangle has. I believe "plane figure" would be a better choice of words there.
Just use bitmaps. 32*32*32 with visibility directions + type + light + color will usually take around 50-200 bytes. For filled chunks such as air it will just take couple of bits. You also get greedy meshing along x axis with this approach AND greedy blocks (you pass through visible blocks/bits, skipping all empty block iterations). You can also just render entire FoV 10*10*10 chunks by recombining bitmaps, optimize it, then calculate greedy mesh for entire FoV.
I just knew I heard Brambles from Donkey Kong Country 2 in the background.
If I'm not mistaken, on OpenGL 3.1+ you can use glDrawArraysInstanced. You do not need to use 64 byte transformation matrices, and can use 12 byte 3D vectors because you only need to translate the block from model space to world space.
That music choice from the end of the internet.. Good choice, and great video!
5:40 But... you have exactly 4 options. That fits neatly into 2 bits. Why would you use 3?
Because I was silly and didn't realise that until I was making the video haha
Been trying to figure out the greedy meshing algorithm too, but sadly I too do not understand anything lol
that opening threw me right back into the one and only time I worked in a studio.
The lead was allergic to triangles, but I was modeling something for their Unreal Engine VR movie thing ...
I didn't end up being hired. Fun job but people in this industry can be mindless frustrating.
Allergic to triangles? Sounds like you dodged a bullet regardless
You deserve my like for your awesome work you are doing but this time my like goes for using Chrono trigger music :D
Thanks this video helped a lot mainly so I can understand my codes and even figure out more
I knew this would be first attempt at secret sauce on this. Thinking further about it that paper you highlighted is going to do this same thing algorithmically and shortcut something as this will be the middle or lower middle ground for what needs to be truely optimized. The thing is that if you are going to use bytes there are a set of secrets of just using things representationally and mapping in the code these bytes to another set of values much like base 10 or base 8 - the bits can be representational of an infinite number of values when mapped in different contexts. Going to go smoke some weed and think more on this.
Great video as always. You're a good source of inspiration!
You could store your whole structure into a single unsigned long and a float by using bit shifting
Or just simply for the (x,y,z) those could be inside one int (1,32,16,08) (you need a 1 at the start if x < 10)
Aaah the nostalgia hit when I heard Beyond Good and Evil music
Cave Story and Beyond Good and Evil music? Man you have some great taste. Great video as always :)
Ah the Aquatic Ambiance from Donky Kong Country. I see you are a man of culture as well (:
Great vid, just subbed!
i loved that you showed a screenshot of the valve hammer editor
There’s actually another thing you missed. If your chunk size is 32, your relative block offset can only be 0..31, not 0..32. That means you’re okay with just 5 bits per side instead of 6.
Yes, but it's talking about vertices - the edges of the blocks - and not the blocks themselves, therefore the lowest one is at 0, and the highest one is at 32
6:24 28 bytes is 224 bits. Informative video, though, will use it when I become good enough at coding
Another thing I do is store them in quads and then use indices in the shader to convert quads to triangles, making there be only 4 vertices per block face instead of 6. I also store the 'per vertex' data separately from the 'per block face' data.
Thank you for making this kind of video, it puts my mind to rest a bit, while it would be fun to implement a voxel game, there already are plenty. The exercise to implement the renderer would be fun, probably one day I will give in and do it, but until now, it is nice to reiterate the steps while watching you, good video and thank you!
The cave story soundtrack at the beginning❤️❤️❤️
i was too distracted by the music to pay attention
Nice profile pic
like for the chrono trigger music
I guess people have already told you this, but...
1) If you only have 4 values for lighting, why 3 bits? Use 2. 2 bits give you 4 combinations, exactly what you need. Just shift your values by 2, and you have 0...3 instead of 2...5, which saves one more bit.
2) Why floats? Your vowels are placed in a grid, so you can use integers instead of floats for XYZ. Same goes for texture coordinates. If you are not going to have a situation when the texture is part of one and part of another, why use floats? Go for integers and save more space.
3) If you are looking for extreme optimizations, look into a geometry shader. It allows you to "unfold" vertexes into more vertexes. So, instead of providing 4 vertexes for each face, you only give it one that represents the whole face, and the geometry shader then "unfolds" the one input vertex into 4 output vertexes with math. And you can go even further. Why send each face to rendering if you can send whole blocks? You provide one vertex that represent the whole block to a geometry shader, and it "unfolds" it into 8 vertexes that are passed to other shaders and rendered.
Using those, you can optimize your rendering even more.
That’s a pretty cool video and a tutorial, however that would work only for games that use purely voxels, I.e. it wouldn’t be possible to pack such data in case you would want to introduce different models per block.
I still found it very informative, thanks!
the music you chose in this video made me feel like i was gonna see some checkpoint comments :v
Gimmie the time stamp and I'll tell you the music
Is all in description anayway
@@Hopsonn no, you didnt understand what i meant, i know the music in this video, its just that all of the tracks have been posted in videos where people do a think in the comment section called a "checkpoint"
example1: at 0:23 starts the track in this vid
ruclips.net/video/hHKu9W_m0nc/видео.html
example2: at 6:05 ruclips.net/video/Q9XTqQbuavI/видео.html
it was just a comment in case someone else recognised the songs because of the checkpoint vids, but i guess its not as known as i thought :v
Oh and you could also just store 2 bits (instead of 3) for the lighting, since you only have 4 values. That would give you values from 0-3. Adding 2 to that gives you values from 2-5 which you can then divide by
awww YES Thorn Thorn Tale Meiro - Super Donkey Kong 2
wow just 4 bytes! that is actually super convenient and super impressive! awesome, and subd
You don't need to pass in 2 bits for the UV lookup, just use gl_VertexID % 6 with a 6 row lookup table
0:00 Illuminati
Voxel engine development, cute lizard avatar? This is microtargeted at me somehow. Subscribed.
It's really useful. Thank you!
Put subtitles in Portuguese, I'm from Brazil and I love your channel
*donkus kong music intensifies*
It's important to note that these optimizations are only possible because you're leaving definition behind, not that it's bad, but because those are the compromises you're willing to make
I've never watched your videos before but I approve of your choice of music
Beyond Good and Evil is such a good game
I have considered this approach in my little MC-like game, but using integers for the coordinates meant that block models with fractional coordinates are not supported: things like half-slabs, glass panes, the brewing stand. To support those, a fixed-point number could be used, but I wasn't sure how to design such a structure. I didn't want to pick the number of bits for the fractional part, e.g. 4 bits for a resolution of 0.0625 blocks, only to later on find out that I want to implement a block that needs a greater resolution for its model.
Now that I think about it, it's not such a big deal. Changing the number of bits for the fractional part could be as easy as just changing a constant in the CPU program and vertex shader with no changes to code, but at the time I was kinda scared to make a decision.
There's several big improvements to do.
The first one would be to only use 4 vertex per face, using vertex index.
The second would be (and here I'm being more hypothetical), to only use 1 vertex per block, since all the relevant data of a single voxel can be contained in a single vertex, and the the whole block can be constructed in the geometry shader or somethig
Using an index buffer as you suggest would actually increase the memory usage.
My method 6 vertices *4 bytes each =24 bytes per face
Index buffer 4 vertices * 4 bytes each + 6 indices * 4 bytes each = 40 bytes
As for the geometry shader, I could but I never learned how use those lol
Finally this series is back!
Instead of lighting value, I would use a normal index which maps to one of six possible normal vectors in de shaders that you can then use for any light sources. Since you only need to worry about 6 possible normals, 3 bits will still suffice.
3:40 I don't know if you made a mistake, but 32 binary values can fit within 5 bits, from 0 (00000) to 31 (11111). So we only need 15 bits to store position information.
There are 33 possible vertex positions from 0 to 32
Imagine chunks are 2x2, then the top verticies would be like this
._._.
Where the dots represents vertex, the positions go from 0 to 2, giving 3 possible vertex positions in a given axis
Hopson I really like your videos so I'm making this comment to stimulate the algorithm
Music from BG&E... Thank you :D
0:15 Wanted to point out a mistake here. All triangles are convex. in simple terms this means that if you wrap a string or rubber band around it you'll never have points that poke inward away from the band.
Triangles are also coplanar, for which the definition in the video is given as the definition of 'convex'.
Not sure what coplanar means but it's probably out the scope of what the point of this video is, but I'll look into that regardless
Any updates on this project? Love seeing this code optimization type videos. A suggestion on the lighting though, make it 1 byte so you have all possible light intensities (0-255). Its going to make the light decay from torches or other light sources look much better
saw the 2017 one week minecraft vid and now I'm trying to decide how to catch up
Great video!
definitely late to the party, but I just wanted to point out that you could have saved an additional bit on lighting. Instead of storing 2 through 5, you could subtract 2 from each and only store 0 through 3, which can be stored in just 2 bits instead of 3. Afterwards on the unpacking method you can just add the 2 you took previously to return it in the range of 2 to 5, and divide by 5 normally.
Probably too late to even mention but I just wanted to contribute somewhat.
These videos are so nice to watch!
this video is super awesome, thanks alot dude!
Yaaaay i been waiting for another of these. Inspiration!!
you a real one for the DKC2 tracks
ahh, good memories,
wrote my bachelor thesis about a better greedy meshing implementation,
abusing the fact that faces can overlap other same texture faces and span over occluded space.
tho, with a new method, I have also proven that you can trade memory and face count, yielding at max 96 face checkerboard chunk of 32x32x32 blocks. in this usecase gpu mem might be cheaper than flops.
I know that background music.... Cave Story!
a really fun video I enjoyed watching!
yeah absolutely understood
Also you could shave another bit off the lighting easily but seeing as it fits nicely into a 32 bit int I don't see a reason to. (You can store it as 0 to 3 and do number*0.2 + 0.2 to convert back.)
When I heard CaveStory music at the start I almost fainted
Just use a volume texture and have a bit for each voxel on the rendering side, and then maybe a byte for material. Just calculate everything else on the fly.
Greedy meshing is a sloppy approximate to the least quads or optimal coverage problem, it's very easy to implement, will more than 20x your memory efficiency and doesn't require crazy math (0fps makes everything seem complicated) just iterate slices of your chunks, as usual we will be collecting up all the instances of solid voxels which have a faces exposed to air,
For greedy meshing we just place these 1x1 boxes into a 2d array and expand / combine them, the silly epsilon symbols and so forth on the 0fps page just say that he does that by growing / merging to the right and then down, it's a simple algorithm with no math involved.
To get OPTIMAL meshing (side note: again you don't need any of this advanced technology to solve your basic problem of needing LOD, and besides view distance is fundamentally N*3 and so will never scale well with any (even enormous) linear performance optimizations, but since you made this great video I'll explain; Finding the least rects to cover a 2d grid is exactly the same type of task as path finding thru a 2d grid, in both cases there is some definite optimal goal (the shortest path or smallest mesh), in both cases it is possible to layout a series of steps or changes (for navigation it's movement , for meshing it's placing a piece of geometry) this task can be done OPTIMALLY if you have a heuristic or scoring system which is able to reliably return an upper-bound no better than it really is, It can be done EFFICIENTLY if your heuristic produces a tight lower-bound. Thankfully these are both trivial for the axis aligned uniformly sized uniformly distributed 2d case, you can just count the remaining corners (since you know they will eventually need a box) which is to say the optimal path thru this mesh space (note: use a branch and bound don't try to actually code this next part) is to draw a box which covers every (say top left) corner and then expand out as much as possible, there's much that can be done with texture packing and slice render fusion but again, LOD will save u. Lov ur vid, peace out
How about just rendering quadrilaterals, since a voxel world doesn't really have any triangles in it? That should bring down the memory usage a ton.
Maybe it was obvious , but chunkPositionLocation is an uniform . I couldn't for my life understand how all that data could fit in 6 bits :)
2:36 WHAT IS THIS BEAUTIFUL SONG
'Home sweet home' :Beyond Good and evil , it's an old PlayStation 2 game. Love it 😍
@@Biggy691 thank youuuu
Indexed rendering works fine with voxels, with ogl just tryAdd() each vert of your chunk to a hashmap and if it succeeds then store that vert in a new list, also make an int list with each of the original verts location in this new list, then just bind your buffers and switch your glDrawArrays() to a glDrawElementsBaseVertex(), but keep both code paths, drawArray is usually a better trade off in terms of mesh build time vs need to minimize maximum memory pool usage, speaking of which, you don't need to squeeze your vert data or embrace triangle lists (although you should if you also really need great performance) you are clearly trying to load too much of the world at full detail, accept level of detail into your life S:^P Peace
I love your videos man, you inspire me
That's actually insane, congratulations
You like Donkey Kong Country 1,2 and Cave Story musics xD
Surely you could build all the vertices in the geometry shader, only needing to store the voxel X,Y,Z pos and an index to it's texture.
That bg music is just awesome!!)
Where is he?
Cheers! All music is listed in the description
No, guy, I mean, why ain't ya Makin new videos? I love programming, regardless to the fact that I m a little bit newbie...)
What about vertex indexing? Usually you have a list of vertices, and a list of 16-bit unsigned integers to specify the sequence of how the vertices should be rendered. This means that vertices never have to be duplicated, helping a lot.
While it might be possible to do this in a voxel game that uses polygon rendering, it's incredibly awkward due to the nature of how the mesh is generated.
Usually you would add individual block faces to a mesh (a quad), and keep adding more quads. Issue is its hard to predict whether the next quad will be able to share vertices or not, without looking ahead of time. And by this point, algorithms such as greedy meshing give much better results, where rather than sharing verticies, you instead share entire faces, drastically reducing the triangle count, giving a huge boost in performance.
And sharing the vertices in the block faces themselves would actually use more memory than doing it this way. (I would type out the numbers to prove this, but I am on mobile atm :p)
Thanks for watching!