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

Abstract

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