دانلود مقاله ISI انگلیسی شماره 26144
ترجمه فارسی عنوان مقاله

برنامه ریزی پویا چند بعدی در سطحی اتصالات قاعده مند

عنوان انگلیسی
Multi-dimensional dynamic programming in ruled surface fitting
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
26144 2014 11 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Computer-Aided Design, Volume 51, June 2014, Pages 39–49

ترجمه کلمات کلیدی
- اتصالات سطح قاعده مند - برنامه ریزی چند بعدی دینامیکی - ترکیب سطح به سطح - الگوریتم های -
کلمات کلیدی انگلیسی
Ruled surface fitting, Multi-dimensional dynamic programming, Surface–surface composition, GPU algorithms,
پیش نمایش مقاله
پیش نمایش مقاله  برنامه ریزی پویا چند بعدی در سطحی اتصالات قاعده مند

چکیده انگلیسی

Ruled surfaces play an important role in many manufacturing and construction applications. In this work, we explore a multi-dimensional dynamic programming based ruled surface fitting scheme to a given freeform rational surface, SS. Considering two initial opposite boundaries of SS, sampled into a discrete piecewise linear polyline representation, the ruled surface fitting problem is reduced to a pairing-search between the polylines and elevations above the polylines, in the normal directions of SS. A four-dimensional dynamic programming solution is sought for the four dimensions prescribed by the two polylines and the two elevation levels along the surface normals. This multi-dimensional dynamic programming is evaluated using highly parallel algorithms running on GPUs that ensures the best fit to the sampled data. In order to evaluate the fitting error with respect to SS, we derive a scheme to compute a bound from above on the maximal error between a bilinear surface patch (formed by two consecutive point-pairs) and its corresponding surface region on SS. Surface–surface composition is employed to extract the corresponding surface region on SS to compare against. Finally, the above ruled surface fitting approach is also extended into a discrete algorithm to find the non-isoparametric subdivision curve on SS when a discrete recursive piecewise-ruled surface fitting is considered. A five- or seven-dimensional dynamic programming solution is employed towards this end and once again, surface–surface composition is employed to extract the two subdivided patches as tensor products.

مقدمه انگلیسی

