When I use Box3.setFromObject
to compute the bounding box of the an Object3D
, I was expecting it to return the AABB in local coordinates aligned to the local frame within the specified object, but instead it returns an AABB in world coordinates. I was wondering if would be good to add an option to this function to allow either local or world AABB to be returned?
I made a wrapper function that implements this option by temporarily setting the local matrix to the inverse of the worldMatrix of its parent object, but it seems like a messy and inefficient solution.
public getBounds(coords: CoordinateSystem): Box3 {
this._object3D.updateMatrix();
let oldMatrix = this._object3D.matrix;
let oldMatrixAutoUpdate = this._object3D.matrixAutoUpdate;
if (coords === CoordinateSystem.LOCAL) {
this.updateMatrixWorld();
let m = new Matrix4();
if (this.getParent() !== null)
{
m.getInverse(this._object3D.parent.matrixWorld, false);
}
this._object3D.matrix = m;
// to prevent matrix being reassigned
this._object3D.matrixAutoUpdate = false;
this.updateMatrixWorld();
}
var bounds = new Box3();
bounds.setFromObject(this._object3D);
if (coords === CoordinateSystem.LOCAL) {
this._object3D.matrix = oldMatrix;
this._object3D.matrixAutoUpdate = oldMatrixAutoUpdate;
this.updateMatrixWorld();
}
return bounds;
}
Is the object a single mesh, or is it a hierarchy of transformed objects?
It could be either, so in general I can't use the mesh BB directly.
Having said that, for efficiency reasons it might be more efficient for me to compute bounding box of the transformed mesh bounding boxes (i.e. rather bounding box of all transformed vertices, which I think is what Box3.setFromObject
does?) Though admittedly that potentially gives different results if combined child rotation transforms are not multiples of 90 degrees.
So you have a hierarchy of transformed objects and you want to compute the bounding box of the hierarchy -- but without regard to the transform of either the hierarchy's root object or the root object's parents?
Yes, that's correct. In effect, what I want is to be able to get the bounding box of a subtree of my hierarchy. i.e. the bounding box of all the contained geometry aligned within the coordinate space of the root of the subtree.
Perhaps I'm thinking about this wrong, but it seemed like something a lot of people might want, for example to show a box around the bounds of the subtree, where the box is aligned to the orientation of the selected node.
it seemed like something a lot of people might want, for example to show a box around the bounds of the subtree, where the box is aligned to the orientation of the selected node.
Sorry, I think you are on your own on this one...
Hmm.. oh well, thanks anyway. I feel like I must be missing a trick though. Or does it mean that everyone else is happy for bounding boxes to be aligned to world coordinates? Doesn't that look weird if you rotate an object and its bounding box stays aligned to world space? What am I missing?
It is an AABB - axis-aligned bounding box. If you rotate an object, the AABB likely changes dimensions.
What you want to be able to do, I think, is to be able to specify the axes (frame-of-reference) to which the AABB is aligned.
Wikipedia says:
_In the case where an object has its own local coordinate system, it can be useful to store a bounding box relative to these axes, which requires no transformation as the object's own transformation changes._
Yes, exactly, a most useful frame of reference for the AABB is for the object that I want to know the bounds of. If my scene contains a object representing a sofa measuring 2000 x 1000 x 800mm, would it not be nice if when I asked for the bounds of my sofa it returned 2000x1000x800, regardless of its rotation within the room?
Box3 has .setFromPoints which could do the trick with geometry.vertices, but nothing for BufferGeometry
ah wait, no, there is setFromBufferAttribute
hi makc, the problem is that I need the bounds of a group object that contains multiple meshes below various transforms, but in the coordinate space of the group. The code I posted at the top achieves this, but in an inelegant way. So I was mainly looking for a neater way of achieving it. If there was an option like @WestLangley hints at, to pass in the reference transform matrix, that would be ideal.
Some time ago i've planned to develop an Oriented Bounding Box class for three.js
. Most algorithms calculate in the first step the convex hull of the considered geometry. The good thing is that we already have a QuickHull
implementation that calculates the convex hull with good time complexity (average-case O(nlogn)).
In the next step you can use a method that is called rotating calipers to compute the oriented minimum bounding box for the given convex hull. Once the OBB is computed, you can use the SAT algorithm for fast collision detection. This would be a proper solution for even more complex requirements.
The API could look like this:
var convexHull = new THREE.QuickHull().setFromObject( mesh ); // already possible
var obb = new THREE.OBB().setFromConvexHull( convexHull ); // new class
// methods
obb.intersectsBox( box ); // OBB-AABB intersection test based on SAT
obb.intersectsOBB( obb2 ); // OBB-OBB (also SAT)
obb.intersectsSphere( sphere ); // OBB-Bounding Sphere via closest point
Although there are more efficient algorithms for OBB creation (like this one), the mentioned technique should be feasible to implement. And yeah, i know three.js
is not a library for computational geometry but it's always handy to have these algorithms around :innocent: . At least in the examples
directory.
If somebody wants to try an OBB implementation, i would definitely support this 馃槉 .
Interesting idea. Though for the use case I'm thinking of, it doesn't need to find the minimum bounding box. It just needs the bounding box aligned to a known coordinate frame.
My thinking was that it could be a really simple change to Box3.setFromObject
that optionally transforms collected vertices using a transform relative to the specified object rather than relative to the world root node, as it does now.
I wondered if it was worth me making a PR with the required tweak, but wasn't sure how likely it was to be merged.
@ChrisDenham
If we were to add a frame-of-refrence to setFromObject()
, we would have to do it for every Box3
method.
I suppose we could rename Box3
to AABB
, and add a new class OBB
which has a transform matrix defined. One would extend the other.
In any event, this is an easy change for you to make in your own app.
setFromObject: function ( object, transform ) {
this.makeEmpty();
return this.expandByObject( object, transform );
},
expandByObject: function () {
var v1 = new Vector3();
return function expandByObject( object, transform ) {
var scope = this;
object.updateMatrixWorld( true );
object.traverse( function ( node ) {
var i, l;
var geometry = node.geometry;
if ( geometry !== undefined ) {
if ( geometry.isGeometry ) {
var vertices = geometry.vertices;
for ( i = 0, l = vertices.length; i < l; i ++ ) {
v1.copy( vertices[ i ] );
v1.applyMatrix4( node.matrixWorld );
if ( transform !== undefined ) v1.applyMatrix4( transform );
scope.expandByPoint( v1 );
}
} else if ( geometry.isBufferGeometry ) {
var attribute = geometry.attributes.position;
if ( attribute !== undefined ) {
for ( i = 0, l = attribute.count; i < l; i ++ ) {
v1.fromBufferAttribute( attribute, i ).applyMatrix4( node.matrixWorld );
if ( transform !== undefined ) v1.applyMatrix4( transform );
scope.expandByPoint( v1 );
}
}
}
}
} );
return this;
};
}(),
I suppose we could rename Box3 to AABB
馃憤
@WestLangley thanks. That code is roughly what my PR would have been, except I would have multiplied node.worldMatrix
with the optionally provided transform
outside the vertex loops instead, for efficiency.
I'm not sure what other functions in Box3 would need changing? I can't think of any reason Box3
is any different from Vector3
in respect of what coordinate frame it is assumed to be in. I mean, there should be no assumption in either case. The programmer must always know the coordinate frame to which a Vector3
relates, so why not the same for Box3
(which, after all it is just two Vector3
objects). I don't think the suggested change breaks anything, or requires any other functions to be changed.
@Chrisdenham, I think you can transform that AABB(from Box3) to targeted coordinate, then get simple AABB again.
@whatisor Do you mean transform the object before getting the AABB of it? I'm not sure where transforming AABB would get me. eg. If I got the bounds of a cube rotated by 45 degrees, it's size is no longer a cube in world frame, so no transform of the bounds it going to get it back to a cube. Btw. I do have various solutions to the problem, but here I was just looking for a cleaner way of doing it without needing to trick my sub graph into behaving as though it was at root when getting its bounds.
I think the thing I don't really understand is why getting locally aligned bounds it not something fundamental and builtin to the API. I mean, if I want to draw a box around the bounds of subtree, it seems unlikely to me that i'd want the box aligned with world space, and for it to grow and shrink as i rotate it.
In my case, I am trying to adjust the distance from the camera to the object I want to zoom in/out.
I am looking for a way to have an oriented bounding bound in the camera system. As my camera direction is fixed (at that point), it would be easy to find the proper distance to make the object fit inside the camera view.
Hmm.. oh well, thanks anyway. I feel like I must be missing a trick though. Or does it mean that everyone else is happy for bounding boxes to be aligned to world coordinates? Doesn't that look weird if you rotate an object and its bounding box stays aligned to world space? What am I missing?
I totally agree with you. Hence my #11066, referred by @WestLangley above, and (I think) roughly the same as his sketch, except that it reuses the matrix product.
I also understand that finding the minimal box around an object can be useful, but it is another problem.
Renaming Box3
to AABB
does not sound like the best idea. Box3
means something, it is a (shorthand name for a) mathematical concept (a three-dimensional box). AABB
is just four letters. And when you expand them to "Axis-Aligned Bounding Box" they refer to a specific application of a box, that it bounds something, and also to some axes that are not specified. It could be object axis-aligned, world axis-aligned etc.
Most helpful comment
Some time ago i've planned to develop an Oriented Bounding Box class for
three.js
. Most algorithms calculate in the first step the convex hull of the considered geometry. The good thing is that we already have aQuickHull
implementation that calculates the convex hull with good time complexity (average-case O(nlogn)).In the next step you can use a method that is called rotating calipers to compute the oriented minimum bounding box for the given convex hull. Once the OBB is computed, you can use the SAT algorithm for fast collision detection. This would be a proper solution for even more complex requirements.
The API could look like this:
Although there are more efficient algorithms for OBB creation (like this one), the mentioned technique should be feasible to implement. And yeah, i know
three.js
is not a library for computational geometry but it's always handy to have these algorithms around :innocent: . At least in theexamples
directory.If somebody wants to try an OBB implementation, i would definitely support this 馃槉 .