5 ms·
Neo Geo Dev: Fixed Point Numbers
- vardump 2y agoOn the PC side, most developers stopped predominantly using fixed point for high performance code somewhere in the Pentium 1-3 era. For 486 class systems it was still pretty useful. Other than on retro systems, fixed point is still useful in smaller microcontrollers.
- pjmlp 2y agoMichael Abrash books contain information on these kinds of optimizations, which were exactly on this transition point, as timeframe.
- VyseofArcadia 2y agoA buddy of mine and I are working on a weekend project together. We recently realized that we don't need all that much precision, just a little, and switching from doubles or floats to 16-bit fixed point in our main data structure actually makes it small enough to fit an instance in a typical cache line (< 64 bytes). Completely unnecessary for our target platform but deeply satisfying.
- vardump 2y agoFor performance sensitive code memory bandwidth is very often the limiting factor, thus compressing values tends to make a lot of sense. The number of CPU cores is increasing much faster than memory bandwidth. So not necessarily completely unnecessary.
- VyseofArcadia 2y agoI expect it will have some effect given that we anticipate having ~1000 instances of that data structure alive at worst case, at least dozens at any given time.
- twoodfin 2y agoA few years before that era, I was having a lot of fun with https://en.wikipedia.org/wiki/Fractint https://en.wikipedia.org/wiki/Fractint
- mmaniac 2y agoThis sort of thing is ordinary for consoles without floating point numbers. It's easy to do in software with integers, but sometimes hardware acceleration will use it too. The SNES and GBA both supported affine transformations, where the elements of the multiplication matrix are fixed point numbers. The Playstation's geometry coprocessor (GTE) used fixed point matrices with quite low 16 bit precision. An emulator feature called PGXP is able to perform these calculations at higher precision.
- 01HNNWZ0MV43FF 2y agoAnd just to head off the discussion that happens every single thread: - Yes, the PS1 had "jittery" vertices because 16 bits is not enough precision - No, it was not because of using integers, you can use integers (AKA fixed-point) to do 3D just fine. If it had been 16.16 (32 bits total) it would probably look fine. - No, this isn't the cause of the texture warping, that's because unlike the N64 it only supported affine texture mapping, not perspective-correct texture mapping. The PS1 saw every 3D triangle as just a 2D triangle, and texture mapping in 2D differs from texture mapping in 3D - Yes, the texture warping is why many of the best-looking PS1 games were basically built on a grid or found other ways to use a large amount of small triangles instead of a small amount of large triangles.
- fidotron 2y agoIt's worth saying the original Playstation was entirely fixed point. You can go surprisingly far with it. https://en.wikipedia.org/wiki/Fixed-point_arithmetic#Software_application_examples https://en.wikipedia.org/wiki/Fixed-point_arithmetic#Softwar... I spent so much of the early stage of my career doing early mobile stuff I practically still think in fixed point, and always have to adjust to floats, for example, fixed point results can be compared exactly while with floats that is not a great idea. TeX uses fixed point entirely because it was reproducible across machines in an era where floating point was not.
- __s 2y agoI think fixed point would be used a lot more with proper support in programming languages
- fidotron 2y agoWhat you would need is the language to track the expected range of the numbers. You often end up with multiple different multiply/divide implementations (shifting amounts before/after) based on if you can safely guarantee you are within an expected range or not.
- SideQuark 2y agoI doubt it. It fails for far too many useful programming situations that it would cause more problems than floating point. Cannot use it efficiently for nearly anything: finance software, science software, engineering software, high quality graphics software... 3d software, pretty much anything that has any range needed or ability to lower errors while doing accumulation of information. This is exactly why floating point was invented and standardized - fixed point is a failure for most any program, and only can work with much effort only for certain situations. (I've written tons of fixed point code, numerical libraries across the spectrum from high performance, high quality, tunable quality, arbitrary precision libs, posits and unums, IEEE half-float software implementations, and more, so I do know what I'm talking about).
- 2y ago
- adancalderon 2y ago"If you wan't"
- capitainenemo 2y agoHedgewars uses fixed point due to inconsistencies in floating point implementations breaking deterministic lockstep. 0AD and Spring: RTS has similar issues although I think both use streflop now.
- nritchie 2y agoWhen I was a freshman (or so) in high-school, our computer lab had just graduated from a time-share terminal to the next-door university to the Apple II. A kid (Ray Tobey) in the next grade up started to code a project to submit to a Byte Magazine game contest. The due date came and went, but he carried on in every moment of his free time. Long story short, this game became SkyFox of which Woz said "consider this flight simulator as the finest Apple game ever done." From Ray, I learned the value of using continued fraction approximations to trig functions using only integer math. Later, this became useful when I had to implement image rotation in a scan generator for a scanning electron microscope.
- 01HNNWZ0MV43FF 2y agoOh cool! I think I played that on my family's Apple II. I think it was mislabeled as "Star Fox" and probably pirated. Sorry Ray...
- tralarpa 2y agoOn the Amiga and Atari, based on the Motorial 68000 like the NeoGeo, all 3D games used fixed point arithmetic. At that time, such games were written in assembler, and you had to be very careful to place the instructions for scaling and descaling in the right places, not only to get the final result in the right units (i.e., screen coordinates), but also in intermediate calculations to preserve precision.
- wk_end 2y agoI always felt when learning about this stuff that people - pedagogically - make fixed point seem more complicated than it is. Since this article is talking about more precisely positioning sprites in a 2D world, it could practically be a one-liner: "instead of tracking positions/velocities in pixels, track them in half pixels". Everything falls out of that intuition.
- city41 2y agoI'm the author of the blog post. I just used sprite positioning as a simple example. Things like collision detection and physics can't be done with half pixels.
- 01HNNWZ0MV43FF 2y agoThey can't?
- wk_end 2y agoNot sure what you mean - sure you can. Trying to read between the lines here, if your objection is to half-pixels because they’re not precise enough for (good) physics, then I apologize for being unclear - I mean half-pixels, or quarter-pixels, or eighth-pixels, or whatever. Another way of wording my comment is that I think it’s easier - especially for beginners - to think in terms of smaller units (represented as integers) than in terms of a new number format for representing fixed-size fractional parts of larger units. But the two concepts are ultimately the same.
- city41 2y agoBut that's basically what fixed point is, no? Half pixels is fixed point with a single bit for decimals. Quarter pixels is two bits, and so on. I think the disadvantage is you now have to think in a strange unit that isn't intuitive. For my game I tend to think in screen sizes for things. Thinking in screen size*factor would be harder I think. Fixed point is basically just doing that for me and hiding the details really. To be fair, rereading the post I realize I did make it sound like you would only need this for positioning sprites. I'll see about rewording it. Or maybe we're both talking about the same thing and you're taking a different approach. That is fair too.
- fizzynut 2y agoIs it possible to get rid of all the macros TO_FIXED, FROM_FIXED, mult, etc and replace them with a class with the correct constructors / operator overloads? Then your code doesn't ever need to be aware of the special fixed point math and horrible syntax everywhere and everything just works?
- msk-lywenn 2y agoYes it can. I’ve seen it done properly only once though. You still have to pay attention to avoid overflows
- deleted 2y ago[deleted]
- BearOso 2y agoMultiplying without having a larger intermediate is much more complex than the article states. You have to use the commutative property of multiplication and split the whole and decimal parts of each number out, otherwise you're stuck with single digit whole numbers or only multiplying fractions. So you'd take A.a * B.b and split it into A*B + A*b + a*B + a*b Or out = ((A >> fixedbits) * (B >> fixedbits) << fixedbits) + ((A >> fixedbits) * b) + ((B >> fixedbits) * a) + ((a * b) >> fixedbits); If you can get away with a little less precision and smaller whole numbers, you can avoid some of the multiplications by just doing this, which is quite common: (A.a >> (fixedbits / 2)) * (B.b >> (fixedbits / 2))
- Joker_vD 2y agoIt's such a shame that multiplication in C (or most other languages, really) doesn't have its natural type (intM, intN) -> int{M+N}. Instead, you have to recover the higher half of the result either by doing additional narrow multiplication yourself, or by using some compiler intrinsic.
- jnwatson 2y agoGcc can frequently tell what you're trying to accomplish and emit the correct instructions. Still I agree it would be ideal if this were explicit.
- jnwatson 2y agoFYI, the multiply assert isn't guaranteed to work and can be compiled out by a sufficiently smart compiler. Overflow of signed values is UB, the compiler can assume that UB is impossible, therefore the expression in the if resolves to false.
- throwawayk7h 2y agoFixed point should really be used way more often than it is. It's much safer, for one thing, and less mysterious. But because C lacks first-class support for fixed point, the whole world has become flopsy.
- djmips 2y agoNit to the author. Decimal point. Decimal digits. Actually binary point and binary digits.
- pjmlp 2y agoBesides all the given examples, this was also quite common in J2ME games, given the limitations of the environment, and hardware differences across phones.
- teo_zero 2y agoWhen I see a snippet like this int temp = a * b; ngassert( abs(temp) >= abs(a), "overflow!" ); I wonder what stops the compiler from optimizing away the assert, as it's clearly based on an undefined behavior.