Ruled surfaces are widely used in many applications in manufacturing as well as civil engineering application. In manufacturing, while multi-axis CNC processes are well known, other manufacturing technologies, such as wire Electrically Discharged Machining (EDM) [1] and 5-axis CNC flanking milling [2], [3] and [4] are also in extensive use. In wire EDM, a conducting wire is discharging electricity against a conductive stock and evaporates and cuts ruling lines in the material. Tool side CNC machining (e.g., flank milling) exploits the linear edge of the rotating tool to similarly cut along a line after carefully considering the non-zero thickness of the tool. Interestingly enough, other manufacturing processes also cut along lines in 3D. Examples include CNC water jet cutting as well as laser cutting. In building construction, ruled surfaces are used for the realization of free-form architecture [5]. Recently, the use of hot wire cutting in styrofoam was also proposed towards mold making of surface tiles in architecture design [6]. Within all above applications, it is interesting that the following Ruled Surface Fitting (RSF) is still a highly investigated problem: Problem RSF. Given a parametric surface View the MathML sourceS(u,v), find the best ruled surface fit to View the MathML sourceS under some metric. A good solution to the above RSF problem would clearly increase the usability and quality of all aforementioned technologies for fabricating a given surface View the MathML sourceS by swept cutting lines. The accuracy of the resulting artifact would greatly benefit from such an optimal ruling fit. However, as a ruled surface is hyperbolic in general [7], one can expect that only a hyperbolic patch (or parabolic) View the MathML sourceS will benefit from such a ruled surface fitting. Forced to use a line-cutting based technology that constructs ruled surfaces, the benefits for elliptical surface regions cannot be significant. Nevertheless, one can still hope to find the optimal ruled surface fit to any surface View the MathML sourceS under this constrained manufacturing technologies. If multiple ruled surface patches may be tiled together, while fitting View the MathML sourceS, the solution of the best Ruled Surface Partitioning (RSP) problem is also highly desirable: Problem RSP. Given a parametric surface View the MathML sourceS, find the non-isoparametric partitioning of View the MathML sourceS into two sub-patches View the MathML sourceSL and View the MathML sourceSR (or more generally several sub-patches), that is best fitted by two (several) piecewise ruled surfaces, minimizing some metric in RSF. Finding the global optimum for RSF and RSP is difficult; unlike the prior work based on numerical optimization, this paper presents a ruled surface fitting scheme for solving the RSF and RSP problems in the discrete domain formed by sample points. The scheme finds an optimal ruled surface fitting once the discrete piecewise linear sampled sets of the boundaries of View the MathML sourceS and the possible elevation (again discrete) of these points along the local normal of View the MathML sourceS, are given. Each discrete ruling line is defined through two elevated sampled points on two opposite boundaries. The elevation is along the normal of View the MathML sourceS and is also discretized. Two consecutive ruling lines above the discrete sampled point set define a bilinear surface patch View the MathML sourceB for which the corresponding patch of View the MathML sourceS, View the MathML sourceSb, is extracted using a surface–(bilinear) surface composition. An upper bound on the Hausdorff distance between View the MathML sourceB and View the MathML sourceSb is established by computing a bound on View the MathML source‖B(u,v)−Sb(u,v)‖. A four-dimensional dynamic programming problem is defined for all possible pairs of points and all possible allowed elevations. The best ruling fit to this discrete arrangement is then determined by solving a four-dimensional dynamic programming (4D-DP). A simple example can be seen in Fig. 1. The DP algorithm has two phases. First a multi-dimensional table is computed for all possible pairing and elevations, a 4D table in this case. Then, path tracking is conducted from the source (the first ruling line at the beginning of the two boundaries) to the destination (the last ruling line at the end of the two boundaries). Special treatment must be made for the end conditions as the first and last ruling lines can be in arbitrary elevations. Further, if View the MathML sourceS is a periodic surface, the first and the last ruling lines must be the same ruling line. Full-size image (31 K) Fig. 1. An example of (multi-dimensional) dynamic programming (DP) based ruled surface fitting: (a) the given freeform surface SS, (b) the fitted ruled surface interpolating the boundary curves of View the MathML sourceS (which is obtained by [8]—a 2D-DP with 50×50 sampled points), and (c) the ruled surface fitting by also elevating sampled points along the normal of View the MathML sourceS (which is solved using a 4D-DP with 504 samples). The 4D-DP based ruled surface fitting reduces the Hausdorff distance error by 32.8% compared to the 2D-DP based ruled surface fitting. Figure options Both DP steps are of a complexity order that depends on the dimension of the built table. If each side of the table is of length nn, the 4D-DP has complexity of O(n4)O(n4). However, the computation of each entry in the table requires an upper bound on the Hausdorff distance of View the MathML source‖B(u,v)−Sb(u,v)‖ and the construction time of the DP table governs the entire computation costs. Therefore, we employ highly parallel algorithms running on Graphics Processing Units (GPUs) to speed up the construction of the DP table. 1.1. Related work To approximate a general surface, View the MathML sourceS, by ruled surface(s) View the MathML sourceRi, View the MathML sourceS can be divided recursively into strips along isoparametric directions, as in [2], and then each of the strips is fitted with a ruled surface. In [9], a surface subdivision with similar ruled surface fitting goals is made but along isophotes, which bounds the normal deviations but not the maximal deviation between View the MathML sourceS and View the MathML sourceRi. In both cases, the algorithm is greedy and the RSF/RSP computations are not optimal. Approximation of a general surface using ruled surfaces is also considered in [10] by solving a non-linear optimization function that minimizes distances between the tangent planes of the original surface and the fitted ruled surface over the domain. The special case of a surface of revolution is also considered in [10], exploiting fitted hyperboloid of one sheet that are ruled surfaces. Some work on fitting ruled surfaces was also done by using a curve representation on the dual Gaussian sphere of a surface (Refs. [11], [12] and [13]). The research of [14] and [5] focuses on using continuous non-linear optimization methods to solve the RSF problem over sampled point sets from the input surface View the MathML sourceS. They conducted a sequence of quadratic programs to solve the optimal surface problem by the Squared Distance Minimization (SDM) [15] and applications in architecture has been demonstrated. A given surface is divided into strips in [14] by the asymptotic curves computed from the level-set of field of asymptotic directions—tangents to the intersection curves between the input surface and the tangent plane at a surface point. Overall, the result has not Hausdorff distance guarantee to/from the original input surface. Further, this is different from our method, were we tackle the RSP problem in a discrete domain. While not much can be found on ruled surface fitting to general surfaces, there is also a large body of research on piecewise developable surface fitting to general surfaces [16], [17], [18], [19], [20], [21], [22], [23] and [24]. Developable surfaces are a special type of ruled surfaces. In [17] and [20], the input general surface is first divided into strips (along isoparametric curves in [17]), which are then fitted with developable surfaces. Although polygonal meshes are not in the scope of this work, the construction of ruled and developable sheets for a mesh representation has captured much attention. Wang and Tang [8] introduced a fitting of a polygonal strip to a ruled surface and employs the shortest path algorithm to find a best fitting on a graph scored by the fitting error, which is in fact a 2D-DP. The resultant polygonal strips interpolate the boundary curves of the given surface View the MathML sourceS, ending up in a larger fitting error (see Fig. 1 as an example). Mesh surfaces are also processed in [22] and [21] under nonlinear optimization framework into shapes that converge to developable surfaces. In [19], the mesh is divided into polygonal strips and each strip is then laid out flat as a developable sheet. In [18], the mesh model is first decomposed into cylindrical shapes that are then fitting with developable sheets. Other segmentation methods for using developable mesh surface to approximate a given freeform surface can be found in [25]. 1.2. Contributions We present algorithms for solving the RSF and the RSP problems in a discrete domain formed by sampling points over freeform input surfaces. The main contributions of our work include: – An approach is introduced to find the best ruled surface fitting for a discrete, piecewise linear, sampled set of a given general freeform surface, using a four-dimensional dynamic programming scheme. – A method is presented to provide a guaranteed yet fairly tight upper bound on the Hausdorff distance between the bilinear patch formed out of two adjacent ruling lines and the corresponding region in the input surface View the MathML sourceS. – GPU-based algorithms are employed to speed up the evaluation of multi-dimensional DP table. – The presented ruled surface fitting approach based on dynamic programming is also extended to solve the RSP problem by a 5D-DP–7D-DP (which allows to elevate boundary curves). A locally-optimal partitioning curve can be determined for a given surface, View the MathML sourceS, so two ruled surfaces can be fitted to the two subdivided patches, while minimizing some fitting error metric. The rest of the paper is organized as follows. We present the multi-dimensional DP based method for solving the RSF problem in Section 2, with a guaranteed bounds on the Hausdorff error. The GPU-based algorithms for speeding up the computation are introduced in Section 3. The extension of this multi-dimensional DP technique to compute a solution to the RSP problem is derived in Section 4. Examples and performance evaluations of our approach are described in Section 5. Finally, we conclude in Section 6. Acronyms will be used in the rest of this paper—a summary is given in Table 1. Table 1. Summary of acronyms. Acronyms Full description RSF Ruled surface fitting RSP Ruled surface partition DP Dynamic programming GPU Graphics processing units LSAD Line–surface approximate distance SSHB Surface–surface Hausdorff-distance bound VD Voronoi diagram

