• Advertisement

Archived

This topic is now archived and is closed to further replies.

Point - which side of a plane

This topic is 5062 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hi all. I am following tutorial on gamasutra's site : http://www.gamasutra.com/features/20000203/lander_02.htm which is about 3D convex2convex hull intersection using the separating axes method. Basically the idea is to search through my first convex hull C1 for a poly (plane) that will have all of the vertices from the second C2 convex hull on its positive side. My problem is that it works ok for 2 cubes but when I have say two spheres it doesnt work. I think I know where the problem is. At the moment I implemented as the author of that article says.
quote:
For example, I create a vector between points A and B in Figure 6 and call it Vector AB. Then I take the dot product of that vector and the face normal, N • Vector AB. If this value is positive, vertex A is not colliding with the object. If all the vertices in the colliding object are on the far side of the separating plane, then I definitely don’t have a collision, and I’m done.
The author says that if the value is positive vertex A is not colliding. But I get values positive when the normal vector is positive (plane facing upwards (top face of a cube). But I am not sure what to do when the normal is facing downwards the the value is not positive anymore which confuses my test. What sghould I do? Heres my implementation:
// See if each vertex in target polygon is on positive side of a plane (source polygon)

	for( int i=0; i<target.CountVertex; ++i)
	{	// if any vertex below plane found.. failed

		float a = N.DotProd(target.VList[i]-source.VList[0]);
		if( a <= 0) 
		{
			return false; // found at least one vertex under the plane 

		}
	}  
return true;  // all vertices lie on positive side (this polygon doesnt collide.

[edited by - robert_s on April 14, 2004 7:06:21 AM]

Share this post


Link to post
Share on other sites
Advertisement
if N is a normal of convex A, and a a point on that face. If b is a point of convex B.


bool FrontFacing(const CConvex& ConvexA, const CConvex& Convex B)
{
for(int i = 0; i < ConvexA.GetNumFaces(); i ++)
{
Vector a = ConvexA.GetFace(i).GetVertex(0);
Vector n = ConvexA.GetFace(i).GetNormal();

for(int j = 0; j < ConvexB.GetNumVertices(); j ++)
{
Vector b = ConvexB.GetVertex(j);
Vector ab = b - a;

if (ab.Dot(n) > 0.0f)
return false;
}
}
return true;
}


and then you do


if (FrontFacing(A, B) || FrontFacing(B, A))
return false;

// test edge edge collisions

//...

//...

//...



it''s not very fast, nor efficient, and will give you false positives unless you also tests the planes defined by the cross products of edges, but it''s a start. This can be bad for very sharp convex hulls. A GJK algo would be certainly much better.

Share this post


Link to post
Share on other sites
Thanks Olii. Sorry I've made a mistake when subtracting two vectors which one contained some garbage data thats why it didnt work

Last question related to the algo decribed on
gamasutra site
On page one the author says how to find the separating poly. But as I found in some cases we may not be able to find the separating poly which means that the algo will indicate intersection even though there is no intersection. (eg. two pyramids. 4 planes each) So on page two "Balancing on a Polygon Edge" the author describes (please correct me if I'm wrong) how to avoid this problem by adding some extra checks for edges. But the question is. Should I first scan for separating poly (as described on page one) then if not found proceed to the next scan using an edge and a point to form a plane checking again if all vertices are above this newly created plane? But should I perform this test again with each edge in convex hull 1 against each point in convex 2? or there is some shortcut? Please let me know. Thanks!

Hm... GJK I've never tried to implement it. Would it be the most appropriate algo for convex hull intersection? or there are even better ways?

Are there any good tutorials on GJK algo? or you may have some links to demo or anything related to this stuff? I bielieve QHull is using it for intersection tests.



[edited by - robert_s on April 13, 2004 2:43:49 PM]

[edited by - robert_s on April 13, 2004 2:46:26 PM]

Share this post


Link to post
Share on other sites
To simplify the separation axis theorem for convex polyhedras, you can consider only two types of possible collisions. points vs faces, and edges versus edges. all other cases are derived from those two generic cases (edge vs face, face vs face, edge versus point...).

so basically, what you have to do for each faces, find the closest point on the other polygon to that face, and see if it is back facing. That can save some time. Instead of doing the test for each points against the face, pick a point on the convex object, and using the connectivity between points, follow the edge from one point to another to find the point that would be the closest to the face. Since the object is convex, you are bound to find a minimum point towards the face on the other object. if that point is front facing the face, then no collision. This point is called a support point along the face normal. That''s also the basis for the GJK algorithm.

for edges against edges, it''s a lot more tricky. the simplest solution would be, to cross product every edges of convexA against every edges of convexB, and see if the projection of ConvexA and ConvexB along the normal defined by the cross product of the two edges overlap or not. But that''s obviously impractical.

I never tried this, but I would think finding the closest point from an edge, and taking the interconnected edges from that point, and building planes by crossing the edges together would be more practical. although, it''s still very slow.

another method tries to find the closest features on the two convex polyhedras, and caching the closest features, you can quickly test two moving convex polyhedras against each others, taking advantage of the space-time coherence (the objects won''t move much relative to each other between physics frames).

I-collide uses that method, I think, and it''s a popular way of testing two convex objects. You need to store connectivity info for each polyhedras (like a list of neighbouring points for each vertex), but that''s not a big deal.

there is a library developed by Gino Van Der Gergen, called SOLID, which implements the GJK stuff. It''s free and the source code is available.

http://www.win.tue.nl/~gino/solid/


also, for non convex polyhedras, you have a variety of methods, build octrees, a voxel map, split the non convex objects into convex parts, ...

for example
http://www.dh.aist.go.jp/~kawachi/ncmd.html

I used to have a demo of a GJK-like collison detection on convex hulls, but I seemed to have lost it.

Anyway, it should not be too hard to implement, the tricky part is to find the penetration depth (i.e. the embedded points of contacts) when the GJK fails (intersection detected), as there is no easy way to solve that case. But that''s if you allow penetrations to occur.

You would think it should be easy, as easy as when the object do not intersect, but it''s not, for some weird reason (after all, it''s like finding geometrically the point on a convex curve the closest to the origin, when the origin is inside the curve). look for enhanced GJK, which gives pointers on how to solve this.

Share this post


Link to post
Share on other sites
Ok. Thank you very much Olii for help.
But I'll have to ask you again about this stuff to be sure that I understood you 100%.

So you suggesting to ignore those two methods described on gamasutra's site ie. searching for a separating plane using an edge from a convex hull A and a point from convex B.

What you're saying is to select a face in A and select a face in B and in that face (poly) from B search for the nearest point to face A. Am I right? Once the nearest point is found in current face in convex B then perform test if the point is on positive side of the current plane in convex A or not. Once this test is finished then I select the next face in B and search for nearest point to the face in A. I keep selecting faces in B and searching for nearest points in B. Then when there is no more faces to test in B I select another face in A and run those test again through all faces in B searching for nearest points in each face in B. Is this what you meant?

Olii. If you look on the image above you can see that the points B1, B2 on convex B (pyramid: 4 faces) are blue meaning that they are on positive side of the face A (highlighted in red) and the red point B3 even though its not inside the convex hull A it is still below the plane and is marked in red. Now my algo currently indicates that there is a collision as there is no separating plane found. (I still havent implemented the adege-point test as described at teh end of that article I mentioned earlier).
Now, the method you desribed,
quote:
so basically, what you have to do for each faces, find the closest point on the other polygon to that face, and see if it is back facing. That can save some time. Instead of doing the test for each points against the face, pick a point on the convex object, and using the connectivity between points, follow the edge from one point to another to find the point that would be the closest to the face. Since the object is convex, you are bound to find a minimum point towards the face on the other object. if that point is front facing the face, then no collision. This point is called a support point along the face normal.

which point do you consider to be the nearest point to the plane? B1 or B3. I know B3 is below the plane but in terms of numbers B3 is smallest. If B2 is nearest then how do you filter B3 so it desnt tell you that tere is a collision? If B3 is the smallest then this point is not front facing which would mean its a collision. But its not true. Sorry if I still have got you as I should



[edited by - robert_s on April 13, 2004 7:44:17 PM]

[edited by - robert_s on April 13, 2004 7:49:30 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by robert_s
Ok. Thank you very much Olii for help.
But I'll have to ask you again about this stuff to be sure that I understood you 100%.

So you suggesting to ignore those two methods described on gamasutra's site ie. searching for a separating plane using an edge from a convex hull A and a point from convex B.

What you're saying is to select a face in A and select a face in B and in that face (poly) from B search for the nearest point to face A. Am I right? Once the nearest point is found in current face in convex B then perform test if the point is on positive side of the current plane in convex A or not. Once this test is finished then I select the next face in B and search for nearest point to the face in A. I keep selecting faces in B and searching for nearest points in B. Then when there is no more faces to test in B I select another face in A and run those test again through all faces in B searching for nearest points in each face in B. Is this what you meant?




not quite.

1) Select a face on A (called FA).

2) Select a point on B (called PB).

3) Calculate the distance of PB to FA.

