playcanvas / playcanvas/engine

ElementInput: `intersectLineQuad` makes up intersections

Open
#4,928 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

area: ui
Dominant language
JavaScript
Stars
16.8k
Forks
2k
Avg merge
4h 32m
Merged PRs (30d)
222

Description

There is an issue that one can click 3D buttons while standing behind them. I traced this issue down to intersectLineQuad:

const _pq = new pc.Vec3();
const _pa = new pc.Vec3();
const _pb = new pc.Vec3();
const _pc = new pc.Vec3();
const _pd = new pc.Vec3();
const _m = new pc.Vec3();
const _au = new pc.Vec3();
const _bv = new pc.Vec3();
const _cw = new pc.Vec3();
const _ir = new pc.Vec3();
const _sct = new pc.Vec3();
// pi x p2 * p3
function scalarTriple(p1, p2, p3) {
    return _sct.cross(p1, p2).dot(p3);
}
// Given line pq and ccw corners of a quad, return the square distance to the intersection point.
// If the line and quad do not intersect, return -1. (from Real-Time Collision Detection book)
function intersectLineQuad(p, q, corners) {
    _pq.sub2(q, p);
    _pa.sub2(corners[0], p);
    _pb.sub2(corners[1], p);
    _pc.sub2(corners[2], p);

    // Determine which triangle to test against by testing against diagonal first
    _m.cross(_pc, _pq);
    let v = _pa.dot(_m);
    let u;
    let w;

    if (v >= 0) {
        // Test intersection against triangle abc
        u = -_pb.dot(_m);
        if (u < 0)
            return -1;

        w = scalarTriple(_pq, _pb, _pa);
        if (w < 0)
            return -1;

        const denom = 1.0 / (u + v + w);
      
        _au.copy(corners[0]).mulScalar(u * denom);
        _bv.copy(corners[1]).mulScalar(v * denom);
        _cw.copy(corners[2]).mulScalar(w * denom);
        _ir.copy(_au).add(_bv).add(_cw);
    } else {
        // Test intersection against triangle dac
        _pd.sub2(corners[3], p);
        u = _pd.dot(_m);
        if (u < 0)
            return -1;

        w = scalarTriple(_pq, _pa, _pd);
        if (w < 0)
            return -1;

        v = -v;

        const denom = 1.0 / (u + v + w);

        _au.copy(corners[0]).mulScalar(u * denom);
        _bv.copy(corners[3]).mulScalar(v * denom);
        _cw.copy(corners[2]).mulScalar(w * denom);
        _ir.copy(_au).add(_bv).add(_cw);
    }

    // The algorithm above doesn't work if all the corners are the same
    // So do that test here by checking if the diagonals are 0 (since these are rectangles we're checking against)
    if (_pq.sub2(corners[0], corners[2]).lengthSq() < 0.0001 * 0.0001) return -1;
    if (_pq.sub2(corners[1], corners[3]).lengthSq() < 0.0001 * 0.0001) return -1;

    return _ir.sub(p).lengthSq();
}
const origin = new pc.Vec3(0, 20, 10);
const end    = new pc.Vec3(0, 20, 20);
const corners = [
  new pc.Vec3( -92,  6, 5),
  new pc.Vec3( 164,  6, 5),
  new pc.Vec3( 164, 70, 5),
  new pc.Vec3( -92, 70, 5),
];
const ret1 = intersectLineQuad(origin, end   , corners);
const ret2 = intersectLineQuad(end   , origin, corners);
console.log({ret1, ret2});

The z coordinate is the most interesting here, the "plane" (of the corners) is at z=5, while origin/end go from 10 to 20 meaning there is no possible intersection.

If ret1 is -1, ret2 should always be -1 aswell, as there cannot be an intersection if you simply swapped origin/end.

But the result I get is: {ret1: -1, ret2: 225}

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by locating intersectLineQuad in ElementInput and reproduce the reported origin/end and reversed-endpoint cases from the issue. Check the intersection result for a line entirely in front of the quad; done means the function returns -1 for both endpoint orders and does not report a false intersection.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript
Domain
computer-graphics
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.