A K-hedral tiling of a 2D finite domain is a covering of the domain with tiles without gaps or overlaps, where each tile is congruent to one of the K distinct shapes called prototiles. K, the number of prototiles, is preferred to be as small as possible for congruent tiling appearance and reducing fabrication cost, e.g., by molding. Typically, a forward approach is adopted to produce K-hedral tilings by prescribing a set of prototiles and placing prototile instances (i.e., tiles) to cover the input domain. However, the prescribed prototile set may not be sufficient to tile the domain (for small K) or may lead to tiling results with excessive prototiles more than needed (for large K).

Abstract A body‐supporting assembly is an assembly of parts that physically supports a human body during activities like sitting, lying, or leaning. A body‐supporting assembly has a complex global shape to support a specific human body posture, yet each component part has a relatively simple geometry to facilitate fabrication, storage, and maintenance. In this paper, we aim to model and design a personalized body‐supporting assembly that fits a given human body posture, aiming to make the assembly comfortable to use. We choose to model a body‐supporting assembly from scratch to offer high flexibility for fitting a given body posture, which however makes it challenging to determine the assembly's topology and geometry. To address this problem, we classify parts in the assembly into two categories according the functionality: supporting parts for fitting different portions of the body and connecting parts for connecting all the supporting parts to form a stable structure. We also propose a geometric representation of supporting parts such that they can have a variety of shapes controlled by a few parameters. Given a body posture as input, we present a computational approach for designing a body‐supporting assembly that fits the posture, in which the supporting parts are initialized and optimized to minimize a discomfort measure and then the connecting parts are generated using a procedural approach. We demonstrate the effectiveness of our approach by designing body‐supporting assemblies that accommodate to a variety of body postures and 3D printing two of them for physical validation.

Convolutional neural networks, in which each layer receives features from the previous layer(s) and then aggregates/abstracts higher level features from them, are widely adopted for image classification. To avoid information loss during feature aggregation/abstraction and fully utilize lower layer features, we propose a novel decision fusion module (DFM) for making an intermediate decision based on the features in the current layer and then fuse its results with the original features before passing them to the next layers. This decision is devised to determine an auxiliary category corresponding to the category at a higher hierarchical level, which can, thus, serve as category-coherent guidance for later layers. Therefore, by stacking a collection of DFMs into a classification network, the generated decision fusion network is explicitly formulated to progressively aggregate/abstract more discriminative features guided by these decisions and then refine the decisions based on the newly generated features in a layer-by-layer manner. Comprehensive results on four benchmarks validate that the proposed DFM can bring significant improvements for various common classification networks at a minimal additional computational cost and are superior to the state-of-the-art decision fusion-based methods. In addition, we demonstrate the generalization ability of the DFM to object detection and semantic segmentation.

We study a problem of modeling wireframe meshes where the vertices and edges fall into a set of discrete equivalence classes, respectively. This problem is motivated by the need of fabricating large wireframe structures at lower cost and faster speed since both nodes (thickened vertices) and rods (thickened edges) can be mass-produced. Given a 3D shape represented as a wireframe mesh, our goal is to compute a set of template vertices and a set of template edges, whose instances can be used to produce a fabricable wireframe mesh that approximates the input shape. To achieve this goal, we propose a computational approach that generates the template vertices and template edges by iteratively clustering and optimizing the mesh vertices and edges. At the clustering stage, we cluster mesh vertices and edges according to their shape and length, respectively. At the optimization stage, we first locally optimize the mesh to reduce the number of clusters of vertices and/or edges, and then globally optimize the mesh to reduce the intra-cluster variance for vertices and edges, while facilitating fabricability of the wireframe mesh. We demonstrate that our approach is able to model wireframe meshes with various shapes and topologies, compare it with three state-of-the-art approaches to show its superiority, and validate fabricability of our results by making three physical prototypes.

