Analysis of Schedule and Layout Tuning for Sparse Matrices With Compound Entries on GPUs

Large sparse matrices with compound entries, i.e. complex and quaternionic matrices as well as matrices with dense blocks, are a core component of many algorithms in geometry processing, physically based animation and other areas of computer graphics. We generalize several matrix layouts and apply joint schedule and layout autotuning to improve the performance of the sparse matrix-vector product on massively parallel graphics processing units. Compared to schedule tuning without layout tuning, we achieve speedups of up to 5.5 × . In comparison to cuSPARSE, we achieve speedups of up to 4.7 × .     

A visual tool for computer supported learning: The robot motion planning example

We introduce an effective computer aided learning visual tool (CALVT) to teach graph-based applications. We present the robot motion planning problem as an example of such applications. The proposed tool can be used to simulate and/or further to implement practical systems in different areas of computer science such as graphics, computational geometry, robotics and networking. In the robot motion planning example, CALVT enables users to setup the working environment by creating obstacles and a robot of different shapes, specifying starting and goal positions, and setting other path or environment parameters from a user-friendly interface. The path planning system involves several phases. Each of these modules is complex and therefore we provide the possibility of visualizing graphically the output of each phase. Based on our experience, this tool has been an effective one in classroom teaching. It not only cuts down, significantly, on the instructor’s time and effort but also motivates senior/graduate students to pursue work in this specific area of research.     

基于3D WARP的混合绘制算法研究

几何绘制（GBR）是传统计算机图形学的研究内容,随着计算机图形学的发展,图象绘制（IBR）成为研究热点,两者各有其优缺点,其中,GBR具有绘制自由度大,速度慢等特点,需占用大量系统资源,而IBR则正好相反,因此,寻找一种能够结合GBR与IBR优点,而又能克服其缺点的方法是必要的,为了使几何绘制和图象绘制能够实现有机地结合,提出了一 种全新的“基于几何与图象的混合绘制（Geometry and Image-Based Hybrid Rendering,GIBHR)”方法,并分析了GIBHR的研究内容,同时给出了GIBHR的绘制流程,在此基础上,将IBR领域的3DWARP 法在几何绘制领域进行了进一步拓展与推论,证明了其可行性和有效性,提出了一种基于3DWARP的混合绘制算法,最后对算法进行了实验,结果表明,该算法在提高几何绘制速度方面具有明显优势,且具有空间反走样能力。     

MATLAB软件在空间解析几何教学中的应用探索

深入研究MATLAB软件在解析几何学中的应用,讨论二次曲面作图呈现的一般规律性。对于特定范围内图形的绘制,采用全新的图形挖切法,可全面了解图形的结构。研究在同一坐标系下,作出不同的曲面图形,从而帮助学生理解图形之间的位置关系,避免了手工运算的繁琐性。最后,探讨在解析几何中出现的著名立体,得到它的图形,从而突破教学难点。     

A facsimile-based graphics editing system by auxiliary mark recognition

This paper describes a facsimile-based graphics editing system using handwritten mark recognition, and presents some experimental results with the system. In a manner different from usual graphics editors based on CRT displays and data tablets, only facsimiles are used as input and output devices in this system. As the first stage in processing, a graphic subject is first given as a set of line drawings and characters handwritten on a sheet of paper, and it is then input into the computer as a binary picture from a facsimile transmitter. Auxiliary editing information is input into the computer as handwritten marks or seal marks prepared on a separate sheet of paper. As the second stage, the marks are recognized and used to create a mark parameter list for the graphics editing. Third, referencing the mark parameter list, the graphics are expressed by using a set of graphic commands, and edited by the computer. Finally, a correct edited copy of the graphics is constructed by picture processing based on graphic commands, and it is output to a facsimile receiver. Very good results have been obtained for various kinds of hand-written graphics by using the system described here.     

网格参数化研究进展

网格参数化是计算机图形学和数字几何处理的基本工具,有着广泛的应用背景.对网格参数化的研究进展进行了综述,主要从参数域和参数化质量两个方面介绍了网格参数化的研究现状.根据参数域的不同,讨论了平面参数化、基网格参数化、球面参数化以及曲面间的交叉参数化;根据参数化质量的不同,介绍了保长度的参数化、保特征的参数化以及致力于参数域简单的参数化.对参数化进行了分类介绍和讨论分析,概括介绍了每类方法的主要思想,讨论了每类方法的主要特性,对其中一些方法进行了比较分析,并对参数化方法存在的难点问题和未来可能的研究方向进行了总结,以期对参数化的研究进展有全面的了解.     