نتیجه گیری انگلیسی

In this work, we presented a method to compute an optimal set of ruling lines to solve the discrete RSF problem. Multi-dimensional dynamic programming is conducted to find the global optimum in a discrete domain. We sampled the boundary curves of a given surface and elevate them along surface normals. The discrete domain has four degrees-of-freeform for solving the RSF problem and is formulated over these samples. In our current implementation, the discrete domains are formed by the sample points on View the MathML sourceS(u,vmin) and View the MathML sourceS(u,vmax) and the points evaluated along surface normals on these two curves. One may wish to generate the discrete domain on other iso-parametric curves (e.g., View the MathML sourceS(u,vmin+Δ) and View the MathML sourceS(u,vmax−Δ)). However, by allowing normal deviation, the 4D-DP sampled space subsumes the space of samples covered by sampling between View the MathML sourceS(u,vmin+Δ) and View the MathML sourceS(u,vmax−Δ). Our current implementation computes the optimal ruling approximation to periodic surfaces by using the line–surface metric. To employ the better SSHB, we need to overcome the (technical) difficulty of computing the composition across the boundary of S(u,v)S(u,v). A possible solution can first split the u,vu,v patch when it crosses the boundary, divide the split regions into rectangles and compute the composition for the divided pieces. In the future, we will work on how to incorporate the manufacturing constraints (e.g., collision between the cutter and the workpiece) into the procedure of optimal fitting.