Part 4: Other methods for simplification

Another method, known as Vertex decimation, was introduced in 1992 by William Schroeder. It consists in choosing the lowest point with a weight according to some metrics weight point. Then there is a removal of the selected item and all adjacent triangles. Finally, there is the creation of new triangles (the so-called retriangulation) in place resulting holes. The principle is illustrated in next image

Vertex decimation

On the left is the original triangular network, which point Vr was evaluated as the least important, so it has been removed (and all adjacent triangles V1V2Vr, V2V3Vr, etc.). At this point is a hole between points V1-V6, therefore must be added 4 new triangles to patch it.

Polygon reduction by vertex decimation

The number of possible combinations to fill the holes created by new triangles is given by the formula below, where C(i) is the possibility of a combination of filling the hole with a+2 parties. Combining fill many holes and there may be a problem of them quickly select the most appropriate.

C(i)=(2i!)/((i+1)! * i!)

Vertex clustering

This algorithm (also known as Cell collapse) is described by J. Rossignac. The process of simplification is based on that around the object is created a grid. All the points in each cell of grid are united into a single point and all the edges that lead from one to another cell are merged into a single edge. This process is very quick, but there is a visible distortion of the object. Figure illustrates the principle of clustering peaks. On the left is the original object and the resulting law, which was crowding. It is seen that the final point may not be directly in the centre of cells, but it may be, for example, in a place where it is either the most important point, or may be calculated as the average weight of all the points in the cell.

Polygon reduction by vertex clustering

The quality of output depends on the resolution of grid, but even though it is very small. It is not possible to create output with pre-set number of triangles, because their number depends only on the size of grids. Alternatively, it may be the final point of the cells presented as the volume of space (voxelov graphics). This altgorithm was originally designed to simplify the models created in CAD for visualization.

Triangle collapse

This method is selecting the least important VaVbBc triangle and all these points joins into single one. For each transaction occurs to a remove 4 triangles, 6 edges and 3 points. The new point is either one of the Va, Vb, Vc, or any point within the original triangle. The principle of algorithm elimination of the triangle is shown in next figure.

Triangle collapse polygon reduction

If gray triangle is chosen by the removing algorithm as least important, algorithm removes the adjacent triangles at the same time. These are marked green. Operation Triangle removal is equivalent to the removal of two edges, but the calculation is faster and also needs to calculate less memory.

Vyšlo 23.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