Information processing with structured excitable medium

There are many ways in which a nonlinear chemical medium can be used for information processing. Here we are concerned with an excitable medium and the straightforward method of information coding: a single excitation pulse represents a bit of information and a group of excitations forms a message. Our attention is focused on a specific type of nonhomogeneous medium that has an intentionally introduced geometrical structure of regions characterized by different excitability levels. We show that in information processing applications the geometry plays an equally important role as the dynamics of the medium and allows one to construct devices that perform complex signal processing operations even for a relatively simple kinetics of the reactions involved. In the paper we review a number of published chemical realizations of simple information processing devices like logical gates or memory cells and we show that by combining these devices as building blocks the medium can perform complex operations like for example counting of arriving excitations. We also present a new, simple realizations of chemical signal diode that transmits pulses in one direction only.     

基于VTK分形理论的研究

分形理论是一种新兴的几何学,在多种学科中都有着广泛的应用.可视化图形工具包是一个功能强大的可视化和图形图像处理类库.运用VTK流水线进行图形以及三维渲染可使现阶段的分形理论研究可视化,实现分形图形的逼真模拟.在分析分形理论基本算法的基础上,借助VTK设计二维和三维分形图形绘制的渲染流水线,提供生成分形图形和三维分形实体的一种新方法,并以典型的分形集合(曼德尔伯特集)为例,显示渲染效果.     

谈谈图学教材

讨论大图学下的教学理念与方法及大图学学科系列教材的配套建设问题。从学科 分类、图学的科学基础、计算基础、图学实践、图学应用等各个角度讨论了图学的理论教学与 实践教学,以及各学科间的相互关系。基于形是图之源,图是形的载体的认识基础,给出了工 程图学、画法几何、计算机图形学、计算机图像学等主要教材的一些编写原则。基于图学的根 本是几何,建议专门编写一本《图学计算基础》作为图学的公共教材。     

Approximate Symmetry Detection in Partial 3D Meshes

Symmetry is a common characteristic in natural and man‐made objects. Its ubiquitous nature can be exploited to facilitate the analysis and processing of computational representations of real objects. In particular, in computer graphics, the detection of symmetries in 3D geometry has enabled a number of applications in modeling and reconstruction. However, the problem of symmetry detection in incomplete geometry remains a challenging task. In this paper, we propose a vote‐based approach to detect symmetry in 3D shapes, with special interest in models with large missing parts. Our algorithm generates a set of candidate symmetries by matching local maxima of a surface function based on the heat diffusion in local domains, which guarantee robustness to missing data. In order to deal with local perturbations, we propose a multi‐scale surface function that is useful to select a set of distinctive points over which the approximate symmetries are defined. In addition, we introduce a vote‐based scheme that is aware of the partiality, and therefore reduces the number of false positive votes for the candidate symmetries. We show the effectiveness of our method in a varied set of 3D shapes and different levels of partiality. Furthermore, we show the applicability of our algorithm in the repair and completion of challenging reassembled objects in the context of cultural heritage.     

Fast and Exact (Poisson) Solvers on Symmetric Geometries

In computer graphics, numerous geometry processing applications reduce to the solution of a Poisson equation. When considering geometries with symmetry, a natural question to consider is whether and how the symmetry can be leveraged to derive an efficient solver for the underlying system of linear equations. In this work we provide a simple representation‐theoretic analysis that demonstrates how symmetries of the geometry translate into block diagonalization of the linear operators and we show how this results in efficient linear solvers for surfaces of revolution with and without angular boundaries.     

Theories for graphics processors in TIPS-1

This paper describes the theoretical aspects of graphics processors in CAD/CAM system TIPS-1. As one of the man-machine interfaces in the CAD/CAM field, computer graphics plays an important role. And this field, computer graphics involves not only image processing with shaded pictures produced by raster scan displays but also sectional and/or perspective view drawing picture by line drawing display. By using TIPS-1 graphics processors, we can get both raster scan and line drawing pictures for the same of modeled 3-D geometry. The following items are considered as the necessary conditions for developing graphics processors.

• • To develop geometric modeling theory.

• • To develop generative geometry pattern processing theory.

• • To implement problem-oriented graphics routines based on above conditions.

How to complete these conditions is described with several figures and graphic outputs.     

