16 ms·

Ncollide – 2D and 3D collision detection library

94 points by brson 10y ago

Hondor 10y ago
If only somebody would do collision (contact) for elastic bodies with the range of scales and accuracy needed for finite element analysis. As far as I know, this is something that nobody's achieved yet. Users have to manually tweak parameters to prevent parts from intersecting each other too much, bouncing off unphysically or the solver just failing to converge.
mrec 10y ago
The site is down and I can't get to Google's cache of it either, but the GitHub project is still up: https://github.com/sebcrozet/ncollide https://github.com/sebcrozet/ncollide
- steveklabnik 10y ago
  Seems to be up for me. If it's still down for you, that's really unfortunate: one of the reasons this link was submitted (I'm assuming) is that they just got a brand new site, and it's pretty great!
  - mrec 10y ago
    Hmm, interesting. It was still down (everything just timing out) an hour ago from work, but it's fine and snappy now from home. Maybe the corp firewall is blocking it for some reason.
  - mrec 10y ago
    Yup, back at work now and still can't get to it - definitely looks like a corp network/firewall issue.
codehero 10y ago
Sell me: I am a crusty old C++ programmer who started numerical and geometric programming on an SGI machine at the turn of the century. I have seen many academic and commercial 3D libraries come, go or perform poorly (vcollide, RAPID, CGAL and many proprietary ones). It looks interesting but what makes this library any better than what's come before? Why should I learn Rust to use it or really for any computational geometry problem?
- webkike 10y ago
  I'm not sure. I certainly would never use a third party collision library because I think collisions are simple enough, but on the larger subject of whether Rust is suitable for game programming; I think so, but cannot confirm. There are a lot of abstractions that require pointer dereference, which is somewhat likely to give you a performance drain, and those abstractions are I guess somewhat harder to avoid than in C++, but not terribly so. Both languages give you the ability to do "data directed design" if you really really want to. My preference for Rust stems from my preference for interfaces, or traits as they are called in Rust. If you want to use features like these then Rust is a no brainer. I have yet to see the true impact on performance these abstractions have however.
  - openasocket 10y ago
    What abstractions are you referring to? If you're using traits and writing your functions with generics there shouldn't be any overhead, other than the increased number of instructions, but this is no different than C++ generics. There are trait objects, but these come up somewhat less often then you would think, and have the same performance as using abstract classes/polymorphism in C++. But maybe you're referring to something else?
    - webkike 10y ago
      I am referring to trait objects, and I use those pretty extensively (although I limit my usage because I am making games and want to avoid a pointer dereference). For libraries you might not need them as much, but I definitely find their convenience indespensible for application side programming.
      - openasocket 10y ago
        Personally, I've found that most cases you can avoid using trait objects by just using generics, but it obviously depends on your use case. You especially need trait objects to have things like heterogeneous arrays. Trait objects are pretty much the same as C++ classes with virtual methods, with one tweak in the representation. A C++ object is referred to by a pointer to (vtable_ptr, class_fields). A trait object "&Foo" is a fat pointer (vtable_ptr, ptr_to_fields). So a trait object reference is two pointers, but doesn't have a pointer stuck to the front of all of its structs. Method invocation requires you to dereference the vtable, get the function pointer, and call that, passing the data pointer. In C++ you would dereference your pointer, dereference the vtable, then pass the pointer to the function. If anything, I think the Rust method may be faster because you avoid the double de-reference, but it's probably so small as to be unmeasurable in all but pathological uses.
webkike 10y ago
It's a neat project, but ultimately I don't think I'll be replacing my own collision library any time soon. I should write a blog post about this, but basically it boils down to not having enough support for accurate toa collisions for capsules. You can have exact toa collisions for essentially any exact toa collision you can have with spheres, one of the reasons capsules are such a great tool for making hitboxes. As far as I can tell this library does not support that.
- willvarfar 10y ago
  Please do write that blog post and, if possible, release your code :) I struggled so long and basically put my hobby game on ice after failing to sort out capsule plane collisions! :( What language is your own library in?
  - webkike 10y ago
    My collision code is in Rust, actually. Pretty funny. Capsule-plane collisions are pretty simple, simple enough that I can outline here. The first thing you want to do is find the sphere on the capsule to perform the test on, call this time t_X. Create a line from the segment (starts at t_0, ends at t_1) bounding the capsule and determine its intersection point with the plane. If there is no intersection, just set t_x to mean(t_0, t_1), or halfway on the capsule's segment. If there is an intersection, and the time is between t_0 and t_1, set t_x to that time. Otherwise clamp it between t_0 and t_1. Now you have a sphere and a position (the time t_x on the capsule segment), and you can perform a moving sphere - plane collision. This algorithm works because the premise - the point on a capsule closest to a plane will always get closer to the plane, unless the capsule is moving away - is sound, as far as I can tell.
    - willvarfar 10y ago
      Had to go revisit my hobby code to work out what my hangup was. It was specifically capsule/triangle collision I got stuck on. I had reasoned that with just capsule triangle I could do a 3D platform game on a mesh. However, I kept getting very wrong bounces off of edges.
lcfcjs 10y ago
AHH Rust! ::runs off::
joeld42 10y ago
Rust is C-linkable, right? How hard would it be to use this from C?
- TillE 10y ago
  You'd need to write the C API yourself. Probably not worth it, unless there's something special you need from this particular library. https://doc.rust-lang.org/book/ffi.html#calling-rust-code-from-c https://doc.rust-lang.org/book/ffi.html#calling-rust-code-fr...
- codehero 10y ago
  Why use this library when similar libraries implemented in C have been in production for decades?
  - warmwaffles 10y ago
    What C library is there that I can use? I don't want a C interface to Bullet.
Animats 10y ago
Nice. Now we have a 3D collision library in Rust. It may take a while to see how good it is. I notice that they have decomposition of non-convex objects into a union of convex objects. That's very useful. Convex polyhedron vs convex polyhedron is very fast, only slightly worse that constant time for repeated tests on moving objects. (GJK is the preferred convex vs convex test.) Mesh vs mesh is generally slow, although there are "polygon soup" systems that just compare triangles and understand no higher structure. Meshes are not necessarily solids; collision detection is better for things which are definitely solids. Other objects vs. height field is very useful in games; that's what you use for terrain. Collision detection which drives a non-trivial physics system has to have certain properties. It helps a lot if the forces are differentiable against object movement. If there are infinitesimal movements which result in discontinuous changes in forces, physics models won't work right. This causes such artifacts as objects lying on the ground which vibrate. The closest point vector is shifting from corner to corner as two planes come into parallelism. It's static indeterminism in action. The solution is a multi-point contact model, where you have several closest point vectors with distances, and compute forces for each point of support. If you have at least three, stability is possible. If you're working on legged locomotion, and care about foot/ground contact and friction, you need that. Ncollide's videos look good. Although check the first one where the balls fall into a cone. At the top, there's one ball perched stably on top of another ball. I used to do this stuff.[1] [1] https://news.ycombinator.com/item?id=11359181https://news.ycombinator.com/item?id=11359181 https://news.ycombinator.com/item?id=11359181https://news.yc...
- santaclaus 10y ago
  > It helps a lot if the forces are differentiable against object movement. If there are infinitesimal movements which result in discontinuous changes in forces, physics models won't work right. There are models of non-smooth interactions that get used in mechanics, graphics, and robotics - I'm thinking Baraff and Moreau and Stewart and Trinkle type stuff. You end up with dynamics formulated as differential inclusions, but it all still works out.
  - Animats 10y ago
    Baraff-type impulse-based collisions occur in zero time, which is why objects banging around in games look too light.
viperscape 10y ago
This library is sort of rough as you delve deeper, for instance mesh data gets put into an Arc, which in Rust terms is read only and thread safe but doesn't seem to belong in the library in my opinion because something simple like scaling a mesh is complicated now: https://github.com/sebcrozet/ncollide/issues/112 https://github.com/sebcrozet/ncollide/issues/112 There are some other quirks I found like trying to store sphere colliders in a hashmap but found I instead need to store the Point type explicitly which wasn't obvious at first. Overall I think the library is good but needs more work, and an abstraction to work with space partitioning would be nice, even if it was in a different library or module. I wish I could offer help, this is definitely a good project. The sister library nalgebra is fantastic in my opinion, great linear algebra library: https://github.com/sebcrozet/nalgebra https://github.com/sebcrozet/nalgebra

94 points by brson 10y ago

If only somebody would do collision (contact) for elastic bodies with the range of scales and accuracy needed for finite element analysis. As far as I know, this is something that nobody's achieved yet. Users have to manually tweak parameters to prevent parts from intersecting each other too much, bouncing off unphysically or the solver just failing to converge.

mrec 10y ago

The site is down and I can't get to Google's cache of it either, but the GitHub project is still up: https://github.com/sebcrozet/ncollide https://github.com/sebcrozet/ncollide

steveklabnik 10y ago
Seems to be up for me. If it's still down for you, that's really unfortunate: one of the reasons this link was submitted (I'm assuming) is that they just got a brand new site, and it's pretty great!
- mrec 10y ago
  Hmm, interesting. It was still down (everything just timing out) an hour ago from work, but it's fine and snappy now from home. Maybe the corp firewall is blocking it for some reason.
- mrec 10y ago
  Yup, back at work now and still can't get to it - definitely looks like a corp network/firewall issue.

codehero 10y ago

Sell me: I am a crusty old C++ programmer who started numerical and geometric programming on an SGI machine at the turn of the century. I have seen many academic and commercial 3D libraries come, go or perform poorly (vcollide, RAPID, CGAL and many proprietary ones). It looks interesting but what makes this library any better than what's come before? Why should I learn Rust to use it or really for any computational geometry problem?

webkike 10y ago
I'm not sure. I certainly would never use a third party collision library because I think collisions are simple enough, but on the larger subject of whether Rust is suitable for game programming; I think so, but cannot confirm. There are a lot of abstractions that require pointer dereference, which is somewhat likely to give you a performance drain, and those abstractions are I guess somewhat harder to avoid than in C++, but not terribly so. Both languages give you the ability to do "data directed design" if you really really want to. My preference for Rust stems from my preference for interfaces, or traits as they are called in Rust. If you want to use features like these then Rust is a no brainer. I have yet to see the true impact on performance these abstractions have however.
- openasocket 10y ago
  What abstractions are you referring to? If you're using traits and writing your functions with generics there shouldn't be any overhead, other than the increased number of instructions, but this is no different than C++ generics. There are trait objects, but these come up somewhat less often then you would think, and have the same performance as using abstract classes/polymorphism in C++. But maybe you're referring to something else?
  - webkike 10y ago
    I am referring to trait objects, and I use those pretty extensively (although I limit my usage because I am making games and want to avoid a pointer dereference). For libraries you might not need them as much, but I definitely find their convenience indespensible for application side programming.
    - openasocket 10y ago
      Personally, I've found that most cases you can avoid using trait objects by just using generics, but it obviously depends on your use case. You especially need trait objects to have things like heterogeneous arrays. Trait objects are pretty much the same as C++ classes with virtual methods, with one tweak in the representation. A C++ object is referred to by a pointer to (vtable_ptr, class_fields). A trait object "&Foo" is a fat pointer (vtable_ptr, ptr_to_fields). So a trait object reference is two pointers, but doesn't have a pointer stuck to the front of all of its structs. Method invocation requires you to dereference the vtable, get the function pointer, and call that, passing the data pointer. In C++ you would dereference your pointer, dereference the vtable, then pass the pointer to the function. If anything, I think the Rust method may be faster because you avoid the double de-reference, but it's probably so small as to be unmeasurable in all but pathological uses.

webkike 10y ago

It's a neat project, but ultimately I don't think I'll be replacing my own collision library any time soon. I should write a blog post about this, but basically it boils down to not having enough support for accurate toa collisions for capsules. You can have exact toa collisions for essentially any exact toa collision you can have with spheres, one of the reasons capsules are such a great tool for making hitboxes. As far as I can tell this library does not support that.

willvarfar 10y ago
Please do write that blog post and, if possible, release your code :) I struggled so long and basically put my hobby game on ice after failing to sort out capsule plane collisions! :( What language is your own library in?
- webkike 10y ago
  My collision code is in Rust, actually. Pretty funny. Capsule-plane collisions are pretty simple, simple enough that I can outline here. The first thing you want to do is find the sphere on the capsule to perform the test on, call this time t_X. Create a line from the segment (starts at t_0, ends at t_1) bounding the capsule and determine its intersection point with the plane. If there is no intersection, just set t_x to mean(t_0, t_1), or halfway on the capsule's segment. If there is an intersection, and the time is between t_0 and t_1, set t_x to that time. Otherwise clamp it between t_0 and t_1. Now you have a sphere and a position (the time t_x on the capsule segment), and you can perform a moving sphere - plane collision. This algorithm works because the premise - the point on a capsule closest to a plane will always get closer to the plane, unless the capsule is moving away - is sound, as far as I can tell.
  - willvarfar 10y ago
    Had to go revisit my hobby code to work out what my hangup was. It was specifically capsule/triangle collision I got stuck on. I had reasoned that with just capsule triangle I could do a 3D platform game on a mesh. However, I kept getting very wrong bounces off of edges.

lcfcjs 10y ago

AHH Rust! ::runs off::

joeld42 10y ago

Rust is C-linkable, right? How hard would it be to use this from C?

TillE 10y ago
You'd need to write the C API yourself. Probably not worth it, unless there's something special you need from this particular library. https://doc.rust-lang.org/book/ffi.html#calling-rust-code-from-c https://doc.rust-lang.org/book/ffi.html#calling-rust-code-fr...
codehero 10y ago
Why use this library when similar libraries implemented in C have been in production for decades?
- warmwaffles 10y ago
  What C library is there that I can use? I don't want a C interface to Bullet.

Animats 10y ago

Nice. Now we have a 3D collision library in Rust. It may take a while to see how good it is. I notice that they have decomposition of non-convex objects into a union of convex objects. That's very useful. Convex polyhedron vs convex polyhedron is very fast, only slightly worse that constant time for repeated tests on moving objects. (GJK is the preferred convex vs convex test.) Mesh vs mesh is generally slow, although there are "polygon soup" systems that just compare triangles and understand no higher structure. Meshes are not necessarily solids; collision detection is better for things which are definitely solids. Other objects vs. height field is very useful in games; that's what you use for terrain. Collision detection which drives a non-trivial physics system has to have certain properties. It helps a lot if the forces are differentiable against object movement. If there are infinitesimal movements which result in discontinuous changes in forces, physics models won't work right. This causes such artifacts as objects lying on the ground which vibrate. The closest point vector is shifting from corner to corner as two planes come into parallelism. It's static indeterminism in action. The solution is a multi-point contact model, where you have several closest point vectors with distances, and compute forces for each point of support. If you have at least three, stability is possible. If you're working on legged locomotion, and care about foot/ground contact and friction, you need that. Ncollide's videos look good. Although check the first one where the balls fall into a cone. At the top, there's one ball perched stably on top of another ball. I used to do this stuff.[1] [1] https://news.ycombinator.com/item?id=11359181https://news.ycombinator.com/item?id=11359181 https://news.ycombinator.com/item?id=11359181https://news.yc...

santaclaus 10y ago
> It helps a lot if the forces are differentiable against object movement. If there are infinitesimal movements which result in discontinuous changes in forces, physics models won't work right. There are models of non-smooth interactions that get used in mechanics, graphics, and robotics - I'm thinking Baraff and Moreau and Stewart and Trinkle type stuff. You end up with dynamics formulated as differential inclusions, but it all still works out.
- Animats 10y ago
  Baraff-type impulse-based collisions occur in zero time, which is why objects banging around in games look too light.

viperscape 10y ago

This library is sort of rough as you delve deeper, for instance mesh data gets put into an Arc, which in Rust terms is read only and thread safe but doesn't seem to belong in the library in my opinion because something simple like scaling a mesh is complicated now: https://github.com/sebcrozet/ncollide/issues/112 https://github.com/sebcrozet/ncollide/issues/112 There are some other quirks I found like trying to store sphere colliders in a hashmap but found I instead need to store the Point type explicitly which wasn't obvious at first. Overall I think the library is good but needs more work, and an abstraction to work with space partitioning would be nice, even if it was in a different library or module. I wish I could offer help, this is definitely a good project. The sister library nalgebra is fantastic in my opinion, great linear algebra library: https://github.com/sebcrozet/nalgebra https://github.com/sebcrozet/nalgebra