Overview

EX00では、オブジェクトの基本的な形( Orthodx Canonical Form )でクラス設計(Fixed)の基礎を学びます。

EX01では、Fixedクラスに整数や浮動小数点の値を扱うコンストラクタを追加していきます。さらに、 固定小数点 として扱えるようにして、人間が理解しやすい形に出力できる様にします。（演算子のオーバーロード）

EX02では、Fixedオブジェクト同士の演算を実装します。具体的には演算子のオーバーロード（比較：>, <, >=, <=, ==, !=, 四則：+, -, *, /, インクリメント・デクリメント ：++, --）の設計。

EX03では、 BSP (Binary Space Partitioning)という幾何学的アルゴリズム（点が三角形の内側にあるかどうか判定する関数bsp）を実装します。判定するためにベクトル演算（クロス積？？）の概念を利用する。

まとめると、Fixedクラスを基本的なオブジェクトの構造から始まり、具体的な数値の扱い、他のオブジェクトの関係性、実用的な問題解決への応用に繋がっていきます。Fixedクラスが進化していく過程を体験します。

Project Links

Intra - CPP02
GitHub - CPP02 (非公開)
My Documents : CPP02 / CPP_Modules

‍Doxygenで作成されたソースコードドキュメントです。

クラスの連携図やソースコードの説明に関する情報がまとめられています。

課題を始める前に

浮動小数点の課題（速度、精度、決定性）を克服する手法として、固定小数点の仕組みが利用されることがあります。

ちなみに、Cub3dの課題でもレンダリングの処理速度を改善するために固定小数点の仕組みを使うこともあります。（実際に実装しました）

また、C++の標準ライブラリには組み込み用固定小数点の型がないため実装する必要があります。

固定小数点の実装を通じて、固定小数点の利点や欠点を理解し、適切な数値型を選択する判断力を養えるだけでなく、クラス設計の演算子オーバーロードによる直感的な操作ができるオブジェクト設計スキルが得られます。

ex00 "My First Class in Orthodox Canonical Form"

Files :

‍Fixed.hpp , Fixed.cpp , main.cpp , Makefile

内容：

‍int型の数値をオブジェクトで扱う。

「標準的な形式」基本的なオブジェクトの形を学びます。

構成

デフォルトコンストラクタ

コピーコンストラクタ

コピー代入演算子

デストラクタ

オブジェクトのライフサイクルを管理する基盤を築く。

オブジェクトの誕生→コピー→終了まで

キーワード、メモ：

‍* 固定小数点の概念、表現、計算、２進数、ビットシフト

コンピューターで固定小数点で値を扱うと、整数・小数・負の値を２進すうで表現できる。

数値のビットパターンと、その半分の値(1/2)のビットパターンが同じ。

2進数小数点（バイナリポイント）の位置が違うだけ。

動作結果

main.cpp

int main(void) {
    Fixed a;
    Fixed b(a);
    Fixed c;
    c = b;
 
    std::cout << a.getRawBits() << std::endl;
    std::cout << b.getRawBits() << std::endl;
    std::cout << c.getRawBits() << std::endl;
 
    return 0;
}

出力

$ ./a.out
Default constructor called
Copy constructor called
Default constructor called
Copy assignment operator called
getRawBits member function called
0
getRawBits member function called
0
getRawBits member function called
0
Destructor called
Destructor called
Destructor called

ex01 "Towards a more useful fixed-point number class"

Files :

‍Fixed.hpp , Fixed.cpp ,

main.cpp , Makefile

内容：

‍より実用的な固定小数点クラスへ改良する

オブジェクトに機能を追加していき、数値表現と操作するためのツールとして進化していく課題。

追加する機能

整数や浮動小数点をFixed型として扱う。

内部の固定小数点の表現を、人間が理解できる表現に戻す。（整数、浮動小数点など）

画面に出力する機能（<< の代入演算子を使って出力）

キーワード、メモ：

整数、浮動小数点を使って固定小数点のオブジェクトを作るコンストラクター。

‍
Fixed::Fixed(const int raw) : fixedPointValue(raw << fractionalBits) {

std::cout << "Int constructor called" << std::endl;

}

Fixed::Fixed
Fixed()
Default constructor.
Definition Fixed.cpp:33

int型のコンストラクター ：raw << fractionalBits

‍例：raw = 10の場合

(0d) 10 << 8 = (0d) 2560

(0b) 1010 << 8 = (0b) 1010 0000 0000

