Jump to content
  • Advertisement
Sign in to follow this  
Ademan555

Dumb Question

This topic is 4951 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Well, i have my 2d engine, just about up and running, but there are a few things missing, an entity manager, and COLLISION DETETCTION to name the 2 most important ones. So what i had planned on was using rectangle/rectangle collision for this. And i can figure out if there was a collision and all that, but then i got to thinking! (thinking can be a dangerous thing sometimes :-p) what about the case where one rectangle penetrates another?! what then?my plan went something like this, find out the vector that would bring the rectangle out of the other rectangle, and then move it there, but then i dont know what to do from there, to i guess... calculate how much time was lost there and do something else with that velocity if anyone could make sense of my ramblings, and give me a clue on what i should be doing, thatd be great thanks -Dan

Share this post


Link to post
Share on other sites
Advertisement
What we do is form a line L between the centres of the rectangles and constrain the velocity vectors to not point towards each other along this line (using a simple projection of the vector onto the line perpendicular to L). This allows the objects to slide off each other and while they will penetrate a little bit they don't get stuck (and can also stack). This is just a 2D version of the standard sliding mechanism.

Actually that's not quite true, the line L is snapped to one of the eight compass directions. This stops all objects acting like circles and means that stacking works far better (before they'd just slide off each other if they weren't stacked directly above one another).

If you mean how to stop fast moving objects missing collisions, what we do is cut each objects velocity into reasonable sized sections and do multiple collision steps. This is ok for our game as there usually aren't many collidable objects that aren't culled by the collision detector, YMMV.

Share this post


Link to post
Share on other sites
Cool, thanks, but how would you go about snapping it to a compass direction? get the angle between the vector and the x axis then compare that with other angles and from there determine which its closest to? or is there a faster way that avoids using trig functions?

edit: and for a couple of recangles, wouldnt you snap to 4 directions?

thanks
-Dan

Share this post


Link to post
Share on other sites
Yeah, you could use 4 directions (I started off doing that), but I like them to slide off at the corners - they look more like octagons than rectangles for collision purposes.

This is the code I use:


const Vector2 cardinals[] =
{
Vector2(1.0,0.0),
Vector2(-1.0,0.0),
Vector2(0.0,1.0),
Vector2(0.0,-1.0),
Vector2(0.707107F,0.707107F),
Vector2(-0.707107F,0.707107F),
Vector2(0.707107F,-0.707107F),
Vector2(-0.707107F,-0.707107F),
};

// v is normalized
Vector2 ClampToCardinal(const Vector2& v)
{
float min_d = -9999.0;
int min_i = -1;

for(int i=0;i<8;i++)
{
float d = Dot(v,cardinals);

if(d > min_d)
{
min_d = d;
min_i = i;
}
}

return cardinals[min_i];
}

Share this post


Link to post
Share on other sites
Hrm, im still kidna confused, what im tryin to do now is use a ray/box intersection to find the point on the box where the collision axis crosses the box and then find that on the other box, and then move those two points together based on some weighting that i havent figured out yet... lol... this could be interesting
-Dan

Share this post


Link to post
Share on other sites
sorry to bump, i guess im really interested to find out how you would resolve the penetration, because obviously that is bad (master of the obvious :-D ), i think i have a solution, but to do it i need to intersect a ray with the bounding box, anyone know how to do that? i guess it shouldnt be too hard if i just find line-line intersection then test if its no the part of the line i want (the actual ray) and make sure that that collision part is on one of the 4 segments of the bounding box

i dunno... heh
-Dan

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Well, I built a class for mathmatics regarding planes. It can do what you want to do and I know how to do it but I don´t think if it´s fast or state-of-the-art enough.
Anyway, here you go:

The prerequisite is that you have a plane defined by a normal (a, b, c), a point (x, y ,z) and a parameter d. It also has to have a boundary. In case of my class this boundary has to be convex to properly work (but I am going to change that as soon as I find some time).

So .. with the a.m. parameters you got your plane like

ax + by + cz = -d

From this equation you get your parameter d.

Here now is the method to make the intersection test:


// Tests a ray against the plane to find an intersection
//
// Parameter : p1 = point of origin of the ray
// dir = direction of the ray
// res = return value -> intersection point
// boundCheck = false -> plane is treated as infinite (DEFAULT)
// true -> plane bounds are considered with the check
// Return : int = 0 == no intersection, 1 == intersection, 2 == line on plane
int CPlane::IntersectsWithRay( vector p1, vector dir, vector &res, bool boundCheck )
{
double len = dir.len();

if( len > 0.0 )
dir /= len();

res.set_x( 0.0 );
res.set_y( 0.0 );
res.set_z( 0.0 );

// equation of a line (ray) is P = P1 + t * V
// where P1 is the initial point and V the vector to the other
// t is a variable scalar and scales through the vector, thus defining the exact position on the line

// so inserting this into the plane equation gives ...
//
// A * (P1.x + t * V.x) + B * (P1.y + t * V.y) + C * (P1.z + t * V.z) = -D
//
// ... resolving that for 't' makes ...
//
// A * P1.x + B * P1.y + C * P1.z + D <-- numerator
// t = ----------------------------------------
// A * -V.x + B * -V.y + C * -V.z <-- denominator
//
// ... with that we can solve the line equation !


// calculate numerator
double numerator = m_dA * p1.x() + m_dB * p1.y() + m_dC * p1.z() + m_dD;
// calculate denominator
double denominator = m_dA * -dir.x() + m_dB * -dir.y() + m_dC * -dir.z();

if( numerator <= m_dEps && numerator >= -m_dEps &&
denominator <= m_dEps && denominator >= -m_dEps ) // line on plane
return 2;
else if( denominator <= m_dEps && denominator >= -m_dEps ) // line parallel to plane (not intersecting it)
return 0;

double t = numerator/denominator;

res = p1 + t * dir;

if( t >= -m_dEps )
{
if( m_bPlaneWithBounds && boundCheck )
{
if( m_oBoundaryPoints == NULL || m_iNumBoundPoints < 3 )
ASSERT(0); // plane not valid -> not enough points
if( PointInsideBounds( res ) )
return 1;
else
return 0;
}
else
return 1;
}
else
return 0;
}




So the first part of this method just checks whether or not the ray intersects with the infinite plane. If it does there will be another check that determines whether or not the intersection point lies inside the boundary. Could look like this:



// Checks if a certain point is inside the defined bounding box of the '2D' plane
// (that means the depth is not taken into account, so a point behind of before the plane may also be inside
// the boundary - use PointOnPlane() function to cover that)
// Parameter : p = point to be checked against the boundary
// Return : true or false
//
bool CPlane::PointInsideBounds( vector p )
{
if( m_oBoundaryPoints == NULL || m_iNumBoundPoints < 3 )
{
ASSERT(0); // plane not valid -> not enough points
return false;
}

for( int i = 0; i < m_iNumBoundPoints; i++ )
{
int index0 = i;
int index1 = i+1;
int index2 = i+2;

if( index1 == m_iNumBoundPoints )
{
index1 = 0;
index2 = 1;
}
else if( index2 == m_iNumBoundPoints )
index2 = 0;

vector vec1 = m_oBoundaryPoints[index1] - m_oBoundaryPoints[index0];
vector vec2 = p - m_oBoundaryPoints[index0];

if( vec2.x() <= m_dEps && vec2.x() >= -m_dEps &&
vec2.y() <= m_dEps && vec2.y() >= -m_dEps &&
vec2.z() <= m_dEps && vec2.z() >= -m_dEps )
{
return true;
}

// Normalize vectors
double len = vec1.len();
if( len > 0.0 )
vec1 /= len;

len = vec2.len();
if( len > 0.0 )
vec2 =/ len;

// Calculate Cross Product
vector cross1( ( v1Norm.y() * v2Norm.z() ) - ( v1Norm.z() * v2Norm.y() ),
( v1Norm.z() * v2Norm.x() ) - ( v1Norm.x() * v2Norm.z() ),
( v1Norm.x() * v2Norm.y() ) - ( v1Norm.y() * v2Norm.x() ) );

vector vec3 = m_oBoundaryPoints[index2] - m_oBoundaryPoints[index0];
// Normalize vector
len = vec3.len();
if( len > 0.0 )
vec3 /= len;

// Calculate Cross Product
vector cross2( ( v1Norm.y() * v3Norm.z() ) - ( v1Norm.z() * v3Norm.y() ),
( v1Norm.z() * v3Norm.x() ) - ( v1Norm.x() * v3Norm.z() ),
( v1Norm.x() * v3Norm.y() ) - ( v1Norm.y() * v3Norm.x() ) );

double dotProduct = cross1.x()*cross2.x() + cross1.y()*cross2.y() +cross1.z()*cross2.z();

if( dotProduct < -m_dEps )
return false;
}
return true;
}}



