теория, алгоритмы, примеры на С++ и OpenGL  

ПОДПИСКА

Компьютерная графика



Мы vkontakte.ru

WWF Russia.
Rambler's Top100 Rambler's Top100
Каталог@Mail.ru - каталог ресурсов интернет

Друзья

Обзоры игр от AntiGamer.RU

Числа с фиксированной точкой

Большим преимуществом чисел в формате плавающей точкой является точность. Но, анализируя некоторые алгоритмы, приходим к выводу, что точности в четыре знака после запятой более чем достаточно. (Яркий пример такого класса алгоритмов – алгоритмы растеризации). А обеспечить такую точность можно всего двумя байтами. Действительно, требуется хранить 10000 градаций: 0.0000 – 0.9999, в то время как 2 байта позволяют хранить 65536.
 
Идея арифметики с фиксированной точкой состоит в следующем. Возьмем четырехбайтный тип данных (тип int в 32-разрядном компиляторе С++). Будем использовать старшие два байта (слово) под целую часть числа, а младшие – под вещественную.
 
Пример. Число 123.654 представится в виде:
 

123

         654
 
Число 123.654 * 216 = 8060928 + 42860 = 8103788
 
Заметим, что числа, хранящиеся в таком представлении, можно:
  • складывать и вычитать между собой;
  • делить и умножать на целые числа в обычном представлении.
При этом результат будет вполне осмысленным. Однако следует обратить внимание, что операции умножения и деления будут весьма неточными. Возникает вопрос, когда следует использовать такой формат представления чисел?
 
Такой формат выгодно использовать в тех случаях, когда в конечном итоге требуется лишь целая часть представляемого числа и преимущественно используются сложения / вычитания. После нескольких тысяч операций        сложения / вычитания накопившаяся ошибка составит около одной десятой. Для некоторых алгоритмов, например растеризации, это оказывается вполне приемлемым. При этом выигрыш по скорости получается весьма ощутимый.
 
Ниже приведена реализация чисел с фиксированной точкой на языке С++:
 
// fixed.h
#ifndef __FIXED__
#define __FIXED__
 
#include "math.h"
 
#define fixed int
#define round(x) floor(x + 0.5)
#define roundf(x) floor(x + 0.5f)
 
// представляет целое число в формате чисел с фиксированной точкой
inline fixed int_to_fixed(int value)
{
      return (value << 16);
}
 
// целая часть числа с фиксированной точкой
inline int fixed_to_int(fixed value)
{
      if (value < 0) return (value >> 16 - 1);
      if (value >= 0) return (value >> 16);
}
 
// округление до ближайшего целого
inline int round_fixed(fixed value)
{
      return fixed_to_int(value + 5 << 15);
}
 
// представляет число с плавающей точкой в формате чисел с фиксированной точкой
// здесь происходят большие потери точности
inline fixed double_to_fixed(double value)
{
      return round(value * (65536.0));
}
 
inline fixed float_to_fixed(float value)
{
      return roundf(value * (65536.0f));
}
 
// записывает отношение (a / b) в формате чисел с фиксированной точкой
inline fixed frac_to_fixed(int a, int b)
{
      return (a << 16) / b;
}
 
#endif
 
Прим. Округление до ближайшего целого можно сделать так: округляем вниз (floor) число плюс 0.5. Выше это делается директивой #define:
 
#define round(x) floor(x + 0.5)
 
При этом можно складывать и вычитать два числа в формате fixed. С умножением и делением все немного сложнее. Умножать имеет смысл только fixed на int. Делить можно fixed на int, тогда получится снова fixed. Если разделить fixed на fixed, получится int.
 
Пример:
 
fixed a, b, c;
int d;
 
a = int_to_fixed(100);
b = int_to_fixed(10);
d = a / b; // d будет содержать 10 в формате int
c = a / 10; // с будет содержать 10 в формате fixed
 
c = a + b; // c будет содержать 110.0 в формате fixed

Скачать библиотеку (fixed.h) и исходный текст демонстрационной программы

Интернет-журнал «Мистер Вульф»