![]() GATE CS Original Papers and Official Keys.DevOps Engineering - Planning to Production.Python Backend Development with Django(Live).Android App Development with Kotlin(Live).Full Stack Development with React & Node JS(Live).Java Programming - Beginner to Advanced.Data Structure & Algorithm-Self Paced(C++/JAVA).Data Structures & Algorithms in JavaScript.Data Structure & Algorithm Classes (Live). ![]() That let me make an image that kept the distance constraints even when it was tiled. Subtracting circle radii from the distance between points let me get toroidal distance between circles and make sure I didn’t place them too closely to each other. The calculations above gave me the basic tool needed to be able to calculate distances between points. I needed to place a few circles on a texture such that the circles weren’t too close to each other, even when the texture was tiled. I hit this problem trying to make a tileable texture. Here is some C++ to show you how it would work in 2D.įloat ToroidalDistance (float x1, float y1, float x2, float y2) It’s now linear in the number of dimensions:, instead of. The computational complexity is a lot better. More importantly, it lets you efficiently calculate the distance between the two points in toroidal space (doughnut space!) This lets you minimize the distance without having to explicitly figure out which combination makes the point closest. ![]() The distance of that other way is one minus whatever distance you just calculated since the distance from one point to itself is 1!ĭo that for each axis and use those 1d distances in the distance formula to get the actual distance. The intuition here is that if you are in a 1d repeating space, if going from A to B is more than half the distance, it means that you went the wrong way, and that going the other way is shorter. If that distance is greater than 0.5, the real distance for that axis is 1-distance. Still working on each axis individually, you can calculate the absoluate value of the 1D distance between the two points on that axis. This gives you the closest point which you can then plug into the distance formula to get the distance between the points in this wrap around space. You’d repeat for the y axis to get the y axis location to use (and would repeat for any further axes for higher dimensions). Whichever x axis value of the red dot gives you the minimal x axis 1D distance is the x axis location to use. On the x axis you’d find if the x axis distance between the red and green point is minimal when you subtract 1 from the red dot’s x axis position, leave it alone, or add 1. So, the better way is to minimize each axis individually. Looking at the distance formula we can see that if we minimize each axis individually, that we will also end up with the minimal distance overall. All possible combinations of the x and y axis having -1, +0 or +1 added to them are valid locations of the red dot. If you look at the image with 9 copies of the red dot, you can see that they are just the 9 possible combinations of having -1, +0, +1 on each axis added to the red dot’s coordinates. Let’s say that our universe (image) is 1 unit by 1 unit big (aka we are working in texture UVs). Luckily there’s a better way to approach this. In 3D, it requires 27 distance calculations to find the shortest point, and 81 distance calculations in 4D! Going up in dimensions makes the problem even worse. ![]() You can work with squared distances instead of regular distances to avoid a square root on each of these distance calculations, but that’s still a bit of calculation to do. Something not so desirable about this is that it takes 9 distance calculations to find the minimum distance. You’d calculate the distance from the green point to each of the 9 red points, and whatever distance was smallest would be the answer. One way to do this would be to pick one of the points (I’m picking red in this case) and clone it 8 times to surround the cell like the below. Let’s imagine the situation below where we are trying to find the distance between the red point and the green point: How would you calculate the distance between two points in a universe like this? If you go far enough “left” you end up where you previously considered “right”. If you go “down” you end up where you previously considered “up”. If you imagine yourself on the surface of a doughnut, it would behave exactly this way. It’s actually an impossible object, a “flat torus”, so not exactly a doughnut, but whatever. This universe is actually shaped like a toroid, also known as a doughnut. Let’s say you are trying to find the distance between two points in 2D, but that these points are in a universe that “wraps around” like old video games – leaving the screen on the right, left, top or bottom side makes you re-appear on the opposite edge. ![]()
0 Comments
Leave a Reply. |