This paper presents a new algorithm, Weighted Squared Volume Minimization (WSVM), for generating high-quality tetrahedral meshes from closed triangle meshes. Drawing inspiration from the principle of minimal surfaces that minimize squared surface area, WSVM employs a new energy function integrating weighted squared volumes for tetrahedral elements. When minimized with constant weights, this energy promotes uniform volumes among the tetrahedra. Adjusting the weights to account for local geometry further achieves uniform dihedral angles within the mesh. The algorithm begins with an initial tetrahedral mesh generated via Delaunay tetrahedralization and proceeds by sequentially minimizing volume-oriented and then dihedral angle-oriented energies. At each stage, it alternates between optimizing vertex positions and refining mesh connectivity through the iterative process. The algorithm operates fully automatically and requires no parameter tuning. Evaluations on a variety of 3D models demonstrate that WSVM consistently produces tetrahedral meshes of higher quality, with fewer slivers and enhanced uniformity compared to existing methods.

Abstract We present a computational framework for modeling land parcels and streets. In the real world, parcels and streets are highly coupled with each other since a street network connects all the parcels in a certain area. However, existing works model parcels and streets separately to simplify the problem, resulting in urban layouts with irregular parcels and/or suboptimal streets. In this paper, we propose a hierarchical approach to co‐generate parcels and streets from a user‐specified polygonal land shape, guided by a set of fundamental urban design requirements. At each hierarchical level, new parcels are generated based on binary splitting of existing parcels, and new streets are subsequently generated by leveraging efficient graph search tools to ensure that each new parcel has a street access. At the end, we optimize the geometry of the generated parcels and streets to further improve their geometric quality. Our computational framework outputs an urban layout with a desired number of regular parcels that are reachable via a connected street network, for which users are allowed to control the modeling process both locally and globally. Quantitative comparisons with state‐of‐the‐art approaches show that our framework is able to generate parcels and streets that are superior in some aspects.

A mechanism is an assembly of moving parts interconnected by joints to transfer an input motion to a desired output motion. Traditionally, to generate a complex motion, mechanisms are modeled by selecting and combining a number of mechanical parts with simple shapes such as links, gears, and cams. Combining multiple mechanical parts results in a mechanism with an intricate topology, which not only complicates assembly and maintenance but also deteriorates the functionality of generating motions due to accumulation of manufacturing imprecisions. To get rid of these limitations, we study mechanisms with a single pair of moving parts for generating complex motions. We model the pair of moving parts as a pair of conjugate surfaces with multiple conjugation points, forming a multi-point conjugation mechanism. To study this new mechanism, we establish a connection between conjugate surface pairs and form-closure grasps to formulate a dynamic form closure condition under which one conjugate surface is able to continuously transfer the motion to the other conjugate surface by utilizing multiple conjugation points. Guided by the condition, we propose an optimization-based approach to model the geometry of a multi-point conjugation mechanism for exactly generating a user-specified motion, in 1-, 2-, or 3-DOF motion space. The core of our approach is to model multiple conjugate curve pairs that satisfy various requirements in multi-point conjugation, dynamic form closure, and surface fabricability. We demonstrate the effectiveness of our approach by modeling different classes of multi-point conjugation mechanisms to generate various motions, evaluating the mechanisms' kinematic performance with 3D printed prototypes, and presenting three applications of these mechanisms.

Adversarial attack on point clouds plays a vital role in evaluating and improving the adversarial robustness of 3D deep learning models. Current attack methods are mainly applied by point perturbation in a non-manifold manner. In this paper, we formulate a novel manifold attack, which deforms the underlying 2-manifold surfaces via parameter plane stretching to generate adversarial point clouds. First, we represent the mapping between the parameter plane and underlying surface using generative-based networks. Second, the stretching is learned in the 2D parameter domain such that the generated 3D point cloud fools a pretrained classifier with minimal geometric distortion. Extensive experiments show that adversarial point clouds generated by manifold attack are smooth, undefendable and transferable, and outperform those samples generated by the state-of-the-art non-manifold ones.

