#50815 - omaremad - Sat Aug 13, 2005 1:07 pm
Hello, i have ported some directx collision code to nds opengl. it returns true if a point(position of the camera) intersects a triangle; using this method i am making a maze game called maze of doom which will incorporate metroid like controls but no strafe to make it hard for the player to avoid walls. So the aim of the game is to escape the maze without touching the walls. Feel free to use the code but before any one does please make sure i ported it correctly (there is a problem with fabs since it not in the ds math lib). So please help me completely port this code(see directx code below as well).
thank you
(for interesting stuff read from the bool part the first bit is just making acos since it not in the ndslib)
//a,b,c are vertices of a triangle being scanned
nintendo ds arm9 version
| Code: |
#define PI 3.14159265358979323846
#define HALF_PI 1.5707963267948966192313216916398;
static const float ACOS_C0 = HALF_PI;
static const float ACOS_C1 = -0.213300989f;
static const float ACOS_C2 = 0.077980478f;
static const float ACOS_C3 = -0.02164095f;
float rr_poly_acos( float x )
{
//Worst-case error ~= 0.002 degrees
//Function is exact at -1, 0 and 1
if( x >= 0.0f )
{
const float sx = SQRT( 1.0f - x );
const float px = ACOS_C0 + x*(ACOS_C1 + x*(ACOS_C2 + x*ACOS_C3));
ASSERT( SANE(sx) );
return( sx * px );
}
else
{
const float sx = SQRT( 1.0f + x );
const float px = ACOS_C0 - x*(ACOS_C1 - x*(ACOS_C2 - x*ACOS_C3));
ASSERT( SANE(sx) );
return( PI - (sx * px) );
}
}
#define ACOS(x) rr_poly_acos(x)
#define ASIN(x) (HALF_PI - ACOS(x))
BOOL CheckPointInTriangle(vector* point ,vector* a, vector* b, vector* c) {
double total_angles = 0.0f;
// make the 3 vectors
vector* v1 = point-a;
vector* v2 = point-b;
vector* v3 = point-c;
//convert v1 to a f32 array to be accepted into normalisation and dot funcs.
f32 v1f[2];
v1f[0]=v1.x;
v1f[1]=v1.y;
v1f[2]=v1.z;
//convert v2 to a f32 array to be accepted into normalisation and dot funcs.
f32 v1f[2];
v2f[0]=v2.x;
v2f[1]=v2.y;
v2f[2]=v2.z;
//convert v3 to a f32 array to be accepted into normalisation and dot funcs.
f32 v1f[2];
v3f[0]=v3.x;
v3f[1]=v3.y;
v3f[2]=v3.z;
normalizef32(v1f);
normalizef32(v2f);
normalizef32(v3f);
total_angles += ACOS(dot(v1f,v2f));
total_angles += ACOS(dot(v2f,v3f));
total_angles += ACOS(dot(v3f,v1f));
// allow a small margin because of the limited precision of
// floating point math.
if (fabs(total_angles-2*PI) <= 0.005)//there is no fabs in the ds lib math(what should i do?)
return (TRUE);
return(FALSE);
}
|
pc direct x version
| Code: |
BOOL CheckPointInTriangle(D3DVECTOR point ,D3DVECTOR a, D3DVECTOR b, D3DVECTOR c) {
double total_angles = 0.0f;
// make the 3 vectors
D3DVECTOR v1 = point-a;
D3DVECTOR v2 = point-b;
D3DVECTOR v3 = point-c;
normalizeVector(v1);
normalizeVector(v2);
normalizeVector(v3);
total_angles += acos(dot(v1,v2));
total_angles += acos(dot(v2,v3));
total_angles += acos(dot(v3,v1));
// allow a small margin because of the limited precision of
// floating point math.
if (fabs(total_angles-2*PI) <= 0.005)
return (TRUE);
return(FALSE);
}
|
#50822 - ecurtz - Sat Aug 13, 2005 4:56 pm
You really shouldn't be taking all those arc cosines, there is a much better test based on matrix algebra. Even if that sounds scary it is really a very simple idea.
See http://mcraefamily.com/MathHelp/GeometryPointAndTriangle2.htm for a decent description or google something like "matrix point in triangle determinant"
#50829 - omaremad - Sat Aug 13, 2005 5:59 pm
Thanks exurtz
that way is easier but i am trying to calculate things in a 3d space rater than on a 2d plane.
im not sure what my one does but im sure it checks collision on a 3d space.
now is there a workaround the missing fabs function?
I am sure the ds isnt that weak.
#50832 - omaremad - Sat Aug 13, 2005 6:23 pm
Ahh i just realised that there is a major flaw inn the code snippet. What if the camera moves by 1 unit every time and thus never actually hit the triangle and just passes through it?
has any one done collision detection for opengl or ds? The Nehe tutorial checks against predefined shape , while i want detection againts an array of trinagles loaded from a file.
if we cooperate and manage to do this we can all start making 3d games not 3d demos ;).
#50837 - octopusfluff - Sat Aug 13, 2005 7:32 pm
| omaremad wrote: |
Thanks exurtz
that way is easier but i am trying to calculate things in a 3d space rater than on a 2d plane.
|
It's just adding another axis. That algorithm is fairly trivial to extend.
#50882 - omaremad - Sun Aug 14, 2005 6:09 am
i found this really good collision detection library (the simplest ever)
it accepts triangles simlar to those of the open gl and has only one system dependent function the time function.
i am going to stufy the source and see if it is portable or not
If you are interested please help.
Here it is: http://www.photoneffect.com/coldet/
#50988 - Ethos - Mon Aug 15, 2005 3:20 am
Hmmm...I've heard there is hardware collision detection
So this might be a waste of time.
_________________
Ethos' Homepage (Demos/NDS 3D Tutorial)
#50992 - tepples - Mon Aug 15, 2005 5:50 am
Hardware collision detection is not present in any Nintendo game system that I know about.
What real games do involves considering each pair of sprites and testing their bounding rectangles or circles for overlap. Search the forum for "collision".
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#55618 - DeaneGainey - Fri Sep 30, 2005 1:24 am
Full phasic collision detection in a 3d environ:
1. "Bounding sphere" check.
Centred on the median of the width, length, and height of each object, with a radius or the longest edge, the bounding sphere is a hard rule. The checks are from largest bounding spheres against smaller. If two bounding spheres do not overlap, there is no way for the 2 objects to be hitting and a more complex test can be skipped.
Then the friend triangle test, to see if 2 triangles are inside one another.
And depending, maybe an intermediary test.
_________________
--- Posts say it all, nothing to see here ---
#55629 - sajiimori - Fri Sep 30, 2005 3:43 am
Most real games don't test polys versus polys, especially not on a 66MHz system.
#56154 - oxymen - Thu Oct 06, 2005 7:57 pm
The best way in may cases is to just test collision with a simple sircle which is barely surrounding the object. this way you will have no issues with movement, because often if every pixel in fairly complex shapes is checked, the object will in many cases end up stuck with other objects. this is a method which is commonly used in many commersial games, and it is often very hard to notice that it is not pixel-correct check
#56786 - omaremad - Tue Oct 11, 2005 4:07 pm
I have some good news!
I constructed a small 3d engine for the nds its has sevral classes for loading maps and adding a camera and lights and models in an easy way.
It make rotations easy and does all the matrix stuff for you.
It also generate textures automatically.
And It has collison detection!!!!!!!!!(sphere to triangle mesh)
But i have a question before i release it.
I am using floating points for my math so it runs fast on the ds but do i have to operate on the floating points like this to take advantage of the ds's hardware.
or can i just do this and it would still run fast and accurately
#56799 - omaremad - Tue Oct 11, 2005 5:39 pm
just found the answer thanks.
I will get working.
btw any one good at python here? i need help writting a blender blugin.
#58119 - SevenString - Fri Oct 21, 2005 12:40 am
For character collisions, one trick i've used in the distant past is to tag particular vertices of a meshed character as spherical "colliders" with a unique radius. For instance, the torso has a sphere, the head has a smaller sphere, the legs and arms even smaller, and finally the hands and feet.
For a more advanced implementation, in the 3D animation package, you could create tagged (named) collision spheres that animate with the geometry or skeleton, but only get exported along with the original character mesh data as a series of sphere locations and radii.
So as the character moves and animates, the attached spheres move along with the character parts. What you get is an internal virtual representation of the character that looks like the "Michellin Man".
[Images not permitted - Click here to view it]
But for each game tick, you can do collision of this set of spheres with other objects or the environment, yet that collision comes across to the player as detailed because it is more than just a single sphere representing the whole character.
And if you do your collision comparisons using the square of the radius, the cost of using multiple spheres is pretty negligible, even on a handheld.[/img]
_________________
"Artificial Intelligence is no match for natural stupidity."
#61900 - Cupcakus - Thu Nov 24, 2005 7:28 pm
You are really overcomplicating collision quite a bit...
Assuming your character is a ball? And the maze consists of flat walls, you have very simple sphere vs. oriented bounding box collision.
Even if your character is not a ball, you can still give it a sphere and have very decent collision vs. walls.
If your walls are curved enough that bounding boxes are impractical, you're probably using too many poly's for a DS anyway :-)
I can't think of any reason to have poly v. poly collision in a DS game.
#62062 - sajiimori - Sun Nov 27, 2005 1:04 am
Cupcakus, you must think Mario 64 is overcomplicated because it doesn't use axis-aligned walls and floors. Also, colliding a sphere versus a set of boxes is linear time. Faster methods are often needed for real life as levels grow beyond arena-size.
#83881 - blaow - Fri May 19, 2006 6:45 am
following this topic, In an example im working on I have bounding box collisions working on all objects and was thinking of applying further triangle to triangle collision check only to those objects that actually collide. Is there a more efficient way not mentioned here to check collisions in a deeper level once the bounding boxes collide, something less processor consumming?
Thanks
_________________
blaow~~
#83948 - sajiimori - Fri May 19, 2006 9:34 pm
Continue to subdivide the model into smaller parts, like boxes or spheres.
If at least one of the shapes does not animate, a BSP tree might be a good way to represent its collision shape.
#84610 - blaow - Tue May 23, 2006 6:18 pm
Not focussing on collisions but more on the Orientation,
Should these deeper-level bounding boxes/spheres be actual models (drawn in 3d prog, not calculated) that i map to the target model areas, so that when the target model rotates or is scaled, i can have a procedure that rotates/scales all bounding objects asigned to that model in the same manner (just using opengl calls since they are models as well).
Right now what i have is a bounding box mechanism based on a structure (not drawn in 3d prog) that stores the min and max height&width&depth of each model, and i use that to check collisions of any 2 models. I am doubting however if this approach can be as scalable and as easy to make it "Oriented bounding box" based as it doesnt use opengl calls to rotate, scale etc..
any suggestions would be great
forgive my noobness to 3D :)
thanks
_________________
blaow~~
#84619 - sajiimori - Tue May 23, 2006 7:13 pm
When you say "actual models," I'm assuming you mean triangle meshes. They are not usually a good bounding volume to use because they are expensive to collide against. Bounding volume tests should be inexpensive. Boxes and spheres are cheaper than triangle meshes, both in terms of CPU and memory usage.
But we're getting ahead of ourselves. Bounding volume hierarchies are an optimization, and optimizations should only be done after you have the functionality working (that is, per-poly collision). Get that working, then we'll talk about optimizing it.
#84820 - tepples - Wed May 24, 2006 10:18 pm
| sajiimori wrote: |
| Bounding volume hierarchies are an optimization, and optimizations should only be done after you have the functionality working (that is, per-poly collision). |
That's like saying "hitboxes in a 2D sprite based fighting game are an optimization, and optimizations should only be done after you have the functionality working (that is, per-pixel collision)." But does any major 2D fighting game use anything but hitboxes?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#84847 - sajiimori - Thu May 25, 2006 12:13 am
It's not analogous. His goal was to do accurate collision. I know you often suggest to people that they avoid doing things that are probably unnecessary from a gameplay standpoint, but I tend to just answer questions. The fact of the matter is that hardly any hobbyist work gets published, so doing something that's probably overkill can nevertheless be a good way to learn new skills.
#84918 - blaow - Thu May 25, 2006 6:44 pm
| Quote: |
| When you say "actual models," I'm assuming you mean triangle meshes. |
Yes.
| Quote: |
| Boxes and spheres are cheaper than triangle meshes |
By that you mean spheres and boxes that are calculated( based on a given vertex and radius/box dimension) and that are not actually drawn on top of the 3dmodel as "invisible" triangle meshes?
what i was thinking was to draw these collision zones(spheres, boxes) as meshes that lay on top of the model but that are not visible to the user. I could do simple sphere, bounding box collision tests with any of these areas (by using their dimensions/radii only) if and only if the "Main bounding box" that sorrounds the whole visible model has collided. keeping the collision check at 2 levels only.
Since they are meshes, i could then use opengl calls
to rotate and scale these collision zones in the same direction/proportion as the visible model. (if i follow this approach i will forget about poly vs poly collisions, since in my oppinion it should be accurate enough but probably more memory consumming since extra meshes are drawn for collision purposes).
I just cant see a way to pick point special areas of an existing model, and calculate the size, orientation of collision areas during runtime without previuos mapping of these zones.
Thats more less whats troubeling me at the moment.
Cheers
_________________
blaow~~
#84921 - sajiimori - Thu May 25, 2006 7:08 pm
By boxes and spheres, I do not mean triangle meshes of boxes and spheres.
By a sphere, I mean a center point and a radius.
By a box, I mean a center point and the extent on each axis. If the box is rotated, add a vector for the 3 local axes.
(Spheres are easier to work with.)
Storing basic collision primitives as triangle meshes is weird and extremely inefficient, but whatever works for you. I recommend that you do not design your collision code around OpenGL because OpenGL is a graphics library.
Generating bounding volume hierarchies at runtime is a very advanced topic. Start with hand-made hierarchies.
#85058 - blaow - Fri May 26, 2006 9:06 pm
^^ Thanks, now i have a point of direction more less, i will read up on ways to "tag" collision primitives to the 3d-model desired zones without using triangle meshes.
_________________
blaow~~
![[Images not permitted - Click here to view it]](http://www.annotatedmst.com/episodes/eyecreatures/michman.gif){kind=link}