   merge two oriented boundary boxes
  Hi all!Does anyone have a robust merging code for two oriented ( Vector3 center, Vector3[3] axes, float[3] extents) boxes?Dave Eberly has changed the pseudocode and code in 'A Prac. Approach to 3D Game Engine Design' book and site http://www.magic-software.com  but it still calculates the center of the result box wrong! Last code is below :template Box3 Wml::MergeBoxes (const Box3& rkBox0,    const Box3& rkBox1){    // construct a box that contains the input boxes    Box3 kBox;    // The first guess at the box center.  This value will be updated later    // after the input box vertices are projected onto axes determined by an    // average of box axes.    kBox.Center() = ((Real)0.5)*(rkBox0.Center() + rkBox1.Center());    // A box's axes, when viewed as the columns of a matrix, form a rotation    // matrix.  The input box axes are converted to quaternions.  The average    // quaternion is computed, then normalized to unit length.  The result is    // the slerp of the two input quaternions with t-value of 1/2.  The result    // is converted back to a rotation matrix and its columns are selected as    // the merged box axes.    Quaternion kQ0, kQ1;    kQ0.FromRotationMatrix(rkBox0.Axes());    kQ1.FromRotationMatrix(rkBox1.Axes());    if ( kQ0.Dot(kQ1) < 0.0f )   kQ1 = -kQ1;    Quaternion kQ = kQ0 + kQ1;    Real fInvLength = Math::InvSqrt(kQ.Dot(kQ));    kQ = fInvLength*kQ;    kQ.ToRotationMatrix(kBox.Axes());    // Project the input box vertices onto the merged-box axes.  Each axis    // D containing the current center C has a minimum projected value    // pmin and a maximum projected value pmax.  The corresponding end    // points &#111;n the axes are C+pmin*D and C+pmax*D.  The point C    // is not necessarily the midpoint for any of the intervals.  The actual    // box center will be adjusted from C to a point C' that is the midpoint    // of each interval,    //   C' = C + sum_{i=0}^2 0.5*(pmin+pmax)*D    // The box extents are    //   e = 0.5*(pmax-pmin)    int i, j;    Real fDot;    Vector3<Real> akVertex[8], kDiff;    Vector3<Real> kMin = Vector3<Real>::ZERO;    Vector3<Real> kMax = Vector3<Real>::ZERO;    rkBox0.ComputeVertices(akVertex);    for (i = 0; i < 8; i++)    {   kDiff = akVertex - kBox.Center();   for (j = 0; j < 3; j++)   {  fDot = kDiff.Dot(kBox.Axis(j));  if ( fDot > kMax[j] ) kMax[j] = fDot;  else if ( fDot < kMin[j] ) kMin[j] = fDot;   }    }    rkBox1.ComputeVertices(akVertex);    for (i = 0; i < 8; i++)    {   kDiff = akVertex - kBox.Center();   for (j = 0; j < 3; j++)   {  fDot = kDiff.Dot(kBox.Axis(j));  if ( fDot > kMax[j] ) kMax[j] = fDot;  else if ( fDot < kMin[j] ) kMin[j] = fDot;   }    }    // [kMin,kMax] is the axis-aligned box in the coordinate system of the    // merged box axes.  Update the current box center to be the center of    // the new box.  Compute the extens based &#111;n the new center.    for (j = 0; j < 3; j++)    {   kBox.Center()[j] += ((Real)0.5)*(kMax[j]+kMin[j]);   kBox.Extent(j) = ((Real)0.5)*(kMax[j]-kMin[j]);    }    return kBox;}Thanks In AdvanceBurak<SPAN CLASS=editedby>[edited by - holyburak &#111;n February 5, 2004 9:43:12 AM]</SPAN>  </i>  
  If they are already axis-aligned, just take the largest and smallest X value, largest and smallest Y value and the largest and smallest Z value and you have the sides of your containing box. The center is simple the average of the largest and smallest of each. ;  Ok, I''ll give it a try kBox.Center() is probably expressed in the "standard" coordinate systemHowever, as stated in the source code comments, [kMin,kMax] is the axis-aligned box in the coordinate system of the merged box axes, which is totally different !Therefore the correct way of updating kBox.Center() should be :for(j = 0; j < 3; j++){    Vector3 translate = kBox.Axes()[j] * (kMax[j] + kMin[j]) / 2;    kBox.Center() += translate;}(Note that I assume the operators are correctly overloaded) ;  do you need your final bounding box to be the smallest possible bounding box that can contain the two oriented bounding boxes (i.e. also be oriented itself with a different set of axis no doubt)? or will an axis aligned bounding box do? ;  overnhet you are right. Seems like the global coordinates have been forgotten to turn into box coordinates.In the comments of the code ; // C'' = C + sum_{i=0}^2 0.5*(pmin+pmax)*D<br>I think D is not in the code.<br><br>I replaced following code ;<br><br>for (j = 0; j < 3; j++)<br>{<br>kBox.Center()[j] += ((Real)0.5)*(kMax[j]+kMin[j]);<br>kBox.Extent(j) = ((Real)0.5)*(kMax[j]-kMin[j]);<br>}<br><br>with :<br><br>Real tx, kx;<br>for (j = 0; j < 3; j++)<br>   {<br>kx =  ((Real)0.5)*(kMax[j]+kMin[j]);<br>tx  = (Real) (kx * (kBox.Axis(j).X() + <br>kBox.Axis(j).Y() + <br>  kBox.Axis(j).Z()) ) ;<br><br>   kBox.Center()[j] += tx;<br>   kBox.Extent(j) = ((Real)0.5)*(kMax[j]-kMin[j]);<br>    }<br><br>but just D[2] was okay. Whats the problem?<br><br><br>SpaceDude, yes it must be possible minimum box containing the other two no matter what the orientation is.<br>I tried following code but does not give the minimum box.<br><br>Box3f Merge_Boxes(Box3f* box1, Box3f* box2)<br>{<br>Box3f box;<br>Vector3f akVertex1[8], akVertex2[8], akVertex[16];<br><br>box1->ComputeVertices(akVertex1) ;<br>box2->ComputeVertices(akVertex2) ;<br><br>for(int i=0;i<8;i++)<br>{<br>akVertex = akVertex1;<br>akVertex = akVertex2;<br>}<br><br>box = ContOrientedBox (16, akVertex);<br><br>return box;<br><br>}<br><br><br><br>  </i>  ;quote:Original post by holyburak  I replaced following code ;for (j = 0; j < 3; j++){kBox.Center()[j] += ((Real)0.5)*(kMax[j]+kMin[j]);kBox.Extent(j) = ((Real)0.5)*(kMax[j]-kMin[j]);}with :Real tx, kx;for (j = 0; j < 3; j++)   {kx =  ((Real)0.5)*(kMax[j]+kMin[j]);tx  = (Real) (kx * (kBox.Axis(j).X() + kBox.Axis(j).Y() + kBox.Axis(j).Z()) ) ;    kBox.Center()[j] += tx;   kBox.Extent(j) = ((Real)0.5)*(kMax[j]-kMin[j]);    } but just D[2] was okay. Whats the problem?Well, looks like you don''t understand fully the underlying mathematical notions For the sake of clarity, I''ll note kMean = (kMax + kMin) / 2 and ai = kBox.Axis(i)What you want is to "translate" kMean from box axes coordinate system to box center coordinate system. This is equivalent to performing the following rotation :r = [a0,a1,a2] * kMeanwhere [a0,a1,a2] is the matrix formed by the 3 vectors, so that the first column of the matrix is a0... and r is a Vector3. Now if you look at the result, you''ll see that :r[0] = a0[0] * kMean[0] + a1[0] * kMean[1] + a2[0] * kMean[2]r[1] = a0[1] * kMean[0] + a1[1] * kMean[1] + a2[1] * kMean[2]r[2] = a0[2] * kMean[0] + a1[2] * kMean[1] + a2[2] * kMean[2]whereas your tx was :tx[0] = kMean[0] * (a0[0] + a0[1] + a0[2])...Hence the error Now the first bit of code I posted was way more compact because at each step it updated the 3 components simultaneously. So if it is possible, you should use it instead of the stuff above : less lines => less errors :D;  Thank you very much overnhet. In fact a simple thank you is not sufficient. If i code something useful (!), i will make it freeware for the sake of the people here. Vector3 kMean = ((Real)0.5)*(kMax + kMin); for (j = 0; j < 3; j++){kBox.Center() += kBox.Axis(j) * kMean[j];kBox.Extent(j) = ((Real)0.5)*(kMax[j]-kMin[j]);}makes everything ok. thanks again...