HTML5 games: 3D collision detection | Hacker News Reader

HTML5 games: 3D collision detection

hacks.mozilla.org

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.

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...

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.

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.

I'm not a fan of using libraries for simple examples either, but WebGL just requires tons of boilerplate even for the simplest stuff.

If you just want to show a pixel shader, you probably don't need any library. Still, creating textures, setting up the buffer for your single quad, compiling pixel and vertex shaders and the shaders themselves will easily pile up to a good 100 lines of code.

Now, if you want to do anything with real 3d objects, such as in this example, you need code to:

  - generate or load the models
  - set up your camera
  - trace clicks on the canvas to the objects (not a simple feat in 3d space)
  - implement this mover widget/drag+drop of objects
  - implement some sort of lighting
  - implement some sort of shadow rendering, so it's easier to estimate 
    the position of the objects
  - (for all of the above) implement a library for 
    vector and matrix math

You'll easily end up with a thousand lines of code there, and you haven't done anything yet to solve the actual problem this article discusses.

I respectfully disagree. I write raw WebGL but I also have written 6 game engines. I'll never do that again. I just want to get shit done. That means for a game I'll start with Unity or Unreal.

Similarly for 3D most people just want to get shit done. In that case Three.js is a great way to to just get stuff done.

There's man years of work to do to a full 3d engine. You can easily spend a couple of man years just writing exporter/importers and trying to get every little piece of data out and into some meaningful way into your engine. People spend years making rendering systems and shader combiners and post processing system.

I'm not saying three.js is perfect but at least at some level much of that is already in there. Why should anyone skip all of that? Just to make years of extra work for themselves?

If you want to do raw WebGL then go for, but don't push that on others. To me that's like someone saying "you should write in assembly language". No, I'll choose something that provides existing solutions so I can move on to my actual content instead of re-inventing the wheel.

That's fine, but he makes a valid point about tutorials whose title makes it sound like it's a WebGL tutorial but mostly cover Three.js. It's like finding a tutorial about assembly, and having it be about C.

Hi, I'm the author the post.

I agree that it is important to know how things work without 3rd party helpers, regardless of whether you'd use a game engine / library later or not.

However, the post on the Hacks blog presents some articles and demos we created for the MDN and IMHO the title is appropriate, since one of the two articles introduced (https://developer.mozilla.org/en-US/docs/Games/Techniques/3D...) is generic and it's about algorithms in raw JavaScript.

I just thought there would be value too in showing how to do collision detection using one of the most popular 3D graphics library and a physics engine as well, since that would be the most common case when people are developing games (versus making an engine)

Just to be clear, I wasn't suggesting anything was wrong with your post (especially since it's about collision detection), just that there was valid point made in general.

I agree that if the thing you're trying to show is "Here's bounding volumes and intersections in 3D", then the Three usage just cleans up a secondary implementation detail. However, it seems to be rare that people will write "Oh, and the drawing part is just for visualization, ignore this code because it's convenient".

The problem with the wide spread of Three is that it is some crazy sprawly combination of utility library, engine, and framework, and that it encourages a particular worldview on new graphics programmers that don't have any understanding on how the underlying hardware or math works.

It's useful in the hands of somebody that already knows that stuff, but harmful from a pedagogical point of view.

They are showing off collision detection, not teaching you how to write OpenGL ES applications for the web. Take a low level graphics course, or write your own tutorial about this, and get back to us about how much time you actually want to spend setting up buffers for textures and vertices and normals and indices etc. and dealing with a low level state machine. They even have "hack" in the title of their site, like they are hacking it together.

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...

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!

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), 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.

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.

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.

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

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.)

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

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/

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.

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

Doesn't run in Chrome - because of NPAPI?

Reply on news.ycombinator.com