Analytic Curve Skeletons for 3D Surface Modeling and Processing

We present a new curve skeleton model designed for surface modeling and processing. This skeleton is defined as the geometrical integration of a piecewise harmonic parameterization defined over a disk‐cylinder surface decomposition. This decomposition is computed using a progressive Region Graph reduction based on both geometric and topological criteria which can be iteratively optimized to improve region boundaries. The skeleton has an analytical form with regularity inherited from the surface one. Such a form offers well‐defined surface‐skeleton and skeleton‐surface projections. The resulting skeleton satisfies quality criteria which are relevant for skeleton‐based modeling and processing. We propose applications that benefit from our skeleton model, including local thickness editing, inset surface creation for shell mapping, as well as a new mid‐scale feature preserving smoothing.     

面向Web的机械产品三维模型简化算法研究

对机械产品三维模型数据量大不利于网络传输和Web显示的问题,提出了基于半边折叠的三维模型简化算法.通过引入顶点领域三角形平均面积、顶点领域三角形的法向量变化以及折叠边的边长,计算折叠代价,通过对折叠代价排序与预先设定好的阙值,对机械产品三维模型进行简化处理.实验结果表明,该算法有效减少了机械产品三维模型的数据量,提升了Web环境下机械产品三维模型数据传递和浏览器显示的流畅性,对机械产品分布式设计和制造技术的发展起到了促进作用.     

GeoBuilder: A Geometric Algorithm Visualization and Debugging System for 2D and 3D Geometric Computing

Algorithm visualization is a unique research topic that integrates engineering skills such as computer graphics, system programming, database management, computer networks, etc., to facilitate algorithmic researchers in testing their ideas, demonstrating new findings, and teaching algorithm design in the classroom. Within the broad applications of algorithm visualization, there still remain performance issues that deserve further research, e.g., system portability, collaboration capability, and animation effect in 3D environments. Using modern technologies of Java programming, we develop an algorithm visualization and debugging system, dubbed GeoBuilder, for geometric computing. The GeoBuilder system features Java's promising portability, engagement of collaboration in algorithm development, and automatic camera positioning for tracking 3D geometric objects. In this paper, we describe the design of the GeoBuilder system and demonstrate its applications.     

Computing hierarchical curve-skeletons of 3D objects

A curve-skeleton of a 3D object is a stick-like figure or centerline representation of that object. It is used for diverse applications, including virtual colonoscopy and animation. In this paper, we introduce the concept of hierarchical curve-skeletons and describe a general and robust methodology that computes a family of increasingly detailed curve-skeletons. The algorithm is based upon computing a repulsive force field over a discretization of the 3D object and using topological characteristics of the resulting vector field, such as critical points and critical curves, to extract the curve-skeleton. We demonstrate this method on many different types of 3D objects (volumetric, polygonal and scattered point sets) and discuss various extensions of this approach.     

3D打印中的几何计算研究进展

3D打印技术改变了传统的减式材料制造模式,带来了制造工艺和生产模式的变革,有力地推动了3D数字化相关技术与研究的发展.文中从3D打印的社会背景与理论背景出发,介绍了3D打印技术的分类、原理与过程.以此为基础,对近几年的3D打印中的几何计算问题给出了全面的综述,根据问题特点将其分为几何优化、结构分析、材料表面效果定制、机构设计、自支撑结构设计、内部结构设计等六大类,并对每一类作了详细的分类介绍,最后对其发展方向作了初步展望.     

3D and 2D/3D holograms model

The estimating problem of 3D holograms orientation selectivity on angular, orthogonal, and azimuthal sensitivity parameters is formulated and solved. Tenfold increase of density 3D, 2D/3D holograms in comparison with 2D holograms at given selectivity for ones is shown in theory and experimentally.     

3D Skeletons: A State‐of‐the‐Art Report

Given a shape, a skeleton is a thin centered structure which jointly describes the topology and the geometry of the shape. Skeletons provide an alternative to classical boundary or volumetric representations, which is especially effective for applications where one needs to reason about, and manipulate, the structure of a shape. These skeleton properties make them powerful tools for many types of shape analysis and processing tasks. For a given shape, several skeleton types can be defined, each having its own properties, advantages, and drawbacks. Similarly, a large number of methods exist to compute a given skeleton type, each having its own requirements, advantages, and limitations. While using skeletons for two‐dimensional (2D) shapes is a relatively well covered area, developments in the skeletonization of three‐dimensional (3D) shapes make these tasks challenging for both researchers and practitioners. This survey presents an overview of 3D shape skeletonization. We start by presenting the definition and properties of various types of 3D skeletons. We propose a taxonomy of 3D skeletons which allows us to further analyze and compare them with respect to their properties. We next overview methods and techniques used to compute all described 3D skeleton types, and discuss their assumptions, advantages, and limitations. Finally, we describe several applications of 3D skeletons, which illustrate their added value for different shape analysis and processing tasks.     

