Proper ellipsoid support.

[kevzettler]

The current implementation only uses a scalar value to represent the radius of the supposed ellipsoid. The original paper demonstrates support for a Vec3 to represent the ellipsoid and uses this to calculate a "Change of basis" Mat3 that is then applied to the collision tests.

I believe the scalar radius is a deviation from the papers original intended algorithm. But it might be a math shortcut i'm misunderstanding. If it is a deviation that means this current implementation with the scalar radius is strictly a sphere-to-triangle collision and not full ellipsoid.

I have been able to reproduce the CBM ellipsoid version of the algorithm in another implementation and will leave this issue open as a reminder and incase anyone else encounters this.

[mreinstein]

@kevzettler you mentioned having ellipsoid support in another implementation, how far along is this? I'm thinking about doing the same thing for a 2d version of this module, and it'd be great to re-use if you have something far enough along.

[kevzettler]

@mreinstein I have it working however its a complicated story. The implementation I have it working is more of a rewrite and it is tightly coupled and dependent on the Mobx library. I can try and summarize the changes.

You will want to construct a CBM matrix that looks like

    this.CBM = [
      1/eRadius[0], 0, 0,
      0, 1/eRadius[1], 0,
      0, 0, 1/eRadius[2],
    ];

eRadius should be a vector defining the radii of your ellipsoid

Anywhere the current implementation converts to eSpace using invRadius like:

https://github.com/kevzettler/gl-swept-sphere-triangle/blob/master/src/index.js#L152-L154

you want to change to the CBM transformation. That will convert a vector or point in to eSpace. To then transform back to R3 space you transform with an inverted CBM mat3.invert(this.iCBM, this.CBM);

Of course this is 3D and i'm not sure how the 2d case would look

[mreinstein]

Ah ok.

so is this sitting in a branch because some other project using mobx is using this, and you wanted tighter integration, or are you planning to re-write this existing module to use mobx?

It seems like an odd thing to couple to this largely independent collision routine, but I get that I completely lack context.

[kevzettler]

@mreinstein the mobx implementation is part of a larger game engine in which I also calculate collision response vectors. This gl-swept-sphere-triangle module purely handles detection and not response.

I found it was more optimal to reuse data structures between the detection and response phases in the engine. This data structure reuse required alterations to the code from this module. During that rewrite I also updated the detection phase to use the proper ellipsoid calculations.

There is opportunity to update the ellipsoid calculations of this module I don't personally have to capacity to do that work at the moment.

[mreinstein]

There is opportunity to update the ellipsoid calculations of this module I don't personally have to capacity to do that work at the moment.

I totally get that 👍 and don't mean to inundate you with discussion points here. :) I'm happy to take a stab at it, since I need this for the 2d case, and it's not radically different logic for the 3d case (probably just going 1D up from the 2d vectors and matrices used :) )

Another thing I've considered refactoring is the traceinfo object. I'd like to move to a pure data-oriented, functional structure. If that is something you'd also find agreeable I'm happy to send a PR for that too.

[mreinstein]

sorry for disappearing for a while, I was working on the 2d version of this, along with some other collision related things. I got this working in 2d with ellipsoids:

when loading the collidableLines:

const ellipsoidRadius = vec2.fromValues(2, 5)  // width, height radii of ellipsoid

// each line is an array of 2 vec2s: [ startPoint, endPoint ]
for (const line of collidableLines) {
    vec2.divide(line[0], line[0], ellipsoidRadius)
    vec2.divide(line[1], line[1], ellipsoidRadius)
}

when colliding:

function collideAndSlide (lines, position, ellipsoidRadius, moveVel, contact) {
    // convert position and velocity into ellipsoid space
    const eSpacePosition = vec2.divide(vec2.create(), position, ellipsoidRadius)
    const eSpaceVelocity = vec2.divide(vec2.create(), moveVel, ellipsoidRadius)

    // the lines, position, and moveVel have already been normalized into sphere space,
    // so set the sphere radius to 1.0
    sphereRadius = 1.0
    const finalPosition = collideWithWorld(lines, eSpacePosition, sphereRadius, eSpaceVelocity, contact)
}

Another nice optimization for this would be to pre-calculate all of the line/triangle normals, but I haven't bothered with that yet since I'm mostly dealing with a small number of potential colliders thanks to a reasonable broadphase cull step.

I would imagine this same exact logic should work for 3d, by just replacing vec2 with vec3, and lines with triangles.