基于正方形瓦片的三角形正方形的坐标系中的边框 [英] Bounding boxes in coordinate system based on right triangle quadrants of square tiles
问题描述
我正在为游戏创建一个2D，基于瓦片的地形系统。然而，我还使用游戏中的坐标，需要能够将边框映射到瓦片坐标中，并点击边界框所接触的每个瓦片（不用担心，有一个kd树和所有这些工作精细）。使用固定点真实世界坐标，我可以使每个瓦片计数为2 ^ n，只需右移位即可截断到瓦片坐标。我使用最小的x，y对和最大的x，y对来形成边框。我会分别叫他们 R0 和 R1 。
这里是一个边框，坐标为 R0：0.8，0.7 到 R1：2.2，1.7 映射到图块。
现在，这很简单。但是，我想将我的瓷砖分成4个三角形象限，这让我做出更多有趣的事情。由于每个瓦片变成4个三角形，所以我假设它们可以以某种方式被引用2位（不一定是我显示的）。我想使用尽可能少的位来标记这些三角形。我要将三角形标签放在其瓦片坐标旁边，以[XX]的形式放置一个点，其中XX是表示它是三角形的位。
然而，我这使用了几个问题。我需要能够将我的真实世界边界框坐标转换为三角坐标，但是看起来完全描述边界框太有意义了。三角形地面中的相同坐标可以描述将与不同三角形相撞的边界框。
我和左边一样有第一个边框： R0：0.8,0.7 到 R1：2.2，1.7
在右边，我有一个新的边框 R0：0.8，0.3 到 R1：2.2，1.7 ，所以左上角的y分量向上移动。它们都转换为相同的三角坐标，但如果在实际坐标中完成，则与不同的三角形相撞。但是，在三角坐标中不作区分，因此数据丢失，并产生一组不正确的冲突。
此外，同一个问题出现在同一个三角形中开始和结束的边界框。相同的三角坐标描述有时完全在该三角形中的边界框，有时不是。
必须有一种方法来映射这些，也许使用更多的位，以便所有三角形坐标在kd-tree范围查询中执行的比较可以匹配真实世界边界框如何与真实世界坐标中的相同三角形相撞。但是我很失落。
我下了兔子洞创建子砖，以分割每个平铺在4轴对齐的正方形，也分割每个因为我注意到许多情况是由于不知道我的坐标所映射到的每个三角形的哪一边而导致的。
但是当我遵循例外之后，更详细的规则，我最终最终将我的子瓷砖变成了同样的四角形象限设计，并结束了我开始的地方，除了更小的瓷砖。
我知道只是 可以实现这种压缩并进行适当的比较，但是每当我尝试时，我都会继续进行圈内操作。如何做？
[0，0，x1，y1] 至 [x1，y1 ，xmax，ymax]
但是，Alexey的解决方案将无法正常工作，即使我尝试补偿8维坐标。 / p>
如果坐标系与原来考虑的坐标系不一样，只要三角象限仍然可以显示相同的结果，那我就不在乎了。 / p>
看起来你需要的最小细分是每个方块变成八分圆。每个正方形应由两个对角线和水平和垂直中线分开。如果对于每个角落（不仅仅是左上角和右下角，而是四个），您可以存储哪个最后一个平铺的八分圆，您将有足够的信息来查找与所有原始三角形拼图（但不是所有八边形）发生碰撞。
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.
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).
这篇关于基于正方形瓦片的三角形正方形的坐标系中的边框的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