This paper proposes a method to model masonry shell structures where the shell elements fall into a set of discrete equivalence classes. Such shell structure can reduce the fabrication cost and simplify the physical construction due to reuse of a few template shell elements. Given a freeform surface, our goal is to generate a small set of template shell elements that can be reused to produce a seamless and buildable structure that closely resembles the surface. The major technical challenge in this process is balancing the desire for high reusability of template elements with the need for a seamless and buildable final structure. To address the challenge, we define three error metrics to measure the seamlessness and buildability of shell structures made from discrete equivalence classes and develop a hierarchical cluster-and-optimize approach to generate a small set of template elements that produce a structure closely approximating the surface with low error metrics. We demonstrate the feasibility of our approach on various freeform surfaces and geometric patterns, and validate buildability of our results with four physical prototypes. Code and data of this paper are at https://github.com/Linsanity81/TileableShell.

Abstract We study structural rigidity for assemblies with mechanical joints. Existing methods identify whether an assembly is structurally rigid by assuming parts are perfectly rigid. Yet, an assembly identified as rigid may not be that “rigid” in practice, and existing methods cannot quantify how rigid an assembly is. We address this limitation by developing a new measure, worst‐case rigidity, to quantify the rigidity of an assembly as the largest possible deformation that the assembly undergoes for arbitrary external loads of fixed magnitude. Computing worst‐case rigidity is non‐trivial due to non‐rigid parts and different joint types. We thus formulate a new computational approach by encoding parts and their connections into a stiffness matrix, in which parts are modeled as deformable objects and joints as soft constraints. Based on this, we formulate worst‐case rigidity analysis as an optimization that seeks the worst‐case deformation of an assembly for arbitrary external loads, and solve the optimization problem via an eigenanalysis. Furthermore, we present methods to optimize the geometry and topology of various assemblies to enhance their rigidity, as guided by our rigidity measure. In the end, we validate our method on a variety of assembly structures with physical experiments and demonstrate its effectiveness by designing and fabricating several structurally rigid assemblies.

Interlocking puzzles are intriguing geometric games where the puzzle pieces are held together based on their geometric arrangement, preventing the puzzle from falling apart. High-level-of-difficulty , or simply high-level , interlocking puzzles are a subclass of interlocking puzzles that require multiple moves to take out the first subassembly from the puzzle. Solving a high-level interlocking puzzle is a challenging task since one has to explore many different configurations of the puzzle pieces until reaching a configuration where the first subassembly can be taken out. Designing a high-level interlocking puzzle with a user-specified level of difficulty is even harder since the puzzle pieces have to be interlocking in all the configurations before the first subassembly is taken out. In this paper, we present a computational approach to design high-level interlocking puzzles. The core idea is to represent all possible configurations of an interlocking puzzle as well as transitions among these configurations using a rooted, undirected graph called a disassembly graph and leverage this graph to find a disassembly plan that requires a minimal number of moves to take out the first subassembly from the puzzle. At the design stage, our algorithm iteratively constructs the geometry of each puzzle piece to expand the disassembly graph incrementally, aiming to achieve a user-specified level of difficulty. We show that our approach allows efficient generation of high-level interlocking puzzles of various shape complexities, including new solutions not attainable by state-of-the-art approaches.

Exact 3D path generation is a fundamental problem of designing a mechanism to make a point exactly move along a prescribed 3D path , driven by a single actuator. Existing mechanisms are insufficient to address this problem. Planar linkages and their combinations with gears and/or plate cams can only generate 2D paths while 1-DOF spatial linkages can only generate 3D paths with rather simple shapes. In this paper, we present a new 3D cam-linkage mechanism, consisting of two 3D cams and five links, for exactly generating a continuous 3D path. To design a 3D cam-linkage mechanism, we first model a 3-DOF 5-bar spatial linkage to exactly generate a prescribed 3D path and then reduce the spatial linkage's DOFs from 3 to 1 by composing the linkage with two 3D cam-follower mechanisms. Our computational approach optimizes the 3D cam-linkage mechanism's topology and geometry to minimize the mechanism's total weight while ensuring smooth, collision-free, and singularity-free motion. We show that our 3D cam-linkage mechanism is able to exactly generate a continuous 3D path with arbitrary shape and a finite number of C 0 points, evaluate the mechanism's kinematic performance with 3D printed prototypes, and demonstrate that the mechanism can be generalized for exact 3D motion generation.

