Computing surfaces invariant under subdivision

In this paper, we propose a general subdivision algorithm for generating surfaces. The algorithm has as motivation our earlier work on the design of free form curves where similar ideas were investigated. Here we describe some properties of uniform refinement algorithms for surface generation. A detail analysis of their properties will be given later by one of us.     

Education-driven research in CAD

We argue for a new research category, named education-driven research (EDR), which fills the gap between traditional field-specific research that is not concerned with educational objectives and research in education that focuses on fundamental teaching and learning principles and possibly on their customization to broad areas (such as mathematics or physics), but not to specific disciplines (such as CAD). The objective of EDR is to simplify the formulation of the underlying theoretical foundations and of specific tools and solutions in a specialized domain, so as to make them easy to understand and internalize. As such, EDR is a difficult and genuine research activity, which requires a deep understanding of the specific field and can rarely be carried out by generalists with primary expertise in broad education principles. We illustrate the concept of EDR with three examples in CAD: (1) the Split and Tweak subdivisions of a polygon and its use for generating curves, surfaces, and animations; (2) the construction of a topological partition of a plane induced by an arbitrary arrangement of edges; and (3) a romantic definition of the minimal and Hausdorff distances. These examples demonstrate the value of using analogies, of introducing evocative terminology, and of synthesizing the simplest fundamental building blocks. The intuitive understanding provided by EDR enables the students (and even the instructor) to better appreciate the limitations of a particular solution and to explore alternatives. In particular, in these examples, EDR has allowed the author to: (1) reduce the cost of evaluating a cubic B-spline curve; (2) develop a new subdivision curve that is better approximated by its control polygon than either a cubic B-spline or an interpolating 4-point subdivision curve; (3) discover how a circuit inclusion tree may be used for identifying the faces in an arrangement; and (4) rectify a common misconception about the computation of the Hausdorff error between triangle meshes. We invite the scientific community to encourage the development of EDR by publishing its results as genuine research contributions in peer-reviewed professional journals.     

Second-order accurate constraint formulation for subdivision finite element simulation of thin shells

We present a new method for enforcing boundary conditions within subdivision finite element simulations of thin shells. The proposed framework is demonstrated to be second-order accurate with respect to increasing refinement in the displacement and energy norm for simply supported, clamped, free and symmetric boundary conditions. Second-order accuracy on the boundary is consistent with the accuracy of subdivision-based approaches for the interior of a body. Our proposed framework is applicable to both triangular and quadrilateral refinement schemes, and does not impose any topological requirements upon the underlying subdivision control mesh. Several examples from an obstacle course of benchmark problems are used to demonstrate the convergence of the scheme. Copyright © 2004 John Wiley & Sons, Ltd.     

Adaptive generation of surfaces in volume data

A widespread approach to generating polygonal approximations of iso-surfaces or contour surfaces in volume data is the socalled marching-cubes algorithm. This algorithm, however, has the disadvantage that the number of polygonal chains generated is considerable. The splitting-box algorithm presented here reduces the number of polygonal chains by adapting their size to the shape of the surface. The resulting polygonal chains offer a wide spectrum for representing the contour surface. An exact representation is achieved by a new type of generic patches calculated from the polygonal chains. Approximations of different quality may be obtained by combining the algorithm generating the patches with simple triangulations.     

An efficient hierarchicaltraversal algorithm for ray tracing

Ray tracing has been shown to be an excellent technique for rendering realistic images. However, it is important to reduce the lengthy computation time resulting from the brute-force nature of the original ray-tracing algorithms. In this paper, two ideas are proposed to speep up the well-known hierarchical subdivision method. First, a new hierarchy traversal scheme is described to reduce the number of raybounding volume intersection tests for secondary rays. Then, a plane-sweep method is proposed to make fewer intersection checks for eye rays. Experiments and discussions are presented to prove the feasibility of our methods.     

Microstructural change of ultrafine-grained aluminum during high-speed plastic deformation

Effect of strain rate on microstructural change in deformation of the ultrafine grained (UFG) aluminum produced by severe plastic deformation (SPD) was studied. Commercial purity 1100 aluminum sheets were highly strained up to an equivalent strain of 4.8 by the Accumulative Roll-Bonding (ARB) process at ambient temperature. The ARB-processed sheets were found to be filled with pancake-shaped ultrafine grains surrounded by high-angle grain boundaries. The ultrafine grains had a mean grain thickness of 200 nm and a mean grain length of 1100 nm. The ultrafine-grained aluminum sheets were deformed at various strain rates ranging from 2 to 6.0×10⁴ s⁻¹ by conventional rolling, ultra-high-speed rolling, and impact compression. High-speed plastic deformation generates a large amount of heat, inducing coarsening of the ultrafine grains during and after deformation. On the other hand, it was also suggested that high-speed plastic deformation is effective for grain-subdivision, in other words, ultra-grain refinement, if the effect of heat generation is extracted.     

An Efficient Code-Based Voxel-Traversing Algorithm

The paper considers an efficient approach to traversing a uniformly-subdivided space pierced by a line segment. A voxel, as the basic constituent element of the uniformly subdivided space, is restricted to having the form of a cube. The algorithm works in two steps. In the first step, the so-called Bresenham voxels are identified and, by comparing their position codes, their type of connectivity is determined. To achieve the required connectivity between neighbouring voxels, the second step of the algorithm is applied to find the missing voxels. In this way, the algorithm efficiently switches between face-, edge- and vertex-connectivity. Although the algorithm works with oating-point precision, it is extremely computationally efficient, and tests of speed compared with the Müller, Cleary & Wyvill, Amanatides & Woo, and Zemčik algorithms are described.     

图像半色调化算法研究综述

半色调化算法是图像打印输出的关键技术之一。介绍了简单阈值比较算法、使用随机数的半色调化算法、误差扩散算法、点扩散算法、按序抖动算法和抖动算法等一系列半色调化算法,并揭示了这些算法之间的联系。为了高效率地对图像做半色调化操作,商用光栅图像处理器一般使用抖动算法。抖动算法生成的半色调化图像的质量取决于所采用的抖动矩阵。基于几何分割设计半色调化抖动矩阵的方法可以在满足堆栈限制的前提下优化半色调化图像的质量。使用随机数的半色调化算法可以消除图像半色调化中产生的莫尔纹。随机半色调化算法的基础是将一定数量的随机点均匀地分布到一个正方形区域中。Asano提出了随机点均匀分布问题等价于圆形装填问题的命题,本文对该命题给出了初步的证明。最后,给出了一些有待进一步研究的图像半色调化课题。     

基于SOPC的高精度超声波温度计设计

根据在介质中超声波的传播速度随温度变化而变化的特点为设计原理,以基于Nios II处理器软核的可编程系统级芯片(SOPC)为控制核心,设计了高精度超声波温度计。在SOPC上同时实现了高频信号发生器模块、高速信号电路控制模块、信号自动采集控制模块以及Nios II软核处理器模块,缩小了体积,并降低了成本。传播时间的精确测量采用软件细分插补算法,经过理论分析和实验验证,该方法能够达到ns级超声波传播时间的测量,使设计的超声波温度计能够实现分辨率优于0.001℃的温度测量。