Graphics Data Reduction



Data Reduction

Graphics data is mainly composed of vertex and facet data. In order to remove a vertex, facets which are related to the removed vertex must be maintained. Otherwise, a hole will be created in the target object. Therefore, removing a vertex should be considered as merging the vertex into another vertex. With this idea, facets data can also be maintained. As a result, no hole will be created.

The Graphics Data Reduction Algorithm is as follows.

  1. For every vertex, calculate the error distance from the vertex to planes created by removing the vertex (or by merging the vertex into another vertex). The maximum distance is adopted as the error distance if there are several different error distance. Also, if there are several candidates which the vertex is merged into, the vertex which gives the minimum error distance is taken as the merged vertex.
  2. Select the vertex which gives the minimum error distance among all vertices.
  3. If the vertex amount is equal to or less than the required amount, stop.
  4. Otherwise, remove the selected vertex (or merge the selected vertex into another vertex).
  5. Continue until the vertex amount is equal to or less than the required amount.


File Merge

By the above algorithm, a set of reduced data is created; however, it is troublesome to handle several files. Therefore, these reduced data files should be merged into one file.

The File Merge Algorithm is as follows.

  1. Compare the two vertex lists: smaller list and bigger list. Then search the difference.
  2. Find which vertices should be added to create the bigger list from the smaller one. Then make Vertex Addition List.
  3. Add the vertices which are in the Vertex Addition List to the smaller vertex list.
  4. Compare the new vertex list with the old bigger list. Then search the difference.
  5. Make a map table which translates the index number of vertex in the old bigger vertex list to the index number of vertex in the new vertex list.
  6. Convert the index number of vertex in the bigger facet list with the map table created above. As a result, a new bigger facet list is created.
  7. Compare the two facet lists: smaller old list and bigger new list. Then search the difference.
  8. Find which facets should be added and deleted to create the bigger new list. Then make Facet Addition List and Facet Deletion List.
  9. Add Vertex Addition List, Facet Addition List and Facet Deletion List to the smaller data file.