Algorithm for triangle picking?

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.

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.