基于三维加速度的连续手势识别

由于基于图像处理的手势识别方法对环境背景要求较高且存在不稳定性问题,文章使用三维加速度传感器的连续数据进行手势识别.三维加速度传感器内置于大部分智能手机中,具有应用方便的特点.实验通过传感器获取加速度信号,经过低通滤波、去重力和特征提取的信号预处理过程后,结合隐马尔可夫模型和混合高斯模型的理论方法,实现手机手势的连续识别,并驱动应用层预先定义的交互命令.     

Continuous Global Optimization in Multiview 3D Reconstruction

In this article, we introduce a new global optimization method to the field of multiview 3D reconstruction. While global minimization has been proposed in a discrete formulation in form of the maxflow-mincut framework, we suggest the use of a continuous convex relaxation scheme. Specifically, we propose to cast the problem of 3D shape reconstruction as one of minimizing a spatially continuous convex functional. In qualitative and quantitative evaluation we demonstrate several advantages of the proposed continuous formulation over the discrete graph cut solution. Firstly, geometric properties such as weighted boundary length and surface area are represented in a numerically consistent manner: The continuous convex relaxation assures that the algorithm does not suffer from metrication errors in the sense that the reconstruction converges to the continuous solution as the spatial resolution is increased. Moreover, memory requirements are reduced, allowing for globally optimal reconstructions at higher resolutions. We study three different energy models for multiview reconstruction, which are based on a common variational template unifying regional volumetric terms and on-surface photoconsistency. The three models use data measurements at increasing levels of sophistication. While the first two approaches are based on a classical silhouette-based volume subdivision, the third one relies on stereo information to define regional costs. Furthermore, this scheme is exploited to compute a precise photoconsistency measure as opposed to the classical estimation. All three models are compared on standard data sets demonstrating their advantages and shortcomings. For the third one, which gives the most accurate results, a more exhaustive qualitative and quantitative evaluation is presented.     

直接计算二维离散卷积的快速定限方法

导出了二维离散线性卷积的快速定限求解方法给出了在二维平面的十个区域中卷积的简便求和公式及卷积的上下限精确表达式。该法可很方便地扩展至三维、多维空间。     

Computing Contour Trees for 2D Piecewise Polynomial Functions

Contour trees are extensively used in scalar field analysis. The contour tree is a data structure that tracks the evolution of level set topology in a scalar field. Scalar fields are typically available as samples at vertices of a mesh and are linearly interpolated within each cell of the mesh. A more suitable way of representing scalar fields, especially when a smoother function needs to be modeled, is via higher order interpolants. We propose an algorithm to compute the contour tree for such functions. The algorithm computes a local structure by connecting critical points using a numerically stable monotone path tracing procedure. Such structures are computed for each cell and are stitched together to obtain the contour tree of the function. The algorithm is scalable to higher degree interpolants whereas previous methods were restricted to quadratic or linear interpolants. The algorithm is intrinsically parallelizable and has potential applications to isosurface extraction.     

Hierarchical Representations of 2D/3D Gray-Scale Images and Their 2D/3D Two-Way Conversion

This article proposes G-octree as an extension of G-quadtree to three dimensions. A G-octree reflects in its construction a hierarchy of gray-scale level value homogeneity, as well as a hierarchy of spatial resolution. The article also develops two-way G-quadtree/Goctree conversion procedures based on the algorithms for the binary case. These procedures provide an integrated processing environment for hierarchically represented 2D/3D gray.scale images. We demonstrate our approach with an application to the color coding of macro-autoradiography images taken from rat brains.     

一种基于包络控制的三角形收缩简化三维几何模型的新算法

本文算法先将原始模型上的每一点沿各自的法矢量方向偏移一定的距离，使整个原始模型收缩或扩张，生成内外两层包络．在构造包络时采用了一维搜索中的二分法来逼近最佳偏移值，以保证原始模型尽可能简化，然后依次选择原始模型上的一些三角形，将其三个顶点合并，收缩成一个三雏点．如果这样收缩简化后的模型依然位于两层包络围成的空间中．则收缩操作产生的误差被认为是可接受的．这也就保证了简化模型与原始模型外形上的相似．同时，本文还设计了一个演示系统，实现了这种算法．实验结果表明．通过这种算法简化三维几何模型后，简化模型不仅具有一定的压缩率，而且保留了原始几何模型的尖锐特征，两者在外形上十分相似。     

超级计算在3D动画渲染中的运用研究

国家出台各项政策扶持国产动画,动画产业发展势头良好。但三维动画制作周期长,消耗经费多（硬件设备购置及损耗、项目内人员工资发放等）,严重阻碍了国产动画产业的发展。三维动画流程包含前期设定、模型、配景、UV贴图、动画、特效、材质灯光、分层渲染及后期合成等各环节,其中渲染约占项目总耗时的30%左右,但人员安排却仅占整个项目的1/20左右,因此,节省渲染时间无疑能大大缩短动画项目周期,降低人力物力财力成本。超级计算在动画渲染中的应用研究成功后,能产生巨大的直接及间接效益,并造成深远的社会影响,大大缩短动画制作周期,节约成本,从而拉动国内动画产业的迅速发展。     

