Interactive Cover Design Considering Physical Constraints

We developed an interactive system to design a customized cover for a given three‐dimensional (3D) object such as a camera, teapot, or car. The system first computes the convex hull of the input geometry. The user segments it into several cloth patches by drawing on the 3D surface. This paper provides two technical contributions. First, it introduces a specialized flattening algorithm for cover patches. It makes each two‐dimensional edge in the flattened pattern equal to or longer than the original 3D edge; a smaller patch would fail to cover the object, and a larger patch would result in extra wrinkles. Second, it introduces a mechanism to verify that the user‐specified opening would be large enough for the object to be removed. Starting with the initial configuration, the system virtually “pulls” the object out of the cover while avoiding excessive stretching of cloth patches. We used the system to design real covers and confirmed that it functions as intended.     

A novel 3D mesh compression using mesh segmentation with multiple principal plane analysis

This paper proposes a novel scheme for 3D model compression based on mesh segmentation using multiple principal plane analysis. This algorithm first performs a mesh segmentation scheme, based on fusion of the well-known k-means clustering and the proposed principal plane analysis to separate the input 3D mesh into a set of disjointed polygonal regions. The boundary indexing scheme for the whole object is created by assembling local regions. Finally, the current work proposes a triangle traversal scheme to encode the connectivity and geometry information simultaneously for every patch under the guidance of the boundary indexing scheme. Simulation results demonstrate that the proposed algorithm obtains good performance in terms of compression rate and reconstruction quality.     

Priority-based encoding of triangle mesh connectivity for a known geometry

In certain practical situations, the connectivity of a triangle mesh needs to be transmitted or stored given a fixed set of 3D vertices that is known at both ends of the transaction (encoder/decoder). This task is different from a typical mesh compression scenario, in which the connectivity and geometry (vertex positions) are encoded either simultaneously or in reversed order (connectivity first), usually exploiting the freedom in vertex/triangle re-indexation. Previously proposed algorithms for encoding the connectivity for a known geometry were based on a canonical mesh traversal and predicting which vertex is to be connected to the part of the mesh that is already processed. In this paper, we take this scheme a step further by replacing the fixed traversal with a priority queue of open expansion gates, out of which in each step a gate is selected that has the most certain prediction, that is one in which there is a candidate vertex that exhibits the largest advantage in comparison with other possible candidates, according to a carefully designed quality metric. Numerical experiments demonstrate that this improvement leads to a substantial reduction in the required data rate in comparison with the state of the art.     

Semi‐Automatic Conversion of 3D Shape into Flat‐Foldable Polygonal Model

This paper presents a method that can convert a given 3D mesh into a flat‐foldable model consisting of rigid panels. A previous work proposed a method to assist manual design of a single component of such flat‐foldable model, consisting of vertically‐connected side panels as well as horizontal top and bottom panels. Our method semi‐automatically generates a more complicated model that approximates the input mesh with multiple convex components. The user specifies the folding direction of each convex component and the fidelity of shape approximation. Given the user inputs, our method optimizes shapes and positions of panels of each convex component in order to make the whole model flat‐foldable. The user can check a folding animation of the output model. We demonstrate the effectiveness of our method by fabricating physical paper prototypes of flat‐foldable models.     

Vertex data compression through vector quantization

Rendering geometrically detailed 3D models requires the transfer and processing of large amounts of triangle and vertex geometry data. Compressing the geometry bit stream can reduce bandwidth requirements and alleviate transmission bottlenecks. In this paper, we show vector quantization to be an effective compression technique for triangle mesh vertex data. We present predictive vector quantization methods using unstructured code books as well as a product code pyramid vector quantizer. The technique is compatible with most existing mesh connectivity encoding schemes and does not require the use of entropy coding. In addition to compression, our vector quantization scheme can be used for complexity reduction by accelerating the computation of linear vertex transformations. Consequently, an encoded set of vertices can be both decoded and transformed in approximately 60 percent of the time required by a conventional method without compression     

From on-line sketching to 2D and 3D geometry: a system based on fuzzy knowledge

