A technique for motion specification in computer animation

A technique is discussed for the interactive specification and real-time evaluation of the movements of geometrical objects with several degrees of freedom. The technique is a midway between a faithful simulation of the dynamics and kinematics of the object and completely free user control, and as such it is well suited for animated drawings, for example. The method works in two steps: first, the motion of a relevant subobject (the skeleton) is specified interactively in real time. Next, the entire object is deformed and oriented in space such as to match the form of the skeleton. Depending on the complexity of the object, this second step either takes place in real time, or as a batch process. Several forms of geometrical constraints, as well as stretching and squeezing, are supported.     

Fast interference detection between geometric models

We present efficient algorithms for interference detection between geometric models described by linear or curved boundaries and undergoing rigid motion. The set of models include surfaces described by rational spline patches or piecewise algebraic functions. In contrast to previous approaches, we first describe an efficient algorithm for interference detection between convex polytopes using coherence and local features. Then an extension using hierarchical representation to concave polytopes is presented. We apply these algorithms along with properties of input models, local and global algebraic methods for solving polynomial equations, and the geometric formulation of the problem to devise efficient algorithms for convex and nonconvex curved objects. Finally, a scheduling scheme to reduce the frequency of interference detection in large environments is described. These algorithms have been successfully implemented and we discuss their performance in various environments.     

Dynamic sculpting and animation of free-form subdivision solids

Published online: 15 March 2002     

Interactive collision detection in three-dimensional visualizations of simulated construction operations

This paper presents research that led to the design and implementation of fast and interactive collision detection methods that can be used to identify and report undesirable conflicts that occur among static (e.g., structure in-place, idle equipment), dynamic (e.g., active machines and workers), and abstract (e.g., hazard spaces) construction resources in 3D animations of construction operations modeled using discrete-event simulation. Computational efficiency and interactive speed in the designed interference detection methods were the primary challenges that the research addressed. In addition, the efficiency and speed were achieved with minimal trade-off against accuracy. In order to achieve this, the authors capitalized on advanced documented algorithms for proximity queries between arbitrarily moving 3D geometric objects to design mechanisms for interference detection, control, and response in construction process visualizations. The designed methods are implemented in a software tool called C-Collide that integrates as an add-on with the VITASCOPE visualization system.     

Minimizing probable collision pairs searched in interactive animation authoring

Animation authoring involves an author’s interaction with a scene, resulting in varying scene complexity for a given animation sequence. In such a varying environment, detection and prediction of collision in minimal time and with high accuracy is a challenge. This paper proposes using the bounding volume-based space subdivision mechanism to reduce search space for an object pair collision search. This data structure is enhanced using a direction-based spatial hash table, which predicts collision between static and dynamic objects. These techniques are shown to work in conjunction with existing search space reduction methods. The event of collision is accurately detected using known methods, such as kinetic data structures. Simulation results show that for a scene with 10000 objects with varying dynamic objects (10–90%), the method finds probable collision-pairs with 95–99% accuracy.     

An iterative approach to dynamic simulation of 3-D rigid-body motions for real-time interactive computer animation

A method is presented for approximating the motions of linked 3-dimensional rigid body systems that may be applied in the context of interactive motion specification for computer animation. The method is based on decoupling the ballistic (free) component of the motion of the points that constitute the solid, and the component due to the shape constraint of the solid. This allows for a conceptually simple and computationally efficient algorithm for motion specification.     

Empirical comparisons of animation and narration in requirements validation

Increasingly powerful computing technology suggests an expansion of multimedia features in requirements engineering methods. It is not obvious, however, that techniques such as animation and narration would improve the effectiveness of communicating domain information to stakeholders for validation. Three principles from the cognitive theory of multimedia learning (CTML) are used to compare validation methods using animation and narration with more traditional methods using static diagrams and text. Results suggest animation and narration can have significant positive impact on the level of domain understanding attained by participants. In particular, narration yielded strongly significant results. While these results should be viewed as preliminary, they indicate a potential advantage in the use of narration and possibly animation in requirements validation. The results provide justification for further research on the integration of multimedia techniques in developing and validating requirements.     

Patterns of discussion between pupil pairs in computer and non-computer environments

Abstract This paper presents some findings of research into the discussion between pupils in computer and non-computer environments. The research was concerned with analysing the processes whereby pairs of pupils came to make mathematical generalizations in three environments, LOGO , spreadsheet and paper and pencil. Critical decisions in the generalization process were identified in order to allow comparisons to be made across environments. The analysis reveals differences in the effects of task environment on the negotiation of the mathematical generalization particularly in relation to the part played by formalization.     

Oriented bounding box and octree based global interference detection in 5-axis machining of free-form surfaces

Global interference detection is a critical problem in 5-axis NC machining of free-form surfaces. Based on the hierarchical oriented bounding box (OBB) which is used in virtual reality to detect spatial collisions between 3D objects, a new global interference detection method is developed in this paper. In this method, in order to simplify the computation process of updating tool positions and orientations in 5-axis machining, the cutter and cutter holder are modeled by a hierarchical OBB structure, whereas the workpiece surfaces are approximated by an octree. Interference detection is conducted between the tool OBBs and the gray octants of the surface octree with the separating axis theorem. With the hierarchical structure of octree, if interference is found in one octant, its sub-octants are further processed to locate the exact colliding leaf nodes and the discretized surface points contained in these leaf nodes are tested with a conventional vector calculation method for exact interference detection; if no interference is detected, all the sub-octants are then considered as interference free and are not processed further. Meanwhile, with the hierarchical structure of the tool OBBs, should interference occur between octants and the OBBs in the first level of the hierarchical structure, the sub-OBBs in the second level would be further tested. Otherwise it could be determined with certainty that there is no interference between the tool and the octant.     

