Super Fast Ray Casting in Tiled Worlds using DDA
Vložit
- čas přidán 27. 02. 2021
- In this video I look at how the "traditional OLC" method of raycasting in various videos is in fact terrible, and look at the more intelligent DDA algorithm which can significantly (orders of magnitude) be more effective at determining ray length in tile or voxel based worlds.
Source: github.com/OneLoneCoder/Javid...
Demo: community.onelonecoder.com/me...
Also: lodev.org/cgtutor/raycasting....
Patreon: / javidx9
CZcams: / javidx9
/ javidx9extra
Discord: / discord
Twitter: / javidx9
Twitch: / javidx9
GitHub: www.github.com/onelonecoder
Homepage: www.onelonecoder.com - Věda a technologie
"C for cimplicity"
C for complicated.
@@deleted_handle C for coping.
So far so good
that's literally THE article that i reed for learning raycasting
I think its one of the best resources out there certainly.
Me too lol
Me too
me too
Me too, years and years ago
I figured this out by myself while making a 2D platformer for a homework, and thought that its the stupidest solution possible, but now I'm kind of proud of myself
occams razor for you
Same thing !
But I did it for 3D, now that's a bit more stupid ...
@@antoninperonnet6138 well worry not you have aabb now implemented then!
Be proud. _I_ nudged Javi in this direction with one of my comments on his "code a DOOMlike engine as a Windows console app" video he made last year. _You_ made a working implementation, which takes more work.
EDIT: This one, czcams.com/video/xW8skO7MFYw/video.html
@9:06
its very difficult for me to get into perspective from math information
firstly ,
at first i thought when dx=1
dy/dx=dy which means the problem is solved...
but actually we are finding the distance not the gradient so we need to calculate that..
other thing that made me confuse
was from previous part
sin RayAngle would give unit vector which means the hypoteneus is 1 and x has some value (i.e EyeX)
the same is true for cos RayAngle which gives the y value to update (EyeY)
so in the previous video that diagonal is moved by 1 unit .. or maybe (0.1 unit)
but this time we want to move x or y direction so that we know what is hypoteneus distance
so does that mean we need to check whether sin RayAngle < cos RayAngle
or do we need to compare nTestX < nTestX
nTestX=playerX+distanceToWall*EyeX
nTestX=playerX+distanceToWall*EyeX
to know which direction to go whether in y direction or x direction?
i think we must compare nTestX < nTestY
I implemented this in Minecraft for my custom entity hitbox and motion system, it has allowed me to make physics-based movements for my mobs. It's really quite something.
is it faster than the raycasting api provided by spigot?
@@jaylawlmc1915 My implementation is in a data pack, so that is unlikely.
@@Dominexis oh interesting! i didnt know you could code things like raytracing into datapacks. thats cool
@@jaylawlmc1915 If you want to learn more, you could hop on my Discord server and we can discuss how it works. I'd love to share it. The link is in the description of every one of my videos.
That's amazing! I got into computer graphics in university and at that time we didn't visualize anything and concencrated mostly on the math aspects. I spent a few weeks in my semester break and coded a few computer graphic algorithms on my own. At the beginning it was really frustrating but then I really got into it and nowdays it is one of my favorite computer science topics. I wish they had teached us that beautiful subject like you did. It's super intuitive with a little bit of drawing. Thanks man. I really appreciate your great content!
Yeah, maths with a bit of sparkle goes a long way 🤣 Thanks Marc!
I don't know how to say that your tutorials are perfect. you are so patient in explaining things and I really love it. you are my hero in programming.
I have been looking for this exact solution for months as an aside to a voxel project I'm working on! I even used your A* algo for it (albeit heavily modified). Thanks for making such digestible content, it really helps beginner developers such as myself understand concepts that seem just a little out of reach :)
Before this, my raycaster was taking small little steps and it was SUUPER laggy. I was about to quit until I tried your method and it ran butter smooth! What a relief.
This video has been super helpful for me in implementing block selection in my Minecraft clone. I've tried twice to adapt the method to 3D and everything tends to work except when I aim down the planes made by any two axis. This second time I checked someone else's implementation of DDA and found a comment in their code where they note that truncating the ray origin into a vector of integers will have issues in the negative axis. Turns out this was exactly the source of my issue and now after applying a component-wise flooring everything works fine.
I’m just about to make a voxel raycast engine using oct-trees and sign distance functions, and was trying to think of how to do this. Thank you for the video.
Wow you helped me so much! I never really understood the DDA algorithm so I couldn't implement it into my C# raycasting engine. The way you explained it really helped and I've got it working with my engine now. The speed has improved greatly from about 11fps to 500fps. Thanks!
Probably can make it even faster using branchless version from shadertoy, and even then its possible to optimize it even further by doing early termination and applying mask without if statements etc etc, there many ways to implement it
Oh neat, just 12 hrs ago I posted a video of a wolfenstein-ish renderer using this raycasting method that I ported entirely into a compute shader
I'm glad you're putting this out now, the command prompt FPS was really neat but I was very dissatisfied with that raycasting method. You have a clear way of communicating and I appreciate that you code in a real language :P
Thanks for the video ! I started to look into DDA ray casting and found the article you've mentioned, but couldn't understand it. So I started to reverse-engineer the RayCastWorld extension of the PGE, but my implementation wasn't working properly. You've saving me lots of headache :)
heh yeah its a little different in RCW because it yields coordinate perfect wall planes, and is selective about the side of the tile hit.
Nice, this is how I learned Raycasting as a kid and subsequently programming as a whole from that project. I ended up incorporating everything I learned into that project in some way or another. Funny part is how you can manage to get this done in such a small amount of code yet in Turbo and Borland C++ the size of this project, even before I started adding a bunch of features was rather large in order to get it to run at a decent speed needing things like DMA pixel transfer, special video modes and screen buffers, Fixed point mathematics
ah cool, I used this method but in 3d for voxels recently.
Haha me too! I've got it to real-time raycasting for small scenes on CPU, but want to improve my algorithm before porting to GPU. There are some clever ways of exploiting progressive rendering, to skip empty areas, and some shadow caching tricks I want to explore first.
you definitely want some sort of accelerating structure to skip empty space instead of marching it. you can start with a simple octree raycasting and then go in the direction of SVO's that are far more efficient on big datasets (>1024^3)
@@Alexander_Sannikov I've tried using oct-trees, but this kind of optimized ray marching code is so efficient, that the overhead of navigating the tree is often more expensive than just "dumb" marching. Obviously this does depend on scene complexity & other factors. A mostly empty scene will always be faster with an oct tree. I'm thinking of using a '64-tree' in combination with a progressively rendered depth buffer. Render at low resolution, use the lowest depth value of adjacent pixels to inform a guaranteed voxel free frustum for that region of the render, Render at the next highest resolution, skipping those regions, etc...
@@benjaminmiller3620 for any two given algorithms, one of which has O(log(N)) complexity and the other one has O(N) comlexity, there exists M large enough so that for any N > M, the log-algorithm will be faster than the linear one. However, it also means that for any N < M it will be slower. Octree algorithms do have a significant constant hiding in that O()-notation that's why they will be slower on small datasets. However, there will always be a threshold in dataset size so that it'll be faster for datasets greater than that threshold.
That hidden constant in O(log N) also greatly depends on your implementation details. For example, if you're using pointers to store the octree, it's a no-go -- you need to store it flattened. Even something as simple as rearranging your tree breadth-first vs depth-first has no change from algorithmic point of view, but has drastic impact on cache coherency and overall performance.
I just wanna say thank you SO MUCH for this tutorial! You teach the topic so understandable and simple!
I made something similar for octrees some times ago. Glad to see how you would have done it
Such an excellent video! Hats off to you sir!
Using DDA to do longer jumps requires multiplication which is a slower operation than many adds, especially on older computers (and 8 bit computers dont even have multiplication) so adding might be just as fast as the only way to speed this up in such a CPU is by massive table lookups to do the multiplication often in a system that is low on memory. I have done a raycaster on a C64 but will look more into if I can use elements of DDA to speed it up even more, or if the multiplication tables will take too much space. But thanks for explaining the algorithm with such precision.
Fixed-point only requires addition and bitshifts IIRC in each loop iteration with the exception of a single multiplication and division outside the loop. A code snippet from my codebase which can rasterize over 1 billion projected 3D lines per second with the added cost of a hierarchical Z-Buffer depth test per pixel on the CPU (the code shown below is the simpler 2D version which accepts 2-vectors, but I use an extended version in 3D which accepts floating-point 3-vectors which then get converted into fixed-point within the function with the Z value interpolated at each step using bitshifts).
// Calls plot(x, y) for each pixel of a line drawn from p1 to p2 using fixed-point DDA.
template
void plot_line(Plot plot, Vec2i p1, Vec2i p2)
{
const Vec2i64 slen = p2 - p1;
constexpr int32_t sign[2] = {-1, 1};
const bool a_small = abs(slen.y) < abs(slen.x);
const bool a_large = !a_small;
const int64_t end_val = slen[a_large];
const int64_t step = sign[slen[a_large] >= 0];
const int64_t x_len = slen[a_large] * step;
const int64_t slope = div_nz(slen[a_small] > 32ll)};
plot((int32_t)pt[a_large], (int32_t)pt[a_small]);
}
}
Can use 32-bit instead with 16-bit shifts, or even 16-bit with 8-bit shifts, or 8-bit with 4-bit shifts depending on acceptable precision/range and hardware demands. 'div_nz' is just a function to perform division with a check to avoid division by zero, returning zero in that case. Not sure how well it'd perform on C64 with the single division and multiplication per line (not per step), but it's something I lean on heavily to rasterize wireframes on very high-resolution 3D meshes (millions of polygons each) in real-time and faster than the GPU can do it (at least consumer-grade NVIDIA and AMD GPUs are surprisingly slow to rasterize lines; I think because they actually convert each line to a triangle strip and rasterize them as triangles).
It'd need to be adapted a bit for raycasting to avoid possible ray leaks (the above doesn't plot any doubles as pixel artists call them) but the same fixed-point concept should apply to change the requirements for division and multiplication each iteration into bitshifts. I keep hearing that Bresenham is faster than DDA for line rasterization but I think that's assuming floating-point and not fixed-point. I've yet to find any Bresenham implementation beating this at least on today's hardware.
The explanation is crisp as always, I could go and implement right after the theory!
This speeds things up from the old "step a tiny amount" method by several orders of magnitude, I reckon. Incidentally, it's remarkably easy to replace the wall finding code from your "First Person Shooter" videos with this.
I think I even have enough cycles left to repeat the raycasting process a couple more times now, - I can have different tiles/blocks rendering above (or below) the "zero" height.
Also, I've tried Lode, Sage3D, Permadi and Vinibiavatti1's tutorials and while Vinibiavatti1's comes close, your tutorials are the only ones I've been able to follow and implement well and correctly.
Thank You Javid!
Now I'm off to make "RayCraft" (TM) 😀
I don't think you need to repeat the ray casting, just store more data in the ray (distance, block side, block height, block texture, maybe block array). If you do define different levels (in height) of blocks, I think you do need to to cast for each level.
@@PaulSpades You are correct; by the end I had the concept of cubes rather than walls and floors, so using a 3D array and walking each level was the way to go for me. But if the ground were just a heightmap, then yes, one cast for all levels would be more efficient.
Exactly what I needed for my roguelike game!
Best video ever on Raycasting really! I've finally understood it, all thanks to you!
I'd seen this before somewhere and was too lazy to look it up again :D
With the ol Voxel stuff this is invaluable! thank you.
I could have used this for my 2D game with rope bending mechanics. I went the "several small increments" route for checking collision of the rope with the tiles. It was veeeery complicated to keep it bug free.
I was just working on something with the PGE and I saw this pop up in my notifications. Glorious days!
lol thank you Robben, make sure you share your PGE adventures!
very good explanation of the concept of raycasting with dda algorithm, thank you by the way!
you precalculate the rise and run (you also calculate the *first* rise and run, as your position could be anywhere inside the square at first)
you set a variable to your X coordinate (call it "A")
in the loop:
--you get the Y coord of the next wall up
--you go right one square, and go up by the rise
--if you've crossed the Y coordinate of the next wall up:
----you increment "A" by the run
----do a wall check at (X - "A", Y = the Y coord of the next wall up)
--do a wall check at (X = current X pos, Y = current Y pos)
do this until you've found a wall
also flip some things to check other quadrants
also be careful with precision because rounding errors accumulate here
Niice! Just realized you can also use the same DDA algo to draw an antialiased line.
Fantastic video, thank you for doing this.
thank you I've used this to implement raycasting in my engine. I've tested it a lot and it's amazing what these magical 40 lines of code can do
Good video as always!
Once saw this being used for voxel tree traversal, had no idea what its called. Thank you.
You could talk about the raycasting technique used in doom or dukenuken, i think it would make a great video, honestly
So I've been working on a game engine and this was LITERALLY EXACTLY what I needed for one of the issues in my code. Massive legend.
Very nice explanation. Thanks.
Excellent video. I code my own games for fun every once in awhile and old school 2d is my bread and butter. Although, I never actually finish a game and learn more each time. Starting out with an ultima clone, to super mario, to megaman and eventually played with some ray casting. It amazes me how useful trig is for games.
you can generate a distance field in O(n) time and use that to skip tiles based on how close the nearest filled tile is.
thanks a lot, i really needed this video!
Found your channel from the procedural universe video. I'm very interested in your lessons now. When will we get a video on saving state in a procedural universe?
Since we are talking about straight lines we know that they have one constant angle to the x-axis and one constant angle to the y-axis. This means that for one ray you need to compute 1/cos(theta_x) and 1/cos(theta_y) only once and those are your increments in lengths of the line when we increment x and y by 1 respectively, no square roots needed since they are expensive to compute.
There's another tutorial that's been around for a while, like Lode's... though it recommends using pre-calculated look up tables for sin and cos... www.permadi.com/tutorial/raycast/rayc8.html
so no overhead of square roots
Thank you for the information.
Very thanks for this video! I gonna make some test's with this raycast method :P
Used this for my Minecraft clone and it's working FLAWLESSLY thank you!
Thanks much! this is useful!
Just Joined your channel to show my support for your awesome videos :)
Hey thanks Python++ 😄 much appreciated!
Note, you can use a very similar algorithm to implement exact time-step-less collision physics with AABBs and circles/spheres.
In fact, with just _one_ more little coordinate substitution, you can make the object's position an implicit value computed directly from the current time based on object data that only needs to be updated (and synchronized across threads!) when an object actually collides.
can you expands on how it could be used on AABBs? I know how it's aabb vs aabb is done(add the sizes of one box to the another and then raycast), but I simply can't imagine how it can be done with this algorithm
Love that ray casting article
That's very interesting! It could be useful in 3D tiled-based games as well. For ex. raycasting in minecraft
It took me an entire month to understand the lodev article....only if u had made this video earlier. I could have saved time
This is basically the same algorithm used in the Wolf 3D source. Although John Carmack used goto to switch between x steps and y steps. I read the code in Game Engine Black Book: Wolfenstein 3D, but the source code is also available free online. I read about it while playing around with your first console FPS video. :-)
You're a LEGEND👍
Yoo let's go this is sick
When you think about it, the bresenham line algorithm is the DDA algorithm with optimizations based on the quadrant the direction is in. So you could benefit from some of those same optimizations. (Plus the bresenham line algorithm uses an error threshold of 0.5 to change direction to keep the line thin. You'd need to change that to 0)
When I developed this method independently, all those years ago (heh, as many others did, it seems), I realized it's the 2D generalization of Bresenham's. (Which is to say the same thing, merely going the other direction!) You keep two error accumulators, increment and conditionally-decrement each by their respective slopes -- importantly, the slope doesn't need to be normalized anymore -- and just let it spin!
The importance of denormal is, for creating a 3D view, you project a view plane relative to the view angle, and this all happens with basic 2D geometry. Which, I didn't know complex arithmetic or linear algebra at the time, but it's exactly that, as it happens. There's no trig involved whatsoever (beyond the one sin/cos pair to start with), no divide by zero, no janky hacks for special angles or quadrants -- it just works!
And the thing about denormal slope is, it gives you the perspective-corrected distance automatically. Dividing the view plane into angles, say, is a whole different projection and needs a complicated correction to look right (to preserve straight lines). This does of course mean, you can't go to 180° FOV, but that's typical of perspective projection.
There should really be a specific name for this alteration of the DDA algorithm. It doesn't help running into this all over the web while knowing in some cell sized grid space, you can just check each axis intersect rather than some small amount along the direction of the vector. Thanks for this, it's incredible!
Good tutorial !! I have a problem with the intersection circle, which is drawn in the center of the square and not on the edge.
This is one of the most useful videos on your channel, only bested by balls and capsules! :)
The next game I make that is tiled, I see if I can include this. I have only ever implemented raycasting for non-tiled things using a different method, but this seems simpler for tiled. (Maybe a tad slower though for large simple secnes)
15:00 when you shaded in the cells you checked, it shows that this is just a low-resolution pixelated line. Look at the fast algorithm for drawing a line: depending on the slope you always move either x or y; after a certain number of pixels you move 1 in the other axis.
I've done that in x86 (16-bit) assembly language, back in the late 80's through early 90's.
So, super-fast code for that is around, and even if you're not writing directly in ASM and keeping track of register usage, it still minimizes the number of values needed and avoids expensive operations like division and avoids branching.
oh my god thank you so much lol this helped a lot
I have a suggestion for an interesting topic for a video. There is an 128-bit decimal in C#. What is the best way to create a 128-bit double or float or decimal in C++? I did read about quad precision floats and doubles. I did possibly see a couple of projects on GitHub but I haven't looked into it that much. There is apparently an 80-bit double which is supported by non-microsoft compilers but that fact limits its usefulness a bit, especially if you use Visual Studio.
Maybe I can finally implement that collision algorithm I've been struggling with
Thank you
Amazing video, amazing voice!
Thank you so much!
Don't you have this for 3D as well? I would love to see it, as I am currently struggling with it :D
I was the 0x100 viewer, or at least that is what the counter showed, nice video!
you are one of the best CZcamsr
Thank you!
This is just absolutely genius
sheet, I was in need of this
What about edge cases for example rays with theta equal to 45 degrees? Wouldn't floating point operations result in some unreliability at touching points between two tiles?
If `direction` is normalized vector then `vRayUnitStepSize` can be calcualted as `{ 1 / vRay.x, 1 / vRay.y }`, knowing the fact that `sqrt(vRay.x^2 + vRay.y^2)` is equal to `1`
Ok, I joined your discord. My first one. any other one's you might recommend?
God content
DDA/Brezenham has linear complexity: the longer the line you're casting, the more expensive it gets. for large-scale data (say, for rendering voxels) you need faster average case convergence than O(N).
there's multiple approaches to do that like octrees, kd-trees, BVH's, SVO's, brick maps, but that's beside the point, I just wanted to note that DDA is certainly not a fast solution from asymptotic analysis standpoint. it's surely fast to implement though and works well for small scenes with low resolution grids (
Is there anything you could do in case of a direction bias with line: 82: *if (vRayLength1D.x < vRayLength1D.y)*? Say if a player is running against a wall upwards or downwards, eventually they'll be stopped at some axis crossing because at least in my tests, I note a "leftover" amount for the player to continue moving along the wall if some amount of force they experience is passed that said wall, and I used this to determine which direction to move them in that leftover amount. However there's a bias of the player stopped against that axis I mentioned once *vRayLength1D x and y* get really close to becoming the same value.
Hello Javi, nice work I would like to understand better all the formulas that you used in the video to implement it my own code. Do you have any recomendación? Thanks again
I have a video which is "maths for aspiring game developers" which covers the basics
@@javidx9Hello javi dou you know how to scale sprites when texturizing the walls? mi grid size is designed for 8 units but my sprites are 128*128. Do you know if its possbile?
2:12 I remember trying to make my own bad ray engine and the way I implemented it was to go out half the length, check for collision, then if there was one, go back a 4th, then check again, go forward an 8th and so on. It was way faster than the step by step like shown here, but still pretty slow due to the engine I used
edit, the method I used is called ray marching apparently
zeno's paradox at it finest, you'll be eternally computing it and never reaching that edge.
I have a different method, scrap the ray casting, instead just calculate the xy of the furthest point you want to draw, then skim through all the cells between that point and the player within a certain range of that point, while going through those cells you fill in a seperate array with the closest points to the player with an object, those are what you actually draw, for an easy to understand image, imagine a square with the player at any corner looking at the opposite corner, you just start skiming from that opposite corner through every cell in the square towards the player with each diagonal between the player and the opposite corner serving as a column, the edge columns will always have the adjacent corners as their closet cell, the opposite corner will always have the furthest cell that can be declared to hold something
btw the xy of the furthest point can be calculated by this method: y = ceil(dist * normalized angle), x = ceil(dist - y), you can then just calculate the furthest cells that are in range by using the normalised angle and -(0 - normalised angle), haven't directly checked any of that but I don't see any particlur issues with it
I am actually surprised that the code you are showing actually seem to work. I implemented this a few years ago and the first thing I encountered was that my program aborted with a division by 0 exception whenever dx or dy where 0. So basically if my line was parallel to one of the coordinate axis. I had to implement a special handling for those two cases for getting the algorithm to work, which was easy enough to do, as you are simply going along one axis then.
Just wanted to add this here in case someone encounters the same issue as I once did. :)
Well infinity is a valid floating point number and the maths still works out when it is used, so should be ok.
@@javidx9 yeah. but NaN is not infinity... well we all assumed something
How can we know the face of box where intersection happens also can this work in 3d ?
Detecting the face just requires some creative if/else action based upon the ray direction, and yes I believe this will work just as well in 3D.
I think that combining this raycasting technique with quadtree rather than a static cell size would lead to an interesting implementation
Nvidia has an article like this on doing it with sparse voxel octrees, infact that's what I'm working on at the moment.
I gave this a go using the pen & paper explanation you give. I've almost got it working and I decided to compare what I have with the code you've written. I tried substituting my own variables into the algorithm with no success. If I understand correctly, what is being displayed is an "illusion" and all of the vectors and map coordinates are actually way up in the top left corner of the screen. I think there was a similar thing going on in the A* video as well. Is that correct?
I can see the benefit, specifically where the map has no actually coordinates. That's like 2000 x and y variables that don't need to be created. I was gonna ask if, I should strive for this approach, but I think I've answered my own question. Do all games really only take place in the top left corner of the screen? Damn, that's crazy!
Wouldn't Bresenham Line Drawing algorithm be a better implementation for game development based on it's ability to be implemented using only integers?
That's a good idea! For fastest response, you'll probably want precomputed look up tables dx,dy for each vector direction. Not a problem with today's large memory computer, but it was back then. Just make sure that you do the right 1st step since it is fractional step.
@@ImGelling Modified Bresenham, obviously. Optimized for Raycasting.
I don't think it's good compared to DDA. DDA lines work similar to convervative rasterisers in that every pixel the line cross is marked (perfect for a ray marcher), Bresenham skips pixels as it's optimised for 1 pixel per column (assuming a more horizontal slope). See 18:49 for an example of a DDA covering more pixels
Love your videos. Can you please also do a floor casting in 3D raycaster? I am looking for an efficient way to map floor without having to cast one ray for each pixel on screen.
Thanks Harshit, my RayCastWorld "engine" does floor and ceiling sample still with columnar rays. czcams.com/video/Vij_obgv9h4/video.html
I tried my had at a 3d implementation. Can't tell if my variables were borked, or if my math was. Either way, it ran FAR too slowly to be usefull. Might end up revisiting it at a later date once I am using a shader instead of CPU.
I substituted "fast inverse sqrt" into the olc::PGE, pretty interesting results, but overall it does give a frame rate boost, especially casting many rays.
If you follow the link to the source you'll see an even faster implementation commented out that just uses abs() function.
Can this be used with tiles that have sloped edges or is it only possible with axis-aligned edges?
It could be If you are prepared to interrogate the cell for some alternative description of collision. This of course slows you down.
I wonder if you can use a modified form of the Bresenham's line algorithm or the Xiaolin Wu's line algorithm. Both would probably be a bit faster than DDA (maybe 2x faster?). Also, neither requires the computation of a square root, only a single division.
Raycasting must both hit every tile and tell you how far away that hit was. I think you might be able to do something similar by testing all the x intersections then all the y then taking the shortest, but I doubt it would be any better.
Hope someone can help!
I've almost been able to get this to work, but the ray goes from the lower-left corner of the source tile to the lower left corner of the target tile, while it should go from center to center. This causes a slight offset in the tiles marked as visited.
i love this channel even though I understand shit .... feelin productive :D
How would you do something like this for a hexagonal grid?
I don’t get 7:04 could someone explain to me what cos(theta), sin(theta) would mean in code or even logical maths i can’t picture it please
I did this to draw ropes using 8x8 sprites for NES without knowing it had a name :p Or at least a very similar technique.
In a 3d world, what is this formula for each axis? I'm searching this for a while and can't figure it out
This algorithm was a game changer for me as I used it in my internship project to build a voxel-based simulation environment for drones to train using deep learning algorithms. The algorithm brought significant improvements when it comes to raycasting in 3D. However, I would like to further optimize it. Since I'm dealing with a large dataset (simulation inside a warehouse) and a high number of repetition (Deep Learning), there is a lot of empty space that needs to be tested, but in vain. What do you guys recommend to tackle that issue? Aim for a better data structure or maybe use another raycasting algorithm? Has anyone heard of BVH? Thanks in advance!
I have a quick question, I'll be glad if you can help.
Since you are using fElapsedTime for vPlayer, vecMap[vMapCheck.y * vMapSize.x + vMapCheck.x] can't return proper value because vMapCheck is a float. Did you made any changes on your code which is not available on github?
Ah sorry, I miss this part: float(vMapCheck.y)
4:47, coming back to this a year later and I still think it's faster to use normalisation and virtual/imaginary boxes, though I admit I may suck at explaining it. I'll try again in list format.
1. Imagine the space between the ray source and the ray target as the area of your imaginary square
2. Normalise the angle to your target into just the space in that quadrilateral - for example: ((angle / 360) % 4) * 4
3. Decide which axis the angle should represent - for example: x = (angle < 0.5) ? angle : 1.0 - angle, y = vise versa
4. Multiply both normalised values against the distance between the ray source and the scene borders to get the ray targets position (if you didn't have it already and were working from just an angle)
5. Get the distance between the ray source vs target, this is the limits of your imaginary box from point 1
6. Divide the larger edge by the smaller, so width by height or vise versa, this value is how many units (pixels if it helps with imagery) you must process in the larger edge before moving up 1 unit in the smaller edge
7. Everything that shows up in those units is hit by the ray, do whatever with it, you can identify the other visible objects in a view cone by just iterating upto half the cone's width in units from the center ones you find, just use a normalised semi-circle's points to identify the remaining ones at the cone's front (or should I call it base?, feels like the point end should be the base though)
**Edit:** Btw to apply the same math to 3d space just pretend the z axis is an x axis and do the math for each x axis separately, you'll end up with 2 y values, to get the mid point between them in the 3d cone's view, just multiply their normalised values against each other
Typically these types of visibility tests benefit from terminating as quickly as possible (finding the nearest occluder ASAP and stopping the search). If you want everything that intersects the ray or other primitive like view cone or a circular/spherical search parameter without the occlusion, I think best bet is to use a spatial index and use it to find all things that intersect the primitive in logarithmic time.
@@darkengine5931 I didn't say can't use an index table with this, I'm saying that you use the size of the scene to determine how far in the table to jump x and y indices before reading the next index before switching axis, in other words because you know how far to jump you skip the "is dist 1 greater than dist 2" check and keep adding the values until you passby the scene boundaries or find an indice that is not 0
@@zxuiji I see! But I think #7 sounds a bit expensive if I understand since you're performing a parameter search if I understand correctly (something that I think would require a miniature loop or some additional inner branching). DDA achieves the equivalent of #7 by exactly determining which grid cell to check each marching step when all we have is a grid and slope from #6 with just a tiny bit of arithmetic each step and no need for any inner loop. If I'm misunderstanding, could you describe #7 with some pseudocode along with the overall loop?
this could be handy, I usually used pseudo-quadtrees for this kind of task
Hey Javidx, I have been trying for days on end to implement something similar in 3d space to scan triangles in 3d space. Really struggling with finding an algorithm and implementing. I have tried various things. scanlines, outrees, rayTraingleIntersect, rayAABB(around the triangles) and others. Each with varying degrees of success. Something are kept to help in rendering for example the octree. the others are made with joml. Is there any advice for traversing a 3d mesh with the intention of voxelizing it?
I'd rather use existing solution for voxelization, or at least look at existing implementations. Maybe "gvox" can do it, idk. One way I was thinking of is generating point cloud from from mesh by taking each triangle and generating points on the triangle , and then voxelizing that point cloud..
@@sti3167, Yeah, I'm just having a break from it for now. I did try something similar to voxelating a point cloud. I simply turned every point in the mesh into a voxel. The problem I was having, as I increase the resolution, gaps appear, Lack of experience with this sort of thing I think. I did think maybe I just subdivide all the faces down to a size smaller than the voxel faces but I don't know how efficient that would be and I haven't given it a go as of yet.
I wish I could find a 3rd party lib for Java, trust me I have looked. I have a working implementation in Python using TriMesh. Its fast enough and gives good results but,...bound to Java. I toyed with the idea of compiling python into an executable and then running that from Java but this in itself has problems. I also toyed with the idea of hitting an end point to get the job done. While that will work I don't like the idea of having to host a server and have the application call out every time I need to voxelize something.
Either way thanks for the suggestions.
i dont get the part where you calculate the sx and sy, can anyone help me understand that