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.     

Optimum sweeps of simple polygons with two guards

A polygon P admits a sweep if two mobile guards can detect an unpredictable, moving target inside P  , no matter how fast the target moves. Two guards move on the polygon boundary and are required to always be mutually visible. The objective of this study is to find an optimum sweep such that the sum of the distances travelled by the two guards in the sweep is minimized. We present an O(n²)$O(n^2)$ time and O(n)$O(n)$ space algorithm for optimizing this metric, where n   is the number of vertices of the given polygon. Our result is obtained by reducing this problem to finding a shortest path between two nodes in a graph of size O(n)$O(n)$.     

基于Loop细分算法的人体模型网格平滑

网格平滑是实现三维模型离散造型的主要方法。为了实现数字人体几何模型的光顺效果,本文提出一种基于Loop细分算法的三维人体模型的网格平滑方法。细分曲面是用低分辨率的控制网格和定义在控制网格上的一种细分规则来表示曲面的,它能有效改善三维人体几何模型的表面不光滑以及分辨率低的缺点。实验证明,该方法对基于参数化建模方法的、多曲率网格人体模型取得了很好的效果,实现简单高效,特征保持效果也很好。     

基于平行截面上轮廓之间重构问题的研究

研究了基于平行截面上两多边形轮廓重构的基本问题,给出了利用体积最大化作为度量标准来求得一个"较好"并且合法的重构的目标函数,然后得出:其中一个多边形轮廓在其所在的截面上沿着法向平移、在截面内平移和在截面内等比例缩放都不影响最大化体积后的结果。该结论对于三维实体的可视化和几何造型领域具有重要的实用价值。     

Boolean operations on general planar polygons

Computing boolean operations between general planar polygons is one of the fundamental problems in geometric and solid modeling. In this work we present a new algorithm to calculate intersection, union and difference, valid for general planar polygons (manifold and non-manifold, with and without holes), based on a formal representation system. This formal model is based on the concept of simplicial chain, developed by Feito and Rivero (Computers & Graphics 22(5) (1998)). Using algebraic operations between simplicial chains we can obtain any general polygon and the Boolean operations between them. The fact of that our algorithm is based on simplicial chains and their operations, reduces the study of special cases, and allows us to develop a robust and efficient algorithm to calculate the intersection between general polygons.     

基于方位角计算的拓扑多边形自动构建快速算法

自动构建多边形是地理数据拓扑关系建立的重点和难点之一,其算法的自动化、速度和复杂性一直制约着ＧＩＳ中有关模块的设计开发和地理数据库的建立。针对该问题,通过研究,提出了一种基于方位角计算的多边形快速构建算法,很好地解决了多边形的构建及“岛屿”与“飞地”的处理问题,整个算法结构清晰,简单易懂,且程序设计易于实现。     

基于凸包求解的简单多边形方向判断新算法

Graham ScanA求解简单多边形凸包算法简洁高效,但是对于未确定方向的简单多边形,该算法需设定一个方向求解其凸包。提出一种新的算法,该算法通过利用凸包求解的Graham ScanA算法来判断简单多边形的方向。算法取得了较好的实用效果。     

非均匀有理B样条曲线在工业建模中的优势

从工业建模的需求出发,对主流建模手段多边形、NURBS与细分表面进行了对比。NURBS建模手段因在精确性、控制性和系统资源占用率的平衡性最优而确定为最终技术方案,以完成设计与建模任务。