vtkFastNumericConversion Class Reference
#include <vtkFastNumericConversion.h>
Detailed Description
Enables fast conversion of floating point to fixed point.vtkFastNumericConversion uses a portable (assuming IEEE format) method for converting single and double precision floating point values to a fixed point representation. This allows fast integer floor operations on platforms, such as Intel X86, in which CPU floating point conversion algorithms are very slow. It is based on the techniques described in Chris Hecker's article, "Let's Get to the (Floating) Point", in Game Developer Magazine, Feb/Mar 1996, and the techniques described in Michael Herf's website, http://www.stereopsis.com/FPU.html. The Hecker article can be found at http://www.d6.com/users/checker/pdfs/gdmfp.pdf. Unfortunately, each of these techniques is incomplete, and doesn't convert properly, in a way that depends on how many bits are reserved for fixed point fractional use, due to failing to properly account for the default round-towards-even rounding mode of the X86. Thus, my implementation incorporates some rounding correction that undoes the rounding that the FPU performs during denormalization of the floating point value. Note that the rounding affect I'm talking about here is not the effect on the fistp instruction, but rather the effect that occurs during the denormalization of a value that occurs when adding it to a much larger value. The bits must be shifted to the right, and when a "1" bit falls off the edge, the rounding mode determines what happens next, in order to avoid completely "losing" the 1-bit. Furthermore, my implementation works on Linux, where the default precision mode is 64-bit extended precision.
This class is contributed to VTK by Chris Volpe of Applied Research Associates, Inc. (My employer requires me to say that -- CRV)
This code assumes that the FPU is in round-to-nearest mode. It assumes, on Linux, that the default extended precision mode is in effect, and it assumes, on Windows, that the default double precision mode is in effect.
Definition at line 77 of file vtkFastNumericConversion.h.
Public Types | |
| typedef vtkObject | Superclass |
Public Member Functions | |
| virtual const char * | GetClassName () |
| virtual int | IsA (const char *type) |
| void | PrintSelf (ostream &os, vtkIndent indent) |
| int | TestQuickFloor (double val) |
| int | TestSafeFloor (double val) |
| int | TestRound (double val) |
| int | TestConvertFixedPointIntPart (double val) |
| int | TestConvertFixedPointFracPart (double val) |
| void | PerformanceTests (void) |
| void | SetReservedFracBits (int bits) |
| int | ConvertFixedPoint (const double &val, int &fracPart) |
Static Public Member Functions | |
| static vtkFastNumericConversion * | New () |
| static int | IsTypeOf (const char *type) |
| static vtkFastNumericConversion * | SafeDownCast (vtkObject *o) |
| static double | RoundingTieBreaker () |
| static int | QuickFloor (const double &val) |
| static int | SafeFloor (const double &val) |
| static int | Round (const double &val) |
Protected Types | |
| enum | { exponent_pos = 1, mantissa_pos = 0 } |
Protected Member Functions | |
| vtkFastNumericConversion () | |
| ~vtkFastNumericConversion () | |
| void | InternalRebuild (void) |
Static Protected Member Functions | |
| static double | BorrowBit () |
| static double | QuickRoundAdjust () |
| static double | SafeRoundAdjust () |
| static int | SafeFinalShift () |
| static double | two30 () |
| static double | two52 () |
| static double | two51 () |
| static double | two63 () |
| static double | two62 () |
| static double | QuickFloorDenormalizer () |
| static double | SafeFloorDenormalizer () |
| static double | QuickExtPrecTempDenormalizer () |
| static double | SafeExtPrecTempDenormalizer () |
Member Typedef Documentation
Member Enumeration Documentation
anonymous enum [protected] |
Constructor & Destructor Documentation
| vtkFastNumericConversion::vtkFastNumericConversion | ( | ) | [inline, protected] |
Definition at line 441 of file vtkFastNumericConversion.h.
| vtkFastNumericConversion::~vtkFastNumericConversion | ( | ) | [inline, protected] |
Definition at line 459 of file vtkFastNumericConversion.h.
Member Function Documentation
| static vtkFastNumericConversion* vtkFastNumericConversion::New | ( | ) | [static] |
Create an object with Debug turned off, modified time initialized to zero, and reference counting on.
Reimplemented from vtkObject.
| virtual const char* vtkFastNumericConversion::GetClassName | ( | ) | [virtual] |
Reimplemented from vtkObject.
| static int vtkFastNumericConversion::IsTypeOf | ( | const char * | name | ) | [static] |
Return 1 if this class type is the same type of (or a subclass of) the named class. Returns 0 otherwise. This method works in combination with vtkTypeRevisionMacro found in vtkSetGet.h.
Reimplemented from vtkObject.
| virtual int vtkFastNumericConversion::IsA | ( | const char * | name | ) | [virtual] |
Return 1 if this class is the same type of (or a subclass of) the named class. Returns 0 otherwise. This method works in combination with vtkTypeRevisionMacro found in vtkSetGet.h.
Reimplemented from vtkObject.
| static vtkFastNumericConversion* vtkFastNumericConversion::SafeDownCast | ( | vtkObject * | o | ) | [static] |
Reimplemented from vtkObject.
| void vtkFastNumericConversion::PrintSelf | ( | ostream & | os, | |
| vtkIndent | indent | |||
| ) | [virtual] |
| int vtkFastNumericConversion::TestQuickFloor | ( | double | val | ) |
Wrappable method for script-testing of correct cross-platform functionality
| int vtkFastNumericConversion::TestSafeFloor | ( | double | val | ) |
Wrappable method for script-testing of correct cross-platform functionality
| int vtkFastNumericConversion::TestRound | ( | double | val | ) |
Wrappable method for script-testing of correct cross-platform functionality
| int vtkFastNumericConversion::TestConvertFixedPointIntPart | ( | double | val | ) |
Wrappable method for script-testing of correct cross-platform functionality
| int vtkFastNumericConversion::TestConvertFixedPointFracPart | ( | double | val | ) |
Wrappable method for script-testing of correct cross-platform functionality
| static double vtkFastNumericConversion::BorrowBit | ( | ) | [inline, static, protected] |
Internal use: multiply the denormalizer value by 1.5 to ensure that it has a "1" bit, other than the implicit initial "1" bit, from which to borrow when adding (flooring) a negative number, so that we don't borrow from the implicit "1" bit, which would cause partial re-normalization, resulting in a shift of our integer bits.
Definition at line 111 of file vtkFastNumericConversion.h.
| static double vtkFastNumericConversion::two30 | ( | ) | [inline, static, protected] |
Represent 2^30 as a double precision float. Use as a stepping stone for computing 2^52 as a double, since we can't represent 2^52 as an int before converting to double.
Definition at line 117 of file vtkFastNumericConversion.h.
| static double vtkFastNumericConversion::two52 | ( | ) | [inline, static, protected] |
Represent 2^52 as a double precision float. This value is significant because doubles have 52 bits of precision in the mantissa
Definition at line 126 of file vtkFastNumericConversion.h.
| static double vtkFastNumericConversion::two51 | ( | ) | [inline, static, protected] |
Represent 2^51 as a double precision float. This value is significant because doubles have 52 (explicit) bits of precision in the mantissa, but we're going to pretend we only have 51 to play with when using safe floor, since the default round-to-even on an X86 mucks with the LSB during the denormalizing shift.
Definition at line 138 of file vtkFastNumericConversion.h.
| static double vtkFastNumericConversion::two63 | ( | ) | [inline, static, protected] |
Represent 2^63 as a double precision float. We need this value to shift unwanted fractional bits off the end of an extended precision value
Definition at line 148 of file vtkFastNumericConversion.h.
| static double vtkFastNumericConversion::two62 | ( | ) | [inline, static, protected] |
Represent 2^62 as a double precision float. We need this value to shift unwanted fractional bits off the end of an extended precision value. Use when we're doing a SafeFloor.
Definition at line 158 of file vtkFastNumericConversion.h.
| static double vtkFastNumericConversion::RoundingTieBreaker | ( | ) | [inline, static] |
Small amount to use as a rounding tie-breaker to prevent round-to-nearest-and-even mode from flooring-down odd numbered integers. But number to nudge by depends on number of bits mantissa in our floating point representation minus number of mantissa bits in the range of signed ints we need to handle. In order to ensure that flooring-down doesn't happen even for very large odd-integer values, the number of bits used to represent the tie-breaker (i.e. to the right of the binary-point), plus the number of bits needed to represent the integer (to the left of the binary point), can not exceeds the number of bits in the current precision mode. Thus, in selecting the tie-breaker value, we select the largest number of bits to the right of the binary point as possible while still maintining that inequality. Thus, extended precision mode allows a larger number of bits to the right of the binary point. This, in turn, implies a smaller value of the tie-breaker. And a smaller tie-breaker will impose a tighter window on the range of values that are erroneously rounded-up by a floor operation. Under double precision, a QuickFloor of 0.9999998 (six 9's and an 8) correctly yields 0. A value must be very close to 1.0, in fact, at least as close as 0.9999999 (seven 9's)in order for the tie-breaker to bump it up to 1. Under extended precision, an even smaller tie-breaker can be used. In this mode, a QuickFloor of 0.9999999999 (ten 9's) correctly yields 0. A QuickFloor of 0.99999999999 (eleven 9's) gets rounded up to 1. Since these spurious round-ups occur only when the given value is virtually indistinguishable from the next higher integer, the results should be acceptable in most situations where performance is of the essence. Make this public so that clients can account for the RoundingTieBreaker if necessary
Definition at line 215 of file vtkFastNumericConversion.h.
| static double vtkFastNumericConversion::QuickFloorDenormalizer | ( | ) | [inline, static, protected] |
This is the magic floating point value which when added to any other floating point value, causes the rounded integer portion of that floating point value to appear in the least significant bits of the mantissa, which is what we want.
Definition at line 227 of file vtkFastNumericConversion.h.
| static double vtkFastNumericConversion::SafeFloorDenormalizer | ( | ) | [inline, static, protected] |
This is the magic floating point value which when added to any other floating point value, causes the rounded integer portion of that floating point value to appear in the NEXT TO least significant bits of the mantissa, which is what we want. This allows the CPU rounding mode to muck with the LSB which we can then discard in SafeFloor
Definition at line 237 of file vtkFastNumericConversion.h.
| static double vtkFastNumericConversion::QuickExtPrecTempDenormalizer | ( | ) | [inline, static, protected] |
This value is added to and then subtracted from an extended precision value in order to clear the fractional bits so that they do not adversely affect the final double-precision result.
Definition at line 245 of file vtkFastNumericConversion.h.
| static double vtkFastNumericConversion::SafeExtPrecTempDenormalizer | ( | ) | [inline, static, protected] |
Just like QuickExtPrecTempDenormalizer(), but preserves one extra bit of fixed point precision to guard against the CPU mucking with the LSB
Definition at line 253 of file vtkFastNumericConversion.h.
| static double vtkFastNumericConversion::QuickRoundAdjust | ( | ) | [inline, static, protected] |
Definition at line 257 of file vtkFastNumericConversion.h.
| static double vtkFastNumericConversion::SafeRoundAdjust | ( | ) | [inline, static, protected] |
Definition at line 258 of file vtkFastNumericConversion.h.
| static int vtkFastNumericConversion::SafeFinalShift | ( | ) | [inline, static, protected] |
Definition at line 259 of file vtkFastNumericConversion.h.
| void vtkFastNumericConversion::SetReservedFracBits | ( | int | bits | ) | [inline] |
Set the number of bits reserved for fractional precision that are maintained as part of the flooring process. This number affects the flooring arithmetic. It may be useful if the factional part is to be used to index into a lookup table of some sort. However, if you are only interested in knowing the fractional remainder after flooring, there doesn't appear to be any advantage to using these bits, either in terms of a lookup table, or by directly multiplying by some unit fraction, over simply subtracting the floored value from the original value. Note that since only 32 bits are used for the entire fixed point representation, increasing the number of reserved fractional bits reduces the range of integer values that can be floored to.
Definition at line 283 of file vtkFastNumericConversion.h.
| void vtkFastNumericConversion::PerformanceTests | ( | void | ) |
Conduct timing tests so that the usefulness of this class can be ascertained on whatever platform it is being used. Output can be retrieved via Print method.
| static int vtkFastNumericConversion::QuickFloor | ( | const double & | val | ) | [inline, static] |
Perform a quick flooring of the double-precision floating point value. The result is sometimes incorrect, but in a way that makes it acceptable for most uses. The naive way to implement floor(), given that the x86 FPU does round() by default, is to define floor(x) as round(x-.5). This would work fine except for the fact that the x86 FPU breaks rounding ties by selecting the even number. Thus, floor(4.0) = round(3.5) = 4, but floor(3.0) = round(2.5) = 2. As a result, subtracting .5 gives the wrong answer for odd integers. So, let's subtract just a TEENSY bit less than .5, to swing the odd-integer results up to their corect value. How teensy? Well, if it's too teensy, it will be insignificant compared to 0.5, and will become equivalent to 0.5. And if it's not teensy enough, we'll overshoot, causing results like floor(N-epsilon)==N, for some epsilon. Furthermore, the "too teensy" problem is exacerbated when trying to floor larger numbers, due to limitations of the representation's dynamic range. See the definition of RoundingTieBreaker() for details.
Definition at line 322 of file vtkFastNumericConversion.h.
| static int vtkFastNumericConversion::SafeFloor | ( | const double & | val | ) | [inline, static] |
Perform a SAFE flooring. Similar to QuickFloor, but modified to return the correct result always. Use this when it absolutely positively needs to be the correct answer all the time, and considering 0.9999999 as being equal to 1.0 is simply not acceptable. It works similarly to QuickFloor, but it retains one extra bit of fixed point precision in the conversion process, so that the problem with QuickFloor affects only an unneeded bit, and then it ditches that bit from the resulting integer with a right-shift. In other words, it rounds to the nearest one-half, choosing the EVEN one-half (i.e. the integer) as a tie-breaker, and then shifting off that half-integer bit. As a result of maintaining one extra bit of fixed point precision in the intermediate calculation, the range of integers supported is reduced by one bit. Plus, it takes a little longer to execute, due to the final bit shift.
Definition at line 359 of file vtkFastNumericConversion.h.
| static int vtkFastNumericConversion::Round | ( | const double & | val | ) | [inline, static] |
Round to nearest int. This is pretty sweet in the default round-to-nearest FPU mode, since it is generally immaterial how ties are broken when rounding. I.e., either "2" or "3" are acceptable results for "Round(2.5)", but only one of them (the one naively not chosen without jumping through the hoops in QuickFloor and SafeFloor) is the acceptable result for the analogous "Floor(3)". Therefore, we don't need to worry at all about adding a teensy but not too teensy tie breaker, or shifting off a half-integer bit. This makes it exceptionally fast.
Definition at line 389 of file vtkFastNumericConversion.h.
| int vtkFastNumericConversion::ConvertFixedPoint | ( | const double & | val, | |
| int & | fracPart | |||
| ) | [inline] |
Convert the value to a fixed point representation, returning the integer portion as function value, and returning the fractional part in the second parameter.
Definition at line 420 of file vtkFastNumericConversion.h.
| void vtkFastNumericConversion::InternalRebuild | ( | void | ) | [protected] |
The documentation for this class was generated from the following file:
- dox/Common/vtkFastNumericConversion.h
