Circle(Sphere)Group Approximation Algorithm For Irregular Shapes And Its Applications

Using simple primitives to represent irregular shapes,with a desired degree of approximation,is very helpful in many applications of computer graphics.We propose a circle group approximation algorithm based on straight skeletons,and a sphere group approximation algorithm based on medial faces.The aim is to generate an efficient representation of irregular shapes,considering the approxi-mation error and the resulting complexity,i.e.the number of circles(spheres).Both circle and sphere group approximation algorithms have a consistent process.First,we extract the medial axis of the model.Then we determine the centers and the radii of the initial circles(spheres),according to the length of the medial axis,and the distance between the medial axis and the model.Finally,we set two controllable parameters,the users can get a variety of results as required.The circle group approximation algorithm can generate a circle group inside the polygon entirely.It can also generate a circle group covers the polygon completely or partially by polygon offsetting.Compared with the existing circle group approximation algorithms,ours can control the maximum length of the circle protruding the polygon and the number of circles in the results,and shows great flexibility.In comparison experiments with others,ours achieves higher accuracy with fewer circles,reflecting its su-periority.Although our sphere group approximation algorithm only generates approximation results,it fits the original model tighter than others,laying a solid foundation for further study of sphere covering problems.In the end,we apply algorithms to the mosaics synthesis and the 3D packing problem respectively,which leads to efficient solutions of these two problems.They can avoid getting stuck at bad local minima when using the original shapes during the optimization process and obtain good results with stability.