かつてのMac OS9までの描画エンジンの主役はQuickDrawが担っていた。GUIなOSでは、文字も含めてすべてをグラフィックとして扱うので、画面に見えているすべてのもの*1はQuickDrawによって描かれていたことになる。描画エンジンは、GUIなOS開発の要となる技術である。その出来が、GUIなOS開発の成否を分けるとも言える。 そして、最初期のQuickDrawは、ビル・アトキンソンがたった一人で開発したそうである。 当時(25年以上前)のCPUは、動作クロックが8MHzという性能だった。(現在は2GHz=2000MHzかつ、複数コアが当たり前) そのような性能であっても、違和感なくマウスで操作できるOS環境にするために、斬新な発想や試行錯誤を重ね、相当な努力の末に開発されたのがLisaやMacintoshであった。 Amazon.co.jp: レボリューション・イン・ザ・バレー
ACM/ICPC(プログラミングコンテスト)系列の問題を解くことを目標にして,各種アルゴリズムを C++ で実装してみた.極めて意地が悪い類の問題には対応していないし,特定の入力に対して高速に動くということもない.計算量も最良とは限らない. これらを参考にする方への注意とお願い: これらの記述は正確とは限りません.参考文献を参照することを強く推奨します.間違っている場合は是非教えてください. これらのプログラムは間違っているかもしれません.各人で検証することを強く推奨します.バグがあれば是非教えてください. 分類が怪しいので,これはこっちだろう,ということがあればコメントを下さると助かります. 注意! 現在書き換え中 TODO 分類を正しく行う. 全体的に説明と使い方を詳しく. Verify していないものを Verify. ボロノイ図(いつになることやら……) 基本 テンプレート グラフ
ここでは,ACM/ICPC頻出の平面幾何について,基本的なベクトル演算を解説します。 最後にライブラリとしてソースコードを載せているので本番では印刷して持っておくとよいでしょう。 ベクトルの基礎 デカルト座標系とユークリッド空間 スカラーとベクトル 点とベクトル ベクトルの和と差 ベクトルの利用 complex型の導入 絶対値,2点間の距離,単位ベクトル 法線ベクトル,単位法線ベクトル 内積と外積 内積・外積 2直線の直交判定・平行判定 点が線上にあるかないかの判定 直線と線分 直線と点の距離 線分と点の距離 線分の交差判定 線分の交点計算 直線の交点計算 ソースコード $Id: index.shtml 1825 2007-09-23 00:35:10Z SYSTEM $
O:原点 OA:回転軸 P:回転前の点の位置 P':回転後の点の位置 Q:点 P を含む回転面と回転軸の交点 a:回転軸の方向・向きを表す単位ベクトル θ:回転角 回転方向は,座標系が右手系ならば a に対して右ネジの向き,左手系ならば左ネジの向きとする. p ≡ O→P p' ≡ O→P' u ≡ Q→P v ≡ a × u (u を +90°回転させたベクトル) 注意:右手系と左手系では外積の向きの定義が逆になる. O→Q は単位ベクトル a に対する p の平行成分,u は垂直成分なので, ……………………………………… (2.2.1) ………………… (2.2.2) v は定義より, …………………(2.2.3) a⊥u かつ |a|=1 なので,|u|=|v| である点に注意. 以上と u⊥v であることを考慮すると,回転後の位置 p' は2次元の回転の式を使って次のように書ける
S ≡ (Px - Cx) * (Qy - Cy) - (Py - Cy) * (Qx - Cx) とする.S>0 なら左回り,S<0 なら右回り,S=0 ならば C,P,Q は一直線上にある.(注) なお,この判別方法は,CP と CQ が同じ長さである必要はない. θを求めたい場合はこちらへ. この問題を見て,逆三角関数 tan-1 (C言語では atan() や atan2()) を使って CP と CQ の角度をそれぞれ求め, 両者を比較しようと考えた方が多いのではないでしょうか. しかしこの問題では,角度そのものではなく角度差の符号を求めればよいので, 逆三角関数を使う方法よりも簡単で優れた,外積を使う方法を紹介します. 2つの2次元ベクトル A=(Ax, Ay), B=(Bx, By) の外積を次のように定義する. A × B ≡ Ax * By - Ay * Bx ここで O
● はじめに 3次元CGのプログラムを作成しているとき、任意軸周りの回転の行列が求められると、便利です。以下では、その求め方を、簡単に説明します。 ● 任意軸周りの回転行列の計算 まず、以下のように、x軸、y軸、z軸上の単位ベクトルをi、j、kとおきます。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く