How to detect intersection of polyline and box

CesiumJS
1

Hi, everyone, does anybody know is there any function in Cesium to compute the intersections of a polyline and a box?

I find maybe the Cesium.IntersectionTests.lineSegmentTriangle function could do this, but a little complicated, need to let every linesegments in the polyline to intersect every triangles in the box(12 triangles at six face with 2 per face), is there any more direct functions?

Thanks.

2

Hi @wangqiuyan,

Unfortunately, I don’t know of any more direct API methods for doing a polyline-box intersection test. You’re right that the lineSegmentTriangle intersection test would work but would be a little overkill. You could write a more performant function yourself that directly tests line segments against boxes, rather than against triangles.

Here’s a starting point (admittedly drafted with some LLM help - so use with caution). Two functions, one to get an intersection of a line segment and an axis-aligned box. The other works for oriented bounding boxes.

// returns {hit: boolean, tmin, tmax} or {hit:false}
function lineSegmentAABB(p0, p1, aabbMin, aabbMax) {
  const dir = Cesium.Cartesian3.subtract(p1, p0, new Cesium.Cartesian3());
  let tmin = 0.0;
  let tmax = 1.0;
  const eps = 1e-12;

  for (let i = 0; i < 3; ++i) {
    const p0c = i === 0 ? p0.x : (i === 1 ? p0.y : p0.z);
    const dirc = i === 0 ? dir.x : (i === 1 ? dir.y : dir.z);
    const minc = i === 0 ? aabbMin.x : (i === 1 ? aabbMin.y : aabbMin.z);
    const maxc = i === 0 ? aabbMax.x : (i === 1 ? aabbMax.y : aabbMax.z);

    if (Math.abs(dirc) < eps) {
      // line is parallel to slab; must be inside slab to intersect
      if (p0c < minc || p0c > maxc) {
        return { hit: false };
      }
    } else {
      let t1 = (minc - p0c) / dirc;
      let t2 = (maxc - p0c) / dirc;
      if (t1 > t2) { const tmp = t1; t1 = t2; t2 = tmp; }
      if (t1 > tmin) tmin = t1;
      if (t2 < tmax) tmax = t2;
      if (tmin > tmax) return { hit: false };
    }
  }

  return { hit: true, tmin: tmin, tmax: tmax };
}


function lineSegmentOBBIntersect(p0, p1, obb) {
  // compute transform world->boxLocal
  const worldFromBox = Cesium.OrientedBoundingBox.computeTransformation(obb, new Cesium.Matrix4());
  const boxFromWorld = Cesium.Matrix4.inverseTransformation(worldFromBox, new Cesium.Matrix4());

  const p0Local = Cesium.Matrix4.multiplyByPoint(boxFromWorld, p0, new Cesium.Cartesian3());
  const p1Local = Cesium.Matrix4.multiplyByPoint(boxFromWorld, p1, new Cesium.Cartesian3());

  // half extents = lengths of the columns of obb.halfAxes
  const col0 = Cesium.Matrix3.getColumn(obb.halfAxes, 0, new Cesium.Cartesian3());
  const col1 = Cesium.Matrix3.getColumn(obb.halfAxes, 1, new Cesium.Cartesian3());
  const col2 = Cesium.Matrix3.getColumn(obb.halfAxes, 2, new Cesium.Cartesian3());
  const hx = Cesium.Cartesian3.magnitude(col0);
  const hy = Cesium.Cartesian3.magnitude(col1);
  const hz = Cesium.Cartesian3.magnitude(col2);

  const min = new Cesium.Cartesian3(-hx, -hy, -hz);
  const max = new Cesium.Cartesian3( hx,  hy,  hz);

  return lineSegmentAABB(p0Local, p1Local, min, max);
}

Again, take a look and treat with caution. For example, I would use scratch variables instead of making new Cartesian3’s and Matrix3’s for every function call.

3

Hi @mzschwartz5

Thanks for your suggestion. The intersect AABB function is helpful in the situation.