Quad Layout Generation And Optimization Via Divide-and-Conquer Schemes

A quadrilateral is an important object of geometry processing algorithm research.It has been widely used in the field of geometry processing:in texture mapping,the texture is generally stored as a rectangular matrix composed of M x N rectangular pixels;in the mesh processing,the quad mesh has developed rapidly in recent years,and has excellent properties beyond the triangle mesh in many fields...and these applications often have higher requirements for the quad layout.The so-called quad layout means that some quads form a whole according to a specific arrangement.The geometry(position,size,shape,etc.)and topology(adjacent relationship among points,lines,and surfaces,etc.)of these quads will significantly affect the whole property.The quad layout is determined by the requirements in different applications to achieve the best results.This paper mainly studies the quad layout problem in two aspects:the texture atlas packing problem and the quad mesh reconstruction problem.For these two types of issues,new quad layout generation and optimization algorithms are proposed.In the past,many algorithms dealing with these two problems could only get good results for a specific type of data,and it is difficult to adapt to a wide range of input models.For atlas generation and quad mesh reconstruction problems,this paper proposes algorithms based on region segmentation.By segmenting complex input into relatively local simple quad regions,a better solution is obtained for these local regions by dividing and conquering,and the algorithm has high robustness.The most significant of the algorithms proposed in this paper is that even if the input model is very complex,this paper can disassemble the input into simple sub-models.While simplifying the input,they ensure that the better solution of the sub-models can always result in the better solution of the original input.This avoids the problem that many algorithms in the past have difficulty dealing with various conflicting requirements when faced with multiple inputs.The first work of this paper is a good algorithm which solves the atlas packing problem.The requirements of atlas packing include a high space utilization rate,short total border length,and low distortion before and after packing.The state-of-the-art algorithm before this algorithm meets the above requirements by straightening the boundary of the input model into axis alignment,dividing the straightened result into rectangles,then packing the rectangles and performing distortion reduction optimization.This algorithm gets the result with a tight rectangle layout.However,the condition of straightening into axis alignment is too strong in many cases and cannot be satisfied in theory,leading to failures in many examples.This method improves the above algorithm,relaxes the strict axis alignment requirement,and only straightens the input model to approximate axis alignment.On this basis,this method proposes an innovative segmentation scheme for the approximate axis-aligned model,which can robustly divide the approximate axis-aligned model into a series of approximately rectangular blocks and then transform these blocks into rectangles and packing them.Compared with the previous algorithm,this algorithm dramatically improves the robustness while meeting the basic requirements of atlas packing.In the experiment,the previous algorithm failed about one-eighth of the examples,and our method was successful for all inputs.The quality of our results was comparable to the previous algorithm,which proved the effectiveness of this method.In the second work of this paper,we propose a high quality quad mesh generation algorithm for planar domains.For a quad mesh,many applications often require simplicity in its layout.That is,the regions divided by the singular vertices of the quad mesh should be as simple as possible.Compared with triangle meshes,quad meshes with good quality are more suitable as parameter domains to construct various interpolation functions.In the finite element method,when the quad mesh and the triangle mesh reach the same accuracy,the number of elements of the quad mesh is smaller.However,the existing algorithms for generating quad meshes are challenging to meet the following requirements at the same time:simple quad layout structure,high quality and no flipped elements,the scale of the quads are close to the value specified by the user,and the features of the input model can be maintained.To this end,this paper proposes a new algorithm,which can generate a quad mesh that meets the above requirements for the input model of a plane region.The idea of this method is derived from the first work.The basic idea is to decompose the complex input mesh into simpler sub-models through segmentation,and decompose complex problems into simpler sub-problems,divide and conquer.The whole algorithm is mainly divided into four parts:first,the input model is processed by a new algorithm to straighten the boundary,and a model with more straightforward boundary is obtained,and the distortion and bijection are kept low when straightening;then,an innovative segmentation method is used to divide the model into sub-models with simple shapes;each sub-model is quadrilateralized by the proposed template-based quadrilateralization method;finally,these sub-quad meshes are spliced together,and the layout is simplified and optimized to obtain the final quad mesh.Experimental results show that the quad mesh generated by this algorithm can meet the given requirements,and the algorithm is robust,and all inputs are successfully executed.In the third work of this paper,we propose a simplification algorithm for curved quad meshes.When the quadrilateralization problem is extended to meshes in threedimensional space,it is difficult to copy the segmentation method mentioned above directly.This is because the shape of the mesh is more complex,and its surface undulates in a three-dimensional space.It is difficult to find the curve on the surface of the model to divide the model into simple regions.The existing algorithms can generate quad meshes with high geometric quality,but the result has a more complicated layout and more singular points.Based on the above facts,this paper proposes an algorithm that simplifies the input quad mesh with a complex layout and reduces singular points.The method consists of three main steps:(1)find a region with many singular points on the input mesh through an innovative method.The region is as flat as possible and the boundary is as smooth as possible.(2)Some boundary points of the region are selected as corners,and an existing method is used to generate a new sub-quad mesh that matches the boundary of the region,and the sub-quad mesh has a simple layout.(3)The sub-quad mesh is projected back to the original surface and the quality is optimized to obtain the final result.The experimental surface,this method can significantly reduce the number of singular points of the quad mesh,and maintain a high quad quality and the features of the original mesh.