Abstract We present a system for creating a hair model that matches a user's hairstyle from images. The model consists of guide hair strands and can be used in a real‐time hair simulator. Our goal differs from most previous works that aim to create realistic high‐resolution hair for off‐line applications or create a mesh of the exterior of the hair volume for image manipulation. Our primary aim is for a user to be able to put his/her hairstyle into game or other real‐time applications. By taking photos in eight views of the user's head using a smartphone camera and segmenting the images with some easy‐to‐use tools, the player will obtain his/her own hair model in NVIDIA's HairWorks, which is a hair simulator used in many games. We show a number of results demonstrating the capabilities of our system in this paper.

We present a system for creating hair model that matches a user's hairstyle. The model consists of guide hair strands and is ready to be used in a real-time hair simulator. Our goal differs from most previous work which aims to create realistic high resolution hair for off-line applications or create mesh of exterior of hair volume for image manipulation. Our primary aim is for user to be able to put his/her hairstyle into game or other real-time applications. By taking photos in 8 views of the user's head using a smart phone camera and segmenting images with some easy to use tools, the player will obtain his/her own hair model in NVIDIA's HairWorks, which is a hair simulator used in many games. We show a number of results demonstrating the capabilities of our system in this paper.

An object is caged by a formation of fingers when it is blocked by the fingers from moving arbitrarily far away. Although some objects such as those with opposing concave sections can be caged by only two fingers, many other objects require at least three. Rectangles and 3-D convex objects without a supporting plane, for example, require at least four. This paper focuses on multifinger squeezing caging in which the positions of fingers obey dispersion constraints. In particular, we present an algorithm for computing all initial finger placements at which the object can be caged in an aforementioned manner. An implementation of the proposed algorithm is described along with implementation results both in 2-D and 3-D.

We propose a novel method to calculate scalar version of the grasp quality measure proposed, which is the magnitude of minimal disturbance force applied to the object that breaks the grasp. This measurement is adopted in several works but all of them are essentially calculated by enumerating over discretized directions of forces. Our proposed method does not need to discretize the direction, rendering the method more complete. The key idea of our method is that the measure is formulated as a function which depends on object vertices, disturbance force direction and hyperplanes of Unit grasp wrench space(UGWS). We proved that the reciprocal of this function is indeed concave over disturbance force direction, for a fixed object and fixed hyperplane of UGWS. Hence, we can derive analytical solution that find the global minimum of this function. A numerical example was carried out and the result shows that our proposed method can outperform the original computation in term of accuracy and efficiency.

This paper presents a general grasp synthesis algorithm. The algorithm follows a stochastic approach that calculate a large number of grasps with good quality in short amount of time. It takes as an input a 3D point cloud that represents the contact points of the object and heuristically selects concurrent points which are covered by contact points and identifies concurrent grasps from such contact points. Empirical examples are performed to show that the proposed algorithm can generate a large number of good quality grasps comparing to other methods.

When an object is caged by a set of fingers, it cannot move arbitrarily far from the caging fingers regardless of what possible rigid motion it takes. Although this condition makes caging an attractive choice for nonprehensile manipulation, directly computing caging configurations is still a complex process. More importantly, using a cage could be too restrictive than necessary in many real cases. This is because some object motions rarely occur in reality. Therefore, some non-caging formations of fingers that only allow these rare escape motions can still effectively be deployed in many caging tasks. This paper introduces a concept of partial cage quality which determine an ability to cage an object of a non-caging formation of fingers, partial cage. We believe that the quality is closely related to possibility of an object escaping from a partial cage. A measurement framework based on motion planning is presented together with experimental results to illustrate and justify the proposed concept.

In general, any object can be restricted or caged within a bounded region if we evenly place a sufficient number of fingers around the object. This naive approach often leads to inefficient utilization of fingers because only two fingers are sufficient to cage most nonconvex objects. In this paper, we propose an algorithm that identifies all the caging sets, i.e., set of two-finger placements that cage a given polytope representing the object. Whether a finger placement could cage the object can be queried efficiently from a structure generated by the algorithm. We implemented and tested the algorithm in the case of 2-D and 3-D objects.

We present new strategy for finding kinematically-feasible precision grasps for particular robot hand. By collecting samples of hand posture and classifying them into multi level-of-detail of posture information for each hand configuration, we can efficiently search for valid hand postures given a set of contact points within reasonable processing time. The approach for creating hand posture database can be also applied to any kind of robot hands as long as the kinematic specification of those hands are provided.

