Accurate bounding box of an object

Question

I'm trying to create an accurate bounding box of an object, but it appears that if the object isn't aligned with the axis (I think) the box is not aligned with the object.

For example:

The pink and closer orange vertices are the Box3.min, Box3.max of this wall, but you see the red and green and blue are not on that wall. You can ignore the aqua vertices.

This is the code that creates the bounding box (returns Box3):

  static getWorldBoundingBox(model, dbId) {

    return new Promise(async(resolve, reject)=>{

      try{

        var fragIds = await ViewerToolkit.getFragIds(
          model, dbId);

        if(!fragIds.length){

          return reject('No geometry, invalid dbId?');
        }

        var fragList = model.getFragmentList();

        var fragbBox = new THREE.Box3();
        var nodebBox = new THREE.Box3();

        fragIds.forEach(function(fragId) {

          fragList.getWorldBounds(fragId, fragbBox);
          nodebBox.union(fragbBox);
        });

        return resolve(nodebBox);
      }
      catch(ex){

        return reject(ex);
      }
    });
  }

And that's how I create the box from the min, max:

    let ddd = new THREE.Vector3(min.x, min.y, min.z);
    let ddu = new THREE.Vector3(min.x, min.y, max.z);
    let dud = new THREE.Vector3(min.x, max.y, min.z);
    let udd = new THREE.Vector3(max.x, min.y, min.z);

    let duu = new THREE.Vector3(min.x, max.y, max.z);
    let uud = new THREE.Vector3(max.x, max.y, min.z);
    let udu = new THREE.Vector3(max.x, min.y, max.z);
    let uuu = new THREE.Vector3(max.x, max.y, max.z);

    this.drawVertices([ddd,ddu,dud,udd,duu,uud,udu,uuu]);

    let facesPoints = [
        {
            BL: ddd.clone(),
            UL: ddu.clone(),
            UR: udu.clone(),
            BR: udd.clone()
        },
        {
            BL: udd.clone(),
            UL: udu.clone(),
            UR: uuu.clone(),
            BR: uud.clone()
        },
        {
            BL: uud.clone(),
            UL: uuu.clone(),
            UR: duu.clone(),
            BR: dud.clone()
        },
        {
            BL: dud.clone(),
            UL: duu.clone(),
            UR: ddu.clone(),
            BR: ddd.clone()
        }
    ];

I want to avoid a brute force approach of sorting all distances of all pairs of vertices and taking the first two.

Is there another data structure will expose 8 points of a cube instead of just 2 that I could give to it polygons to build it just like in the above function?

Answer 1

I found a way to do this, first I collected all the vertices to a general set using this function from Autodesk's viewer extensions (Mesh data):

  static getMeshVertices(viewer, fragId) {

    var fragProxy = viewer.impl.getFragmentProxy(
      viewer.model,
      fragId);

    var renderProxy = viewer.impl.getRenderProxy(
      viewer.model,
      fragId);

    fragProxy.updateAnimTransform();

    var matrix = new THREE.Matrix4();
    fragProxy.getWorldMatrix(matrix);

    const verticesSet = new GeneralSet();
    const geometry = renderProxy.geometry;
    const attributes = geometry.attributes;

    if (attributes && attributes.index !== undefined) {

      const indices = attributes.index.array || geometry.ib;
      const positions = geometry.vb ? geometry.vb : attributes.position.array;
      const stride = geometry.vb ? geometry.vbstride : 3;
      let offsets = geometry.offsets;

      if (!offsets || offsets.length === 0) {

        offsets = [{ start: 0, count: indices.length, index: 0 }];
      }

      for (var oi = 0, ol = offsets.length; oi < ol; ++oi) {

        const start = offsets[oi].start;
        const count = offsets[oi].count;
        const index = offsets[oi].index;

        for (var i = start, il = start + count; i < il; i += 3) {

          const vA = new THREE.Vector3();
          const vB = new THREE.Vector3();
          const vC = new THREE.Vector3();
          const a = index + indices[i];
          const b = index + indices[i + 1];
          const c = index + indices[i + 2];

          vA.fromArray(positions, a * stride);
          vB.fromArray(positions, b * stride);
          vC.fromArray(positions, c * stride);

          vA.applyMatrix4(matrix);
          vB.applyMatrix4(matrix);
          vC.applyMatrix4(matrix);

          verticesSet.add(vA);
          verticesSet.add(vB);
          verticesSet.add(vC);
        }
      }

      return verticesSet;
    }
    else {

      var positions = geometry.vb ? geometry.vb : attributes.position.array;
      var stride = geometry.vb ? geometry.vbstride : 3;

      for (var i = 0, j = 0, il = positions.length; i < il; i += 3, j += 9) {
        let vA = new THREE.Vector3();
        let vB = new THREE.Vector3();
        let vC = new THREE.Vector3();
        var a = i;
        var b = i + 1;
        var c = i + 2;

        vA.fromArray(positions, a * stride);
        vB.fromArray(positions, b * stride);
        vC.fromArray(positions, c * stride);

        vA.applyMatrix4(matrix);
        vB.applyMatrix4(matrix);
        vC.applyMatrix4(matrix);

        verticesSet.add(vA);
        verticesSet.add(vB);
        verticesSet.add(vC);
      }

      return verticesSet;
    }
  }

Then I used a graph diameter algorithm from here: https://cs.stackexchange.com/a/213/43035 once on the set of vertices (as if the set represent a complete graph) to get two opposite corners, lets call them u, w.

Then I removed u, w from the set of vertices and ran the graph diameter again, getting the two other corners.

Now with four corners it's possible to generate all the rest, and to sort them, there are 3 conditions to check for each of the 4 corners (which will reveal the 4 other corners), distance from camera (closer or further), height (upper or lower corner) and left or right from the middle of the object (using a cross and dot, like this https://forum.unity3d.com/threads/left-right-test-function.31420/ (they have js code)).

This will give you 8 corners such that you'll know which corner is where, and the corners are on the object, it doesn't matter how the object is aligned with the axes.