EntityDistance Vs Sqr(a^2+b^2+C^2) speeds.
Blitz3D Forums/Blitz3D Programming/EntityDistance Vs Sqr(a^2+b^2+C^2) speeds.
| ||
| I've found on my system EntityDistance() is about 25% faster then using pythagoras' method. So start using entity distance in 3d instead! |
| ||
| I think most of us do use entitydistance. And ^ is dead slow... very very slow! use this equation instead! Sqr(xd*xd + yd*yd + zd*zd) |
| ||
| Good find! I just tested that myself as I was curious about what overhease ^2 would have. Thanks for the update. |
| ||
| Yeah... ^ supports 2^2.5 which is quite a slow calculation. x*x is less general, and is faster. |
| ||
| But if you read some book about game the distance =|x1-x2 | + |y1-y2| + |z1-z2| @+ Eole |
| ||
| which book? you never know, maybe pythagoras was wrong. BTW don't forget that you need two entities to use entitydistance. to calulate the distance of two points it would probably be faster to use the maths than to create two pivots and get entitydistance and then delete them again. |
| ||
| Why create two pivots every loop? Just make them global, and reuse them every time. |
| ||
| ok. but you still need to position them :P |
| ||
| But if you read some book about game It's not the same, it's called L1 distance (well some mathematicians call it that way). The "real" distance is really Sqr( (x1-x2)^2 +(y1-y2)^2 +(z1-z2)^2) and is called the L2 distance. In situations where accuracy matters less than speed, then the L1 distance is worth using. the distance =|x1-x2 | + |y1-y2| + |z1-z2| |
| ||
| for distance comparisons you can also optimize by staying in squared space: If Sqr(x*x+y*y+z*z)<d can be written: If (x*x+y*y+z*z)<(d*d) |
| ||
| the distance = |x1-x2 | + |y1-y2| + |z1-z2| ... It's not the same, it's called L1 distance (well some mathematicians call it that way). When I studied topology that measure of distance was also called the Taxicab Metric. It measures distance when you are confined to a grid. In a city suppose you need to travel to a place 3 blocks north and 4 blocks east. The distance is 3 + 4 = 7 if you travel along the streets. The distance is Sqr( 9 + 16 ) = 5 if you can fly. |
| ||
| Precisely. |
| ||
| SR, do you have a demo of any of this stuff you're doing? |
| ||
| For culling or other thing, you never need the real distance, so use it |
| ||
| So L1 distance would be 2 if you go from one corner of a square to the other, because it goes up one side, and across the other, and L2 distance would be 1.414213562 because it calculates the distance of the true shortest route, which is across the diagonal. There's several other ways to estimate distance as well. Isn't the L1 distance also known as the Manhattan distance? That would make sense because Manhattan is divided into a grid. I've never heard any distance measurement called the "Taxicab metric". |
| ||
| Isn't the L1 distance also known as the Manhattan distance? Yep, exactly. Reminds me my old math courses. Seems so far now... |
| ||
| Well, a link :-) http://www.flipcode.com/articles/article_fastdistance.shtml in this article there a Fast Approximate Distance Functions @+ eole |
| ||
| I'm pretty sure there's an article on gamasutra.com which offers several distance approximation functions as well, because there was an article in game developer magazine on that several years back. Personally, I think if you're optimizing your distance function then it's very likley that you're doing the wrong thing and could get much greater speed improvements by improving your algorithm. For example, in my Bunny Blast screensaver, I had a thousand land mines spread out over a feild, and a hundred bunnies. I needed to know if any bunnies approached any of the land mines too closely. My first attempt was the brute force method. But in Dark Basic, which is what I coded the screensaver in, doing 100,000 distance calculations per frame was just too slow. (In Blitz, it might have been more realistic since I didn't have much else going on in the world.) Now, I could have tried to optimize the distance function and simply used an approximation. But even then, who's to say it would have been fast enough? Dark Basic was an interpreted language after all. So I decided to alter my algorithm instead. There were many different kinds of algorithm I could have used to solve this problem, but the one _I_ chose for this scenario, was to place the landmines in a grid, with a maximum of one land mine per grid square, and centered in the grid square. Then it became a simple matter of creating an array which said if a land mine was in a particular square, and each frame I merely calculated which square the center of each bunny was in. Then I determined the distance to the land mine if there was a land mine in that square that was active. This drastically reduced the number of computations I needed to do. But there were other ways I could have solved the problem without restrting to having one land mine per grid square. I could have done awya with the grid entirely and used an octree, or simply made the grid system a little more sophisticated and had a linked list containing all land mines that had radii which fell within a particular grid square. |
| ||
| Not true sswift. There are many situations where you need to check the distances of many things, for example vertexes. |
| ||
| Yes, but even if you need to do that, then there are ways to approximate the result that you could use which would be far faster than calculating an exact result. For example, if you have a 64,000 vertices in a model, but you need to find the center of mass, you can create a 3d grid, and then weight each grid square according to how many vertices it contains. You can then calculate the median location of only to those grid squares which contain vertcies. Okay that might actually be slower than simply adding up the locations of all the vertices and then dividing by the number of vertices. But if you need to do that once a frame it implies the data will be changing, and then such an angorithm could have big benefits because you'd only need to add or subtract a few values from your total for cubes that change the number of vertices they contain. Anyhow, you get my point. There's rarely a situation you cannot optimize better by using a better algorithm than by writing faster code. |
| ||
| There is not small optimization. 3 or 4 optimizations put end to end can save 1 FPS. If all it is counted on the totality of a game one, this small thing arrives has a considerable profit of FPS. |
| ||
| French to English translation: "The little stuff can add up." I have to disagree. While optimizing this distance function might save you 5fps, optimizing the ALGORITHM will save you 10, and the optimization of the distance function then, since it will only be called 20 times instead of 20,000, will only give you a 0.005 fps increase on top of that. And while every little bit counts, you have to consider if it's worthwhile to even bother with. Of course I encourage anyone to use the SQUARED distance when possible, because that requires no extra effort. But you can't always use these weird alternative distance functions and get away with it. And anyhow, my point was that you should optimize the algorithm FIRST, not that you should not attempt to optimize the distance function. What I suggest is that if something is too slow, you examine the algorithm first, and see if you can divide the problem up into a set of smaller problems... gorup objects together for example, and then only work on those within a certain region. And THEN, once you're sure you've got a good algorithm, you can go for the smaller optimizations. But I can't recall a time when I have really needed to optimize a distance function in my code. I use the squared distance when I can out of habit, but I don't think I've had any situations where it actually provided a significant benefit. Btw, that's another trick you should be aware of. If you are merely COMPARING two distances then you can just delete the square root, and compare the two results, and you will get perfeclty accurate results with very little cost. |
| ||
| That said, there is considerable speed difference between ^ and *. |
| ||
| And while every little bit counts, you have to consider if it's worthwhile to even bother with. Glad to see this bunch of wiseness :)That's my whole phylosophy: don't count your time when it comes to optimize globally (algorithm-wise) or locally (like using faster distance computations) but only in the very few critical areas, like in a loop that gets executed thousands of times per frame. Never, ever lose your time (and your source readability and maintainability) doing local optimizations on a part of the code that has no significant impact on the speed (and that's 95% of the code). And also as stated by Sswift, optimize globally first, and start to do local optimizations as the very last stage, once everything is stable and well architectured. |
| ||
| Very good advices here. Worth reading. This community is a gold mine. Thanks to all, Sergio. |
| ||
| How about using three if statements. Surely that must be super quick? check the x then the y then the z? |
| ||
| Hem, probably not. 'If' statements are usually the slowest part of the code, because it gets compiled to conditional jumps. And jumps are slow because it empties the CPU pipeline, ie it discards the instructions that were being executed ahead of time (though branching prediciton tempers a bit this fact). |
   |