15 replies to this topic

[Nyad]

What do you think of this idea for testing for collisions?
It uses a Z-buffer idea.

We want to test between two objects.
so we take the direction vector with which object1 is moving. and we construct a matrix which will transform all the points as though the object was 2D and being looked at from this same direction vector. ie as if a viewer is standing right infront of it. we do similar calcs like in software rendering to make a z-buffer. then we stop. Note the width and height of the z-buffer will be mapped to the max size of the largest object, so it does not correspond in any way to the viewport.
Now for the second object. we transform it using a matrix constructed from the same direction vector as object1, the matrix will be different since these two objects are in different positions. we also construct a z-buffer for this object
and we test the two z-buffers to see at which "x and y pixel" they collide.
we can use these x-y pairs to work backwards and find the exact world collision point.

Sound good?

[z80]

Sounds like a good way to waste both CPU and RAM at the same time ;-) Also it would only work for convex objects. Testing links in a chain this way for example would go terribly wrong.

[.oisyn]

What if the objects have features that are smaller than a single z-buffer element (a "zbufel"? :happy:), such as pointy spikes? This of course aside from the fact that it is very computationally expensive, as z80 already pointed out.

I'll stick to a simple yet very accurate separating axis test for convex polyhedra, or GJK for general convex objects .

[Nyad]

.oisyn said:

I'll stick to a simple yet very accurate separating axis test for convex polyhedra, or GJK for general convex objects :).

Is this method faster than using plane-plane collision detection?
if so could you point me to some documentation please :)

[Kenneth Gorking]

There are heaps of info about the separating axis test on the net, it isn't hard to find

[SmokingRope]

I wonder if all of the transformations and zbuffer rendering would reduce to the intersection tests that are published elsewhere on the net.

[Mattias Gustavsson]

Nyad, why don't you try your idea and let us know if it's any good? Best way to find out...

[rouncer]

Heres what I gather->
I make a basis that includes both the models in the direction object one is
going, with an orthogonal projection - draw model a in red, model b in green.
draw model b in cw mode then if there is any red in the render, then they
collide?
if thats true i dont see how it would go slow, because its a pretty small
pixel shader and it could go fast...

[Reedbeta]

rouncer: it would have to be a little more complicated than that. Think of model A being a big sphere and model B being a little sphere. Then even if they don't collide you will see red in the render because model B is not big enough to cover up model A. So you would have to look only at the pixels that were drawn when rendering model B and see if any were depth-failed.

[rouncer]

Hey you are dead right.

what you draw them translucently - and only if red and green are filled they
both filled that pixel?

[rouncer]

Do the first render as big as you want detail. then when rendering the next model, put
the first render in as a texture in the shader, make the render target 1 pixel,
and check every pixel to every pixel, as soon as you get a depth fail, write 1,1,1,1 to the output pixel.
if its a pass write 0,0,0,0. (nothing)
then grab the 1 pixel from the video card into the system memory(its only 1
pixel, so it should go fast), lock and read.

and you got it. per pixel collision detection. what an awesome idea if you do want to go to that detail.

but if you use the zbuffer or stencil buffer, maybe you avoid crossing the bus.

[Nyad]

well we don't really need colours at all, we could just use 0 for nothing, 1 for object1 and 2 for object2 and 3 for a collision. and we have a z-value so its 5bytes per pixel in the z-buffer.

Now think of there being a plane infront of object1 which is the 'location' of our Z-buffer. This will be on the closest pixel of object1.

To do the test we fill our z-buffer with 1's where object1 comes into play.
Then whenever object2 has a pixel that is further away than object1, ie it doesn't overwrite the z-buffer, we mark that pixel as 3. (meaning a collision)

The only problem comes in with penetration depth. since 2 or more pixels of object2 could intersect in the same block as each other in the z-buffer. so we might have to store another array/buffer which holds the minimum z-value whilst our original z-buffer holds the max z-value of our collision.

The major problem that arises is, I may be able to calculate the exact collision point, but then I still have to search for which polygons intersect :(

Does this method have any practical applications or is it just way too slow?
remember that pre sphere-sphere tests help with obvious elimination, but the algorithm is slower for larger objects

[rouncer]

You could do it any way you wanted.

[Mattias Gustavsson]

Nyad said:

Does this method have any practical applications or is it just way too slow?

Try it, then tell us :yes:

[Nyad]

Mattius it is too slow.
I tried writing just the part of modifying a buffer of size 1024*768 200times and
it was hitting 230milliseconds to do. which is far too slow if I want to reach anything near 60fps

PS: this was in asm but without mmx/sse123. but if it needs those instructions already at that stage then its too slow to begin with

[rouncer]

Its like rendering a shadowmap.