Fixed::Fixed(const float raw) : fixedPointValue(static_cast<int>(roundf(raw * (1 << fractionalBits)))) {

std::cout << "Float constructor called" << std::endl;

}

float型のコンストラクター ：static_cast<int>(roundf(raw * (1 << fractionalBits)))

‍例：raw = 42.42f の場合

42.42f * (1 << 8) = 42.42f * 256f = 10859.52f

roundf(10859.52f) = 10860

(0d) 10860 == (0b) 10 1010 0110 1100

roundf()：浮動小数点の小数部を丸める。（四捨五入）
オブジェクト固定小数点数から数値を取り出すメソッド : toInt(), toFloat()

‍raw = 10の場合：

fixPointValue(10 << 8) -> (0b)1010 0000 0000 == (0d)2560

**toInt()**

‍
int Fixed::toInt(void) const { return this->fixedPointValue >> fractionalBits; }

Fixed::toInt
int toInt(void) const
Converts the fixed-point value to an integer value (truncates the fractional part).
Definition Fixed.cpp:101

toInt() -> 2560 >> 8 -> (0b)1010 == (0d)10

**toFloat()**

‍
float Fixed::toFloat(void) const { return static_cast<float>(this->fixedPointValue) / (1 << fractionalBits); }

Fixed::toFloat
float toFloat(void) const
Converts the fixed-point value to a floating-point value.
Definition Fixed.cpp:92

toFloat() -> 2560.0f / 256.0f = 10.0fを返します。

分数256.0fは(1 << franctionalBits) == 1 << 8 == 256が暗黙的にfloat型にキャストされます。

出力ストリーム演算子<<のオーバーロード

‍
std::ostream &operator<<(std::ostream &o, const Fixed &fixed) {

o << fixed.toFloat();

return o;

}

std::ostream

operator<<
std::ostream & operator<<(std::ostream &o, const Fixed &fixed)
Overloads the output stream operator to insert the float representation of the fixed-point number int...
Definition Fixed.cpp:113

出力ストリームの参照 : std::ostream &o

Fixedオブジェクトの定数参照 : const Fixed &fixed

出力ストリームにオブジェクトを出力 : o << fixed.toFloat();

覚え書き: 符号付き整数に対する算術右シフト C++98の初期の規格では、一部のハードウェアには>>の命令が直接用意されており、コンパイラはその命令をそのまま利用することがあります。ただし、CPUによっては、算術右シフト命令がなく、複数の命令を組み合わせて同等の動作を実現することが必要となり、その方法が異なることがありました。

特に負の数の右シフト結果の実装の違いの例をあげると
小さい方向へ丸める std::floor() or ゼロ方向へ丸める std::trunc()

std::floor()

std::trunc()

C++20以降の変更点として、 値を小さい方へ丸める (rounds towards negative infinity) に定義されていました。(std::floor()と同等)
詳しくは、アセンブラの課題で勉強しましょう！

覚え書き

std::floor()関数と固定小数点数の動作イメージ

‍機能：小数部を切り捨てる。(その数よりも小さい整数値を返します。)

‍-> cppreference.com

正の数の例：

‍std::floor(42.42f) = 42.0f

fixedPointValue(42.42f) -> 10860 -> toInt() -> 42

* 負の数の例：

‍std::floor(-5.2f) = -6.0f

fixedPointValue(-5.2f) -> -1331 -> toInt() -> -6

動作結果

main.cpp

int main(void) {
    Fixed a;
    Fixed const b(10);
    Fixed const c(42.42f);
    Fixed const d(b);
    a = Fixed(1234.4321f);
 
    std::cout << "a is " << a << std::endl;
    std::cout << "b is " << b << std::endl;
    std::cout << "c is " << c << std::endl;
    std::cout << "d is " << d << std::endl;
    std::cout << "a is " << a.toInt() << " as integer" << std::endl;
    std::cout << "b is " << b.toInt() << " as integer" << std::endl;
    std::cout << "c is " << c.toInt() << " as integer" << std::endl;
    std::cout << "d is " << d.toInt() << " as integer" << std::endl;
    return 0;
}

出力

$ ./a.out
Default constructor called
Int constructor called
Float constructor called
Copy constructor called
Float constructor called
Copy assignment operator called
Destructor called
a is 1234.43
b is 10
c is 42.4219
d is 10
a is 1234 as integer
b is 10 as integer
c is 42 as integer
d is 10 as integer
Destructor called
Destructor called
Destructor called
Destructor called

