1

I'm about to create a terrain for a mobile game which allows a huge terrain which is mostly limited by the available hardisk space.

This requires to keep the floating points limited to a "after-point-precision" of 2 numbers. What is a good approach to keep it at the precision of 2 numbers after the point?

Remember: I'm running on a mobile device, so the method should be fast and easy to use and should be applicable to any arithmetic which is needed for games.

More information

I'm not talking about space( i know how much space a float takes guys, really ), i'm talking about the issue that i loose precision when my floating point is going to have to many numbers after the decimal point.

Using a int would cause that i've to convert the int into a float each frame. I don't know how fast the conversion is but this seems to cost a lot of performance when doing it for a lot of objects. ( Remeber i'm on a mobile device ).

Of course i'm also not talking about the terrain, i'm talking about objects in the terrain! The terrain is a specialized system which actually can hold a terrain size which extends the limits of the floats a lot ( It's even possible to save north america in this system when you have enough disk space, but actually the limits are set to -99km to +99km ).

Edit 2

As usual in games the movement is timebased, means i need to multiply the speed of the object with a modifier given to me by unity, this corrupts my numbers which are limited to 2 numbers after the decimal point.

Community
  • 1
  • 1
Felix K.
  • 6,201
  • 2
  • 38
  • 71
  • 9
    Will an `int` not suffice and just have it represent the smallest possible accuracy you want? As in, 2 decimal places. Floating point issues then simply disappear. 1.02 then becomes 102 in `int` land. – Adam Houldsworth Mar 20 '12 at 13:43
  • technically, floats have a larger precision then that, do you want to limit the precision? Please re-write your question to be more precise, add what you have tried and where you have failed. –  Mar 20 '12 at 13:44
  • As an add-on to the comment above, "after-point-precision of 2 numbers" seems to imply that you need precision to 1/100th of some unit. If you multiply all of your unit values by 100, then you have integer precision values, and you won't have to use floating points. – qxn Mar 20 '12 at 13:47
  • @AdamHouldsworth That's true, but then i have to convert the int's in any place into a float before i can use it in Unity3D. – Felix K. Mar 20 '12 at 13:48
  • 1
    @Adam: Do you not end up with a heap of special handling for multiplication & division? i.e. `1.00 * 1.00 = 1.00` ; `100 * 100 = 10000` – Binary Worrier Mar 20 '12 at 13:49
  • 2
    First off, floats are four bytes no matter what number they contain. Second, if you can do the storage in integers, do it. Third, if you want to represent a large terrain in a small space then you're going to have to take advantage of some kind of compression technology. Is the terrain immutable? If so then you might be able to get good compression out of an immutable quadtree; that's a pretty standard technique for games with large terrain resources. – Eric Lippert Mar 20 '12 at 13:49
  • I have no idea about the math, I was just side stepping the issue by suggesting that you try to fit it all into integral numbers, not floating point numbers. If accuracy deeper than defined is needed, then yes I suppose you would get headaches. – Adam Houldsworth Mar 20 '12 at 13:51
  • @BinaryWorrier: Do you often *multiply* the height of a mountain by the height of another mountain? – Eric Lippert Mar 20 '12 at 13:51
  • @Shingetsu I just want to avoid that i got numbers like this `1.2302`. Because when the number is greater like `25382.27512` it's not longer precise and i don't need any numbers after `25382.27` – Felix K. Mar 20 '12 at 13:51
  • @EricLippert interesting approach. I see your point here, you should write it as an answer. –  Mar 20 '12 at 13:51
  • @FelixK. if you want to limit the precision, you can either increment by 0.01 when you do your loop, or pass it through a rounding function: (that is to say check if the 3d number after point is 5+ or less and manually assign the second number after point) –  Mar 20 '12 at 13:53
  • @Eric: I don't often juggle mountain heights no :), but I can imagine needing to divide a distance by a length. – Binary Worrier Mar 20 '12 at 13:55
  • @EricLippert I know, that's not the point. I gonna update my answer, otherwise the comments here are going to explode. – Felix K. Mar 20 '12 at 13:55
  • @felixk. How do you create the terrain? Heighdata in a file then looping through it? Predefined vectors? –  Mar 20 '12 at 14:00
  • You dont have to convert them every frame. One of thr basis of algorithms is memorization. You can either store the results directly, or store in a dictionary by custom object (operand 1,2 and action) –  Mar 20 '12 at 14:03
  • @Shingetsu I need to convert the objects each frame, because they are moving around. ( Not talking about the terrain, talking about objects which move on the terrain ). – Felix K. Mar 20 '12 at 14:08
  • When the objects move, set minimal movement value to 0.01 and increase it by 0.01 for larger output. –  Mar 20 '12 at 14:09
  • During multiplication, round it down. Something like: `float result = ...; float modulus = result%0.01; if(modulus>0.05) { result-=modulus; result+= 0.01;} else result-=modulus;` –  Mar 20 '12 at 14:18
  • if this answer is good enough, please say so so I post it as an answer. –  Mar 20 '12 at 14:19
  • @Shingetsu That's a good approach, would be interesting if there are any faster possibilities. Looking at the disassembly it results i a lot of operations. – Felix K. Mar 20 '12 at 14:31
  • @FelixK. technically, it's O(n). you have your result, then you get the modulus (a division, O(1)), then a conditional statement comparing to currently static values (so also O(1)), then 2 small actions if it is true and one small action if it's false. You would only be doing this every time an object moved, so it would get more and more heavy with more moving objects, so the question is, do you plan to have an avalanche with 500 particles per meter falling? If yes, let's try to find another way, if no, this should work fine. –  Mar 20 '12 at 14:35
  • @BinaryWorrier: If you are dividing distances by distances then that is invariant under scale changes. 1.2 / 0.3 is the same as 12000.0 / 3000.0. – Eric Lippert Mar 20 '12 at 14:39
  • 2
    OK, so let's take a step back here. *Why* do you want to limit precision? Why are you making your logic *less accurate* and *less precise*, and *slower* when it could be *more accurate*, *more precise* and *faster*? – Eric Lippert Mar 20 '12 at 14:40
  • @Shingetsu Not particles, but a lot of characters and deers. This could reach 500 in numbers with ease. ( I'm disabling far objects, but if you have a herd of 200 deers and some characters it's enough. – Felix K. Mar 20 '12 at 14:42
  • @EricLippert I think OP is trying to avoid floating point inexactness by rounding it: http://answers.unity3d.com/questions/50187/floating-point-accuracy-weirdness.html –  Mar 20 '12 at 14:44
  • @FelixK. with my method 200 total is nothing. It would take a few thousand visible moving objects to even slightly slow the process down due to the low cpu second cost of the technique. Try to implement it and see if it works. –  Mar 20 '12 at 14:45
  • @FelixK. you can discuss further of my answer on my answer! (I posted it now, this should limit comment amount in the question) –  Mar 20 '12 at 14:45
  • @EricLippert According to msdn, floating point precision is limited to 7 digits. Actually, as written above, i limiting the range of my terrain to -99km to +99km. Means: (+/-)99,999.99 Meters, which are exactly 7 digits. I don't need sizes below 1cm so i can ignore them. But when my number has a larger precision than 2 digits after the decimal point i loose precision. – Felix K. Mar 20 '12 at 14:46
  • 4
    @FelixK.: You need to represent positions to within a centimeter over a range of 200 km. Let's bump that up to millimeter precision just for the heck of it. There are only two hundred million distinct points. Assign each of them an integer. A 32 bit integer can hold numbers between +/- two billion. Now *all* your calculations will be rounded to the nearest millimeter. – Eric Lippert Mar 20 '12 at 14:53
  • 2
    @EricLippert I have a feeling OP wants to multiply movement (force) by a float (time), so using floats make sense in this case as the result of such an operation is a float. His main problem is that he doesn't want floating point imprecision and wants to round the floats to a 0.01 precision point. I think my solution is good enough in this case. Representing all of the positions is also an interesting answer, but it won't help in getting movement. –  Mar 20 '12 at 15:01
  • @Shingetsu: OK, then convert the positions to doubles, do all the physics in doubles, and then convert the result back to int once the physics are done. That way the physics are done with the largest possible precision, but the positions are always discrete. – Eric Lippert Mar 20 '12 at 15:02
  • 1
    @EricLippert converting involves much more time then my method does. Unless you mean casting, but casting directly involves more imprecision then the original plan. So I think running a modulus based calculation will wind up being more effective. –  Mar 20 '12 at 15:05
  • @EricLippert I'm on a mobile device. Double precision calculations in a 3D-Game could slow down the app a lot on a mobile device. That's the reason i'm asking this question and looking for the best solution for it. But thank you for your help anyway. – Felix K. Mar 20 '12 at 15:09
  • 1
    @FelixK.: Doubles are usually *faster* than singles, even on mobile devices. I believe Windows Phone 7 hardware is required to do double arithmetic in hardware. What device are you using where doubles are slower than singles? – Eric Lippert Mar 20 '12 at 15:46
  • @EricLippert I'm using iOS-Devices ( iPhone4/iPad and greater ) and the performance of floats seems to be much faster. ( http://stackoverflow.com/questions/1622729/double-vs-float-on-the-iphone ) – Felix K. Mar 20 '12 at 15:56
  • 2
    @FelixK.: Well, I learn something new every day. And that was my one thing for today, so time to go home I guess. :-) – Eric Lippert Mar 20 '12 at 16:13

2 Answers2

1

An interesting way would be to implement this into the movement function:

float result = //multiply force by time
float modulus = result%0.01f;
result -= modulus; //you will do this in any case
if(modulus>=0.005f) {/*round up. if you want it to only round down, remove
  the next 2 lines, if you want it to only round up, remove
  the conditional statement*/
  result+=0.01f; }

I can't think about how to optimize it further, I removed the else statement and have it take away the modulus without condition as it will be done anyway.

  • Made some test's, the performance seems to be ok as long not to many objects are moved. – Felix K. Mar 20 '12 at 15:44
  • Which is what I've been saying ^^. Mathematical operations actually take up very little performance, and, at the base, this is just 2-3 math operations for every object. A possible improvement would be to declare result and modulus OUTSIDE the loop to prevent deallocating-reallocating memory in each iteration (like: `float result=0, modulus=0; //begin the loop where you just use them rather then declare them again and again` –  Mar 20 '12 at 15:54
  • 1
    Note that the rounding logic has an away-from-zero bias because it doesn't employ so-called "banker's rounding". – phoog Mar 20 '12 at 16:39
  • a) Use binary numbers as smallest value: Instead of using 0.01f. use 0.0078125 if you do not mind. This is faster than a division with a filled mantissa because it is equivalent to a simple shift operation. b) Instead using the division use inverse multiplication because multiplication is faster than division. Ok, normally compilers get it, but the principle stays. c) At all it is following operations: Multiply with 128, floor(A fast replacement of floor is adding with 16777216 and subtracting 16777216 again), and multiply with 1/128. – Thorsten S. Mar 21 '12 at 22:44
  • @ThorstenS. a. technically, I'd have to implement a cast. casting also takes time. So no big difference (might even be slower, this is C# remember?) b. This is .NET, JIC compiler takes care of it. c. This makes code unreadable. People generally go towards higher level languages, even though it takes away effectiveness, in order to have code more readable and easier to manage. If OP was looking towards squeezing every bit of performance he would be writing in C or assembly, and using code obfuscation (we know it speeds things up) –  Mar 22 '12 at 00:31
0

Huh, doesn't matter what precision you choose to operate at they still take up the same amount of space. Single or double would make a difference, but the real question you should ask is do you need floating points at all. If you can fit the numbers in an int, do that.

Tony Hopkinson
  • 20,172
  • 3
  • 31
  • 39
  • OP wants to use it in Unity3D. What I don't see is why he has a problem with float vars. –  Mar 20 '12 at 13:50
  • I'm not interested in saving space. I like to keep the "after-point-precision" in a specific range to avoid precision issues with floats. – Felix K. Mar 20 '12 at 13:53
  • You can have it processed in the loop (0.01 increments (O(1)), automatically round them down (O(n)) or just ignore numbers past 0.01 (O(1)) –  Mar 20 '12 at 13:55
  • 1
    Avoiding "precision" issues with floats is an exercise in futility, if it's a concern avoid floats. By the time you've ironed out all the potential for precision errors you'll have invented a badly designed inefficient and unmaintainable fixed point type anyway... – Tony Hopkinson Mar 20 '12 at 16:30