Calculate OBB from rotated cube-buffergeometry (manually)

[cabada]

Hello everyone,

I’m trying to calculate an OBB manually from an unknown rotated Cube-BufferGeometry mesh.

Since there is no setFromObject method for OBB, it must be done manually.

My findings so far:

For building an OBB, 3 parameters are needed: center, halfSize and rotation.

I’ve already calculated the center of the BufferGeometry, which was pretty straight forward:

1. Got all local positions of the corners of the mesh from the BufferGeometryAttribute (8 corners in total) and added them together (Obviously separeted by X, Y, Z)
2. Divided these sums by 8, so I get the exact center of the rotated box.

But I’m getting confused on how to get the halfSize and rotation out of this, and it’s not just calculating the distance from the center to any vertex, since everything is rotated.

This is an example of how the cube-geometry looks. It’s important to mention that the rotation of the object is (0, 0, 0), the vertices positions are the ones that make it look rotated.

So how to calculate the halfSize and rotation of the OBB?

One of the ideas that I came up to try to achieve this is to:

1. First calculate the rotation of the object.
2. Then after having the rotation, I can normalize the geometry’s matrix so it has no rotation
3. Then I can calculate the halfSize for every axis

But I also find this hard and confusing to try, and don’t even know if it’d be a correct way of doing it.

Goal is to have a way to generate a OBB from any cube-geometry, even when they are randomly rotated within their local space.

I also think this can help Three.JS in a way to develop the missing setFromObject methods for the OBB?

Thanks in advance.

[Mugen87]

@cabada

I also think this can help Three.JS in a way to develop the missing setFromObject methods for the OBB?

Just working with cube geometries won’t help much. Implementing OBB.setFromObject() is tricky since the related algorithms for computing the minimum enclosing OBB are complicated and do not always produce expected results. I’ve implemented such a method for Yuka based on Collision Queries using Oriented Bounding Boxes. However, since this approach has problems with certain edge cases (it does not compute good OBBs for certain symmetric shapes), I doubt the implementation will be accepted in the three.js repo.

You can see Yuks’s OBB implementation in the following example that compares different types of bounding volumes for a typical game asset: Yuka | Bounding Volumes

A more accurate but more complex implementation would be An Exact Algorithm for Finding Minimum Oriented Bounding Boxes. If you are interested in this topic, it might be worth to study the paper and figure at a JS implementation.

[cabada]

Thanks for the links, will check them out.

One thing to mention is that I cannot do too much computational processes cause I’m calculating the OBB for hundreds/thousands of pieces at a time.

If I want to do for just simple cubes, no complex objects, would my approach still not feasible?

(don’t really care about how accurate it is. It does not have to be perfect for my implementation)

[makc3d]

Ive done this before for one job using Principal component analysis - Wikipedia this basically finds ordered set of axes that vertices are distributed along the most to the least, which form the basis of transformation matrix for the box you are looking for. The method always works, but the axes might flip around wildly if you move the vertices even by tiny bit.

The code I used as a reference could be borrowed here, btw. I think. It looks similar.

[anidivr]

Does this work?

    let box3 = mesh.geometry.boundingBox;
    if (!box3) {
      mesh.geometry.computeBoundingBox();
      box3 = mesh.geometry.boundingBox;
    }
    if (box3) {
      this._obb.fromBox3(box3)
      this._obb.halfSize.copy(box3.getSize(new Vector3())).multiplyScalar(0.5);
      // now rotate the OBB object to mesh rotation
      this._obb.applyMatrix4(mesh.matrixWorld);

      this._obb.intersectXXX();  // perform intersection test
  }

[cabada]

This would only work if the mesh was axis-oriented, which is not the case. And I cannot force it to be axis-oriented to calculate the bounding box, cause orientation is not even assigned at mesh-level, but more like a result of how the vertex are positioned

[cabada]

Thanks @Mugen87

This really helped! I got it working with the Yuka example, plus it’s amazing it has ConvexHull calculation as well. I’ll keep playing around with it to see how far it can go for my use-case.