一种检测点是否在多边形或多面体内的方法

提出一种新的方法，以检测一个点是否在多边形或多面体内．此方法以射线法的基础，用垂直于射线的直线(或平面)将多边形(或多面体)分成两大部分，检测时，仅仅处理射线所指向的那个部分，根据射线穿过的多边形的折线或多面体的多边形曲面的个数的奇偶性判断检测点是否在多边形或多面体内，在检测过程中该方法只求解少量的方程，不必处理每个面和每条边，实验结果表明，该方法简单，可靠，检测速度快。     

基于八叉树结构实现机械零件的表面重构

在移动立方体算法的基础上,利用八叉树结构的边树方法以连续的方式定义阈值穿过的位王.通过边树方式提取严谨的多边形面片,利用最小区域剖分生成三角形面片.用SolidWorks的模型,将八又树结构边树方法应用于机械零件的表面重构中,取得了较好的效果,实现了对机械零件的方便控制和变换.     

多个凹凸形多面体的深度优先消隐算法研究

为了对多个凹凸形多面体进行消隐处理，应首先对单个凹凸形多面体进行可见性测试。对多个凹凸形多面体间可能出现的遮蔽进行屏幕投影多边形的重叠排除验证，对可能出现重叠的多边形边进行交点计算、包容性测试和深度检查。本文指出，凹凸形多面体在可见性测试及投影多边形包容性测试方面应采用不同的处理方法。实践结果表明，此算
算法可以取得较好的效果。     

确定两个任意简单多边形空间关系的算法

阐述了把简单多边形的边分为奇偶边的新思想,根据一多边形的边与另一多边形的拓朴关系,划分边为5种拓朴类型:内边、外边、重叠边、相交边、复杂边,进而给出了确定两个多边形空间关系的算法,算法的时间复杂度为O((n+m)log(n+m)),其中n、m分别是两输入多边形的顶点数。该算法建立在数学理论基础之上,没有奇异情况需要处理,易于编程实现。算法的主要思想对确定两个简单多面体空间关系亦有参考价值。     

基于倾斜摄影的三维模型单体化方法研究

利用三角面片的可分割性质,解决倾斜摄影数据的三维模型可分离单体化问题。该方法首先绘制切割多边形,确定单体化模型边界,然后使用包围盒方法进行求交检测,获得需要切割的三角面片。之后计算求交检测所得三角面片与切割多边形的交点,然后详细分析切割多边形与三角面片相交时的不同相交情形,并针对不同的相交情形采用不同的切割方法。最后,对相交区域三角面片进行裁切并重构,再纹理重构并实现多细节分层后得到分离的单体化模型。实验结果表明,该方法可有效实现倾斜摄影三维模型的分离单体化。     

虚拟场景中多面体浮力算法研究

随着仿真技术的不断发展,游戏玩家们对与流体有关的场景中的仿真效果的要求也不断提升.应此要求,在对虚拟场景中的多面体浮力算法进行研究基础上,提出了新的、并更加行之有效的计算多面体浮力的方法.采用分割多边形的途径,将组成多面体的各多边形的水下部分分割成若干三角形,之后再计算水下部分多边形的体积,进而求出浮力.同时,考虑到阻力因素的作用,计算出相关的阻力和阻力力矩后,便可精确显示出多面体在场景中的力作用情况.算法采用以仿真能量损耗和水流耦合,更简单于全动态水体仿真,并且不需要额外的创建步骤.方法效率高,易实现,且便于集成到物理引擎中.     

基于投影法的隐式曲面多边形化

绘制多边形可借助图形系统的硬件来实现,因此,隐式曲面的多边形化是隐式曲面绘制的主要方法,文中提出了基于投影法的隐式曲面多边形化的方法,先在平面进行网格划分,再把平面上所有多边形面片映射到隐式曲面上,该方法对隐式曲面上有全部投影,部分投影和没有投影的多边形面片分别进行了讨论,该方法也适用于绘制隐式载剪曲面。     

凸多面体碰撞检测的棱线投影分离算法EI北大核心CSCD

针对凸多面体碰撞检测问题,以直线投影法为基础对分离面投影法进行改进,提出一种采用棱线投影分离的凸多面体实时精确碰撞检测算法.首先分析了凸多面体各种相对位置关系并提出了投影分离线的概念,针对凸多面体的各种分离情况证明投影分离线的存在;其次选取凸多面体相向面上的棱集构造准投影分离线,通过沿着准投影分离线方向投影可将3D凸多面体碰撞检测降维为2D凸多边形的碰撞检测问题;最后将分离投影的思想延用至为2D凸多边形的碰撞检测,再次将2D问题降维为1D问题.算法分析和实验结果表明,该算法对于凸多面体碰撞检测具有较高的响应速度和检测精度.     

