What is causing the artifacts in my raytracer?

Question

EDIT: I have now solved the problem; you can see my solution in the answers.

I'm in the process of writing a realtime raytracer using OpenGL (in a GLSL Compute Shader), and I've run into a slight problem with some of my line-triangle intersections (or at least, I believe they are the culprit). Here's a picture of what's happening:

As you can see some pixels are being coloured black at the intersection of two triangles near the top of the image. It's probably got something to do with the way I'm handling floats or something, and I've tried searching for a solution online but can't find similar situations. Perhaps there's an important keyword I'm missing?

Anyways, the important piece of code is this one:

#define EPSILON 0.001f
#define FAR_CLIP 10000.0f
float FindRayTriangleIntersection(Ray r, Triangle p)
{
    // Based on Moller-Trumbone paper
    vec3 E1 = p.v1 - p.v0;
    vec3 E2 = p.v2 - p.v0;
    vec3 T = r.origin - p.v0;
    vec3 D = r.dir;
    vec3 P = cross(D, E2);
    vec3 Q = cross(T, E1);

    float f = 1.0f / dot(P, E1);
    float t = f * dot(Q, E2);
    float u = f * dot(P, T);
    float v = f * dot(Q, D);

    if (u > -EPSILON && v > -EPSILON && u+v < 1.0f+EPSILON) return t;
    else return FAR_CLIP;
}

I've tried various values for EPSILON, tried variations with +/- for the EPSILON values, but to no avail. Also, changing the 1.0f+EPSILON to a 1.0-EPSILON yields a steady black line the whole way across.

Also to clarify, there definitely is NOT a gap between the two triangles. They are tightly packed (and I have also tried extending them so they intersect, but I still get the same black dots).

Curiously enough, the bottom intersection shows no sign of this phenomenon.

Last note: if more of my code is needed just ask and I'll try to isolate some more code (or maybe just link to the entire shader).

UPDATE: It was pointed out that the 'black artifacts' are in fact brown. So I've dug a bit deeper and turned off all reflections, and got this result:

The brown colour is actually coming from just the copper material on the top, but more importantly I think I have an idea what the cause of the problem is, but I'm no closer to solving it.

It seems that when the rays get fired out, due to very slight imperfections in the floating arithmetic, some rays intersect the top triangle, and some intersect the bottom.

So I suppose now the question reduces to this: how can I have some sort of consistency in deciding which triangle should be hit in cases like this?

Answer 1

So it turns out it was not the code I had posted that caused the problem. Thanks to some help in the comment, I was able to find it was this code when I'm determining the nearest object to the camera:

float nearest_t = FAR_CLIP;
int nearest_index = 0;
for (int j=0; j<NumObjects; j++)
{
    float t = FAR_CLIP;
    t = FindRayObjectIntersection(r, objects[j]);

    if (t < nearest_t && t > EPSILON && t < FAR_CLIP)
    {
        nearest_t = t;
        nearest_index = j;
    }
}

When determining t, sometimes the triangles were so close together that the t < nearest_t had an almost probabilistic result, since the intersections were roughly the same distance from the camera.

My initial solution was to change the inner if-statement to:

if (t < nearest_t-EPSILON && t > EPSILON && t < FAR_CLIP)

This ensures that if two intersections are very close together, it will always choose the first object to display (unless the second object is closer by at least EPSILON). Here is a resulting image (with reflections disabled):

Now there were still some small artifacts, so it was clear that there was still a slight problem. So upon some discussion in the comments, @Soonts came up with the idea of blending the triangles' colours. This lead me to have to change the above code further in order to keep track of the distance to both triangles:

if (t > EPSILON && t < FAR_CLIP && abs(nearest_t - t) < EPSILON)
{
    nearest_index2 = nearest_index;
    nearest_t2 = nearest_t;
}
if (t < nearest_t+EPSILON && t > EPSILON && t < FAR_CLIP)
{
    nearest_t = t;
    nearest_index = j;
}

I also added this colour blending code:

OverallColor = mix(c1, c2, 0.5f * abs(T1 - T2) / EPSILON);

After these two steps, and honestly I think this effect was more from the logic change than the blending change, I got this result:

I hope others find this solution helpful, or at the very least that it sparks some ideas to solve your own problems. As a final example, here is the beautiful result with reflections, softer shadows and some anti-aliasing all turned on:

Happy raytracing!