Computing with Shapes: Reconstruction and Decimation

形状计算：重建和抽取Tamal Dey俄亥俄州使用形状计算在CAD/CAM、医学成像、物理模拟等多个应用领域中非常普遍。我们建议研究其中的两种计算，即重建和抽取。选择这两种手术是因为它们在应用中的迫在眉睫的相关性，我们正在进行的研究，以及它们丰富的理论挑战。我们主要关注低维形状，如二维和三维的曲线和曲面。这些形状在应用中是普遍存在的，对它们的理解是向高维形状发展的关键。我们所说的重建是指从一组样本点计算一个形状的分段线性近似。激光扫描仪的现代技术使得从物体边界获得密集的样本点变得容易。这些采样点的分段线性近似有助于为对象建模，以进行原型制作、视觉检查和进一步的重新设计。这个问题已经被图形界研究过，他们使用数值方法来解决这个问题。计算几何学家用离散几何和微分几何的思想来解决这个问题。虽然这些方法已经取得了相当大的成功，但行业对处理具有边界、尖锐特征和噪声的形状的需求越来越大，这些都是当前方法无法很好地解决的。抽取形状是减小表示该形状的数据结构大小的过程。由于输入样本集通常很大，因此从样本重建的模型可能具有大量元素，例如三角形。这样一个包含大量元素的模型对于进一步的处理(如图形渲染或物理模拟)来说变得很笨拙。一个标准的策略是通过边缘收缩来减少三角形的数量。在此方法中，选定的边收缩到一个新顶点。所有事件简化都相应地进行了简化。大量的应用对抽取过程中的形状的几何和拓扑提出了不同的要求。虽然一些应用程序需要保留拓扑，但其他应用程序希望以受控的方式更改它。这位研究人员与社区中的其他研究人员一起研究了边收缩时保持拓扑的问题。允许以受控方式改变拓扑结构的问题在很大程度上仍未得到解决。图形的几何图形取决于替换收缩边的新顶点的位置。用于此目的的一个有效的数值工具是二次误差度量，它试图优化新顶点到相邻三角形平面的距离之和。该策略倾向于生成各向异性网格，其三角形根据形状的曲率拉长。尽管各向异性网格在某些应用程序中是首选的，但也有一些应用程序倾向于具有有界长宽比的三角形的各向同性网格。在重建和抽取之后，我们能产生一个各向同性的网格吗？有没有可能在重建后对模型进行抽取，而不是抽取样本本身？在最近的一项研究中，这位调查者试图解决这个问题。这项工作远未完成，我们建议继续进行，以获得新的结果。为这一项目提出的理论研究将需要结合计算拓扑学新兴领域的核心问题--拓扑学和几何的思想。作为我们理论研究的结果，将开发新的算法，但它们的最终性能将通过实施进行测试，这也是我们议程的一部分。

Computing with Shapes: Reconstruction and DecimationTamal DeyOhio StateComputations with shapes are prevalent in a number of application areas ranging over CAD/CAM, medical imaging, physical simulations and so on. We propose studying two of these computations, namely, reconstruction and decimation. The choice of these two operations is prompted by their imminent relevance in applications, our ongoing research on them, and their rich theoretical challenges. We focus mainly on low dimensional shapes such as curves and surfaces in two and three dimensions. These shapes are ubiquitous in applications and their understanding is essential to move forward to higher dimensional shapes.By reconstruction we mean computing a piecewise linear approximation of a shape from a set of sample points. Modern technology with laser scanners has made it easy to obtain a dense set of sample points from the boundary of an object. A piecewise linear approximation from these sample points help to model the object for prototyping, visual inspection, and further reengineering. The problem has been studied by graphics community who used numerical approaches to the problem. Computational geometers attacked the problem with ideas from discrete and differential geometry. Although a considerable success has been made by these approaches, there are growing demand from the industry to handle shapes with boundary, sharp features, noise which cannot be tackled robustly with the current methods. Decimation of a shape is the process of reducing the size of the data structure representing the shape. The model reconstructed from a sample may have a large number of elements such as triangles since the input sample set is typically large. Such a model with large number of elements becomes unwieldy for further processing such as graphic rendering or physical simulations. A standard strategy is to reduce the number of triangles by edge contractions. In this method selected edges are contracted to a new vertex. All incident simplices are contracted accordingly. Different kinds of demands on the geometry and topology of the shapes during decimation are put forward by multitude of applications. While some of the applications need to preserve the topology, the others want to change it in a controlled manner. The investigator with other researchers in the community studied the problem of preserving topology during edge contractions. The question of allowing topology change in a controlled manner is still largely unsolved. The geometry of the shape depends on the location of the new vertex replacing the contracted edge. An effective numerical tool used for this purpose is the quadric error measure that tries to optimize the the sum of distances of the new vertex from the planes of the neighboring triangles. This strategy tends to produce an anisotropic mesh whose triangles are elongated according to the curvature of the shape. Although anisotropic meshes are preferred in some applications, there are others who favor isotropic meshes that have triangles with bounded aspect ratio. Can we produce an isotropic mesh after reconstruction and decimation? Instead of decimating the model after reconstruction, is it possible to decimate the sample itself? In a recent work, the investigator tries to address this issue. This work is far from complete and we propose to continue it for new results.Theoretical studies proposed for this project would require combining ideas from topology and geometry, a central issue in the emergent field of Computational Topology. New algorithms will be developed as a result of our theoretical study, but their ultimate proof of performance will be tested through implementation which is also part of our agenda.