Sana060101
asked on
Collision detection in d3d
How we detect collision in d3d. Do we detect it using untransformed vertices or transformed. How can we reach the transformed vertices if directx has performed the transformation. One way can be locking the vertex buffer do we always use that (for detecting collision and determining co-ordinate of rectangle that is to be redrawn). I have tried D3DXVec3Project function but that give strange results. Its one parameter is viewport. We do not always manually set a viewport as in directx 8 samples. Then how can we call that function.
ASKER
Cybermike3D
Thank you for such a detailed description. But what I want to know that do you detect collision on the original vertices of an object without appling the view and projection transformation?.
Thank you for such a detailed description. But what I want to know that do you detect collision on the original vertices of an object without appling the view and projection transformation?.
>>do you detect collision on the original vertices of an >>object without appling the view and projection >>transformation?
You can do it either before or after. I was in fact trying to come up with a solution to one of my simulations which had few objects but a vast universe of discourse. The way you can do collision detection here is to create 3 hash tables for each x, y, and z coordinate. Every coordinate of every object in the scene is hashed and the cell in the hash table corresponding to the result is incremented by one (all are initialized to 0 to begin with). After incrementing, you check if the value exceeds 1 (2 or more). If that is the case, then you know that atleast 2 objects are being rendered in close proximity to one another. Thats collision detection.
I haven't tried it yet, so let the more experienced developers place comments. Generally, there is always a trade of between fine granularity and space efficency of the hash table.
Zawar.
You can do it either before or after. I was in fact trying to come up with a solution to one of my simulations which had few objects but a vast universe of discourse. The way you can do collision detection here is to create 3 hash tables for each x, y, and z coordinate. Every coordinate of every object in the scene is hashed and the cell in the hash table corresponding to the result is incremented by one (all are initialized to 0 to begin with). After incrementing, you check if the value exceeds 1 (2 or more). If that is the case, then you know that atleast 2 objects are being rendered in close proximity to one another. Thats collision detection.
I haven't tried it yet, so let the more experienced developers place comments. Generally, there is always a trade of between fine granularity and space efficency of the hash table.
Zawar.
Collision detection is an interesting problem. Fortunately
there are several methods and techniques used in solving
it. I recently had to do something like this myself, so
I'll just explain how I handled it.
Untransformed vertices are vertices which are still in
model space. Therefore, they usually do not indicate the
position an object will be rendered to, in world space. As
such, they cannot be used to indicate a collision
detection with another object that is in world space. Not
by themselves anyway. Let me explain what I mean.
Assume you have a game which generates random randomly-
sized asteroids and throws them at your spaceship. If your
craft collides with the asteroid, Game Over.
So, basically you'll be performing collision detection in
your game loop, every frame. To perform collision
detection here, you could easily use bounding spheres,
using the coordinates of the centre of your ship VS the
coordinates of the centre of the nearest asteroid. These
coordinates would be in world space, so in this scanerio,
that's what you would use.
This solution is of course only suitable if you have the
coordinates of the centre of your objects in world space.
In this example, you would have them because during your
generation of the asteroids, you were randomly generating
their positions too. Use the numbers which indicated their
positions.
Just remember, only world space coordinates can indicate
where objects are in the world, and so, only they can be
used to detect collision. But, as you mentioned, you
cannot get the transformed vertices back (not easily
anyway), so, a possible way around this, is to create a
substitute coordinate set which you can use to track the
centre of every object without having to worry about the
transformed vertices.
Sometimes it isn't as easy as this though because
circumstances can vary greatly depending on the way your
game internals are setup.
there are several methods and techniques used in solving
it. I recently had to do something like this myself, so
I'll just explain how I handled it.
Untransformed vertices are vertices which are still in
model space. Therefore, they usually do not indicate the
position an object will be rendered to, in world space. As
such, they cannot be used to indicate a collision
detection with another object that is in world space. Not
by themselves anyway. Let me explain what I mean.
Assume you have a game which generates random randomly-
sized asteroids and throws them at your spaceship. If your
craft collides with the asteroid, Game Over.
So, basically you'll be performing collision detection in
your game loop, every frame. To perform collision
detection here, you could easily use bounding spheres,
using the coordinates of the centre of your ship VS the
coordinates of the centre of the nearest asteroid. These
coordinates would be in world space, so in this scanerio,
that's what you would use.
This solution is of course only suitable if you have the
coordinates of the centre of your objects in world space.
In this example, you would have them because during your
generation of the asteroids, you were randomly generating
their positions too. Use the numbers which indicated their
positions.
Just remember, only world space coordinates can indicate
where objects are in the world, and so, only they can be
used to detect collision. But, as you mentioned, you
cannot get the transformed vertices back (not easily
anyway), so, a possible way around this, is to create a
substitute coordinate set which you can use to track the
centre of every object without having to worry about the
transformed vertices.
Sometimes it isn't as easy as this though because
circumstances can vary greatly depending on the way your
game internals are setup.
Yea, there are so many variations on collision detection that the style used depends very much on the application. If it works in one app, doesn't mean its gonna work in another. Its all fine and well to use bounding boxes and bounding spheres, but cars and planes and people dont conform to those simple shapes.
Why oh why couldnt microsoft have included a simple command like 'TESTCOLLISION Mesh1, Mesh2, flag' And just set a flag if any of the lines joining 2 vertices on mesh one passed through any of the polygon faces of mesh 2. That would do it. I suppose then that would be making our life easier, and heaven forbid that MS should make our lives easy.
Why oh why couldnt microsoft have included a simple command like 'TESTCOLLISION Mesh1, Mesh2, flag' And just set a flag if any of the lines joining 2 vertices on mesh one passed through any of the polygon faces of mesh 2. That would do it. I suppose then that would be making our life easier, and heaven forbid that MS should make our lives easy.
If this Proposed Answer served you, please accept it to grade and close this. If more is needed, advise the experts here.
Thanks,
Moondancer
Community Support Moderator @ Experts Exchange
Thanks,
Moondancer
Community Support Moderator @ Experts Exchange
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Place a comment under that question and if any answers come up there, you too will be notified.
The way I see it however are that there are different approaches to the problem. These are the solutions I have tried ... with varied levels of success .... to achieve the best possible speed.
First, find the closest object to the object that you are testing for colision with. Then determine if it falls within a bounding box or bounding sphere of this object.
If it does, then use the intersect function to determine if a collison has taken place.
ie. Place the start of the ray at the centre of your source object (Your car) . Place the end of ray at the centre of your destination object (The tree). Test the ray intersect distance to the mesh of the car. Do the same test for the tree. If the intersecting triangle of the tree is closer to the centre of the car than the intersecting triangle of the car then a collision has occurred.
If the distance from the centre of the car to the intersecting traingle face of the car is less than the distance from the centre of the car to the intersecting face of the tree ... then no collision has occurred.
You can also use the meshtool function as demonstrated in the dolphin demo to extract specific vertices and manipulate them.
So for speed ... the structure of the code should be something like this :
(This is in Visual Basic)
Maximumdistance = 10000000000
tarx = posx(0)
tary = posy(0)
tarz = posz(0)
mesh_collided_with = 0
for loop = starting_mesh to ending_mesh
'bounding box'
if abs(posx(loop)-tarx)< 1 and abs(posy(loo)-tary) < 1 and abs(posz(loop) - posz) < 1 then meshcolidedwith = loop
next
'The above will tell you the number of a reference mesh whose centre that falls within a bounding box sized 1 to -1 from the centre of a target mesh along the x,y,z axis .
'bounding sphere'
distance1 = posx(loop) - tarx
distance2 = posy(loop) - tary
distance3 = posz(loop) - tarz
temp = sqr(distance1^2 + distance2^2)
dist = sqr(temp^2 + distance3^2)
if dist < maximumdistance then
maximumdistance = dist
closest_object_index = loop
if dist < 1 then
mesh_collided_with = loop
endif
endif
next
'will tell you the number of a mesh whose centre falls within a radius of 1 unit from the centre of the target mesh ... also, it will tell you the number of the closest object to your target object.
Then, you do the intersect test on the closest object.
if mesh_collided_with > 0 then
l = closest_object_index
0 = reference_object_index
raystart.X = posx(l)
raystart.Y = posy(l)
raystart.z = posz(l)
rayend.X = posx(0)
rayend.Y = posy(0)
rayend.z = posz(0)
'test the distance to the target
Call g_D3DX.Intersect(g_mesh(l)
closest_target_face = raydist
Call g_D3DX.Intersect(g_mesh(0)
closest_reference_face = raydist
if closest_target_face < closest_reference_face then
'Collision has ocurred'
endif
endif
Let me know if this helps .....
Personaly, I think there should be something better out there ... This is what i'm using at the moment ... it is fast, and works 99% of the time. I'm sure there is something somewhere that sets a flag if there is a mesh collision ... but I aint found it yet. But, to test for mesh collison on a vertex by vertex, line by line, face by face basis ... that is just much too slow ... and totaly out of the question ... even using the meshtool.
Regards
Cybermike3D