Imagine you are on a hardware that is 8bits like the nes or the game boy, NO mul no div, only add and shift. Given a rectangle or integer size nk*mk, where k is the size of the underlying grid, and P a point inside the rectagle with a direction D.

How do i figure out cheaply :

Which side of the rectangle the line L starting from P in direction D will hit enter image description here

So far I figure out we can cut the rectangle in quadrant using the coordinate of P. Solving the simple case of a square of size k, it simply hit which side the direction has the biggest component. The reason is we can draw the diagonal from P to the given corner of the quadrant, and which side of the diagonal it point inside give the rectangle side, so it's the slope, if the slope is smaller than the diagonal, it hit the horizontal side else it's the top side

Now going back to the rectangle, the slope varies according to the length of the biggest side. Abusing symmetry, we will consider positive direction, and lay the rectangle on his biggest side, such as the width is always the biggest component. IF D biggest component different than the symmetric laid rectangle, then it's the top side of the symmetry, SO the question is, is there a cheap test that guess the side who will be hit,for when the component, of the direction and the rectangle, are both relative to the same axis? Then once we figure out which side, how to efficiently compute the coordinate in which we hit?

  • \$\begingroup\$ Just to clarify - is the rectangle axis aligned? \$\endgroup\$
    – Pikalek
    Feb 1, 2022 at 15:14
  • \$\begingroup\$ Yes! any form of simplification is welcome, such as defining k in convenient number that simplify, as long as we can do the side selection. The idea is to have as many early exit before "complex math" as possible, the goal is to try and make a mix of grid raycaster like wolfeinstein and sector based portal renderer like the BUILD engine of duke nukem. I figure out there is a "cone of ambiguity" that range from the 45° slope angle to "k"/ "max cell size" (max tan angle), no idea where that leads to though. \$\endgroup\$
    – user29244
    Feb 1, 2022 at 19:31


You must log in to answer this question.

Browse other questions tagged .