The paper describes the development of a fuzzy knowledge-based prototype system for conceptual design. This real time system is designed to infer user's sketching intentions, to segment sketched input and generate corresponding geometric primitives: straight lines, circles; arcs, ellipses, elliptical arcs, and B-spline curves. Topology information (connectivity, unitary constraints and pairwise constraints) is received dynamically from 2D sketched input and primitives. From the 2D topology information, a more accurate 2D geometry can be built up by applying a 2D geometric constraint solver. Subsequently, 3D geometry can be received feature by feature incrementally. Each feature can be recognised by inference knowledge in terms of matching its 2D primitive configurations and connection relationships. The system accepts not only sketched input, working as an automatic design tool, but also accepts user interactive input of both 2D primitives and special positional 3D primitives. This makes it easy and friendly to use. The system has been tested with a number of sketched inputs of 2D and 3D geometry.     

Feature Oriented Progressive Lossless Mesh Coding

A feature‐oriented generic progressive lossless mesh coder (FOLProM) is proposed to encode triangular meshes with arbitrarily complex geometry and topology. In this work, a sequence of levels of detail (LODs) are generated through iterative vertex set split and bounding volume subdivision. The incremental geometry and connectivity updates associated with each vertex set split and/or bounding volume subdivision are entropy coded. Due to the visual importance of sharp geometric features, the whole geometry coding process is optimized for a better presentation of geometric features, especially at low coding bitrates. Feature‐oriented optimization in FOLProM is performed in hierarchy control and adaptive quantization. Efficient coordinate representation and prediction schemes are employed to reduce the entropy of data significantly. Furthermore, a simple yet efficient connectivity coding scheme is proposed. It is shown that FOLProM offers a significant rate‐distortion (R‐D) gain over the prior art, which is especially obvious at low bitrates.     

基于凸壳与有向包围盒的骨架提取方法

为获取三维模型的几何及拓扑信息,提出一种基于凸壳与有向包围盒(OBB)的线性骨架提取方法.首先将三维网格模型进行分割生成多个子网格模型;然后对各子网格中的点集求取凸壳作为该子网格点集的近似,由凸壳顶点的形心构成原始骨架点;再用OBB进行重叠计算求出相交点集,以生成关节骨架点;最后对原始骨架点与关节骨架点进行连接,经冗余检测后形成完整骨架.实验结果表明,该方法快速、有效,提取出的骨架能保证连通性与中心性且能很好地提取关节骨架点,为蒙皮关节动画、模型形状分析等提供有效信息.     

Convex sets as prototypes for classifying patterns

We propose a general framework for nonparametric classification of multi-dimensional numerical patterns. Given training points for each class, it builds a set cover with convex sets each of which contains some training points of the class but no points of the other classes. Each convex set has thus an associated class label, and classification of a query point is made to the class of the convex set such that the projection of the query point onto its boundary is minimal. In this sense, the convex sets of a class are regarded as “prototypes” for that class. We then apply this framework to two special types of convex sets, minimum enclosing balls and convex hulls, giving algorithms for constructing a set cover with them and for computing the projection length onto their boundaries. For convex hulls, we also give a method for implicitly evaluating whether a point is contained in a convex hull, which can avoid computational difficulty for explicit construction of convex hulls in high-dimensional space.     

Partwise cross-parameterization via nonregular convex hull domains

In this paper, we propose a novel partwise framework for cross-parameterization between 3D mesh models. Unlike most existing methods that use regular parameterization domains, our framework uses nonregular approximation domains to build the cross-parameterization. Once the nonregular approximation domains are constructed for 3D models, different (and complex) input shapes are transformed into similar (and simple) shapes, thus facilitating the cross-parameterization process. Specifically, a novel nonregular domain, the convex hull, is adopted to build shape correspondence. We first construct convex hulls for each part of the segmented model, and then adopt our convex-hull cross-parameterization method to generate compatible meshes. Our method exploits properties of the convex hull, e.g., good approximation ability and linear convex representation for interior vertices. After building an initial cross-parameterization via convex-hull domains, we use compatible remeshing algorithms to achieve an accurate approximation of the target geometry and to ensure a complete surface matching. Experimental results show that the compatible meshes constructed are well suited for shape blending and other geometric applications.     