基于Minkowski和的多面体快速碰撞检测算法

为了进一步提高碰撞检测的实时性,提出一种基于Minkowski和的多面体快速碰撞检测算法.该算法以Minkowski和为工具,无需精确计算两个多面体之间的最短距离,首先通过构造两个多面体的Minkowski和,将多面体碰撞检测问题转化为判断原点是否在该Minkowski和内,然后运用射线和求交计算将三维空间问题转化为二维平面问题,再通过判断原点是否在平面多边形内来检测多面体是否发生碰撞,进而提高了碰撞检测的实时性和可靠性.在Visual C#环境下,利用OpenGL图形库搭建一个路径规划仿真系统.实验结果表明,该算法平均检测效率明显高于传统算法,并且有效降低了存储空间和时间复杂度.     

凸多面体碰撞检测的棱线投影分离算法

针对凸多面体碰撞检测问题,以直线投影法为基础对分离面投影法进行改进,提出一种采用棱线投影分离的凸多面体实时精确碰撞检测算法.首先分析了凸多面体各种相对位置关系并提出了投影分离线的概念,针对凸多面体的各种分离情况证明投影分离线的存在;其次选取凸多面体相向面上的棱集构造准投影分离线,通过沿着准投影分离线方向投影可将3D凸多面体碰撞检测降维为2D凸多边形的碰撞检测问题;最后将分离投影的思想延用至为2D凸多边形的碰撞检测,再次将2D问题降维为1D问题.算法分析和实验结果表明,该算法对于凸多面体碰撞检测具有较高的响应速度和检测精度.     

基于面向对象的线画图立体图形的实体模型设计

文中应用面向对象的设计方法，针对消除隐藏线算法，为由点，直线段，多边形构成的立体图形设计了一种实体模型，该实体模型具有封装性和可维护性等面向对象设计方法的优点，同时由于记录了大量的立体图形的点、边、面的拓扑关系，使消除隐藏线算法减少很多已知点，边、面查找相关的点、边、面的运算，从而提高了算法的效率，使在显示进行平移，放缩，旋转等变换的立体图形时，可较好地满足消除隐藏线的实时性的要求。     

快速成型中一种改进的轮廓线生成算法

在对STL模型分层求交线过程中,针对三角面片的边与切平面很接近时,浮点运算引起的精度损失可能导致的错误交线问题,提出一种基于STL模型局部拓扑的分层算法。将所有可能引起错误交线的三角面片提取出来,建立拓扑结构,以接近切平面的边在切平面的投影替代交线,消除了由于浮点运算误差导致的轮廓线缺边和重边的错误。实验结果表明,该算法在计算出交线段集后不需要再进行修复,简单连接后就能得出正确的切片轮廓线。     

Structures of Periodical Knots and Links as Geometric Models of Complex Surfaces for Designing

Practical modeling of spatial surfaces is more convenient by means of transformation of their flat developments made as topologically connected kinetic structures. Topologically, any surface in 3D space consists of three types of elements: planar facets, linear edges and point vertexes. Planar facets and linear edges can be identifed respectively with the structural units of folding structures and kinematical nets. Here we consider a third possible type of flat transformable structures with vertexes as form-generative units, in which flat developments of surfaces are formed by arranged point sets given by contacting crossing points of the periodic knots and links made of elastic-flexible materials, so that their crossing points have real physical contacts. This new form-generative method can be applied to modeling of both oriented and non-oriented differentiable topological 2D manifolds. The method of form generation based upon the developing properties of periodic structures of knots and links may be applied to many practical fields, including art, design and architecture.     

一种基于正交视图的三维模型多特征匹配算法

针对现今多数三维检索算法在匹配精度、检索速度以及算法复杂度三者难以相互兼顾的问题,文中提出一种基于正交视图的三维模型多特征匹配算法。首先对被检索三维模型的6个正视角进行投影,获得6个正视图像;接着分别用灰度级图像来描述各个正视图特征,并根据投影后模型各面的分布情况填补顶点与面片之间的间隙;然后动态提取每个灰度级图像的投影直方图特征和Zernike矩特征;最后在分析各特征的优缺点的基础上,融合多个特征来匹配三维模型的相似度。与传统LFD算法和D2算法进行对比实验,结果表明,文中算法能较好地提高对三维模型检索的查全率与查准率,具有计算量小、匹配精度高、运行速度快的优点。     

