Adaptive marching cubes

The marching cubes algorithm (MC) is a powerful technique for surface rendering that can produce very high-quality images. However, it is not suitable for interactive manipulation of the 3D surfaces constructed from high-resolution volume datasets in terms of both space and time. In this paper, we present an adaptive version of MC called adaptive marching cubes (AMC). It significantly reduces the number of triangles representing the surface by adapting the size of the triangles to the shape of the surface. This improves the performance of the manipulation of the 3D surfaces. A typical example with the volume dataset of size 256×256×113 shows that the number of triangles is reduced by 55%. The quality of images produced by AMC is similar to that of MC. One of the fundamental problems encountered with adaptive algorithms is thecrack problem. Cracks may be created between two neighboring cubes processed with different levels of subdivision. We solve the crack problem by patching the cracks using polygons of the smae shape as those of the cracks. We propose a simple, but complete, method by first abstracting 22 basic configurations of arbitrarily sized cracks and then reducing the handling of these configurations to a simple rule. It requires onlyO(n ²) working memory for an×n×n volume data set.     

移动立方体算法中的三角剖分

Marching Cubes（MC）算法是基于规则体数据抽取等值面的经典算法。分析了该算法中的交点连接问题,解决连接上的二义性问题,从而更好地生成多边形;对于生成的非平面多边形,对三角剖分进行了优化,以此改进了移动立方体算法,通过实验验证了算法的正确性。     

Compressing isosurfaces generated with marching cubes

Published online: 24 January 2002     

A complete lookup table for marching cubes

The well-known marching cubes method is used to generate isosurfaces from volume data or data on a 3D rectilinear grid.To do so,it refers to a lookup table to decide on the possible configurations of the isosurface within a given cube,assuming we know whether each vertex lies inside or outside the surface.However,the vertex values alone do not uniquely determine how the isosurface may pass through the cube,and in particular how it cuts each face of the cube.Earlier lookup tables are deficient in various respects.The possible combinations of the different configurations of such ambiguous faces are used in this paper to find a complete and correct lookup table.Isosurfaces generated using the new lookup table here are guaranteed to be watertight.     

Improving the robustness and accuracy of the marching cubes algorithm for isosurfacing

This paper proposes a modification of the Marching Cubes algorithm for isosurfacing, with the intent of improving the representation of the surface in the interior of each grid cell. Our objective is to create a representation which correctly models the topology of the trilinear interpolant within the cell and which is robust under perturbations of the data and threshold value. To achieve this, we identify a small number of key points in the cell interior that are critical to the surface definition. This allows us to efficiently represent the different topologies that can occur, including the possibility of "tunnels." The representation is robust in the sense that the surface is visually continuous as the data and threshold change in value. Each interior point lies on the isosurface. Finally, a major feature of our new approach is the systematic method of triangulating the polygon in the cell interior.     

On the sizes of extended Fibonacci cubes

Hypercube is a popular interconnection network whose size must be a power of 2. Several interconnection networks have been proposed that do not suffer this limitation. Among them the extended Fibonacci cubes are based on the same sequence of the Fibonacci cubes and share many appealing structural properties. In this paper, we show how Extended Fibonacci Cubes can be seen as (Cartesian) product graphs whose components are hypercubes and Fibonacci Cubes. By exposing this property, we prove a conjecture that there are no distinct Extended Fibonacci Cubes (except the trivial ones) with the same number of nodes. Our result further validates the motivations behind the proposal of this interconnection network as a flexible alternative to hypercubes     

On embedding cycles into faulty twisted cubes

The twisted cube TQ_n is an alternative to the popular hypercube network. Recently, some interesting properties of TQ_n were investigated. In this paper, we study the pancycle problem on faulty twisted cubes. Let f_e and f_v be the numbers of faulty edges and faulty vertices in TQ_n, respectively. We show that, with f_e + f_v ? n − 2, a faulty TQ_n still contains a cycle of length l for every 4 ? l ? ∣V(TQ_n)∣ − f_v and odd integer n ? 3.     

Parallel marching Poisson solvers

The paper presents parallel algorithms for solving Poisson equation at N² mesh points. The methods based on marching techniques are structured for efficient parallel realization. Using orthogonal decomposition properties of arising matrices, the algorithms can be formulated in terms of transformed vectors. On a MIMD computer with not more than N processors, the computations can be performed in horizontal slices with minimal synchronization requirements. Considering an SIMD machine with N² processors, the complexity bound O(log N) has been achieved, whereby the single marching requires 10 log N steps only.     

Lattice of cubes

A new type of lattices, lattice of cubes, is defined and described. It is proved that the number of all subcubes of the cube of the dimension m is 3 ^m . It is shown that the set of such subcubes with an appropriate choice of the operations of union and intersection is a lattice, called the lattice of cubes. An algorithm of constructing this lattice is proposed, and the problem of minimization and maximization of supermodular functions is considered on it. Particular examples of such functions are given. Optimizations algorithms, as well as the possibility of setting and solving a new class of problems on the cubes lattices are discussed.     

Paths in Möbius cubes and crossed cubes

The Möbius cube MQn and the crossed cube CQn are two important variants of the hypercube Qn. This paper shows that for any two different vertices u and v in G∈{MQn,CQn} with n?3, there exists a uv-path of every length from dG(u,v)+2 to n²−1 except for a shortest uv-path, where dG(u,v) is the distance between u and v in G. This result improves some known results.     