ex02 "Now we’re talking"

Files :

‍Fixed.hpp , Fixed.cpp ,

main.cpp , Makefile

内容：

ポリフォーリズム Polymorphism
　直訳：多型性。１つのシンボルで複数の異なる形を表すこと。（生物学の用語、原理から借用）
　異なるデータ型のエンティティに対して１つのインターフェースを提供すること。
　・演算子のオーバーロード、関数のオーバーロード
　・他にもポリモーフィズムはあるが、他のC++モジュールで勉強しましょう。
　　テンプレート関数、
　　動的ポリモーフィズム（仮想関数virtual function）、
　　抽象クラス(Abstract Class)と純粋仮想関数(Pure Virtual Functions)

学んだことのキーワード：

固定小数点のメリット
　一定の精度（仮数部23bitで扱える範囲）まではfloat型を使わず小数の計算を高速化できる
　FPUと搭載しないコンピューターでも小数の計算ができる。
 
ユニットテストに関して
　浮動小数点数の精度
　FLT_EPSILON
　テストツール　google test
　Floatの許容範囲

動作結果

main.cpp

int main(void) {
    Fixed a;
    Fixed const b(Fixed(5.05f) * Fixed(2));
 
    std::cout << a << std::endl;
    std::cout << ++a << std::endl;
    std::cout << a << std::endl;
    std::cout << a++ << std::endl;
    std::cout << a << std::endl;
 
    std::cout << b << std::endl;
 
    std::cout << Fixed::max(a, b) << std::endl;
 
    return 0;
}

出力

$ ./a.out
0
1
1
1
2
10.1016
10.1016

その他

cpprefjp FLT_EPSILON, FLT_MAX
テストコード

‍

固定小数点数の最小分解能を考慮した数値比較

++

// 固定小数点数の最小分解能を考慮した許容範囲

void fixedEquals(float expected, float actual) {

int k = 1;

float epsilon = (1.0f / (1 << 8)) * k; // fractionalBits は 8 と仮定

ASSERT_NEAR(expected, actual, epsilon);

}

分母０による除算の挙動

++

void checkDivisionByZero(Fixed &a) {

// std::cerr の出力をキャプチャするためのstringstream

std::stringstream ss_cerr;

std::streambuf *old_cerr = std::cerr.rdbuf();

std::cerr.rdbuf(ss_cerr.rdbuf());

Fixed result = a / Fixed(0.0f);

// std::cerr の内容を元に戻す

std::cerr.rdbuf(old_cerr);

// エラーメッセージのチェック

std::string expected_error = "Division by zero is undefined. Returning maximum float.";

ASSERT_NE(ss_cerr.str().find(expected_error), std::string::npos)

<< "Expected error message not found in cerr: \"" << ss_cerr.str() << "\"";

// 返り値が最大 float 値に近いかのチェック

float max_float = std::numeric_limits<float>::max();

ASSERT_FLOAT_EQ(result.toFloat(), Fixed(max_float).toFloat());

// NG

// ASSERT_FLOAT_EQ(result.toFloat(), max_float);

// より緩やかな比較が必要な場合は ASSERT_NEAR を使用

// float epsilon = 1e-6; // 適宜調整

// ASSERT_NEAR(result.toFloat(), max_float, epsilon);

}

std::streambuf

std::string

std::stringstream

std::cerr

std::numeric_limits::max
T max(T... args)

std::stringstream::rdbuf
T rdbuf(T... args)

std::stringstream::str
T str(T... args)

<<出力の動作確認

++

TEST(FixedOutputTest, OutputStreamOperator) {

Fixed a(123.45f);

std::stringstream ss;

ss << a;

fixedEquals(std::stof(ss.str()), 123.45f);

// 123.449 ~= 123.45f ... neary equal

// Bad Test

// ASSERT_EQ(ss.str(), "123.453125"); // Due to fixed-point precision

}

std::stof
T stof(T... args)

レビュー後に自分の実装の間違いに気づいたこと

インクリメント、デクリメントの実装

‍間違い

‍課題要件として、表現可能な最小値（the smallest representable ε, such that 1 + ε > 1）でインクリメント・デクリメントすることが求められていたのに、わざわざ整数値１相当の値（fixedPoint += (1 << franctionalBits)）で計算していたことが判明。

正解

‍fixedPointValue++の実装が正しいです。
算術演算の実装について

‍間違い
++

Fixed Fixed::operator*(const Fixed &other) const { return Fixed(this->toFloat() * other.toFloat()); }

