8 ms·

HTML5 games: 3D collision detection

mrspeaker 11y ago
The link seems to be the overview (with nifty demo) - the actual article is here: https://developer.mozilla.org/en-US/docs/Games/Techniques/3D_collision_detection https://developer.mozilla.org/en-US/docs/Games/Techniques/3D... I've been playing around with 3D for a while, and have found that collision detection is the (relatively) easy bit: it's collision resolution that messes me up!
- talloaktrees 11y ago
  Yes, you're exactly right. Resolution is the tricky part. I made a simple FPS game engine using Java + libgdx (https://github.com/jrenner/gdx-proto https://github.com/jrenner/gdx-proto), and it leveraged the bullet physics library for collision detection, but handling collision resolution myself. Even simple things like getting an object to to slide along a wall as it collides with it at an angle can be tricky.
  - JupiterMoon 11y ago
    If you're already using bullet why not use if for collision resolution as well? Or if you want to manually change things try using ODE as this is more amiable towards doing so.
- maccard 11y ago
  Even detecting collisions accurately isn't easy. This is only between primitives (spheres and boxes). Detecting collisions between convex hulls (and more difficultly non-convex shapes) is quite difficult.
  - chaosemer 11y ago
    Detecting collisions between two convex hulls isn't that hard, but it is slow-ish. The Separating Axis Theorem (or its more general and WAY COOLER SOUNDING Hyperplane Separation Theorem) lets you do a dot-product per face and if they all come out positive, there's no collision. https://en.wikipedia.org/wiki/Hyperplane_separation_theorem https://en.wikipedia.org/wiki/Hyperplane_separation_theorem
    - Animats 11y ago
      Convex collision detection is very fast with incremental GJK. When the axis-aligned bounding boxes for two objects intersect, you create an object pair and start GJK for the pair. It walks along the edges and faces of the polyhedra to find the shortest distance. This is O(log N) on the number of vertices. On the next frame, you rerun GJK starting from the previous result, and if the objects haven't moved much, look at 0 or 1 new edges, vertices, or faces. So the incremental approach is nearly constant time after the startup. Doing a dot-product for every face pair is O(N^2). Bad for large N. If you do this right, convex hulls with a few hundred faces are no problem. When constructing convex hulls for this, you can use a tool like QHull. Tell it that you want at least some minimal angle such as 1 degree at each edge. This will eliminate many near-coplanar faces. Also, it's better to use polygonal faces than triangular faces. With triangles, a rectangular face has two coplanar faces, and GJK will toggle between them, making resting object jiggle. (Basic annoyance of polyhedra and roundoff: if you tesselate, you get coplanar faces; if you use polygon faces, they're not perfectly flat.)
    - snaily 11y ago
      There's something about multidimensional geometry and great theorem names. I bring you the ham sandwich theorem: https://en.wikipedia.org/wiki/Ham_sandwich_theorem https://en.wikipedia.org/wiki/Ham_sandwich_theorem
frik 11y ago
As one of the linked articles is based on Three.js . It's like a plague that simple 3D examples and tutorials almost always features that Three.js library instead of "vanilla" Javascript with WebGL. People should learn WebGL and JS first and later decide if such a library is even suitable for their usecase (known to be slow). It reminds me of 2-3 years ago, where almost every Javascript tutorial was littered with JQuery library function calls. Most Stackoverflow questions were answered with JQuery answers. In the meantime things have obviously changed for the better. With Three.js it's still extreme, there are even several books with "WebGL" in the title that cover only or 90% of the content Three.js. In the meantime organisations like Mozilla could start and ditch Three.js in favour WebGL. It would be in common interest of everone.
- k__ 11y ago
  JQuery was the way to go, because of API differences, so it was easier to write one example in JQuery than 5 in Vanilla JavaScript. WebGL is probably very hard to do in Vanilla JavaScript, so people are using Three.js...
- xixixao 11y ago
  Great analogy, wrong resolution. The situation is like jQuery, because WebGL is a TERRIBLE API for any but the most low level drawing code (remember, it's not even a 3D API, just a drawing API to interact with the graphics hardware). What will hopefully happen, as did with jQuery, that people will lean down the original and come up with better ways of doing the same (React3D(tm)). Where this analogy doesn't work is that jQuery mainly united the broken implementations across browsers, which is not a big problem with WebGL. So unless there is a committee for a higher level 3D graphics API we can't expect much from the browsers themselves.
  - __jack__ 11y ago
    Just because webgl has a more complex api compared to others in the browser world it doesnt mean that it is a terrible api. Its flexible, because you know its not a 3d api, its a 2d one flexible enough to be use for everything from 2d to 3d.
- 11y ago
pachydermic 11y ago
Thanks for sharing - not really interested in the 3d stuff yet, but the fact that they're doing tutorials like this is amazing!
tigeba 11y ago
A few years ago when I needed to write collision detection for a variety of specialized cases, I found the book "Real-Time Collision Detection". It is one of the few really comprehensive resources I was able to find on the topic. The example sources are C++ but the concepts apply to 3d in any domain. The website for the book is http://realtimecollisiondetection.net/ http://realtimecollisiondetection.net/
- vvanders 11y ago
  This is seriously the best technical book I've ever seen. It's basically 3D data structures but also with a focus on cache friendly-ness that you don't traditionally see anywhere else.
- deleted 11y ago
  [deleted]
hellbanner 11y ago
Doesn't run in Chrome - because of NPAPI?

The link seems to be the overview (with nifty demo) - the actual article is here: https://developer.mozilla.org/en-US/docs/Games/Techniques/3D_collision_detection https://developer.mozilla.org/en-US/docs/Games/Techniques/3D... I've been playing around with 3D for a while, and have found that collision detection is the (relatively) easy bit: it's collision resolution that messes me up!

talloaktrees 11y ago
Yes, you're exactly right. Resolution is the tricky part. I made a simple FPS game engine using Java + libgdx (https://github.com/jrenner/gdx-proto https://github.com/jrenner/gdx-proto), and it leveraged the bullet physics library for collision detection, but handling collision resolution myself. Even simple things like getting an object to to slide along a wall as it collides with it at an angle can be tricky.
- JupiterMoon 11y ago
  If you're already using bullet why not use if for collision resolution as well? Or if you want to manually change things try using ODE as this is more amiable towards doing so.
maccard 11y ago
Even detecting collisions accurately isn't easy. This is only between primitives (spheres and boxes). Detecting collisions between convex hulls (and more difficultly non-convex shapes) is quite difficult.
- chaosemer 11y ago
  Detecting collisions between two convex hulls isn't that hard, but it is slow-ish. The Separating Axis Theorem (or its more general and WAY COOLER SOUNDING Hyperplane Separation Theorem) lets you do a dot-product per face and if they all come out positive, there's no collision. https://en.wikipedia.org/wiki/Hyperplane_separation_theorem https://en.wikipedia.org/wiki/Hyperplane_separation_theorem
  - Animats 11y ago
    Convex collision detection is very fast with incremental GJK. When the axis-aligned bounding boxes for two objects intersect, you create an object pair and start GJK for the pair. It walks along the edges and faces of the polyhedra to find the shortest distance. This is O(log N) on the number of vertices. On the next frame, you rerun GJK starting from the previous result, and if the objects haven't moved much, look at 0 or 1 new edges, vertices, or faces. So the incremental approach is nearly constant time after the startup. Doing a dot-product for every face pair is O(N^2). Bad for large N. If you do this right, convex hulls with a few hundred faces are no problem. When constructing convex hulls for this, you can use a tool like QHull. Tell it that you want at least some minimal angle such as 1 degree at each edge. This will eliminate many near-coplanar faces. Also, it's better to use polygonal faces than triangular faces. With triangles, a rectangular face has two coplanar faces, and GJK will toggle between them, making resting object jiggle. (Basic annoyance of polyhedra and roundoff: if you tesselate, you get coplanar faces; if you use polygon faces, they're not perfectly flat.)
  - snaily 11y ago
    There's something about multidimensional geometry and great theorem names. I bring you the ham sandwich theorem: https://en.wikipedia.org/wiki/Ham_sandwich_theorem https://en.wikipedia.org/wiki/Ham_sandwich_theorem

frik 11y ago

As one of the linked articles is based on Three.js . It's like a plague that simple 3D examples and tutorials almost always features that Three.js library instead of "vanilla" Javascript with WebGL. People should learn WebGL and JS first and later decide if such a library is even suitable for their usecase (known to be slow). It reminds me of 2-3 years ago, where almost every Javascript tutorial was littered with JQuery library function calls. Most Stackoverflow questions were answered with JQuery answers. In the meantime things have obviously changed for the better. With Three.js it's still extreme, there are even several books with "WebGL" in the title that cover only or 90% of the content Three.js. In the meantime organisations like Mozilla could start and ditch Three.js in favour WebGL. It would be in common interest of everone.

k__ 11y ago
JQuery was the way to go, because of API differences, so it was easier to write one example in JQuery than 5 in Vanilla JavaScript. WebGL is probably very hard to do in Vanilla JavaScript, so people are using Three.js...
xixixao 11y ago
Great analogy, wrong resolution. The situation is like jQuery, because WebGL is a TERRIBLE API for any but the most low level drawing code (remember, it's not even a 3D API, just a drawing API to interact with the graphics hardware). What will hopefully happen, as did with jQuery, that people will lean down the original and come up with better ways of doing the same (React3D(tm)). Where this analogy doesn't work is that jQuery mainly united the broken implementations across browsers, which is not a big problem with WebGL. So unless there is a committee for a higher level 3D graphics API we can't expect much from the browsers themselves.
- __jack__ 11y ago
  Just because webgl has a more complex api compared to others in the browser world it doesnt mean that it is a terrible api. Its flexible, because you know its not a 3d api, its a 2d one flexible enough to be use for everything from 2d to 3d.
11y ago

pachydermic 11y ago

Thanks for sharing - not really interested in the 3d stuff yet, but the fact that they're doing tutorials like this is amazing!

tigeba 11y ago

A few years ago when I needed to write collision detection for a variety of specialized cases, I found the book "Real-Time Collision Detection". It is one of the few really comprehensive resources I was able to find on the topic. The example sources are C++ but the concepts apply to 3d in any domain. The website for the book is http://realtimecollisiondetection.net/ http://realtimecollisiondetection.net/

vvanders 11y ago
This is seriously the best technical book I've ever seen. It's basically 3D data structures but also with a focus on cache friendly-ness that you don't traditionally see anywhere else.
deleted 11y ago
[deleted]

hellbanner 11y ago

Doesn't run in Chrome - because of NPAPI?