DOC PREVIEW
Duke CPS 296.1 - Surface Simplification

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

II.4 Surface Simplification 37II.4 Surface SimplificationIn applications it is often necessary to simplify the data or its representation.One reason is measurement noise, which we would like to eliminate, anotherare features, which we look for at various levels of resolution. In this section,we study edge contractions used in simplifying triangulated surface models ofsolid shapes.Edge contraction. Suppose K is a triangulation of a 2-manifold withoutboundary. We recall this means that edges are shared by pairs and vertices byrings of triangles, as depicted in Figure II.9. Let a and b be two vertices andab the connecting edge in K. By the contraction of ab we mean the operationthat identifies a with b and removes duplicates from the triangulation. Callingthe new vertex c, we get the new triangulation L from K by• removing ab, abx, and aby;• substituting c for a and for b wherever they occur in the remaining set ofvertices, edges, and triangles;• removing resulting duplications making sure L is a set.As a consequence of the operation, there are new incidences between edges andtriangles that did not exist in K; see Figure II.9.ba cyxyxFigure II.9: To contract ab we remove the two dark triangles and repair the hole bygluing their two left edges to their two right edges.Algorithm. To simplify a triangulation, we iterate the edge contraction op-eration. In the abstract setting any edge is as good as any other. In a practical38 II Surfacessituation, we will want to prioritize the edges so that contractions that preservethe shape of the manifold are preferred. To give meaning to this statement,we will define shape to mean the topological type of the surface as well asthe geometric form we get when we embed the triangulation in R3. We willdiscuss the latter meaning later and for now assume we have a function thatassigns to each edge ab a real number Error(ab) assessing the damage thecontraction of ab causes to the geometric form. Small non-negative numberswill mean little damage. To write the algorithm, we assume a priority queuestores all edges ordered by the mentioned numerical error assessment. The pro-cedure MinExtract removes the edge with minimum error from the priorityqueue and returns it. Furthermore, we assume the availability of a boolean testisSafe that decides whether or not the contraction of an edge preserves thetopological type of the surface.while priority queue is non-empty doab = MinExtract;if isSafe(ab) then contract ab endifendwhile.Some modifications are necessary to recognize edges that no longer belong tothe triangulation and to put edges back into the priority queue when theybecome safe for contraction. Details are omitted. The running time of the al-gorithm depends on the size of local neighborhoods in the triangulation and onthe data structure we maintain to represent it. Under reasonable assumptionsthe most time-consuming step is the maintenance of the priority queue, whichfor each step is only logarithmic in the number of edges.Topological type. We now consider the question whether or not the con-traction of an edge preserves the topological type. Define the link of an edgeab as the set of vertices that span triangles with ab, and the link of a vertexa as the set of vertices that span edges with a and the set of edges that spantriangles with a,Lk ab = {x ∈ K | abx ∈ K};Lk a = {x, xy ∈ K | ax, axy ∈ K}.Since the topological type of K is that of a 2-manifold without boundary, eachedge link is a pair of vertices and each vertex link is a closed curve made ofedges and vertices in K. Let L be obtained from K by contracting the edge ab.We slightly abuse language by blurring the difference between a triangulationand the topological space it triangulates.II.4 Surface Simplification 39Link Condition Lemma. The triangulations K and L have the same topo-logical type iff Lk ab = Lk a ∩ Lk b.In other words, the topological type is preserved iff the links of a and b intersectin exactly two points, namely the vertices x and y in the link of ab, as in FigureII.9.Proof. We have Lk ab ⊆ Lk a, Lk b, by definition. The only possible violationto the link condition is therefore an extra edge or vertex in the intersectionof vertex links. If Lk a and Lk b share an edge then the contraction of abcreates a triangle sticking out of the surface, contradicting that L triangulatesa 2-manifold. Similarly, if the two vertex links share a vertex z 6∈ Lk ab thenthe contraction of ab creates an edge cz that belongs to four triangles, againcontradicting that L triangulates a 2-manifold.a bcFigure II.10: Mapping the neighborhood of c in L to a triangulated polygon andoverlaying it with a similar mapping of the neighborhoods of a and b in K.To prove the other direction, we draw the link of c in L as a convex polygon inR2; see Figure II.10. Using Tutte’s Theorem from Chapter I, we can decomposethe polygon by drawing the triangles incident to c in L. Similarly, we candecompose the polygon by drawing the triangles incident to a or b in K. Wesuperimpose the two triangulations and refine to get a new triangulation, ifnecessary. The result is mapped back to K and to L, effectively refining theneighborhoods of a and b in K and that of c in L. The link of c and everythingoutside that link is untouched by the contraction. Hence on an outside thelink K and L are the same and inside the link K and L are now isomorphicby refinement. It follows that K and L are isomorphic and therefore have thesame topological type.40 II SurfacesSquare distance. To talk about the geometric meaning of shape we nowassume that K is embedded in R3, with straight edges and flat triangles. Todevelop an error measure we use the planes spanned by the triangles. Lettingu ∈ S2be the unit normal of a plane h and δ ∈ R its off-set, we can write h asthe set of points p ∈ R3for which hp, ui = −δ. Using matrix notation for thescalar product the signed distance of a point x ∈ R3from h isd(x, h) = (x − p)T· u = xT· u + δ.Defining xT= (xT, 1) and uT= (uT, δ) we can write this as a four-dimensionalscalar product, xT· u. We use this to express the sum of square distances froma set of planes in matrix form. Letting H be a finite set of planes, this gives afunction EH: R3→ R defined byEH(x) =Xhi∈Hd2(x, hi)=Xhi∈H(xT· ui)(uTi· x)= xT· Xhi∈Hui· uTi!· x.Hence EH(x) = xT· Q · x, whereQ =Xhi∈H(ui· uTi) =A P Q UP B R VQ R C WU V W Zis a symmetric, four-by-four matrix we


View Full Document

Duke CPS 296.1 - Surface Simplification

Documents in this Course
Lecture

Lecture

18 pages

Lecture

Lecture

6 pages

Lecture

Lecture

13 pages

Lecture

Lecture

5 pages

Load more
Download Surface Simplification
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Surface Simplification and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Surface Simplification 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?