The main thing I want to know if this code prevents square root from being performed. My own version of this algorithm does use square root, so it would be nice speed-wise if I can prevent this square root.
The problem with Eigen::Vector3d is that I cannot find it in the Eigen source code, the search does not locate Vector3d
I do believe it is part of the eigen namespace. Perhaps the vector from c++ is added to the Eigen namespace.
I am unsure about that.
I tried loading the source code in visual studio 2019, but as always Microsoft's Visual Studio products are 9 out of 10 times total CRAP and this version is no different. Can't login because this fool of a product uses internet explorer 11 to try and login with community edition, which ofcourse miserably fails because of login script errors.
Why people continue coding in this garbage product and language is beyond me, but ok the code is nice, there is just no way to compile it. Very maybe visual studio 2010 might work, the only decent version that was ever produced by this Microsoft company (after I sweared the shit out of them with vs 2008 slow editor where templates for coloring syntax lines caused massive slow down !!! If it wasn't for my debugging this shit there product would still be CRAP HAHAHAHAHA, I wouldn't be surprised if VS code project was start because of vs 2008 crap !!!!), but ofcourse it has old c++ language. I ll give it a try and see how far it gets.
I disabled these 3 lines to make code compile to see if it works:
// for (auto& i : ids) {
// std::cout << "> " << i.transpose() << std::endl;
// }
also added the eigen library to c/c++>general> additional library includes
I was surprised it works/builds at all.
Unfortunately find declaraction or find definition on eigen:vector3d doesn't work at all, re-assuring me that this product is total crap and this library is ingenious total crap !
I bet you yourself don't even know what the fuck you wrote ! HAHA.
Good luck finding it ! ;) =D
Thanks for the code anyway, maybe it might be of some use.
To give you back some value and to answer your to-do problem about the "on border" point question.
From what I remember from my own experimentation with this algorithm: One simple has to choose a default.
For example always choose the voxel less than the other one so 0 < 1.
Simply choose top, left first... if equal on border.
In principe this does make sense because the algorithm crosses borders, so eventually it will process all voxels.
However there might be a problem with this general idea, if the voxels have to be processed in a certain order than it might be problematic, this could actually be a slight weakness with this algoritm.
For example if wanting to make sure that a point is always closest from going in a certain direction... it would be nice if the order is perfect in that case, no further distance comparisions need to be done, otherwise distance has to be checked if wrong order is done. I am not even sure if this is a real problem but maybe...
During the start of the algorithm it should not be much of a problem, if it's on the border than again shouldn't be much of a problem.
So I may not sure what the problem here is:
// The id of the last voxel hit by the ray.
// TODO: what happens if the end point is on a border?
Eigen::Vector3i last_voxel(std::floor(ray_end[0]/_bin_size),
std::floor(ray_end[1]/_bin_size),
std::floor(ray_end[2]/_bin_size));
Perhaps the question is here, to process or not the process the last voxel around this border ?
This is a good question...The safe thing to do is both... but also the question is not yet answered is the order of voxel traversal correct ? I hope so and it probably will be correct ;)
This is actually the reason why one of my version actually processes a square root to calculate the distance of the ray.
In my code the ray is of limited length... and I limit the ray to this length.
So the while loop is different:
while (vRayBoundaryX < vRayLength) or (vRayBoundaryY < vRayLength) {or (vRayBoundaryZ <= vRayLength)} do
Something like that... RayLength has to be computed for this.
So perhaps this is a bit misleading in this algorithm title "fast grid traversal" but that is ofcouse not what it said it reads:
A Fast Voxel Traversal Algorithm
for
Ray Tracing
So this is very situational.... as long as it does not have to compute a length for rays and can just exit then maybe... another problem is if the voxel grid is larger, this loop while take a much longer time than necessary if the light ray has diminished in strength so to speak... light pretending it's light from a candle... the further the distance the less like there would be a ray so might as well cut it out. I tried using this for shadows and such, can't tell exactl how that secret ;)
Anyway there is a quake 1 or quake 3 method of computing an inverse square root very fast, there is even a youtube video of it,
for raytracing it's probably garbage and would produce bad results.. but maybe it stil accurate enough not sure.
(Also if this point on border problem remains, then perhaps special algorithm must be added to decide which border to process first perhaps based on old step and new step variables, that would probably be easy to do and would probably work flawlessly, could also be added as a last step).
It uses a little bit same technique as mine but a little bit different, instead of comparing against ray length, it tries to verify against end voxels of algorithm.
Theoretically that could problem work, though not entirely sure, seems interesting and might be computationally less expensive than the square root version of mine haha. Though very maybe there might be an oversight somewhere... perhaps indeed with border issues or something.. hmmm... I think I tried a version like this, in practice maybe it fails for some corner cases, not sure yet.
Actually your code also tries to compute last voxel somehow, but it is not clear to me how this is done, seems to be something with binsize.
And also comparing against some kind of voxel pointer or so, a bit fuzzy code without knowlege from eigen lib I presume.
No now I see it's a vectori3... that comparision is probably calling an equal operator and probably performs 3 comparisions as well, shorter code, but harder to read... was it really worth saving 3 equals from typing, perhaps not, giving the ammount of time necessary to lookup the code and the complexities involved with it getting the look up working ! ;) which right now is not working at all or barely.
I am trying to understand this line of code:
Eigen::Vector3d ray = ray_end-ray_start
The main thing I want to know if this code prevents square root from being performed. My own version of this algorithm does use square root, so it would be nice speed-wise if I can prevent this square root.
The problem with Eigen::Vector3d is that I cannot find it in the Eigen source code, the search does not locate Vector3d
I do believe it is part of the eigen namespace. Perhaps the vector from c++ is added to the Eigen namespace.
I am unsure about that.
I tried loading the source code in visual studio 2019, but as always Microsoft's Visual Studio products are 9 out of 10 times total CRAP and this version is no different. Can't login because this fool of a product uses internet explorer 11 to try and login with community edition, which ofcourse miserably fails because of login script errors.
Why people continue coding in this garbage product and language is beyond me, but ok the code is nice, there is just no way to compile it. Very maybe visual studio 2010 might work, the only decent version that was ever produced by this Microsoft company (after I sweared the shit out of them with vs 2008 slow editor where templates for coloring syntax lines caused massive slow down !!! If it wasn't for my debugging this shit there product would still be CRAP HAHAHAHAHA, I wouldn't be surprised if VS code project was start because of vs 2008 crap !!!!), but ofcourse it has old c++ language. I ll give it a try and see how far it gets.
I disabled these 3 lines to make code compile to see if it works:
// for (auto& i : ids) { // std::cout << "> " << i.transpose() << std::endl; // }
also added the eigen library to c/c++>general> additional library includes
I was surprised it works/builds at all.
Unfortunately find declaraction or find definition on eigen:vector3d doesn't work at all, re-assuring me that this product is total crap and this library is ingenious total crap !
I bet you yourself don't even know what the fuck you wrote ! HAHA.
Good luck finding it ! ;) =D
Thanks for the code anyway, maybe it might be of some use.
To give you back some value and to answer your to-do problem about the "on border" point question.
From what I remember from my own experimentation with this algorithm: One simple has to choose a default.
For example always choose the voxel less than the other one so 0 < 1.
Simply choose top, left first... if equal on border.
In principe this does make sense because the algorithm crosses borders, so eventually it will process all voxels.
However there might be a problem with this general idea, if the voxels have to be processed in a certain order than it might be problematic, this could actually be a slight weakness with this algoritm.
For example if wanting to make sure that a point is always closest from going in a certain direction... it would be nice if the order is perfect in that case, no further distance comparisions need to be done, otherwise distance has to be checked if wrong order is done. I am not even sure if this is a real problem but maybe...
During the start of the algorithm it should not be much of a problem, if it's on the border than again shouldn't be much of a problem.
So I may not sure what the problem here is:
// The id of the last voxel hit by the ray. // TODO: what happens if the end point is on a border? Eigen::Vector3i last_voxel(std::floor(ray_end[0]/_bin_size), std::floor(ray_end[1]/_bin_size), std::floor(ray_end[2]/_bin_size));
Perhaps the question is here, to process or not the process the last voxel around this border ?
This is a good question...The safe thing to do is both... but also the question is not yet answered is the order of voxel traversal correct ? I hope so and it probably will be correct ;)
This is actually the reason why one of my version actually processes a square root to calculate the distance of the ray.
In my code the ray is of limited length... and I limit the ray to this length.
So the while loop is different:
Something like that... RayLength has to be computed for this.
So perhaps this is a bit misleading in this algorithm title "fast grid traversal" but that is ofcouse not what it said it reads:
A Fast Voxel Traversal Algorithm for Ray Tracing
So this is very situational.... as long as it does not have to compute a length for rays and can just exit then maybe... another problem is if the voxel grid is larger, this loop while take a much longer time than necessary if the light ray has diminished in strength so to speak... light pretending it's light from a candle... the further the distance the less like there would be a ray so might as well cut it out. I tried using this for shadows and such, can't tell exactl how that secret ;)
Anyway there is a quake 1 or quake 3 method of computing an inverse square root very fast, there is even a youtube video of it,
for raytracing it's probably garbage and would produce bad results.. but maybe it stil accurate enough not sure.
(Also if this point on border problem remains, then perhaps special algorithm must be added to decide which border to process first perhaps based on old step and new step variables, that would probably be easy to do and would probably work flawlessly, could also be added as a last step).
Update:
This version is actually also quite interesting:
https://github.com/cgyurgyik/fast-voxel-traversal-algorithm/blob/master/amanatidesWooAlgorithm.cpp
It uses a little bit same technique as mine but a little bit different, instead of comparing against ray length, it tries to verify against end voxels of algorithm.
Theoretically that could problem work, though not entirely sure, seems interesting and might be computationally less expensive than the square root version of mine haha. Though very maybe there might be an oversight somewhere... perhaps indeed with border issues or something.. hmmm... I think I tried a version like this, in practice maybe it fails for some corner cases, not sure yet.
Actually your code also tries to compute last voxel somehow, but it is not clear to me how this is done, seems to be something with binsize.
And also comparing against some kind of voxel pointer or so, a bit fuzzy code without knowlege from eigen lib I presume.
No now I see it's a vectori3... that comparision is probably calling an equal operator and probably performs 3 comparisions as well, shorter code, but harder to read... was it really worth saving 3 equals from typing, perhaps not, giving the ammount of time necessary to lookup the code and the complexities involved with it getting the look up working ! ;) which right now is not working at all or barely.
Bye for now, Skybuck.