Polygons which have a vertex exactly "west" of the origin where that vertex does not have any clockwise walls can produce some artifacts due to completing the sweep incorrectly.

[aaclayton]

1. Create a new scene
2. Place a vertical wall segment with grid snapping
3. Create a light and place it on the same height as the upper wall segment point and to the right of it
4. Make sure the light radius is large enough, otherwise it doesn't fail for some reason

[aaclayton]

Originally in GitLab by @caewok

Two initial observations:

1. I could not replicate this on scenes that already existed before updating to v9.236. I could replicate it by creating a new scene in v9.236.
2. In all cases, whether the padding was added correctly or not, the vertices according to CONFIG.debug.polygons = true were ordered such that the first vertex was the one due west. This suggests to me that the vertex sort is probably not the culprit---if it were the culprit, I would expect vertex order to move around between the "good" and the "bad" versions.

[aaclayton]

Originally in GitLab by @caewok

Took a run through the ClockwiseSweepPolygon code:

In executeSweep, vertex 1 is the one due west. There are no active edges. The vertex has one counter-clockwise edge. Therefore, it (incorrectly) falls into this case:

// Case 3 - If there are no counter-clockwise edges we must be beginning traversal down a new edge
// empty -> edge
// empty -> limited
if ( !activeEdges.size || !nccw ) {
  return this._beginNewEdge(ray, result, activeEdges, isBinding);
}

Instead, what should happen is that there should be one active edge, and vertex 1 should be processed in Case 6 (complete edge).

I strongly suspect the problem lies with _initializeActiveEdges.

  _initializeActiveEdges() {
    const rMin = this.config.rMin;
    const edges = new Set();
    for ( let edge of this.edges ) {
      const x = foundry.utils.lineSegmentIntersects(rMin.A, rMin.B, edge.A, edge.B);
      if ( x ) edges.add(edge);
    }
    return edges;
  }

The lineSegmentIntersects is not picking up the intersection if the ray is very large. For example, running through the console I see this for that first vertex:

edge:
A: 1800, 1700
B: 1800, 1100

rMin:
A: 2300, 1100
B: 1210.8, 1099.9999999999998

This tells me that as the radius gets larger, numerical approximations are cropping up and causing the segment intersection test to fail. This is likely only a problem because we need this intersection test to be consistent with the vertices sort and the identification of ccw/cw edges. In other words, if Foundry thinks the ray due west does not intersect this first vertex, that would be fine but for the fact that the sort placed it first. This inconsistency likely is causing the error. It shows up for larger radius values because a larger radius increases the distance between the ray and the vertex if the ray is slightly off-angle due to a numerical approximation like 1099.9999 instead of 1100.

Possible solutions: (1) see if a robust ccw test for the sort and this intersects test makes a difference; (2) make the intersects test more lenient, maybe by also testing for closeness to an edge vertex; (3) ?? somehow tie the initialize active edges more strongly to the sort, to resolve the inconsistency.

[aaclayton]

Originally in GitLab by @dev7355608

I know very little about this stuff, but I observed that the collisions of the first/westwards ray are not ordered correctly. Not sure why CONFIG.debug.polygons = true implies otherwise?

[aaclayton]

Originally in GitLab by @caewok

