29-05-2021, 08:43 AM
(This post was last modified: 29-05-2021, 08:50 AM by josemendez.)
(28-05-2021, 10:24 PM)Hatchling Wrote: For a raycast, I know you can approximate a point of impact by getting the closest point between the ray and a simplex. For example, you could get the closest point between a ray and line segment, and if the distance is less than the thickness of the ray + the thickness of the line segment, it is a hit, and the closest point on the ray is the hit point. But this isn't accurate; it shouldn't be the point of deepest penetration, but of first penetration, which requires a bit more weird math to compute. Are you using the approximate or exact method (or some other method) to calculate the hit point?
Short answer: Exact method.
Long answer: Simplex collisions use an iterative method (Frank-Wolfe convex optimization) to calculate distances/intersections of any convex shape with a simplex, which might be made of particles of different radius. In case of rays: for each iteration, it calculates the intersection between the ray and a sphere centered at the current barycentric coordinates in the simplex (sphere radius is interpolated from the radii at the simplex vertices). If there's no intersection, it calculates the distance between the ray and the sphere. Over a few iterations (8 by default, up to 32, exposed in the solver as a parameter) this converges to the exact solution: a point in the surface of the simplex where the ray first intersects it, or the closest point between the ray and the simplex otherwise.
For 0-simplices (particles), this gives the exact solution in just one iteration as it reduces to a sphere/ray intersection test, or a point-ray distance test if the intersection fails.
(28-05-2021, 10:24 PM)Hatchling Wrote: Also, I'm guessing the Bresenham algorithm is a way to enumerate through cells that intersect with a line. I'm guessing it intuitively just checks what face of a cell intersects with a line, and then navigates to the neighbor on the other side of that face, repeating until the end of the line or grid is reached. I think Wolfenstein did something similar to this to render their grid-based 2.5d worlds.
I can see this being slower than just enumerating through a small list of occupied cells, though it might be faster when there are a lot of them... which shouldn't happen too often (maybe it'd be more a problem with fluid?). (I can see this approach being especially costly when you have to also search neighbors when using a thick ray.)
I wonder what % of occupied cells would be required for the more complex enumeration to be worthwhile. ::thinkingface::
In any case, this is just food for thought. I'm sure this is plenty!
Right on point about everything. The two main showstoppers for Bresenham (actually, DDA in my case) are: #1) Need to check all cells intersected by the ray, and very long rays are common. #2) I need to check not only the cells intersected by the ray but their 27 neighbors too, many of which might be empty. This results in a lot of unnecessary work. For thick rays it's even worse.
(28-05-2021, 10:24 PM)Hatchling Wrote:
Regarding the collision-detection stuff needing to be enabled for raycasts to work (as otherwise the simplex grid isn't built), it might be a good idea to make note of that on the solver in the inspector, just for the sake of making it easier for future users. Perhaps name the collision module "Collision/Queries" and when unfolded, it shows a HelpBox() in there. *shrug*
Will do, thanks for the suggestion
Perfect.