圖形的即時3D碰撞演算法

Collision-Based 3D Layout Algorithm for On-line Graph Visualization in DIVA

曾建智

指導教授 ： 鄭永斌

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2007年)

摘要

隨著程式的複雜化，一般傳統的除錯方法對於程式設計師的幫助有限，因此除錯器的開發對於程式設計師而言，變的越來越不可或缺。目前的除錯器大部分仍止於文字階段，然而文字所能傳達的僅僅只有變數值的變化，難以表達資料結構間複雜的關係。，因此更近一步地，有人設計出可以使用圖形化的方式來表達程式的資料之間相互關係的工具。比起文字，透過圖形化的表現方式，往往能讓程式設計師更加快速且直覺化的掌握程式的脈絡。然而，一但在圖形數量一多，圖形之間可能會互相的重疊與覆蓋(在本論文中用「碰撞」來稱呼重疊與覆蓋)，以至於整個畫面的可讀性隨之下滑，所以視覺化物件畫面中的排版就變的非常的重要。因此，我們的研究目標，就是透過適合的演算法讓空間中的物件都有各自的一塊獨立空間，將空間中的除錯資訊做較佳的輸出，提高整體的可讀性。
於本篇論文中，我們針對空間中碰撞的問題在DIVA(Debugging Information Visualization Assistant)的三維空間環境中設計了一套排版列演算法。藉由此套演算法，可以處理空間中碰撞的問題，已達到較佳的視覺效果。

關鍵字

輸出演算法 ； 視覺化方法 ； 軟體視覺化 ； 除錯器

並列摘要

Because of the increase in complexity of software programs, debugging without help from tools is no longer adequate. Therefore, debugger has become an important tool in programmer’s everyday life. Nowadays, debuggers only show the debugging information in textual form. It is considered inadequate for understanding complicated data structures. There are some debugging tools that can display debugging information in graphic presentation, which is much more informative than textual information.
However, it is useless when too much information is rendered together. In this thesis, a tool called DIVA(Debugging Information Visualization Assistant) is proposed. DIVA has object-oriented framework that enables the separation of VM programming from visualization system and particularly the composability of visualization metaphors. Based on the framework, a layout algorithm called Collision-Based layout algorithm is designed and implemented to arrange visuals in proper positions in a scene.

並列關鍵字

Layout Algorithm ； Visualization Metaphor ； Software Visualization ； Debugger

參考文獻

[7]. B. A. Price, R. M. Baecker and I. S. Small, A Principled Taxonomy of Software Visualization, Journal of Visual Languages and Computing 4(3), September 1993, p211-266

[9]. Knight, Munro, “Visualising Software - A Key Research Area”, Proceedings of the IEEE International Conference on Software Maintenance ,page: 437, 1999

[11]. M. Lanza and S. Ducasse “Polymetric Views—A Lightweight Visual Approach to Reverse Engineering”, IEEE Transactions on Software Engineering archive, volume 29, Issue 9, pages:78 -795, 2003

[1]. Emden R. Gansner ,Eleftherios Koutsofios, Stephen C. North, and Kiem-Phong, A technique for drawing directed graphs. IEEE transactions on Software Engineering, vol 19,NO.3, pp. 214-230, 1993

[2]. J. B. Rosenberg, How Debuggers Work: Algorithms, Data Structure, and Architecture, John Wiley & Sons. , September 27, 1996