generating OOBBs
Author
hello. i am having some trouble, so i decided to ask... well, i wouldnt be here writing this topic if that wasnt true.
first of all, i am using c#.
i am implementing a procedure to build OOBBs on the fly, i know this is not probably the best method around, but its good enough for the application.
the idea is - i have a skinned mesh, and i want to create an OOB able to change its dimensions in time, so:
a) i move the mesh at the origin, reset its rotation and scaling (to me, this makes the world space the same as the model space, am i right?).
b) then, i would like to access the vertex data of the mesh, so i can compute the max-min coordinates for each dimension - which means i can build an AABB.
c) finally, its only a matter to apply the transformations of the mesh to the AABB previously created, to get my OOBB.
d) lastly, since the model is animated, the OOBB corners will have to be recomputed again each time the animation advances in time, using the same scheme.
on paper, this seems reasonable, and is good enough for what i have in mind.
anyway, i am currently facing some problems.
1) how do i access the *whole* vertex data of the mesh? as usual, my animated mesh is "broken" into many Mesh Containers objects (better, many objects of the class i derived from MeshContainer) and i draw the model calling the Draw method recursively through the hierarchy tree of the model. how do i store all the info in one place?
2) given the scheme i defined over (expecially point a) ) should i apply some transformations to the vertices i extract from the mesh, or is my assumption ok, that the model space will the the same as the world space?
I've been looking at valve's MDL format recently, and it occurs to me that the way they do it may be useful to you.
Essentially, they store AABBs in 'bone space'. Not every bone has a hitbox, just enough to give decent coverage.
That way, you reduce the storage reqs by using AABBs instead of OBBs and can update the boxes by transforming them by the relevant bone's absolute transform (e.g. all parent bone transforms concatenated), which should be much faster than looking at the individual vertices.
This may not be as accurate as your method, but if you choose which bones hae hitboxes carefully, it should be pretty good.
hope that's some use
Essentially, they store AABBs in 'bone space'. Not every bone has a hitbox, just enough to give decent coverage.
That way, you reduce the storage reqs by using AABBs instead of OBBs and can update the boxes by transforming them by the relevant bone's absolute transform (e.g. all parent bone transforms concatenated), which should be much faster than looking at the individual vertices.
This may not be as accurate as your method, but if you choose which bones hae hitboxes carefully, it should be pretty good.
hope that's some use
Transforming the corners of your oobb should do the job
Just as a note:
The common way to calculate the OOBB is the covariance matrix approach
(that is what I have seen in many applications so far)
you have N vertices so you get a NxN matrix
the diagonal matrices are the variances of each vertex
you process like this
1.) calculate the mean of all vertices
mean = 1/N *SUM_OVER_ALL_VERTICES = E(X)
the expectation value
2.) COV = Covariance
COV(X,X) = VAR(X) VAR = Variance
COV(X,Y) = COV(Y,X)
The covariance in this special case is calculated for 2 identical random variables, thats why you use the mean of all vertices
COV(X,Y) = E((X-E(X))(Y-E(X)))
as you see you get a symmetric matrix
|COV(A,A) COV(A,B) COV(A,C) COV(A,D)|
|COV(B,A) COV(B,B) COV(B,C) COV(B,D)|
|COV(C,A) COV(C,B) COV(C,C) COV(C,D)|
|COV(D,A) COV(D,B) COV(D,C) COV(D,D)|
we call this matrix THETA
3.) calculate the eigen vectors
possible since for each symmetric matrix there exists a decomposed representation
THETA = U * SIGMA * Utransposed
U holds the eigen vectors in its columns
SIGMA is a diagonal matrix which holds the eigenvalues
the eigen vectors in U's column are orthogonal, thus they are basis and represent the axis of your object oriented bounding box, all you have to do now is to calculate the min and max values of the OOBB based on the eigen vectors.
In order to actually compute the eigenvectors I suggest you to pick some existing code available on the net for free.
some reference for eigen vector compuation algorithms
QR algorithm
Jacobi method(we used this one at university)
seems to be easiers than the QR approach
Just as a note:
The common way to calculate the OOBB is the covariance matrix approach
(that is what I have seen in many applications so far)
you have N vertices so you get a NxN matrix
the diagonal matrices are the variances of each vertex
you process like this
1.) calculate the mean of all vertices
mean = 1/N *SUM_OVER_ALL_VERTICES = E(X)
the expectation value
2.) COV = Covariance
COV(X,X) = VAR(X) VAR = Variance
COV(X,Y) = COV(Y,X)
The covariance in this special case is calculated for 2 identical random variables, thats why you use the mean of all vertices
COV(X,Y) = E((X-E(X))(Y-E(X)))
as you see you get a symmetric matrix
|COV(A,A) COV(A,B) COV(A,C) COV(A,D)|
|COV(B,A) COV(B,B) COV(B,C) COV(B,D)|
|COV(C,A) COV(C,B) COV(C,C) COV(C,D)|
|COV(D,A) COV(D,B) COV(D,C) COV(D,D)|
we call this matrix THETA
3.) calculate the eigen vectors
possible since for each symmetric matrix there exists a decomposed representation
THETA = U * SIGMA * Utransposed
U holds the eigen vectors in its columns
SIGMA is a diagonal matrix which holds the eigenvalues
the eigen vectors in U's column are orthogonal, thus they are basis and represent the axis of your object oriented bounding box, all you have to do now is to calculate the min and max values of the OOBB based on the eigen vectors.
In order to actually compute the eigenvectors I suggest you to pick some existing code available on the net for free.
some reference for eigen vector compuation algorithms
QR algorithm
Jacobi method(we used this one at university)
seems to be easiers than the QR approach
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
