Find regular grid cells intersecting arbitrary shaped quadrilateral

Question

I need to find all indexes [x, y] for grid cells intersecting an arbitray shaped quadrilateral, defined by its corner coordinates;

• grid cells are tiles with 128 x 128 px

• grid cells have an integer index between [-nx, -ny] and [nx, ny]
  (max extend is a square with (2nx * 128) * (2ny * 128) px)

• quadrilateral is defined by corner points, with coordinates (qx, qy) in pixel space given as (tl, tr, br, bl)

• This is integrated in a three.js scene:
  • corner points/coordinates are raycasted from camera on a base THREE.PlaneBufferGeometry

How to get all intersecting tiles in a computationally efficient manner in JavaScript?

For now I compute the perimeter tiles by traversing each quadrilateral edge using mx + b with the tile dimension (128px) as step; from there, I just add interior tile indexes row for row. But that´s somewhat clumsy, which might or might not be a coding skill issue. I am about to try using the THREE.Raycaster to get the perimeter tile indexes, but not sure how, yet.

I am seeking a better solution algorithm-wise; basic formulae, pseudo code, ideas, or definite solutions.

Answer 1

To effectively find grid cells intersected by quad edges, you can use Woo and Amanatides grid traversal algorithm: article "Fast Voxel Traversal Algorithm...".
Practical implementation is in grid traversal section here
Example:

For inner cells of convex quads: during edge traversal remember the leftmost cell in row for "right" edges, the rightmost cell for "left" edges, and fill horizontal gap between them.