3 ms·

This seems like an intricate implementation for a very specific case. What if you wanted to have moving walls or non-rectilinear walls, etc? There are more appr

by joshu 12y ago

This seems like an intricate implementation for a very specific case. What if you wanted to have moving walls or non-rectilinear walls, etc? There are more appropriate data structures for storing a set of lines and efficiently seeing if another line (eg the dot's trajectory) has intersected one of them.

sillysaurus3 12y ago
If your walls and balls are both moving, you'll need to do collision detection by making the ball into a capsule (integrate its bounding sphere's position over current timestep) and make the wall into a quadrilateral (integrate wall's position over current timestep). If the ball's path intersects the quadrilateral, its velocity needs to be reflected at the intersection point. When your collision is dynamic like that, your performance isn't going to be O(1), which is what the poster was trying to achieve. You can make it sublinear, but when there are fewer than ~100 objects the speed gain isn't really worth the complexity. 100x100 is still only 10,000 ops, which can probably be done in javascript without performance problems. It's definitely a fun learning exercise though, and it will give you some valuable insight into how physics libraries work.
- joshu 12y ago
  i think the usual way is to advance the timestep, see if the item penetrates the other item, and then go back and advance half a timestep. but my point is, you don't need to check the entire world if you are using a quadtree or rtree or whatever.
  - sillysaurus3 12y ago
    I don't think that's the usual way, because it will completely miss collisions for fast-moving balls. They don't need a quadtree or an rtree if the number of objects is fewer than 100. Also, when using a quadtree/rtree etc with dynamic objects, you'll need to rebalance the tree as objects move around. If the rebalancing is more expensive than the speed gained by using it, then those datastructures can be harmful, not helpful. This is case is relatively rare but something to keep in mind.
userbinator 12y ago
storing a set of lines and efficiently seeing if another line (eg the dot's trajectory) has intersected one of them. This is the basic principle behind raytracing and the variant raymarching, which can be used to create some very interesting images with very compact descriptions: http://iquilezles.org/www/material/nvscene2008/rwwtt.pdf http://iquilezles.org/www/material/nvscene2008/rwwtt.pdf Applied to things bouncing around on other things, this technique would enable calculating exactly when the collisions are, which is a possible optimisation to requiring collision checks at each time step. It is very similar to the principle of a discrete event simulator.

by joshu 12y ago

sillysaurus3 12y ago

If your walls and balls are both moving, you'll need to do collision detection by making the ball into a capsule (integrate its bounding sphere's position over current timestep) and make the wall into a quadrilateral (integrate wall's position over current timestep). If the ball's path intersects the quadrilateral, its velocity needs to be reflected at the intersection point. When your collision is dynamic like that, your performance isn't going to be O(1), which is what the poster was trying to achieve. You can make it sublinear, but when there are fewer than ~100 objects the speed gain isn't really worth the complexity. 100x100 is still only 10,000 ops, which can probably be done in javascript without performance problems. It's definitely a fun learning exercise though, and it will give you some valuable insight into how physics libraries work.

joshu 12y ago
i think the usual way is to advance the timestep, see if the item penetrates the other item, and then go back and advance half a timestep. but my point is, you don't need to check the entire world if you are using a quadtree or rtree or whatever.
- sillysaurus3 12y ago
  I don't think that's the usual way, because it will completely miss collisions for fast-moving balls. They don't need a quadtree or an rtree if the number of objects is fewer than 100. Also, when using a quadtree/rtree etc with dynamic objects, you'll need to rebalance the tree as objects move around. If the rebalancing is more expensive than the speed gained by using it, then those datastructures can be harmful, not helpful. This is case is relatively rare but something to keep in mind.

userbinator 12y ago

storing a set of lines and efficiently seeing if another line (eg the dot's trajectory) has intersected one of them. This is the basic principle behind raytracing and the variant raymarching, which can be used to create some very interesting images with very compact descriptions: http://iquilezles.org/www/material/nvscene2008/rwwtt.pdf http://iquilezles.org/www/material/nvscene2008/rwwtt.pdf Applied to things bouncing around on other things, this technique would enable calculating exactly when the collisions are, which is a possible optimisation to requiring collision checks at each time step. It is very similar to the principle of a discrete event simulator.