Yeah, I called it voronoi lookup table later in the video for that reason (also because it can be abbreviated to VoLT, which is nice). Still, the title and thumbnail had to contain "Voronoi Diagram" so that people knew the topic.
If all you want to do is create a voronoi texture, there's actually an even faster way to do it on the GPU than the jump flooding algorithm. You can use rasterization, and render colored cones with their tips at each of your points. The cones will overlap and depth testing means the nearest surface wins - cones will be taller closer to the tip, so the cone with the frontmost surface will be the one that corresponds to the nearest point. That's already VERY fast, but further optimizations could be made like using an occlusion culling algorithm - and because you're just rendering meshes, the same algorithms that work for regular rendering also work for the cones. You can also add distances to the nearest point really easily - it's just the depth buffer. There are some edge cases like when the points are farther apart than the width of your cones at their bases, but typically it's good enough for a lot of applications.
You would also get into some trouble because of the geometry of the cones (they are not perfect cones, but triangle approximations). But nice idea! I can see that work... but also even more complicated setup than JFA I think. You'll also need a custom shader for the cones.
@eGames_blenderfanyeah, but I remember there being a few blog posts/demos of people who did it this way and it seemed to work pretty well. One guy did it with geometry, but another guy did it with quads that just wrote depth out (either there was a fragment shader that just did distance to a point or a texture that did the same) and that one wouldn't any issues with a triangle approximation (but did have huuuge overdraw problems). Though in practice the geometry approach seemed to work perfectly fine, especially since you're just instancing the same cone a bunch of times you can make it pretty high poly without much consequence. As for a custom shader it's about as trivial as it gets, you literally only really need visibility. Pretty much a one-liner vertex shader and maybe a few lines fragment shader. Can't say if it's more/less complicated than JFA since I haven't written code for it myself yet tho.
@@MustacheMerlinUnity does not have cones by default, so you would have to create them in code first, so this is why I say the setup is more complicated. You then also need to place them correctly etc. And then activate / deactivate them correctly. Complicated is maybe the wrong word. No step would be particularly difficult, but it would take a while (and explaining each step in a video would take even longer). But like I said, I can see it work for most cases and I think it is a very interesting solution (the triangulation would just be a "problem" or rather inaccurate if you had specific distributions of points. In all other cases the error would be miniscule and probably on par with the error you have from using a grid) However, I just want to say, that the creation of the texture does not have to be that fast anyway, because you would use it statically. Or rather: You should not use voronoi textures / diagrams with moving objects in the first place that would require such a performance.
Interesting video. I tend to use octrees for 3d work - but Voronois, being a lookup (after the initial calculations) make them interesting too. Food for thought...
Yes, they both serve their purpose. Although for 3D, arguably voronoi is less useful because memory becomes an issue. But it depends on the problem and the required accuracy
No, because how would you find the closest grid cell that contains an asteroid without searching? And you also might have to search multiple cells, because you do not know where an asteroid is within a cell... and there could be multiple asteroids within a cell.... etc.
@@ParableGames_blenderfan you pre-process the grid to put a pointer to the nearest asteroid in the cell data. If you have equidistant asteroids then store multiple.
@eGames_blenderfanwell you only have to go through multiple entries if there are multiple asteroid equidistant to the cell, which I believe your soltuion doesn't handle? And it's faster because it's just a coarser version of your texture lookup, significantly smaller and more likely to fit in cache.
@@cfehunter How is a texture not a grid as well? You could change the texture resolution if you want a coarser version... and no, your version would have to do these things also when asteroids are not equidistant (because multiple asteroids can be in a cell). The same thing would happen for voronoi if the texture resolution is too low.
True, I also mention it in the video. But it is not necessarily always faster, it depends on the table / texture size and the number of sites. For a small number of sites, this method will be faster. But the true reason I did not do it in the video is that it is harder to setup and would require a little bit more explaining.
The O(1) performance comes because you are actually using a grid data structure (your texture) that you have populated from the voronoi data structure. It's good to know that you could keep around the original polygons if you wanted to keep the original precision. I disagree when you say that a KD-Tree or Quadtree will NEVER beat a Voronoi diagram - you're comparing your grid-lookup O(1) implementation, which isn't doing any voronoi calculations at runtime, and while I agree that your O(1) grid is asymptotically better than a O(lg n) tree structure, that's not the same as "never" - if I needed to have a small number of moving obstacles, I can imagine that a tree might outperform generating a grid as the obstacles move.
You do not disagree with me, as it is the same thing I said in the video haha. Yes, voronoi diagrams are slower, by far, if you have moving objects, like mentioned at the end.
@@ParableGames_blenderfan I agree that you mentioned moving objects, I'm specifically pointing to 13:47 where you say that trees will "never beat" a grid lookup, which is not how big-O notation works. You then say "unbeatable in terms of algorithmic complexity", which feels like a slightly different claim, more academic, and not necessarily useful when deciding what I should use in my game. Another grid-based approach that I've been using in a lot of my projects is Bridson's algorithm, which is a different way of storing information in a grid and getting O(1) lookups for finding neighbors within a pre-determined maximum radius.
Isn't spatial hashing strictly better than using voronoi? It also has amortized constant time lookups, can easily support moving objects and generalizes to any number of dimensions
No, as you can have many objects in a cell you would have to iterate through. And if you make the cells to small, then you lose accuracy as objects start to be overlapping cells / be in multiple cells. Also, finding the nearest neighbor will require you to potentially search multiple cells. Also, spatial hashing supports point data, but will have problems for other shapes (which voronoi can handle) Voronoi also generalize to higher dimensions. So, no it is not strictly better, but an alternative that is useful in some cases. Especially as it is cheaper to construct. Pros and Cons as always.
@@ParableGames_blenderfan I don't see how this is a clear win for your voronoi method versus spatial hashing. Voronoi requires a grid that is finer than the smallest collision object, while spatial hashing requires a grid that is coarser than the biggest collision object. The spatial hashing algorithm thus always beats you on space usage, and on scenes with objects of approximately the same size (like the one in the video), both will have a constant lookup time (although for voronoi the constant is lower since it's just one array lookup versus 4 or 9 hashmap lookups). In an extreme case, if the lookup table for the voronoi method is too big, then the spatial hashing method might beat it by not causing as many cache misses. The voronoi method also has some serious drawbacks: it can't handle moving objects (like you said), and it can't accurately handle collisions involving intersecting objects (here if two asteroids partially intersect and a spaceship comes at the exact right angle, the tip of the spaceship won't register the collision). I'd say it's a niche optimization, for when your scene has big, well-separated and static collision objects.
The issue is that this works well on a plane, but does not expand nicely to three dimensions. It is not suitable for dynamic scenes as you are using asynchronous GPU so the CPU is looking at the voronoi diagram coming from the bus from a frame or multiple frames in the past. Synchronous may even be slower than the naive solution. It's a niche solution that would definitely be useful for boids behaviors in 2d games or even RTS games using the GPU to make distance fields around geometry to be used for generating pathfinding flowfields. It's not really a generic solution however. You could technically take it to 3D by doing orthographic raymarching with a lower resolution grid and some interpolation it could be gotten to work.
It is indeed not suitable for non-static objects (moving objects)... which is also what I said in the video 🤣 That does not mean it is a niche solution. You can not only use it for Boids: Finding the closest building in the world, the closest item lying around in the world, the closest tower in a TD game etc. It just highly depends on the games you are working on, on how useful it is (and how well you can precompute things and the scale you are operating in) As for the raymarching idea: That works only if you are not using indices but the position (but using indices was the point in the video - you can use them in other shaders then as well for further computations, you don't have to copy back to the CPU - asynchronous or synchronous). Indices do not work as for example interpolating 1 and 10 would give you all values 2-9 as well (and those objects could be anywhere)
@@ParableGames_blenderfan I think we have miscommunicated. I did also mention use cases for RTS and other games that work from an underlying 2d grid for behaviors like entity picking or so. From what I understood, the basis of your technique is to use the GPU for fast spatial partition by taking in Dividing nodes of the graph to build the Voronoi into the GPU (Asteroid positions) and rendering out a voronoi with e.g the index of the asteroid encoded into the color channel with a small format like single color 16bit pixel format as a 2d texture. I suggested that it can be extended to three dimensions with raymarching and 3d texture output. You are correct that I was wrong about the interpolation, if the entity index is being interpolated this creates fake indexes or yes e.g you gave 1 vs 10 spatial boundary giving some nonsense like 2..9 this is my bad. Without interpolation can still have a lower resolution of spatial grid e.g 10 world units buckets to map from 1:1 to 1:10 resolution. It is a cool video.
@@charactername263 It seems so 😅 Well, I am however not sure how much Raymarching would make sense (except for displaying the 3D Texture)... the technique for the indices can easily be extended to 3D by using 3D uv coords and calculating the distances in 3D (exactly the same code essentially, just 3D, assuming a static context). In a dynamic context, you would not really do raymarching because it would be more efficient to simply calculate the nearest neighbor brute force for each moving point. Btw. it is not too expensive to calculate 3D Voronoi in a static context (well, depends on the resolution of course), the real problem lies in the memory cost. An alternative, that takes a little bit more computation power for would be GPU KD-Tree NNS. These can also potentially be updated from the CPU-side (although not exactly cheap) and also are able to do kNNS (but that can become pretty expensive) But for a dynamic context I'd recommend spatial indexing on the GPU or similar techniques, not Voronoi or KD-Trees at all, as this would also enable you to do other queries ("sphere casts", "box casts" - and equivalent)😁Maybe I make a video about that too. Anyway, thanks for watching!
One little problem, at 60 frames per second you render at 16ms, you have 0.600 ms... you are way lower than the average 60 fps/ms. the problem you are creating now is, useless frame generation which makes the GPU and CPU work in vain to keep up the MS. And its very simple to look at performance, before and after, just look at ur GPU/CPU usage in task manager or other monitoring software.
This is totally crap advice. Of course, someone who uses Unity completely disregards cache performance and memory, then makes up a bunch of random stuff about how the 'algorithmic complexity' is unbeatable. Never clicking on one of these stupid youtube videos again, I always expect something actually practical but it's always a false teacher wasting everyone's time.
![[Gimme DOTS Geometry]: Delaunay Triangulation](/img/n.gif)
Good work Agent 47, you distracted the targets well
I see the resemblance 🤣
An Agent 47 that hacks. That makes him even more dangerous
This gave me an idea.
If generated texture fills each cell with signed distance field you also get information how far you are from asteroid.
Indeed, and that is what is called a generalized voronoi diagram. Altough those are not explicitly with SDFs.
Suicidal spaceships constantly aiming to crash into the nearest asteroid.
* No animals were harmed in the production of this video 🤣
I would refer to this as a "voronoi buffer" as a diagram is something for humans to look at to understand a topic.
Yeah, I called it voronoi lookup table later in the video for that reason (also because it can be abbreviated to VoLT, which is nice). Still, the title and thumbnail had to contain "Voronoi Diagram" so that people knew the topic.
If all you want to do is create a voronoi texture, there's actually an even faster way to do it on the GPU than the jump flooding algorithm. You can use rasterization, and render colored cones with their tips at each of your points. The cones will overlap and depth testing means the nearest surface wins - cones will be taller closer to the tip, so the cone with the frontmost surface will be the one that corresponds to the nearest point.
That's already VERY fast, but further optimizations could be made like using an occlusion culling algorithm - and because you're just rendering meshes, the same algorithms that work for regular rendering also work for the cones.
You can also add distances to the nearest point really easily - it's just the depth buffer.
There are some edge cases like when the points are farther apart than the width of your cones at their bases, but typically it's good enough for a lot of applications.
You would also get into some trouble because of the geometry of the cones (they are not perfect cones, but triangle approximations).
But nice idea! I can see that work... but also even more complicated setup than JFA I think. You'll also need a custom shader for the cones.
@eGames_blenderfanyeah, but I remember there being a few blog posts/demos of people who did it this way and it seemed to work pretty well. One guy did it with geometry, but another guy did it with quads that just wrote depth out (either there was a fragment shader that just did distance to a point or a texture that did the same) and that one wouldn't any issues with a triangle approximation (but did have huuuge overdraw problems). Though in practice the geometry approach seemed to work perfectly fine, especially since you're just instancing the same cone a bunch of times you can make it pretty high poly without much consequence.
As for a custom shader it's about as trivial as it gets, you literally only really need visibility. Pretty much a one-liner vertex shader and maybe a few lines fragment shader.
Can't say if it's more/less complicated than JFA since I haven't written code for it myself yet tho.
@@MustacheMerlinUnity does not have cones by default, so you would have to create them in code first, so this is why I say the setup is more complicated.
You then also need to place them correctly etc. And then activate / deactivate them correctly.
Complicated is maybe the wrong word. No step would be particularly difficult, but it would take a while (and explaining each step in a video would take even longer).
But like I said, I can see it work for most cases and I think it is a very interesting solution (the triangulation would just be a "problem" or rather inaccurate if you had specific distributions of points. In all other cases the error would be miniscule and probably on par with the error you have from using a grid)
However, I just want to say, that the creation of the texture does not have to be that fast anyway, because you would use it statically. Or rather: You should not use voronoi textures / diagrams with moving objects in the first place that would require such a performance.
Interesting video. I tend to use octrees for 3d work - but Voronois, being a lookup (after the initial calculations) make them interesting too. Food for thought...
Yes, they both serve their purpose. Although for 3D, arguably voronoi is less useful because memory becomes an issue. But it depends on the problem and the required accuracy
oh I like how you use lerp to get the position instead of annoyingly calculating it out, now I feel dumb
You live and learn. Next time someone else might feel dumb because you are using lerp now too ^^
amazing video, thanks!
Great explanations, good stuff :)
Thanks!
awesome as always, i bought your gimme dots geometry and its amazing
Thank you so, so much!
neat... i want to call it a binary distance field.. a 1-bit distance field opposed to an SDF. good content, well explained
You are a legend
Maybe it's just a quirk of the example, but wouldn't this be significantly cheaper and faster if you just used an appropriately sized grid?
No, because how would you find the closest grid cell that contains an asteroid without searching? And you also might have to search multiple cells, because you do not know where an asteroid is within a cell... and there could be multiple asteroids within a cell.... etc.
@@ParableGames_blenderfan you pre-process the grid to put a pointer to the nearest asteroid in the cell data. If you have equidistant asteroids then store multiple.
@@cfehunterYes, and how would that be faster than a lookup if you have to go through multiple entries and cells?
@eGames_blenderfanwell you only have to go through multiple entries if there are multiple asteroid equidistant to the cell, which I believe your soltuion doesn't handle?
And it's faster because it's just a coarser version of your texture lookup, significantly smaller and more likely to fit in cache.
@@cfehunter How is a texture not a grid as well? You could change the texture resolution if you want a coarser version... and no, your version would have to do these things also when asteroids are not equidistant (because multiple asteroids can be in a cell). The same thing would happen for voronoi if the texture resolution is too low.
You can use the jumpflood algorithm to speedup the generation of the Voronoi Diagram
True, I also mention it in the video. But it is not necessarily always faster, it depends on the table / texture size and the number of sites. For a small number of sites, this method will be faster.
But the true reason I did not do it in the video is that it is harder to setup and would require a little bit more explaining.
The O(1) performance comes because you are actually using a grid data structure (your texture) that you have populated from the voronoi data structure. It's good to know that you could keep around the original polygons if you wanted to keep the original precision.
I disagree when you say that a KD-Tree or Quadtree will NEVER beat a Voronoi diagram - you're comparing your grid-lookup O(1) implementation, which isn't doing any voronoi calculations at runtime, and while I agree that your O(1) grid is asymptotically better than a O(lg n) tree structure, that's not the same as "never" - if I needed to have a small number of moving obstacles, I can imagine that a tree might outperform generating a grid as the obstacles move.
You do not disagree with me, as it is the same thing I said in the video haha. Yes, voronoi diagrams are slower, by far, if you have moving objects, like mentioned at the end.
@@ParableGames_blenderfan I agree that you mentioned moving objects, I'm specifically pointing to 13:47 where you say that trees will "never beat" a grid lookup, which is not how big-O notation works.
You then say "unbeatable in terms of algorithmic complexity", which feels like a slightly different claim, more academic, and not necessarily useful when deciding what I should use in my game.
Another grid-based approach that I've been using in a lot of my projects is Bridson's algorithm, which is a different way of storing information in a grid and getting O(1) lookups for finding neighbors within a pre-determined maximum radius.
@@DaveLeCompte I say it right in the next sentence in 13:58 how when quadtrees etc. are better 😁
Isn't spatial hashing strictly better than using voronoi? It also has amortized constant time lookups, can easily support moving objects and generalizes to any number of dimensions
No, as you can have many objects in a cell you would have to iterate through. And if you make the cells to small, then you lose accuracy as objects start to be overlapping cells / be in multiple cells.
Also, finding the nearest neighbor will require you to potentially search multiple cells.
Also, spatial hashing supports point data, but will have problems for other shapes (which voronoi can handle)
Voronoi also generalize to higher dimensions.
So, no it is not strictly better, but an alternative that is useful in some cases. Especially as it is cheaper to construct.
Pros and Cons as always.
@@ParableGames_blenderfan
I don't see how this is a clear win for your voronoi method versus spatial hashing. Voronoi requires a grid that is finer than the smallest collision object, while spatial hashing requires a grid that is coarser than the biggest collision object.
The spatial hashing algorithm thus always beats you on space usage, and on scenes with objects of approximately the same size (like the one in the video), both will have a constant lookup time (although for voronoi the constant is lower since it's just one array lookup versus 4 or 9 hashmap lookups).
In an extreme case, if the lookup table for the voronoi method is too big, then the spatial hashing method might beat it by not causing as many cache misses.
The voronoi method also has some serious drawbacks: it can't handle moving objects (like you said), and it can't accurately handle collisions involving intersecting objects (here if two asteroids partially intersect and a spaceship comes at the exact right angle, the tip of the spaceship won't register the collision).
I'd say it's a niche optimization, for when your scene has big, well-separated and static collision objects.
The issue is that this works well on a plane, but does not expand nicely to three dimensions. It is not suitable for dynamic scenes as you are using asynchronous GPU so the CPU is looking at the voronoi diagram coming from the bus from a frame or multiple frames in the past. Synchronous may even be slower than the naive solution.
It's a niche solution that would definitely be useful for boids behaviors in 2d games or even RTS games using the GPU to make distance fields around geometry to be used for generating pathfinding flowfields. It's not really a generic solution however.
You could technically take it to 3D by doing orthographic raymarching with a lower resolution grid and some interpolation it could be gotten to work.
It is indeed not suitable for non-static objects (moving objects)... which is also what I said in the video 🤣
That does not mean it is a niche solution. You can not only use it for Boids: Finding the closest building in the world, the closest item lying around in the world, the closest tower in a TD game etc. It just highly depends on the games you are working on, on how useful it is (and how well you can precompute things and the scale you are operating in)
As for the raymarching idea: That works only if you are not using indices but the position (but using indices was the point in the video - you can use them in other shaders then as well for further computations, you don't have to copy back to the CPU - asynchronous or synchronous). Indices do not work as for example interpolating 1 and 10 would give you all values 2-9 as well (and those objects could be anywhere)
@@ParableGames_blenderfan I think we have miscommunicated. I did also mention use cases for RTS and other games that work from an underlying 2d grid for behaviors like entity picking or so.
From what I understood, the basis of your technique is to use the GPU for fast spatial partition by taking in Dividing nodes of the graph to build the Voronoi into the GPU (Asteroid positions) and rendering out a voronoi with e.g the index of the asteroid encoded into the color channel with a small format like single color 16bit pixel format as a 2d texture.
I suggested that it can be extended to three dimensions with raymarching and 3d texture output. You are correct that I was wrong about the interpolation, if the entity index is being interpolated this creates fake indexes or yes e.g you gave 1 vs 10 spatial boundary giving some nonsense like 2..9 this is my bad.
Without interpolation can still have a lower resolution of spatial grid e.g 10 world units buckets to map from 1:1 to 1:10 resolution.
It is a cool video.
@@charactername263 It seems so 😅
Well, I am however not sure how much Raymarching would make sense (except for displaying the 3D Texture)... the technique for the indices can easily be extended to 3D by using 3D uv coords and calculating the distances in 3D (exactly the same code essentially, just 3D, assuming a static context). In a dynamic context, you would not really do raymarching because it would be more efficient to simply calculate the nearest neighbor brute force for each moving point.
Btw. it is not too expensive to calculate 3D Voronoi in a static context (well, depends on the resolution of course), the real problem lies in the memory cost. An alternative, that takes a little bit more computation power for would be GPU KD-Tree NNS. These can also potentially be updated from the CPU-side (although not exactly cheap) and also are able to do kNNS (but that can become pretty expensive)
But for a dynamic context I'd recommend spatial indexing on the GPU or similar techniques, not Voronoi or KD-Trees at all, as this would also enable you to do other queries ("sphere casts", "box casts" - and equivalent)😁Maybe I make a video about that too.
Anyway, thanks for watching!
The Godot community can't agree on how to pronounce "Godot", so you can say pretty much anything and it's arguably correct. :)
I will pronounce it like Godot in Berserk then
Don't worry about mispronouncing things, we all do.
Next time I use text-to-speech, then my hands are clean 🤣
One little problem, at 60 frames per second you render at 16ms, you have 0.600 ms... you are way lower than the average 60 fps/ms. the problem you are creating now is, useless frame generation which makes the GPU and CPU work in vain to keep up the MS. And its very simple to look at performance, before and after, just look at ur GPU/CPU usage in task manager or other monitoring software.
I explain it later in the video that I only measure the time it takes for the spaceships to find the closest asteroids. The total frame time is longer
This is totally crap advice. Of course, someone who uses Unity completely disregards cache performance and memory, then makes up a bunch of random stuff about how the 'algorithmic complexity' is unbeatable. Never clicking on one of these stupid youtube videos again, I always expect something actually practical but it's always a false teacher wasting everyone's time.
I have regarded it, you just didn't watch the video until the end 🤣
5:27