Is this a bug? Very different BoundingSphere values between Points and InstancedMesh objects, even though they are using the same point/instance locations

Questions
, , , ,
1

In three.js, I have a Points object and an InstancedMesh object. They both contain points/instances at the following locations:

const pointsData = [
  { x: -7505.97314453125, y: 182.7720489501953, z: 6319.98291015625 },
  { x: -3888.849853515625, y: 104.75480651855469, z: -8840.5166015625 },
  { x: 6898.529296875, y: 342.9034423828125, z: -495.22833251953125 },
  { x: 10786.9365234375, y: 311.8286437988281, z: 5985.064453125 },
];

The instances in the InstancedMesh are very tiny spheres with radius = 0.001 to mimic “points”.

When I calculate the BoundingSphere for the Points geometry and then for the InstancedMesh, and compare each of their BoundingSpheres, I get significantly different BoundingSphere values (center and radius) between the Points and InstancedMesh objects, even though they are using the same point/instance locations. The difference outweighs any effect that the tiny sphere geometry radius may have. Here are the values:


points.geometry.boundingSphere.center
x: 1640.481689453125
y: 223.8291244506836
z: -1260.266845703125

points.geometry.boundingSphere.radius
11879.373218935876

instancedMesh.boundingSphere.center
x: -807.2474263273366
y: 204.7621198590103
z: 137.41963115252497

instancedMesh.boundingSphere.radius
12985.820753310756

Is this a bug? Or am I doing something wrong? Here is my code:

JSFiddle: Edit fiddle - JSFiddle - Code Playground

import * as THREE from 'three';

(async function () {
  const renderer = new THREE.WebGPURenderer({});
  await renderer.init();
  renderer.outputColorSpace = THREE.LinearSRGBColorSpace;
  const scene = new THREE.Scene();
  const body = document.body;
  const camera = new THREE.PerspectiveCamera(
    70,
    body.offsetWidth / body.offsetHeight,
    0.01,
    1000,
  );
  camera.position.x = 0;
  camera.position.y = 0;
  camera.position.z = 20;
  scene.add(camera);
  const canvas = renderer.domElement;
  canvas.style.position = 'absolute';
  canvas.style.inset = '0';
  body.appendChild(canvas);

  setCanvasSize();

  function setCanvasSize() {
    renderer.setSize(body.offsetWidth, body.offsetHeight);
    camera.aspect = body.offsetWidth / body.offsetHeight;
    camera.updateProjectionMatrix();
    setTimeout(setCanvasSize, 1000);
  }

  const pointsData = [
    { x: -7505.97314453125, y: 182.7720489501953, z: 6319.98291015625 },
    { x: -3888.849853515625, y: 104.75480651855469, z: -8840.5166015625 },
    { x: 6898.529296875, y: 342.9034423828125, z: -495.22833251953125 },
    { x: 10786.9365234375, y: 311.8286437988281, z: 5985.064453125 },
  ];

  {
    const positions = new Float32Array(pointsData.length * 3);
    pointsData.forEach((p, i) => {
      positions[i * 3] = p.x;
      positions[i * 3 + 1] = p.y;
      positions[i * 3 + 2] = p.z;
    });

    const geometry = new THREE.BufferGeometry();
    geometry.setAttribute('position', new THREE.BufferAttribute(positions, 3));
    geometry.computeBoundingBox();
    geometry.computeBoundingSphere();
    const center = geometry.boundingSphere.center;
    document.getElementById('pointsCenterElem').innerHTML = `
    x: ${center.x}<br/>
    y: ${center.y}<br/>
    z: ${center.z}
    `;
    const radius = geometry.boundingSphere.radius;
    document.getElementById('pointsRadiusElem').innerHTML = radius;

    const material = new THREE.PointsMaterial({
      color: 0xffffff,
      size: 0.1,
    });

    const points = new THREE.Points(geometry, material);
    scene.add(points);
  }

  {
    const geometry = new THREE.SphereGeometry(0.001, 8, 8);
    geometry.computeBoundingBox();
    geometry.computeBoundingSphere();
    const material = new THREE.MeshBasicMaterial({
      color: 0xffffff,
    });
    const instancedMesh = new THREE.InstancedMesh(
      geometry,
      material,
      pointsData.length,
    );
    const temp = new THREE.Object3D();
    pointsData.forEach((p, i) => {
      temp.position.set(p.x, p.y, p.z);
      temp.updateMatrix();
      instancedMesh.setMatrixAt(i, temp.matrix);
    });
    instancedMesh.computeBoundingBox();
    instancedMesh.computeBoundingSphere();
    const center = instancedMesh.boundingSphere.center;
    document.getElementById('instancedMeshCenterElem').innerHTML = `
    x: ${center.x}<br/>
    y: ${center.y}<br/>
    z: ${center.z}
    `;
    const radius = instancedMesh.boundingSphere.radius;
    document.getElementById('instancedMeshRadiusElem').innerHTML = radius;
    scene.add(instancedMesh);
  }

  render();

  function render() {
    renderer.render(scene, camera);
    requestAnimationFrame(render);
  }
})();
2

There’s a misconception going on here. boundingSphere is not what you think.

It’s a conservative bounding shape, meaning that it can and often is - larger than the optimal bounding sphere.

It seems silly perhaps, since we can do it for a bounding box, but for a sphere - it’s a much harder problem.

Typically, you compute a bounding box, and then just inscribe a sphere over it. Something like this:

sphere_center = box.center;
sphere_radius = box.size.length() * Math.SQRT1_2; // Math.hypon( size.x, size.y ,size.z)

To further confuse thing, computing bounds from vertices is slow. You have to go over EVERY vertex in the mesh, so we cheat. We compute bounds for a geometry and then when we apply some position / rotation / scale to a mesh - we don’t rebuild the bounds from vertices, we just transform the bounding shape for the geometry.

This is conservative, the shape that we get through these transformations is guaranteed to fit all vertices, but it’s almost always going to be larger than the tightly fitter bounding shape.

All that to say - don’t trust your .boundingSphere, and don’t trust .boundingBox on a mesh.

Why is it like that?

Because bounds exist primarily for frustum culling, those tests need to be conservative. That is - we can accept false positives, but false negatives are a no-go.

Can we do better?

Yes! There are better algorithms for calculating bounds spheres. As a shameless plug, here’s one from meep that calculates close to optimal bounding sphere using an algorithm from “Fast Smallest-Enclosing-Ball Computation in High Dimensions” paper:

/**
 *
 * @param {BufferGeometry} geometry
 * @returns {Vector4} x,y,z are sphere center and w is radius
 */
function computeGeometryBoundingSphereMiniball(geometry: BufferGeometry ) : Vector4

That algorithm is exceptionally good at computing tight bounds and often has half the volume of what three.js produces by default.

Finally, produces an actual smallest possible bounding sphere.

2 Likes
3

Thanks, that explains everything.

Edit: I’m checking out the source for your meep engine to see the implementation for computeGeometryBoundingSphereMiniball().

1 Like