When I have the following info. 1) vertices of every mesh in the scene 2) normals of every mesh in the scene 3) the ray starting position 4) the ray direction
What does the general opengl coding look like for picking operations in my case? I have the code from Recast, but I am not sure how to modify it to suit my needs.
// Compute triangle normal. Can be precalculated or cached if // intersecting multiple segments against the same triangle vcross(norm, ab, ac);
// Compute denominator d. If d <= 0, segment is parallel to or points // away from triangle, so exit early float d = vdot(qp, norm); if (d <= 0.0f) return false;
// Compute intersection t value of pq with plane of triangle. A ray // intersects iff 0 <= t. Segment intersects iff 0 <= t <= 1. Delay // dividing by d until intersection has been found to pierce triangle vsub(ap, sp, a); t = vdot(ap, norm); if (t < 0.0f) return false; if (t > d) return false; // For segment; exclude this code line for a ray test
// Compute barycentric coordinate components and test if within bounds vcross(e, qp, ap); v = vdot(ac, e); if (v < 0.0f || v > d) return false; w = -vdot(ab, e); if (w < 0.0f || v + w > d) return false;
// Segment/ray intersects triangle. Perform delayed division t /= d;
int nt = mesh.getTriCount(); const float* verts = mesh.getVerts(); const float* normals = mesh.getNormals(); const int* tris = mesh.getTris(); tmin = 1.0f; bool hit = false;
for (int i = 0; i < nt*3; i += 3) { const float* n = &normals; if (vdot(dir, n) > 0) continue;
float t = 1; if (intersectSegmentTriangle(src, dst, &verts[tris*3], &verts[tris[i+1]*3], &verts[tris[i+2]*3], t)) { if (t < tmin) tmin = t; hit = true; } }
return hit; }
You see in this case there is a destination parameter involved. But general picking shouldn't care about the destination, should it? Any thoughts? Thanks Jack
What does the general opengl coding look like for picking operations in my case?
OpenGL is a graphics library, not a collision detection library; It doesn't directly support "picking" / ray-cast operations.
You see in this case there is a destination parameter involved. But general picking shouldn't care about the destination, should it?[/quote]When performing a ray-cast, I've seen a few games that work with lines defined by a start-point and an end-point (source/destination) instead of a start-point and direction. If you do want to work with a source and a direction with one of these APIs, then you can use something like [font="Courier New"]destination = source + direction * large_number[/font]
Thanks for the replies. I finally came up with this by myself. Will this work or not? bool intersect2( const float *src, const float *dir, const float *a, const float *b, const float *c, float &t) { float edge3[3]; float edge1[3]; // edge 3 edge3[0] = b[0] - a[0]; edge3[1] = b[1] - a[1]; edge3[2] = b[2] - a[2];
float sqroot = sqrtf(temp[0]*temp[0]+temp[1]*temp[1]+temp[2]*temp[2]); Even if you're programming in pure C, these types of operations should be factored out into their own dedicated functions (or macros, if you must). Doing so will make the code easier to read, write, understand, and debug.
Thanks jyk for the suggestions. I will try to refactor my code.... (BTW, do I just leave a message here in order to let the mod move this thread?) If so, could the mod move this if it is seen.... Jack
Will you or anyone ever write a collision detection against a mesh that works on first try? Probably not, but this one seems to be missing some steps at a glance. Here is some code to look at:
I was going to copypast all the stuff you need but it turns out I'd have to post a ton of crap I didn't realize. Anyway I found this a while back while trying to do the same thing you are and it's not too advanced ot anything but seems to work ok for basic collision and computational geometry problems.
http://nutils.sourceforge.net/
This is my thread. There are many threads like it, but this one is mine.
Thanks, I'll take a serious look at the source code you posted and the website you mentioned. However, I was wondering what the destination/end point means. Is it any point on the target mesh or do I randomly choose an end point? In case I already had the ray direction, do I ignore this end point? because I see that the ray is calculated by normalize (end-origin); I don't get it...
The origin and endpoint are the start and end of the rays that are cast against the triangles.
The basic process of the most brute force approach is you go through every triangle and see if there is a collision.
Even then it is a PITA because you have a possibility to detect a collision from the wrong direction. However, you can test against the winding order to discard selections (I forget exactly how).
The other thing you can do is only accept the closest hit. Just go through them all.
This is slow compared to something fancy like a BSP or octree (I think there is some octree collision in that lib as well but it looked complicated so I just used brute force), but for something done in user interface, it ultimately doesn't matter. For like rendering you will never get away with brute force but if it's mouse picking or something it's not a big deal.
This is my thread. There are many threads like it, but this one is mine.
However, I was wondering what the destination/end point means. Is it any point on the target mesh or do I randomly choose an end point? In case I already had the ray direction, do I ignore this end point? because I see that the ray is calculated by normalize (end-origin);
The code in question implements a segment-triangle test rather than a ray-triangle test (although it can easily be adapted to implement a ray-triangle test instead).
The 'end' parameter simply represents the endpoint of the segment. If you have a ray represented by an origin and a unit-length direction vector, and a maximum distance that you're interested in, you can compute 'end' as:
end = origin + direction * max_distance; A couple of other things to be aware of regarding the code posted above. First, the code may fail if the ray/segment is parallel or nearly parallel to the triangle plane. (Normally you would check for this and early-out in that case.)
Note that this variable:
float dp = GeomUtil::dot(ray, normal); Is never used and can be removed.
The code checks to see if the intersection point is past the end of the segment by comparing squared lengths. However, this test can be performed in a more straightforward manner in the 'intersect plane' function itself. Also, it shouldn't be necessary to normalize the ray direction in linePlane(). (With a few changes, the code could be tightened up and made both more efficient and more robust.)
This is a corner case, but note that with this code, there's a chance rays/segments might 'fall between the cracks' between triangles; that is, false negatives may be returned. This case is unlikely enough that you could easily use this method and never see it occur. However, it's something to be aware of. In any case, for a truly robust, production-quality solution, you'd want to use a different method (one that handles edge tests uniformly and will therefore never miss intersections between triangles).
