Help needed in creating an AABB function
Blitz3D Forums/Blitz3D Programming/Help needed in creating an AABB function
| ||
| Hi all, Given a mesh of any shape or size, how do we align a box to best fit yet take up the least amount of space? The box has to rotate in order to take up the least possible room.it's a tricky thing to work out and beyond me. We don't know the axis of the mesh we are working with. The challenge is to fit a rectangular cube mesh around for example, a sphere which has been stretched and rotated. We don't know in advance what shape the model is, other than we must fit a cube around it in the most efficient manner possible. I don't think it can be done easily.  |
| ||
| Mmmm, ain't as easy as it first seems. My first attempt was to get the angle from the two corners of the default bounding box, find the tangent angle, and extend it out until it intersected the other tangent from the other angle. But then it hit me. This would produce a diagonal box, and would waste space. |
| ||
| May be of use. Don't understand it, too deep for me right now :) http://www.cs.unc.edu/~zhangh/technotes/bbox.pdf |
| ||
| Check out http://www.magic-software.com/Containment.html magic-software also has stuff on how to do OBB (Oriented bounding box) collision check. and maybe http://geometryalgorithms.com/Archive/algorithm_0107/algorithm_0107.htm |
| ||
| I can think of a kludgy way of doing it, but I'm no mathematician and there's probably a much faster way of doing it using maths... if you were to take 6 planes and move them towards the object until they intersect, then rotate until they don't, then move towards until they do again, repeat until they always intersect, you could approximate a box around the object like that, couldn't you? |
| ||
| I can think of another kludgy way wich I think would work quite well. Rotate the mesh in all possible ways in steps of say 5 degrees. For each rotation, and for each vertex, calculate (Tform) the worldspace x,y,z finding the smallest and largest x,y,z. For each rotation calulate the volume (maxx-minx)*(maxy-miny)*(maxz-minz) The smallest volume, is the best bounding box. Rotate the mesh to best fit position, create the bounding box, fitmesh(bestfitminx,bestfitminy,bestfitminz,bestfitmaxx,bestfitmaxy,bestfitmaxz) and parent it to the mesh. |
| ||
| Rob, if your trying to do what I think your trying to do... which is either precalculate the bounding box dimensions, or calculate it realtime, theres one easy way to do it. Loop through all of the mesh's vertices, find the vertices that are the farthest from the mesh's center in each axis. Remebering the box is aligned to the global coord system(I assume). We then have the dimensions for the bounding box(It will perfectly fit the object. If the Object rotates, the bounding box will have to be recalculated. So, for example, to find the width of the bounding box. Loop through the vertices of the mesh, Find the location of the vertex farthest in the posotive X axis. This is the "right" most side of the box. Then find the vertes farthes in the negetive X axis. This is the "Left" most side of the box. Now just calculate the distance between them and you have the width of the box. Do the same in the Z/X axis and your set. If you want this bounding box to not be recalculated every time the object rotates, do yourself a favor and create a cube to represent the bounding box, and child it. Hope this makes sense. |
| ||
| Have you tried cycling through each of the meshes vertices and getting the outer bounds of the mesh? If you did that you could use FitMesh to squash the cube into the correct size... |
| ||
| I really think the only way to do it is to test the width/height/depth at varying angles and find the one which results in the lowest volume, which is basically what Peter Scheutz said. That way should be fast enough. How fast does it need to be? |
| ||
| Tough problem. When I look at the image, I think the way I figure it out is by looking for the center of the model, which is the average position of all points, and then I find the line that passes through that point that minimizes the distance between itself and all other points. That would be the long axis of the box. But I don't know how to solve for that in a fast way. |
| ||
| Oh and that's an "oriented bounding box", not an "axis aligned bounding box". AABB's are aligned to the axis of the world, not the object. OBB's are oriented to the object. |
| ||
| I would think that this doesn't have to be to fast, since you could implement it in some kind of editer that stores a file giving data opn the box. I think I have a rather good way of getting the pitch ,yaw, and length of the best rectangle. simply measure all the distances between each vertice. then find the longest one. this distance is your boxes length, and the boxes angle. Then, you find all the other vertice's distances from the line (closest distance, that is). The largest distance's vector is then reversed, and the farthest point in the object recorded. now you simply average these two points to get the centerpoint. These two points also give the width-wise diaganol of the bounding box. Then this can be used to define the roll as well, although I'm not sure exactly how. The problem with this scheme so far is that the x and the y of the box will always come out equal. I think this might be solved by getting a line that is perpindicular to the line that defined the diagonol. These lines would then represent the x and y of the box. This may seem a little like hocus pocus, but I think it may work. Hopefully someone caught on to my idea, and translated the rest of it. My scheme is troublesome to code, but not very iterative. You just have to iterate through the vertices several times. For many purposes iterative aproaches other than mine should work well, but maybe not for runtime loading. |
| ||
| What is the practical purpose you intend to use the for? That would help in knowing what information you have available. Looks like it'll be tough though. In 3D, it is considerably more complicated to find the minimum volume bounding box of a convex polyhedron. The current fastest algorithm is by [O'Rourke, 1985], and it runs in O(n3) time. But it may be possible to improve on this. Regardless, since O(n3) algorithms are slow in practice for large point sets, there is considerable interest in fast approximations for the minimum volume box in 3D and higher dimensions. Recently, [Barequet & Har-Peled, 1999] have described two randomized algorithms that run in O(n log n + 1/å4.5) and O(n log n + n/å3) expected time, where Ä is the error of the approximation. The deterministic variants of these algorithms run in O(n log2 n + 1/å4.5) and O(n log2 n + n/å3) time. Only the second of these algorithms is simple enough to implement in practice. |
| ||
| This is for occulsion i think. If you precalculate all the boxes though, and make a cube out of it, then parent the cube, you should be ok. If it's a moving entity i dunno tho. I'm working on something just now. |
| ||
| See if this is any use, or if I've missed the point completely (need to use the CenterMesh function on loaded meshes, as opposed to CreateCube/Sphere, etc)... BTW Replace the CreateCube with CreateSphere and enable to ScaleMesh line to get something like the screenshot in the first post...
; Use this for loaded meshes...
Function CenterMesh (entity)
FitMesh entity, -(MeshWidth (entity) / 2), -(MeshHeight (entity) / 2), -(MeshDepth (entity) / 2), MeshWidth (entity), MeshHeight (entity), MeshDepth (entity)
End Function
; Parameters: camera used, mesh...
Function BoxMesh (box, mesh)
For s = 1 To CountSurfaces (mesh)
surf = GetSurface (mesh, s)
For vert = 0 To CountVertices (surf) - 1
vx# = VertexX (surf, vert)
vy# = VertexY (surf, vert)
vz# = VertexZ (surf, vert)
; lv* -- lowest vertex x/y/z
; hv* -- highest vertex x/y/z
If vx < lvx# Then lvx = vx
If vy < lvy# Then lvy = vy
If vz < lvz# Then lvz = vz
If vx > hvx# Then hvx = vx
If vy > hvy# Then hvy = vy
If vz > hvz# Then hvz = vz
Next
Next
PositionEntity box, EntityX (mesh, 1), EntityY (mesh, 1), EntityZ (mesh, 1)
FitMesh box, lvx, lvy, lvz, hvx * 2, hvy * 2, hvz * 2
RotateEntity box, EntityPitch (mesh, 1), EntityYaw (mesh, 1), EntityRoll (mesh, 1)
End Function
AppTitle "Cursors, A & Z..."
Graphics3D 640, 480, 0, 2
cam = CreateCamera ()
cube = CreateCube () ;LoadMesh ("C:\Program Files\Blitz3D\samples\Blitz 3D Samples\Hi-Toro\Shooter\Shooter\msh\ship.x")
CenterMesh (cube)
MoveEntity cube, 0, 0, 5
light = CreateLight ()
MoveEntity light, -10, 2, 5
PointEntity light, cube
Color 0, 255, 0
box = CreateCube ()
EntityColor box, 255, 0, 0
EntityAlpha cube, 0.25
EntityAlpha box, 0.25
;ScaleMesh cube, 1, 1, 3
Repeat
If KeyDown (203) TranslateEntity cube, -0.1, 0, 0
If KeyDown (205) TranslateEntity cube, 0.1, 0, 0
If KeyDown (200) TranslateEntity cube, 0, 0.1, 0
If KeyDown (208) TranslateEntity cube, 0, -0.1, 0
If KeyDown (30) TranslateEntity cube, 0, 0, 0.1
If KeyDown (44) TranslateEntity cube, 0, 0, -0.1
TurnEntity cube, 0.1, 0.2, 0.3
RenderWorld
BoxMesh box, cube
Flip
Until KeyHit (1)
End
|
| ||
| @bot builder i was thinking along the same lines. except i was starting with the centroid (per sswift's post) and finding only the furthest point and dropping an axis through those two. with an axis and furthest point create a perp plane. determine second point furthest from first axis and drop a plane down from the first (perp of course). step around the box using points/distances and angular constraints. problem is that for a really complex shape, these planes may not be enclosing the least volume (for example, that second point/axis probably fit snugly in a corner of the box). that means you're back to iterating shapes per Peter and Perturbatio. in the end, it's probably more trouble to do this then just doing the iterations from the start as already suggested (and perhaps now coded). |
   |