Bounding boxes in coordinate system based on right

Question

I'm creating a 2D, tile-based system of terrain for a game. However, I'm also using in-game coordinates that need to be able to map a bounding box into the "tile coordinates" and hit each tile the bounding box touches (don't worry, have a kd-tree and all that working fine). Using fixed point "real world" coordinates, I can make each tile count as 2^n of them and simply right shift the bits off to truncate down to tile coordinates. I form a bounding box using the smallest x,y pair and the largest x,y pair. I'll call them R0 and R1 respectively.

Here's a bounding box with coordinates R0: 0.8, 0.7 to R1: 2.2, 1.7 being mapped to the tiles.

Now, that's simple enough. However, I want to split my tiles into 4 triangular quadrants, which lets me make more interesting stuff. Since each tile becomes 4 triangles, I assumed that they can be referenced by 2 bits in some manner (not necessarily the one I show). I want to use as few bits as possible to "label" these triangles. I'm going to put my triangle label for a point right next to its tile coordinates, in the form of [XX] with XX being the bits indicating which triangle it is.

However, I've ran into several problems using this. I need to be able to convert my real world bounding box coordinates into "triangle coordinates", but it appears that it is too lossy to fully describe the bounding box. The same coordinates in triangle land can describe bounding boxes that would collide with different triangles.

I have the same first bounding box as before on the left: R0: 0.8, 0.7 to R1: 2.2, 1.7
On the right, I have a new bounding box R0: 0.8, 0.3 to R1: 2.2, 1.7, so the y component of the top left corner is moved up. They both translate to the same triangle coordinates, but collide with different triangles if it is done in real world coordinates. No distinction is made in triangle coordinates, though, so data is lost and an incorrect set of collisions is generated.

Further, the same problem occurs with bounding boxes that start and end in the same triangle. The same triangle coordinates describe bounding boxes that sometimes are totally in that triangle, and sometimes not.

There has got to be a way to map these, maybe using more bits, so that all triangle coordinate comparisons performed in the kd-tree range query can match how the real world bounding box would collide with those same triangles in real world coordinates. But I'm at a loss.

I went down the rabbit hole creating "sub-tiles" to split each tile in 4 axis-aligned squares, which also split each quadrant tile in 2 along the axis it crosses, since I noticed many cases were caused by not knowing which side of each triangle my coordinates got mapped to.

But as I followed exception after exception to ever more detailed rules, I eventually ended up turning my sub-tiles into the same 4 triangular quadrant design and ending up where I began, except with smaller tiles.

I know it just has to be possible to achieve this "compression" and have proper comparisons, but I keep going in circles whenever I try. How can it be done??

edit:
Alexey proposed a solution that would allow me to describe a bounding box, but it is incompatible with using a kd-tree to find bounding box overlaps. With my kd-tree (storing the top left and bottom right coords) range query and a search region [x0, y0], [x1, y1] I do a range query over:

[0, 0, x1, y1] to [x1, y1, xmax, ymax]

But Alexey's solution won't work with this, even if I attempt to compensate for the 8 dimensional coordinates.

I don't really mind if a coordinate system is sorta different than what I was originally considering, as long as it can still manifest the same results with the triangular quadrants.

Answer 1

Seems the minimal subdivision you need is that of each square into octants. Each square should be divided by two diagonals AND the horizontal and vertical midlines. If for each corner of the box (not just for the upper left and lower right, but for all four) you store in which octant of which tile it ended up, you'll have enough information to find collisions with all your original triangular tiles (but not with all octants).