Woof, looks like I'm gonna need a couple of Advil before I try to draw this out on paper... [grin]
Thanks a bazillion for the explanation, oliii, I don't think there would be any way I'd begin to understand this if it weren't for you. You ROCK! I'll read up on what you've posted and see if I can figure why this works, and then I can better apply this new knowledge to my future games. I may pick your brain a little later on getting this to work with "line-rotated box" collisions, but I'd better try to learn how to do it with simple boxes first. Time to start reading... Wish me luck!
Thanks again, I REALLY appreciate it!
Adding vector from another moving object...
it's not just for you, you know :) I intend to get that thread stickified (maybe slightly modified), so it's done once and for all. Any comments appreciated, then I can edit my posts as you try to decipher the algo, add a couple of pics...
Now onto oriented boxes.
If you've been reading stuff on the SAT, you would know that the algorithms basically gets decomposed into a number of 1D interval intersection tests, where each object get 'projected' on a given axis.
The axes of projection, for 2D polygons, are basically the vectors perpendicular to edges. For an oriented box, since the 4 edges are either perpendicular or parallel, the number of axes per boxes is only 2. For 2 oriented boxes, we will have to test 4 separation axes in all.
so now, we need a way to find the projection interval of a box along an arbotrary axis, for example, the projection interval of box A when projected on one axis of box B.
for boxes, it is
Now that we have both min and max for both boxes along an arbitrary axis, we can pass it to the PointSlabCollision() function. Here, I do away with the concept of point-box representation, and use the two boxes' intervals directly. It just a juggling of scalar values anyway.
OrientatedBoxesCollision.cpp
As a side note, AABBoxes have another added property, where the boxes also share the same axes of projections, that reduces the tests between two boxes to only 2 (along the X and Y axis).
From the code I presented, you can see that PointSlabCollision() is effectively testing two interval along any arbitrary axis.
This can be used for arbitrary convex polygons as well. Like axis-aligned boxes and oriented boxes, convex polygons are also the result of the intersection of slabs.
from there, it's quite easy to see what to do next. Form the picture, you can see that slabs are basically following edges of the polygons. so in general, there are as many slabs to test as there are edges for each polygons (disregarding parallel edges, like in the first picture). Second, each slab will be parallel to edges, so the intervals we need will have to be projected on the perpendicular axis of the slab, that is, the vector perpendicular to the edge corresponding to the slab.
so the main loop function will simply be
And now, what we need is a way for calculating the interval for a polygon. A simple min-max expansion should do.
One last thing peculiar to using non-normalised arbitrary axes.
First of all, in case of collision, becasue all interval calculations, and various dot products, everything is scaled by the axis length. This is fine, as in the end, when you calculate the time of collision, you dived quantites which are both scaled by axis length. In essence, it cancels out, and all is good.
In case of an intersection, you have to factor in the axis length in the equations, to get a proper MTD vector. When calculating the mtd, quantities are in fact scaled but the SQUARED length of the axis. Which is grand, since all we have to do is divide the quantities by the square length, which is easy and inexpensive to calculate.
ConvexPolygonCollision.cpp
[Edited by - oliii on November 14, 2005 2:22:45 AM]
If you've been reading stuff on the SAT, you would know that the algorithms basically gets decomposed into a number of 1D interval intersection tests, where each object get 'projected' on a given axis.
The axes of projection, for 2D polygons, are basically the vectors perpendicular to edges. For an oriented box, since the 4 edges are either perpendicular or parallel, the number of axes per boxes is only 2. For 2 oriented boxes, we will have to test 4 separation axes in all.
so now, we need a way to find the projection interval of a box along an arbotrary axis, for example, the projection interval of box A when projected on one axis of box B.
for boxes, it is
void CalculateBoxIntervalOnAxis(const Vector& Axis, const Vector& Pos, const Vector& Ext, const Vector* Dir, float& min, float& max){ // projected centre on axis float p = Pos * Axis; // projected box extents on axis float r = fabs(Dir[0] * Axis) * Ext.x + fabs(Dir[1] * Axis) * Ext.y; // min and max of the box min = p - r; max = p + r;}Now that we have both min and max for both boxes along an arbitrary axis, we can pass it to the PointSlabCollision() function. Here, I do away with the concept of point-box representation, and use the two boxes' intervals directly. It just a juggling of scalar values anyway.
//===========================================================================//// COLLISION CODE////===========================================================================void CalculateBoxIntervalOnAxis(const Vector& Axis, const Vector& Pos, const Vector& Ext, const Vector* Dir, float& min, float& max){ float p = Pos * Axis; float r = fabs(Dir[0] * Axis) * Ext.x + fabs(Dir[1] * Axis) * Ext.y; min = p - r; max = p + r;} bool PointSlabCollision(float slabamin, float slabamax, float slabbmin, float slabbmax, float displacement, const Vector& SlabNormal, float& tfirst, Vector& Nfirst, float& tlast, Vector& Nlast, Vector& MTD, float& mtdsquared, bool& bCollision){ float dist_0 = slabamin - slabbmax; float dist_1 = slabamax - slabbmin; // point inside the slab bool bIntersect = (dist_0 < 0.0f && dist_1 > 0.0f); if (bIntersect) { // the vector we use to push the point outside the slab float slabmtd = (fabs(dist_0) < fabs(dist_1))? dist_0 : dist_1; Vector SlabMTD = SlabNormal * slabmtd; float slabmtdsquared = SlabMTD * SlabMTD; // Check if that push vector is smaller than our curent push vector if (slabmtdsquared < mtdsquared || mtdsquared < 0.0f) { MTD = SlabMTD; mtdsquared = slabmtdsquared; } } // if not moving, then we can only // collide through intersections if (fabs(displacement) < 1.0E-8f) return bIntersect; float tslab0 = (dist_0) / (displacement); float tslab1 = (dist_1) / (displacement); float tslabenter; float tslabexit; float sign; if(tslab0 < tslab1) { tslabenter = tslab0; tslabexit = tslab1; sign = -1.0f; } else { tslabenter = tslab1; tslabexit = tslab0; sign = 1.0f; } if (tslabenter > tfirst) { tfirst = tslabenter; Nfirst = SlabNormal * sign; bCollision = true; } if (tslabexit < tlast) { tlast = tslabexit; Nlast = SlabNormal * -sign; } if (tlast < tfirst) return false; return true;}bool IntervalColllision(const Vector& Apos, const Vector& Aext, const Vector* Adir, const Vector& Bpos, const Vector& Bext, const Vector* Bdir, const Vector& Axis, const Vector& Displacement, float& tfirst, Vector& Nfirst, float& tlast, Vector& Nlast, Vector& MTD, float& mtdsquared, bool& bCollision){ float amin, amax; float bmin, bmax; CalculateBoxIntervalOnAxis(Axis, Apos, Aext, Adir, amin, amax); CalculateBoxIntervalOnAxis(Axis, Bpos, Bext, Bdir, bmin, bmax); float disp = Displacement * Axis; return PointSlabCollision( amin, amax, bmin, bmax, disp, Axis, tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision);}bool BoxBoxCollision(const Vector& Apos, const Vector& Aext, const Vector* Adir, const Vector& Bpos, const Vector& Bext, const Vector* Bdir, const Vector& Displacement, float& tfirst, Vector& Nfirst, Vector& MTD){ const float tolerance = 1.0E-8f; bool bCollision = false; float mtdsquared = -1.0f; MTD = Vector(0, 0); tfirst = 0.0f - tolerance; Nfirst = Vector(0, 0); float tlast = 1.0f + tolerance; Vector Nlast = Vector(0, 0); if (!IntervalColllision(Apos, Aext, Adir, Bpos, Bext, Bdir, Adir[0], Displacement, tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision)) { return false; } if (!IntervalColllision(Apos, Aext, Adir, Bpos, Bext, Bdir, Adir[1], Displacement, tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision)) { return false; } if (!IntervalColllision(Apos, Aext, Adir, Bpos, Bext, Bdir, Bdir[0], Displacement, tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision)) { return false; } if (!IntervalColllision(Apos, Aext, Adir, Bpos, Bext, Bdir, Bdir[1], Displacement, tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision)) { return false; } if (bCollision) { // check if we found a valid time of collision if(tfirst < 0.0f || tfirst > 1.0f) return false; MTD = Vector(0, 0); } else { tfirst = 0.0f; Nfirst = MTD; Nfirst.Normalise(); } return true;}OrientatedBoxesCollision.cpp
As a side note, AABBoxes have another added property, where the boxes also share the same axes of projections, that reduces the tests between two boxes to only 2 (along the X and Y axis).
From the code I presented, you can see that PointSlabCollision() is effectively testing two interval along any arbitrary axis.
This can be used for arbitrary convex polygons as well. Like axis-aligned boxes and oriented boxes, convex polygons are also the result of the intersection of slabs.
from there, it's quite easy to see what to do next. Form the picture, you can see that slabs are basically following edges of the polygons. so in general, there are as many slabs to test as there are edges for each polygons (disregarding parallel edges, like in the first picture). Second, each slab will be parallel to edges, so the intervals we need will have to be projected on the perpendicular axis of the slab, that is, the vector perpendicular to the edge corresponding to the slab.
so the main loop function will simply be
bool PolygonPolygonCollision(const Vector* Averts, int Anumverts, const Vector* Bverts, int Bnumverts, const Vector& Displacement, float& tfirst, Vector& Nfirst, Vector& MTD){ const float tolerance = 1.0E-8f; bool bCollision = false; float mtdsquared = -1.0f; MTD = Vector(0, 0); tfirst = 0.0f - tolerance; Nfirst = Vector(0, 0); float tlast = 1.0f + tolerance; Vector Nlast = Vector(0, 0); int j = Anumverts-1; for(int i = 0; i < Anumverts; j = i, i ++) { Vector Edge = Averts - Averts[j]; Vector Axis(-Edge.y, Edge.x); // direction perpendicular to edge if (!IntervalColllision(Averts, Anumverts, Bverts, Bnumverts, Axis, Displacement, tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision)) { return false; } } j = Bnumverts-1; for(int i = 0; i < Bnumverts; j = i, i ++) { Vector Edge = Bverts - Bverts[j]; Vector Axis(-Edge.y, Edge.x); // direction perpendicular to edge if (!IntervalColllision(Averts, Anumverts, Bverts, Bnumverts, Axis, Displacement, tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision)) { return false; } } if (bCollision) { // check if we found a valid time of collision if(tfirst < 0.0f || tfirst > 1.0f) return false; MTD = Vector(0, 0); } else { tfirst = 0.0f; Nfirst = MTD; Nfirst.Normalise(); } return true;}And now, what we need is a way for calculating the interval for a polygon. A simple min-max expansion should do.
void CalculatePolygonIntervalOnAxis(const Vector& Axis, const Vector* Vertices, int inumverts, float& min, float& max){ min = max = Vertices[0] * Axis; for(int i = 1; i < inumverts; i ++) { float p = Vertices * Axis; if (p < min) min = p; else if (p > max) max = p; }}One last thing peculiar to using non-normalised arbitrary axes.
First of all, in case of collision, becasue all interval calculations, and various dot products, everything is scaled by the axis length. This is fine, as in the end, when you calculate the time of collision, you dived quantites which are both scaled by axis length. In essence, it cancels out, and all is good.
In case of an intersection, you have to factor in the axis length in the equations, to get a proper MTD vector. When calculating the mtd, quantities are in fact scaled but the SQUARED length of the axis. Which is grand, since all we have to do is divide the quantities by the square length, which is easy and inexpensive to calculate.
float dist_0 = slabamin - slabbmax; // value scaled by axis length float dist_1 = slabamax - slabbmin; // value scaled by axis length // point inside the slab bool bIntersect = (dist_0 < 0.0f && dist_1 > 0.0f); if (bIntersect) { // the vector we use to push the point outside the slab float slabmtd = (fabs(dist_0) < fabs(dist_1))? dist_0 : dist_1; float slabnormalsquared = SlabNormal * SlabNormal; // Slab Normal isn't garanteed to be normalised Vector SlabMTD = SlabNormal * (slabmtd / slabnormalsquared); float slabmtdsquared = SlabMTD * SlabMTD; // Check if that push vector is smaller than our curent push vector if (slabmtdsquared < mtdsquared || mtdsquared < 0.0f) { MTD = SlabMTD; mtdsquared = slabmtdsquared; } }ConvexPolygonCollision.cpp
[Edited by - oliii on November 14, 2005 2:22:45 AM]
for 3D, there is only a little more work to do. I've you've experimented with the SAT in 3D, you'll know that the separation axes are made of the surface normals, and the cross product of edges between surfaces on both objects.
and example. Take two triangles (A0, A1, A2) and (B0, B1, B2). Each are made of one surface, and three edges. the separation axes to test will be
(A2 - A1) x (A1 - A0) // triangle normal
(B2 - B1) x (B1 - B0) // triangle normal
(A1 - A0) x (B1 - B0) // first of of A cross first edge of B
(A1 - A0) x (B2 - B1) // first of of A cross second edge of B
(A1 - A0) x (B0 - B2) // first of of A cross third edge of B
(A2 - A1) x (B1 - B0) // second of of A cross first edge of B
(A2 - A1) x (B2 - B1) // second of of A cross second edge of B
(A2 - A1) x (B0 - B2) // second of of A cross third edge of B
(A0 - A2) x (B1 - B0) // second of of A cross first edge of B
(A0 - A2) x (B2 - B1) // second of of A cross second edge of B
(A0 - A2) x (B0 - B2) // second of of A cross third edge of B
You also need to implement the inteerval calculation function. Again, we can use the same min-max calculations as for 2D.
all in all, you get
One thing you have to watch out though, for 2 coplanar polygons. In that case, you should revert back to the 2D type of algorithm (where you use vectors perpendicular to the edges, and also to the polygon plane now). The algo above will most likely fail.
all the other functions do not have to be modified. Except that you are using 3D vectors, of course :)
for oriented boxes, the algorithm is similar to 2D boxes. you have now 15 axes.
Adir[0]
Adir[1]
Adir[2]
Bdir[0]
Bdir[1]
Bdir[2]
Adir[0] x Bdir[0]
Adir[0] x Bdir[1]
Adir[0] x Bdir[2]
Adir[1] x Bdir[0]
Adir[1] x Bdir[1]
Adir[1] x Bdir[2]
Adir[2] x Bdir[0]
Adir[2] x Bdir[1]
Adir[2] x Bdir[2]
and the interval function is now
so there. That should cover everything for 2D and 3D polygonal collisions.
3DBoxPolygonCollision.cpp
DXInputs.cpp
DXInputs.h
[Edited by - oliii on November 14, 2005 2:32:56 AM]
and example. Take two triangles (A0, A1, A2) and (B0, B1, B2). Each are made of one surface, and three edges. the separation axes to test will be
(A2 - A1) x (A1 - A0) // triangle normal
(B2 - B1) x (B1 - B0) // triangle normal
(A1 - A0) x (B1 - B0) // first of of A cross first edge of B
(A1 - A0) x (B2 - B1) // first of of A cross second edge of B
(A1 - A0) x (B0 - B2) // first of of A cross third edge of B
(A2 - A1) x (B1 - B0) // second of of A cross first edge of B
(A2 - A1) x (B2 - B1) // second of of A cross second edge of B
(A2 - A1) x (B0 - B2) // second of of A cross third edge of B
(A0 - A2) x (B1 - B0) // second of of A cross first edge of B
(A0 - A2) x (B2 - B1) // second of of A cross second edge of B
(A0 - A2) x (B0 - B2) // second of of A cross third edge of B
You also need to implement the inteerval calculation function. Again, we can use the same min-max calculations as for 2D.
void CalculateIntervalOnAxis(const Vector& Axis, const Vector* Vertices, int inumverts, float& min, float& max){ min = max = Vertices[0] * Axis; for(int i = 1; i < inumverts; i ++) { float p = Vertices * Axis; if (p < min) min = p; else if (p > max) max = p; }}all in all, you get
bool 3DPolygonPolygonCollision( const Vector* Averts, int Anumverts, const Vector* Bverts, int Bnumverts, const Vector& Displacement, float& tfirst, Vector& Nfirst, Vector& MTD){ const float tolerance = 1.0E-8f; bool bCollision = false; float mtdsquared = -1.0f; MTD = Vector(0, 0, 0); tfirst = 0.0f - tolerance; Nfirst = Vector(0, 0, 0); float tlast = 1.0f + tolerance; Vector Nlast = Vector(0, 0, 0); Vector Axis; Axis = (Averts[2] - Averts[1]) ^ (Averts[1] - Averts[0]); // Polygon A normal if (!IntervalColllision(Averts, Anumverts, Bverts, Bnumverts, Axis, Displacement, tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision)) { return false; } Axis = (Bverts[2] - Bverts[1]) ^ (Bverts[1] - Bverts[0]); // Polygon B normal if (!IntervalColllision(Averts, Anumverts, Bverts, Bnumverts, Axis, Displacement, tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision)) { return false; } int j = Anumverts-1; for(int i = 0; i < Anumverts; j = i, i ++) { Vector EdgeA = Averts - Averts[j]; k = Bnumverts-1; for(int l = 0; l < Bnumverts; k = l, l ++) { Vector EdgeB = Bverts[l] - Bverts[k]; Axis = EdgeA ^ EdgeB; // cross product of edges // degenerate axis. if (Axis * Axis < 1.0E-4f) continue; if (!IntervalColllision(Averts, Anumverts, Bverts, Bnumverts, Axis, Displacement, tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision)) { return false; } } } if (bCollision) { // check if we found a valid time of collision if(tfirst < 0.0f || tfirst > 1.0f) return false; MTD = Vector(0, 0); } else { tfirst = 0.0f; Nfirst = MTD; Nfirst.Normalise(); } return true;}One thing you have to watch out though, for 2 coplanar polygons. In that case, you should revert back to the 2D type of algorithm (where you use vectors perpendicular to the edges, and also to the polygon plane now). The algo above will most likely fail.
bool 3DCoplanarPolygonPolygonCollision( const Vector* Averts, int Anumverts, const Vector* Bverts, int Bnumverts, const Vector& Displacement, float& tfirst, Vector& Nfirst, Vector& MTD){ const float tolerance = 1.0E-8f; bool bCollision = false; float mtdsquared = -1.0f; MTD = Vector(0, 0, 0); tfirst = 0.0f - tolerance; Nfirst = Vector(0, 0, 0); float tlast = 1.0f + tolerance; Vector Nlast = Vector(0, 0, 0); Vector PolyNormal = (Averts[2] - Averts[1]) ^ (Averts[1] - Averts[0]); if (!IntervalColllision(Averts, Anumverts, Bverts, Bnumverts, PolyNormal, Displacement, tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision)) { return false; } int j = Anumverts-1; for(int i = 0; i < Anumverts; j = i, i ++) { Vector Edge = Averts - Averts[j]; Vector Axis =Edge ^ PolyNormal; if (!IntervalColllision(Averts, Anumverts, Bverts, Bnumverts, Axis, Displacement, tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision)) { return false; } } j = Bnumverts-1; for(int i = 0; i < Bnumverts; j = i, i ++) { Vector Edge = Bverts - Bverts[j]; Vector Axis =Edge ^ PolyNormal; if (!IntervalColllision(Averts, Anumverts, Bverts, Bnumverts, Axis, Displacement, tfirst, Nfirst, tlast, Nlast, MTD, mtdsquared, bCollision)) { return false; } } if (bCollision) { // check if we found a valid time of collision if(tfirst < 0.0f || tfirst > 1.0f) return false; MTD = Vector(0, 0); } else { tfirst = 0.0f; Nfirst = MTD; Nfirst.Normalise(); } return true;}all the other functions do not have to be modified. Except that you are using 3D vectors, of course :)
for oriented boxes, the algorithm is similar to 2D boxes. you have now 15 axes.
Adir[0]
Adir[1]
Adir[2]
Bdir[0]
Bdir[1]
Bdir[2]
Adir[0] x Bdir[0]
Adir[0] x Bdir[1]
Adir[0] x Bdir[2]
Adir[1] x Bdir[0]
Adir[1] x Bdir[1]
Adir[1] x Bdir[2]
Adir[2] x Bdir[0]
Adir[2] x Bdir[1]
Adir[2] x Bdir[2]
and the interval function is now
void CalculateBoxIntervalOnAxis(const Vector& Axis, const Vector& Pos, const Vector& Ext, const Vector* Dir, float& min, float& max){ float p = Pos * Axis; float r = fabs(Dir[0] * Axis) * Ext.x + fabs(Dir[1] * Axis) * Ext.y + fabs(Dir[2] * Axis) * Ext.z; min = p - r; max = p + r;}so there. That should cover everything for 2D and 3D polygonal collisions.
3DBoxPolygonCollision.cpp
DXInputs.cpp
DXInputs.h
[Edited by - oliii on November 14, 2005 2:32:56 AM]
that is one of the most heroic posts i have ever seen....
for another quick reference and explaination of linear interpolation, i found this site helpful:
http://gpwiki.org/index.php/Linear_Interpolation
for another quick reference and explaination of linear interpolation, i found this site helpful:
http://gpwiki.org/index.php/Linear_Interpolation
Author
Awesome oliii, you ROCK! This should either be made into a 'sticky post' or turned into a GameDev article.
I've been trying to graph this all on paper, and I get lost right about here...
I'm having a hard time getting the 'raw math' behind this function... Would somebody break this down into its x/y components? Also, would you define 'Ext' and 'Dir' and how to get the values behind those variables? Thanks!
I've been trying to graph this all on paper, and I get lost right about here...
void CalculateBoxIntervalOnAxis(const Vector& Axis, const Vector& Pos, const Vector& Ext, const Vector* Dir, float& min, float& max){ // projected centre on axis float p = Pos * Axis; // projected box extents on axis float r = fabs(Dir[0] * Axis) * Ext.x + fabs(Dir[1] * Axis) * Ext.y; // min and max of the box min = p - r; max = p + r;}I'm having a hard time getting the 'raw math' behind this function... Would somebody break this down into its x/y components? Also, would you define 'Ext' and 'Dir' and how to get the values behind those variables? Thanks!
Author
Oh, and here's a very good site to go to learn the 'basics' of this sort of math.
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry1
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry1
Quote:Original post by Dookie
Awesome oliii, you ROCK! This should either be made into a 'sticky post' or turned into a GameDev article.
I've been trying to graph this all on paper, and I get lost right about here...void CalculateBoxIntervalOnAxis(const Vector& Axis, const Vector& Pos, const Vector& Ext, const Vector* Dir, float& min, float& max){ // projected centre on axis float p = Pos * Axis; // projected box extents on axis float r = fabs(Dir[0] * Axis) * Ext.x + fabs(Dir[1] * Axis) * Ext.y; // min and max of the box min = p - r; max = p + r;}
I'm having a hard time getting the 'raw math' behind this function... Would somebody break this down into its x/y components? Also, would you define 'Ext' and 'Dir' and how to get the values behind those variables? Thanks!
I tend to take liberties with vector operators. if you look at the source, you should be able to break it up, or replace operators in the class by functions, like DotProduct(), CrossProduct(), Add(), Sub(). ANd then eventually replace it with pure C code (Vector_DotProduct(a, b), Vector_Add(result, a, b)).
anyway...
'*' with two vectors is a dot product.
so in raw maths.
void CalculateBoxIntervalOnAxis(const Vector& Axis, const Vector& Pos, const Vector& Ext, const Vector* Dir, float& min, float& max){ // box centre projected on axis float p = (Pos.x * Axis.x) + (Pos.y * Axis.y); // box dir[0] extent projectect on axis float d0 = fabs((Dir[0].x * Axis.x) + (Dir[0].y * Axis.y)) * Ext.x; // box dir[1] extent projectect on axis float d1 = fabs((Dir[1].x * Axis.x) + (Dir[1].y * Axis.y)) * Ext.x; // size of the box when projected on axis float r = d0 + d1; // min and max of the box min = p - r; max = p + r;}say Dir[0] represents the direction of the 'length' axis of the box.
say Dir[1] represents the direction of the 'width' axis of the box.
so d0 is basically how much of the 'length' of the box gets projected on the axis.
so d1 is basically how much of the 'width' of the box gets projected on the axis.
add both, and you get the overall size of the box when projected on the axis.
Author
Awesome, thanks for the fast reply oliii. That really helps! But I need one more definition, what is 'Ext' and how do I get its value?
Thanks again!
Thanks again!
Quote:Original post by Dookie"Ext" holds in each component the half-width (or "radius") of the box along the corresponding box axis.
Awesome, thanks for the fast reply oliii. That really helps! But I need one more definition, what is 'Ext' and how do I get its value?
For separating-axis tests, oriented boxes are uniquely determined by a center position, three unit vectors specifying the orientation of the box (its axes), and three scalar values that describe how far the box extends along each of the three axes (the half-widths).
The reason the half-width is stored rather than, say, the full width (the diameter) is that it simplifies the testing that's done for a given axis.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