This paper addresses the problem of regrasp planning for a polygon with a large number of edges. We propose an approach for computing sequences of finger repositioning that allow the hand to switch from one grasping configuration to another while maintaining force-closure during the entire process. The proposed approach is based on exploring a structure called switching graph. Complete sets of two-fingered force-closure grasps are computed in grasp space. Adjacent sets of force-closure grasps are merged into a connected set which allows finger repositioning by continuous movements of fingers on adjacent polygonal edges. We present an output sensitive algorithm to construct a switching graph from the obtained connected sets. A method for finding the optimal solution of a finger switching is also presented. The proposed approach has been implemented and some preliminary results are presented.

One of the ultimate challenges in robotics is to manipulate an arbitrary object without knowing its exact shape beforehand. The shape is rather acquired on the spot via using a laser range scanner, structure from multiple views; therefore, maybe only partially observed and corrupted by a certain degree of noise. We propose an algorithm to identify available failsafe strategies capable of preventing an object from escaping from the fingers, i.e. caging, even if its shape is partially and/or inaccurately observed. This algorithm extends the previously proposed one that characterizes all caging sets via a maximal dispersion control but, instead of taking a single polytope P exactly representing the object as input, it takes two polytopes: P+and P-containing P and contained in P, respectively. The algorithm characterizes all possible formations of fingers that guarantee to cage any polytope P such that P-⊆ P ⊆ P+as long as the dispersion (i.e. looseness) of the fingers' formation is kept under a critical value called the maximal dispersion. This allows us to gracefully handle uncertainty of acquired shapes and quickly identify robust solutions in case of simplified shapes.

We consider the task of grasping novel objects and cleaning fairly cluttered tables with many novel objects. Recent successful approaches employ machine learning algorithms to identify points on the scene that the robot should grasp. In this paper, we show that the task can be significantly simplified by using segmentation, especially with depth information. A supervised localization method is employed to select graspable segments. We also propose a shape completion and grasp planner method which takes partial 3D information and plans the most stable grasping strategy. Extensive experiments on our robot demonstrate the effectiveness of our approach.

This work proposes a necessary condition for n-finger force closure grasp which considers true quadratic force cone without linearization. The condition finds its use as a heuristic for multiple queries force closure test. The heuristic works as a filtering criteria which improves the overall running time of the entire set of queries. An empirical example shows that our approach could speed up the force closure test be the factor of four. This work improves our earlier works to cover the case of n-finger grasp.

We propose a heuristic approach for a regrasp planning problem. The input with a large number of discrete contact points is considered. In this setting, traditional methods of complete solution is not available. Based on wrench space information of the input, our proposed algorithm clusters the input into groups and chooses a representative contact point from each group. A global graph structure for regrasp planning is then constructed using all force closure grasps that can be formed only by representative contact points. Also described are approaches for finding a regrasping sequence from an arbitrary grasp to a grasp in the global structure. Once such regrasping sequences are found for linking the input initial and target grasps to the global graph structure, the regrasp planning problem can be solved as a graph search. The results from preliminary experiments indicate that our method can solve many problem instances efficiently.

This paper addresses the problem of optimizing the maximal independent contact region for two-fingered force- closure grasp of a rigid object in 2D. Existing methods for optimizing this criterion considered only independent graspable regions on a given pair of edges. We propose an algorithm that takes nearby edges into consideration so that larger independent contact regions can be obtained. Our method takes the input polygons, computes graspable regions for each pair of edges, merge all adjacent regions together, and then find the best independent contact region inscribed in those regions. Two different criteria to define the best independent contact region are studied. The first criterion maximizes area of the axis-parallel rectangle in the configuration space, while the other criterion maximizes the smaller side's length of the rectangle. For a given object with n vertices, the first criterion can be optimized using the algorithm from Karen Daniels et al. in O(n2log2n) time, while the other criterion can be optimized using the algorithm from Evanthia Papadopoulou and D. T. Lee in O(n2log n) time.

The object caging problem focuses on designing a formation of fingers that keeps an object within a bounded space without immobilizing it. This paper addresses the problem of designing such formation for object represented by a polytope in any finite dimensional workspace and for any specified number of pointed finger. Our goal is to characterize all the caging sets, each of which corresponds to a largest connected set of initial formations of fingers guaranteed to cage the object, up to maintaining a certain class of real-valued measurement induced by the whole fingers' formation below a critical value. In our previous works, such measurement is simply the distance between two fingers (the formation). We found that it is possible to apply the framework based on graph search from the previous works to broader classes of measurements. In this paper, we introduce two of measurements, called dispersion and concentration and propose a generalized approach to query and to report all caging sets with respect to a given dispersion or concentration.

We consider a 3D grasping problem. We propose a test of Ropf3-positive span of force cones and a test of Ropf3-positive span of their torque set. Our methods consider directly the quadratic force cone without pyramidal linearization of a cone. The conditions can be computed in a constant time and they are used as a heuristic for 3D force closure test. We also show that our proposed heuristic greatly improve the performance of existing grasp testing algorithms.

The problem of object caging is defined as a problem of designing a formation of fingers to restrict an object within a bounded space. Assuming two pointed fingers and a rigid polygonal or polyhedral object, this paper addresses the problem of two-finger squeezing caging, i.e., to characterize all possible formations of the fingers that are capable of caging the object via limiting their separation distance. Our study is done entirely in the object's frame allowing the object to be considered as a static obstacle so that the analysis can be performed in terms of the finger motion. Our solution is based on partitioning the configuration space of the problem into finite subsets called nodes. A graph of these nodes can then be constructed to represent all possible finger motion where a search based method can be applied to solve the caging problem. The partitioning of the configuration is based on convex decomposition of the free space. Let m be the number of convex subsets from the decomposition, our proposed algorithm reports all squeezing cage sets in O(n2+ nm + m2log m) for a polygonal input with n vertices and O(nN3+ n2+ nm + m2log m) for a polyhedron with n vertices and having TV edges exhibiting a reflex angle. After reporting all squeezing cages, the proposed algorithm can answer whether a given finger placement can cage the object within a logarithmic time.

An object is captured by a set of fingers when there exists no trajectory to bring the object arbitrarily far from the fingers. Object concavity is a special geometric property that allows objects to be captured with only few fingers. In particular, certain concave objects may be captured by appropriately placing two fingers close to some pair of opposite concave sections. This paper addresses the problem of computing all configurations of the fingers that are farthest away from each other while still capable of capturing the object. We propose an O(n2lg n) algorithm for this task and present preliminary results showing efficiency of the algorithm

Given a set of n contact points on the boundary of a 2D object together with their contact normals and frictional coefficient, we present an output sensitive algorithm for computing all combinations of three points from this set that achieve force-closure under the frictional contact assumption. The proposed algorithm runs in O(n2lg2n + K) where K is the number of different solutions. Preliminary implementation is described along with experimental results showing efficiency of the algorithm

This paper formalizes and proposes an algorithm to compute coverage diameters of polygons in 2D. Roughly speaking, the coverage diameter of a polygon is the longest possible distance between two points through which the polygon cannot pass in between. The primary use of coverage diameter is to form a cage for transporting an object, not necessarily convex, with multiple disc-shaped robots. The main idea of the computation of coverage diameter is to convert the problem into a graph structure, then perform the search for a solution path in that graph. The proposed algorithm runs in O(n2log n) time for the input polygon with n vertices

This paper proposes a necessary and sufficient condition for parallel grasps. We extend the use of this condition to the task of regrasp planning. In particular, we propose a graph structure called a switching graph which contains information about primitive grasping operations such as finger switching and finger sliding. The problem of regrasp planning is transformed to a graph search problem. Mainly, this work concentrates on a parallel grasp with force closure. Assuming frictional point contacts, the proposed method has been implemented and some preliminary results are presented.

This paper addresses the problem of testing whether three contact points form a 3-fingered force-closure grasp in two dimensions. In particular, assuming frictional point contacts, we present a new necessary and sufficient condition for three fingers to form a force-closure grasp. The proposed condition is based on a technique for representing a friction cone as a line segment in a dual plane. This representation allows force-closure test to be formulated as the problem of intersection detection between a line segment and a convex polygon. The resulting geometric condition is presented along with an efficient algorithm for using the condition in force-closure test.

This paper addresses the problem of computing frictional 4-fingered force-closure grasps of three-dimensional objects. The proposed approach searches for force-closure grasps from a collection of sampled points on the object's surface. Unlike most other works, the approach is not limited to the objects with a certain class of shapes. It can be applied to an object in any shape since only the object's surface points and corresponding surface normal at the points are needed. The efficiency of the approach arises from a heuristic for search space pruning which is based on ability to efficiently locate regions in three dimensional space where friction cones intersect and a randomized test for checking force-closure condition. The proposed approach is implemented and preliminary results are presented.

A successful grasp of an object can be guaranteed when the object can never escape from the surrounding fingers during the entire grasping execution. Ability to capture an object clearly contributes to the robustness and success of grasping tasks. Object concavity is a useful geometric property allowing objects to be captured with only few fingers. In particular, certain concave objects may be captured using two fingers by appropriately placing the fingers close to some pair of opposite concave sections. Based on this intuitive idea, we address the problem of capturing concave polygonal objects with two disc-shaped distance such that the two fingers can move away from a given immobilizing grasp but still prevent the object from escaping; when within this computed range, it is guaranteed under the frictionless contact assumption that the fingers can move toward each other to bring the object to the given immobilizing grasp. the proposed approach is implemented and the preliminary result is presented.

This paper proposes an approach for computing a sequence of finger repositioning that allows a 4-fingered hand to switch from one grasping configuration to another while maintaining a force-closure grasp of a polygon during the entire process. Assuming frictional point contacts, the proposed approach is based on exploring a structure called switching graph. The connectivity of this structure captures ability to switch from one grasp to another and allows regrasp planning to be formulated as a graph search. The proposed approach has been implemented and some preliminary results are presented.

This paper addresses the problem of a 5-fingered hand manipulating a polyhedron. In particular, assuming frictional point contacts, we present an approach for computing a sequence of finger repositioning that allows the hand to switch from one grasping configuration to another while maintaining a force-closure grasp of the polyhedron during the entire process. The proposed approach captures ability to switch from one grasp to another in a graph structure, allowing regrasp planning to be reduced to a graph search problem. The proposed approach is implemented and preliminary results are presented.

An object is captured when it is restricted to stay within a bounded region of the workspace. In this paper, we present a sufficient condition for a team of disc-shaped robots to capture a two dimensional rigid object in the plane by enclosing it in a capturing formation. This condition is defined in terms of the robots' positions and a certain geometric property of the object. We do not assume any particular geometry, therefore the condition immediately holds for all object shapes. We also sketch an application of the capturing formation to the problem of object manipulation.

A part that is placed on a massively parallel actuator array can be manipulated by the force generated by a large number of supporting actuators. At a high level of abstraction, this form of nonprehensible distributed manipulation can be modeled using programmable force fields. This paper addresses the problem of manipulating multiple parts using programmable force fields. In particular, given two convex parts in different shapes which are in unknown configurations, we introduce a sequence of force fields that isolates, recognizes, and brings each part to its target configuration without using a sensor. The novelty of the proposed approach lies in the part isolation stage. Our technique uses part interaction under a radial force field as a condition ensuring that both parts will be separated from each other and moved into opposite halves of the plane. Once separated, each part can be processed independently and simultaneously using techniques for handling a single part.

This paper addresses the problem of transporting multiple objects in the plane with a team of disc-shaped robots. Using geometric properties of the objects, we present a method for computing positions of the robots that can kinematically constrain the objects to lie in a subset of the workspace. This computation is then used for deriving a motion plan of the robots for simultaneously pushing the objects to a given region. The approach is demonstrated in a simulation where a team of robots cooperatively sweep multiple objects that are scattered in a room to one of its sides.

This paper addresses the problem of using three disc-shaped robots to manipulate a polygonal object in the plane in the presence of obstacles. The proposed approach is based on the computation of maximal discs (dubbed maximum independent capture discs, or MICaDs) where the robots can move independently while preventing the object from escaping their grasp. It is shown that, in the absence of obstacles, it is always possible to bring a polygonal object from any configuration to any other one with robot motions constrained to lie in a set of overlapping MICaDs. This approach is generalized to the case where obstacles are present by decomposing the corresponding motion planning task into the construction of a collision-free path for a modified form of the object, and the execution of this path by a sequence of simultaneous and independent robot motions within overlapping MICaDs. The proposed algorithm is guaranteed to generate a valid plan, provided a collision-free path exists for the modified form of the object. It has been implemented and experiments with Nomadic Scout mobile robots are presented.

In automated assembly, before parts can be put together, they often have to be appropriately oriented and positioned. The device performing this task is generally referred to as a part feeder. A new class of devices for non-prehensile distributed manipulation, such as MEMS actuator arrays, vibrating plates, etc., provide an alternative to traditional mechanical platforms for part feeding. These devices can be abstracted as programmable vector fields. Manipulation plans for these devices can therefore be considered as strategies for applying a sequence of fields to bring parts to some desired configurations. Typically, to uniquely orient and position a part, several fields have to be sequentially employed. Previously, it has been proven that there exists a combination of the unit radial field and a constant field that induces a unique stable equilibrium for almost any part. However, that work focuses mainly on an existential proof and fails to address how to compute the field for a given part. We propose a radically different field with a proof confirming that the field induces a unique stable equilibrium for almost any part. This proof leads us to a method for computing a single field for orienting a given part, together with the corresponding stable equilibrium configuration of the part.

In automated assembly, before parts can be put together, they often have to be appropriately oriented and positioned. The device performing this task is generally referred to as a part feeder. A new class of devices for non-prehensible distributed manipulation, such as MEMS actuator arrays, vibrating plates, etc., provides an alternative to traditional mechanical platforms for part feeding. These devices can be abstracted as programmable vector fields. Manipulation plans for these devices can therefore be considered as strategies for applying a sequence of fields to bring parts to some desired configurations. Typically, to uniquely orient and position a part, several fields have to be sequentially employed. In previous work (2001), we have shown that this objective can be accomplished using a single field. The work characterizes such a field for a given part. In this paper, we discover another interesting property of the field. In particular, we show that for a finite set of parts (with different shapes), we can specify a single field that can uniquely orient and position every part in the set. A force field device implementing this field therefore may be used as a part feeder for every part in the set without any reconfiguration.

Presents an implementation of a planner that uses three disc-shaped robots to manipulate a polygonal object in the plane in the presence of obstacles. The approach is based on the computation of the maximal discs (maximal independent capture discs or MICaDs) where the robots can move independently while preventing the object from escaping their grasp. It has been shown that, in the absence of obstacles, it is always possible to bring a polygonal object from any configuration to any other one with robot motions constrained to lie in a set of overlapping MICaDs. This approach is generalized to the case where obstacles are present by decomposing the motion planning task into (1) the construction of a collision-free path for a modified form of the object, and (2) the execution of this path by a sequence of simultaneous and independent robot motions within overlapping MICaDs. The approach is guaranteed to work provided a collision free path exists for the modified form of the object. Experiments with Nomadic Scouts and a visual localization system are presented.

This paper addresses the problem of using three disc-shaped robots to manipulate a polygonal object in the plane in the presence of obstacles. The proposed approach is based on the characterization of the maximal discs (maximum independent capture discs, or MICaDS) where the robots can move independently while preventing the object from escaping their grasp. It is shown that, in the absence of obstacles, it is always possible to bring a polygonal object from any configuration to any other one with robot motions constrained to lie in a set of overlapping MICaDS. A strategy for computing these motions is used in conjunction with an exact motion planner to devise an algorithm guaranteed to find a motion plan avoiding collisions with obstacles as long as a collision-free path exists for the object grown by the diameter of the robots plus some arbitrary positive number /spl epsiv/.

Addresses the problem of grasping and manipulating a polygonal object with three disc-shaped robots in the plane. These robots may be the fingertips of a gripper or mobile platforms. The proposed approach is based on the characterization of the range of possible object motions when two of the effectors are fixed and the third one is allowed to move in the plane with two degrees of freedom. This technique does not assume that contact is maintained during the execution of the grasping/manipulation task, nor does it rely on detailed (and a priori unverifiable) models of friction or contact dynamics, but it allows the construction of manipulation plans guaranteed to succeed under the weaker assumption that jamming does not occur during the task execution. The proposed approach is validated by simulation examples and preliminary experiments with Nomadic Scout robots.

This paper addresses the problem of grasping and manipulating a polygonal object with three disc-shaped robots capable of translating in arbitrary directions in the plane. The main novelty of the proposed approach is that it does not assume that contact is maintained during the execution of the grasping/manipulation task, nor does it rely on detailed (and a priori unverifiable) models of friction or contact dynamics. Instead, the range of possible object motions for a given position of the robots is characterized in configuration space. This allows the construction of manipulation plans guaranteed to succeed under the weaker assumption that jamming does not occur during the task execution.

Addresses the problem of manipulating three-dimensional objects with a reconfigurable gripper. A detailed analysis of the problem geometry in configuration space is used to devise a simple and efficient algorithm for manipulation planning. The proposed approach has been implemented and preliminary simulation experiments are discussed.

We propose a reconfigurable gripper that consists of two parallel plates whose distance can be adjusted by a computer-controlled actuator. The bottom plate is a bare plane, and the top plate carries a rectangular grid of actuated pins that can translate in discrete increments under computer control. We propose to use this gripper to immobilize objects through frictionless contacts with three of the pins and the bottom plate. We present an efficient grasp planning algorithm, describe the design of the gripper, which is currently under construction, and report preliminary simulation experiments.

It was shown in Ponce et al. (1993) that four-finger force-closure grasps fall into three categories: concurrent, pencil, and regulus grasps. The authors propose new techniques for computing these three types of grasps. The authors have implemented them and present examples.