Creating contacts for a custom shape (voxel terrain)

fenomas commented 8 years ago

Hi, thanks for your earlier help with this.

I now have a custom shape for voxel terrain that collides spheres, and which seems to work, within a first approximation. But it seems to be very slightly nonphysical in some cases - e.g. a sphere rolling slowly across a voxel boundary. I wonder if you could take a look at the way I'm creating the contacts and normals, and see if things look off?

What I'm specifically doing is creating a contact at the point on the voxel's surface which is closest to the sphere center. Not sure if this is what cannon expects, or if it should be on the sphere's surface, or in between, or if each shape should get a point on its own surface, etc.

Here is the demo with the implementation - important bit is lines 50 - 70. Thanks!

<!DOCTYPE html>
<html>

<head>
  <title>cannon.js - voxels demo</title>
  <meta charset="utf-8">
  <link rel="stylesheet" href="css/style.css" type="text/css" />
  <meta name="viewport" content="width=device-width, user-scalable=no, minimum-scale=1.0, maximum-scale=1.0">
</head>

<body>
  <script src="../build/cannon.js"></script>
  <script src="../build/cannon.demo.js"></script>
  <script src="../libs/dat.gui.js"></script>
  <script src="../libs/Three.js"></script>
  <script src="../libs/TrackballControls.js"></script>
  <script src="../libs/Detector.js"></script>
  <script src="../libs/Stats.js"></script>
  <script src="../libs/smoothie.js"></script>
  <script>

CANNON.Shape.types.VOXELS = 512;

var Narrowphase = CANNON.Narrowphase;
var Shape = CANNON.Shape;

var _tempvec1 = new CANNON.Vec3()
function square(x) { return x * x }

Narrowphase.prototype[Shape.types.SPHERE | Shape.types.VOXELS] =
  Narrowphase.prototype.sphereVoxels = sphereVoxels_impl_HF

function sphereVoxels_impl_HF(si, sj, xi, xj, qi, qj, bi, bj) {
  // i is sphere, j is voxels
  var radius = si.radius
  var query = sj.query

  // iterate over all voxels touched by the body
  var i0 = Math.floor(xi.x - radius)
  var i1 = Math.floor(xi.x + radius)
  var j0 = Math.floor(xi.y - radius)
  var j1 = Math.floor(xi.y + radius)
  var k0 = Math.floor(xi.z - radius)
  var k1 = Math.floor(xi.z + radius)

  for (var i = i0; i <= i1; ++i) {
    for (var j = j0; j <= j1; ++j) {
      for (var k = k0; k <= k1; ++k) {
        if (!query(i, j, k)) continue

        // find point on surface of AABB closest to sphere
        var contact = _tempvec1
        contact.x = (xi.x < i) ? i : (xi.x > i + 1) ? i + 1 : xi.x
        contact.y = (xi.y < j) ? j : (xi.y > j + 1) ? j + 1 : xi.y
        contact.z = (xi.z < k) ? k : (xi.z > k + 1) ? k + 1 : xi.z

        // distance check from point of contact to sphere center
        if (xi.distanceSquared(contact) > radius * radius) continue

        // definitely colliding - create the contact
        var r = this.createContactEquation(bi, bj, si, sj)

        // sphere's contact normal - sphere center to contact point
        contact.vsub(xi, r.ni)
        r.ni.normalize()

        // positions - from body center to contact point 
        contact.vsub(bi.position, r.ri)
        contact.vsub(bj.position, r.rj)

        // finish
        this.result.push(r)
        this.createFrictionEquationsFromContact(r, this.frictionResult)
      }
    }
  }
}

CANNON.VoxelShape = function(queryFn) {
  CANNON.Shape.call(this);

  /**
   * @property {Function} query
   */
  this.query = queryFn;
  this.type = CANNON.Shape.types.VOXELS;

  if (!queryFn) {
    throw new Error('Voxel shape needs a voxel-solidity query function.');
  }

  this.updateBoundingSphereRadius();
};
CANNON.VoxelShape.prototype = new CANNON.Shape();
CANNON.VoxelShape.prototype.constructor = CANNON.VoxelShape;

CANNON.VoxelShape.prototype.calculateLocalInertia = function(mass, target) {
  target = target || new CANNON.Vec3();
  target.set(0, 0, 0);
  return target;
};

CANNON.VoxelShape.prototype.volume = function() {
  return Number.MAX_VALUE;
};

CANNON.VoxelShape.prototype.updateBoundingSphereRadius = function() {
  this.boundingSphereRadius = Number.MAX_VALUE;
};

CANNON.VoxelShape.prototype.calculateWorldAABB = function(pos, quat, min, max) {
  min.set(-Number.MAX_VALUE, -Number.MAX_VALUE, -Number.MAX_VALUE);
  max.set(Number.MAX_VALUE, Number.MAX_VALUE, Number.MAX_VALUE);
};

