Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


Picking question


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
18 replies to this topic

#1 lucky6969b   Members   -  Reputation: 636

Like
0Likes
Like

Posted 22 April 2011 - 05:44 AM

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.

bool intersectSegmentTriangle(const float* sp, const float* sq,
							  const float* a, const float* b, const float* c,
							  float &t)
{
	float v, w;
	float ab[3], ac[3], qp[3], ap[3], norm[3], e[3];
	vsub(ab, b, a);
	vsub(ac, c, a);
	vsub(qp, sp, sq);
	
	// 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;
	
	return true;
}

static bool raycast(rcMeshLoaderObj& mesh, float* src, float* dst, float& tmin)
{
	float dir[3];
	vsub(dir, dst, src);
	
	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[i];
		if (vdot(dir, n) > 0)
			continue;
		
		float t = 1;
		if (intersectSegmentTriangle(src, dst,
									 &verts[tris[i]*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

Sponsor:

#2 alexjc   Members   -  Reputation: 450

Like
2Likes
Like

Posted 22 April 2011 - 06:46 AM

What do you mean by picking? A ray / polygon intersection test? What are you trying to do?

Alex

P.S. You might want to read this for future reference.

Join us in Vienna for the Game/AI Conference 2014, on July 7-10... Don't miss it!


#3 Hodgman   Moderators   -  Reputation: 31920

Like
1Likes
Like

Posted 22 April 2011 - 08:41 AM

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?

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 destination = source + direction * large_number

#4 lucky6969b   Members   -  Reputation: 636

Like
-1Likes
Like

Posted 23 April 2011 - 01:30 AM

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];

	// edge 1
	edge1[0] = c[0] - b[0];
	edge1[1] = c[1] - b[1];
	edge1[2] = c[2] - b[2];


	// cross product of the 2 edges composing the triangle
	float temp[3];
	vcross(temp, edge3, edge1);

	
	float n2[3];
	memcpy (n2, temp, sizeof(float)*3);

	// normalize the cross product vector
	float sqroot = sqrtf(temp[0]*temp[0]+temp[1]*temp[1]+temp[2]*temp[2]);
	
	if (sqroot != 0.0f) {
		n2[0] = n2[0] / sqroot;
		n2[1] = n2[1] / sqroot;
		n2[2] = n2[2] / sqroot;
	}

	float d = vdot(a, n2);

	float p0n = vdot(src, n2);

	float dn = vdot(dir, n2);

	float t;

	if (dn != 0.0f)
		t = d - p0n / dn;

//... Test the value t for intersection





Thanks

#5 scgames   Members   -  Reputation: 1977

Like
1Likes
Like

Posted 23 April 2011 - 03:01 AM

The topic isn't directly related to AI or OpenGL; it's really just a general math topic. (Maybe you could get a mod to move the thread for you...)

The code looks ok (although I didn't proof it thoroughly). But, it's not a complete test, and you shouldn't need to normalize the triangle normal.

More importantly though, before moving forward, I'd recommend that you refactor the code. You never want to be writing anything like this:

edge3[0] = b[0] - a[0];
edge3[1] = b[1] - a[1];
edge3[2] = b[2] - a[2];

float n2[3];
memcpy (n2, temp, sizeof(float)*3);

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.

#6 lucky6969b   Members   -  Reputation: 636

Like
0Likes
Like

Posted 23 April 2011 - 03:23 AM

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

#7 thatguyfromthething   Members   -  Reputation: 80

Like
1Likes
Like

Posted 23 April 2011 - 06:53 PM

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:

	bool IntersectUtil::segmentTriangle(const Point3& origin, const Point3& end, const Point3& vert1, const Point3& vert2, const Point3& vert3, Point3& intersectionPoint)
	{
		bool intersectsPlane = linePlane(origin, end, vert1, vert2, vert3, intersectionPoint);

		if(intersectsPlane==false)
		{
			return false;
		}

		float segmentLength = distanceSquared(origin, end);
		float intersectDistance = distanceSquared(origin, intersectionPoint)+EPSILON;

		if(intersectDistance>=segmentLength)
		{
			return false;
		}
		
		return GeomUtil::pointInTriangle(intersectionPoint, vert1, vert2, vert3);
	}

	bool IntersectUtil::linePlane(const Point3& origin, const Point3& end, const Point3& vert1, const Point3& vert2, const Point3& vert3, Point3& intersectionPoint)
	{
		Point3 ray = GeomUtil::normalize(end-origin);
		Point3 edge1 = vert2-vert1;
		Point3 edge2 = vert3-vert1;
		Point3 normal = GeomUtil::cross(edge1, edge2);

		float dp = GeomUtil::dot(ray, normal);

		Point3 toVert1 = origin-vert1;
		float det1 = -GeomUtil::dot(normal, toVert1);
		float det2 = GeomUtil::dot(normal, ray);
		float r = det1/det2;
		if(r<0)
		{
			return false;
		}

		intersectionPoint = origin+ray*r;

		return true;
	}

	bool GeomUtil::pointInTriangle(const Point3& p, const Point3& vert1, const Point3& vert2, const Point3& vert3)
	{
		if(sameSideLine(p, vert2, vert1, vert3)&&sameSideLine(p, vert3, vert1, vert2)&&sameSideLine(p, vert1, vert2, vert3))
		{
			return true;
		}
		return false;
	}

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/

#8 lucky6969b   Members   -  Reputation: 636

Like
0Likes
Like

Posted 24 April 2011 - 12:29 AM

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...

thanks once more
Jack

#9 thatguyfromthething   Members   -  Reputation: 80

Like
1Likes
Like

Posted 24 April 2011 - 01:16 AM

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.

#10 scgames   Members   -  Reputation: 1977

Like
1Likes
Like

Posted 24 April 2011 - 01:29 AM

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).

#11 lucky6969b   Members   -  Reputation: 636

Like
0Likes
Like

Posted 24 April 2011 - 01:34 AM

Hi, it's me again
I wonder how do I know the end point in advance if rays are supposed to be infinite.
I am interested in knowing (as in the code) if the distance between origin and dest is shorter than the ray, it would return a false to the invoker.
Thanks
Jack

#12 scgames   Members   -  Reputation: 1977

Like
1Likes
Like

Posted 24 April 2011 - 01:57 AM

Hi, it's me again
I wonder how do I know the end point in advance if rays are supposed to be infinite.
I am interested in knowing (as in the code) if the distance between origin and dest is shorter than the ray, it would return a false to the invoker.

So is it a ray test or a segment test that you want? If you want to impose a 'max distance' limit on the ray, then it's actually a segment test that you want.

Also, did you see my post above? It includes some info that might be relevant to your question.

#13 lucky6969b   Members   -  Reputation: 636

Like
0Likes
Like

Posted 24 April 2011 - 01:58 AM

Hi jyk,
Now that I know how to handle the endpoint, so what is the method that handles edge tests uniformly as you mentioned? Any code snippets for me to reference.
Sorry, I've read your post, it's a matter of coincidence we posted at the same time :)
Thanks
Jack

#14 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 24 April 2011 - 02:23 AM

Now that I know how to handle the endpoint, so what is the method that handles edge tests uniformly as you mentioned?

If books are an option for you, there's good coverage of the topic in Christer Ericson's collision detection book. (That's actually the only reference I can think of off the top of my head that covers it in detail, although I'm sure there are others as well.)

#15 lucky6969b   Members   -  Reputation: 636

Like
0Likes
Like

Posted 24 April 2011 - 02:36 AM

Ok, many thanks, i shall check that out too...

#16 thatguyfromthething   Members   -  Reputation: 80

Like
0Likes
Like

Posted 24 April 2011 - 04:01 AM

:~

Why do you assume it falls through the cracks if you don't have the code for sameSideLine? Well, it doesn't because 0 value is counted as positive.

The other method is to use is actually less accurate and has more round error. It's (possibly but not necessarily) faster for comparisons but no one (but you apparently) would argue it's more accurate.

Normalizing also makes for more accuracy in some cases, too, though it is slower of course.

Good catch on the unused code that will get optimized out, though, I guess.

#17 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 24 April 2011 - 04:17 AM

Why do you assume it falls through the cracks if you don't have the code for sameSideLine? Well, it doesn't because 0 value is counted as positive.

Counting 0 as positive doesn't address the problem. (Feel free to post the code for sameSideLine() though if you want.)

The other method is to use is actually less accurate and has more round error.

What method are you referring to?

but no one (but you apparently) would argue it's more accurate.

Nope, it's not just me. (For example, the book I mentioned earlier advocates the alternate approach as well.)

#18 thatguyfromthething   Members   -  Reputation: 80

Like
0Likes
Like

Posted 24 April 2011 - 04:53 AM

I see what you are talking about now, the distanceSqared check with the epsilon. That's wrong, too, though for different reasons :D But I'm sure it's not the most optimal way, but computing barycentric coordiantes should not be more accurate but less, and if anything this method will give false positives.

#19 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 24 April 2011 - 05:15 AM

but computing barycentric coordiantes should not be more accurate but less, and if anything this method will give false positives.

Well, I'm not sure what you mean by that. Using barycentric coordinates is standard in point-triangle containment tests and intersection tests involving linear components and triangles (just check the literature). It's not inaccurate, and it won't return false positives. Although I'd have to see the code to be sure, I'd guess that even your sameSideLine() function uses barycentric coordinates.

If needed, I can provide links to articles, tutorials, books, and code samples that use barycentric coordinates to solve this problem. (Among other things, the book I mentioned earlier is a standard reference on collision detection, and it uses exactly the method I'm talking about here.) It's completely standard, so I'm not sure why you think there's something wrong with this approach.

There are different ways to compute the barycentric coordinates, of course, and the point of the method I'm advocating is to compute them in a way that avoids false negatives due to numerical error. Otherwise, there's nothing remarkable (or problematic) about the method in question.

The only thing I can guess is that we're not actually talking about the same thing here. In any case, there's nothing wrong with using barycentric coordinates for this, and that is in fact the standard solution to the problem.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS