In this paper we introduce a computational framework for computing the maximum build volume for given non-circular extruders and printing machines that have 2, 3 and perhaps higher number of degrees of freedom (DOF). The proposed method also outputs the accessible configuration space of a multi-DOF AM machine that is instrumental in planning the final (temporal) motion of single or multiple print heads. Furthermore, we show that the proposed method allows the ranking of multiple extruders based on their volumetric deviation from nominal geometry. This formulation makes no assumption about the number of machine DOFs, nor about the planarity of the target contour, making it applicable to emerging AM technologies such as 6-axis printing with non-planar layers, and layer-less additive manufacturing.

An important application of haptic technology to digital product development is in virtual prototyping (VP), part of which deals with interactive planning, simulation, and verification of assembly-related activities, collectively called virtual assembly (VA). In spite of numerous research and development efforts over the last two decades, the industrial adoption of haptic-assisted VP/VA has been slower than expected. Putting hardware limitations aside, the main roadblocks faced in software development can be traced to the lack of effective and efficient computational models of haptic feedback. Such models must 1) accommodate the inherent geometric complexities faced when assembling objects of arbitrary shape; and 2) conform to the computation time limitation imposed by the notorious frame rate requirements — namely, 1 kHz for haptic feedback compared to the more manageable 30−60 Hz for graphic rendering. The simultaneous fulfillment of these competing objectives is far from trivial.
This survey presents some of the conceptual and computational challenges and opportunities as well as promising future directions in haptic-assisted VP/VA, with a focus on haptic assembly from a geometric modeling and spatial reasoning perspective. The main focus is on revisiting definitions and classifications of different methods used to handle the constrained multibody simulation in real-time, ranging from physics-based and geometry-based to hybrid and unified approaches using a variety of auxiliary computational devices to specify, impose, and solve assembly constraints. Particular attention is given to the newly developed ‘analytic methods’ inherited from motion planning and protein docking that have shown great promise as an alternative paradigm to the more popular combinatorial methods.
In addition, we provide the most complete bibliography to date of haptic-assisted VP/VA systems complemented by a discussion and comparison of their key features.

Current practice in mechanical product description and computational processing is rooted in the theory of solid modeling whose principles were established almost four decades ago. Despite providing a concrete foundation for computerizing the product development process at the time, the limited capacity of the traditional models to answer the growing design and manufacturing needs is only recently being recognized in the scientific and engineering communities.

I propose an alternative approach that employs spatial functions (i.e., 3D signals) instead of (or in addition to) topological pointsets in the Euclidean 3−space to abstract physical objects and their various geometric, physical, and material properties. The central benefit of this new approach is its great promise and potential extensibility in response to the emerging needs for more meaningful form-function correlations (e.g., for conceptual design) and more powerful tools for modeling new materials (e.g., knitted composites) and processes (e.g., additive manufacturing). This requires a paradigm shift from ‘explicit’ descriptions equipped with ‘combinatorial’ methods—e.g., combinatorial intersection test between objects modeled as r-sets, approximated by sphere trees, and tested using set-theoretic operations that exploit efficient tree traversal—to ‘implicit’ descriptions equipped with ‘analytic’ methods—e.g., analytic intersection test between objects modeled as density functions, approximated by frequency domain samples, and tested using measure-theoretic operations that are streamlined via fast Fourier transforms (FFT).

The results obtained so far suggest that the proposed approach is a powerful unifying alternative to the conventional approaches to geometric computing and overcomes some of the key shortcomings of the traditional models. It opens up new promising theoretical and computational directions for future research in the nascent but emerging field of analytic solid geometry. I hope that the early-stage results in this thesis will inspire other researchers to develop more rigorous formal models and that it will eventually encourage broad industrial adoption of the analytic techniques into future generations of the product life-cycle management (PLM) software.

I propose an alternative approach that employs spatial functions (i.e., 3D signals) instead of (or in addition to) topological pointsets in the Euclidean 3−space to abstract physical objects and their various geometric, physical, and material properties. The central benefit of this new approach is its great promise and potential extensibility in response to the emerging needs for more meaningful form-function correlations (e.g., for conceptual design) and more powerful tools for modeling new materials (e.g., knitted composites) and processes (e.g., additive manufacturing). This requires a paradigm shift from ‘explicit’ descriptions equipped with ‘combinatorial’ methods—e.g., combinatorial intersection test between objects modeled as r-sets, approximated by sphere trees, and tested using set-theoretic operations that exploit efficient tree traversal—to ‘implicit’ descriptions equipped with ‘analytic’ methods—e.g., analytic intersection test between objects modeled as density functions, approximated by frequency domain samples, and tested using measure-theoretic operations that are streamlined via fast Fourier transforms (FFT).

The results obtained so far suggest that the proposed approach is a powerful unifying alternative to the conventional approaches to geometric computing and overcomes some of the key shortcomings of the traditional models. It opens up new promising theoretical and computational directions for future research in the nascent but emerging field of analytic solid geometry. I hope that the early-stage results in this thesis will inspire other researchers to develop more rigorous formal models and that it will eventually encourage broad industrial adoption of the analytic techniques into future generations of the product life-cycle management (PLM) software.

The ability to compare the shapes of objects is crucial to the practice of engineering design. Spectral shape signatures provide a high-quality similarity measure based on diffusion physics by means of the spectrum of an estimate of the Laplace-Beltrami operator for the surface of an object.
However, point cloud and mesh models often have very large intrinsic sizes and subsequently large Laplace-Beltrami estimate matrices. Recommendations from the current spectral shape signature literature are to use only a fixed number of arithmetically greatest eigenvalues and their corresponding eigenvectors in the computation of a spectral shape signature. This recommendation “seems to work well”, but it is not yet understood the degree to which this fixed number of eigenpairs approximates the full spectrum for the purposes of shape similarity measures or even what fixed number to use. Using a fixed number of eigenpairs for all model sizes and samplings also introduces inconsistencies between different samplings of the same shape at different intrinsic sizes and may cost unnecessary computational effort on resource-limited systems (e.g., drones or robots).
In this paper we briefly examine the performance of fixed numbers of eigenpairs on approximating the spectrum of models of different sizes, propose an adaptive cutoff selection method which improves consistency between models for spectral signature use, demonstrate the method on Heat and Wave Kernel signatures (HKS and WKS) for point clouds, and briefly discuss the trade-off between running time and desired error or convergence properties.

Recent hardware advances in the field of 3D imaging are democratizing 3D sensing with tremendous scientific and societal implications. Point cloud processing has traditionally required meshing the point clouds output by 3D cameras followed by surface reconstruction, and geometric feature recognition. However, meshing a point cloud is fundamentally an ill-posed problem, and the definition of a good solution is not general. This, in turn, demands new paradigms for processing point cloud information.
In this paper, we focus on the task of classifying 3D point clouds captured with commercial 3D cameras, and we integrate supervised machine learning algorithms with three different yet underexplored shape descriptors, namely Light-Field Descriptors, Angular Radial Transform (ART), and Zernike Descriptors (ZD). We evaluate the classification performance of different machine learning algorithms combined with these different shape descriptors on point cloud models obtained from the Google 3D Warehouse, and we demonstrate good classification performance for 3D point clouds. Furthermore, we show that Zernike Descriptors are practically insensitive to noise levels typically found in point cloud models captured via 3D sensing.

Haptic-assisted virtual assembly and prototyping has seen significant attention over the past two decades. However, in spite of the appealing prospects, the adoption has been slower than expected. Putting hardware limitations aside, the main roadblocks faced in software development can be traced to the lack of effective and efficient computational models. Such models must 1) accommodate the inherent geometric complexities faced when assembling objects of arbitrary shape; and 2) conform to the computation time limitation imposed by the frame rate requirements---namely, 1 kHz for haptic feedback compared to the more manageable 30-60 Hz for graphic rendering. The fulfillment of these competing objectives is far from trivial.
In this thesis, I propose the concept of a generic `geometric energy' field to obtain the guidance forces and torques that effectively assist the user in the exploration of the virtual environment (VE), from repulsing collisions to attracting proper contact. The energy function is formulated as a cross-correlation of shape descriptors called skeletal density functions (SDF), which applies to arbitrary geometry. I show that this approach unifies the two phases of free motion (based on collision detection) and fine insertion (based on geometric constraints) widely popular in the recent implementations. The formulation can thus be regarded as a generalization of the manually specified `virtual fixtures' or heuristically identified `mating constraints' proposed in the literature. % Although such a generalization comes at the expense of computational intensity in its original form, the computations can be streamlined by leveraging Fourier transforms. % Particularly, the real-time algorithm admits an efficient implementation using fast Fourier transforms (FFT) accelerated via graphics processing units (GPU). I show that the proposed method is effective for assembling objects of arbitrary topological, geometric, and syntactic complexity, providing a meaningful trade-off between the desired fidelity and computational efficiency.
The results suggest that the proposed approach is a powerful unifying alternative to the existing myriad of ad hoc techniques, thus opens up new promising theoretical and computational directions for haptics researchers and developers.

The synthesis of functional molecular linkages is constrained by difficulties in fabricating nano-links of arbitrary shapes and sizes. However, the classical mechanism synthesis methods, which assume the ability to manufacture any designed links, do not provide a systematic synthesis process for molecular linkages.
We propose a new approach to build functional mechanisms * with prescribed mobility*by only using elements from a predefined link soup. First, we enumerate an exhaustive set of topologies, while employing divide-and-conquer algorithms to control the generation and elimination of redundant topologies. Then, we construct the linkage arrangements for each valid topology. Finally, we output a set of feasible geometries through a positional analysis step that minimizes the error associated with closure of the loops in the linkage while avoiding geometric interference. The proposed systematic approach outputs the ATLAS of candidate mechanisms, which can be further processed for downstream applications. The resulting synthesis procedure is the first of its kind that is capable of synthesizing functional linkages with prescribed mobility constructed from a soup of primitive entities.

Haptic-assisted virtual assembly and prototyping has seen significant attention over the past two decades. However, in spite of the appealing prospects, its adoption has been slower than expected. We identify the main roadblocks as the inherent geometric complexities faced when assembling objects of arbitrary shape, and the computation time limitation imposed by the notorious 1 kHz haptic refresh rate. We solved the first problem in a recent work by introducing a generic energy model for geometric guidance and constraints between features of arbitrary shape. In the present work, we address the second challenge by leveraging Fourier transforms to compute the constraint forces and torques. Our new concept of ‘geometric energy’ field is computed automatically from a cross-correlation of ‘skeletal densities’ in the frequency domain, and serves as a generalization of the manually specified virtual fixtures or heuristically identified mating constraints proposed in the literature. The formulation of the energy field as a convolution enables efficient computation using GPU-accelerated Fast Fourier Transforms (FFT). We show that our method is effective for low-clearance assembly of objects of arbitrary geometric and syntactic complexity.

A reliable prediction of 3D protein structures from sequence data remains a big challenge due to both theoretical and computational difficulties. We have previously shown that our kineto-static compliance method (KCM) implemented into the Protofold package can overcome some of the key difficulties faced by other de novo structure prediction methods, such as the very small time steps required by the molecular dynamics (MD) approaches or the very large number of samples needed by the Monte Carlo (MC) sampling techniques. In this article, we improve the free energy formulation used in Protofold by including the typically underrated entropic effects, imparted due to differences in hydrophobicity of the chemical groups, which dominate the folding of most water-soluble proteins. In addition to the model enhancement, we revisit the numerical implementation by redesigning the algorithms and introducing efficient data structures that reduce the expected complexity from quadratic to linear. Moreover, we develop and optimize parallel implementations of the algorithms on both central and graphics processing units (CPU/GPU) achieving speed-ups up to two orders of magnitude on the GPU. Our simulations are consistent with the general behavior observed in the folding process in aqueous solvent, confirming the effectiveness of model improvements. Finally, we present the signifficant enhancements in running times that make the folding simulation tractable for large molecules.

Analytic methods are emerging in solid and configuration modeling, while providing new insights into a variety of shape and motion related problems by exploiting tools from group morphology, convolution algebras, and harmonic analysis. However, most convolution-based methods have used uniform grid-based sampling to take advantage of the Fast Fourier Transform (FFT) algorithm. We propose a new paradigm for more efficient computation of analytic correlations that relies on a grid-free discretization of arbitrary shapes as countable unions of balls, in turn described as sublevel sets of summations of smooth radial kernels at adaptively sampled `knots.' Using a simple geometric lifting trick, we interpret this combination as a convolution of an impulsive skeletal density and primitive kernels with conical support, which faithfully embeds into the convolution formulation of interactions across different objects. Our approach enables fusion of search-efficient combinatorial data structures prevalent in time-critical collision and proximity queries with analytic methods popular in path planning and protein docking, and outperforms uniform-grid based FFT methods by leveraging nonequispaced FFTs. We provide example applications in formulating holonomic collision constraints, shape complementarity metrics, and morphological operations, unified within a single analytic framework.

The development of a generic and effective force model for semi-automatic or manual virtual assembly with haptic support is not a trivial task, especially when the assembly constraints involve complex features of arbitrary shape. The primary challenge lies in a proper formulation of the guidance forces that effectively assist the user in the exploration of the virtual environment, from repulsing collisions to attracting proper contact. The secondary difficulty is that of efficient implementation that maintains the standard 1 kHz haptic refresh rate. We propose a purely geometric model for an artificial energy field that favors spatial relations leading to proper assembly, differentiated to obtain forces and torques in a 6 DOF motion. The energy function is expressed in terms of a convolution of shape-dependent affinity fields, precomputed offline separately for each object. We test the effectiveness of the method using familiar peg-in-hole examples. We show that the proposed technique unifies the two phases of free motion (based on collision detection) and precision assembly (based on geometric constraints) in haptic simulations into a single interaction mode, and provides a generic and automatic constraint model for the so-called virtual fixtures, with no restrictive assumption on the types of the involved assembly features.

We present a new selection technique that facilitates the use of natural hand gestures for virtual object manipulation in 3D. Our method supports the use of 3D imaging techniques for tracking the user’s body and therefore it does not require the use of any hand held devices that would restrict the manipulative capabilities of the user’s hands. The key contribution of our work is the novel use of characteristic behavioral cues, which are representative for general goal directed movement, to infer the object targeted by the user during selection. The resulting technique enables us to select objects whose largest dimension is smaller than the sensing resolution of our system in spite of body tracking uncertainties and hand placement faults. Furthermore, by means of intention inference, our method automatically adapts to the user’s subjective need for variable levels of tolerance to hand placement faults, jitter, or tracking noise.

We present a new 3D user interface (3DUI) that allows its user to employ free natural hand gestures to manipulate virtual objects in a workspace larger than the span of the human arms. The proposed techniques support the use of 3D imaging methods for tracking the user’s body, and therefore, they do not require the use of any hand held devices that would restrict the manipulative capabilities of the user’s hands. The key contribution of our work is the novel use of characteristic behavioral cues from neuropsychology to develop metrics for classifying the observed hand movement into motion primitives that correspond to manipulative gestures in real time. Importantly, we show that our framework is robust against the variability of human gestures, and the proposed manipulation techniques compensate for the tracking instabilities introduced by the imaging methods as well as for the loss in hand positioning precision. Furthermore, by means of intention inference our manipulation methods automatically adapt to the user’s subjective needs for various enhancements such as hand placement fault tolerance, hand positioning precision enhancement or scene view adjustments.

Low-cost 3D imaging hardware (e.g., Microsoft Kinect) generate depth maps of observed scenes and are democratizing 3D sensing. Generally, shape analysis of point cloud models seeks to compute compact descriptors of shapes (e.g., shape signatures), measure shape similarity, and perform comparison and shape segmentation of point cloud models.
In this work we explore the structure of powerful physics-based shape signature methods and develop a framework for shape analysis and segmentation of point cloud models for real objects of engineering interest. First, we develop and show the convergence of a symmetric Laplace-Beltrami operator for point clouds, allowing physics-based shape signatures to be used on point cloud models. Then, we employ topological clustering techniques to segment point cloud models of engineering artifacts into geometric features. The key advantage of this approach is that, by combining our symmetric point cloud Laplace-Beltrami operator with shape signatures and unique clustering techniques derived from topological persistence, we obtain practical shape analysis capabilities that operate directly on point clouds. We show that the proposed techniques are robust against typical noise present in point clouds and segment shapes into semantically meaningful sub-shapes. We additionally demonstrate a method for categorizing these sub-shapes automatically into distinct classes by Vietoris-Rips clustering of the sub-shapes’ maximum signature values. Our methods enable classification of geometric features of point cloud models and differentiation of types of features within those models. The techniques discussed in this paper open the doors to automatic understanding of and reasoning about point clouds that correspond to shapes seen by 3D imaging systems.

In computer graphics and scientific visualization, B-splines are common geometric representations. A typical display method is to render a piecewise linear (PL) approximation that lies within a prescribed tolerance of the curve. In dynamic applications it is necessary to perturb specified points on the displayed curve. The distance between the perturbed PL structure and the perturbed curve it represents can change significantly, possibly changing the underlying topology and introducing unwanted artifacts to the display. We give a strategy to perturb the curve smoothly and keep track of the error introduced by perturbations. This allows us to refine the PL curve when appropriate and avoid spurious topological changes. This work is motivated by applications to visualization of Big Data from simulations on high performance computing architectures.

Knee pain, muscle weakness, and their associated medical conditions cause a significant loss of mobility for a large and growing number of people. Accordingly, the need for effective, simple, and noninvasive solutions is becoming more apparent. To that end, we have designed a quasi-passive knee-orthosis that employs a ”hybrid joint mechanism” as a central component. This joint combines a four-bar linkage with a compliant mechanism to follow natural knee motion. There exists large variability in characteristic knee motion between patients, and the effectiveness of an orthosis can be detrimentally affected by a poorly fitted hinge mechanism that inhibits knee motion. Our design can be optimized to fit a given user, based on both motion capture data and their particular condition, which leads to several potential advantages over standardized hinges. In this paper, we will explore the design and individualization process of the joint mechanism as well as background covering various design decisions.

Loss of personal mobility is a large and growing issue that can be caused by a variety of medical problems. Knee pain, muscle weakness, and their associated conditions are among the most common causes of impaired walking. Currently, conventional solutions include simple braces, canes, and medication. In more extreme cases, surgery is also routine. We propose a design for a novel quasi-passive orthotic knee brace which combines a smart support system employing magnetorheological (MR) fluid with a passive load reduction system. To work in concert with the walking motion of the knee, we have designed a four-bar linkage in conjunction with a compliant mechanism. The resulting orthotic knee brace will alleviate common symptoms related to knee pain and restore lost mobility, most notably in cases of osteoarthritis.

This paper presents an improved computational framework for protein folding software package PROTOFOLD. The energetics now include solvation free energy terms in addition to van der Waals and Columbic interactions. Efficient data structures have been utilized to speed-up the sequential running times from O(n^{2}) to O(n), n being the number of atoms. It turns out, however, that an accurate evaluation of solvation free energy is the computational bottleneck to the entire simulation. Massive computational power offered by Graphics Processing Units (GPUs) can be used to further speed-up the aforementioned step. The algorithm is efficiently parallelized to target the Single-Instruction Multiple-Thread (SIMT) architecture of the GPU. The implementation is optimized to take advantage of device memory hierarchy and to hide memory access latencies. The running times are monitored for different steps of the folding simulation for different molecule sizes. Significant performance improvements are observed, promising for protein design applications where numerous iterative runs are needed.

In this paper a generalized methodology is proposed to address the problem of protein folding. It has been previously demonstrated that the approach called Kineto-static Compliance Method (KCM) can overcome some of the difficulties arising in traditional methods, such as sampling techniques and Molecular Dynamics (MD). In this work, the previous free energy formulation has been extended and improved. The solvation free energy terms, which contribute predominantly to the folding phenomena, have been added to van der Waals and Columbic interactions. In addition, significant speed-ups have been achieved utilizing efficient algorithms and data structures. The computational complexity has been decreased from O(n^{2}) to O(n), n being the number of atoms. A hybrid search method, comprised of Monte Carlo sampling and KCM has been carried out on a protein molecule, in an effort to find the global minimum of folding free energy. Promising results are obtained, showing the general behavior prevalent in conformational changes of protein biomolecules in biological environments.

The study of geometry in motion can be traced back to the scientists of the ancient world. Since then, kinematics developed into a mature and sophisticated set of tools that can be used to describe and analyze the motion of geometry. Since folding of proteins is fundamentally nothing but coordinated movement of geometry (atoms) under the influence of internal constraints and external stimuli, kinematics can naturally play a key role in the understanding of how proteins fold, which, in itself, is one of the crucial problems in science today. In this chapter we review some of the central kinematic elements used to model proteins and study their folding and flexibility.

The function of a protein macromolecule often requires conformational transitions between two native configurations. Understanding these transitions is essential to the understanding of how proteins function, as well as to the ability to design and manipulate protein-based nano-mechanical systems. It is widely accepted that the pathway connecting two native protein conformations in nature should satisfy a minimum energy criterion. The premise of this paper is that such a pathway can be found by using dihedral angle combinations that have been shown to have a high probability of occurrence in naturally observed proteins. In order to quantify this probability, we are proposing statistical propensity torque maps for tuples of dihedral angles. These maps are constructed in the angle space, similar to the Ramachandran Charts, but are based on data obtained from more than 38,600 proteins from Protein Data Bank (PDB) so that each map contains the experimentally observed pairs of dihedral angles (φ_{i},ψ_{i}), (φ_{i},ψ_{i+1}), (φ_{i}, φ_{i+1}) and (ψ_{i},ψ_{i+1}).

Interaction with 3D information is one of the fundamental and most familiar tasks in virtually all areas of engineering and science. Several recent technological advances pave the way for developing hand gesture recognition capabilities available to all, which will lead to more intuitive and efficient 3D user interfaces (3DUI). These developments can unlock new levels of expression and productivity in all activities concerned with the creation and manipulation of virtual 3D shapes and, specifically, in engineering design.

Building fully automated systems for tracking and interpreting hand gestures requires robust and efficient 3D imaging techniques as well as potent shape classifiers. We survey and explore current and emerging 3D imaging technologies, and focus, in particular, on those that can be used to build interfaces between the users’ hands and the machine. The purpose of this paper is to categorize and highlight the relevant differences between these existing 3D imaging approaches in terms of the nature of the information provided, output data format, as well as the specific conditions under which these approaches yield reliable data. We also explore the impact of each of these approaches on the computational cost and reliability of the required image processing algorithms. We highlight the main challenges and opportunities in developing natural user interfaces based on hand gestures, and conclude with some promising directions for future research.

Building fully automated systems for tracking and interpreting hand gestures requires robust and efficient 3D imaging techniques as well as potent shape classifiers. We survey and explore current and emerging 3D imaging technologies, and focus, in particular, on those that can be used to build interfaces between the users’ hands and the machine. The purpose of this paper is to categorize and highlight the relevant differences between these existing 3D imaging approaches in terms of the nature of the information provided, output data format, as well as the specific conditions under which these approaches yield reliable data. We also explore the impact of each of these approaches on the computational cost and reliability of the required image processing algorithms. We highlight the main challenges and opportunities in developing natural user interfaces based on hand gestures, and conclude with some promising directions for future research.

We describe a cost-effective device that uses an off-the-shelf force transducer to measure patient bite force as a diagnostic aid in determining dental implant size, number of implants, and prosthetic design for restoring partial edentulism. The main advantages of the device are its accuracy, simplicity, modularity, ease of manufacturing, and low cost.

The popularity of medial axis in shape modeling and analysis comes from several of its well known fundamental properties. For example, medial axis captures the connectivity of the domain, has a lower dimension than the space itself, and is closely related to the distance function constructed over the same domain.

We propose the new concept of a medial zone of an n-dimensional semi-analytic domain Ω that subsumes the medial axis MA(Ω) of the same domain as a special case, and can be thought of as a ‘thick’ skeleton having the same dimension as that of Ω. We show that by transforming the exact, non-differentiable, distance function of domain Ω into approximate but differentiable distance functions, and by controlling the geodesic distance to the crests of the approximate distance functions of domain Ω, one obtains families of medial zones of Ω that are homeomorphic to the domain and are supersets of MA(Ω). We present a set of natural properties for the medial zones MZ(Ω) of Ω and discuss practical approaches to compute both medial axes and medial zones for 3-dimensional semi-analytic sets with rigid or evolving boundaries. Due to the fact that the medial zones fuse some of the critical geometric and topological properties of both the domain itself and of its medial axis, re-formulating problems in terms of medial zones affords the ‘best of both worlds’ in applications such as geometric reasoning, robotic and autonomous navigation, and design automation.

We propose the new concept of a medial zone of an n-dimensional semi-analytic domain Ω that subsumes the medial axis MA(Ω) of the same domain as a special case, and can be thought of as a ‘thick’ skeleton having the same dimension as that of Ω. We show that by transforming the exact, non-differentiable, distance function of domain Ω into approximate but differentiable distance functions, and by controlling the geodesic distance to the crests of the approximate distance functions of domain Ω, one obtains families of medial zones of Ω that are homeomorphic to the domain and are supersets of MA(Ω). We present a set of natural properties for the medial zones MZ(Ω) of Ω and discuss practical approaches to compute both medial axes and medial zones for 3-dimensional semi-analytic sets with rigid or evolving boundaries. Due to the fact that the medial zones fuse some of the critical geometric and topological properties of both the domain itself and of its medial axis, re-formulating problems in terms of medial zones affords the ‘best of both worlds’ in applications such as geometric reasoning, robotic and autonomous navigation, and design automation.

Shape optimization (with topological changes) has become a de facto standard approach for synthesizing new designs. Current approaches heavily rely on voxelized modifications of the initial domain, followed by heuristic reconstruction procedures that result in a detailed shape design. The initial domain is almost always conservatively estimated so that the design space spans a sufficiently large set of possible solutions.

We propose a novel approach to shape optimization that exploits the geometric and topologic properties of medial zones and a new shape modification paradigm to synthesize shapes with topological guarantees. The medial zone is a ‘thick skeleton’ of the domain induced by prescribed boundary conditions, and represents an initial solution that is topologically valid. We modify such an initial solution by adding or subtracting ‘bubbles’ of material defined via prescribed shape functions. The proposed approach has many advantages in terms of topological guarantees, shape control, and computational cost, supports parametric optimization of free-form geometry, and can be implemented in any geometric representation that supports distance computations.

We propose a novel approach to shape optimization that exploits the geometric and topologic properties of medial zones and a new shape modification paradigm to synthesize shapes with topological guarantees. The medial zone is a ‘thick skeleton’ of the domain induced by prescribed boundary conditions, and represents an initial solution that is topologically valid. We modify such an initial solution by adding or subtracting ‘bubbles’ of material defined via prescribed shape functions. The proposed approach has many advantages in terms of topological guarantees, shape control, and computational cost, supports parametric optimization of free-form geometry, and can be implemented in any geometric representation that supports distance computations.

The function of protein molecules is defined by their 3-D geometry, as well as their internal mobility, which is heavily influenced by the internal hydrogen bonds. The correct identification of these hydrogen bonds and the prediction of their effect on the mobility of protein molecules can provide an invaluable mechanism to understand protein behavior. Applications of this study ranges from nano-engineering to new drug design.

We are extending our recent approach from identifying main-chain main-chain hydrogen bonds to all types of hydrogen bonds that occur in protein structures, such as α-helices and β-sheets. We use the Gru ̈bler-Kutzbach kinematic mobility criterion to determine the degrees of freedom of all closed loops (rigid loops as well as closed loops of one or more degrees of freedom) formed by Hydrogen bonds. Furthermore, we systematically develop constraint equations for non-rigid closed loops. Several examples of protein molecules from PDB are used to show that these additions both improve the accuracy of mobility analysis and enable us to study a broader range of the motion of protein molecules. This approach offers theoretical insight as well as extensive numerical efficiencies in protein simulations.

We are extending our recent approach from identifying main-chain main-chain hydrogen bonds to all types of hydrogen bonds that occur in protein structures, such as α-helices and β-sheets. We use the Gru ̈bler-Kutzbach kinematic mobility criterion to determine the degrees of freedom of all closed loops (rigid loops as well as closed loops of one or more degrees of freedom) formed by Hydrogen bonds. Furthermore, we systematically develop constraint equations for non-rigid closed loops. Several examples of protein molecules from PDB are used to show that these additions both improve the accuracy of mobility analysis and enable us to study a broader range of the motion of protein molecules. This approach offers theoretical insight as well as extensive numerical efficiencies in protein simulations.

Parametric modeling changed the way we design and reason about mechanical artifacts due to the ability to handle (mainly 2-dimensional) constraints imposed on geometric entities. However, the inherent history dependence of parametric models limits the changes that can be achieved with a given parametrization.

We propose a new history-independent approach to edit geometric models via a geometric deformation procedure that relies on motion interpolation to define and control local geometric modifications. Our approach generates useful geometric deformations such as stretching, bending, and twisting of existing point sets without relying on pre-existing parametrizations or on specific representations of the geometry. The proposed approach provides a small set of parameters that allow direct control and editing of the geometric modifications, and can preserve important geometric invariants such as constant cross-sectional properties of the deformed models. Furthermore, our shape deformation paradigm complements emerging direct boundary manipulation capabilities, and maintains the ability to perform parametric optimization of the associated models.

We propose a new history-independent approach to edit geometric models via a geometric deformation procedure that relies on motion interpolation to define and control local geometric modifications. Our approach generates useful geometric deformations such as stretching, bending, and twisting of existing point sets without relying on pre-existing parametrizations or on specific representations of the geometry. The proposed approach provides a small set of parameters that allow direct control and editing of the geometric modifications, and can preserve important geometric invariants such as constant cross-sectional properties of the deformed models. Furthermore, our shape deformation paradigm complements emerging direct boundary manipulation capabilities, and maintains the ability to perform parametric optimization of the associated models.

Prevalent discretization methods based on Delaunay triangulations and advancing fronts, which sample and mesh simultaneously, can guarantee well shaped triangles but at a fairly high computational cost. In this paper we present a novel and flexible two-part sampling and meshing algorithm, which produces topologically correct meshes on arbitrary boundary representations whose faces are represented parametrically, without requiring an initial coarse mesh. Our method is based on a hybrid spatial partitioning scheme driven by user-designed subdivision rules that combines the power of quadtree decomposition with the flexibility of the binary decompositions to produce meshes that favor prescribed geometric properties. Importantly, the algorithm offers a performance increase of approximately two orders of magnitude over Delaunay based methods and at least one order of magnitude over advancing front methods. At the same time, our algorithm is practically as fast as the computationally optimal algorithm based on a pure quadtree decomposition, but with a markedly better distribution in the regions with parametric distortion. The hierarchical nature of our surface decomposition is well suited to interactive applications and multithreaded implementation.

The task of planning a path between two spatial configurations of an artifact moving among obstacles is an important problem in practically all geometrically-intensive applications. Despite the ubiquity of the problem, the existing approaches make specific limiting assumptions about the geometry and mobility of the obstacles, or those of the environment in which the motion of the artifact takes place.

We present a strategy to construct a family of paths, or roadmaps, for two- and three-dimensional solids moving in an evolving environment that can undergo drastic topological changes. Our approach is based on a potent paradigm for constructing geometric skeletons that relies on constructive representations of shapes with R-functions that operate on real-valued half-spaces as logic operations. We describe a family of skeletons that have the same homotopy as that of the environment and contains the medial axis as a special case. Importantly, our skeletons can be designed so that they are “attracted to” or ”repulsed by” prescribed spatial sites of the environment. Moreover, the R-function formulation suggests the new concept of a medial zone, which can be thought of as a ‘thick’ skeleton with significant applications for motion planning and other geometric reasoning applications. Our approach can handle problems in which the environment is not fully known a priori, and intrinsically supports local and parallel skeleton computations for domains with rigid or evolving boundaries. Furthermore, our path planning algorithm can be implemented in any commercial geometric kernel, and has attractive

We present a strategy to construct a family of paths, or roadmaps, for two- and three-dimensional solids moving in an evolving environment that can undergo drastic topological changes. Our approach is based on a potent paradigm for constructing geometric skeletons that relies on constructive representations of shapes with R-functions that operate on real-valued half-spaces as logic operations. We describe a family of skeletons that have the same homotopy as that of the environment and contains the medial axis as a special case. Importantly, our skeletons can be designed so that they are “attracted to” or ”repulsed by” prescribed spatial sites of the environment. Moreover, the R-function formulation suggests the new concept of a medial zone, which can be thought of as a ‘thick’ skeleton with significant applications for motion planning and other geometric reasoning applications. Our approach can handle problems in which the environment is not fully known a priori, and intrinsically supports local and parallel skeleton computations for domains with rigid or evolving boundaries. Furthermore, our path planning algorithm can be implemented in any commercial geometric kernel, and has attractive

The integration of traditional mechanism theory with biology and medicine at the molecular level enables the use of polypeptide chains to design, manipulate and fabricate biomimetic artificial nano-machines. In this paper we establish a procedure to analyze the mobility of protein molecules based on predicting the formation of hydrogen bonds, which, in turn, is the primary cause for mobility reduction in proteins. We improved our graph-based approach by including side chain and mixed chain hydrogen bond prediction capabilities as well as an energy analysis of these interactions. This method has been emploied to evaluate the internal mobility and identify the rigid and flexible segments of the protein molecules. This computational procedure has been used to assess the stability and mobility of three specific candidate proteins to build a nanobiodevice. Our simulations show that only one of these structures is capable of producing a stable nanoparticle, which is in agreement with the experimental results.

Curve skeletons are 1D entities that capture the essential topology and geometry of a shape in a simple and very compact form, and have found a multitude of applications in engineering and science. The concept itself is ill-defined, which is why the many existing definitions are ad-hoc and employ heuristic algorithms revolving around the (unique) medial axis. We propose a framework for computing curve skeletons for arbitrary planar domains that relies on a modified medial axis, and is based on R-functions that can be thought of as continuous forms of the Boolean logic functions. Furthermore, we propose one particular definition of such a curve skeleton that preserves the homotopy of the domain, is stable in the presence of noise and is well-suited to downstream applications. The framework can be implemented in any commercial geometric kernel for planar domains, and has attractive computational properties. Furthermore, the mathematical concepts are extendable to medial surfaces and curve skeletons in 3D domains.

Sweeping moving objects has become one of the basic geometric operations used in engineering design, analysis and physical simulation. Despite its relevance, computing the boundary of the set swept by a non-polyhedral moving object is largely an open problem due to well-known theoretical and computational difficulties of the envelopes. We have recently introduced a generic point membership classification (PMC) test for general solid sweeping. Importantly, this PMC test provides complete geometric information about the set swept by the moving object, including the ability to compute the self-intersections of the sweep itself. In this paper, we compare two recursive strategies for sampling points of the space in which the object moves, and show that the sampling based on a fast marching cubes algorithm possesses the best combination of features in terms of performance and accuracy for the boundary evaluation of general sweeps. Furthermore, we show that the PMC test can be used as the foundation of a generic sweep boundary evaluator in conjunction with efficient space sampling strategies for solids of arbitrary complexity undergoing affine motions.

Modeling protein molecules as kinematic chains provides the foundation for developing powerful approaches to the design, manipulation, and fabrication of peptide based molecules and devices. Nevertheless, these models possess a high number of degrees of freedom (DOFs) with considerable computational implications. On the other hand, real protein molecules appear to exhibit a much lower mobility during the folding process than what is suggested by existing kinematic models. The key contributor to the lower mobility of real proteins is the formation of hydrogen bonds during the folding process. In this paper, we explore the pivotal role of hydrogen bonds in determining the structure and function of the proteins from the point of view of mechanical mobility. The existing geometric criteria on the formation of hydrogen bonds are reviewed and a new set of geometric criteria is proposed. We show that the new criteria better correlate the number of predicted hydrogen bonds with those established by biological principles than other existing criteria. Furthermore, we employ established tools in kinematics mobility analysis to evaluate the internal mobility of protein molecules and to identify the rigid and flexible segments of the proteins. Our results show that the developed procedure significantly reduces the DOF of the protein models, with an average reduction of 94%. Such a dramatic reduction in the number of DOF can have enormous computational implications in protein folding simulations.

The task of planning a path between two spatial configurations of an artifact moving among obstacles is an important problem in many geometrically-intensive applications. Despite the ubiquity of the problem, the existing approaches make specific limiting assumptions about the geometry and mobility of the obstacles, or those of the environment in which the motion of the artifact takes place. In this paper we propose a powerful approach for 2D path planning in a dynamic environment that can undergo drastic topological changes. Our algorithm is based on a potent paradigm for medial axis computation that relies on constructive representations of shapes with R-functions that operate on real-valued half-spaces as logic operations. Our approach can handle problems in which the environment is not fully known a priori, intrinsically supports local and parallel skeleton computations for domains with rigid or evolving boundaries, and appears to extend naturally to 3D domains. Furthermore, our path planning algorithm can be implemented in any commercial geometric kernel, and has attractive computational properties. The capability of the proposed technique are explored through several examples designed to resemble highly dynamic environments.

Dental implants have enabled a dramatic increase in the quality of life for many partially edentulous and edentulous patents. Immediate loading of newly placed dental implants is a recent advancement that attempts to meet patient demand. However, immediate loading of a just placed implant may induce implant failure to osseointegrate. Some patients can generate a biting force that can reach approximately 1300 Newtons (N) in the posterior jaws. The magnitude of bite force that would cause failure of osseointegration of newly placed implants is currently unknown. It has been proposed that osseointegration would fail if an implant is luxated in bone more than 50 to 150 microns. Fibrous tissue, not bone, would form. This study investigated the quantity of various off-axial forces required to move a nonosseointegrated 4.3 x 13 mm implant 50 microns. The previously published pilot study for this study found that the amount of horizontal force required to displace an implant 50 microns was approximately 150 N. This study found that the force needed to move the implants 100 microns at a horizontal approach, 0 degrees, averaged 50 N, with a range of 23-79 N; at 22 degrees, averaged 52 N, with a range of 27-70 N; and at 60 degrees averaged 87 N, with a range of 33-105 N.

Modeling protein molecules as kinematic chains provides the foundation for developing powerful approaches to the design, manipulation and fabrication of peptide based molecules and devices, while circumventing the current bottlenecks facing conventional protein simulation approaches. Nevertheless, these models possess a high number of degrees of freedom (DOF) with considerable computational implications. On the other hand, real protein molecules appear to exhibits a much lower mobility during the folding process than what is suggested by existing kinematic models. The key contributor to the lower mobility of real proteins is the formation of Hydrogen bonds (H-bonds) during the folding process. In this paper we explore the pivotal role of Hydrogen bonds in determining the structure and function of the proteins from the point of view of mechanical mobility. The existing geometric criteria on the formation of Hydrogen bonds are reviewed and a new set of geometric criteria are proposed. We show that the new criteria better correlate the number of predicted Hydrogen bonds with biological principles than the other existing criteria. Furthermore, we employ established tools in kinematics mobility analysis to evaluate the internal mobility of the protein molecules, and to identify the rigid and flexible segments of the proteins. Our results show that the developed procedure significantly reduces the DOF of the protein models, with an average reduction of 94%. Such a dramatic reduction in the number of DOF can have has enormous computational implications in protein folding simulations.

Shape skeletons are fundamental concepts for describing the shape of geometric objects, and have found a variety of applications in a number of areas where geometry plays an important role. Two types of skeletons commonly used in geometric computations are the straight skeleton of a (linear) polygon, and the medial axis of a bounded set of points in the k-dimensional Euclidean space. However, exact computation of these skeletons of even fairly simple planar shapes remains an open problem. In this paper we propose a novel approach to construct exact or approximate (continuous) distance functions and the associated skeletal representations (a skeleton and the corresponding radius function) for solid 2-dimensional semi-analytic sets that can be either rigid or undergoing topological deformations. Our approach relies on computing constructive representations of shapes with R-functions that operate on real-valued half-spaces as logic operations. We use our approximate distance functions to define a new type of skeleton, i.e, the C-skeleton, which is piecewise linear for polygonal domains, generalizes naturally to planar and spatial domains with curved boundaries, and has attractive properties. We also show that the exact distance functions allow us to compute the medial axis of any closed, bounded and regular planar domain. Importantly, our approach can generate the medial axis, the straight skeleton, and the C-skeleton of possibly deformable shapes within the same formulation, extends naturally to 3D, and can be used in a variety of applications such as skeleton-based shape editing and adaptive motion planning.

This paper describes a new approach to perform continuous collision and interference detection between a pair of arbitrarily complex objects moving according to general 3-dimensional affine motions. Our approach, which does not require any envelope computations, recasts the problem of detecting collisions and computing the interfering subsets in terms of inherently parallel set membership classification tests of specific curves against the original (static) geometric representations. We show that our approach can compute the subsets of the moving objects that collide and interfere, as well as the times of collision, which has important applications in mechanical design and manufacturing.

Our approach can be implemented for any geometric representation that supports curve-solid intersections, such as implicit and parametric representations. We describe an implementation of the proposed technique for solids given as a boundary representation (B-rep), and illustrate its effectiveness for several rigid and deformable moving objects bounded by tesselated and freeform surfaces of various complexities. Furthermore, we show that our approach can be extended to also identify the local and global self-intersections of the envelopes of the moving objects without requiring to compute these envelopes explicitly. The paper concludes by summarizing the proposed approach as well as reviewing relevant computational improvements that can decrease the computational cost of the prototype implementation by orders of magnitude.

Our approach can be implemented for any geometric representation that supports curve-solid intersections, such as implicit and parametric representations. We describe an implementation of the proposed technique for solids given as a boundary representation (B-rep), and illustrate its effectiveness for several rigid and deformable moving objects bounded by tesselated and freeform surfaces of various complexities. Furthermore, we show that our approach can be extended to also identify the local and global self-intersections of the envelopes of the moving objects without requiring to compute these envelopes explicitly. The paper concludes by summarizing the proposed approach as well as reviewing relevant computational improvements that can decrease the computational cost of the prototype implementation by orders of magnitude.

The function of a protein macromolecule often requires conformational transitions between two native conformations. Understanding these transitions is essential to the understanding of how proteins function, as well as to the ability to design and manipulate protein-based nano-mechanical systems. In this paper we propose a set of 3D Cartesian workspace maps for exploring protein pathways. These 3D maps are constructed in the Euclidean space for triads of chain segments of protein molecules that have been shown to have a high probability of occurrence in naturally observed proteins based on data obtained from more than 38,600 proteins from Protein Data Bank (PDB). We show that the proposed 3-dimensional propensity maps are more effective navigation tools than the propensity maps constructed in the angle space. We argue that the main reason for this improved efficiency is the fact that, although there is a one-to-one mapping between the 2D dihedral angle maps and the 3D Cartesian maps, the propensity distributions are significantly different in the two spaces. Hence, the 3D maps allow the pathway planning to be performed directly in the 3D Euclidean space based on propensities computed in the same space, which is where protein molecules change their conformations.

Coming Soon...

Many diverse engineering problems can be modeled with solid sweeping in a conceptually simple and intuitive way, and sweeps are considered to be one of the basic representation schemes in solid modeling. However, many properties of sweeps as well as their “informational completeness” are not well understood, which is the primary reason why computational support for solid sweeping remains scarce.

We propose a generic point membership classification (PMC) for sweeping solids of arbitrary complexity moving according to one parameter affine motions. The only restrictive assumption that we make in this paper is that the initial and final configurations of the moving object do not intersect during the sweep. Our PMC test is defined in terms of inverted trajectory tests against the original geometric representation of the generator object, which implies that this test can be implemented in any geometric representation that supports curve-solid intersections. Importantly, this PMC test provides complete geometric information about the set swept by 3-dimensional objects in general motions. At the same time, it establishes the foundations for developing a new generation of computational tools for sweep boundary evaluation and trimming, as well as a number of practical applications such as shape synthesis, contact analysis and path planning.

We propose a generic point membership classification (PMC) for sweeping solids of arbitrary complexity moving according to one parameter affine motions. The only restrictive assumption that we make in this paper is that the initial and final configurations of the moving object do not intersect during the sweep. Our PMC test is defined in terms of inverted trajectory tests against the original geometric representation of the generator object, which implies that this test can be implemented in any geometric representation that supports curve-solid intersections. Importantly, this PMC test provides complete geometric information about the set swept by 3-dimensional objects in general motions. At the same time, it establishes the foundations for developing a new generation of computational tools for sweep boundary evaluation and trimming, as well as a number of practical applications such as shape synthesis, contact analysis and path planning.

The modeling of many practical problems in design and manufacturing involving moving objects relies on sweeps and their boundaries, which are mathematically described by the envelopes to the family of shapes generated by the moving object. In many problems, such as the design and analysis of higher pairs or tool path planning, contact changes between the moving object and the boundary of its swept volume become critical because they often translate into functional changes of the system under consideration. However, the difficulty of this task quickly escalates beyond the reach of existing approaches as the complexity of the shape and motion increases.

We recently proposed a sweep boundary evaluator for general sweeps in conjunction with efficient point sampling and surface reconstruction algorithms that relies on our novel point membership classification (PMC) test for general solid sweeps. In this paper we describe a new approach that automates the prediction of changes in the state of contact between a shape of arbitrary complexity moving according to an affine motion, and the boundary of its swept set. We show that we can predict when and where such contact changes occur with only minimal additional computational cost by exploiting the data output by our sweep boundary evaluator. We discuss the problem and the associated computational issues in a 2D framework, and we conclude by discussing the extension of our approach to 3D moving objects.

We recently proposed a sweep boundary evaluator for general sweeps in conjunction with efficient point sampling and surface reconstruction algorithms that relies on our novel point membership classification (PMC) test for general solid sweeps. In this paper we describe a new approach that automates the prediction of changes in the state of contact between a shape of arbitrary complexity moving according to an affine motion, and the boundary of its swept set. We show that we can predict when and where such contact changes occur with only minimal additional computational cost by exploiting the data output by our sweep boundary evaluator. We discuss the problem and the associated computational issues in a 2D framework, and we conclude by discussing the extension of our approach to 3D moving objects.

Dental implants are used to retain and support fixed and removable dental prostheses. In many clinical situations, local bone morphology requires dental implants that have a diameter that is significantly smaller than the typical implant diameters. In these cases, the fatigue life of the smaller diameter implants becomes a critical therapeutic parameter. However, this fatigue life depends on the implant itself, on the physical properties of the bone, as well as on other morphological characteristics that are patient dependent. In other words, this fatigue life varies greatly with each newly placed implant, but the capability to predict the fatigue life of dental implants does not exist today. In this paper, we present the first steps towards establishing such a methodology. We develop a finite element based fatigue model for rigidly mounted dental implants, and correlate its results with both analytical predictions as well as physical measurements. This implies that such a model can be used as a valid predictor of fatigue life of dental implants themselves, and can be used as a valuable implant design tool. Furthermore, we present the design of a cost effective device to measure the fatigue life of dental implants that can be either rigidly or bone mounted (in vitro). This device was used to measure the fatigue life of an initial sample of nine dental implants, and we show that the results predicted by the finite element model correlated well with our initial experimental results.

Loading of dental implants immediately after placement is an important attribute for the patients receiving the implants, but may induce a failure in the osseointegration of the implant. Even though the loading required to induce such failures is currently unknown, it is estimated that the osseointegration may fail if an implant is luxated in bone by more than 50μm. Therefore, the ability to measure this loading can provide the practicing dentist with critical information in estimating the functional life of a newly placed implant. This paper discusses the design and fabrication of a cost-effective test setup for measuring the amount of horizontal force required to displace a nonosseointegrated implant, and presents the results of our pilot in vitro load measurements for dental implants mounted in a bovine mandible. Although the sample size of our measurements is not statistically significant, the initial data show that the amount of horizontal force required to displace a 4.3×13mm implant by 50μm is in the order of 150N, and therefore the implant may fail to osseointegrate for biting forces that are as low as 440N, which is about half of the typical biting force of an adult in the molar area. One implication of our study is that implants having smaller diameters may move and fail to osseointegrate for even lower biting forces. Furthermore, our work represents the first steps in developing appropriate metrics to correlate the measured biting force generated by a patient with his or her candidacy for immediate functional implant loading.

The fatigue life of mini or small-diameter dental implants is of particular interest because these implants are used to retain and support fixed and removable dental prostheses. The fatigue life of an implant depends on both the implant itself as well as on the physical properties of the bone. However, the capability to predict the fatigue life of a newly placed implant is currently inexistent. This pilot study represents the first step in developing such a methodology and focuses on the design of a cost-effective device to measure the fatigue life of a dental implant. In our measurements, the implant has been mounted in an essentially rigid support, but test specimens can also be bone mounted in vitro. Furthermore, we developed a finite element-based computer model capable of predicting the corresponding fatigue life. The finite element analysis was performed in ABAQUS, and the results predicted by the model correlated fairly well with our initial experimental results. Most of the 2-mm diameter implants fractured after more than a million cycles.

Sweeping moving objects has become one of the basic geometric operations in engineering design, analysis and physical simulation. Despite their relevance, computing the boundary of the set swept by a non-polyhedral moving object is largely an open problem due to well known theoretical and computational difficulties of the envelopes.

We have recently introduced a generic point membership classification (PMC) test that classifies a given point as an interior, a boundary or an exterior point to the set swept by an arbitrarily complex moving object. Importantly, this PMC test provides complete geometric information about the set swept by the moving object. In this paper we explore the use of this test as the core of a sweep boundary evaluator for general sweeps in conjunction with efficient point sampling and surface reconstruction algorithms. Clearly, a large part of the computational cost of such a boundary evaluation approach comes from the point sampling strategy. We discuss an implementation using an octree (cellular) decomposition of space, and investigate other possible approaches to sample the space in which the motion takes place.

We have recently introduced a generic point membership classification (PMC) test that classifies a given point as an interior, a boundary or an exterior point to the set swept by an arbitrarily complex moving object. Importantly, this PMC test provides complete geometric information about the set swept by the moving object. In this paper we explore the use of this test as the core of a sweep boundary evaluator for general sweeps in conjunction with efficient point sampling and surface reconstruction algorithms. Clearly, a large part of the computational cost of such a boundary evaluation approach comes from the point sampling strategy. We discuss an implementation using an octree (cellular) decomposition of space, and investigate other possible approaches to sample the space in which the motion takes place.

Sweeps are considered to be one of the basic representation schemes in solid modeling, and have numerous applications in very diverse fields ranging from engineering design and manufacturing to computer graphics. Despite their prevalence, many properties of the general sweeps are not well understood. Furthermore, boundary evaluation algorithms for 3-dimensional solid objects currently exist only for reasonably simple objects and motions. One of the main reasons for this state of affairs is the lack of a generic point membership test for sweeps. In this paper we describe a point membership classification (PMC) for sweeping solids of arbitrary complexity moving according to one parameter affine motions such that the initial and final configurations of the moving object do not intersect. Our PMC test is defined in terms of inverted trajectory tests against the original geometric representation of the generator object. This PMC test provides complete geometric information about the set swept by the 3-dimensional moving object, and can play a fundamental role in sweep boundary evaluation and trimming algorithms, as well in a number of practical applications such as contact analysis of higher pairs in design and manufacturing. Since our PMC is formulated in terms of intersections between inverted trajectories and the generator, it can be implemented for any geometric representation that supports curve-solid intersections.

Mechanical designs undergo numerous geometric changes throughout the design process. Performing these changes relies, whenever possible, on the parametric models used to create the initial geometry. However, a number of open issues prevent the current parametric modeling systems to support many practical design situations, which, in turn, forces the geometry to evolve independently of the original parametric model. The fact that every parametric update can be expressed in terms of a sequence of shape deformations implies that the same geometric updates could be obtained, at least in principle, via shape deformation procedures that parameterize the deformation itself. In this paper we propose a new approach to create and edit solid models by introducing a geometric deformation procedure that relies on motion interpolation. We show that the proposed approach induces a parametrization of the deformation that allows direct control and editing of the deformation, is capable of preserving important geometric invariants such as constant cross-sectional properties of the deformed models, and maintains the ability to perform parametric optimization of the associated solid models. We conclude by discussing advantages and limitations of this approach as well as a number of important research directions that we will pursue in the near future.

The mathematical envelopes of families of both rigid and non-rigid moving shapes play a fundamental role in a variety of problems from very diverse application domains, from engineering design and manufacturing to computer graphics and computer assisted surgery. Geometric singularities in these envelopes are known to induce malfunctions or unintended system behavior, and the corresponding theoretical and computational difficulties induced by these singularities are not only massive, but also well documented. We describe a new approach to detect and quantify the envelope singularities induced by 2-dimensional shapes of arbitrary complexity moving according to general non-periodic and non-singular planar affine motions. Our approach, which does not require any envelope computations, is reframing the problem in terms of “fold points” and “fold regions” in the neighborhood of geometric singularities, and we show that the existence of these fold points is a necessary condition for the existence of singularities. We establish a mathematically well defined duality between the 2-dimensional Euclidean space in which the motion takes place and a 2+1 spacetime domain. Based on this duality, we recast the problem of detecting and quantifying geometric singularities into inherently parallel tests against the original geometric representation in the 2-dimensional Euclidean space. We conclude by discussing the significance of our results, and the extension of our approach to 3-dimensional moving shapes.

Immediate loading of newly placed dental implants is a consideration when attempting to meet patients' demands. However, immediate loading may induce implant failure to osseointegrate, particularly in the case of a patient who can generate a biting force that can reach approximately 1300 Newtons (N) in the posterior jaws. The range of biting forces that prevent osseointegration of newly placed implants is currently unknown. However, it is suspected that osseointegration may fail if an implant is luxated in bone more than 50 μm, in which case fibrous tissue will be formed instead of bone. This pilot study was focused on finding the amount of horizontal off-axial force required to move a nonosseointegrated 4.3 × 13–mm implant 50 μm. The initial data show that the amount of horizontal force required to displace such an implant by 50 μm was on the order of 150 N. Assuming that the angle between the direction of the biting force and the vertical lies between 0° and 20°, our data show that a 4.3 × 13–mm implant may fail to osseointegrate for biting forces that are as low as 440 N. One implication of our study is that implants having smaller diameters may move and fail to osseointegrate for even lower biting forces.

Protein molecules are the nano machines of the biological world and one of the most suitable mechanisms to manipulate matter at nano level. Predicting the final configuration of the folded protein remains one of the most important open problems in science. The ab initio approaches to protein folding seek to develop a framework, based on first physical principles, for predicting the final protein configuration by minimizing the total potential energy of the protein. However, navigating the utterly complex energy landscape of a protein remains one of the main bottlenecks in protein folding today due to the large number of local energy minima that effectively act as energy traps for any and all simulation algorithms.

This paper proposes two generic strategies for locally modifying the energy landscape aimed at avoiding these energy traps, namely, segmental manipulation and progressive side chain scaling. These strategies are implemented in ProtoFold, our comprehensive approach to protein folding based on kineto-static compliance of the protein chain. We show that these strategies effectively extricate the protein molecule from the trapped configurations, and allow the numerical simulation to proceed.

This paper proposes two generic strategies for locally modifying the energy landscape aimed at avoiding these energy traps, namely, segmental manipulation and progressive side chain scaling. These strategies are implemented in ProtoFold, our comprehensive approach to protein folding based on kineto-static compliance of the protein chain. We show that these strategies effectively extricate the protein molecule from the trapped configurations, and allow the numerical simulation to proceed.

Parametric modeling systems are fundamentally changing the design process practiced in the industry today. Practically all commercial CAD systems combine established solid modeling techniques with constraint solving and heuristic algorithms to create, edit and manipulate solid models, while enforcing the requirement that every such solid model must maintain the validity of the prescribed geometric constraints. However, a number of fundamental (open) problems limit the functionality and performance of these parametric modeling systems. For example, the allowable parametric changes are history dependent; the number of parameters describing even relatively simple parts can quickly become prohibitively large, and commercial constraint solvers are limited today to 2-dimensional geometric constraints. Consequently, current parametric modeling systems do not support many practical design situations due to the associated theoretical and computational difficulties, as well as to the considerable organizational obstacles generated by the need to handle large parametric models. This paper investigates the current practices and limitations of parametric solid modeling systems, and explores some alternative approaches that could complement the identified limitations.

Moving parts in contact have been traditionally synthesized through specialized techniques that focus on completely specified nominal shapes. Given that the functionality does not completely constrain the geometry of any given part, the design process leads to arbitrarily specified portions of geometry, without providing support for systematic generation of alternative shapes satisfying identical or altered functionalities. Hence the design cycle of a product is forced to go into numerous and often redundant iterative stages that directly impact its effectiveness. We argue that the shape synthesis of mechanical parts is more efficient and less error prone if it is based on techniques that identify the functional surfaces of the part without imposing arbitrary restrictions on its geometry. We demonstrate that such techniques can be formally defined for parts moving in contact through equivalence classes of mechanical parts that satisfy a given functionality. We show here that by replacing the completely specified geometry of the traditional approaches with partial geometry and functional specification, we can formally define classes of mechanical parts that are equivalent, in the sense that all members of the class satisfy the same functional specifications. Moreover, these classes of functionally equivalent parts are computable, may be represented unambiguously by maximal elements in each class, and contain all other functional designs that perform the same function.

Conventional mechanical design focuses on a single completely specified nominal shape that is later toleranced to allow for variations in form. The corresponding design processes usually involve arbitrary decisions affecting the geometry and do not support systematic generation of alternative shapes satisfying identical or altered functionalities. This places a serious handicap on the design cycle of a product, since most new designs are obtained by modifying existing products to comply with new functional specifications. Since the functionality of a part does not usually define all of its geometry, a more coherent approach would be to design classes of equivalent mechanical parts that satisfy a given functionality. We show here that, by replacing the completely specified geometry of the traditional approaches with partial geometry and functional specification, we can generate classes of mechanical parts that are equivalent, in the sense that all members of the class satisfy the same functional specifications. Ability to define, compute, and represent classes of functionally equivalent parts will allow one to generate, compare and modify functionally equivalent designs, perhaps having dissimilar geometries. We identify three such equivalence classes for artifacts with parts moving in contact, which presume, at the very least, contact between parts, spatial containment during their relative motion, and external loads applied on the moving parts. We show that these classes of functionally equivalent parts are computable and may be represented unambiguously by maximal elements of each class.

We consider the general problem of designing mechanical parts moving in contact under the influence of externally applied loads. Geometrically, the problem may be characterized in terms of a conjugate triplet, which is formed by the two shapes moving in contact and their relative motion. We show that every such triplet belongs to one or more classes of functionally equivalent designs that may be represented uniquely by maximal triplets, corresponding respectively to the two largest contact shapes that are guaranteed to contain all other possible solutions to the contact design problem. In practical terms, the proposed characterization of the contact problem enables the systematic exploration of the design space using fully defined representatives of the functionally equivalent class of parts. Furthermore, such exploration may be performed using standard tools from geometric modeling, and without assuming any particular parameterization that necessarily restrict both the design space and possible computational techniques for exploring feasible designs. Because the proposed approach supports the generation of an essentially unlimited space of design solutions for a given contact problem, it is particularly effective at the conceptual design stage.

This is an early version of the journal paper that appeared in Research in Engineering Design, no 13, pp 157-166, 2002.

Mechanical parts are modeled as (predominantly rigid) solid shapes that may move in space in order to function, be manufactured (for example, machine or be machined), and be assembled or disassembled. While it is clear that such mechanical shapes are greatly influenced by collision, interference, containment, and contact constraints through prescribed motions, the motion itself is usually not part of these shape models. This in turn leads to proliferation of computational methods for modeling and analysis of various motion-related constraints. We show that all motion-related constraints can be formulated and applied within the same computational framework that treats motion as an integral part of the model. Our approach relies on two computational utilities. The first one is the unsweep operation which, given an arbitrary n-dimensional subset of Euclidean space E and a general motion M, returns the largest subset of E that remains inside E under M. The second modeling utility is a disjoint decomposition of space induced by the operations of unsweep and the standard set operations. The proposed approach subsumes and unifies the traditional sweep-based modeling of moving parts, and provides improved computational support for mechanical shape design.

As an infinite union operation, sweep of a moving object through space is a powerful and natural addition to the Boolean set operations that incorporates motion-related information for the purposes of shaping, collision detection, and simulation of moving objects. Use of sweep has been hindered by limited computational support and by the fact that it is a ‘material growing’ operation, whereas many applications, such as interference elimination and mechanism design, appear to be better modeled by a ‘material removal’ operation. This article formally defines a new geometric modeling operation of unsweep. Given an arbitrary subset E of Euclidean space and a general motion M, unsweep(E,M) returns the largest subset of E that remains inside the original E under M. When M is a translation, unsweep (E,M) naturally reduces to the standard Minkowski difference of E and the trajectory generated by the inverted motion M. In this sense, the operation of unsweep is a generalization of Minkowski difference that corresponds to a ‘material removal’ operation, it can be also defined as an infinite intersection operation, and is the dual of sweep in a precise set-theoretic sense. We show that unsweep has attractive theoretical and computational properties, including a practical point membership test for arbitrary general motions. Using duality, the established properties of unsweep is extended to the general sweep operation, and can be used to improve the computational support for general sweeps.

This is an early version of the journal paper that appeared in ASME Transactions Journal of Mechanical Design, Vol 122, no 4, Dec. 2000, pp 567-574.

We introduce and formally define a new geometric modeling operation unsweep(E, M) which, given an arbitrary n-dimensional subset of Euclidean space E and a general motion M, returns the subset of E that remains inside E under M. This new operation is dual to the usual sweeping operation and has important applications in mechanical design. When M is a translation, unsweep(E, M) naturally reduces to the usual Minkowski difference of E and the trajectory generated by the inverted motion k. We show that unsweep has attractive computational properties and give a practical point membership test for arbitrary general motions. By duality, the established properties of unsweep can be used to develop a practical point membership test for general sweeps.

The rise of solid modeling as a principal medium for mechanical product description can be traced to the requirement of “informational completeness” of geometric representations. Unfortunately, traditional geometry-based systems do not contain important information needed for many engineering activities and tend to force costly iterations in a product development cycle. We seek to understand and to establish spatial properties of mechanical parts in terms of simple interacting constructs related to part functionality and manufacturing processes. Existence of such a structure is illustrated for a simple part that is characterized in terms of its kinematics, strength, spatial containment, and manufacturing characteristics. The resulting explicit representation of correspondence between mechanical characteristics and spatial elements allows systematic product development, efficient modification procedures, and rational tolerancing approaches – eliminating many costly errors and iterations in a product development cycle. The study also highlights the lack of and the need for formal models supporting systematic design process.

Effects of spatial random fluctuations in the yield condition of rigid-perfectly plastic continuous media are analysed in cases of Cauchy and characteristic boundary value problems. A weakly random plastic microstructure is modeled, on a continuum mesoscale, by an isotropic yield condition with the yield limit taken as a locally averaged random field. The solution method is based on a stochastic generalization of the method of sliplines, whose significant feature is that the deterministic characteristics are replaced by the forward evolution cones containing random characteristics. Comparisons of response of this random medium and of a deterministic homogeneous medium, with a plastic limit equal to the average of the random one, are carried out numerically in several specific examples of the two boundary value problems under study. An application of the method is given to the limit analysis of a cylindrical tube under internal traction. The major conclusion is that weak material randomness always leads to a relatively stronger scatter in the position and field variables, as well as to a larger size of the domain of dependence—effects which are amplified by both presence of shear traction and inhomogeneity in the boundary data. Additionally, it is found that there is hardly any difference between stochastic slipline fields due to either Gaussian or uniform noise in the plastic limit.

Broadly, mechanical design is the transformation, or mapping, from a functional description of a device to a form, or structural description. In general there are many shapes satisfying the same functional description, which implies that any systematic approach to mechanical design would require the construction and exploration of the space of design solutions corresponding to a given functional description. Thus, both generating and searching this space for solutions to a given problem must rely on an appropriate characterization of the design space.

In this work we propose a characterization of the design space of solutions for the class of problems of moving parts subjected to spatial containment and contact constraints. Cams, latches, and other mechanisms involving higher kinematic pairs are examples of parts whose shapes are subjected to such spatial constraints. Our design space characterization relies on the concept of the largest part satisfying given spatial constraints, and is used as a basis for the formulation of a new set-theoretic approach to designing moving parts based on a `material shrinking' paradigm. Within this formulation, the design proceeds by eliminating only the material whose presence would violate given spatial constraints, and results in the largest part satisfying containment and contact constraints. To determine and reason about the shape of this largest part, we have developed a set of specific tools that are aimed at constructing and exploring the space of design solutions for the class of problems of interest.

The approach proposed in this thesis results in a family of parts satisfying the same spatial constraints. The presented approach does not impose arbitrary restrictions on the geometry of the shape, but it identifies the largest shape satisfying the specified constraints. Consequently, any other shape satisfying the same constraints must be a subset of this largest shape. We illustrate the viability of our approach by applying our experimental implementation of the concepts and tools developed in this thesis to the shape design of parts belonging to four different application domains.

In this work we propose a characterization of the design space of solutions for the class of problems of moving parts subjected to spatial containment and contact constraints. Cams, latches, and other mechanisms involving higher kinematic pairs are examples of parts whose shapes are subjected to such spatial constraints. Our design space characterization relies on the concept of the largest part satisfying given spatial constraints, and is used as a basis for the formulation of a new set-theoretic approach to designing moving parts based on a `material shrinking' paradigm. Within this formulation, the design proceeds by eliminating only the material whose presence would violate given spatial constraints, and results in the largest part satisfying containment and contact constraints. To determine and reason about the shape of this largest part, we have developed a set of specific tools that are aimed at constructing and exploring the space of design solutions for the class of problems of interest.

The approach proposed in this thesis results in a family of parts satisfying the same spatial constraints. The presented approach does not impose arbitrary restrictions on the geometry of the shape, but it identifies the largest shape satisfying the specified constraints. Consequently, any other shape satisfying the same constraints must be a subset of this largest shape. We illustrate the viability of our approach by applying our experimental implementation of the concepts and tools developed in this thesis to the shape design of parts belonging to four different application domains.

The University of Connecticut

191 Auditorium Avenue

Storrs, CT 06269

email: ilies at engr.uconn.edu