The emerging 4D printing techniques open new horizons for fabricating self-actuated deformable objects by combing strength of 3D printing and stimuli-responsive shape memory materials. This article focuses on designing self-actuated deformable solids for 4D printing such that a solid can be programmed into a temporary shape and later recovers to its original shape after heating. To avoid a high material cost, we choose a dual-material strategy that mixes an expensive thermo-responsive shape memory polymer (SMP) material with a common elastic material, which however leads to undesired deformation at the shape programming stage. We model this shape programming process as two elastic models with different parameters linked by a median shape based on customizing a constitutive model of thermo-responsive SMPs. Taking this material modeling as a foundation, we formulate our design problem as a nonconvex optimization to find the distribution of SMP materials over the whole object as well as the median shape, and develop an efficient and parallelizable method to solve it. We show that our proposed approach is able to design self-actuated deformable objects that cannot be achieved by state of the art approaches, and demonstrate their usefulness with three example applications.

Abstract An assembly refers to a collection of parts joined together to achieve a specific form and/or functionality. Designing assemblies is a non‐trivial task as a slight local modification on a part's geometry or its joining method could have a global impact on the structural and/or functional performance of the whole assembly. Assemblies can be classified asstructuresthat transmit force to carry loads andmechanismsthat transfer motion and force to perform mechanical work. In this state‐of‐the‐art report, we focus on computational design of structures with rigid parts, which generally can be formulated as a geometric modeling and optimization problem. We broadly classify existing computational design approaches, mainly from the computer graphics community, according to high‐level design objectives, including fabricability, structural stability, reconfigurability, and tileability. Computational analysis of various aspects of assemblies is an integral component in these design approaches. We review different classes of computational analysis and design methods, discuss their strengths and limitations, make connections among them, and propose possible directions for future research.

Motion control, both on the trajectory and timing, is crucial for mechanical automata to perform functionalities such as walking and entertaining. We present composite cam-follower mechanisms that can control their spatial-temporal motions to exactly follow trajectories and timings specified by users, and propose a computational technique to model, design, and optimize these mechanisms. The building blocks of our mechanisms are a new kind of cam-follower mechanism with a modified joint, in which the follower can perform spatial motion on a planar, cylindrical, or spherical surface controlled by the 3D cam's profile. We parameterize the geometry of these cam-follower mechanisms, formulate analytical equations to model their kinematics and dynamics, and present a method to combine multiple cam-follower mechanisms into a working mechanism. Taking this modeling as a foundation, we propose a computational approach to designing and optimizing the geometry and layout of composite cam-follower mechanisms, with an objective of performing target spatial-temporal motions driving by a small motor torque. We demonstrate the effectiveness of our technique by designing different kinds of personalized automata and showing results not attainable by conventional mechanisms.

We present a computational framework for modeling and optimizing complex assemblies using cone joints. Cone joints are integral joints that generalize traditional single-direction joints such as mortise and tenon joints to support a general cone of directions for assembly. This additional motion flexibility not just reduces the risk of deadlocking for complex joint arrangements, but also simplifies the assembly process, in particular for automatic assembly by robots. On the other hand, compared to planar contacts, cone joints restrict relative part movement for improved structural stability. Cone joints can be realized in the form of curved contacts between associated parts, which have demonstrated good mechanical properties such as reduced stress concentration. To find the best trade-off between assemblability and stability, we propose an optimization approach that first determines the optimal motion cone for each part contact and subsequently derives a geometric realization of each joint to match this motion cone. We demonstrate that our approach can optimize cone joints for assemblies with a variety of geometric forms, and highlight several application examples.

