3D collision detection

I'm programming a 3D game and I have made ??libraries for display models from ".obj" files and functions to handle the movement of each body section.
I solved the problem of composition of movements of different body parts and I
including a stage on which the characters are moved.
Now I have encountered the problem of collision detection. I've heard of the bounding
boxes, but that means almost re-draw the model manually without the aid of GX.
Does anyone have any idea how to approach this issue?

how complicated are your models? If your models are simple then you can use a set of coordinates (usually a cube around the models position) to check if a collision or over lap has occurred between objects in the scene.

e.g. if x1 > x2 and x1< (x2 + width) then collision=true;
do this for all axis.

A cube is not exact enough. My scenario have different objects as houses, stones and so not aligned with coordinates axis.
I'm starting to develop automatic bounding boxes starting from the model.
The idea is to divide the space in boxes and set each box solid or not depending on contains a part of the model. Is like to draw the model in low resolution.
The only problem, is necesary to write functions to draw filled triangles in this discrete space and is necesary a big amount of memory to represent the bounding boxes. By other hand is extremely fast to check the collisions.
I'm writing the drawing lines and filled triangles based on DDA algoritm.
I would appreciate a more easy alternative but I don't now if it is possible.

depending on how flexible your code is you would use the big cube test first, then afterwards you would do a detail check for collisions in the model. You really do not need allot of memory to do these simple checks. try it on a simple model first before trying to work on larger models.

I am currently working on a similar problem with my game [wiibrew.org]



Edited 1 time(s). Last edit at 06/27/2011 12:56AM by owen.

Seems nice your new game!!

That you say is the idea for my first aproximation, but for the next I think I'll need a boolean grid in the space where is located the object.
How do you calculate the collision with non aligned objects? Perhaps you align first the objects and then you rotate them?

You can see a video of my game some time ago:
[www.youtube.com]

From the moment I recorded this video I have added a house, some palms and I programed different points of views for the player (first person, third person, view....) and now I am trying to solve the collision detection in every case. Palms are easy because is only necessary to check them as a cilynder, but the walls of the house are more complex because are not a box.For instance I can contact a wall with 30º, or jump to the ceiling.

I''ll upload some images and a new video of my game soon.



Edited 2 time(s). Last edit at 06/27/2011 08:39AM by wilco2009.

Currently I loop through all the faces of the object and check for collision , so it does not matter if the object is non-aligned.

Well you can try using the Bullet physics engine ( [en.wikipedia.org] ). or Any of the other free ones available; [forum.wiibrew.org]

Seems nice...
I'll check the source code.
But my objects have 2000 or 3000 vertex and near to 1000 faces each one, could be Wii fast enough using this method?

No, I doubt the Wii could handle that many. You need to do tests to see how much stuff you can put on the screen before it starts to drop frames, The sooner you test the limits the better you are in the end. They do not have to be complicated, just draw a bunch of models on the screen. You will quickly see.

Also its good to have a frame rate counter. Look in this; [www.google.com]

This morning I got a model with 700 faces and my game froze. My game is not the best optimized and I am is drawing directly to the screen but the wii is fast if you keep things simple. Though the wii is NOT super fast. I have to use tricks to limit the amount of points I check, I divide up my game space so that I only do collision checking on things that are near the player or bullet. I also have something like a [en.wikipedia.org] for determining which objects are close to each other.

There are an additional difficulty. That is we are doing nested transformations to simulate the movements.
Ok, for the characters is not necesary to take in acount every joint transformation but only is necesary to treat it as a cylinder aplying main translation, rotation and scalation.
The problem appears when we try to do an automated procedure to search the limits, because each subelement of a group applies its own transformations over the parent group transformations, and it is recursive in my program. Model can have many levels of depth each one with its own transformation primitives.
I'm programming a function to found the real borders through the application of all nested transformation using matix operations.

There are an additional difficulty. That is we are doing nested transformations to simulate the movements.
Ok, for the characters is not necesary to take in acount every joint transformation but only is necesary to treat it as a cylinder aplying main translation, rotation and scalation.
The problem appears when we try to do an automated procedure to search the limits, because each subelement of a group applies its own transformations over the parent group transformations, and it is recursive in my program. Model can have many levels of depth each one with its own transformation primitives.
I'm programming a function to found the real borders through the application of all nested transformation using matix operations.

