Inexact correspondence between the area of intersection of two triangles and the triangle constructed from the points of this intersection

Hello,

I’m trying to draw a flat shadow from a single face and a light source that has a small radius, like in some platformer games.

To do this, I use two triangles, each of which forms its own side of the penumbra (and further 1-2 for full shade). The position of the points forming the triangles is calculated in the geometry shader; only two points forming the edge and the point defining the center of the light source are input to it. The radius of the light source and the length of the shadow are constant.

As long as the triangles do not intersect, the algorithm performs well. (1)
(All images are combined into one due to “An error occurred: Sorry, new users can only put one embedded media item in a post.” Sorry.)

But, in order to correctly process the color at the intersection of the triangles, in the geometry shader I create another triangle, highlighted in red in the image below. (2)

In most cases this works well: (3)

But sometimes on the border between the intersection and a single triangle, points of the wrong color are formed. As far as I understand, this is an error related to the use of float, and because of which the penumbra edge and the intersection edge do not coincide quite a bit. (4)

I tried to avoid this problem in three ways - using anti-aliasing; slightly adjusting the position of the initial points forming the triangle (since they are all calculated before being passed to the fragment shader), but could not come up with an algorithm that would fix this; using a different algorithm for determining the point of intersection of lines. I also tried to find a way to pass a double value to gl_Position, but as I understand it, this is impossible?

Are there other ways to avoid this without radically changing the algorithm? (All drawing is done in one call to glDrawElements(…))

The points calculation code is as follows:

(A, B_one, B_two - input vec3 points (where z always 0.0), in_distance and in_radius - input floats)

Location of points on image above (5)

``````vec3 AB_one = B_one - A; //Vector from B_one to A
vec3 AB_two = B_two - A; //Vector from B_two to A
vec3 AR_one = (normalize(cross(AB_one, vec3(0,0,sign((A.x - B_one.x) * (B_two.y - B_one.y) - (A.y - B_one.y) * ( B_two.x - B_one.x))))) * in_radius); //Vector to the outermost point of the light source relative to B_one
vec3 AR_two = (normalize(cross(AB_two, vec3(0,0,sign((A.x - B_one.x) * (B_two.y - B_one.y) - (A.y - B_one.y) * ( B_two.x - B_one.x))))) * in_radius); //Vector to the outermost point of the light source relative to B_two
vec3 E_one = B_one + (normalize((B_one - (A - AR_one))) * in_distance);
vec3 D_two = B_two + (normalize((B_two - (A + AR_two))) * in_distance);
vec3 D_one = B_one + (normalize((B_one - (A + AR_one))) * in_distance);
vec3 E_two = B_two + (normalize((B_two - (A - AR_two))) * in_distance);
vec2 I = Intersect(vec4(B_one.x, B_one.y, E_one.x, E_one.y), vec4(B_two.x, B_two.y, D_two.x, D_two.y));
``````

Intersect function:

``````vec2 Intersect(vec4 line_one, vec4 line_two){

vec2 a1 = vec2(line_one.x, line_one.y);
vec2 b1 = vec2(line_one.z, line_one.w);
vec2 a2 = vec2(line_two.x, line_two.y);
vec2 b2 = vec2(line_two.z, line_two.w);

float deltaX1 = b1.x - a1.x;
float deltaX2 = b2.x - a2.x;
float slope1 = 1000000.0;
float slope2 = 1000000.0;

float intersectX;
float intersectY;

if (deltaX1 != 0.0) {
slope1 = (b1.y - a1.y) / deltaX1;
}

if (deltaX2 != 0.0) {
slope2 = (b2.y - a2.y) / deltaX2;
}

float yIntercept1 = a1.y - a1.x * slope1;
float yIntercept2 = a2.y - a2.x * slope2;

if (slope1 != slope2) {

intersectX = (yIntercept1 - yIntercept2) / (slope2 - slope1);
intersectY = intersectX * slope1 + yIntercept1;

}

return vec2(intersectX,intersectY);

}
``````

Also tried using this version (and both version with double values):

``````vec2 Intersect(vec4 line_one, vec4 line_two){

vec2 a1 = vec2(line_one.x, line_one.y);
vec2 b1 = vec2(line_one.z, line_one.w);
vec2 a2 = vec2(line_two.x, line_two.y);
vec2 b2 = vec2(line_two.z, line_two.w);

float x1 = line_one.x;
float y1 = line_one.y;
float x2 = line_one.z;
float y2 = line_one.w;

float x3 = line_two.x;
float y3 = line_two.y;
float x4 = line_two.z;
float y4 = line_two.w;

float uA = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1));
float uB = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1));

if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) {

float intersectionX = x1 + (uA * (x2 - x1));
float intersectionY = y1 + (uA * (y2 - y1));

return vec2(intersectionX,intersectionY);
}
``````