Abstract We study a general form of gears known as non‐circular gears that can transfer periodic motion with variable speed through their irregular shapes and eccentric rotation centers. To design functional non‐circular gears is nontrivial, since the gear pair must have compatible shape to keep in contact during motion, so the driver gear can push the follower to rotate via a bounded torque that the motor can exert. To address the challenge, we model the geometry, kinematics, and dynamics of non‐circular gears, formulate the design problem as a shape optimization, and identify necessary independent variables in the optimization search. Taking a pair of 2D shapes as inputs, our method optimizes them into gears by locating the rotation center on each shape, minimally modifying each shape to form the gear's boundary, and constructing appropriate teeth for gear meshing. Our optimized gears not only resemble the inputs but can also drive the motion with relatively small torque. We demonstrate our method's usability by generating a rich variety of non‐circular gears from various inputs and 3D printing several of them.

Abstract Dissection puzzles require assembling a common set of pieces into multiple distinct forms. Existing works focus on creating 2D dissection puzzles that form primitive or naturalistic shapes. Unlike 2D dissection puzzles that could be supported on a tabletop surface, 3D dissection puzzles are preferable to be steady by themselves for each assembly form. In this work, we aim at computationally designing steady 3D dissection puzzles. We address this challenging problem with three key contributions. First, we take two voxelized shapes as inputs and dissect them into a common set of puzzle pieces, during which we allow slightly modifying the input shapes, preferably on their internal volume, to preserve the external appearance. Second, we formulate a formal model of generalized interlocking for connecting pieces into a steady assembly using both their geometric arrangements and friction. Third, we modify the geometry of each dissected puzzle piece based on the formal model such that each assembly form is steady accordingly. We demonstrate the effectiveness of our approach on a wide variety of shapes, compare it with the state‐of‐the‐art on 2D and 3D examples, and fabricate some of our designed puzzles to validate their steadiness.

We study assemblies of convex rigid blocks regularly arranged to approximate a given freeform surface. Our designs rely solely on the geometric arrangement of blocks to form a stable assembly, neither requiring explicit connectors or complex joints, nor relying on friction between blocks. The convexity of the blocks simplifies fabrication, as they can be easily cut from different materials such as stone, wood, or foam. However, designing stable assemblies is challenging, since adjacent pairs of blocks are restricted in their relative motion only in the direction orthogonal to a single common planar interface surface. We show that despite this weak interaction, structurally stable, and in some cases, globally interlocking assemblies can be found for a variety of freeform designs. Our optimization algorithm is based on a theoretical link between static equilibrium conditions and a geometric, global interlocking property of the assembly---that an assembly is globally interlocking if and only if the equilibrium conditions are satisfied for arbitrary external forces and torques. Inspired by this connection, we define a measure of stability that spans from single-load equilibrium to global interlocking, motivated by tilt analysis experiments used in structural engineering. We use this measure to optimize the geometry of blocks to achieve a static equilibrium for a maximal cone of directions, as opposed to considering only self-load scenarios with a single gravity direction. In the limit, this optimization can achieve globally interlocking structures. We show how different geometric patterns give rise to a variety of design options and validate our results with physical prototypes.

Interlocking assemblies have a long history in the design of puzzles, furniture, architecture, and other complex geometric structures. The key defining property of interlocking assemblies is that all component parts are immobilized by their geometric arrangement, preventing the assembly from falling apart. Computer graphics research has recently contributed design tools that allow creating new interlocking assemblies. However, these tools focus on specific kinds of assemblies and explore only a limited space of interlocking configurations, which restricts their applicability for design. In this paper, we propose a new general framework for designing interlocking assemblies. The core idea is to represent part relationships with a family of base Directional Blocking Graphs and leverage efficient graph analysis tools to compute an interlocking arrangement of parts. This avoids the exponential complexity of brute-force search. Our algorithm iteratively constructs the geometry of assembly components, taking advantage of all existing blocking relations for constructing successive parts. As a result, our approach supports a wider range of assembly forms compared to previous methods and provides significantly more design flexibility. We show that our framework facilitates efficient design of complex interlocking assemblies, including new solutions that cannot be achieved by state of the art approaches.

