Computing with Shapes: Reconstruction and Decimation

形状计算在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.