# Collision between particles (Planes) and Box

## Recommended Posts

Medo Mex    891

I'm trying to detect collision between planes (particles) and boxes (building bounding box) so I can prevent rain/snow particles from entering buildings.

Here is what I'm doing (not working though):

// q1, q2, q3, q4 = Particle plane verticesAABB aabb = GetBuildingBoundaryBox(); // *** The bounding box is calculated using D3DXComputeBoundingBox() ***
D3DXVECTOR3 boxPosition = GetBuildingPosition();
D3DXMATRIX matBox;
D3DXMatrixTranslation(&matBox, boxPosition.x, boxPosition.y, boxPosition.z);

D3DXVec3TransformCoord(&aabb.Min, &aabb.Min, &matBox);
D3DXVec3TransformCoord(&aabb.Max, &aabb.Max, &matBox);

Plane plane;
plane.normal = GetTriangleNormal(q1, q2, q3);
plane.offset = D3DXVec3Dot(&plane.normal, &q1);

if (TestBoxToPlaneCollision(plane, aabb))
{
// Collision detected
} else {
// Collision NOT detected
}


Is the above code valid? It's not working with me (It's detecting collision when there is no collision)

##### Share on other sites
ongamex92    3255

Collision is not the way to prevent snowflakes to enter the building! The reason is that the intersection detection will be extreamly slow!

The right way to do it is by using the Z-Depth test for the particles.

There are some cool workarounds:

1) Display the particles in only predefined shapes(like boxes). with that method you can control the particles. Pseudo code

CParticeEmiter snowEmiter(PARTICLE_SNOW, boundingBoxMin, boundingBoxMax); //boundingBoxMin & boundingBoxMax will defined there area where snowing is allowed

and later in your spawn method ....

void snowEmiter::spwanNewPartice()

{

const float newParticleXPox = lerp(boundingBoxMin.x, boundingBoxMax,y rndFloat(0.f, 1.f));//that line is a crap you've got the idea

.......
}

2) The second method is to move snowEmiter with the player. if the player enters a building then you will deatach the particle emitter and leave it in front of the building entrance.

There are a lot of different solutions but you've got the idea.

3) I need to make a picture for you

http://postimg.org/image/x4807pz0j/

Edited by imoogiBG

##### Share on other sites
Medo Mex    891
Collision is not the way to prevent snowflakes to enter the building! The reason is that the intersection detection will be extreamly slow!

Doubt it, I have many snow rains per particle (not only one rain drop per particle)

The right way to do it is by using the Z-Depth test for the particles.

Z-Depth test? I don't know what the depth has to do with preventing particles from entering buildings

2) That's a good idea, but what if the player entered from the door and then went to look from a window upstairs? The rain/snow particles would be still infront of the door and he can't see it infront of the window.

Another problem is that the player could look at the building entrance from outside and see rain inside the building!

##### Share on other sites

Ignoring the possibility of subtle math bugs you have a conceptual problem; you are treating the particle's as if they have infinite extent.  A plane equation extends forever so it's not enough to simply test an AABB against a particle's plane equation.  A particle is a polygon so there are bounds that must be considered.

While particles are usually rendered as 2d quads you rarely want to consider the topology of the rendered geometry while doing collision detection.  Particles are typically stored as points with a radius, to render them you orient a quad towards the camera.  This suggest that a particle's physical geometry is better represented with a sphere.  I would switch approaches and use a sphere to AABB collision routine, it will make your life easier.

Edited by nonoptimalrobot

##### Share on other sites
Medo Mex    891

@nonoptimalrobot: I have the plane vertices v1, v2, v3, v4

How do I calculate the plane radius so I can do AABB to sphere collision test?

##### Share on other sites

It should be noted that in the case of particles used for snow and rain this problem is solved differently in a number of commercial engines.  The elementary solution is to not spawn particles indoors, this works okay but requires meta data to be attached to level geometry (indoor / outdoor bounding boxes) and doesn't extent well to cases where precipitation occluders are smaller than the actual particles (which happens if you have dozens/hundreds of rain or snow elements per particle).

A more elegant albeit complex solution is to use a form of shadow mapping.  Precipitation particles are continuously generated in a volume that is moved around with the camera.  A depth map is generated to correspond to this volume using an orthographic projection where the look direction is parallel to the direction of the precipitation.  While rendering particles this depth map can be sampled and pixels with values that are occluded by the depth map are discarded.  This is a flexible solution where all types of occluding geometry are accounted for and the occlusion is done on a per pixel basis so the size of your precipitation particles relative to the size of the blocking geometry is largely irrelevant.

Edited by nonoptimalrobot

##### Share on other sites

@nonoptimalrobot: I have the plane vertices v1, v2, v3, v4

