# Algorithm for triangle picking?

I need a triangle picking algorithm, that is, I need to see if my mouse is over a triangle. I've heard what color picking is, but it would pretty much just drop the performance twice (which is not what I want).

I use LWJGL java, and OpenGL 3.3.

If anyone can point me to a triangle picking algorithm then that would be awesome!

My best attempt was to do some transformations on the vertices and then check if it is within the center, it is limited and not what I exactly want.

What I do is a test known as Ray-Picking. It is a test to see if a "ray" intersects a triangle. In order to use it, you need to learn how to convert your mouse coordinate into world coordinates (where your triangles are). Then, you need to create a matrix which is the inverse of how you render your triangles, so it should equal the inverse view matrix ** multiplied by the **inverse projection matrix.

QVector3D screenToSpace(int x, int y, int z)
{
makeCurrent();
GLint viewport[4];
GLfloat winX, winY;

glGetIntegerv(GL_VIEWPORT, viewport);
winX = ((float)x/viewport[2]*2)-1;
winY = ((float)(viewport[3]-y)/viewport[3]*2)-1;

QMatrix4x4 mat =  ViewMatrix().inverted() * Projection().inverted();
QVector4D wSC = (mat) * QVector4D(winX,winY,z,1);
wSC /= wSC[3];     // Divide xyz by w (the fourth component in a 4D vector)
return wSC.toVector3D();
}


The above method is called to generate a ray at a given z distance. If you are just clicking on the screen, the first point of the ray should use a z of -1, and a far ray point should be +1.

With the ray points, you can now use the following alogorithm to check if your mouse coordinates (now converted into a line in 3D space, and in the code = NearPoint && FarPoint) intersects with a triangle:

bool intersect(QVector3D nearP, QVector3D farP)
{
for (int aA = 0; aA < triangles.size(); aA+=3)
{
QVector3D    u, v, n;              // triangle vectors
QVector3D    dir, w0, w;           // ray vectors
float     r, a, b;                 // params to calc ray-plane intersect

// get triangle edge vectors and plane normal
u = Point1 - Point0;
v = Point2 - Point0;
n = QVector3D::crossProduct(u,v);    // cross product
if (n == (QVector3D(0,0,0)))         // triangle is degenerate
return false;                    // do not deal with this case

dir = farP - nearP;                  // ray direction vector
w0 = nearP - temp0;
a = -dot(n,w0);
b = dot(n,dir);
if (fabs(b) < 0.00000001) {     // ray is  parallel to triangle plane
if (a == 0)                 // ray lies in triangle plane
continue;
else continue;              // ray disjoint from plane
}

// get intersect point of ray with triangle plane
r = a / b;
if (r < 0.0)                    // ray goes away from triangle
continue;                   // => no intersect
// for a segment, also test if (r > 1.0) => no intersect

QVector3D I;
I = (nearP + r * dir);          // intersect point of ray and plane

// is I inside T?
float    uu, uv, vv, wu, wv, D;
uu = dot(u,u);
uv = dot(u,v);
vv = dot(v,v);
w = I - temp0;
wu = dot(w,u);
wv = dot(w,v);
D = uv * uv - uu * vv;

// get and test parametric coords
float s, t;
s = (uv * wv - vv * wu) / D;
if (s < 0.0 || s > 1.0)         // I is outside T
continue;
t = (uv * wu - uu * wv) / D;
if (t < 0.0 || (s + t) > 1.0)  // I is outside T
continue;

return true;                   // I is in T
}
return false;
}


In practice, the above 2 functions can be used like this:

bool createRay(int MouseX, int MouseY)
{
QVector3D nearP = screenToSpace(MouseX,MouseY,-1);
QVector3D farP = screenToSpace(MouseX,MouseY,1);
bool rayIntersect = intersect(nearP, farP);
return rayIntersect;
}


Where "createRay() returns true if the mouse intersects a triangle, and false if not.

• Awesome! This is just what i was looking for, the extra bit of information you just wrote out helped me a LOT thanks! – EEVV Oct 12 '15 at 17:39
• I updated the code in my post. It pretty much came straight from my project, so the logic loops through all the vertices for a given object, and returns if it is within it or not. – Yattabyte Oct 12 '15 at 17:45
• yeah the last bit needs some editing, it doesnt appear to be in a "code box" – EEVV Oct 12 '15 at 17:46
• My mistake, however I really did update the chunk on the intersection algorithm's code – Yattabyte Oct 12 '15 at 17:47
• alright thanks again, i would upvote this but i lack the reputation :( – EEVV Oct 12 '15 at 17:50

You only need to render the triangle IDs when you need to pick and if the rendered scene changed (object moved, camera rotated,...) since the last time you needed to pick.

You can also improve picking by only rendering what can be picked. No need to render the background into the color pick buffer if it can't be interacted with. You can simplify the geometry of the pickable objects as well.

Often you can use a smaller target texture than the 4kp screen as you only need a small area around the mouse. Applying a scaling offset matrix at the bottom (after projection) of the transform stack will let you render only the needed area.

If you absolutely refuse to do color picking then can use a raycast instead. This will cast a ray and return the first object it hit. This works fastest with a spatial partitioning so you don't need to iterate over all objects to find the one that hits.

• This answer is helpful towards colorpicking, but i would prefer not to use it at this point... Since it woulf halve the performance (not really but there is 2 times the things you need to render) i appreciate your answer nonetheless – EEVV Oct 12 '15 at 16:30
• Picking buffer and main frame can be rendered in single pass with multiple render targets – Stranger in the Q Aug 7 '18 at 6:55
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://gamedev.stackexchange.com/questions/109579/algorithm-for-triangle-picking/109591", "fetch_time": 1627833977000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2021-31/segments/1627046154214.63/warc/CC-MAIN-20210801154943-20210801184943-00272.warc.gz", "warc_record_offset": 286322097, "warc_record_length": 40926, "token_count": 1565, "char_count": 5718, "score": 3.5625, "int_score": 4, "crawl": "CC-MAIN-2021-31", "snapshot_type": "longest", "language": "en", "language_score": 0.8470500111579895, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00055-of-00064.parquet"}