Part 3: Polygon reduction algorithms

There are many algorithms for simplifying objects with different features, such as efficiency, quantity of memory, scalability, etc. The most frequently used methods are described in next chapters. This chapter describes Edge collapse algorithm.

Simplification of the model is based on losing of detail, which can be neglected. It is necessary to consider whether it should be rapid and greater loss of object detail, or slower views with more detail. Typically in computer games may be the lesser quality because it shows a large number of objects, but the views such as medical data is important in large detail and speed plays a crucial role views.

Another possibility is the creation of a simplified model of manual work, which creates a graphic designer or animator at the same time, several versions of the object. This solution, however, is very expensive and time-consuming, but the results are better, because only a graphic artist knows that the object in the area are important and need more detail and which not.

Removing edges by edge collapse

This method is known as edge collapse, is most frequently used of all, and it is suitable for general non-triangular network. Algorithm chooses according to some metrics edge uv (from the list of edges) with the lowest weight, from point u to point v where first point will be moved into second. Following are carried out following operations:

  • The removal of all triangles, which contain both points u and v (ie. edge uv)
  • Update of all other triangles, which contain point u in such a way as to use the point v besides point u
  • Removal of point u

Each of the operation edge collapse removes three edges, two triangles and one point. The whole process is repeated so long as it does not achieve the desired amount of triangles. Illustration example is the removal of edges presented in Figure 1. The low number of polygons (low polygonal model) is created so that every time choose such edge, which causes the elimination of the smallest visual change. The selection depends on the edge of the metrics, see next part of this article.

Although the operation of edges removal is simple, it is necessary to give attention to the case where the normals of some neighboring triangles overflows the other side. The issue of solving problems in separate part of this article.

Principle of edge collapse

This method can be improved so that the transfer point for point to point in creating a new section in between these points in order to the smallest error. This calculation is much more demanding. The principle of simplification of the building through the elimination of some edge is shown in next image.

Simplification of object

Vyšlo 16.08.2008, v blogu: (printer friendly version)


Thank you that you decided to read this article. I like also for comments. If you delivered this article and would like to recommend it to others, please support us by taking take a minute of your time and make a link on your site or weblog. I wish pleasant reading

Latest articles

Diskuse k blogu

Zatím nikdo nevložil komentář. Chcete být první?
Přidání příspěvku
©Polygon reducer 2000-2008 | Optimised for 1024*768