A simple fix would be to add the ccw edges for the first vertex to activeEdges directly. Say, right after let activeEdges = this._initializeActiveEdges(); in _executeSweep. This would not, however, fix the problem for edges behind the initial vertex (where the edge was aligned just like the front-most one, with its cw vertex aligned on the west ray. It would still be possible for those edges to get missed by the intersection test. I think to ensure those get captured would require a more permissive intersection test.

[aaclayton]

Originally in GitLab by @dev7355608

lineSegmentIntersects is 100% accurate if all points are <=25bit integer (lineSegmentIntersection wouldn't need an epsilon check as well if the points are integer). Maybe it would be a good idea to round the ray's start-/endpoints to integer coordinates?

[aaclayton]

Originally in GitLab by @caewok

If you want a more permissive intersection test, here is one option:

/**
 * Quickly test whether the line segment AB nearly intersects with the line segment CD,
 * meaning that they are within ± √2 / 2 of one another
 * This method does not determine the point of intersection, for that use lineLineIntersection
 * @memberof helpers
 *
 * @param {Point} a                   The first endpoint of segment AB
 * @param {Point} b                   The second endpoint of segment AB
 * @param {Point} c                   The first endpoint of segment CD
 * @param {Point} d                   The second endpoint of segment CD
 *
 * @returns {boolean}                 Do the line segments intersect?
 */


function lineSegmentNearlyIntersects(a, b, c, d) {
  const xab = (nearOrient2d(a, b, c) * nearOrient2d(a, b, d)) <= 0;
  const xcd = (nearOrient2d(c, d, a) * nearOrient2d(c, d, b)) <= 0;
  return xab && xcd;
}


/**
 * Is the point counterclockwise, clockwise, or colinear w/r/t the ray a,b
 * Consider coordinates within ± √2 / 2 from the line as colinear
 * (√2 / 2 is half the diagonal distance between two pixels on a grid, where the 
 *  pixels are at opposite corners of a grid square.)
 * @param {Point} a                   The first endpoint of segment AB
 * @param {Point} b                   The second endpoint of segment AB
 * @param {Point} c                   The first endpoint of segment CD

 */
function nearOrient2d(a, b, c) {
  // p may be close enough to the line to be colinear
  // orient2d returns ~ double the area of the triangle formed by the three points.
  // in the base case, orient2d for a line 1,1 --> 1,0 and a point 1 - √2 / 2, 0 returns
  // area of √2 / 2. 
  // orient 2d for a line 1,2 --> 1,0 with point 1 - √2 / 2, 0 returns √2 / 2 * 2
  // I.e., a given point would be nearly colinear if orient2d <= √2 /2 * line distance
  // Can square both sides, to compare orient2d ^ 2 <= 0.5 * line distance ^2    


  const orientation = orient2dFast(a, b, c);
  const orientation2 = Math.pow(orientation, 2);
  
  const dx = b.x - a.x;
  const dy = b.y - a.y
  const dist2 = Math.pow(dx, 2) + Math.pow(dy, 2);
  
  const cutoff = 0.5 * dist2;
    
  if(orientation2 < cutoff) return 0; 
  return orientation;   
}

The idea here is that if your coordinates are within 1 pixel, you want them treated as equal---"rounding" them to the nearest pixel. Imagine a grid square, where 0,0 is a pixel and 0,1 is another pixel. 0,0.5 could be equivalent to either pixel, so a line that goes through 0,0.5 should "intersect" a line going through 0,1 or 0,0. Now, it might be sufficient to use 0.5, but the above actually does the math for when you have 0,0 and want, say, 0.5, 0.5 to be equivalent. It turns out the math for considering the diagonal case is fairly simple, as the √2 /2 ends up being squared to 0.5.

nearOrient2d relies on the fact that orient2d is actually returning double the area of a triangle connecting the three points. It figures out the cutoff for when that area is close enough to 0 (the collinear case) to be treated as 0 given that we want coordinates between pixels to be "rounded" to the nearest pixel. Then it has to round up the cutoff for the actual distance of the a,b ray.

[aaclayton]

Originally in GitLab by @dev7355608

If the ray start-/endpoints were integer, we wouldn't need those special intersection tests. But I'm not sure if the ray endpoints cannot be rounded for an important reason, so this may be irrelevant.

// Assume a, b, c, and d have less than 2^25 and greater than or equal to -2^25 integer coordinates.

// 100% accurate.
function lineSegmentIntersects(a, b, c, d) {
  const xab = (orient2dFast(a, b, c) * orient2dFast(a, b, d)) <= 0;
  const xcd = (orient2dFast(c, d, a) * orient2dFast(c, d, b)) <= 0;
  return xab && xcd;
}

// The intersection point may not be the most accurate, but whether we get an intersection is 100% accurate.
function lineLineIntersection(a, b, c, d) { /* ... */ }

// With a nonzero epsilon this may actually return false-positives; it is 100% accurate if epsilon is zero.
function lineSegmentIntersection(a, b, c, d, epsilon=1e-8) { /* ... */ }

// Here aInside/bInside-checks would be accurate if center.x/center.y are integers, epsilon is zero, and we would get passed radius squared instead of radius and radius squared is precise.
// Not sure about the accuracy of quadraticIntersection given integers.
function lineCircleIntersection(a, b, center, radius, epsilon=1e-8) { /* ... */ }

[aaclayton]

Originally in GitLab by @caewok

The ray start points should be the origin, which is usually (always?) integer coordinates. The ray end points will not always be integers and cannot always be integers.

However, for the initial ray in the non-limited-angle case, the ray is always due west, I believe. This due west ray should have integer coordinates at the endpoint. (I am not sure why it currently doesn't always, but seems like something is causing it to be slightly off.)

[aaclayton]

Originally in GitLab by @dev7355608

The origin is sometimes noninteger to break ties with walls. The clockwise polygon only is guaranteed to work correctly up to a scene size of (2^16-1)x(2^16-1) by design (because of PolygonVertex.key). So there are still 9 bit of the 25 bits unused, well 2 bits we need to reserve so that ray startpoint + maxR doesn't overflow, I think. That leaves us with 7 bits for sub-pixel accuracy. Do we need more accuracy than 2 decimal places?

[aaclayton]

I appreciate the careful thought going into this discussion, and I am interested in long-term opportunities to improve the algorithm. In the (very) short term for v9 stable release I'm going to look for something that is more of a workaround - we'll see if I can find a simple band-aid.

[aaclayton]

Originally in GitLab by @caewok

Makes sense, Andrew. Regarding non-integer coordinates, I don't think the user needs more than two decimals to place walls. Particularly if you are limiting scene size by design. Indeed, we are already assuming integer coordinates for walls. So that leaves intersections with:

1. Other walls. Probably fine to limit to 2 decimal places. The test would be to take a token origin at one edge of the canvas, and have some walls such that some of the vision stretches all the way across to the other canvas edge. So like, a wall reasonably close to the token, with vision going beyond the vertex of the wall all the way across the canvas to intersect somewhere on the canvas edge. That canvas edge intersection would necessarily be rounded to two decimals in this case, which will affect the angle of that vision polygon line between the wall edge and the canvas edge---is that variation from the true angle noticeable? (It would be noticeable if the angle of the line from token origin --> wall vertex looks different than wall vertex --> canvas edge intersection, then you know you need more than 2 decimal places.

2. Line-circle intersections. I am less certain here, but we are already approximating a circle with a polygon, so this could probably work as well. In testing, look for vision errors with large radii that might indicate more precision is required.

[aaclayton]

Too risky to try and deep-dive/address for the stable release today. We hope to address this during our V9 maintenance cycle.

[aaclayton]

Need a bit more time on this one.

[aaclayton]

Originally in GitLab by @Feu-Secret

marked this issue as related to #6339