• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
masterbubu

Creating OBB

9 posts in this topic

Hi all,

I'm trying to create an OBB for my engine but failed to do so.

I have read good articles/tutorials on line, and I think I understand the concept, but still the OBB does not look good.

The algorithm I use:

for each vertex on the mesh vertices do:
m+= vertex

m/= vertices.size()

Now calculation the covariance matrix:

for each vertex on the mesh vertices do:
{

upperRight3x3Triangle[0] += p.x*p.x - m.x*m.x;
upperRight3x3Triangle[1] += p.x*p.y - m.x*m.y;
upperRight3x3Triangle[2] += p.x*p.z - m.x*m.z;
upperRight3x3Triangle[3] += p.y*p.y - m.y*m.y;
upperRight3x3Triangle[4] += p.y*p.z - m.y*m.z;
upperRight3x3Triangle[5] += p.z*p.z - m.z*m.z;
}

basically I have computed the upper right triangle of the covariance matrix.

Then I just create the matrix from those values, so that the lower triangle of the matrix is symmetrical to the upper triangle.

My problem is that according to the resources I have read, this matrix has the form of [ Right, Up, Forward ] (3x3 rotation matrix ),

Those 3 axes that represents the OBB orientations should be orthogonal to each other ( because the matrix is symmertic ). I have draw

the box axes, and they are not orthogonal to each other.

what am I missing ?

Any help/reference would be great.

tnx a lot Edited by masterbubu
0

Share this post


Link to post
Share on other sites
Your covariance calculation is incorrect. The covariance of (x,y) is E[(x-µ[sub]x[/sub])(y-µ[sub]y[/sub])] = E[xy - xµ[sub]y[/sub] - yµ[sub]x[/sub] - µ[sub]x[/sub]µ[sub]y[/sub]], where µ[sub]x[/sub] and µ[sub]y[/sub] are the mean values of x and y, respectively, which is not equal to E[xy - µ[sub]x[/sub]µ[sub]y[/sub]].
0

Share this post


Link to post
Share on other sites
Hi,
Tnx for you reply.
If I understand u right, for vec3, I needs to have something like that (x-a)(y-b)(z-c) where x,y,z are the coords of some vertex, and a,b,c are the coords of the mean,

I have followed this paper:

[attachment=12026:Screen Shot 2012-10-31 at 6.28.07 PM.png]

which seems to take the multiplication of ( 3x1 ) ( 1x3 ) vectors, which gives the matrix.

please correct me if I'm wrong.

tnx
0

Share this post


Link to post
Share on other sites
In my post, x and y are scalar random processes. They correspond to p.x, p.y or p.y, or whatever pair of coordinates axes you want to estimate the covariance of. On vector form, the equations are just what you posted. But my point of my post is that, if you expand the product in the summation, then you don't get what your code shows. Expand the product and and do the calculations for every component of the vectors and see what you get. Edited by Brother Bob
0

Share this post


Link to post
Share on other sites
Hi,

Well I thought about it, and decided to change the covariance code.

[CODE]
float xx = 0,xy = 0,xz = 0,yy = 0,yz = 0,zz = 0;
for ( int i = 0 ; i < vertices.size(); ++i )
{
const vec3 &p = vv[i];
const vec3 diff = p - midPoint;
xx += diff.x * diff.x;
xy += diff.x * diff.y;
xz += diff.x * diff.z;
yy += diff.y * diff.y;
yz += diff.y * diff.z;
zz += diff.z * diff.z;
}
upperRight3x3Triangle[0] = xx;
upperRight3x3Triangle[1] = xy;
upperRight3x3Triangle[2] = xz;
upperRight3x3Triangle[3] = yy;
upperRight3x3Triangle[4] = yz;
upperRight3x3Triangle[5] = zz;

[/CODE]

But still I'm getting odd results:
[attachment=12038:Untitled.png]

I'm not sure what is the problem. I don't care about the look of the box ( for now ), I just want to get the axis orthogonal to each other :(
0

Share this post


Link to post
Share on other sites
If you want the orthogonal basis of the distribution having the calculated covariance matrix, then you need to further process the covariance matrix. Look up [url="http://en.wikipedia.org/wiki/Principal_component_analysis"]principal component analysis[/url]. The basic idea is that the orthogonal basis are made up of the eigenvectors of the covariance matrix. The power of each basis vector is given by the inverse of the eigenvalue of the corresponding eigenvector.
0

Share this post


Link to post
Share on other sites
Just a note, generally computing the cov matrix in order to find its eigenvectors is a grave mistake (may lead to a very serious round-off error).
A much better approach is to find the SVD directly, that is right after you QR'ed the deviations Nx3 matrix into Q Nx3 and R 3x3. Edited by max343
0

Share this post


Link to post
Share on other sites
HI,

max343 : can u please refer me to some reference regarding that thing ?


I'm trying to update the OBB according the bones movement. Each OBB has its corresponding bone, which deforms it. The problem is the coords system of the

bone, does not matches to the OBB coords system, which causes wrong rotations. setting the OBB rotation axes to be the same as the bone, gives the correct

rotation, but the OBB loose its original shape. Any ideas?
0

Share this post


Link to post
Share on other sites
I'm not sure whether your problem is with finding the eigenvectors or something else.

Either way, implementing the general SVD is rather complex (generally references describe only this), your best way out is to use some math library like LAPACK, GNUSL, MKL and etc...
If you don't want to use external math libraries, you can implement a special case 3x3 SVD with the next steps:
1. Implement the QR decomposition (this is easy). There're tons of documentation on how to do it correctly. Apply it on your deviations matrix, and toss Q away, as you won't be needing it anymore.
2. Bidiagonalize your R matrix. This is very easy since R is a 3x3 upper triangular matrix. All you'll need to do is to apply a single Householder transformation in order to zero the (1,3) element. Keep the Householder matrix (or vector, it doesn't matter) besides the obvious bidiagonal matrix (let's call it B).
3. Here comes the tricky part. You'll need to implement a variant of the QR algorithm to work on B, but not to find its eigenvalues/eigenvectors, but rather its singular values and right singular vectors. The easiest (right) way to do this is to diagonalize the matrix H which is defined by this matlab'ish notation H=[0,B';B,0]. But in order to do that efficiently you'll need to apply a permutation so it'll be a tridiagonal 6x6. The permutation for 3x3 base case is known: P=[e1,e4,e2,e5,e3,e6]. So you'll start with P'HP (this is basically one vector of the distinct elements of B in order, duplicated along the secondary diagonals of H). Now run the normal QR algorithm on this tridiagonal matrix to find its eigenvalues/eigenvectors. Afterwards apply the inverse of P (trivial) on the eigenvectors. Take the non-negative eigenvalues (there will be 3, zeroes notwithstanding), and the corresponding eigenvectors. The 3 eigenvalues are actually the singular values of R. Now truncate the taken eigenvectors to 3 coordinates so they form a 3x3 matrix. Multiply the Householder matrix from the previous step by this matrix to obtain the right singular vectors.

As you can see, even for this relatively simple case the SVD implementation is not that easy. Edited by max343
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0