playcanvas / playcanvas/engine
ElementInput: `intersectLineQuad` makes up intersections
Nobody has claimed this yet.
- 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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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