/**
 * Demos of the Body.type types.
 */
var demo = new CANNON.Demo();
demo.currentMaterial.wireframe = true
demo.settings.contacts = true
demo.settings.normals = true

function getVoxels(i, j, k) {
  var ri = i
  var rj = j-1
  var rk = 17-k
  return (ri*ri + rj*rj + rk*rk > 350)
}

function rand(a,b) { return a + (b-a)*Math.random() }

function addDynamicSphere(world, mass, mat) {
  var b2 = new CANNON.Body({
    mass: mass,
    shape: new CANNON.Sphere(rand(0.3, 1.2)),
    position: new CANNON.Vec3(rand(5,-5), rand(0,-4), rand(5,10) ),
    material: mat
  });
  world.addBody(b2);
  demo.addVisual(b2);
}

function addStaticBox(size, x, y, z, world, mat) {
  var b2 = new CANNON.Body({
    shape: new CANNON.Box(new CANNON.Vec3(size/2, size/2, size/2)),
    mass: 0,
    position: new CANNON.Vec3(x, y, z),
    material: mat
  });
  world.addBody(b2);
  demo.addVisual(b2);
}

demo.addScene("Voxels",function(){

    var world = demo.getWorld();
    world.gravity.set(0,0,-10);

    var mat = new CANNON.Material({
      restitution: 0.8,
      friction: 0.1
    })

    for (var i=0; i<5; i++) {
      addDynamicSphere(world, 1, mat)
    }

    // add custom voxel shape/body
    var body = new CANNON.Body({
      mass: 0,
      position: new CANNON.Vec3(0, 0, 0),
      shape: new CANNON.VoxelShape(getVoxels),
      material: mat,
    });
    world.addBody(body);

  });

demo.start();

CANNON.Demo.prototype.addVoxelVisuals = function(query){
    var obj = new THREE.Object3D();
    for (var i=-6; i<7; i++) {
        for (var j=-6; j<7; j++) {
            for (var k=-2; k<4; k++) {
                if (!query(i,j,k)) continue
                var geom = new THREE.BoxGeometry(1, 1, 1);
                var mesh = new THREE.Mesh( geom, this.currentMaterial );
                mesh.receiveShadow = true;
                mesh.castShadow = true;
                mesh.position.set(i + 0.5, j + 0.5, k + 0.5);
                obj.add(mesh);
            }
        }
    }
    this.scene.add(obj)
}
demo.addVoxelVisuals(getVoxels)

  </script>
</body>
</html>

schteppe commented 8 years ago

Looks like both .ri and .rj vectors go to the same point, which is wrong. The vectors need to go to the surface on the respective body. Wish I could give you the fix but I'm currently on the phone.

Internally, the solver use these two vectors to check how much the bodies are overlapping. If they go to the same point, the overlap would always be zero and no contacts would need to be solved...

The easiest way to solve this would be to use the .sphereBox method instead. It's already done, why not use it?

fenomas commented 8 years ago

Thanks, setting the two contacts to their respective surfaces solved the problem!

As for why I didn't use .sphereBox, I tried to, and couldn't get it to work - but now that I try it again it seems to work fine. Though I guess my version should be faster, since it can assume each voxel box is static and fixed size and axis-aligned.

By the way, it looks like .sphereBox can create more than one contact for each sphere/box pair, for the box's face, edge and corner. My naive version just creates a single contact at whatever point on the box's surface is closest to the sphere's center. Are more contacts necessary for things to work correctly?

schteppe commented 8 years ago

Great! Actually 1 contact is enough. The problem is the normal. You probably want a different normal vector depending on if it's on a side, edge or corner. It should always point straight out of the sides, right? and on the corner you probably want the normal to point from the corner to the center of the sphere. If this is not the case, you will get a weird contact behavior.

fenomas commented 8 years ago

Yes, this is what I'm doing - I find the point on the box's surface closest to the sphere (which might be on a face or an edge or a corner), and then set the normal to be the vector from that point to the sphere's center. Is that the right idea? If so then I was just wondering .sphereBox handles things as three separate cases.

schteppe commented 8 years ago

That's one way to solve it and I'm not sure what the result will be - I'm curious to see how it goes.

.sphereBox does 3 cases depending on if it's a vertex/side/corner collision. Maybe this is not needed. If you could verify this I'd be happy!

fenomas commented 8 years ago

Sure, I'd like to look at this. Is there any particular test content I can check to compare the results to the current implementation?

schteppe commented 8 years ago

Cool. I guess you could try the stacks demo (demos/stacks.html), to see if the sphere/box stuff behaves weirdly. Go through all the cases in the dat.gui list to the right. Also would be nice to see what happens with larger penetrations. Maybe the FPS demo (examples/threejs_fps.html) could test that. Shoot spheres at the boxes, particularly at the corners & edges.

schteppe / cannon.js

Creating contacts for a custom shape (voxel terrain) #287