In my final year at university- I was tasked with creating a software tool designed to render, view, and edit geometric data for the purpose of selecting and grouping semantic structures within a large data set.

This article gives a brief overview to the project based on the final year report - Structure from Soup (4.2MB).

Polygon soup

Polygon soup is any set of unstructured 3D data containing vertices and primitives. A vertex is a 3D point in space, described as a vector with three numeric values. A primitive is a collection of vertices with instructions on how to connect those vertices, such as in a line, a triangle, a triangle fan, or a triangle strip.

Large unstructured sets of polygon data are considered as polygon soup when there is no discernible grouping, naming, or hierarchy in place to describe the set of data. To understand the meaning of a raw set of vertices the data must either be rendered into an image or analysed to find enclosed spaces. The aim of this project was to use the human ability to visually distinguish shapes in order to quickly build up a structured selection.

Sources of polygon soup

Sources of polygon soup can be found from laser scanning devices, optimized scenes with no source files, and unstructured VRML (Virtual Reality Modelling Language) files from the web. When created, the structure of these datasets may have been included, but when published, structural data is often stripped out. In some sense, optimization is necessary for gaining performance, but as data sources grow older, and source files are lost, the task of managing these information sources becomes more difficult.

Interactive Visual Editor

To assist users in the task of identifying and grouping polygons within a source set of data it was evaluated that a 3D editor with good visual controls and easy to use tools would be the best way explore and group the data. Other automated methods, such as 3D model matching and flood-group search were investigated, but the output of such operations might produce inflexible or incorrect data that would require a user to filter; such tools were considered outside the scope of the project.

The 3D editor would allow users to identity structure within the soup.

Semantic Hierarchy

To improve the quality of the information identified, it was decided that tools to create a semantic hierarchy of the scene's structure would assist the user. These included tree-manipulation methods that would allow structures, such as 'a car with four wheels', to be organised. Implemented as a scenegraph and displayed as a tree-list, the semantic hierarchy doubles up as a navigation aid and a document overview.

Project success

Developing a 3D editor to display and manipulate polygon soup was a challenging one. I felt that I carefully researched and implemented an application that was both useful and cleary demonstrated my ability to plan and build a complex software application. It certainly scored well and secured my degree.

For me, it was interesting test to trial C++ development with the QT Framework and to apply 3D user interface development from my scrapbook to an OpenGL environment. I went into the project with an open mind and a will to learn, and produced a software application better then I first imagined.