Reconfigurable assemblies consist of a common set of parts that can be assembled into different forms for use in different situations. Designing these assemblies is a complex problem, since it requires a compatible decomposition of shapes with correspondence across forms, and a planning of well-matched joints to connect parts in each form. This paper presents computational methods as tools to assist the design and construction of reconfigurable assemblies, typically for furniture. There are three key contributions in this work. First, we present the compatible decomposition as a weakly-constrained dissection problem, and derive its solution based on a dynamic bipartite graph to construct parts across multiple forms; particularly, we optimize the parts reuse and preserve the geometric semantics. Second, we develop a joint connection graph to model the solution space of reconfigurable assemblies with part and joint compatibility across different forms. Third, we formulate the backward interlocking and multi-key interlocking models, with which we iteratively plan the joints consistently over multiple forms. We show the applicability of our approach by constructing reconfigurable furniture of various complexities, extend it with recursive connections to generate extensible and hierarchical structures, and fabricate a number of results using 3D printing, 2D laser cutting, and woodworking.

Wind-up toys are mechanical assemblies that perform intriguing motions driven by a simple spring motor. Due to the limited motor force and small body size, wind-up toys often employ higher pair joints of less frictional contacts and connector parts of nontrivial shapes to transfer motions. These unique characteristics make them hard to design and fabricate as compared to other automata. This paper presents a computational system to aid the design of wind-up toys, focusing on constructing a compact internal wind-up mechanism to realize user-requested part motions. Our key contributions include an analytical modeling of a wide variety of elemental mechanisms found in common wind-up toys, including their geometry and kinematics, conceptual design of wind-up mechanisms by computing motion transfer trees to realize the requested part motions, automatic construction of wind-up mechanisms by connecting multiple elemental mechanisms, and an optimization on the part and joint geometry with an objective of compacting the mechanism, reducing its weight, and avoiding collision. We use our system to design wind-up toys of various forms, fabricate a number of them using 3D printing, and show the functionality of various results.

This paper presents CofiFab, a coarse-to-fine 3D fabrication solution, combining 3D printing and 2D laser cutting for cost-effective fabrication of large objects at lower cost and higher speed. Our key approach is to first build coarse internal base structures within the given 3D object using laser cutting, and then attach thin 3D-printed parts, as an external shell, onto the base to recover the fine surface details. CofiFab achieves this with three novel algorithmic components. First, we formulate an optimization model to compute fabricatable polyhedrons of maximized volume, as the geometry of the internal base. Second, we devise a new interlocking scheme to tightly connect the laser-cut parts into a strong internal base, by iteratively building a network of nonorthogonal joints and interlocking parts around polyhedral corners. Lastly, we optimize the partitioning of the external object shell into 3D-printable parts, while saving support material and avoiding overhangs. Besides cost saving, these components also consider aesthetics, stability and balancing. Hence, CofiFab can efficiently produce large objects by assembly. To evaluate CofiFab, we fabricate objects of varying shapes and sizes, and show that CofiFab can significantly outperform previous methods.

