I noticed that you're calculating the vector to the sun's location for every point but since the sun is very far away we can say that the sun is always in the same direction so can calculate this once. This would also mean that when the sun is directly overhead there would be no shadows rather than shadows coming out radially which doesn't really make sense.
I was thinking about this after I'd uploaded the video, it's definitely a point light not a directional light so shouldn't have called it the sun! You could very easily repurpose the sun vec3 as a direction and use that instead of calculating per fragment, as you say.
Maybe could do a "reverse ray marching". That is from each visible pixel, a ray shoots toward the sun's supposed direction, if its ray can 'escape' (step > threshold) then it must not be in a shadow.
Nice! You can speed things up by creating mip-maps for the height texture, where a mipmap pixel stores the maximum height of the 2x2 pixel square from the lower mipmap level (instead of the usual average value). Effectively this forms a quadtree, with each tree node storing the maximum height in the corresponding region. This way, you can traverse the heightmap in larger steps and read high mipmap levels to skip large parts of the heightmap: if the maximum height in a large region of the map (corresponding to a pixel in some mipmap level) is smaller than the height of the corresponding part of the ray towards the sun (the part that goes over this region), you can be sure this region doesn't produce shadow at all. Otherwise, you descend to a smaller mipmap level, effectively traversing the quadtree.
I haven't actually used mipmaps before but this sounds like it could be the perfect way to try it out! I really like this idea, thanks for the comment!
I don't really know enough about shader compile-time optimization, but this seems like it might not gain all that much efficiency? I know in a CPU-based scenario this would definitely work, but with how shaders batch operations of different fragments/pixels, the way that fragments will have different shader run times based on if() conditions seems like the kind of thing that could easily slow it to worst case anyway (since afaik, a common method of shaders dealing with conditional branching that can't be optimized out like that is that it computes all cases + then only picks the correct result), as opposed to typical mipmap usage which isn't trying to operate unusual conditional logic like this.
Fun fact. This is used in game engines and it is called "Screen Space Shadows" or "Contact Shadows". Maybe useful if someone wants to find more information on this topic.
I came across a short paper a few month ago about self shadowing (Efficient Self-Shadowed Radiosity Normal Mapping, Chris Green). I never took the time to properly read it or implement it but if i remember correctly, they bake shadow information in their normal map so that they can render surface shadows with a single texture fetch. It could be worth a shot to look into it !
This is basically a self shadowing algorithm for PO mapping (with the same aliasing artifacts). Afaik there isn't really a much better way of doing this. Shadowmaps don't really work because they require geometry intersection. There are some approximations/heuristics that can be used so you have to do fewer steps per ray/pixel (or can get higher detail for the same number of steps) but in the end it's still the same general algorithm
You can make a 2D shadowmap (top down instead of from light direction) storing the minimum height that is not in shadow for each sample. You can then not only use that for other geometry on the terrain, you can also look at each sample of the heightmao itself and see if it is in shadow.
There absolutely is a better way, voxel ray tracing techniques apply and will be very fast considering There's a lot less data in a 2d height map than there is in a 3d voxel volume! Maybe look into DDA!
@@stysner4580 I obviously mean something different than what is shown in the video, otherwise I wouldn't have said something. Whether you want to call it raymarching or raytracing is irrelevant, but if you're interested, I've made a bunch of videos about voxels. DDA is a axis-aligned grid traversal algorithm designed to not miss any intersections, which would work for this. Also check out the "Fast Voxel Traversal Algorithm" paper by Amanatides and Woo
This is a very interesting video! The raycasting step size can be proportional to the difference between the height of the terrain at that point and the sampled position's height, so that it takes fewer steps when the sampled point is near the terrain and more when it is further away. You can also limit the step size so that it doesn't overshoot as often, and I think that this would reduce a lot of the artifacts.
These are all brilliant suggestions! I did want to put something like that in but, at least for the version of GLSL I'm running (very old because I'm using WEBGL), you HAVE to use a constant in a for loop, so I just have a fixed number of steps. I could probably get around it by just breaking early though! I'll give it a shot! Thanks for the comment!
@@BarneyCodes Since stepping along a distance field will never actually hit the object it doesn't matter how many loop iterations there are, it can be constant
@@Markyparky56 Similar but the p.y - heightmap.y SDF is not a true SDF, only an approximation, and a very rough one at that hence why you would need to clamp the max step distance otherwise you may run into overstepping issues (not even a lower bound)
Cone tracing is your friend and will allow you to get much higher quality at a low lower perf cost. How does cone tracing work? For each pixel in you height map you want to store the height but also the angle of the largest vertical cone that does not intersect any other terrain. When you do your ray cast you use the cone at a pixel to work out the max distance you can travel in a direction without hitting anything. This lets you do less samples when your ray is not near terrain but also sample at a higher resolution when near a blocker
Something tells me there has to be a way to bake this into a separate rgba texture. The sun’s position can be reduced to a 2 vector - theta with the origin being the center of the island, and height. If we want to make it more realistic with a day night cycle (and don’t mind rebaking if we want to change where north is) we can take it down to one. We just need some way of baking a whole gradient into one int. Then the rgba texture baking will be possible
Well you actually dont need a whole gradient. Since there are no overhangs for each pixel there will be a time where it leaves the shadow in the morning and a time where it enters it again in the evening. Now you can encode these two as values as time or as angle in an int and bake it.
Well thinking about it there are 2 ways of going about it. One is just optimizing the tracing, using some sort of height heiarchy with mipmaps maybe or using signed distance fields. The other way to do it, is straight up copying the 3D way of doing it and using a shadowmap, that would just cost VRAM and a bunch of matrix multiplications. Another simple optimization is to just do temporal calculation over a couple of frames.
Potential Solution to the artifacts caused by the large step sizes. Make each step length random per pixel per step. Keep the step size random between a range. This will replace the "stepped" look around the edges of the shadows in place for a noisy edge. To fix this, a small kernel box blur on the shadow mappings can help with that noise. This is assuming we are rendering the shadows onto a sperate render texture, and then later mixing it with the colors on another pass. If you don't want to blur the shadow, we can make the step lengths random per pixel per step per frame between a range, and then accumulate the results of the shadows over time.
One fix for the jagged shadow edges you can try is to step back when the ray hit: - Do the normal steps - When the ray hit, do a small loop that tries to go to the previous step with smaller increments, to have more precisions, stop when the ray doesn't hit anymore. You can even go further by using that fine hit position to calculate the "distance of the shadow", and reduce a bit the shadow intensity, to cheap fake smooth shadows from the sun (smaller distance = crisper shadows). And to have even more "precision", you can use the last two micros-steps (the blocking and non blocking ones), using their distance from the heightmap to do an inverse lerp and have a better estimation of the height of the projected shadow, and the distance.
to smooth out that dither or just get definition without ray marching cast shadows you can also generate a normal map then take the dot product of the stored vector to the vector of from the pixel too the light source and darken those pixels too. adding a threshold will give you a mask you can blend with to the mask generated by the ray marching before you darken the pixels
This video reminds me of a playable light and shadow demo and game by Nicky Case back in 2014. What he did was set a ray segment that stops when it hits an obstacle, set 50 of them in all directions and shape a polygon that simulated light by connecting the points together. However, this created some really jank polygons, the light would clip inside the obstacles or the rays would not hit right. It wouldn't matter if he did 360 rays or 50, it would look really jank regardless. So his solution was simple: rather than have the ray segments be cast in all directions, all he had to do was cast a ray until it hits a line segment, then added 2 rays that's + - 0.00001 radians of the ray segment. He then connects them all as a polygon (once again, to simulate light) then it magically made a beautiful light and shadow effect. For added effect, he made 11 more polygons that were radial around the center light source with different transparency to create a fuzzy light effect. Perhaps this could give you an idea on how to improve your 2d realtime shadow casting? I don't know the specifics and limitations but this could give you the idea you need. Also, check out Nicky Case's stuff in his website. He has some pretty cool stuff (and my tiny mind was blown away by the shadow and lights effect demo that he used which made me appreciate the game even more). What I wrote here is a shortened version of what he wrote in his website.
These are great comments and a great video! You could also borrow some tricks ray marching. My bet is that some of the square artifacts are from the steps just missing the heightmap when they should have hit. The trick would be to take really large steps when you are far from the heightmap and really small steps as you came closer to hitting it. So if you first made a small step twards the light, then checked the distance to the heightmap strait down, then used that value (maybe scaled) as the distance to make the next step. This would work because the heightmap should be continuous and have a maximum d at any point. The steps would start very small but increase as you passed over a deep valley. Then as you started getting closer to the heightmap the steps would automatically start getting smaller again. Maybe you could think of a smarter way to increase and decrease the step distance with more points but definitely leverage the fact that the noise should be continuous. You could test to see if this would work by setting the step distance to 100th its normal value and seeing if the artifacts go away. Obviously that would not be practical but you would know for sure its just a step size issue. Then figure out how to make big steps when you can and shorten them only when you need to.
I've actually just recently managed to get the method you described (moving relative to the vertical distance) and it definitely makes it look a LOT better! I think I'll probably do a follow up video with the new and improved version. Thanks for the comment!
This appears to simply be parallax self shadowing, which in 3D is a "practically solved" problem. For a purely 2D solution, Cone Step Mapping may end up the best solution. It has a fair bit of pre-processing, so it can't be used for realtime terrain generation. For a more real time compatible version, it may be possible to use a mip map based binary tree search, where each mip map contains the maximum height of the 4 pixels at this location. In the shader you then work down from the highest mip level to the lowest, requiring at worst pow(2, maxMipLevel-1) steps. Actually sounds fun to try and implement, so now I kind of want to do that.
I haven't heard of cone step mapping, I might have to look into it! A few other people have mentioned the mipmap technique too! I haven't used mipmaps before so could be a fun challenge to get it working!
Been using P5 web editor for years and watch youtube all the time but this is the first time I have ever seen anyone else use it!!! Well besides Dan The Coding Train Man! I made a few vids with it so this video is special to me thanks mate!
Thanks so much! I felt the same way when I was learning this stuff, there are a few really great channels out there but they either seem very beginner focussed or are really advanced, so I'm aiming for something in-between!
Looks great! I played around with the fragment shader to incorporate the distance between the sun and the pixel position into the number of steps taken. So the closer together they are, the fewer steps needed, and further they are, the more steps needed. Then set min and max number of steps. That stopped the shadows from breaking apart when the sun was far from the mountain, but I think overall average number of steps was similar
Perhaps as an optimization you could have a downscaled version of the heightmap where the height is determined by the maximum value in a region of pixels on the original heightmap. Then you can use bigger steps to get a rough estimate of whether a ray will be blocked or not and only use small steps on the actual height map in a small region.
There must be a better way than raycasting. My first thought was to smear the height map data along the projected sun direction. Places where the smeared image 'height' value is above the unaltered version is in shadow.
I found simply using smaller types (vec2 lightDir, vec2 p, vec2 stepDir), setting the colours mainly outside the loop, and a quick height check based on the height of the sun, which is just a smoothstep of how close the cursor is to the middle, fixed most issues here and gives a mostly reasonable result. Granted, it's hard to judge just how natural or reasonable the result is without a side-view. So gl_FragColor = texture2D(colour, pos); before the loop; then only run the loop if hgt > sunHeight; and then if h > hgt we do: gl_FragColor *= mix(SHADOW_TINT, gl_FragColor, 2.0 * i / MAX_STEPS) before the break.
You could use dynamic programming to have it run in constant (amortized) time on each unit (because the total cost is linear in the number of units), but then you introduce ordering requirements, which are not all that good for using it on GPUs. The idea is basically to start under the light source, and then expand out from there, with structure that constantly refers to what the previous highest point in that direction is, making the check for whether a new point is shadowed need only a constant amount of operations to find out. If the new point receives light, it is recorded as a new highest point, and depending on how you spread and such the old point might be removed. Depending on the pattern of expansion and such it might get a bit slower, as looking up in arbitary order can introduce some lookup costs, but it is possible to construct at least one kind of ordering where you do not need expensive lookups, and at most will have to discard a bunch of highest point at once, which is the part that make the cost be amortized.
Sounds like an interesting approach! Though like you said, I think it would be pretty much impossible to implement on the GPU. And the speed of the GPU is basically just as long as the slowest pixel so even if that slowest pixel is pretty slow, I imagine it would still be faster than doing each pixel one after the other on the CPU (especially at higher resolutions!). Would be an interesting experiment to try out though!
What you could do is paralize things in a pizza like slizing. There would be some extra work for each slize, so it would not be down to constant time per unit, but the algorithm has locality in those directions so it would still work and give you a huge reduction in requirements. Calculating such a slize would also only be marginally slower than calculating a single unit with ray tracing otherwise. An example of the power of this is that if you only do work on the outermost units, then you do the work equivalent to ray tracing, but just in the other direction, and while you pass each possible obstacle you have the option of noting down the solution to that object. Heck if you do it like this one could even go with computing an ongoing average for each pixel of how many of the paths through it that gave it light or not, and then use that average to give a softer transition from shadow to light.
I'm excited to try this! I might try baking an ambient occlusion texture to give the shadowed regions some detail. You could even bake a normal map and add full shading. Shaders are cool.
That sounds really cool, I'd love to see what you come up with! I was thinking about figuring out the normal on the fly in the shader so that way I can modify the terrain in real time and still get proper shading.
@@BarneyCodes I have no experience with shaders but I just learned about multivariate calculus in a maths unit I did. I think you can make a normal map by looking at the difference in height between every pair of pixels, once along the x axis and once along the y axis. You then make a 2D vector for each pixel, where the x component is change in height along the x axis (partial derivative with respect to x) and likewise for the y component. This is calculating the gradient of the heightmap as a vector field. You then need to figure out how much physical height the height map represents, as that affects the steepness of the normal map. Then we use trigonometry. The normal map angle along the x axis for each pixel is arctan(a/b), where a is the vertical change along the x direction adjusted for real height (get from the x component of gradient vector sample) and b is distance represented by a single pixel in the same unit, which is a constant. Do likewise for y angle. Not sure on the details for normal maps like how the angles are normalised but I think that would work.
My plan was something along those lines, but I didn't get much further than looking at the difference of height of neighbours. Thanks for fleshing it out!
For improved accuracy you can check for intersection at every pixel instead of every fixed step. Mark all traversed pixels ignoring vertical movement, then check for intersection. You can combine this with matt_miles' answer (precalculating the light vector) and precalculate the traversed pixels as well. There will be aliasing issues with this kind of optimization, which you can fix by doing precalculations at the sub-pixel level and blending at runtime.
The only real reason I did fixed steps is cos the version of GLSL I'm running is really old and only supports constants in for loops. I can get around that by not being lazy and just setting a max limit and breaking out of the loop if I hit my actual desired number of iterations. I'll definitely add this in! Thanks for the comment!
What I was thinking, is that you could cast a shadow for any pixel, that would only be rendered on pixels below it's height. So if you had a plane, there would be no shadow because they're all at the same height. I'm not a programmer so I cannot say if that's too resource intensive or not, I know gpus are good for parallel calculations so I would honestly try too brute force it before asking Reddit about it.
Because Perlin noise based terrain will never have overhangs, there are likely some optimizations you can gain by looking at the slope of surrounding pixels. I haven't done any math at this time, but I was just thinking "if the sun is directly above a pixel, you don't need to ray march because there can't possibly be any terrain between you and the sun". Extrapolating from this, if you're looking at the pixel just to the right of the one below the sun then there is a certain slope of the line drawn between sun and pixel. Unless you perlin noise is capable of generating leaps in height greater than that slope, you know this pixel must be lit. By knowing the maximum possible change in height and knowing the slope to the sun, you can probably avoid ray tracing for "trivially lit" pixels.
That’s a very interesting idea. Imagining the 2D cross section view, with the sun on the west side of the sky, and yourself marching from the west to east - You should be able to shadow the terrain it based on these conditions. 1) The terrain decreases in height as you march - i.e. negative slope value. 2) The negative slope is of an angle equal to or greater than the angle of the sun in the sky (gentle slopes away from the sun can still be lit if sun is high enough) 3) Terrain can still be shadowed by being behind large peaks - also can be identified via this gradient map. I can imagine a two-pass algorithm for this. First step based on the slope alone, then the second based on a reverse ray-marching from identified peaks. This gradient map can be precalculated, but has to be done for every direction (with respect to the sun), though the angle of the sun in the sky does not matter. No idea how intensive this gradient calculation is - so whether this can support dynamic terrain is unknown.
Lmao "perlin noise will never have overhangs". Bruh, he is using a 2D noise, of course it's not going to have overhangs that can only exist in 3D space
I can see a top down roman army strategy game in this still while adding fog for a fog of war scenario. With mounted and skirmisher scouts advancing forward to know where the enemy is before they know you are in.
I thought of a way to speed it up. I'm not sure how well it works in practice but here's my idea: You precompute the lowest slope to a limited amount of directions at every pixel of the height map so that the line with that slope in that direction doesn't hit (or just barely touch) the ground and then store the result into a texture. The precision can be kept very low so that the texture (or probably easier the textures for each direction) don't take up too much memory. Then when you have to decide if a point is in shadow you simply compare the slope to the sun and the slope stored in the texture of the closest direction to the sun and if the slope in the texture is higher than the one to the sun it's in shadow. I'm not sure how bad the memory cost is but it would be very fast since it's a simple comparison. With a low amount of "direction textures" it'd probably not look too good but I guess that could be optimized by testing. Maybe it looks interesting instead of simply bad because different points would snap to another direction texture at different times if the sun circled around for example.
Very interesting idea! I wonder if you could get away with a single texture, using the r, g, b, a values for slopes in the four cardinal directions, and just interpolate between them to get a better approximation of the sun?
@@BarneyCodes maybe you could even treat r, g, b, a as "signed" by setting an integer to be the value minus 127. This way you can store left-right, up-down, and the two diagonals in a single rgba texture. This would halve the "vertical" angle precision, but it would double the - much lower - precision on the plane of the image.
If any of your points are in shadow, then all fragments below the ray from the fragment up to the ray’s point of intersection with the terrain will also be in shadow. You can then mark all of these points as being in shadow, and check for each fragments shadow state before evaluation - that way you’ll save a bunch of iterations. (Edit for another thought:) In addition, if you travel back along the ray away from the sun, rather than up from your fragment toward it, there is another optimisation you could use along side the above suggestion. Assuming that you are moving away from the sun, then you could specify that the algorithm create an ordered set of fragments, sorted by height. If you then start the shadow casting from the highest fragment, that will maximise the number of additional fragments which will also be in shadow, and so will then not need to be checked. Starting with the highest ‘non-shadowed’ fragment guarantees that it will not itself be in shadow. In addition, once you’ve ‘hit’ the terrain, you can continue along/up it and mark off fragments as lit. (Imagine walking up the slope ‘following’ your silhouette and letting it point the direction you should travel) Any fragment you ‘walk’ on will be guaranteed to be ‘non-shadow’ fragments. These can be marked as non-shadow and they then don’t need to be checked. Then when you find the height begin to drop again, just switch back to the shadow casting check as before until you reach the next bit of terrain. Switch back and forth between these until you hit water. This will speed up the operation as always searching back from the highest fragment each iteration will produce the longest average shadows and the longest swaths of known shadow/lit fragments, reducing the number of remaining fragments to check on each cycle by the largest degree.
The issue with that first optimization is that every calculation for every pixel happens simultaneously on a GPU, so you can't share information to other pixels like that. In addition, the thing that really determines compute time on the GPU is how long the worst case scenario computation takes, so without reducing how long that longest step takes, it won't actually improve framerates
@@benjaminlehmann yeah GPU programming is quite hard because of issues like that. You don't really want to optimize the number of calculations, but the number of calculation in the worst case scenario, which is quite counterintuitive, and a very different task to accomplish. It's a completely different beast to CPU programming
This is probably dumb but could you make a separate shadow buffer? Where you take the pixel height the slope of the light and 2d direction to draw a line in the map with the value of the line decreasing along the slope of the light. For every pixel in the shadow buffer you draw to you just take the higher value. Then you just overlay the shadow map on the real map and for every value where the shadow map is higher then the real map you draw shadow.
(I know nothing about code so I don't know if its hard to code but) I think it could be optimized by instead of checking a bunch of times for each pixel, you could take each level of height map (every pixel with 0.01, then every with 0.02) and move it away from the sun and make it larger, the effect getting stronger the higher it is. This probably won't work though.
That's an interesting idea, I think it would produce a really interesting effect! Unfortunately with the way shaders work (they run all at the same time for each pixel on the screen, so your code can only influence one pixel), it might not be possible. I love the idea though, thanks for the comment!
I think one way to speed this up would be improving the ray tracing element. At the cost of memory, if you had something like a 3D texture that contained an SDF against the heights you could probably speed up the search drastically use sphere tracing.
Color theory tip: don't shadow things by just multiplying .rgb with a value, it makes things look dead. You can use some other color space like oklch(there's also a cool color picker online), a gradient map or at least some power curves(e.g. e^(-0.8 * brightness) for r and 0.9 for g, b, to make shadows a little redder). You could also pick some colors with higher oklch chroma to make the island look more alive.
@@BarneyCodesadding to what blacklistnr1 is saying there's a channel on youtube called acerola that does alot with color theory and he made a good video and mentioned something called 'oklab' which ig is like rgb if it was scalled to human color perception rather than screen color perception. heres the video btw: ua-cam.com/video/fv-wlo8yVhk/v-deo.html
@@BarneyCodes You could also use some edge detect filter on the hight map to get a fast ambient occlusion map or you could generate an ambient map for what it should look like if everything is in shadow and just add the light pass to that, however you might have to play around with some color remapping to keep things within the range of 0-1. Things in shadow should usually be slightly blue because the sky is blue but some things are even at least partially in shadow of the sky itself and those should be close to black.
RGB color multiplication is very close to what happens in real life. Just tweak the color values a bit. To get really realistic you need two light sources: sun and sky. The sun is close to white with a slight yellow tint, the sky is very blue. Then: FinalColor = TerrainColor * (SunColor * IsNotInShadow + SkyColor)
Maybe you could save the shadow to a separate texture and apply some smoothing to it, before applying it to the terrain? It could help with some of the artifacts
@@BarneyCodes for soft shadows you could take into account how close was the closest sample to the terrain on it's path to the light source and make it not a simple on/off but more of a blend. this should also help with blockiness
Nice video, this looks fun : ) I have little practical experience, but my two cents: - You could have a preprocessing step on the height map which looks for the point where the slope direction changes, and then cast shadows only from these (instead of checking for a line to the sun). This would reduce the number of point to check (drastically for most terrains) and also, I think, the distance to step per point checked (but not as drastically). I think you can stop checking in any direction as soon as you find a higher terrain as well (since it will have to lead to another, higher, summit before getting lower again). But maybe the 2Dness of the map would make this a little harder than I'm thinking, not sure. - You could also use a shadow map instead of directly recoloring. This has some overhead, but I think combined with the step above it would still be faster (supposing it actually makes sense), and it opens up the opportunity to process the shadow in different ways. You could, for example, blur it's edges (I think, maybe this is not so easy because you'd have to avoid blurring the start of the shadows), or tint the shadow, etc; - Other than that, I see other comments talking about color theory, so I'd just like to second that : p
Running the noise function during calculation should be better than fixed resolution baked texture, but I guess performance would depend on noise function time
Part of the reason I did it this way is because I want to experiment with being able to modify the terrain while it's running and I think that'll be a lot easier on the CPU! Definitely could speed up the generation by using a shader though!
Makes sense. Are you doing noise based modifications or like individual tile? If just noise then you could have the noise inputs as uniforms. If tiles it could still be done but streaming tiles all the time to the GPU sounds like a pain
by casting the ray from the mouse (sun) to the point, the sun becomes like a point light. to have a parallel light (more like the sun), change line 21 in the fragment shader to ```vec3 stepDir = (sunPos*2.0-1.0)/STEPS;```
Thanks for the suggestion! I've been messing around with it a bit more and I think at somepoint it comes down to a limitation of using a texture for the height information. I'm now looking into either defining the terrain with SDFs or some other continuous function which will give me nice, smooth shadows!
I wonder if you could use interactive horizon mapping for this. It's a technique back from 2000 meant to produce self-shadowing on bump-mapped surfaces. I think it'll be less accurate, but also much faster.
Couldent you prebake this by having a normal map with the most extreme angles that the sun can be seen from encoded in color so that if the angle from the point to the sun is too extreme you turn shadow it You would need 1 channel for the most western angle the sun can be seen from, one for the most eastern, then the same for north/south im very tired when typing this so forgive me if im wrong
I was wondering about something similar to this, and then you would lerp between the four directions I suppose? I'll have to try it out, thanks for the comment!
Hey I know this is a bit old by now, but maybe step per pixel using Bressenhams (not sure about spelling) line drawing algorithm and pass the image resolution to the shader
Could you initialize a "light height" texture to the terrain, then propagate shadows along the direction of light rays using a jump flood algorithm (requiring multiple shader passes to generate a new light height texture each time), then darken any terrain lower than the light height texture?
@@BarneyCodes "The Quest for Very Wide Outlines" reports quite fast performance for a similar task (drawing outlines around objects, rather than shadows) but the algorithm should transfer. I don't know how to write multi-pass shaders though.
please correct me if i'm wrong, but can't you do the "shadow casting" the other way around ? something like this maybe: first you create a grid of coordinates based on the height of the map on each point (more points, better shadow resolution?) and you sort them by height then you create a vector from the sun to the highest point in your map (which is always illuminated) and mark it as done once you have that vector, you can follow it down until it reaches the ground again, marking all points "below" that as shaded then you just filter your coordinates array, removing all points either shaded or illuminated, and repeat. i think this is something similar to what some pathfinding algorithms do, but i've never done anything even remotely related to shaders or graphics, so pardon my ignorance. also, this is really interesting, and now i wanna try it for myself. if someone spots a flaw with my logic, please let me know before i lose whats left of my hair
I like this approach a lot! But unfortunately I don't think it will work well in a shader. Basically what a fragment shader does is figure out what colour each pixel should be, and it does this by running the code for each pixel all at the same time, so it's very hard to share data between fragments/pixels. I think you're approach would work pretty well on the CPU though!
Thanks so much for all the support and suggestions! If you'd like to see what else I'm working on, it would be great if you could wishlist my game Star Mining Co. on Steam! s.team/a/2584800/
I'll have a look into bisection! As for using an SDF, I can't seem to find a good method for generating one based on a heightmap, otherwise I'd definitely use one!
To try to remove the artefacts you could maybe dynamically change the step size (the closer the point to the ray, the smaller the steps are) just like ray marching !
What would be amazing is to try and figure out some way to convert the heightmap into an SDF so that proper ray marching techniques could be used! In it's heightmap form though it's a bit tricky to figure out what a safe step size is (while staying performant!) Thanks for the comment!
@@BarneyCodes Ah you're probably right, it would be quite expensive to calculate a safe size for each steps, it's a very interesting subject, I going to give it a try ! Really nice video btw, well done and thank you !
I'm sure there is, and a lot of people have suggested using mipmaps as a quad tree to help take larger steps when possible. I'd really love to create some method of generating an SDF from a height map so then you could do some proper ray marching
Could this be used to generate Self-Shadowing Bumpmaps like Valve uses in their games? Basically, you generate 3 shadows at 120 degree intervals, represented by a red, green, and blue shadow on the image, where the intensity of each shadow represents how high the sun has to be before that pixel is no longer in shadow.
I haven't heard of that technique before but it sounds really interesting! I'm guessing you'd interpolate between the colours for angles between the 120 degree intervals? I certainly think you could do something like that with this shader with a bit of modification!
i'm not sure if this would work, but instead of simply making small steps to check the vector, use DDA raycasting, it might improve performance as well.
there is website which name is shademap, I wonder how it makes the sine shape on larger scale and managing render shadow of mountains, when you scroll out you can see what I mean, could you explain how?
It honestly looks like it would use a similar technique to the one I show in this video. I would assume they have access to the height data of the region of the map they are showing and they can use that to do the ray casting to see if an area is in shadow or not!
This being similar to a 3d raymarching algorithm you can take advantage of it's low hanging fruit enhancements like rendering the shadows penumbra making it more realistic ❤
In this video I'm using P5js which is a JavaScript librbary that gives really easy access to the canvas and WebGL. The shader itself is written in GLSL. Hope that clears things up!
Wonderful video. Such a good concept. Ive built this in unity. Using compute shader to generate the height and color map. Just not able to get the shadows working. Not sure if i should pass the mouse position as texture coordinates or uv. Please help me.
Glad you liked it! I haven't used Unity so I'm not 100% sure, but there should be a way for you to set variables in your shader from your script. In this case you'll probably want to use a vector with the mouse coordinates in the x and y. From a bit of googling it looks like there is a SetVectorArray() function which looks like it lets you set a vector array in your shader. Hope that helps!
Thank you. That isn't the problem. I'm not sure if the vector from the point to the "sun" is in texture coordinates or world space coordinates. Because of this the iteration for the shadows isn't giving me consistent pixel values. Anyways, I'll keep trying and I'll let you know if I've cracked it. Thanks for the video. Pretty awesome.
Hey! Small update, I got it working!! I was trying to do this in the compute shader itself. That was my mistake. I didn't even notice that it was not in a fragment shader. Looks wonderful. Thank you so much ❤️🔥🤙
Turn the sun from a point-like source to an area (or even approximate with a 3x3 "circle") and you'll improve the aliased shadows and get softer shadowing.
Thank you! Very helpful feedback, I haven't really used music in my videos much before so still getting the hang of it, hopefully will be better next time!
@@BarneyCodes I usually just keep an eye on the audio levels and keep the music at around half (or less) of the average db level for mic, you'll get a feel for it but other than that, it's a fantastic video!
what you could do is turn the heightmap into a normal map, use that to calcualte lighting, and then ignore all the regions that that algorithm puts in shadow
Since publishing the video I did try this and it definitely seemed to help, but the normal map unfortunately suffers from the same issue of the data it's using is discrete (since the height map is an image) so I get some artifacts in the normal, just like I was getting with the original shadows
I feel like ray-marching could greatly improve the performance, but I'm not sure how you'd calculate the minimum distance you can travel. (that's what I did in my 3d raycaster :D) If I figure it out, I'll edit this comment.
I've been trying to figure this out as well, I think it would not only be a massive performance boost, but should reduce a lot of the artefacts too. A few people have suggested using mipmap levels as a sort of quadtree, but I can see how, in WEBGL, to set up the mipmaps to use the MAX of a neighbour hood rather than the average, which is what would be needed to get it to work! I was wondering if there would be a way to use an FFT to break the height map into a series of frequencies and using that, but I'm not sure how that would look in 2D and how to use that in the GPU for more accurate distance calculations. My other idea was to try and approximate the shape of the height map with a series of spheres that would then be very easy to do an SDF on, but I can't think of a good way to approximate it! If you've got any thoughts I'd love to hear them!
pretty cute shader. Welcome to integration functions. There's loads of complicated ways of improving this. One is power spacing so the futher away from the source you are the larger the step, and the second is doing quasiy sphere tracing where you use the fact that your heightmap is smooth to guess if you are close to the ground and do more samples when the terrain height get's closer too current sample height. This is really complicated solving from scatch and I recomend using Desmos or the like to write you math first.
@@BarneyCodes Thank You! You not only made video with easy to understanding and interesting demonstration, but share full code! It's rarely seen nowadays. I am additionally gratefull for simplest noise-generated terrain example i ever seen. Every topic about terrain generation includes 'actaves', 'amplitude' and 'frequency', which makes my brain instantly evaporate. In your example less features, but still looks great!
Thank you so much, that's very kind! I think things like procedural generation can get as complex or as simple as you like. Definitely for more realistic terrain you'll need to start diving into those things, but for the basics it's not too necessary. In case you're interested, octaves, amplitudes and frequencies are all just used to layer noise together. Each layer is called an "octave" and each octave has double the frequency of the previous one, but a lower amplitude. A higher frequency means that the noise is more zoomed-out looking, so the hills it creates will be closer together, but to make that not overwhelm the terrain, the amplitude is turned down, which just means that the close together hills are not as tall as the ones of the previous octave. By adding together these different noise layers you end up with terrain that has large hills and valleys, but those hills and valleys also have some variation to them instead of just being smooth. Adding more octaves adds more detail to the terrain! Hopefully that wasn't too mind-evaporating! It can definitely be a bit difficult to conceptualise, but I'm sure it'll make sense with some practice!
heres something i learned about shaders: staw away from using gray colors to represent height. because at most you only get 255 possible height levels, which might be way too little depending on your needs.
This would work in 2d but probably not 3d: turn heightmap into a math formula (eg sum of sines) then do some magic to fin the range where formula A (ray line) > formula B (height)
oh cosine decomposition, I like it, it's not super important that the shape of the height-map is perfectly preserved so the lossy nature of it isn't a big deal
I usually complain a lot about UA-cam and their stupid fucking algorythms n that but I'm ngl, the past few weeks I've been getting some awesome channels.
I noticed that you're calculating the vector to the sun's location for every point but since the sun is very far away we can say that the sun is always in the same direction so can calculate this once. This would also mean that when the sun is directly overhead there would be no shadows rather than shadows coming out radially which doesn't really make sense.
I was thinking about this after I'd uploaded the video, it's definitely a point light not a directional light so shouldn't have called it the sun!
You could very easily repurpose the sun vec3 as a direction and use that instead of calculating per fragment, as you say.
Maybe could do a "reverse ray marching". That is from each visible pixel, a ray shoots toward the sun's supposed direction, if its ray can 'escape' (step > threshold) then it must not be in a shadow.
@@jurian0101 that's the technique shown in the video
yeah, i though so as well
but when the sun is directly overhead irl there _are no shadows_. (see lahaina noon)
Nice! You can speed things up by creating mip-maps for the height texture, where a mipmap pixel stores the maximum height of the 2x2 pixel square from the lower mipmap level (instead of the usual average value). Effectively this forms a quadtree, with each tree node storing the maximum height in the corresponding region. This way, you can traverse the heightmap in larger steps and read high mipmap levels to skip large parts of the heightmap: if the maximum height in a large region of the map (corresponding to a pixel in some mipmap level) is smaller than the height of the corresponding part of the ray towards the sun (the part that goes over this region), you can be sure this region doesn't produce shadow at all. Otherwise, you descend to a smaller mipmap level, effectively traversing the quadtree.
Okay, now I know what a mipmap is ! Thank you !
I haven't actually used mipmaps before but this sounds like it could be the perfect way to try it out! I really like this idea, thanks for the comment!
Never used mip maps sounds basically like a LOD but for a image basically
I don't really know enough about shader compile-time optimization, but this seems like it might not gain all that much efficiency? I know in a CPU-based scenario this would definitely work, but with how shaders batch operations of different fragments/pixels, the way that fragments will have different shader run times based on if() conditions seems like the kind of thing that could easily slow it to worst case anyway (since afaik, a common method of shaders dealing with conditional branching that can't be optimized out like that is that it computes all cases + then only picks the correct result), as opposed to typical mipmap usage which isn't trying to operate unusual conditional logic like this.
My idea exactly
Fun fact. This is used in game engines and it is called "Screen Space Shadows" or "Contact Shadows". Maybe useful if someone wants to find more information on this topic.
I came across a short paper a few month ago about self shadowing (Efficient Self-Shadowed Radiosity Normal Mapping, Chris Green). I never took the time to properly read it or implement it but if i remember correctly, they bake shadow information in their normal map so that they can render surface shadows with a single texture fetch. It could be worth a shot to look into it !
That sounds really interesting, I'll give it a read, thanks for sharing!
This is basically a self shadowing algorithm for PO mapping (with the same aliasing artifacts). Afaik there isn't really a much better way of doing this. Shadowmaps don't really work because they require geometry intersection. There are some approximations/heuristics that can be used so you have to do fewer steps per ray/pixel (or can get higher detail for the same number of steps) but in the end it's still the same general algorithm
Interesting, thanks for sharing! I might look into some of the optimisations you mentioned just for the fun of it!
You can make a 2D shadowmap (top down instead of from light direction) storing the minimum height that is not in shadow for each sample. You can then not only use that for other geometry on the terrain, you can also look at each sample of the heightmao itself and see if it is in shadow.
There absolutely is a better way, voxel ray tracing techniques apply and will be very fast considering There's a lot less data in a 2d height map than there is in a 3d voxel volume! Maybe look into DDA!
@@GabeRundlett Voxel ray tracing... You mean raymarching? What OP is already doing?
@@stysner4580 I obviously mean something different than what is shown in the video, otherwise I wouldn't have said something. Whether you want to call it raymarching or raytracing is irrelevant, but if you're interested, I've made a bunch of videos about voxels. DDA is a axis-aligned grid traversal algorithm designed to not miss any intersections, which would work for this. Also check out the "Fast Voxel Traversal Algorithm" paper by Amanatides and Woo
This is a very interesting video! The raycasting step size can be proportional to the difference between the height of the terrain at that point and the sampled position's height, so that it takes fewer steps when the sampled point is near the terrain and more when it is further away. You can also limit the step size so that it doesn't overshoot as often, and I think that this would reduce a lot of the artifacts.
These are all brilliant suggestions! I did want to put something like that in but, at least for the version of GLSL I'm running (very old because I'm using WEBGL), you HAVE to use a constant in a for loop, so I just have a fixed number of steps. I could probably get around it by just breaking early though! I'll give it a shot! Thanks for the comment!
@@BarneyCodes Since stepping along a distance field will never actually hit the object it doesn't matter how many loop iterations there are, it can be constant
I guess I can just have a max steps and break early if we hit terrain or break free
Effectively sphere tracing an sdf
@@Markyparky56 Similar but the p.y - heightmap.y SDF is not a true SDF, only an approximation, and a very rough one at that hence why you would need to clamp the max step distance otherwise you may run into overstepping issues (not even a lower bound)
Cone tracing is your friend and will allow you to get much higher quality at a low lower perf cost.
How does cone tracing work?
For each pixel in you height map you want to store the height but also the angle of the largest vertical cone that does not intersect any other terrain.
When you do your ray cast you use the cone at a pixel to work out the max distance you can travel in a direction without hitting anything.
This lets you do less samples when your ray is not near terrain but also sample at a higher resolution when near a blocker
Ahh thank you, that's brilliant!
Something tells me there has to be a way to bake this into a separate rgba texture. The sun’s position can be reduced to a 2 vector - theta with the origin being the center of the island, and height. If we want to make it more realistic with a day night cycle (and don’t mind rebaking if we want to change where north is) we can take it down to one. We just need some way of baking a whole gradient into one int. Then the rgba texture baking will be possible
Well you actually dont need a whole gradient. Since there are no overhangs for each pixel there will be a time where it leaves the shadow in the morning and a time where it enters it again in the evening. Now you can encode these two as values as time or as angle in an int and bake it.
@@ben_solo this seems like the best solution. also comes with free soft shadow.
Nice video. I appreciate your dedication to making clear visual aids.
Thanks, appreciate it!
Love a short and sweet video. It's as long as it needs to be to explain the topic. Thanks for not dragging it on for longer than necessary lol
Well thinking about it there are 2 ways of going about it. One is just optimizing the tracing, using some sort of height heiarchy with mipmaps maybe or using signed distance fields. The other way to do it, is straight up copying the 3D way of doing it and using a shadowmap, that would just cost VRAM and a bunch of matrix multiplications. Another simple optimization is to just do temporal calculation over a couple of frames.
Potential Solution to the artifacts caused by the large step sizes. Make each step length random per pixel per step. Keep the step size random between a range. This will replace the "stepped" look around the edges of the shadows in place for a noisy edge. To fix this, a small kernel box blur on the shadow mappings can help with that noise. This is assuming we are rendering the shadows onto a sperate render texture, and then later mixing it with the colors on another pass. If you don't want to blur the shadow, we can make the step lengths random per pixel per step per frame between a range, and then accumulate the results of the shadows over time.
One fix for the jagged shadow edges you can try is to step back when the ray hit:
- Do the normal steps
- When the ray hit, do a small loop that tries to go to the previous step with smaller increments, to have more precisions, stop when the ray doesn't hit anymore.
You can even go further by using that fine hit position to calculate the "distance of the shadow", and reduce a bit the shadow intensity, to cheap fake smooth shadows from the sun (smaller distance = crisper shadows).
And to have even more "precision", you can use the last two micros-steps (the blocking and non blocking ones), using their distance from the heightmap to do an inverse lerp and have a better estimation of the height of the projected shadow, and the distance.
These are some great suggestions, thank you! I'll have to try them out!
to smooth out that dither or just get definition without ray marching cast shadows you can also generate a normal map then take the dot product of the stored vector to the vector of from the pixel too the light source and darken those pixels too. adding a threshold will give you a mask you can blend with to the mask generated by the ray marching before you darken the pixels
ugh. spelling errors, but the meta quest browser wont let me edit.
I think I'll do that in my next video! Just working on generating a normal from a height map at the moment!
This video reminds me of a playable light and shadow demo and game by Nicky Case back in 2014. What he did was set a ray segment that stops when it hits an obstacle, set 50 of them in all directions and shape a polygon that simulated light by connecting the points together. However, this created some really jank polygons, the light would clip inside the obstacles or the rays would not hit right. It wouldn't matter if he did 360 rays or 50, it would look really jank regardless.
So his solution was simple: rather than have the ray segments be cast in all directions, all he had to do was cast a ray until it hits a line segment, then added 2 rays that's + - 0.00001 radians of the ray segment. He then connects them all as a polygon (once again, to simulate light) then it magically made a beautiful light and shadow effect. For added effect, he made 11 more polygons that were radial around the center light source with different transparency to create a fuzzy light effect.
Perhaps this could give you an idea on how to improve your 2d realtime shadow casting? I don't know the specifics and limitations but this could give you the idea you need. Also, check out Nicky Case's stuff in his website. He has some pretty cool stuff (and my tiny mind was blown away by the shadow and lights effect demo that he used which made me appreciate the game even more). What I wrote here is a shortened version of what he wrote in his website.
I'll check out Nicky's work! Thanks for the comment!
This sounds like a very primitive ray traced shadows. Very cool!
These are great comments and a great video!
You could also borrow some tricks ray marching. My bet is that some of the square artifacts are from the steps just missing the heightmap when they should have hit. The trick would be to take really large steps when you are far from the heightmap and really small steps as you came closer to hitting it.
So if you first made a small step twards the light, then checked the distance to the heightmap strait down, then used that value (maybe scaled) as the distance to make the next step. This would work because the heightmap should be continuous and have a maximum d at any point.
The steps would start very small but increase as you passed over a deep valley. Then as you started getting closer to the heightmap the steps would automatically start getting smaller again.
Maybe you could think of a smarter way to increase and decrease the step distance with more points but definitely leverage the fact that the noise should be continuous.
You could test to see if this would work by setting the step distance to 100th its normal value and seeing if the artifacts go away. Obviously that would not be practical but you would know for sure its just a step size issue. Then figure out how to make big steps when you can and shorten them only when you need to.
I've actually just recently managed to get the method you described (moving relative to the vertical distance) and it definitely makes it look a LOT better!
I think I'll probably do a follow up video with the new and improved version.
Thanks for the comment!
This appears to simply be parallax self shadowing, which in 3D is a "practically solved" problem. For a purely 2D solution, Cone Step Mapping may end up the best solution. It has a fair bit of pre-processing, so it can't be used for realtime terrain generation.
For a more real time compatible version, it may be possible to use a mip map based binary tree search, where each mip map contains the maximum height of the 4 pixels at this location. In the shader you then work down from the highest mip level to the lowest, requiring at worst pow(2, maxMipLevel-1) steps.
Actually sounds fun to try and implement, so now I kind of want to do that.
I haven't heard of cone step mapping, I might have to look into it! A few other people have mentioned the mipmap technique too! I haven't used mipmaps before so could be a fun challenge to get it working!
Been using P5 web editor for years and watch youtube all the time but this is the first time I have ever seen anyone else use it!!! Well besides Dan The Coding Train Man! I made a few vids with it so this video is special to me thanks mate!
You could also add normal map and then darken the pixels facing away from the sun, and check for casted shadow only for the ones facing towards it.
Well he already has a dynamically generated height map, it wouldn’t be too hard to get surface normals from it which is basically bump mapping.
I'm going to try implementing this for the next video I think! Thanks for the comment!
This channel is what I always hoped to learn but never found a resource to begin with.....thank you so much for this!!!!!
Really great work.
Thanks so much! I felt the same way when I was learning this stuff, there are a few really great channels out there but they either seem very beginner focussed or are really advanced, so I'm aiming for something in-between!
Looks great! I played around with the fragment shader to incorporate the distance between the sun and the pixel position into the number of steps taken. So the closer together they are, the fewer steps needed, and further they are, the more steps needed. Then set min and max number of steps. That stopped the shadows from breaking apart when the sun was far from the mountain, but I think overall average number of steps was similar
Perhaps as an optimization you could have a downscaled version of the heightmap where the height is determined by the maximum value in a region of pixels on the original heightmap. Then you can use bigger steps to get a rough estimate of whether a ray will be blocked or not and only use small steps on the actual height map in a small region.
That's really clever! I like it a lot, thanks for the comment!
There must be a better way than raycasting.
My first thought was to smear the height map data along the projected sun direction.
Places where the smeared image 'height' value is above the unaltered version is in shadow.
I found simply using smaller types (vec2 lightDir, vec2 p, vec2 stepDir), setting the colours mainly outside the loop, and a quick height check based on the height of the sun, which is just a smoothstep of how close the cursor is to the middle, fixed most issues here and gives a mostly reasonable result. Granted, it's hard to judge just how natural or reasonable the result is without a side-view.
So gl_FragColor = texture2D(colour, pos); before the loop; then only run the loop if hgt > sunHeight; and then if h > hgt we do: gl_FragColor *= mix(SHADOW_TINT, gl_FragColor, 2.0 * i / MAX_STEPS) before the break.
Oh awesome, I'll have to try it out! Thanks for the comment!
You could use dynamic programming to have it run in constant (amortized) time on each unit (because the total cost is linear in the number of units), but then you introduce ordering requirements, which are not all that good for using it on GPUs. The idea is basically to start under the light source, and then expand out from there, with structure that constantly refers to what the previous highest point in that direction is, making the check for whether a new point is shadowed need only a constant amount of operations to find out. If the new point receives light, it is recorded as a new highest point, and depending on how you spread and such the old point might be removed. Depending on the pattern of expansion and such it might get a bit slower, as looking up in arbitary order can introduce some lookup costs, but it is possible to construct at least one kind of ordering where you do not need expensive lookups, and at most will have to discard a bunch of highest point at once, which is the part that make the cost be amortized.
Sounds like an interesting approach! Though like you said, I think it would be pretty much impossible to implement on the GPU. And the speed of the GPU is basically just as long as the slowest pixel so even if that slowest pixel is pretty slow, I imagine it would still be faster than doing each pixel one after the other on the CPU (especially at higher resolutions!).
Would be an interesting experiment to try out though!
What you could do is paralize things in a pizza like slizing. There would be some extra work for each slize, so it would not be down to constant time per unit, but the algorithm has locality in those directions so it would still work and give you a huge reduction in requirements. Calculating such a slize would also only be marginally slower than calculating a single unit with ray tracing otherwise.
An example of the power of this is that if you only do work on the outermost units, then you do the work equivalent to ray tracing, but just in the other direction, and while you pass each possible obstacle you have the option of noting down the solution to that object. Heck if you do it like this one could even go with computing an ongoing average for each pixel of how many of the paths through it that gave it light or not, and then use that average to give a softer transition from shadow to light.
I'm excited to try this! I might try baking an ambient occlusion texture to give the shadowed regions some detail. You could even bake a normal map and add full shading. Shaders are cool.
That sounds really cool, I'd love to see what you come up with! I was thinking about figuring out the normal on the fly in the shader so that way I can modify the terrain in real time and still get proper shading.
@@BarneyCodes I have no experience with shaders but I just learned about multivariate calculus in a maths unit I did.
I think you can make a normal map by looking at the difference in height between every pair of pixels, once along the x axis and once along the y axis. You then make a 2D vector for each pixel, where the x component is change in height along the x axis (partial derivative with respect to x) and likewise for the y component. This is calculating the gradient of the heightmap as a vector field.
You then need to figure out how much physical height the height map represents, as that affects the steepness of the normal map.
Then we use trigonometry. The normal map angle along the x axis for each pixel is arctan(a/b), where a is the vertical change along the x direction adjusted for real height (get from the x component of gradient vector sample) and b is distance represented by a single pixel in the same unit, which is a constant. Do likewise for y angle. Not sure on the details for normal maps like how the angles are normalised but I think that would work.
My plan was something along those lines, but I didn't get much further than looking at the difference of height of neighbours. Thanks for fleshing it out!
For improved accuracy you can check for intersection at every pixel instead of every fixed step. Mark all traversed pixels ignoring vertical movement, then check for intersection.
You can combine this with matt_miles' answer (precalculating the light vector) and precalculate the traversed pixels as well. There will be aliasing issues with this kind of optimization, which you can fix by doing precalculations at the sub-pixel level and blending at runtime.
The only real reason I did fixed steps is cos the version of GLSL I'm running is really old and only supports constants in for loops. I can get around that by not being lazy and just setting a max limit and breaking out of the loop if I hit my actual desired number of iterations. I'll definitely add this in! Thanks for the comment!
What I was thinking, is that you could cast a shadow for any pixel, that would only be rendered on pixels below it's height. So if you had a plane, there would be no shadow because they're all at the same height.
I'm not a programmer so I cannot say if that's too resource intensive or not, I know gpus are good for parallel calculations so I would honestly try too brute force it before asking Reddit about it.
Because Perlin noise based terrain will never have overhangs, there are likely some optimizations you can gain by looking at the slope of surrounding pixels. I haven't done any math at this time, but I was just thinking "if the sun is directly above a pixel, you don't need to ray march because there can't possibly be any terrain between you and the sun". Extrapolating from this, if you're looking at the pixel just to the right of the one below the sun then there is a certain slope of the line drawn between sun and pixel. Unless you perlin noise is capable of generating leaps in height greater than that slope, you know this pixel must be lit. By knowing the maximum possible change in height and knowing the slope to the sun, you can probably avoid ray tracing for "trivially lit" pixels.
That’s a very interesting idea. Imagining the 2D cross section view, with the sun on the west side of the sky, and yourself marching from the west to east - You should be able to shadow the terrain it based on these conditions.
1) The terrain decreases in height as you march - i.e. negative slope value.
2) The negative slope is of an angle equal to or greater than the angle of the sun in the sky (gentle slopes away from the sun can still be lit if sun is high enough)
3) Terrain can still be shadowed by being behind large peaks - also can be identified via this gradient map.
I can imagine a two-pass algorithm for this. First step based on the slope alone, then the second based on a reverse ray-marching from identified peaks.
This gradient map can be precalculated, but has to be done for every direction (with respect to the sun), though the angle of the sun in the sky does not matter.
No idea how intensive this gradient calculation is - so whether this can support dynamic terrain is unknown.
Lmao "perlin noise will never have overhangs". Bruh, he is using a 2D noise, of course it's not going to have overhangs that can only exist in 3D space
I can see a top down roman army strategy game in this still while adding fog for a fog of war scenario. With mounted and skirmisher scouts advancing forward to know where the enemy is before they know you are in.
Ray marching! Love this.
This is perfect for my project.
Thank you!
No worries! Would love to see what you're working on if you want to pop into my discord server?
@@BarneyCodes Sure, why not.
I'm there!
Great work, Barney! I’d love to see a 3d shadow map, but definitely don’t need it in real time. Something I’ve wanted for projects for a while.
Thanks Steve! I'll have to give it a go and let you know how it goes!
I've found that three.js can be used for 3d shadows.
How does this channel only have 7k viewers? I feel like you will eventually have 100s of 1000s.
Wow, thanks! We'll see how it goes haha
I thought of a way to speed it up. I'm not sure how well it works in practice but here's my idea: You precompute the lowest slope to a limited amount of directions at every pixel of the height map so that the line with that slope in that direction doesn't hit (or just barely touch) the ground and then store the result into a texture. The precision can be kept very low so that the texture (or probably easier the textures for each direction) don't take up too much memory. Then when you have to decide if a point is in shadow you simply compare the slope to the sun and the slope stored in the texture of the closest direction to the sun and if the slope in the texture is higher than the one to the sun it's in shadow. I'm not sure how bad the memory cost is but it would be very fast since it's a simple comparison. With a low amount of "direction textures" it'd probably not look too good but I guess that could be optimized by testing. Maybe it looks interesting instead of simply bad because different points would snap to another direction texture at different times if the sun circled around for example.
Very interesting idea! I wonder if you could get away with a single texture, using the r, g, b, a values for slopes in the four cardinal directions, and just interpolate between them to get a better approximation of the sun?
@@BarneyCodes maybe you could even treat r, g, b, a as "signed" by setting an integer to be the value minus 127. This way you can store left-right, up-down, and the two diagonals in a single rgba texture. This would halve the "vertical" angle precision, but it would double the - much lower - precision on the plane of the image.
If any of your points are in shadow, then all fragments below the ray from the fragment up to the ray’s point of intersection with the terrain will also be in shadow. You can then mark all of these points as being in shadow, and check for each fragments shadow state before evaluation - that way you’ll save a bunch of iterations.
(Edit for another thought:)
In addition, if you travel back along the ray away from the sun, rather than up from your fragment toward it, there is another optimisation you could use along side the above suggestion.
Assuming that you are moving away from the sun, then you could specify that the algorithm create an ordered set of fragments, sorted by height. If you then start the shadow casting from the highest fragment, that will maximise the number of additional fragments which will also be in shadow, and so will then not need to be checked.
Starting with the highest ‘non-shadowed’ fragment guarantees that it will not itself be in shadow.
In addition, once you’ve ‘hit’ the terrain, you can continue along/up it and mark off fragments as lit. (Imagine walking up the slope ‘following’ your silhouette and letting it point the direction you should travel) Any fragment you ‘walk’ on will be guaranteed to be ‘non-shadow’ fragments. These can be marked as non-shadow and they then don’t need to be checked. Then when you find the height begin to drop again, just switch back to the shadow casting check as before until you reach the next bit of terrain. Switch back and forth between these until you hit water.
This will speed up the operation as always searching back from the highest fragment each iteration will produce the longest average shadows and the longest swaths of known shadow/lit fragments, reducing the number of remaining fragments to check on each cycle by the largest degree.
The issue with that first optimization is that every calculation for every pixel happens simultaneously on a GPU, so you can't share information to other pixels like that. In addition, the thing that really determines compute time on the GPU is how long the worst case scenario computation takes, so without reducing how long that longest step takes, it won't actually improve framerates
@@adicsbtw Huh. Well that's good to know. I wasn't thinking about that. Good shout.
@@benjaminlehmann yeah
GPU programming is quite hard because of issues like that. You don't really want to optimize the number of calculations, but the number of calculation in the worst case scenario, which is quite counterintuitive, and a very different task to accomplish. It's a completely different beast to CPU programming
This is probably dumb but could you make a separate shadow buffer? Where you take the pixel height the slope of the light and 2d direction to draw a line in the map with the value of the line decreasing along the slope of the light. For every pixel in the shadow buffer you draw to you just take the higher value. Then you just overlay the shadow map on the real map and for every value where the shadow map is higher then the real map you draw shadow.
I think that would definitely work but I think it would be a struggle to get it working in a shader. Neat idea!
(I know nothing about code so I don't know if its hard to code but) I think it could be optimized by instead of checking a bunch of times for each pixel, you could take each level of height map (every pixel with 0.01, then every with 0.02) and move it away from the sun and make it larger, the effect getting stronger the higher it is. This probably won't work though.
That's an interesting idea, I think it would produce a really interesting effect! Unfortunately with the way shaders work (they run all at the same time for each pixel on the screen, so your code can only influence one pixel), it might not be possible. I love the idea though, thanks for the comment!
I think one way to speed this up would be improving the ray tracing element. At the cost of memory, if you had something like a 3D texture that contained an SDF against the heights you could probably speed up the search drastically use sphere tracing.
Came here to say this.
Color theory tip: don't shadow things by just multiplying .rgb with a value, it makes things look dead.
You can use some other color space like oklch(there's also a cool color picker online), a gradient map or at least some power curves(e.g. e^(-0.8 * brightness) for r and 0.9 for g, b, to make shadows a little redder).
You could also pick some colors with higher oklch chroma to make the island look more alive.
Thanks so much for the tips! Design certainly isn't my strong suit but is something I want to get better at!
@@BarneyCodesadding to what blacklistnr1 is saying there's a channel on youtube called acerola that does alot with color theory and he made a good video and mentioned something called 'oklab' which ig is like rgb if it was scalled to human color perception rather than screen color perception. heres the video btw: ua-cam.com/video/fv-wlo8yVhk/v-deo.html
@@BarneyCodes You could also use some edge detect filter on the hight map to get a fast ambient occlusion map or you could generate an ambient map for what it should look like if everything is in shadow and just add the light pass to that, however you might have to play around with some color remapping to keep things within the range of 0-1.
Things in shadow should usually be slightly blue because the sky is blue but some things are even at least partially in shadow of the sky itself and those should be close to black.
RGB color multiplication is very close to what happens in real life. Just tweak the color values a bit.
To get really realistic you need two light sources: sun and sky. The sun is close to white with a slight yellow tint, the sky is very blue.
Then:
FinalColor = TerrainColor * (SunColor * IsNotInShadow + SkyColor)
Maybe you could save the shadow to a separate texture and apply some smoothing to it, before applying it to the terrain? It could help with some of the artifacts
That could definitely work! I wonder if there's a way to blur more if the ray travelled further before hitting the terrain?
@@BarneyCodes I imagine getting the distance travelled wouldn't be hard, but no idea for the blurring :/
@@BarneyCodes for soft shadows you could take into account how close was the closest sample to the terrain on it's path to the light source and make it not a simple on/off but more of a blend. this should also help with blockiness
One issue I see is that this is a point light. A directional light would use the same step direction for all pixels.
Nice video, this looks fun : )
I have little practical experience, but my two cents:
- You could have a preprocessing step on the height map which looks for the point where the slope direction changes, and then cast shadows only from these (instead of checking for a line to the sun). This would reduce the number of point to check (drastically for most terrains) and also, I think, the distance to step per point checked (but not as drastically). I think you can stop checking in any direction as soon as you find a higher terrain as well (since it will have to lead to another, higher, summit before getting lower again). But maybe the 2Dness of the map would make this a little harder than I'm thinking, not sure.
- You could also use a shadow map instead of directly recoloring. This has some overhead, but I think combined with the step above it would still be faster (supposing it actually makes sense), and it opens up the opportunity to process the shadow in different ways. You could, for example, blur it's edges (I think, maybe this is not so easy because you'd have to avoid blurring the start of the shadows), or tint the shadow, etc;
- Other than that, I see other comments talking about color theory, so I'd just like to second that : p
Running the noise function during calculation should be better than fixed resolution baked texture, but I guess performance would depend on noise function time
Part of the reason I did it this way is because I want to experiment with being able to modify the terrain while it's running and I think that'll be a lot easier on the CPU! Definitely could speed up the generation by using a shader though!
Makes sense. Are you doing noise based modifications or like individual tile? If just noise then you could have the noise inputs as uniforms. If tiles it could still be done but streaming tiles all the time to the GPU sounds like a pain
by casting the ray from the mouse (sun) to the point, the sun becomes like a point light. to have a parallel light (more like the sun), change line 21 in the fragment shader to ```vec3 stepDir = (sunPos*2.0-1.0)/STEPS;```
I had that thought after I posted the video that the name "sun" might be a bit of a mis-representation hahaha
Thanks for the comment!
@@BarneyCodesgreat video by the way, i like your content on shaders in p5js! 👍
Great video! You could get rid of the blobbiness by jittering around your sampling point. This will also make the shadow look smoother.
Thanks for the suggestion! I've been messing around with it a bit more and I think at somepoint it comes down to a limitation of using a texture for the height information. I'm now looking into either defining the terrain with SDFs or some other continuous function which will give me nice, smooth shadows!
or draw shadow like a layer and blur that layer ? maybe it will solve it ?
I wonder if you could use interactive horizon mapping for this. It's a technique back from 2000 meant to produce self-shadowing on bump-mapped surfaces. I think it'll be less accurate, but also much faster.
I haven't heard of interactive horizon mapping before, it sounds really interesting, I'll check it out! Thanks for the comment!
Couldent you prebake this by having a normal map with the most extreme angles that the sun can be seen from encoded in color so that if the angle from the point to the sun is too extreme you turn shadow it
You would need 1 channel for the most western angle the sun can be seen from, one for the most eastern, then the same for north/south
im very tired when typing this so forgive me if im wrong
I was wondering about something similar to this, and then you would lerp between the four directions I suppose? I'll have to try it out, thanks for the comment!
@@BarneyCodes no probelm, soft shadows might be cheap too because you can use an esse function near the efges instead of a on off shadow
Hey I know this is a bit old by now, but maybe step per pixel using Bressenhams (not sure about spelling) line drawing algorithm and pass the image resolution to the shader
Great suggestion, I can definitely improve how I'm taking steps!
Could you initialize a "light height" texture to the terrain, then propagate shadows along the direction of light rays using a jump flood algorithm (requiring multiple shader passes to generate a new light height texture each time), then darken any terrain lower than the light height texture?
Sounds like it could work, I'm not sure how fast it would be given it would take multiple shader passes though?
@@BarneyCodes "The Quest for Very Wide Outlines" reports quite fast performance for a similar task (drawing outlines around objects, rather than shadows) but the algorithm should transfer. I don't know how to write multi-pass shaders though.
@@nyanpasu64 Interesting, I'll take a look!
how about a depth map from the light source with a spherical projection?
please correct me if i'm wrong, but can't you do the "shadow casting" the other way around ? something like this maybe:
first you create a grid of coordinates based on the height of the map on each point (more points, better shadow resolution?) and you sort them by height
then you create a vector from the sun to the highest point in your map (which is always illuminated) and mark it as done
once you have that vector, you can follow it down until it reaches the ground again, marking all points "below" that as shaded
then you just filter your coordinates array, removing all points either shaded or illuminated, and repeat.
i think this is something similar to what some pathfinding algorithms do, but i've never done anything even remotely related to shaders or graphics, so pardon my ignorance.
also, this is really interesting, and now i wanna try it for myself. if someone spots a flaw with my logic, please let me know before i lose whats left of my hair
I like this approach a lot! But unfortunately I don't think it will work well in a shader. Basically what a fragment shader does is figure out what colour each pixel should be, and it does this by running the code for each pixel all at the same time, so it's very hard to share data between fragments/pixels.
I think you're approach would work pretty well on the CPU though!
@@BarneyCodes ah, i see! i knew it was too good to be true :D
Thanks so much for all the support and suggestions!
If you'd like to see what else I'm working on, it would be great if you could wishlist my game Star Mining Co. on Steam! s.team/a/2584800/
Maybe you could generate a distance field to increace gpu utilization at the cost of memory. That would redecue the needed steps for each ray.
Id LOVE to see you generating the normals from the height
I'm trying this at the moment, I'll make a video about it when I've got it working!
there are methods for getting an exact solution that is much faster, you should use bisection or ray marching using a signed distance field
I'll have a look into bisection! As for using an SDF, I can't seem to find a good method for generating one based on a heightmap, otherwise I'd definitely use one!
To try to remove the artefacts you could maybe dynamically change the step size (the closer the point to the ray, the smaller the steps are) just like ray marching !
What would be amazing is to try and figure out some way to convert the heightmap into an SDF so that proper ray marching techniques could be used! In it's heightmap form though it's a bit tricky to figure out what a safe step size is (while staying performant!)
Thanks for the comment!
@@BarneyCodes Ah you're probably right, it would be quite expensive to calculate a safe size for each steps, it's a very interesting subject, I going to give it a try !
Really nice video btw, well done and thank you !
I wonder if there is a way to apply raymarching to this. That should be more efficient than a fixed step length
I'm sure there is, and a lot of people have suggested using mipmaps as a quad tree to help take larger steps when possible.
I'd really love to create some method of generating an SDF from a height map so then you could do some proper ray marching
Could this be used to generate Self-Shadowing Bumpmaps like Valve uses in their games? Basically, you generate 3 shadows at 120 degree intervals, represented by a red, green, and blue shadow on the image, where the intensity of each shadow represents how high the sun has to be before that pixel is no longer in shadow.
I haven't heard of that technique before but it sounds really interesting! I'm guessing you'd interpolate between the colours for angles between the 120 degree intervals?
I certainly think you could do something like that with this shader with a bit of modification!
Awesome video!
General Kenobi...
Thanks, glad you liked it!
i'm not sure if this would work, but instead of simply making small steps to check the vector, use DDA raycasting, it might improve performance as well.
I'll look into it, thanks for the comment!
this is gonna be a great channel
this channel is bouta blow up i can feel it in my kidneys
Hahaha thanks, hopefully your kidneys are telling the truth and aren't trying to tell you something else...
@@BarneyCodes my kidneys whisper many things to me. they’re never wrong.
there is website which name is shademap, I wonder how it makes the sine shape on larger scale and managing render shadow of mountains, when you scroll out you can see what I mean, could you explain how?
It honestly looks like it would use a similar technique to the one I show in this video. I would assume they have access to the height data of the region of the map they are showing and they can use that to do the ray casting to see if an area is in shadow or not!
This is pretty interesting!
This being similar to a 3d raymarching algorithm you can take advantage of it's low hanging fruit enhancements like rendering the shadows penumbra making it more realistic ❤
That sounds really interesting, I'll look into it, thanks!
Very nice video and nice visuals :)
Thanks so much!
Ok and now I want an Voxelspace RTS Pilot-Sim Hybrid with realtime lighting.
That sounds awesome hahaha I kinda want to do something with this and take it further so maybe that's a direction I should explore!
to remove that step issue, add some blue noise my dude
Great idea, thanks!
What software is used to execute this code? I've seen different options, but it's never said what is used in this kind of video :'(
In this video I'm using P5js which is a JavaScript librbary that gives really easy access to the canvas and WebGL. The shader itself is written in GLSL. Hope that clears things up!
maybe blur the pixels that have shadow to reduce the artifacts? idk if its possible, im a shader graph user not shader code writer
I think it's definitely possible, especially if I keep the shadows on a different layer! Thanks for the comment!
congrats and thanks for the video! your explanations are very good! just noticed that the background music is a bit too loud
Thanks for the feedback! I'll fix it for the next one!
you're welcome, man! thanks for the class
Wonderful video. Such a good concept.
Ive built this in unity. Using compute shader to generate the height and color map. Just not able to get the shadows working. Not sure if i should pass the mouse position as texture coordinates or uv. Please help me.
Glad you liked it! I haven't used Unity so I'm not 100% sure, but there should be a way for you to set variables in your shader from your script. In this case you'll probably want to use a vector with the mouse coordinates in the x and y. From a bit of googling it looks like there is a SetVectorArray() function which looks like it lets you set a vector array in your shader.
Hope that helps!
Thank you. That isn't the problem. I'm not sure if the vector from the point to the "sun" is in texture coordinates or world space coordinates. Because of this the iteration for the shadows isn't giving me consistent pixel values. Anyways, I'll keep trying and I'll let you know if I've cracked it. Thanks for the video. Pretty awesome.
@raghavsuriyashekar Oh I see! Sorry! In my case 1pixel = 1unit so the texture coordinate and world coordinate are the same thing!
Yeah I need to find the conversation factor and I should be able to recreate it
Hey!
Small update, I got it working!! I was trying to do this in the compute shader itself. That was my mistake. I didn't even notice that it was not in a fragment shader. Looks wonderful. Thank you so much ❤️🔥🤙
Looks great!
Thanks!
Really helpful video, thanks!!
Glad you found it useful!
Turn the sun from a point-like source to an area (or even approximate with a 3x3 "circle") and you'll improve the aliased shadows and get softer shadowing.
Loved the video! The music was a bit loud, kind of difficult to hear you but visuals were super solid.
Thank you! Very helpful feedback, I haven't really used music in my videos much before so still getting the hang of it, hopefully will be better next time!
@@BarneyCodes I usually just keep an eye on the audio levels and keep the music at around half (or less) of the average db level for mic, you'll get a feel for it but other than that, it's a fantastic video!
@@FirstCrimson Great tip, thanks so much!
what you could do is turn the heightmap into a normal map, use that to calcualte lighting, and then ignore all the regions that that algorithm puts in shadow
Since publishing the video I did try this and it definitely seemed to help, but the normal map unfortunately suffers from the same issue of the data it's using is discrete (since the height map is an image) so I get some artifacts in the normal, just like I was getting with the original shadows
I feel like ray-marching could greatly improve the performance, but I'm not sure how you'd calculate the minimum distance you can travel. (that's what I did in my 3d raycaster :D)
If I figure it out, I'll edit this comment.
I've been trying to figure this out as well, I think it would not only be a massive performance boost, but should reduce a lot of the artefacts too.
A few people have suggested using mipmap levels as a sort of quadtree, but I can see how, in WEBGL, to set up the mipmaps to use the MAX of a neighbour hood rather than the average, which is what would be needed to get it to work!
I was wondering if there would be a way to use an FFT to break the height map into a series of frequencies and using that, but I'm not sure how that would look in 2D and how to use that in the GPU for more accurate distance calculations.
My other idea was to try and approximate the shape of the height map with a series of spheres that would then be very easy to do an SDF on, but I can't think of a good way to approximate it!
If you've got any thoughts I'd love to hear them!
pretty cute shader. Welcome to integration functions. There's loads of complicated ways of improving this.
One is power spacing so the futher away from the source you are the larger the step, and the second is doing quasiy sphere tracing where you use the fact that your heightmap is smooth to guess if you are close to the ground and do more samples when the terrain height get's closer too current sample height.
This is really complicated solving from scatch and I recomend using Desmos or the like to write you math first.
Thanks for the tips! I'll have to do some more research into the areas you mentioned
Great video. Subbed.
Thanks so much!
Oh my god! Loop and conditional exit from a loop in a shader!
hat's so expensive!
I know 😅 but you kinda have to if you want to do any sort of ray marching. I had a maximum number of steps to be safe though!
AWESome!
Thanks so much!
@@BarneyCodes Thank You! You not only made video with easy to understanding and interesting demonstration, but share full code! It's rarely seen nowadays. I am additionally gratefull for simplest noise-generated terrain example i ever seen. Every topic about terrain generation includes 'actaves', 'amplitude' and 'frequency', which makes my brain instantly evaporate. In your example less features, but still looks great!
Thank you so much, that's very kind!
I think things like procedural generation can get as complex or as simple as you like. Definitely for more realistic terrain you'll need to start diving into those things, but for the basics it's not too necessary.
In case you're interested, octaves, amplitudes and frequencies are all just used to layer noise together. Each layer is called an "octave" and each octave has double the frequency of the previous one, but a lower amplitude. A higher frequency means that the noise is more zoomed-out looking, so the hills it creates will be closer together, but to make that not overwhelm the terrain, the amplitude is turned down, which just means that the close together hills are not as tall as the ones of the previous octave. By adding together these different noise layers you end up with terrain that has large hills and valleys, but those hills and valleys also have some variation to them instead of just being smooth.
Adding more octaves adds more detail to the terrain!
Hopefully that wasn't too mind-evaporating! It can definitely be a bit difficult to conceptualise, but I'm sure it'll make sense with some practice!
heres something i learned about shaders:
staw away from using gray colors to represent height.
because at most you only get 255 possible height levels, which might be way too little depending on your needs.
Sorry I am nubies, I see rtx3090 there so is it heavier or not?
This would work in 2d but probably not 3d: turn heightmap into a math formula (eg sum of sines) then do some magic to fin the range where formula A (ray line) > formula B (height)
oh cosine decomposition, I like it, it's not super important that the shape of the height-map is perfectly preserved so the lossy nature of it isn't a big deal
Really cool 🆒 Demo
Thank you!
0:20 how to represent a higher dimension (3D) with only 2.
can I give you some advice? the music is way too loud.
Thanks for the feedback, I'll fix that for the next video!
Great video! Will say the background music was a bit too loud and distracting tho
Thanks for the comment and the feedback! Will be fixed in future videos
Interesting. I figured you'd use a normal map to attenuate the shadows
I'm thinking I'll try generating the normals from the heightmap in the next video!
I usually complain a lot about UA-cam and their stupid fucking algorythms n that but I'm ngl, the past few weeks I've been getting some awesome channels.
Suggestion: The music is a bit loud and makes it harder to hear (even more so for those of us who have overstimulus problems); Content: Stellar :D!
Yea sorry, I absolutely bungled it on this one 😅 should be fixed in future videos, appreciate the feedback! And thanks, glad you enjoyed it!
@@BarneyCodes Lolz that was *very* responsive of you - I made my comment like 2 minutes ago!!
I plead the fifth...😂
perfect videoto enjoy withmylunchtime burrito
Interesting !
Would appreciate lowering the background music, doesn't help.
Noted, sorry about that!
Great video if the music volume would be lower.
Thanks for the feedback!
great video, but I found the music loud and distracting for your voice tone.
Thanks for the feedback! I'll make sure to fix it for the next one!
Very cool - but bg music is major distraction.
Thanks, yeah haha I've learnt my lesson about the music! Thanks for the feedback :)
Rimworld does this to show the time of day - watch any rimworld video.