Page - 179 - in Proceedings - OAGM & ARW Joint Workshop 2016 on "Computer Vision and Robotics“

normal vector voting. Therefore the dot products of consecutive pairs of {nˆ5, ..,nˆ9} is computed, wherevaluesof≈1 indicateflatparts. Thecolormaprepresents thedistance to thexy-plane toshow the three-dimensional nature of the1-ring. Figure 1b shows that the neighboringverticesp4 andp1 are added to the simplifiedmeshcreatinga slight artificial valley togenerally avoidflat areashaving nogradientdirection. The thresholddetermining if thesedotproducts are≈1 is called �and it is the onlyparameter tobesetby theuser. The first vertex is stored in the listLgroupwith label ID 0. For each �nˆi,nˆj�within the range � to the previous entry thenpjwill be added toLgroupwith the same label ID. If not, the label ID will be incremented before inserting the item. The algorithm continues until all verticespj in the 1-ring are processed. When all items are processed, the dot product of thefirst and last entry of the adjacent vertices list needs to be compared because they are contiguous. If the condition to group the two vertices is met, the label ID of all elements with the current label is changed to 0. Now all adjacent vertices are traversed and a newvertex is created for every label, which is assigned the averagefunctionvalue,positionvectorandnormalvectorof thecorrespondingvertices. Thegrouping process isequivalent toa run-lengthencoding. InFigure1b, this results in thenewvertexp�which is theaverageofverticesp5 top9. The reduced1-ringhas tocontainat least3vertices tobeamanifold otherwisepi is not further considered to be amaximum. In casepi is a border vertex theminimum amountof requiredvertices in the1-ring is2. pi p1 p2p3 p4 p5 p6 p7 p8 p9 (a) pi p� p1 p2p3 p4 (b) high low Figure 1: Example of themesh simplification process. (a) The contiguous verticesp5 top9 lie on a plane. (b)The related facesbetweenverticeshavebeengrouped, resulting in thenewvertexp�. 2.2. Principaldirectionof thegradientvaluef(·) Analogously to theCannyalgorithm,wehave tocompute theprincipaldirectiontof thegradient.As we typically use theMSII-filter for f(pi), we have to use the normals to detect t and its orthogonal secondarydirectionb. To achieve this, the dot product �nˆi,nˆj� is computed. Thevertexpjwith the largest dot product is the principal direction t and is saved for later computations. This is illustrated inFigure2awith t=p�−pi. InFigure2b±b=±t× nˆi is shown. Thenormal, theprincipal, and the secondarydirectionspanaFrenet-Serret frame (TNBframe)with theplanesτnt andτnb. According toCannyweneed thegradient valuespandqon the secondarydirections±b. Theseare foundon the intersectionspjk :=τbt∩ejk andplm :=τbt∩elm. Tocomputef(pjk)weinterpolate linearbetween the twoverticespj andpkwith the respective functionvaluesf(pj)andf(pk). 179