Theoretical foundations for the 4×4 determinant method in computer graphics and geometric modelling

Theories of the 4×4 determinant method to resolve interference problems are described, in detail, in succession to the former paper [1]. First, various cases of the 4×4 determinant are discussed including the geometric implications by deriving a few fundamental relations. Secondly, normalization of the determinant is proposed. Thirdly, an intersection formula in homogeneous coordinates is verified which makes it possible to do consistent homogenous coordinate processing from the very beginning of geometric modelling to the very last of the objects displayed. Lastly an outline of how the 4×4 determinant method is applied to basic geometric problems is described.This article will provide, theoretical foundations for the 4×4 determinant method in computer graphics and geometric modelling.     

Asymptotic analysis of memory interference in multiprocessors with private cache memories

A closed Markovian queueing network model of a multiprocessor system with a two-level memory hierarchy is considered. Performance measures are introduced and obtained from the partition function. With a special structure of branching probabilities the network model is reduced to a nonlinear machine interference model. Asymptotic representation of the stationary distribution for heavy traffic conditions in the latter model is used for deriving approximate formulas for the performance measures when the number of processors and memory modules is large. For normal usage the approximations are obtained from asymptotic expansions of the partition function.     

Detection of loops and singularities of surface intersections

Two surface patches intersecting each other generally at a set of points (singularities), form open curves or closed loops. While open curves are easily located by following the boundary curves of the two patches, closed loops and singularities pose a robustness challenge since such points or loops can easily be missed by any subdivision or marching-based intersection algorithms, especially when the intersecting patches are flat and ill-positioned. This paper presents a topological method to detect the existence of closed loops or singularities when two flat surface patches intersect each other. The algorithm is based on an oriented distance function defined between two intersecting surfaces. The distance function is evaluated in a vector field to identify the existence of singular points of the distance function since these singular points indicate possible existence of closed intersection loops. The algorithm detects the existence rather than the absence of closed loops and singularities. This algorithm requires general C² parametric surfaces.     

Visualization of eclipses and planetary conjunction events. The interplay between model coherence, scaling and animation

The problem of an instructive and realistic animation and visualization of the shadow- and color-conditions during conjunctions of actively and passively illuminated cosmic objects has found only particularly satisfying solutions so far. As an example we study a total solar eclipse. There are didactic shortcomings of specialized astronomical software, even though solutions have been given, which are very impressive for experts. Using the possibilities of commercial 3D-animation software we give an object-oriented partial solution. In order to get correct astronomical representations we model – for different tasks – the object space under cinematic aspects with parameters for spatial and temporal scaling, for illumination and coloring under couplings of varying strength. The adaptation of the parameters to optimal acceptance of the spectator must be done a posteriori.     

On the complexity of minimizing interference in ad-hoc and sensor networks

One of the most critical factors for lifetime and operability of ad-hoc and sensor networks is the limited amount of available energy. To this respect, minimizing the interference in the network (i.e., the overlapping of signals at network nodes) has certainly a positive effect, because it induces a reduction of the number of conflicting transmissions, and then results in an overall saving of energy consumption. Along this direction, in this paper we study the computational hardness of several interference minimization problems which arise while supporting some classic network communication patterns such as broadcasting (one-to-all), gossiping (all-to-all), and symmetric gossiping (symmetric all-to-all). In particular, concerning the non-approximability results, we prove that for any of the above communication patterns, the prominent problem of minimizing the maximum interference experienced by any node in the network is hard to approximate within better than a logarithmic factor, unless NP admits slightly superpolynomial time algorithms. On a positive side, we show that any approximation algorithm for the problem of minimizing the total transmission power assigned to the nodes in order to guarantee any of the above communication patterns, can be transformed, by maintaining the same performance ratio, into an approximation algorithm for the problem of minimizing the total interference experienced by all the nodes in the network.     

Performance of 802.11 b/g in the interference limited regime

Signal to interference plus noise ratio, SINR, is one of the main factors that affects the quality of wireless communication. While the impact of white Gaussian noise on a wireless channel is well understood, impact of interference remains one of the less explored areas. With the deployment of dense mesh networks, the interference will be a dominant factor that affects the transmission errors. This paper explores the performance of 802.11 b/g when subject to interference. The findings are based on various controlled experiments in the laboratory setting. One finding of this work is that in contrast to communication over links where the noise is Gaussian, in 802.11 b/g, the probability of successfully transmitting a packet is dominated by the ability of the receiver to synchronize with the carrier. As a result, changing to a lower bit-rate with same synchronization scheme will not make the transmission more resilient to interference. Moreover, we found that the impact of interference is significant even if the interference is 10 dB below the strength of the noise. The significance of this result on bit-rate selection is briefly explored.     

Bayes分类技术在计算机病毒检测中的研究

本文从恶意程序检测的问题入手,介绍了病毒检测技术中的问题和难点,通过对恶意程序的主要特征分析,结合当前迅速发展的模式识别与智能检测成果,提出了使用Bayes分类法对恶意程序进行判断的方案,并对该方案的优缺点进行了分析。     

单片机抗扰设计综述

对单片机应用系统的干扰源进行了分析,重点介绍了单片机系统中常用的硬件和软件抗干扰设计,并提出一种数字滤波全新算法,实时性很强,采用汇编语言来编写。     

碰撞检测技术在三维交互漫游系统中的应用

针对提高交互漫游系统中动态的视点与静态的场景对象之间的碰撞检测性能进行了研究,将碰撞检测算法分成两步:第一步采用包围盒进行碰撞的粗略检测;第二步采用相交测试法进行碰撞的精确检测,并采用限时计算的思想对整个碰撞检测加以优化。实验结果表明,该算法加快了碰撞检测的速度,能较好地适应3D物体碰撞检测准确、快速的要求。