Fixed::operator*
Fixed operator*(const Fixed &other) const
Overloads the multiplication operator.
Definition Fixed.cpp:134

‍NGな理由：固定小数点の利便性を消失している💦

float型の値同士を計算している（時間がかかる＋FPUの機能がないコンピュータだとそもそも動作しない）

また、仮数部23bitで扱える範囲を超えると、計算結果に誤差が生じる。

正解
++

Fixed Fixed::operator*(const Fixed &other) const {

Fixed result;

long long raw_result = (long long)this->fixedPointValue * other.fixedPointValue;

result.setRawBits((int)(raw_result >> fractionalBits));

return result;

}

Fixed::setRawBits
void setRawBits(int const raw)
Sets the raw value of the fixed-point number.
Definition Fixed.cpp:84

解説

‍一時的に64bitのデータに計算結果を入れて、固定小数点の重み256をビットシフトで丸めている。

本来の目的（floatを使わず高速な計算を実現化するクラス）を満たしている。
補足

‍**fractionalBits = 8 の数値が変わった時の影響:**

‍この課題の仕様（value++ 方式）を採用した場合、ビット数によって ++ の「重み」が変わります。

fractionalBits = 8 : ++ を実行すると 1/256 増える。

fractionalBits = 16 : ++ を実行すると 1/65536 増える。

影響:精度を高く設定するほど、++ による値の変化はより細かく（小さく）なります。

汎用性:数学的な「+1」を期待するコード（例：forループのカウンタなど）にこのクラスを使うと、意図通りに動かなくなるため注意が必要です。

処理速度の違い:

‍this->fixedPointValue++ は、CPUの1命令（INC命令など）で処理されるため、これ以上ないほど高速です。

ex03 "BSP"

Files :

‍Fixed.hpp , Fixed.cpp ,

Point.hpp , Point.cpp , bsp.cpp,

main.cpp , Makefile

内容：

平面の点を表すPointクラスを実装
  const Fixedのx, yのプライベート変数
  関数bsp()を実装する：三角形の内外判定

キーワード：

BSP（バイナリ空間分割木）

ベクトルの外積を用いて、平面上の三角形の内外判定を行います。

動作結果

main.cpp

int main(void) {
    Point a(0.0f, 0.0f);
    Point b(10.0f, 0.0f);
    Point c(5.0f, 5.0f);
 
    Point p1(5.0f, 2.5f);
    Point p2(0.0f, 0.0f);
    Point p3(10.0f, 0.0f);
    Point p4(5.0f, 5.0f);
    Point p5(6.0f, 6.0f);
    Point p6(5.0f, 0.0f);
    Point p7(2.0f, 1.0f);
    Point p8(1.0f, 0.9f);
 
    std::cout << "Point a(" << a.getX() << ", " << a.getY() << "), ";
    std::cout << "b(" << b.getX() << ", " << b.getY() << "), ";
    std::cout << "c(" << c.getX() << ", " << c.getY() << "), " << std::endl;
 
    std::cout << "Point p1(" << p1.getX() << ", " << p1.getY() << ") "
              << "is inside triangle (a, b, c): " << bsp(a, b, c, p1) << std::endl;
    std::cout << "Point p2(" << p2.getX() << ", " << p2.getY() << ") "
              << "is inside triangle (a, b, c): " << bsp(a, b, c, p2) << std::endl;
    std::cout << "Point p3(" << p3.getX() << ", " << p3.getY() << ") "
              << "is inside triangle (a, b, c): " << bsp(a, b, c, p3) << std::endl;
    std::cout << "Point p4(" << p4.getX() << ", " << p4.getY() << ") "
              << "is inside triangle (a, b, c): " << bsp(a, b, c, p4) << std::endl;
    std::cout << "Point p5(" << p5.getX() << ", " << p5.getY() << ") "
              << "is inside triangle (a, b, c): " << bsp(a, b, c, p5) << std::endl;
    std::cout << "Point p6(" << p6.getX() << ", " << p6.getY() << ") "
              << "is inside triangle (a, b, c): " << bsp(a, b, c, p6) << std::endl;
    std::cout << "Point p7(" << p7.getX() << ", " << p7.getY() << ") "
              << "is inside triangle (a, b, c): " << bsp(a, b, c, p7) << std::endl;
    std::cout << "Point p8(" << p8.getX() << ", " << p8.getY() << ") "
              << "is inside triangle (a, b, c): " << bsp(a, b, c, p8) << std::endl;
 
    return 0;
}

