• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
lucky6969b

Picking question

18 posts in this topic

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.

[code]
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;
}

[/code]

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
0

Share this post


Link to post
Share on other sites
What do you mean by picking? A ray / polygon intersection test? What are you trying to do?

Alex

P.S. You might want to [url="http://www.catb.org/~esr/faqs/smart-questions.html"]read this[/url] for future reference.
2

Share this post


Link to post
Share on other sites
[quote name='lucky6969b' timestamp='1303472696' post='4801578']What does the general opengl coding look like for picking operations in my case?[/quote]OpenGL is a graphics library, not a collision detection library; It doesn't directly support "picking" / ray-cast operations.[quote]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]
1

Share this post


Link to post
Share on other sites
Thanks for the replies. I finally came up with this by myself. Will this work or not?
[code]
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


[/code]



Thanks
-1

Share this post


Link to post
Share on other sites
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:

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

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

[code]float sqroot = sqrtf(temp[0]*temp[0]+temp[1]*temp[1]+temp[2]*temp[2]);[/code]
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.
1

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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:

[code]
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;
}
[/code]

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/
1

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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.
1

Share this post


Link to post
Share on other sites
[quote name='lucky6969b' timestamp='1303626577' post='4802184']
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);[/quote]
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:

[code]end = origin + direction * max_distance;[/code]
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:

[code]float dp = GeomUtil::dot(ray, normal);[/code]
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).
1

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
[quote name='lucky6969b' timestamp='1303630497' post='4802195']
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.[/quote]
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.
1

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
[quote name='lucky6969b' timestamp='1303631909' post='4802203']
Now that I know how to handle the endpoint, so what is the method that handles edge tests uniformly as you mentioned?[/quote]
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.)
0

Share this post


Link to post
Share on other sites
:~

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

Share this post


Link to post
Share on other sites
[quote name='thatguyfromthething' timestamp='1303639268' post='4802237']
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.[/quote]
Counting 0 as positive doesn't address the problem. (Feel free to post the code for sameSideLine() though if you want.)

[quote]The other method is to use is actually less accurate and has more round error.[/quote]
What method are you referring to?

[quote]but no one (but you apparently) would argue it's more accurate.[/quote]
Nope, it's not just me. (For example, the book I mentioned earlier advocates the alternate approach as well.)
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
[quote name='thatguyfromthething' timestamp='1303642392' post='4802262']
but computing barycentric coordiantes should not be more accurate but less, and if anything this method will give false positives.[/quote]
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.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0