well good luck, I'm clueless when it comes to transformations and matrix.

Not visited the code forum for a while...

I find sphere testing very efficient (the Wii loves floats), here a snip of my code as an example.
Change it to pass in guVector* and also include z as part of the equation.

It's good for a first step test when you need to find out if it's it in or out the field of view.

// note: The radius param takes a squared value so saves using sqrt
bool Vessel::InsideRadius(float center_x, float center_y, float radius)
{
float square_dist = ((GetX()-center_x)*(GetX()-center_x) ) + ((GetY()-center_y)*(GetY()-center_y)) ;
return ( fabs(square_dist) < (radius) );
}

@titmouse what about the radios of the current vessel? do you check that?

No I just check if two points are within a given radius.
I just increase the radius to take account of both vessels, no need for anything more complex - keep it simple.

As you know its C++ so both of the vessels points are known.

Here’s some example calling code, 60*60 is to get rid of the need for sqrt.
(I just love C++ containers, dam fast and I not had _ANY_ bugs let alone crash bugs in my bolt thrower code, powerful stuff... leave the dark side Owen)

for (std::vector::iterator Iter(m_SporesContainer->begin()); Iter!= m_SporesContainer->end(); ++Iter )
{
if (pPlayerVessel->InsideRadius(iter->GetX(), iter->GetY(),60*60))
{ ... }
...
}

Reply Quote

@Titmouse: Thankyou Titmouse. I know this is the best way to detect collision between spheres, just you have a bug. The function parameter have not to be the radius, but the radius square. The method is perfect because is not necessary to calculate the square root, just pass radius*radius.

This method is useful to calculate simple collision, but is not precise enough to complex models, like humans, or something like that. My Idea combine this type of simple calculation with the calculation of multiple spheres around all the model. Is like to make the same model but with low resolution.



Edited 1 time(s). Last edit at 07/10/2011 05:09PM by wilco2009.

I'm keeping stuff as simple as possible if that is the dark side then so be it.

Here is how I do collision check for 2 boxes in 3d, since I'm only dealing with the collision boxs. the fx, fy and fz variables correspond to the scale value of each boxe. (if there is a faster way to do this check then let me know).

bool check_diff(int n1, int n2, int fat) {
	return ( ( (n2>n1) & (n2-fatn1) ) );
}

bool check_collision( int x1, int y1, int z1, int x2, int y2, int z2, 
						int fx1, int fy1, int fz1, int fx2, int fy2, int fz2 ) {
	
	//do_draw_box( x2,y2,z2, 0, 0xCAA95F44, fx2, fy2, fz2 ); //show x2 bounding box
	//do_draw_box( x1,y1,z1, 0, 0xCAA95F44, fx1, fy1, fz1 ); //show x1 bounding box		
	
	return ( (
			check_diff(x1, x2, fx1) & check_diff(y1, y2, fy1) & check_diff(z1, z2, fz1) //check 1st
		 ) | (
			check_diff(x2, x1, fx2) & check_diff(y2, y1, fy2) & check_diff(z2, z1, fz2) //check 2nd		 
		 )	);
	
}

Edited 1 time(s). Last edit at 07/10/2011 10:00PM by owen.

Sorry Owen – that was a bad joke about you using plain C, I would never have a dig at anyone’s coding skills.
Apologies for poking fun at you; dire attempt at trying to get you to move over to C++

wilco2009 - yes it's a very basic check
That’s way I did said: "It's good for a first step test when you need to find out if it's in or out the field of view."

Low detail models derived from the working model sounds a good way to go – that way you can dial it up or down depending on the viewing distance using whatever checking method you believe will work best.

Quote
Titmouse
Sorry Owen – that was a bad joke about you using plain C, I would never have a dig at anyone’s coding skills.
Apologies for poking fun at you; dire attempt at trying to get you to move over to C++

No offence taken. The only problem C++ solves for me is dealing with strings. Aside from that I have bigger problems like shadow mapping.

Owen can you post that bit of code again, think I can help out performance wise.
but the check_diff routine, looks like it has a typo.