Surface registration brings multiple scans into a common coordinate system by aligning their overlapping components. This can be achieved by finding a few pairs of matched points on different scans using local shape descriptors and employing the matches to compute transformations to produce the alignment. By defining a unique local reference frame (LRF) and attaching an LRF to shape descriptors, the transformation can be computed using only one match based on aligning the LRFs. This paper proposes a local voxelizer descriptor, and the key ideas are to define a unique LRF using the support around a basis point, to perform voxelization for the local shape within a cubical volume aligned with the LRF, and to concatenate local features extracted from each voxel to construct the descriptor. An automatic rigid registration approach is given based on the local voxelizer and an expanding strategy that merges descriptor representations of aligned scans. Experiments show that our registration approach allows the acquisition of 3D models of various objects, and that the local voxelizer is robust to mesh noise and varying mesh resolution, in comparison to two state-of-the-art shape descriptors.

Furniture typically consists of assemblies of elongated and planar parts that are connected together by glue, nails, hinges, screws, or other means that do not encourage disassembly and re-assembly. An alternative approach is to use an interlocking mechanism, where the component parts tightly interlock with one another. The challenge in designing such a network of interlocking joints is that local analysis is insufficient to guarantee global interlocking, and there is a huge number of joint combinations that require an enormous exploration effort to ensure global interlocking. In this paper, we present a computational solution to support the design of a network of interlocking joints that form a globally-interlocking furniture assembly. The key idea is to break the furniture complex into an overlapping set of small groups, where the parts in each group are immobilized by a local key, and adjacent groups are further locked with dependencies. The dependency among the groups saves the effort of exploring the immobilization of every subset of parts in the assembly, thus allowing the intensive interlocking computation to be localized within each small group. We demonstrate the effectiveness of our technique on many globally-interlocking furniture assemblies of various shapes and complexity.

A reciprocal frame (RF) is a self-supported three-dimensional structure made up of three or more sloping rods, which form a closed circuit, namely an RF-unit. Large RF-structures built as complex grillages of one or a few similar RF-units have an intrinsic beauty derived from their inherent self-similar and highly symmetric patterns. Designing RF-structures that span over large domains is an intricate and complex task. In this paper, we present an interactive computational tool for designing RF-structures over a 3D guiding surface, focusing on the aesthetic aspect of the design. There are three key contributions in this work. First, we draw an analogy between RF-structures and plane tiling with regular polygons, and develop a computational scheme to generate coherent RF-tessellations from simple grammar rules. Second, we employ a conformal mapping to lift the 2D tessellation over a 3D guiding surface, allowing a real-time preview and efficient exploration of wide ranges of RF design parameters. Third, we devise an optimization method to guarantee the collinearity of contact joints along each rod, while preserving the geometric properties of the RF-structure. Our tool not only supports the design of wide variety of RF pattern classes and their variations, but also allows preview and refinement through interactive controls.

This paper introduces double-sided 2.5D graphics, aiming at enriching the visual appearance when manipulating conventional 2D graphical objects in 2.5D worlds. By attaching a back texture image on a single-sided 2D graphical object, we can enrich the surface and texture detail on 2D graphical objects and improve our visual experience when manipulating and animating them. A family of novel operations on 2.5D graphics, including rolling, twisting, and folding, are proposed in this work, allowing users to efficiently create compelling 2.5D visual effects. Very little effort is needed from the user's side. In our experiment, various creative designs on double-sided graphics were worked out by the recruited participants including a professional artist, which show and demonstrate the feasibility and applicability of our proposed method.

Commercial 3D scene acquisition systems such as the Microsoft Kinect sensor can reduce the cost barrier of realizing mid-air interaction. However, since it can only sense hand position but not hand orientation robustly, current mid-air interaction methods for 3D virtual object manipulation often require contextual and mode switching to perform translation, rotation, and scaling, thus preventing natural continuous gestural interactions. A novel handle bar metaphor is proposed as an effective visual control metaphor between the user's hand gestures and the corresponding virtual object manipulation operations. It mimics a familiar situation of handling objects that are skewered with a bimanual handle bar. The use of relative 3D motion of the two hands to design the mid-air interaction allows us to provide precise controllability despite the Kinect sensor's low image resolution. A comprehensive repertoire of 3D manipulation operations is proposed to manipulate single objects, perform fast constrained rotation, and pack/align multiple objects along a line. Three user studies were devised to demonstrate the efficacy and intuitiveness of the proposed interaction techniques on different virtual manipulation scenarios.