Distance-Ranked Connectivity Compression of Triangle Meshes

We present a new, single-rate method for compressing the connectivity information of a connected 2-manifold triangle mesh with or without boundary. Traditional compression schemes interleave geometry and connectivity coding, and are thus typically unable to utilize information from vertices (mesh regions) they have not yet processed. With the advent of competitive point cloud compression schemes, it has become feasible to develop separate connectivity encoding schemes that can exploit complete, global vertex position information to improve performance. Our scheme demonstrates the utility of this separation of vertex and connectivity coding. By traversing the mesh edges in a consistent fashion, and using global vertex information, we can predict the position of the vertex that completes the unprocessed triangle attached to a given edge. We then rank the vertices in the neighborhood of this predicted position by their Euclidean distance. The distance rank of the correct closing vertex is stored. Typically, these rank values are small, and the set of rank values thus possesses low entropy and compresses very well. The sequence of rank values is all that is required to represent the mesh connectivity—no special split or merge codes are necessary. Results indicate improvements over traditional valence-based schemes for more regular triangulations. Highly irregular triangulations or those containing a large number of slivers are not well modelled by our current set of predictors and may yield poorer connectivity compression rates than those provided by the best valence-based schemes.     

3D网格隐写与隐写分析回顾与展望

在计算机图形学中,3D形状可有多种表示形式,包括网格、体素、多视角图像、点云、参数曲面和隐式曲面等。3D网格是常见的表示形式之一,其构成3D物体的顶点、边缘和面的集合,通常用于表示数字3D物体的曲面和容积特性。在过去的20年中,基于3D网格载体的虚拟现实、实时仿真和交叉3维设计已经在工业,医疗和娱乐等场景得到广泛应用,以3D网格为载体的水印技术、隐写和隐写分析技术也受到研究者的关注。相比于图像与音视频等载体的隐写,3D网格具备嵌入方式灵活与载体形式多变等其自身的优势。本文回顾了3D网格隐写和隐写分析的发展,并对现有研究工作进行了系统的总结和分类。根据嵌入方式和嵌入位置将隐写算法分成4类：两态调制隐写、最低位隐写、置换隐写和变换域隐写;根据特征提取角度将隐写分析算法分为2类：通用型隐写分析和专用型隐写分析。随后,介绍了每个类别的技术,综合安全性、鲁棒性、容量以及运算效率分析了各类算法的优劣性,总结当前的发展水平,并提供了不同嵌入率下两种数据集上隐写分析算法之间的性能比较。最后讨论了3D隐写和隐写分析现有技术的局限性,并探讨了潜在的研究方向,旨在为后续学者进一步推动3D隐写和隐写分析技术提供指导。     

A Flexible Kernel for Adaptive Mesh Refinement on GPU

We present a flexible GPU kernel for adaptive on‐the‐fly refinement of meshes with arbitrary topology. By simply reserving a small amount of GPU memory to store a set of adaptive refinement patterns, on‐the‐fly refinement is performed by the GPU, without any preprocessing nor additional topology data structure. The level of adaptive refinement can be controlled by specifying a per‐vertex depth‐tag, in addition to usual position, normal, color and texture coordinates. This depth‐tag is used by the kernel to instanciate the correct refinement pattern, which will map a refined connectivity on the input coarse polygon. Finally, the refined patch produced for each triangle can be displaced by the vertex shader, using any kind of geometric refinement, such as Bezier patch smoothing, scalar valued displacement, procedural geometry synthesis or subdivision surfaces. This refinement engine does neither require multipass rendering nor any use of fragment processing nor special preprocess of the input mesh structure. It can be implemented on any GPU with vertex shading capabilities.     

基于凸凹信号的网格分割

网格分割在网格参数化、纹理atlas图等几何处理问题中有着重要的应用,提出一种基于顶点或面凸凹信号的简单高效的网格分割算法,基于均匀支撑半径的顶点凸凹信号分析将顶点分为平坦点、凸点、凹点和特征点,先从平坦点进行平坦区域扩展,再从剩下的凸凹点出发进行凸凹区域扩展,最后根据顶点和边界边的光滑度进行区域竞争扩展;对于未能完全分割的简化程度高的模型,基于面的凸凹信号采用类似的过程进一步完成最后的分割,该算法可以快速地进行网格分割并能较好地保持网格特征,特别适用于CAD模型的分割。     