基于自适应网格的快速步进法

针对形状重建及Eikonal方程求解问题,提出了一种根据曲面曲率动态地对网格进行细化的快速步进法,证明了该方法在一阶差分情形下符合因果律,在实现中利用哈希表对邻接点进行快速定位。实验结果表明,该方法较已有方法计算误差小,对噪声适应力较强,可有效处理从明暗恢复形状问题。     

Multiscale visualization using data cubes

Most analysts start with an overview of the data before gradually refining their view to be more focused and detailed. Multiscale pan-and-zoom systems are effective because they directly support this approach. However, generating abstract overviews of large data sets is difficult and most systems take advantage of only one type of abstraction: visual abstraction. Furthermore, these existing systems limit the analyst to a single zooming path on their data and thus to a single set of abstract views. This paper presents: 1) a formalism for describing multiscale visualizations of data cubes with both data and visual abstraction and 2) a method for independently zooming along one or more dimensions by traversing a zoom graph with nodes at different levels of detail. As an example of how to design multiscale visualizations using our system, we describe four design patterns using our formalism. These design patterns show the effectiveness of multiscale visualization of general relational databases.     

Edge-fault-tolerant vertex-pancyclicity of augmented cubes

The n-dimensional augmented cube, denoted as AQn, a variation of the hypercube, possesses some properties superior to those of the hypercube. In this paper, we show that every vertex in AQn lies on a fault-free cycle of every length from 3 to n², even if there are up to n−1 edge faults. We also show that our result is optimal.     

Fault-tolerant pancyclicity of augmented cubes

As an enhancement on the hypercube Qn, the augmented cube AQn, prosed by Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2) (2002) 71-84], not only retains some favorable properties of Qn but also possesses some embedding properties that Qn does not. For example, AQn is pancyclic, that is, AQn contains cycles of arbitrary length for n?2. This paper shows that AQn remains pancyclic provided faulty vertices and/or edges do not exceed 2n−3 and n?4.     

Diagnosability of the Mobius cubes

The recently introduced interconnection networks, the Mobius cubes, are hypercube variants that have some better properties than hypercubes. The n-dimensional Mobius cube M_n is a regular graph with 2ⁿ nodes and n2^n-1 edges. The diameter of M_n is about one half that of the n-dimensional hypercube Q _n and the average number of steps between nodes for M_n is about two-thirds of the average for Q_n, and 1-M_n has dynamic performance superior to that of Q_n. Of course, the symmetry of M_n is not superior to that of Q_n, i.e., Q_n is both node symmetric and edge symmetric , whereas M_n is, in general, neither node symmetric (n⩾4) nor edge symmetric (n⩾3). In this paper, we study the diagnosability of M_n. We use two diagnosis strategies, both based on the so-called PMC diagnostic model-the precise (one-step) diagnosis strategy proposed by Preparata et al. (1967) and the pessimistic diagnosis strategy proposed by Friedman (1975). We show that the diagnosability of M_n is the same as that of Q_n , i.e., M_n is n-diagnosable under the precise diagnosis strategy and (2n-2)/(2n-2)-diagnosable under the pessimistic diagnosis strategy     

Geodesic pancyclicity of twisted cubes

The hypercube is one of the most popular interconnection networks since it has simple structure and is easy to implement. An n-dimensional twisted cube, TQ_n, is an important variation of the hypercube Q_n and preserves many of its desirable properties. The problem of embedding linear arrays and cycles into a host graph has attracted substantial attention in recent years. The geodesic cycle embedding problem is for any two distinct vertices, to find all the possible lengths of cycles that include a shortest path joining them. In this paper, we prove that TQ_n is geodesic 2-pancyclic for each odd integer n ? 3. This result implies that TQ_n is edge-pancyclic for each odd integer n ? 3. Moreover, TQ_n × K₂ is also demonstrated to be geodesic 4-pancyclic.     

Fault-tolerant cycle-embedding of crossed cubes

The crossed cube CQ_n introduced by Efe has many properties similar to those of the popular hypercube. However, the diameter of CQ_n is about one half of that of the hypercube. Failures of links and nodes in an interconnection network are inevitable. Hence, in this paper, we consider the hybrid fault-tolerant capability of the crossed cube. Letting f_e and f_v be the numbers of faulty edges and vertices in CQ_n, we show that a cycle of length l, for any 4?l?|V(CQ_n)|−f_v, can be embedded into a wounded crossed cube as long as the total number of faults (f_v+f_e) is no more than n−2, and we say that CQ_n is (n−2)-fault-tolerant pancyclic. This result is optimal in the sense that if there are n−1 faults, there is no guarantee of having a cycle of a certain length in it.     

Embedding meshes into crossed cubes

Crossed cubes are important variants of hypercubes. In this paper, we consider embeddings of meshes in crossed cubes. The major research findings in this paper are: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded in the n-dimensional crossed cube with dilation 1 and expansion 1. (2) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded in the n-dimensional crossed cube with dilation 1 and expansion 2. The obtained results are optimal in the sense that the dilations of the embeddings are 1. The embedding of the 2 × 2ⁿ⁻¹ mesh is also optimal in terms of expansion because it has the smallest expansion 1.