Due to the convenience of taking pictures with various digital cameras and mobile devices, people often end up with multiple shots of the same scene with only slight variations. To enhance photo triaging, which is a very common photowork activity, we propose an effective and easy-to-use brush-and-drag interface that allows the user to interactively explore and compare photos within a broader scene context. First, we brush to mark an area of interest on a photo with our finger(s); our tailored segmentation engine automatically determines corresponding image elements among the photos. Then, we can drag the segmented elements from different photos across the screen to explore them simultaneously, and further perform simple finger gestures to interactively rank photos, select favorites for sharing, or to remove unwanted ones. This novel interaction method was implemented on a consumer-level tablet computer and demonstrated to offer effective interactions in a user study.

Interlocking puzzles are very challenging geometric problems with the fascinating property that once we solve one by putting together the puzzle pieces, the puzzle pieces interlock with one another, preventing the assembly from falling apart. Though interlocking puzzles have been known for hundreds of years, very little is known about the governing mechanics. Thus, designing new interlocking geometries is basically accomplished with extensive manual effort or expensive exhaustive search with computers. In this paper, we revisit the notion of interlocking in greater depth, and devise a formal method of the interlocking mechanics. From this, we can develop a constructive approach for devising new interlocking geometries that directly guarantees the validity of the interlocking instead of exhaustively testing it. In particular, we focus on an interesting subclass of interlocking puzzles that are recursive in the sense that the assembly of puzzle pieces can remain an interlocking puzzle also after sequential removal of pieces; there is only one specific sequence of assembling, or disassembling, such a puzzle. Our proposed method can allow efficient generation of recursive interlocking geometries of various complexities, and by further realizing it with LEGO bricks, we can enable the hand-built creation of custom puzzle games.

While very large collaborative surfaces are already being widely employed to facilitate concurrent interactions with multiple users, they involve no personalization in the touch interactions. Augmenting them to identify the touch interactions with multiple smart-phones can enable interesting co-located communal applications with context-based personalized interactions and information exchange amongst users' portable devices and the shared wall display. This paper proposes a novel matching technique, called tilt correlation, which employs the built-in tilt sensor to identify smart-phones that make concurrent two-point contacts on a common multi-touch wall display. Experimental investigations suggest that the resultant error rate is relatively low; in addition, we also propose a quantitative measure, called the Bourne Identity Index to allow application designers to determine the reliability of each device identification.

Visual exploration of volume data often requires the user to manipulate the orientation and position of a slicing plane in order to observe, annotate or measure its internal structures. Such operations, with its many degrees of freedom in 3D space, map poorly into interaction modalities afforded by mouse-keyboard interfaces or flat multi-touch displays alone. We addressed this problem using a what-you-see-is-what-you-feel (WYSIWYF) approach, which integrates the natural user interface of a multi-touch wall display with the untethered physical dexterity provided by a handheld device with multi-touch and 3D-tilt sensing capabilities. A slicing plane can be directly and intuitively manipulated at any desired position within the displayed volume data using a commonly available mobile device such as the iPod touch. 2D image slices can be transferred wirelessly to this small touch screen device, where a novel fast fat finger annotation technique (F3AT) is proposed to perform accurate and speedy contour drawings. Our user studies support the efficacy of our proposed visual exploration and annotation interaction designs.

This paper presents an algorithm for acquiring high-quality models from multiple calibrated photographs by computing and merging depth maps. The algorithm first computes depth maps from multi-view stereo using a proposed expansion-based approach that returns a 3D point cloud with noisy and redundant information. Then the estimated depth maps are merged into an accurate surface model by a cleaning, downsampling, surface normal estimation and Poisson surface reconstruction process. The proposed approach has been implemented and the experimental results with several real datasets demonstrate that the approach can produce accurate surface models efficiently.