littlekid 229 Report post Posted November 23, 2007 I have a sphere and a object bounding box. I wish to transform the sphere to the OBB object space to peform a collision test. I know that to get the transformation matrix to object-space, i need the local axis of the OBB Transformation Matrix(MyMatrix) to Object Space: [OBB x-axis] [OBB y-axis] [OBB z-axis] Is this matrix correct? What I wish to know is that this matrix that i construct, before i apply to the sphere, do i have to apply the world transformation for the sphere too? Can I go: Sphere > MyMatrix > becomes in OBB Object space. Or must i do: Sphere > SphereWorldMatrix > MyMatrix > becomes in OBB Object space. Sorry if this question appear stupid. I am just trying to learn my linear algebra. Thanks a million 0 Share this post Link to post Share on other sites
haegarr 7373 Report post Posted November 23, 2007 The testing can be done as soon as all data involved are given in the same co-ordinate frame. This can be the global frame, one local frame of the collision volumes, or any other.A co-ordinate frame is both an orientation as well as a position, both given w.r.t. the parental frame. (So your "MyMatrix" is insufficient, since it shows an orientation but no position, if I understand it correctly.)Assuming a local frame L, then any geometry given in that frame is transformed to the parental frame by applying the matrix L to the geometry. When using column vectors, that looks likep' := L * pGoing the opposite way, namely transforming geometry from the parental frame into the local frame, is the inverse operationL^{-1} * p' = pLets assume furthur that the local frames of the both collision objects are L_{1} and L_{2}, and that the next more global spaces of both is common, then 1st transforming geometry from L_{1} into the common framep' = L_{1} * pand furthur transforming the result into L_{2}p" = L_{2}^{-1} * p'can be summarized top" = L_{2}^{-1} * L_{1} * p'So, extracting the transformation matrix from this, one getsM = L_{2}^{-1} * L_{1}I hope that has clarified the issue somewhat.EDIT: Please bear in mind that collision volumes are often "simple" geometry, e.g. a sphere centered around the origin of the local frame. Hence often M can be optimized. 0 Share this post Link to post Share on other sites
littlekid 229 Report post Posted November 23, 2007 thanks haegarr. I understands the concept of the local frames.I do understand the derivation of: M = L2-1 * L1However, why is it that M is also just simply the equivalent of the L2 local axes? From ur derivation it isn't so is it?Plus any insight on what you mean by optimize M for simple geometry?should I use:[x1, x2, x3][y1, y2, y3][z1, z2, z3]where local x-axis = (x1,y1,z1), y-axis = (x2, y2, z2)or[OBB x-axis][OBB y-axis][OBB z-axis]The main problem I am having is trying to build a matrix to get the sphere to the Object Bounding Box, object space to perform collision detection[Edited by - littlekid on November 24, 2007 12:08:59 AM] 0 Share this post Link to post Share on other sites
haegarr 7373 Report post Posted November 24, 2007 Quote:Original post by littlekidHowever, why is it that M is also just simply the equivalent of the L2 local axes? From ur derivation it isn't so is it?Plus any insight on what you mean by optimize M for simple geometry?As already stated in my previous post, any matrix you want to use has to consist of both an orientation and a position. It can be understood as a concatenation (still using column vectors)L := T * Rwhere T denotes the position (as a translation from the origin) and R denotes the orientation (as a rotation from the standard orientation).My derivation of M computes a matrix to transform geometry from the frame L_{1} to the frame L_{2}.M := L_{2}^{-1} * L_{1}= R_{2}^{-1} * T_{2}^{-1} * T_{1} * R_{1}Now assuming that the geometry is a perfect sphere with its center at the local (0,0,0)c := [0,0,0,1]^{t}and a radius r, as would be typical for a sphere as a collision volume. Transforming the sphere's center then means to computec" := R_{2}^{-1} * T_{2}^{-1} * T_{1} * R_{1} * [0,0,0,1]^{t}But since [0,0,0,1]^{t} is the identity value for a rotation (i.e. it is the only one value in the entire space that isn't altered by applying the rotation), and since T_{1} denotes the origin of the frame, the above formula is principally the same asc" := R_{2}^{-1} * T_{2}^{-1} * [tx,ty,tz,1]^{t}Moreover, since the space doesn't scale (we've defined it w/o any scaling matrix part), the radius is left as is and hence need not explicitely be transformed. So, for the given simple geometry, computing M can be done optimized asM = L_{2}^{-1}Obviously, my M is not "just simply the equivalent of the L2 local axes". That has up to 3 reasons: First, as written above, M must provide also a position! Second, the axes that are given by you as an equivalent of the orientation of the local frame define the local axes w.r.t. the parental frame, and hence are part of the local-to-parent transformation! But your intention of M is to do a parent-to-local transformation (when looking at L_{2} only), so you have to invert. Third, generally you have to consider the first local frame L_{1}, too.Quote:Original post by littlekidshould I use:[x1, x2, x3][y1, y2, y3][z1, z2, z3]where local x-axis = (x1,y1,z1), y-axis = (x2, y2, z2)or[OBB x-axis][OBB y-axis][OBB z-axis]When looking at this, I see 2 things perhaps buried in the question (but perhaps I misunderstand your question): The one is whether to use column or row vectors, and the other is whether you should use local frame axes or else OBB axes. Whether to use column or row vectors is a matter of taste. I personally prefer column vectors, and so chosen it for the math I've written down here. The axes (and position) you should use for the transformation are defintely those of the local co-ordinate frame! The box (or which volume ever) is just a geometry given w.r.t. that frame. E.g., if you use an AABB (i.e. an axes-aligned BB) then the geometry has some simplification potential, similar to the center of the sphere coincident w/ the frame's origin in the example above. The difference of a general OBB w.r.t. an AABB is just that its orientation is explicitely allowed to differ from the local axes orientations.Quote:Original post by littlekidThe main problem I am having is trying to build a matrix to get the sphere to the Object Bounding Box, object space to perform collision detectionWell, with the stuff above, I've already shown thatM = L_{2}^{-1}can be used to simply transform the origin of the bounding sphere into the local frame of the OBB (assuming that L_{2} denotes the frame of the OBB, of course), and that r can be used as is. You can, if you wish, use the OBB's local definition to make the problem a sphere-AABB collision detection, if you apply an additional parent-to-local transformation, yielding inL_{B}^{-1} * Mwhere L_{B} denotes the local frame of the OBB w.r.t. L_{2}.In summary:(1) Build L_{2} as shown at the top of this post from the orientation and position of the frame the OBB is defined in.(2) Compute its inverse L_{2}^{-1} and use the resutl as M.(2a) If you want to do an AABB test instead of OBB, perform (1) and (2) also for the local frame of the OBB, multiplying the result from the left with the previous M, and use the result as new M.(3) Apply the transformation M to the sphere's origin and take the sphere's radius over.(4) Do the actual collision test.Whop, I must try to make less words. However, I hope it helps you to understand the mechaniscs behind the problem :) 0 Share this post Link to post Share on other sites
littlekid 229 Report post Posted November 24, 2007 ahh.. let me try and rephrase what you just say, and check if I understood your post.A sphere has a transformation from its own object space to world space denoted my M1A Box has a transformation from its own object space to world space denoted my M2Hence to get the sphere in to the object space of the Box to peform a Sphere-AABB collision test I wouldSphere.orgin * M1 * Inverse(M2); --- eqn(1)Would that be it?A side question if the M2 matrix includes a non uniform scaling, how should i scale the radius of the sphere. If i just plug the values into eqn(1), which i hope i got it right, wouldn't the sphere become a espilloide after the transformation to the Box object space? 0 Share this post Link to post Share on other sites
haegarr 7373 Report post Posted November 24, 2007 Quote:Original post by littlekidA sphere has a transformation from its own object space to world space denoted my M1A Box has a transformation from its own object space to world space denoted my M2I've named it L (for "local") so far, but okay, its just a convention how to name the things.Quote:Original post by littlekidHence to get the sphere in to the object space of the Box to peform a Sphere-AABB collision test I wouldSphere.orgin * M1 * Inverse(M2); --- eqn(1)This equation is true but if and only if you're using row vectors. (In my explanations so far I've used column vectors, therefore I've written those equation in "transposed order" compared to your writing.)Quote:Original post by littlekidA side question if the M2 matrix includes a non uniform scaling, how should i scale the radius of the sphere. If i just plug the values into eqn(1), which i hope i got it right, wouldn't the sphere become a espilloide after the transformation to the Box object space?Yes, indeed. If your frame shows also scaling, then its simplest form is typically like (I stick with my conventions here to be consistent with previous posts)L_{2} := T_{2} * R_{2} * S_{2}where S_{2} denotes said scaling. ThenM := L_{2}^{-1} = S_{2}^{-1} * R_{2}^{-1} * T_{2}^{-1}obviously still contains the scaling. Notice please that the scaling not only affects the radius but the position of the sphere as well.You can compute it then e.g. by(a) transforming its position as usual c" := M * c, and(b) creating an artificial direction vector (r,r,r) from the sphere's radius r in L_{1}, and computingr" := M * [r,r,r,0]^{t}to yield in a vector (r_{x},r_{y},r_{z}) describing the axes aligned radii of the ellipsoid in L_{2}. 0 Share this post Link to post Share on other sites
littlekid 229 Report post Posted November 24, 2007 Thanks, I think I now better understand the maths behind it.However I did would like to know from the last eqn:r" := M * [r,r,r,0]thence getting the radii of the ellipsoid. However, by making it to a ellipsoid, wouldn't it defeat the purpose of going all the trouble for the collision test?As I was thinking along the line to change from Sphere-OOBB test to Sphere-AABB test to simplfiy the algorithm. By changin the sphere to a ellipsoid, isn't it harder to perform the collision test?my method of testing a sphere against a AABB is just:float Distance = 0.0f;if (SphereOrigin.x < pBox->MinPoint.x) Distance += pow(SphereOrigin.x - pBox->MinPoint.x, 2);else if (Origin.x > pBox->MaxPoint.x) Distance += pow(SphereOrigin.x - pBox->MaxPoint.x, 2);if (SphereOrigin.y < pBox->MinPoint.y) Distance += pow(SphereOrigin.y - pBox->MinPoint.y, 2);else if (Origin.y > pBox->MaxPoint.y) Distance += pow(SphereOrigin.y - pBox->MaxPoint.y, 2);if (SphereOrigin.z < pBox->MinPoint.z) Distance += pow(SphereOrigin.z - pBox->MinPoint.z, 2);else if (Origin.z > pBox->MaxPoint.z) Distance += pow(SphereOrigin.z - pBox->MaxPoint.z, 2);if (Distance > pow(SphereRadius, 2)) return E_FAIL;else return S_OK; 0 Share this post Link to post Share on other sites
haegarr 7373 Report post Posted November 25, 2007 Quote:Original post by littlekidHowever I did would like to know from the last eqn:r" := M * [r,r,r,0]thence getting the radii of the ellipsoid. However, by making it to a ellipsoid, wouldn't it defeat the purpose of going all the trouble for the collision test?It is a range of grays from the simplest sphere-sphere collision test to the complex triangle-triangle test. Of course, testing an ellipsoid against an AABB is more complex than testing a sphere against an AABB, but on the other hand it may produce less 2nd order tests. Its all a matter of costs vs. benefits, sadly dependend on the geometry inside the bounding volume.However, 1st, if the local frame does non-uniform scaling then you have to deal with it. Most likely it doesn't, and you were lucky then. 2nd, you can have situations where optimized handling is possible, namely:(a) If the frame of the AABB is the scaling one (as you've requested if I remember correctly), then you have 3 radii, one for each principal axis direction, instead of 1 for all of them. That is perhaps (dependind on what you're doing) nothing that really harms: Instead ofif (x < r) ...if (y < r) ...if (z < r) ...you'll use something likeif (x < rx) ...if (y < ry) ...if (z < rz) ...(b) You can operate also in a variant of the frame where the ellipsoid is still a sphere. That means nothing else than to inversely scale the AABB instead of forward scale the sphere. Then you still perform a sphere-AABB test. I.e. store and use the box's extend w/o the scaling.Looking at your code snippet I would suggest some things if I'm allowed to do:(1) I don't know whether your compiler knows an intrinsic to replace a pow(...,2) by a multiplication. I would use a*a instead of pow(a,2).(2) pow(SphereRadius, 2) is constant at runtime as long as the sphere isn't altered. You may consider to store and use the squared radius instead of computing it again and again.(3) Mainly a matter of readibility: The ternary operatorreturn (Distance > pow(SphereRadius, 2)) ? E_FAIL : S_OK;or even better, a real boolean resultreturn Distance > pow(SphereRadius, 2); or return Distance <= pow(SphereRadius, 2);is IMHO easier to read (less program code) any presumbly produces less assembler code. 0 Share this post Link to post Share on other sites
littlekid 229 Report post Posted November 25, 2007 I am using the visual studio compiler.I don't quite really understand your 2nd method where you inversely scale the AABB so to retain the Sphere property as well as the Axis Aligniness of the box.I was also thinking another method which I do not know if it is viable:Say to make a Object Bounding Box Axis Align, all I need to do is multiply it my a rotational matrix, M. (Just a rotation, no scale/shear/translation).Hence by multipling the sphere by the same rotational matrix, I can get a sphere-AABB test done.I am not sure if this is workable? Just sudden;y popped in my head after thinking of this for a long time. 0 Share this post Link to post Share on other sites
haegarr 7373 Report post Posted November 25, 2007 Quote:Original post by littlekidI don't quite really understand your 2nd method where you inversely scale the AABB so to retain the Sphere property as well as the Axis Aligniness of the box.Well, look at the math. Our recent transformation, namely that inclusive scaling, wasM_{S} := L_{2}^{-1} = S_{2}^{-1} * R_{2}^{-1} * T_{2}^{-1}to transform the sphere (above indicated by the index S) from L_{1} to L_{2}. Because it become senseful in the next step, we'll also define a transformation for the box. Since the box is already given in L_{2}, so its transformation is of course the identify matrix:M_{B} := INow we want to undo the scaling of the sphere, making the S_{2}^{-1} unhappen inside M_{S}:S_{2} * M_{S} = S_{2} * S_{2}^{-1} * R_{2}^{-1} * T_{2}^{-1} = R_{2}^{-1} * T_{2}^{-1}Since we need to test both volumes in the same frame, we need to perform the same transformation on the box:S_{2} * M_{B} = S_{2} * I = S_{2}Notice please that the scaling as is applied by S is always along the principal axes (other scalings are possible, too, but require surrounding rotations and translations; look e.g. at the "Transform" node of VRML/X3D). That means, that an axes aligned box will remain an axes aligned box; the axes alignment property is invariant against scaling.In other words, if we scale the box but don't scale the sphere, we're still able to test against the sphere. (I've written "inverse scaling" in my above post since S_{2} is applied to the box what is the inverse of S_{2}^{-1} that was formerly applied to the sphere.) All we've done is choosing another, more appropriate co-ordinate frame.Quote:Original post by littlekidSay to make a Object Bounding Box Axis Align, all I need to do is multiply it my a rotational matrix, M. (Just a rotation, no scale/shear/translation).Yes, the operation to make a OBB axis aligned is a rotation, so far you're right. BUT: The resulting AA box will in general not contain the entirety of the orignal OBB, and hence it would perhaps not be a proper AABB. In general an AABB is greater than an equivalent OBB, and it is at least of the same size (namely if the OBB is already axes aligned). That is in fact the reason why OBBs are used besides AABBs at all.To compute an AABB from an OBB, one can look at the 8 corners of the OBB and compute the 6 minimums and maximums of their x,y,z co-ordinates. These values are then the boundary values of the equivalent AABB. Of course, the resulting AABB may be too great, but that cannot be verified when only looking at the original OBB. If you want to have the smallest AABB, you have to investigate the wrapped geometry itself.EDIT: To clarify, please read also my next post!EDIT2: Bug corrected.[Edited by - haegarr on November 28, 2007 1:10:07 AM] 0 Share this post Link to post Share on other sites
haegarr 7373 Report post Posted November 25, 2007 Quote:Original post by littlekidSay to make a Object Bounding Box Axis Align, all I need to do is multiply it my a rotational matrix, M. (Just a rotation, no scale/shear/translation).Hence by multipling the sphere by the same rotational matrix, I can get a sphere-AABB test done.Oh, just a moment ... You actually may mean a slightly other thing than those I've understood during answering in my previous post. Previously, I understood you want to compute an AABB in L_{2}, and that would be subject of the problem I've described in my previous post. But presumbly you want to do the following:You can compute the transformation of a frame L_{B} that is axes aligned with the OBB. Then the overall transformation would becomeM := L_{B}^{-1} * L_{2}^{-1}transforming the sphere into the "axes aligned" frame. Yes, I think that is possible. Presumbly you meant L_{B}^{-1} to be the "rotational matrix M" you mentioned?! 0 Share this post Link to post Share on other sites
littlekid 229 Report post Posted November 25, 2007 cool. I think i understood what you meant. Let me rephrase to see if I am right.So that means in order to avoid scaling the sphere, we scale the box instead.Hence to get them in the same frame, I would:NewSphere = Sphere * Inverse(BoxRotation) * Inverse(BoxTranslation)NewBox = Box * BoxScalingThen I just test NewSphere w.r.t NewBox(Which is still axis align). Hence I can still use a sphere-AABB test.A side note. About the idea that I have, I was not trying to fit the object entierly into the AABB, but just to make the OBB rotate to a AABB, and the sphere to rotate by the same amount to facilitate testing.Example both OBB and Sphere is already in the world space. Hence I would multiply the OBB(World space) by a said amount of Rotation to make it axis align. Then I would multiply the Sphere(World space) also by the same amount of rotation. Hence the testing would be done on a axis align box.Therefore don't think it matters if the resulting AABB does not cover the object entierly.In summary I was thinking:A Sphere test against a Box. Translate/Rotate both sphere and box by any same amount. It will not affect the test result at all. I hope my thinking isn't wrong. 0 Share this post Link to post Share on other sites
haegarr 7373 Report post Posted November 25, 2007 Quote:Original post by littlekidSo that means in order to avoid scaling the sphere, we scale the box instead.Yep. In fact we can transform the space how ever we want as long as all relevant stuff inside the space is transformed with it. E.g. a ray-ellipsoid test during ray-tracing can be done by scaling the space so that the ellipsoid becomes a sphere and the ray another ray. Although we've chosen another frame, the situation remains the same. If you compute relative values it is irrelevant which frame you actually used, but for computing absolute values you may need to transform the result from the used frame back to the original frame. In your case you want to know whether a collision occurs, and that can be done totally in the temporary frame. If, however, you want to know the point of collision, you typically don't want to know it in the temporary frame but the original local frame or even the global frame.Quote:Original post by littlekidHence to get them in the same frame, I would:NewSphere = Sphere * Inverse(BoxRotation) * Inverse(BoxTranslation)NewBox = Box * BoxScalingThen I just test NewSphere w.r.t NewBox(Which is still axis align). Hence I can still use a sphere-AABB test.Yes, that seems me correct.Quote:Original post by littlekidA side note. About the idea that I have, I was not trying to fit the object entierly into the AABB, but just to make the OBB rotate to a AABB, and the sphere to rotate by the same amount to facilitate testing.Example both OBB and Sphere is already in the world space. Hence I would multiply the OBB(World space) by a said amount of Rotation to make it axis align. Then I would multiply the Sphere(World space) also by the same amount of rotation. Hence the testing would be done on a axis align box.Therefore don't think it matters if the resulting AABB does not cover the object entierly.In summary I was thinking:A Sphere test against a Box. Translate/Rotate both sphere and box by any same amount. It will not affect the test result at all. I hope my thinking isn't wrong.Yes, meanwhile also I have understood your intention :/ sorry for my former misunderstanding. My previous post hopefully has shed some light on this issue. However, I'm glad to see that you've found this way, since it shows that you've got a conceptional understanding of the math. 0 Share this post Link to post Share on other sites
littlekid 229 Report post Posted November 25, 2007 Thanks alot haegarr for the time and patience for helping me out with my problem.You have been a great help.Thanks alot, once again 0 Share this post Link to post Share on other sites