出力

$ ./bsp
Point a(0, 0), b(10, 0), c(5, 5), 
Point p1(5, 2.5) is inside triangle (a, b, c): 1
Point p2(0, 0) is inside triangle (a, b, c): 0
Point p3(10, 0) is inside triangle (a, b, c): 0
Point p4(5, 5) is inside triangle (a, b, c): 0
Point p5(6, 6) is inside triangle (a, b, c): 0
Point p6(5, 0) is inside triangle (a, b, c): 0
Point p7(2, 1) is inside triangle (a, b, c): 1
Point p8(1, 0.898438) is inside triangle (a, b, c): 1

その他

Cross_product (外積)
Binary Space Partitioning Trees : cs.columbia.edu

‍

* コピー代入演算子の注意点：constのメンバーを持つクラスは、コピー代入演算子をカプセル化するのを避けるか、慎重に検討する方がいい。

‍placement newを使うなどあるが、直感的な挙動とは異なる可能性がある。

この演習ではコピー代入演算子を使う用途がないため、ダミー用の実装をしています。 (代入せず、*this自分自身を返すだけ）

レビューメモ

コピーコンストラクタについて

直接メンバー変数を使って数値の取り出しと代入をしていましたが、setRawBits(), getRawBits()を使うことでより安全かつ可読性の高いコードができる。という意見がありました。

my code:
Fixed &Fixed::operator=(const Fixed &other) {

std::cout << "Copy assignment operator called" << std::endl;

if (this != &other) {

this->fixedPointValue = other.fixedPointValue;

}

return *this;

}

Fixed::operator=
Fixed & operator=(const Fixed &other)
Copy assignment operator.
Definition Fixed.cpp:52
other code:
++

Fixed &Fixed::operator=(const Fixed &other) {

if (this != &other) {

setRawBits(other.getRawBits());

}

return *this;

}

セッター関数およびコピー代入演算子に関する考え。

セッター関数をpublicにすると、メンバー変数の操作が用意になってしまい、想定外の操作をされてバグの要因につながる可能性がある。（特別な理由で無い限り、publicのセッター関数は作らない。）
効率性の低下：セッター関数のオーバーヘッド（単なる値の代入だけでなく、セッター関数内部の処理で値のチェックや範囲チェックなどを行う可能性がある）
意図しない副作用：ログ出力や他のオブジェクトへの通知など引き起こす可能性あり。
配列や複雑なメンバー変数を持つ場合、メモリの直接コピーの方が効率的。
その他 -> コピー代入演算子でセッター関数を推奨しない理由

結論：前者のコードに落ち着きました。

toFloat()について

my code:
float Fixed::toFloat(void) const { return static_cast<float>(this->fixedPointValue) / (1 << fractionalBits); }

‍例：2560.0f/256.0f=10.0f

元の浮動小数点数は固定小数点の表記にするためにスケーリング係数を乗じた値が保持される。

スケーリング係数で割ることで、この逆の処理ができる。（スケーリング反転）

スケーリング係数：1 << fractionalBits == 256

bad code:

++

float Fixed::toFloat(void) const { return static_cast<float>(this->fixedPointValue) << fractionalBits; }

‍浮動小数点数にビットシフトをすると、符号・指数部・仮数部のスケール反転とは異なる操作となり、大きく異なる値になることがある。

基本的には、x << nは整数に２のn乗を掛ける操作にあたり、浮動小数点数の構造上適していません。

Other

ブランチの使い方

‍main: 安定版

feature/ex00: 各課題の機能開発を行う。

docs: ここにpushすると、GitHub Actions workflowが動作してドキュメントが公開されます。
ドキュメントページ

‍C++ Moduleのプロジェクト毎にDoxygenを使ったドキュメントをまとめています。

doxygen用のcssテーマは、Doxygen Awesomeを使用。

Overview

Project Links

課題を始める前に

ex00 "My First Class in Orthodox Canonical Form"

Files :

内容：

キーワード、メモ：

動作結果

関連URL

ex01 "Towards a more useful fixed-point number class"

Files :

内容：

キーワード、メモ：

動作結果

ex02 "Now we’re talking"

Files :

内容：

学んだことのキーワード：

動作結果

その他

レビュー後に自分の実装の間違いに気づいたこと

ex03 "BSP"

内容：

キーワード：

動作結果

その他

レビューメモ

コピーコンストラクタについて

toFloat()について

Other