How do I calculate the plane radius so I can do AABB to sphere collision test?

Here's some extremely inefficient pseudo code:

void CalcBoundingSphere(const vector3& a_vVertexA,
const vector3& a_vVertexB,
const vector3& a_vVertexC,
const vector3& a_vVertexD,
vector3&       a_vCenter,
{
a_vCenter = (a_vVertexA + a_vVertexB + a_vVertexC + a_vVertexD) / 4;
}


...although you are going about this from the wrong direction.  Your particles should be stored CPU side as (position, radius) pairs and the quad vertices (v1, v2, v3, v4) should be generated from that prior to rendering.  I suggest you check these links out:  Math for Game Developers: Intro to Vectors, Math for Game Developers: Advanced Vectors

Edited by nonoptimalrobot

##### Share on other sites
ongamex92    3255

The right way to do it is by using the Z-Depth test for the particles.

Z-Depth test? I don't know what the depth has to do with preventing particles from entering buildings

Well the explanation really depends on your scene. In our game we are using simple depth test to discard some particle pixels. Note that that method depends on the rendering order(that's why it is scene dependable).

the only thing you need to know is 'is the player inside'

if the player is inside then:

Draw things that are outside (trees, birds stuff...)

turn off z-writing and change depth test to always succeed

draw the particles

turn z-depth buffer things back to normal

draw the building

and that is.

(in our game we have cars in tunnels ect);

##### Share on other sites
Medo Mex    891

@imoogiBG: I'm using soft particles, so I have to render the scene first and then the particles.

So how do I do that in soft particles? (Notice that I must render the particles AFTER the scene in soft particles)

@nonoptimalrobot: I'm already storing the particle size in the memory and then calculating the vertices prior rendering, but the size is not actually the radius.

Can someone point me to sphere/box collision detection sample? I have only implemented box/box collision detection.

Edited by Medo3337

##### Share on other sites
Medo Mex    891

@DonTzzy: This is 2D OOB/Circle collision detection

I'm looking for 3D AABB/Sphere collision detection sample.

##### Share on other sites
ongamex92    3255

http://www.realtimerendering.com/intersections.html

Im not quite shure why you need soft particles for rain/snow, maybe I cannot your art style. It seems like if you want to use Z-depth test to discard particles you must use additional depth buffer.

##### Share on other sites
Medo Mex    891

Currently, I would go for detecting collision between spheres (particles) and boxes (buildings)

Any idea how to detect collision between AABB and Sphere?

Edited by Medo3337

##### Share on other sites
Medo Mex    891

I have been trying to do it myself, I made AABB vs AABB, Sphere vs Sphere, but couldn't get AABB vs Sphere to work correctly.

So I'm looking for code sample.

@imoogiBG: I have multiple rain drops per particles, so it need soft particles or the particles plane would appear intersecting the terrain/ground.

Edited by Medo3337

##### Share on other sites
ongamex92    3255

http://stackoverflow.com/questions/4578967/cube-sphere-intersection-test

also if you want to figure it out yourself and write yourself a better solution use:

Canonical (im not really shure that is the right word in english) equation of a plane : Ax + By+ Cz + D = 0, and point projection on a plane.

Take a look at some linear algebra and analytic geometry articles you will certenly need them in the near future.

##### Share on other sites
Medo Mex    891

@imoogiBG: I got this solution when I used Google, unfortunately it doesn't work

Here is what I'm doing:

bool doesCubeIntersectSphere(D3DXVECTOR3 C1, D3DXVECTOR3 C2, D3DXVECTOR3 S, float R)
{
float dist_squared = R * R;

/* assume C1 and C2 are element-wise sorted, if not, do that now */

if (S.x < C1.x) dist_squared -= squared(S.x - C1.x);
else if (S.x > C2.x) dist_squared -= squared(S.x - C2.x);

if (S.y < C1.y) dist_squared -= squared(S.y - C1.y);
else if (S.y > C2.y) dist_squared -= squared(S.y - C2.y);

if (S.z < C1.z) dist_squared -= squared(S.z - C1.z);
else if (S.z > C2.z) dist_squared -= squared(S.z - C2.z);

return dist_squared > 0;
}

bool TestBoxToSphereCollision(AABB box, D3DXMATRIX boxWorldMatrix, Sphere sphere, D3DXVECTOR3 spherePosition)
{
// We have min and max values, use these to get the 8 corners of the bounding box
D3DXVECTOR3 cornersInModelSpace[8];
cornersInModelSpace[0] = D3DXVECTOR3( box.Min.x, box.Min.y, box.Min.z ); // xyz
cornersInModelSpace[1] = D3DXVECTOR3( box.Max.x, box.Max.y, box.Max.z ); // Xyz
cornersInModelSpace[2] = D3DXVECTOR3( box.Min.x, box.Min.y, box.Min.z ); // xYz
cornersInModelSpace[3] = D3DXVECTOR3( box.Max.x, box.Max.y, box.Max.z ); // XYz
cornersInModelSpace[4] = D3DXVECTOR3( box.Min.x, box.Min.y, box.Min.z ); // xyZ
cornersInModelSpace[5] = D3DXVECTOR3( box.Max.x, box.Max.y, box.Max.z ); // XyZ
cornersInModelSpace[6] = D3DXVECTOR3( box.Min.x, box.Min.y, box.Min.z ); // xYZ
cornersInModelSpace[7] = D3DXVECTOR3( box.Max.x, box.Max.y, box.Max.z ); // XYZ

// Now we transform each corner by the world matrix
D3DXVECTOR3 cornersInWorldSpace[8];
for( int i = 0; i < 8; i++ )
D3DXVec3TransformCoord( &cornersInWorldSpace[i], &cornersInModelSpace[i], &boxWorldMatrix );

D3DXVECTOR3 minBoundsWorldSpace = cornersInWorldSpace[0];
D3DXVECTOR3 maxBoundsWorldSpace = cornersInWorldSpace[0];
for (int i=1;i<8;i++)
{
minBoundsWorldSpace.x = min(minBoundsWorldSpace.x, cornersInWorldSpace[i].x);
minBoundsWorldSpace.y = min(minBoundsWorldSpace.y, cornersInWorldSpace[i].y);
minBoundsWorldSpace.z = min(minBoundsWorldSpace.z, cornersInWorldSpace[i].z);

maxBoundsWorldSpace.x = max(maxBoundsWorldSpace.x, cornersInModelSpace[i].x);
maxBoundsWorldSpace.y = max(maxBoundsWorldSpace.y, cornersInModelSpace[i].y);
maxBoundsWorldSpace.z = max(maxBoundsWorldSpace.z, cornersInModelSpace[i].z);
}

}

Let me know what's wrong in the code above.

##### Share on other sites
ongamex92    3255

your algorithm is wrong here, those lines are exactly the same:

cornersInModelSpace[5] = D3DXVECTOR3( box.Max.x, box.Max.y, box.Max.z ); // XyZ

cornersInModelSpace[7] = D3DXVECTOR3( box.Max.x, box.Max.y, box.Max.z ); // XYZ

cornersInModelSpace[3] = D3DXVECTOR3( box.Max.x, box.Max.y, box.Max.z ); // XYz

cornersInModelSpace[1] = D3DXVECTOR3( box.Max.x, box.Max.y, box.Max.z ); // Xyz

and also :

cornersInModelSpace[0] = D3DXVECTOR3( box.Min.x, box.Min.y, box.Min.z );

cornersInModelSpace[2] = D3DXVECTOR3( box.Min.x, box.Min.y, box.Min.z );

cornersInModelSpace[4] = D3DXVECTOR3( box.Min.x, box.Min.y, box.Min.z );

cornersInModelSpace[6] = D3DXVECTOR3( box.Min.x, box.Min.y, box.Min.z );

Im not going to teach you how to code, but i really think that I must say those things to you: I see that you have great passion but your C++ is not quite good.

See D3DXVECTOR3, D3DXMATRIX, AABB ... those structures are really big(in bytes) and in

bool TestBoxToSphereCollision(AABB box, D3DXMATRIX boxWorldMatrix, Sphere sphere, D3DXVECTOR3 spherePosition)

you're passign them by value. The same syntax is absolutely OK with C#/Java/ect languages, but in C++ this is a different thing. Use references and/or pointers. Try something like this:

bool TestBoxToSphereCollision(AABB& box, D3DXMATRIX& boxWorldMatrix, Sphere& sphere, D3DXVECTOR3& spherePosition)

also you're missign CONSTs A-LOT. const are something like the greatest hit for the compiler. If you use const your code will be faster I promise! Also const methods/functions will help you with debugging and fixing mistakes in code semantics. so your fuction declaration will probably look something like this:

bool TestBoxToSphereCollision(const AABB& box, const D3DXMATRIX& boxWorldMatrix, const Sphere& sphere, const D3DXVECTOR3& spherePosition)

Excuse me if you're already familiar with those things.

Edited by imoogiBG

##### Share on other sites
Medo Mex    891

@imoogiBG: I just copied and pasted the code from a very old project that I made when I started in C++.

I was trying to get it work then I can rewrite the code, trust me this is not the final code for usage purposes. I figured out I had a problem with calculating the bounding box min and max.

I got it to work! the only problem now is that I don't see rain in the area around the building, while the rain should appear around it.