That´s it. It works, but I know I am not that decent a coder, so there might be lots of stuff that could be better/faster/easier.

Anyway, hope it helps.

Twist

Share this post


Link to post
Share on other sites
Ops .. second code piece had some errors because of some changes I made. And I am not allowed to edit my previous post due to a login problem.
So here´s the working one :).


// Checks if a certain point is inside the defined bounding box of the '2D' plane
// (that means the depth is not taken into account, so a point behind of before the plane may also be inside
// the boundary - use PointOnPlane() function to cover that)
// Parameter : p = point to be checked against the boundary
// Return : true or false
//
bool CPlaneMath::PointInsideBounds( vector p )
{
if( m_oBoundaryPoints == NULL || m_iNumBoundPoints < 3 )
{
ASSERT(0); // plane not valid -> not enough points
return false;
}

for( int i = 0; i < m_iNumBoundPoints; i++ )
{
int index0 = i;
int index1 = i+1;
int index2 = i+2;

if( index1 == m_iNumBoundPoints )
{
index1 = 0;
index2 = 1;
}
else if( index2 == m_iNumBoundPoints )
index2 = 0;

vector vec1 = m_oBoundaryPoints[index1] - m_oBoundaryPoints[index0];
vector vec2 = p - m_oBoundaryPoints[index0];

if( vec2.x() <= m_dEps && vec2.x() >= -m_dEps &&
vec2.y() <= m_dEps && vec2.y() >= -m_dEps &&
vec2.z() <= m_dEps && vec2.z() >= -m_dEps )
{
return true;
}

// Normalize vectors
double len = vec1.len();
if( len > 0.0 )
vec1 /= len;

len = vec2.len();
if( len > 0.0 )
vec2 /= len;

// Calculate Cross Product
vector cross1( ( vec1.y() * vec2.z() ) - ( vec1.z() * vec2.y() ),
( vec1.z() * vec2.x() ) - ( vec1.x() * vec2.z() ),
( vec1.x() * vec2.y() ) - ( vec1.y() * vec2.x() ) );

vector vec3 = m_oBoundaryPoints[index2] - m_oBoundaryPoints[index0];
// Normalize vector
len = vec3.len();
if( len > 0.0 )
vec3 /= len;

// Calculate Cross Product
vector cross2( ( vec1.y() * vec3.z() ) - ( vec1.z() * vec3.y() ),
( vec1.z() * vec3.x() ) - ( vec1.x() * vec3.z() ),
( vec1.x() * vec3.y() ) - ( vec1.y() * vec3.x() ) );

double dotProduct = cross1.x()*cross2.x() + cross1.y()*cross2.y() +cross1.z()*cross2.z();

if( dotProduct < -m_dEps )
return false;
}
return true;
}



Twist

Share this post


Link to post
Share on other sites
Simply put I don't worry about the bit of penetration that goes on. The velocity clipping guarantees that collisions are detected before objects penetrate too deep and after they have penetrated they are absolutely forbidden to move any closer. I don't try and move them apart since we don't need a full physics simulation. This would involve far more complex constraints to allow stacking, quite doable but simply not worth it for our game.

Saying that, you only notice the penetration if you're really looking for it, the sprites have irregular shapes anyway which hides it even more.

Now if two objects are *spawned* penetrating, then there is still no problem. Although the objects can't move towards each other they are fully free to move apart. The only issue then is what it looks like - if you don't like it make sure they don't do it :)

If you really want a ray/rect intersection routine, try this:

R(t) = O + D * t (ray equation)

Rectangle defined by corners (x0,y0) (x1,y1)


P(t') = [ x0 + (x1 - x0) * t' ]
[ y0 ]


Is a point on the top (with t' in [0,1]), plug this into R(t):


R(t) = P(t')

Ox + Dx * t = x0 + (x1 - x0) * t'
Oy + Dy * t = y0

t = (y0 - Oy) / Dy

t' = (Ox + Dx * t - x0) / (x1 - x0)


Now check


(1) t > 0
(2) t' is in [0,1]


Do this for each side, discarding those which don't satisfy conditions (1) and (2). Then the side with least t is the closest side.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!