Scalar multivariate subdivision schemes and box splines

We study scalar d-variate subdivision schemes, with dilation matrix 2I, satisfying the sum rules of order k. Using the results of Möller and Sauer, stated for general expanding dilation matrices, we characterize the structure of the mask symbols of such schemes by showing that they must be linear combinations of shifted box spline generators of some polynomial ideal. The directions of the corresponding box splines are columns of certain unimodular matrices. The ideal is determined by the given order of the sum rules or, equivalently, by the order of the zero conditions.The results presented in this paper open a way to a systematic study of subdivision schemes, since box spline subdivisions turn out to be the building blocks of any reasonable multivariate subdivision scheme.As in the univariate case, the characterization we give is the proper way of matching the smoothness of the box spline building blocks with the order of polynomial reproduction of the corresponding subdivision scheme. However, due to the interaction of the building blocks, convergence and smoothness properties may change, if several convergent schemes are combined.The results are illustrated with several examples.     

Calculating with box splines

Box splines are multivariate splines over regular grids. Two recursion formulas for box splines are developed: (1) a Mansfield-de Boor-like expression of box splines as linear combinations of box splines of lower degree and (2) a deBoor-like reduction of the net of box spline control points. The ideas follow those from the paper by deBoor in 1972. The proofs are geometrical and simple.     

A new quadratic and biquadratic algorithm for curve and surface estimation

A new deterministic quadratic parametric algorithm is introduced for curve estimation. A parametric biquadratic algorithm for surface estimation, based on the one for curve estimation is also presented. Our algorithm does not assume that the surface to be estimated, based on a given set of data in the three-dimensional space, has a continuous first derivative, nor does it assume that the data satisfy the assumption of stationarity or the intrinsic hypothesis. The grid formed by the given data does not have to be equidistant; in other words the distance between neighboring points in the two-dimensional domain does not have to be the same. Also since the algorithm leads to parametric equations for the patches of the surface, the estimating surface does not need to be a function. Appropriate parameters are introduced in the blending functions of the parametric equations to produce tension. The algorithm does not require inversion of matrices and is faster than splines and kriging. The estimated surface passes through the given data points. Error analysis based on estimating surfaces of known functions from a sample of data and then comparing to their value, are made. A comparison with biqubic natural splines based on data generated from known functions is also given.     

Rapid and Accurate Contact Determination between Spline Models using ShellTrees

In this paper, we present an efficient algorithm for contact determination between spline models. We make use of a new hierarchy, called ShellTree , that comprises of spherical shells and oriented bounding boxes. Each spherical shell corresponds to a portion of the volume between two concentric spheres. Given large spline models, our algorithm decomposes each surface into Bézier patches as part of pre-processing. At runtime it dynamically computes a tight fitting axis-aligned bounding box across each Bézier patch and efficiently checks all such boxes for overlap. Using off-line and on-line techniques for tree construction, our algorithm computes ShellTrees for Bézier patches and performs fast overlap tests between them to detect collisions. The overall approach can trade off runtime performance for reduced memory requirements. We have implemented the algorithm and tested it on large models, each composed of hundred of patches. Its performance varies with the configurations of the objects. For many complex models composed of hundreds of patches, it can accurately compute the contacts in a few milliseconds.     

Least Committed Splines in 3D Modelling of Free Form Objects from Intensity Images

Generating 3D models of objects from video sequences is an important problem in many multimedia applications ranging from teleconferencing to virtual reality. In this paper, we present a method of estimating the 3D face model from a monocular image sequence, using a few standard results from the affine camera geometry literature in computer vision, and spline fitting techniques using a modified non parametric regression technique. We use the bicubic spline functions to model the depth map, given a set of observation depth maps computed from frame pairs in a video sequence. The minimal number of splines are chosen on the basis of the Schwartz's Criterion. We extend the spline fitting algorithm to hierarchical splines. Note that the camera calibration parameters and the prior knowledge of the object shape is not required by the algorithm. The system has been successfully demonstrated to extract 3D face structure of humans as well as other objects, starting from their image sequences.     

非均匀三次参数样条曲线的能量最优光顺算法

1996年,Poliakoff提出了一种具有广泛应用背景的的光顺算法,该算法将Kjellander算法推广到非均匀三次参数样条曲线的情形,但忽视了对坏点切向量的修改,而坏点切向量有时会严重影响光顺效果．据此,提出了同时修改坏点位置和切向量算法,导出了光顺算法的显式公式,并且证明了该算法是能量最优的;还指出Poliakoff算法是文中算法的一种特例．大量的数值例子表明,文中算法具有很好的光顺效果,具有良好的应用前景．     