基于云计算的三维虚拟学习环境的设计与应用

针对现有的三维虚拟学习环境场景渲染带来的显示延迟和实体运动僵硬等性能问题,将云计算引入到三维虚拟学习环境的建设中.提出了基于云计算的三维虚拟学习环境的体系结构和云计算的一些关键技术.建立了一个基于该体系结构的原型,并通过该原型设计了三维虚拟学习环境.结果表明,云计算与三维虚拟学习环境的结合是有效的,能满足虚拟环境仿真实时性、稳定性和准确性的要求,能解决场景渲染带来的性能问题.     

Motorcycle Graphs and Straight Skeletons

We present a new algorithm to compute motorcycle graphs. It runs in time when n is the number of motorcycles. We give a new characterization of the straight skeleton of a nondegenerate polygon. For a polygon with n vertices and h holes, we show that it yields a randomized algorithm that reduces the straight skeleton computation to a motorcycle graph computation in expected time. Combining these results, we can compute the straight skeleton of a nondegenerate polygon with h holes and with n vertices, among which r are reflex vertices, in expected time. In particular, we cancompute the straight skeleton of a nondegenerate polygon with n vertices in expected time.     

Information availability in 2D and 3D displays

Why are 3D displays good for rapidly appreciating the third dimension of scenes? We show that information availability is more important than the 3D display format. Participants engaged in visual search for the attributes of altitude and pitch for coding schemes. This design let us disentangle the display format and information coding scheme so that we could properly evaluate the effect of each on performance     

3D Fabrication of 2D Mechanisms

The success of physics sandbox applications and physics‐based puzzle games is a strong indication that casual users and hobbyists enjoy designing mechanisms, for educational or entertainment purposes. In these applications, a variety of mechanisms are designed by assembling two‐dimensional shapes, creating gears, cranks, cams, and racks. The experience is made enjoyable by the fact that the user does not need to worry about the intricate geometric details that would be necessary to produce a real mechanism. In this paper, we propose to start from such casual designs of mechanisms and turn them into a 3D model that can be printed onto widely available, inexpensive filament based 3D printers. Our intent is to empower the users of such tools with the ability to physically realize their mechanisms and see them operate in the real world. To achieve this goal we tackle several challenges. The input 2D mechanism allows for some parts to overlap during simulation. These overlapping parts have to be resolved into non‐intersecting 3D parts in the real mechanism. We introduce a novel scheme based on the idea of including moving parts into one another whenever possible. This reduces bending stresses on axles compared to previous methods. Our approach supports sliding parts and arbitrarily shaped mechanical parts in the 2D input. The exact 3D shape of the parts is inferred from the 2D input and the simulation of the mechanism, using boolean operations between shapes. The input mechanism is often simply attached to the background. We automatically synthesize a chassis by formulating a topology optimization problem, taking into account the stresses exerted by the mechanism on the chassis through time.     

支持协同设计的3D动漫造型进化计算方法

为了自动生成创意新颖的3D动漫造型,提出一种基于C/S模式的交互式遗传算法HA IGA.在HA IGA中引入HSF协同技术和AC IS规则,利用三棵二叉树表示AC IS规则表达式,分别用于在x轴、y轴和z轴三个方向上对3D实体进行非均匀缩放;通过对二叉树实施选择、交叉、变异和精英保留操作进化产生新的规则表达式,从而进化生成新的3D动漫造型.实验结果表明,本文提出的方法能够有效支持协同设计,并进化生成一系列创意新颖的3D动漫造型.     

Computing medial axes of generic 3D regions bounded by B-spline surfaces

A new approach is presented for computing the interior medial axes of generic regions in R³ bounded by C⁽⁴⁾-smooth parametric B-spline surfaces. The generic structure of the 3D medial axis is a set of smooth surfaces along with a singular set consisting of edge curves, branch curves, fin points and six junction points. In this work, the medial axis singular set is first computed directly from the B-spline representation using a collection of robust higher order techniques. Medial axis surfaces are computed as a time trace of the evolving self-intersection set of the boundary under the the eikonal (grassfire) flow, where the bounding surfaces are dynamically offset along the inward normal direction. The eikonal flow results in special transition points that create, modify or annihilate evolving curve fronts of the (self-) intersection set. The transition points are explicitly identified using the B-spline representation. Evolution of the (self-) intersection set is computed by adapting a method for tracking intersection curves of two different surfaces deforming over generalized offset vector fields. The proposed algorithm accurately computes connected surfaces of the medial axis as well its singular set. This presents a complete solution along with accurate topological structure.