FacetAtlas: multifaceted visualization for rich text corpora

Documents in rich text corpora usually contain multiple facets of information. For example, an article about a specific disease often consists of different facets such as symptom, treatment, cause, diagnosis, prognosis, and prevention. Thus, documents may have different relations based on different facets. Powerful search tools have been developed to help users locate lists of individual documents that are most related to specific keywords. However, there is a lack of effective analysis tools that reveal the multifaceted relations of documents within or cross the document clusters. In this paper, we present FacetAtlas, a multifaceted visualization technique for visually analyzing rich text corpora. FacetAtlas combines search technology with advanced visual analytical tools to convey both global and local patterns simultaneously. We describe several unique aspects of FacetAtlas, including (1) node cliques and multifaceted edges, (2) an optimized density map, and (3) automated opacity pattern enhancement for highlighting visual patterns, (4) interactive context switch between facets. In addition, we demonstrate the power of FacetAtlas through a case study that targets patient education in the health care domain. Our evaluation shows the benefits of this work, especially in support of complex multifaceted data analysis.     

基于多面体的过渡操作

过渡操作在实体造型中具有重要的实用意义。本文给出一种多面体实体过渡操作的定义和实现方法。其基本原理是用可变半径的圆柱面代替多面体上的被操作边，并对这些圆柱面进行交和离散化。利用这种过渡操作可以生成多面体指定棱边或指定边环的过渡平角或过渡圆角。     

Clamping a polygon

Aclamping hand has two opposing parallel edges; the distance between them can vary. We define what it means for the edges of a clamping hand and some edges of a polygon to form aclamp on the polygon. We conjecture that any polygon can be clamped by a hand if its edges are of positive length, but only provide proofs that clamps must exist for convex polygons and for certain polygons composed of two convex chains. The proofs involve extensive case analyses, and it is not obvious how to generalize them.     

Two data structures for building tetrahedralizations

A polyhedral decomposition can be unambiguously described as the collection of four primitive elements (i.e., polyhedra, facets, edges, and vertices) plus their mutual adjacency relations. We consider here the problem of representing a specific kind of polyhedral decomposition, i.e., a tetrahedralization. We describe two different representations for a tetrahedralization. The first one can only model polyhedral decompositions with tetrahedral cells, while the second one is suitable for describing any partition of a volume into polyhedral cells with triangular facets. We present two sets of primitive Euler operators, which build and manipulate such representations while maintaining their topological integrity. The use of such operators is demonstrated in connection with two algorithms for building a Delaunay tetrahedralization, which show the different hedralization, which show the different uses of the two representations.     

Efficient computation of volume fractions for multi-material cell complexes in a grid by slicing

The paper presents a novel slicing based method for computation of volume fractions in multi-material solids given as a B-rep whose faces are triangulated and shared by either one or two materials. Such objects occur naturally in geoscience applications and the said computation is necessary for property estimation problems and iterative forward modeling. Each facet in the model is cut by the planes delineating the given grid structure or grid cells. The method, instead of classifying the points or cells with respect to the solid, exploits the convexity of triangles and the simple axis-oriented disposition of the cutting surfaces to construct a novel intermediate space enumeration representation called slice-representation, from which both the cell containment test and the volume-fraction computation are done easily. Cartesian and cylindrical grids with uniform and non-uniform spacings have been dealt with in this paper. After slicing, each triangle contributes polygonal facets, with potential elliptical edges, to the grid cells through which it passes. The volume fractions of different materials in a grid cell that is in interaction with the material interfaces are obtained by accumulating the volume contributions computed from each facet in the grid cell. The method is fast, accurate, robust and memory efficient. Examples illustrating the method and performance are included in the paper.     

A Tight Lower Bound for a Special Case of Quadratic 0–1 Programming

We consider a still NP-complete partial case of the unconstrained binary quadratic optimization problem that can be described in terms of an undirected graph with red edges having negative weights and green edges having positive weights. The maximum vertex degree of the graph is three. It can be assumed w.l.o.g. that every vertex is incident to a red and a green edge. We are looking for a vertex cover with respect to the red edges which covers a subset of green edges of total weight as small as possible. We prove that for all connected such graphs except a subclass of special graphs having exactly five green edges it is possible to find a vertex cover with respect to the red edges for which the total weight of uncovered green edges is at least 1/4 fraction of the total weight of all green edges.