0

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.

halfer
  • 19,824
  • 17
  • 99
  • 186
t.ry
  • 97
  • 5
  • Consider https://stackoverflow.com/questions/25016603/ also check https://stackoverflow.com/questions/22634006/ – MBo Sep 18 '18 at 10:48
  • @Mbo thx a lot! ...I just had a quick read, couldn't really grasp it fully yet: first thing I thought was if I can/should move from pixel space to index space (getting the tile index intersecting the corner points) and implement a direct lookup. or is that not really relevant here? – t.ry Sep 18 '18 at 14:02
  • Work both in pixel coordinates and in `[column, row]` indexed cells - indexes of the next cell differ from current by one – MBo Sep 18 '18 at 14:12
  • @MBo indeed, the 'normalized' difference was what I was aiming at. thx again, I'll upvote both your linked answers; if you want, add one here, it seems to be the way to go, or I'll post my solution if I implemented one – t.ry Sep 18 '18 at 14:21

1 Answers1

2

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:

enter image description here

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.

MBo
  • 77,366
  • 5
  • 53
  • 86