Hello guys! I'm making 2D game, I finished graphical, sound, and stuff, also release some kind of physics, but which physics withoud coolest collisions? I'm tired looking in google, because I'm not such a great Geometrist guy and in enternet almost where good solutions exists only for 3D cases. So : Does anybody can give me fast solutions for finding collision by next things : You can use pseudo or C++ code... For handling collision I'm implement 4 approaches It's just for a test... Collision solving method's I'm planning to implement when I will be more smarter in this thread. So here is test aproaches definition:

Quote: bool IsOBBIntersectingOBB( const Vec2D &rect1_min, const Vec2D &rect1_max, const Vec2D &pos1, const Vec2D &vel1, const Mat2x2 &orient1, const Vec2D &rect2_min, const Vec2D &rect2_max, const Vec2D &pos2, const Vec2D &vel2, const Mat2x2 &orient2 ); bool IsAABBIntersectingAABB( const Vec2D &rect1_min, const Vec2D &rect1_max, const Vec2D &rect2_min, const Vec2D &rect2_max ); bool IsCircleIntersectingAABB( const Vec2D &rect_min, const Vec2D &rect_max, const Vec2D &circle_center, const float &circle_radius ); bool IsCircleIntersectingCircle( const Vec2D ¢er1, const Vec2D ¢er2, float radius1, float radius2 ); bool IsSegmentIntersectingSegment( const Vec2D &A1, const Vec2D &B1, const Vec2D &A2, const Vec2D &B2 );

IsOBBIntersectingOBB working really poor, because I'm using IsSegmentIntersectingSegment for each edge vs each edge test... And there can be many faults... I wish to add in every approaches also velocity variables to send there velocities before applying it to objects, because objects can moving really fast and I don't wanna miss each other before solving collisions. So If you guys can somehow help me whith implementing these next things : IsOBBIntersectingOBB IsOBBIntersectingCricle IsOBBIntersectingAABB IsLineSegmentIntersectingOBB IsLineSegmentIntersectingAABB And reimplement to add velocities IsCircleIntersectingAABB IsCircleIntersectingCircle I appreciate any help. All objects execept LineSegment have some velocities, so I need to know how to work around further... If you wish that I post here one of my poor implementations I post it..

This link is a great, informative article on the Separating Axis Theorem and how you use it to collide objects. It's high level, so it doesn't give much code, but that makes it applicable to *all* languages and libraries. You'll need some vector math skills for that. This is a good website to learn basic matrix and vector math, if you don't already have it.

I saw that site few days ago, as you can undestand it didn't give me much...
For example two months ago I trying to use "Box2D" but is soooo complicated in design... And "polycolly" with ideal porting working bad too...
That's why I need more real samples than just theorems or complicated big tech engines.

I tried to implement that last polycolly4 also do some converts of
BoxBoxCollision

So first is jitters, Dunno maybe because my Y axis is inverted in DX9 apps...
I try to cahnge all perp from lefthanded to right handed by it didn't help anyway...
I mean, it collides good, but if object under gravity influence, it will be slowly immersing into another static box, and this will be continuing since object not going to inside...
Also if object bounce several times and then just I pick him and try to put he's left side to another box, and I stop applying velocity... and after few seconds I see that polycolly ContactSolver begins do something with velocity... like 0.00001 and objects begin to slowly going from box(wall) but wtf? before that few seconds velocity was 0.0f where this goes from?....
I can put here a some small video to show what going on maybe is a major bug... :D Also I can put there a code of modified physenv from Cube3D to 2D for my current needs and how it works with polycolly4 coll test methods...

The Second is allow a little penetrations, I see that from DX9 project Vertices.cpp and this is really bad for me...

So don't think that I'm total n00b :D I'm just bad geometrist, before that 3 months messing around whit your's JunkYard where lots of old code for polycolly and so on.. So before I was just wrote lots of applications on WinAPI, and then I just start to play in god :D begin game devlopement from 2D.
And when I almost release all graphics stuff, i.e rendering as well, gui, sound, scripts, wow, so collision mess me up...

