ブレゼンハムのアルゴリズム(Bresenham's line algorithm)は、与えられた始点と終点の間に連続した点を置き、近似的な直線を引くためのアルゴリズム。ブレゼンハムの線分描画アルゴリズム、ブレゼンハムアルゴリズムとも。コンピュータのディスプレイに直線を描画するのによく使われ、整数の加減算とビットシフトのみで実装できるので多くのコンピュータで使用可能である。コンピュータグラフィックスの分野の最初期のアルゴリズムの1つである。これを若干拡張すると、円を描くことができる。 アンチエイリアスをサポートした直線描画アルゴリズム(例えば、Xiaolin Wu's line algorithm)もあるが、ブレゼンハムのアルゴリズムの高速性と単純さは今も重要である。プロッターやビデオカードのGPUといったハードウェアで使用されている。ソフトウェアでは多くのグラフィックスライブラリ(英語版)
かつてのMac OS9までの描画エンジンの主役はQuickDrawが担っていた。GUIなOSでは、文字も含めてすべてをグラフィックとして扱うので、画面に見えているすべてのもの*1はQuickDrawによって描かれていたことになる。描画エンジンは、GUIなOS開発の要となる技術である。その出来が、GUIなOS開発の成否を分けるとも言える。 そして、最初期のQuickDrawは、ビル・アトキンソンがたった一人で開発したそうである。 当時(25年以上前)のCPUは、動作クロックが8MHzという性能だった。(現在は2GHz=2000MHzかつ、複数コアが当たり前) そのような性能であっても、違和感なくマウスで操作できるOS環境にするために、斬新な発想や試行錯誤を重ね、相当な努力の末に開発されたのがLisaやMacintoshであった。 Amazon.co.jp: レボリューション・イン・ザ・バレー
今のPCはグラフィック画面の1ドットが見えないくらい精密な描画をしていますし、APIに座標を指定すればサッと点を打ってくれるのが当たり前なので、どうやって点を打つかなんて気にする必要はまったく無いのですが、8ビットな時代には、必ずしもそんな便利なサブルーチンが提供されているとは限らず、有っても汎用的には便利であっても特定の用途ではパフォーマンスに難があったりして、自力で点を打つ必要に迫られることも無くはありませんでした。 グラフィック画面はVRAMと呼ばれる特定のメモリ領域が使われていて、機種によって構造は大きく異なるのですが、良くある構造はカラープレーンごとに特定のアドレスからビット単位で横方向にデータが並べられて画面の右端まで行くと次の縦方向のデータが続くというものです。 VRAMの構造(例)ですから(0,12)に点を打ちたければ、12は12/8(整数除算)の結果である1をベースアドレ
むかしむかし、グラフィック画面に点を打つのに、自分でアドレスを計算して直接VRAMに値を書き込むことで点を打つ話を以下の記事に書きました。 自分で点を打つ世界 点ですら自分で打たなくてはならなかったくらいなのですから、当然のように線も自分で引かないとなりません。線というのは2つの点を結ぶものですから、2つのXY座標を指定して線を引きます。学校でならったと思いますが、直線の方程式は Y = mX + nですから、2つの点(X0,Y0)と(X1,Y1)を満たすmとnを計算して、XからY(またはYからX)を求める式を作ります。 Y = (Y1 - Y0) / (X1 - X0) ✕ (X - X0) + Y0これでXをX0からX1に変化させながらYを求めて線を描いていけばいいはずです。 【高校】直線の方程式5パターンの求め方をイチから!
追記:続きを書きました。 はじめに 先日以下の記事が投稿され、その斬新な考え方に個人的ながら衝撃を受けました。 内容をざっくり言うと、ニューラルネットワークの学習を現在の主流であるBP法(誤差逆伝播法)ではなく、ED法(誤差拡散法)という新しい学習手法を提案しているものです。 もし記事の内容が本当ならニューラルネットワークの学習がO(1)でできてしまう事になり、まさしく革命が起きてしまいます。 (結論からいうと速度面はそこまででもなかったです(それでも早くなる可能性あり)) (ただこの新手法のポテンシャルは革命を起こす可能性は秘めているといっても過言ではありません) ED法に関してネットを探すとインターネットアーカイブに情報が少し残っていました。 このページですがED法のサンプルプログラム(C言語)が残っており、このサンプルプログラムをベースにpythonで書き起こしたものが本記事となりま
普段は「通知が迷惑かなー」と思ってブックマークしていただいている方に通知せず記事を編集しているのですが、この記事をブクマしていただいている方は続きが気になっている方だと思いますので通知させていただきます。 結論から言うと、この記事を読んだ @pocokhc (ちぃがぅ)さんという方が金子勇さんが書いたED法のサンプルプログラムを見つけてくださいました。 ちぃがぅさんの記事はこちら 自分で解明したかったという気持ちも無いことは無いですが、バズった時点で誰かが実装してくれそうな気はしていました。新卒からIT業界に入って4年目が始まったところですが、業務以外で初めて業界にコントリビュートできた気がして嬉しいです! 追記ついでに、謝罪します。初回公開時に記事タイトル含め本文中で何か所か「Winney」と書いてしまっていた箇所がありました。失礼いたしました。誤字修正してあります。指摘してくださった何
プロダクションEXPO2015でRapidCopyの展示員をしているのですが、当然暇なので xxHashの紹介をしたいと思います。 xxhashってなに? xxhashはyann Collet氏が開発したファイルチェックサム専用の軽量ハッシュライブラリ(正確に言うとアルゴリズム)です。 実装はc++用が作者自身によって公開されていて、BSDライセンスなおかげもあって様々な言語で実装されてます。 github.com 今どきの主要言語はほぼ全てサポートされているので、是非コピペ実装してみてください。 で、このxxhash何が優れているか?って話になるのですが。まとめると以下のようになります。 低いCPU使用率 優れたハッシュ衝突率耐性 例えばみなさんおなじみのMD5なんかと比べると、ハッシュ生成速度はおよそ15倍。 CPU使用率は僕の開発マシンのSandyBridgeベースのCore i7
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く