一种快速的可变形物体的碰撞检测算法

为实现虚拟环境中可变形物体与刚体间实时的碰撞检测,提出了一种快速的基于混合包围盒层次结构的并行碰撞检测算法。算法充分利用包围盒在检测速度和精度上的不同侧重,对可变形物体建立Sphere和AABB混合包围盒层次树,对刚体建立Sphere和OBB混合包围盒层次树;每个物体的混合包围盒层次树又分成上层、中层和下层,每层使用不同的包围盒;在碰撞检测遍历时,上层使用Sphere和Sphere相交检测快速排除不相交物体,在中层使用Sphere和OBB的相交检测进一步排除物体相交的可能性,在下层使用AABB和OBB的相交检测较精确地确定物体是否相交;采用多线程技术,在多核设备上实现并行碰撞检测算法。实验结果表明,与经典的AABB算法相比较,该算法在效率方面具有明显优势,能够满足可变形物体与刚体的碰撞检测要求。     

导弹飞行视景仿真中的碰撞检测算法

针对导弹飞行视景仿真中碰撞检测实时性与精确性的不足,提出了一种优化的混合包围盒碰撞检测算法.该算法在包围盒树的上层使用Sphere,下层使用OBB;将该算法在导弹飞行视景仿真系统中实现后,分别与相交矢量碰撞检测算法、OBB包围盒算法进行对比试验和分析.结果表明,这种混合包围盒算法能够有效地提高导弹飞行视景仿真中碰撞检测的实时性与精确性.     

Android手持设备游戏中的碰撞检测算法研究

针对Android手持终端中复杂游戏场景的碰撞检测需求,提出了一种基于包围球和AABB的实时碰撞检测算法。该算法针对不同的虚拟对象构建不同的包围盒,并将改进后的包围盒投影排序分组方法应用其中。将该算法与使用包围盒投影排序分组方法的包围球算法与AABB算法比较,实验表明,该算法在保持更高精度的前提下仍能满足复杂场景中实时碰撞检测的要求。     

基于二分内包围盒的玉米光照逆光线跟踪算法

为了在玉米仿真中构建逼真有效的光环境,提出一种基于二分内包围盒的玉米光照逆光线跟踪算法。首先,在玉米表面建立二分内包围盒进行预处理,减少光线与玉米相交运算量;其次,引入遮挡因子简化光能计算的复杂度;最后,通过调整光能阈值达到光环境逼真度和算法效率的统一。为了验证算法的快速有效性,建立玉米模型,对比不同包围盒求交运算的速率,得出二分内包围盒的求交速度最快,逆光线跟踪算法模拟出的玉米生长效果较为逼真。     

Suboptimal minimum cluster volume cover-based method for measuring fractal dimension

A new method for calculating fractal dimension is developed in this paper. The method is based on the box dimension concept; however, it involves direct estimation of a suboptimal covering of the data set of interest. By finding a suboptimal cover, this method is better able to estimate the required number of covering elements for a given cover size than is the standard box counting algorithm. Moreover, any decrease in the error of the covering element count directly increases the accuracy of the fractal dimension estimation. In general, our method represents a mathematical dual to the standard box counting algorithm by not solving for the number of boxes used to cover a data set given the size of the box. Instead, the method chooses the number of covering elements and then proceeds to find the placement of smallest hyperellipsoids that fully covers the data set. This method involves a variant of the Fuzzy-C Means clustering algorithm, as well as the use of the Minimum Cluster Volume clustering algorithm. A variety of fractal dimension estimators using this suboptimal covering method are discussed. Finally, these methods are compared to the standard box counting algorithm and wavelet-decomposition methods for calculating fractal dimension by using one-dimensional cantor dust sets and a set of standard Brownian random fractal images.     

Smoothing of cubic parametric splines

The most common curve representation in CADCAM systems of today is the cubic parametric spline. Unfortunately this curve will sometimes oscillate and cause unwanted inflexions which are difficult to deal with. This paper has developed from the need to eliminate oscillations and remove inflexions from such splines, a need which may occur for example when interpolating data measured from a model. A method for interactive smoothing is outlined and a smoothing algorithm is described which is mathematically comparable to manual smoothing with a physical spline.     

YOLO-wLU：考虑定位不确定性的目标检测算法