[Edited by - Lolmen on October 28, 2007 12:48:20 PM]

Using a 3rd party library especially 3D it's sounds bad for me... :)
I need a full control to see of what opportunities I can operate and use em in the best way...
Small example of what collision concept I'm holding in my mind now is a
collision checking, and collision responce if it is necessary ("collision layers")
All stuff below is a reference and applied approaches or (if you like that name more) functions.

1) collision checking (predicting)

There all methods is just a boolean tests without extra computations because we should use a CallBacks to determine do is just a test (example bullet hit player) or maybe we need compute extra MTD and stuff to solve collision...

I'm will be use a next objects:
1) AABB (Axis Aligned Bounding BOX ) simply is BBOX
2) OOBB (Object Oriented Bounding BOX ) simply OBB or Quad
3) Triangle
4) TriangleTree (for complicated objects)
5) Circle (because the term "Sphere" is in 3D geometry)
6) Ray ( ray trace )
7) LineSegment (a gap of line example : begins from vec A and ends at vec B)
8) Cubic Bezier Curve (Can be splitted onto simply line segments or splines)[ I'm use cubic Bezier curve as powerful tool in my level editor to apply some collision shape for something like concave arc or deformated shape of ground in my game.


first for almost of all convex objects and concave objects is AABB test
to predict do they are may to collide because is cheaper that use another...

bool IsAABBIntersectingAABB( CBoxedTile *A, CBoxedTile *B );

where we impacting from (for both of it)

BBOX mins maxs,
BBOX postion
BBOX velocity

for oriented quads (not a box) because of conception (mins/maxs) where x,y can be not aligned use something like:


bool IsQuadIntersectingQuad( const CQuad *A, const CQuad *B );
where we impacting from (for both of it)
quad mins maxs,
quad postion
quad velocity
quad orientation matrice

Not matter if one of quad is static...

For iterative test everything whith ray casting all objects should have a test with ray:

For AABB and quads:

bool IsRayIntersectingAABB( ray_trace_t &ray , CBoxedTile *T );
bool IsRayIntersectingQuad( ray_trace_t &ray , CQuad *pQuad );

where we impacting from next two things:

first is:

( nice ray conception vStart, vDir, max_length )
where components of struct ray_trace_t can be filled directly...
compomets to fill: fraction, hit_pos and ptr to hitted CBoxedTile...
for perspicuity of a picture: fraction = (hit_pos - startpos)/max_length; and Normal (perpendicular to hit flatness)

and a second

BBOX mins maxs,
BBOX postion
BBOX velocity

or

quad mins maxs,
quad postion
quad velocity
quad orientation matrice

For another objects the same concept:

all objects may have some velocity and orientation matrice...

bool IsLineSegIntersectingAABB( line_seg_t &line, CBoxedTile *pBBOX );
bool IsLineSegIntersectingQuad( line_seg_t &line, CQuad *pQuad );
bool IsCircleIntersectingAABB( CCircle *pCricle, CBoxedTile *pBBOX );
bool IsCircleIntersectingQuad( CCircle *pCricle, CQuad *pQuad );
bool IsTriangleIntersectingAABB( CTriangle *pCricle, CBoxedTile *pBBOX );
bool IsTriangleIntersectingQuad( CTriangle *pTri, CQuad *pQuad );
bool IsTriangleIntersectingTriangle( CTriangle *pTri, CTriangle *pTri );
bool IsLineSegItersectingTriangle( CTriangle *pTri, line_seg_t &line );
bool IsRayIntersectingTriangle( ray_trace_t &ray , CTriangle *pTri );
bool IsCircleIntersectingCircle( CCircle *pCircleA, CCircle *pCircleB );
bool IsLineSegmentIntersectingCircle( CCircle *pCircle, line_seg_t &line );
bool IsRayIntersedtingLineSegment( ray_trace_t &ray, line_seg_t &line );
bool IsRayIntersectingRay( ray_trace_t &A, ray_trace_t &B );

A complicated objects before testing more accuracy we make a AABB of triangle tree and if this AABB intersecting with something we provide testing something with this tree:

bool IsTriangleTreeIntersectingCircle( std::vector<CTriangle*> &tree, CCircle *pCircle );
bool IsTriangleTreeIntersectingAABB( std::vector<CTriangle*> &tree, CBoxedTile *pBox );
bool IsTriangleTreeIntersectingQuad( std::vector<CTriangle*> &tree, CQuad *pQuad );
bool IsLineSegIntersectingTriangleTree( line_seg_t &line, std::vector<CTriangle*> &tree );
bool IsRayIntersectingTriangleTree( ray_trace_t &ray, std::vector<CTriangle*> &tree );

then for cubical Bezier curve...

typedef struct curve_t
{
Vector2D P1, P2, P3, P4;
Vector2D origin; // world position
};

example of how I use BezierCurve work in editor
std::vector<curve_t> m_curves;
somewhere:
script_parser::load_map( "maps/my_map01.txt" );

also before begins rendering:

while ( script_parser::parse_keys_va_arg_next( "curve_&d" ) != NULL )
{
std::string data = script_parser::get_key_value( script_parser::current_key();
Vector2D curve_control_points[4];
std_string_to_vec2f_array( data, curve_control_points, 4 );

curve_t curve;
curve.P1 = curve_control_points[0];
curve.P2 = curve_control_points[1];
curve.P3 = curve_control_points[2];
curve.P4 = curve_control_points[3];
m_curves.push_back( curve_t );
script_parser::go_to_next_key();
}

So rendering:

in render func

for ( size_t j = 0; j < m_curves.size(); j++ )
{
Vector2D p1 = m_curves[j].P1;
Vector2D p2 = m_curves[j].P2;
Vector2D p3 = m_curves[j].P3;
Vector2D p4 = m_curves[j].P4;

Vector2D q1, q2, q3;
Vector2D r1, r2;
Vector2D curvePos
float t;


for ( int i = 0; i < 1000; i++ )
{
t = static_cast<float>( i ) / 999.0f;
q1 = VecMa( p1, p2, t );
q2 = VecMa( p2, p3, t );
q3 = VecMa( p3, p4, t );
r1 = VecMa( q1, q2, t );
r2 = VecMa( q2. q3, t );
curvePos = VecMa( r1, r2, t ) + m_curves[j].origin;
PrimitiveRenderer::RenderPixel( curvePos.x, curvePos.y );
}
}

Thats how I undestand cubic curve from picture of wikipedia, because I'm not understand everything i.e from "high mathematic" e.g polyominals, multitudes and another complicated stuff.

So let's back to collisions checking:

bool IsAABBIntersectingCurve( CBoxedTile *pBBOX, curve_t &curve );
bool IsQuadIntersectingCurve( CQuad *pQuad, curve_t &curve );
and for each other objects and ray/line seg...
Curve always static.

2) collision responding (tricky way)

this coming soon...

So what I'm claim? Just help me with implementing everything what checking collision with Quads, Triangles (cuz they oriented too) and Curves, I'm ready to help or implement it by my self but as I said, high mathematics is a big area and I understanding just 15% of papers with explanation of these stuff curves/triangles/quads stuff e.g I not quite understand sense of that operations or approaches what these formulas use.
So if you can help me with that... I'd be glad to take a part. I'm just dunno how and what I can do for that... Maybe I can provide some help, but dunno which.

Thanks in advance.

[Edited by - Lolmen on October 29, 2007 6:11:20 PM]

Oliii, I have just spent the last three hours looking at threads that you've participated in, looking at your code snippets, etc.

You freaking rock.