A computer graphics course for the two cultures

The subject of computer graphics offers a special educational opportunity for bringing together students from the two cultures of the arts/humanities and of the sciences/technologies. The author describes a computer graphics course with this approach. Several important problems arise because of students' varying backgrounds in programming and their expectations, the lack of suitable texts, and the lack of suitably-oriented computer graphics centers. The course schedule is composed of lectures, discussions of readings, and workshops in a computer graphics facility. The hardware and software basis of the course is flexible. Students complete an assigned initial project, a final project of their choice, and are responsible for documenting their project visually and verbally before the close of the semester. Student performance and evaluation of the course suggest this cross-cultural approach is a valid, worthwhile experiment to introduce the structure and significance of computer graphics imagery and computer graphics display systems.     

Symmetry in 3D Geometry: Extraction and Applications

The concept of symmetry has received significant attention in computer graphics and computer vision research in recent years. Numerous methods have been proposed to find, extract, encode and exploit geometric symmetries and high‐level structural information for a wide variety of geometry processing tasks. This report surveys and classifies recent developments in symmetry detection. We focus on elucidating the key similarities and differences between existing methods to gain a better understanding of a fundamental problem in digital geometry processing and shape understanding in general. We discuss a variety of applications in computer graphics and geometry processing that benefit from symmetry information for more effective processing. An analysis of the strengths and limitations of existing algorithms highlights the plenitude of opportunities for future research both in terms of theory and applications.     

Anderson Acceleration for Nonconvex ADMM Based on Douglas-Rachford Splitting

The alternating direction multiplier method (ADMM) is widely used in computer graphics for solving optimization problems that can be nonsmooth and nonconvex. It converges quickly to an approximate solution, but can take a long time to converge to a solution of high-accuracy. Previously, Anderson acceleration has been applied to ADMM, by treating it as a fixed-point iteration for the concatenation of the dual variables and a subset of the primal variables. In this paper, we note that the equivalence between ADMM and Douglas-Rachford splitting reveals that ADMM is in fact a fixed-point iteration in a lower-dimensional space. By applying Anderson acceleration to such lower-dimensional fixed-point iteration, we obtain a more effective approach for accelerating ADMM. We analyze the convergence of the proposed acceleration method on nonconvex problems, and verify its effectiveness on a variety of computer graphics including geometry processing and physical simulation.     

Fourier polygons

Polygons are everywhere, but one place the author didn't expect to see polygons is in the Fourier transform, but he found them there as well. The Fourier transform is an indispensable tool in signal processing. In computer graphics, it helps us understand and cure problems as diverse as jaggies on the edge of polygons, blocky looking textures, and animated objects that appear to jump erratically as they move across the screen. His friend and colleague Alvy Ray Smith recently wrote a memo that demonstrated a surprising interpretation of the Fourier transform. He showed how in some circumstances the Fourier transform looks like nothing more than operations on regular polygons. The article is about that fascinating insight. He starts off with by using complex numbers to do geometry and then moves on to the Fourier series, building up to a discussion of the new interpretation     

An Interactive Approach to Point Cloud Triangulation

We present an interactive system for the generation of high quality triangle meshes that allows us to handle hybrid geometry (point clouds, polygons,. . .) as input data. In order to be able to robustly process huge data sets, we exploit graphics hardware features like the raster manager and the z-buffer for specific sub-tasks in the overall procedure. By this we significantly accelerate the stitching of mesh patches and obtain an algorithm for sub-sampling the data points in linear time. The target resolution and the triangle alignment in sub-regions of the resulting mesh can be controlled by adjusting the screen resolution and viewing transformation. An intuitive user interface provides a flexible tool for application dependent optimization of the mesh.     

Teaching elementary concepts in quantum mechanics with computer graphics

Students in a beginning quantum mechanics course worked with interactive computer graphics before being introduced to the formal structure of the subject. The computer programs and their use in teaching different concepts are described.     

Digital Differential Geometry Processing

The theory and methods of digital geometry processing has been a hot research area in computer graphics, as geometric models serves as the core data for 3D graphics applications. The purpose of this paper is to introduce some recent advances in digital geometry processing, particularly mesh fairing, surface parameterization and mesh editing, that heavily use differential geometry quantities. Some related concepts from differential geometry, such as normal, curvature, gradient, Laplacian and their counterparts on digital geometry are also reviewed for understanding the strength and weakness of various digital geometry processing methods.