Convex Decomposition Based Cluster Labeling Method for Support Vector Clustering

Support vector clustering (SVC) is an important boundary-based clustering algorithm in multiple applications for its capability of handling arbitrary cluster shapes.However,SVC’s popularity is degraded by its highly intensive time complexity and poor label performance.To overcome such problems,we present a novel efficient and robust convex decomposition based cluster labeling (CDCL) method based on the topological property of dataset.The CDCL decomposes the implicit cluster into convex hulls and each one is comprised by a subset of support vectors (SVs).According to a robust algorithm applied in the nearest neighboring convex hulls,the adjacency matrix of convex hulls is built up for finding the connected components;and the remaining data points would be assigned the label of the nearest convex hull appropriately.The approach’s validation is guaranteed by geometric proofs.Time complexity analysis and comparative experiments suggest that CDCL improves both the efficiency and clustering quality significantly.     

Single-rate near lossless compression of animated geometry

Representing mesh geometry in local rather than the world coordinate systems is very useful in many 3D animation processing applications. One can investigate the representation of vertex locations relative to a local coordinate frame (LCF) in the compression of dynamic 3D meshes. Unlike the world coordinates, which scatter in a wide range and show non-linear behavior of the vertices, the local coordinates exhibit a large clustering behavior of the vertex over time. This property is very useful for exploiting a large coherence over the vertex trajectory and between neighboring vertices. In this paper, we discuss the use of the LCF in static and animated mesh encoding and we introduce a new connectivity-guided predictive scheme for single-rate compression for animated meshes. The proposed geometry encoding strategy is based on a region growing encoding order, and only the differences between original and predicted locations are encoded in a local coordinate system, which splits into two tangential and one normal components. The approach is simple, efficient, and well-suited for real time applications.     

圆弧路径法，一种新的多边形变形方法

二维形状变形技术在二维角色动画、模式匹配、几何造型、虚拟现实、工业模拟、科学计算可视化等领域有着重要的应用。本文提出了一种顶点路径圆弧法的二维形状变形新方法。该算法通过控制关键帧多边形顶点按照一条特殊的圆弧曲线路径进行运动，实现二维形状变形。通过许多实例的测试表明，该算法效果良好：不仅可以保持首末关键帧形状的共同特征，而且中间插值形状变化自然平滑。同时，我们的方法易于用户交互控制；容易推广到高维情形；计算量较小、能达到系统实时的要求。     

GEncode: Geometry-driven compression for General Meshes

Performances of actual mesh compression algorithms vary significantly depending on the type of model it encodes. These methods rely on prior assumptions on the mesh to be efficient, such as regular connectivity, simple topology and similarity between its elements. However, these priors are implicit in usual schemes, harming their suitability for specific models. In particular, connectivity‐driven schemes are difficult to generalize to higher dimensions and to handle topological singularities. GEncode is a new single‐rate, geometry‐driven compression scheme where prior knowledge of the mesh is plugged into the coder in an explicit manner. It encodes meshes of arbitrary dimension without topological restrictions, but can incorporate topological properties, such as manifoldness, to improve the compression ratio. Prior knowledge of the geometry is taken as an input of the algorithm, represented by a function of the local geometry. This suits particularly well for scanned and remeshed models, where exact geometric priors are available. Compression results surfaces and volumes are competitive with existing schemes.     

基于重新划分的三角形网格简化的一种改进算法

基于重新划分的三角形网格简化方法能自动生成多细节层次模型，它的基本思想是:根据三角形网格的局部几何和拓扑特征将一定数量的点分布到原网格上,生成一个中间网格,移去中间网格中的老顶点,并对产生的多边形区域进行局部三角化,最后形成以新点为顶点的三角形网格.本文在已有算法的基础上,提出了一种分布新点的算法,从而克服了原有方法的局限性.它利用三角形顶点的曲率和三角形的面积两个因素来反映网格在每个三角形处的特征.文中给出的一组实例说明了算法的有效性.