5) Get the neighbours of PB (called PB[0], PB[1], PB[2], ...).

6) let min = dist(PB, FA);

7) for (each neighbours PB[j])

8) if (dist(PB[j], FA) < min) { min = dist(PB[j], FA); PB = PB[j]; }

9) end loop

10) if (dist(PB, FA) == min) // we have a minimum
11). if (min > 0) return false; // the minimum point is front facing, Face A is the separation plane, PB is the closest point.
12). else goto 1). // test a new face on A.

10) goto 3) // continue the search


[edited by - oliii on April 14, 2004 5:05:01 AM]

[edited by - oliii on April 14, 2004 5:05:31 AM]

Share this post


Link to post
Share on other sites
Thank you Olii. Yes I followed your instructions and implemented my function but it still doesnt fully work. I bet I've done something wrong. Please see my code below.

bool ConvexHull::ConvexIntersection( ConvexHull &c1, ConvexHull &c2) 
{
// for each poly in convex hull ch1

for( int i=0; i<c1.CountPoly; ++i )
{
// 1) Select a face on A (called FA) & find its normal vector

Vec3 N;
Vec3 AB = c1.Polys[i]->VList[0] - c1.Polys[i]->VList[1];
Vec3 BC = c1.Polys[i]->VList[2] - c1.Polys[i]->VList[1];
N.CrossProd(AB,BC);

// For each poly in c2

for( int j=0; j<c2.CountPoly; ++j )
{
// 2) Select a point on B (called PB).

Vec3 PB = c2.Polys[j]->VList[0]; // Select PB point (first point on poly)

Vec3 *FA = c1.Polys[i]->VList;

// 3) Calculate the distance of PB to FA.

float min_dist = N.DotProd(PB - FA[0]); // dist from face A to PB point

float dist = 0.0f;

// For each vertex in c2 poly[k] look for the closest point to currently selected face A

// 4,7) Get the neighbours of PB (called PB[0], PB[1], PB[2], ...). for each neighbours PB[j])

for( int k=0; k<c2.Polys[j]->CountVertex; ++k )
{
// 8) go through all vertex neighbours and calculate distance to FA

dist = N.DotProd(c2.Polys[j]->VList[k] - FA[0]);

if( dist < min_dist )
{
min_dist = dist; // store mind dist

PB = c2.Polys[j]->VList[k]; // store closest vertex in PB to he plane FA

}
} // 9) end loop


// 10) if (dist(PB, FA) == min) // we have a minimum

if( N.DotProd(PB - FA[0]) == min_dist )
{
if (min_dist>0)
{
// 11)

return false; // the minimum point is front facing, Face A is the separation plane, PB is the closest point.

}
else
{
// 12). else goto 1).

break; // test a new face on A.

}
}
}// end loop got to next face A

}

return true;
}