YOLOv3目标检测算法在检测目标时没有考虑边界框坐标定位存在的不确定性,因此有时不能得出正确的检测结果。针对此问题,提出YOLO-wLU（YOLO with Localization Uncertainty）算法。该算法借鉴深度学习中的不确定性思想,使用高斯分布函数建立边界框坐标的概率分布模型以考虑边界框坐标定位不确定性;设计新的边界框损失函数,在检测过程中移除定位不确定性较大的检测结果;通过融合周围边界框坐标信息提高了边界框坐标辨识结果的准确性。实验结果表明,该算法可有效减少误报率,提高检测精度;COCO数据集上测试结果显示,相比YOLOv3算法,该算法的mAP最高可提升4.1个百分点。     

Multidimensional Spline Interpolation: Theory and Applications

Computing numerical solutions of household’s optimization, one often faces the problem of interpolating functions. As linear interpolation is not very good in fitting functions, various alternatives like polynomial interpolation, Chebyshev polynomials or splines were introduced. Cubic splines are much more flexible than polynomials, since the former are only twice continuously differentiable on the interpolation interval. In this paper, we present a fast algorithm for cubic spline interpolation, which is based on the precondition of equidistant interpolation nodes. Our approach is faster and easier to implement than the often applied B-Spline approach. Furthermore, we will show how to loosen the precondition of equidistant points with strictly monotone, continuous one-to-one mappings. Finally, we present a straightforward generalization to multidimensional cubic spline interpolation.      

基于包围盒与碰撞的模型填充算法研究

为了将任意模型使用球体进行密实填充,提出了一种基于包围盒与碰撞的模型填充算法。该算法首先生成模型的轴对称包围盒;其次在包围盒内产生任意数量球体并进行刚体碰撞,碰撞后的球体将会在包围盒的范围内均匀分布;最后采用判断法线方向算法筛选出模型内部的球体并保留至最终结果。通过实例证明,该算法能够根据输入的球体填充数量及孔隙率快速生成模型内的紧密填充球体。该算法对于模型的适应性高,生成速度快,具有2,000万三角网格的模型仅需20秒即可生成内部填充球体,为生成点阵结构模型进一步奠定了基础。     

直线与Bzier曲面求交的分割迭代综合法

本文所介绍的适合光线跟踪算法的直线与B(?)zier曲面求交的方法,采用了空间一般位置的圆柱和长方体作为曲面包围盒,并综合利用了分割法的稳定性和牛顿迭代法的效率,从而加快了用光线跟踪技术生成Bzier曲面的真实感图形的速度。     

Subdivision algorithms for the generation of box spline surfaces

This paper proposes a general approach to subdivision algorithms used in interactive computer aided design for splines which are linear combinations of translates of any box splines. We show how these algorithms can be used for efficient generation of the corresponding spline surfaces. Our results extend several known special cases.     

不确定噪声下基于轴对称盒空间滤波的非线性系统状态估计

针对不确定噪声下的非线性系统状态估计问题, 本文提出了一种基于轴对称盒空间滤波的状态估计方法. 首先, 利用轴对称盒空间包裹线性化过程带来的误差项, 将状态函数线性化误差轴对称盒空间与噪声轴对称盒空间求取闵可夫斯基和, 得到干扰误差轴对称盒空间; 随后, 利用状态量、线性误差和测量噪声的轴对称盒空间的闵可夫斯基和, 得到系统状态预测集; 进而, 利用轴对称盒空间边界正交的性质, 将盒空间拆分为多组超平面, 构造测量更新的约束条件并得到集员包裹. 本文所提方法相比传统的椭球滤波方法而言, 降低了算法的复杂度, 减少了包裹状态可行集和线性化过程带来的余, 获得了更加紧致精确的系统状态集. 最后, 采用非线性弹簧–质量–阻尼器系统验证了本文所提算法的有效性.     

Homogeneous bounding boxes as tools for intersection algorithms of rational bézier curves and surfaces

In the divide-and-conquer algorithm for detecting intersections of parametric rational Bézier curves (surfaces), we use bounding boxes in recursive rough checks. In this paper, we replace the conventional bounding box with a homogeneous bounding box, which is projectively defined. We propose a new rough check algorithm based on it. One characteristic of the homogeneous bounding box is that it contains a rational Bézier curve (surface) with weights of mixed signs. This replacement of the conventional bounding box by the homogeneous one does not increase the computation time.