In some cases the collision occurs even when objects are not colliding. arghhhh.... I have to go through this again. I hope I'll spot my mistake. I mean is there anything not reflecting the instructions you provided Olii?
Thank you. I really appreciate, you helped me alot


[edited by - robert_s on April 14, 2004 7:04:51 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by robert_s
Now, the method you desribed,

which point do you consider to be the nearest point to the plane? B1 or B3. I know B3 is below the plane but in terms of numbers B3 is smallest. If B2 is nearest then how do you filter B3 so it desnt tell you that tere is a collision? If B3 is the smallest then this point is not front facing which would mean its a collision. But its not true. Sorry if I still have got you as I should



B3 will be the closest point.

using the loop above, start with B1.

neighbours are B2, B3, B4.

PB = B1

3)
min = d = dist(PB, FA)

dist(B2, FA) = d2, and (d2 > min)
dist(B3, FA) = d3, and (d3 < min), so min = d3, PB = B3;
dist(B4, FA) = d4, and (d4 > min)

(d != min), go to 3)


3)
PB = B3

neighbours are B1, B2, B4.

min = d = dist(PB, FA)

dist(B1, FA) = d1, and (d1 > min)
dist(B2, FA) = d2, and (d2 > min)
dist(B4, FA) = d4, and (d4 > min)

(d == min),
so P3 is the closest point from face FA.
(d < 0) so that plane is inconclusive, get the next face on Convex A and start again.

obviously caching data would help, to avoid testing the same vertices again and again (B1 B2, B4 have already been tested, no need to test them again at all, for that face).

this stuff works better for complex hulls, obviously. For a tetrahedron, you might as well test all the vertices. As soon as you found a vertex back facing the plane, go to 1). If no vertex back face the plane, you have a separation plane.

eventually, you could find that no face has a closest point front-facing the plane, so in that case, you need to test with edges as well, or you''ll get false positives.

For edges, it''s practically the same thing, except you need to find the closest point to that edge. Once you found it, build planes with edges attached to that point and the edge you are testing, and see if the projections of the convex hulls overlap along the plane normal or not.

this isn''t the best algo in the world, by a mile. it''s painfully slow. But walking along the convex object has it''s use, and is used by GJK and I-Collide to find support vertices. So good to keep.

Share this post


Link to post
Share on other sites

  • Advertisement