The traditional high-level algorithms for rigid body simulation work well for moderate numbers of bodies but scale poorly to systems of hundreds or more moving, interacting bodies. The problem is unnecessary synchronization implicit in these methods. Jefferson's timewarp algorithm [22] is a technique for alleviating this problem in parallel discrete event simulation. Rigid body dynamics, though a continuous process, exhibits many aspects of a discrete one. With modification, the timewarp algorithm can be used in a uniprocessor rigid body simulator to give substantial performance improvements for simulations with large numbers of bodies. This paper describes the limitations of the traditional high-level simulation algorithms, introduces Jefferson's algorithm, and extends and optimizes it for the rigid body case. It addresses issues particular to rigid body simulation, such as collision detection and contact group management, and describes how to incorporate these into the timewarp framework. Quantitative experimental results indicate that the timewarp algorithm offers significant performance improvements over traditional high-level rigid body simulation algorithms, when applied to systems with hundreds of bodies. It also helps pave the way to parallel implementations, as the paper discusses.

Many of the most fundamental examples in probability involve the pose statistics of coins and dice as they are dropped on a flat surface. For these parts, the probability assigned to each stable face is justified based on part symmetry, although most gamblers are familiar with the possibility of loaded dice. In industrial part feeding, parts also arrive in random orientations. We consider the following problem: given part geometry and parameters such as center of mass, estimate the probability of encountering each stable pose of the part. We describe three estimators for solving this problem for polyhedral parts with known center of mass. The first estimator uses a quasistatic motion model that is computed in time O(n log n) for a part with n vertices. The second estimator has the same time complexity but takes into account a measure of dynamic stability based on perturbation. The third estimator uses repeated Monte Carlo experiments with a mechanics simulation package. To evaluate these estimators, we used a robot and computer vision system to record the pose statistics based on 3595 physical drop experiments with four different parts. We compare this data to the results from each estimator. We believe this is the first paper to systematically compare alternative estimators and to correlate their performance with statistically significant experiments on industrial parts.

This article presents the Voronoi-clip, or V-Clip, collision detection alogrithm for polyhedral objects specified by a boundary representation. V-Clip tracks the closest pair of features between convex polyhedra, using an approach reminiscent of the Lin-Canny closest features algorithm. V-Clip is an improvement over the latter in several respects. Coding complexity is reduced, and robustness is significantly improved; the implementation has no numerical tolerances and does not exhibit cycling problems. The algorithm also handles penetrating polyhedra, and can therefore be used to detect collisions between nonvconvex polyhedra described as hierarchies of convex pieces. The article presents the theoretical principles of V-Clip, and gives a pseudocode description of the algorithm. It also documents various test that compare V-Clip, Lin-Canny, and the Enhanced GJK algorithm, a simplex-based algorithm that is widely used for the same application. The results show V-Clip to be a strong contender in this field, comparing favorably with the other algorithms in most of the tests, in term of both performance and robustness.

This work considers sensor based motion planning for rod-shaped robots in unknown environments. The motion planning scheme is based on the rod hierarchical generalized Voronoi graph (rod-HGVG). The rod-HGVG is a roadmap for rod-like robots, and is an extension of a prior roadmap for point-like robots. We give an incremental method to construct the rod-HGVG thereby enabling exploration of unknown environments. An important practical feature of the algorithm is its sole reliance upon the use of work space distance measurements to objects that are within line of sight. Such measurements can be readily provided by conventional range sensors. Moreover, motion planning in a configuration space is achieved without explicitly constructing each configuration space obstacle. A key result derived in this paper is the distance gradient between two convex sets.

Article Design galleries: a general approach to setting parameters for computer graphics and animation Share on Authors: J. Marks MERL - A Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MA MERL - A Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MAView Profile , B. Andalman Harvard Univ. Harvard Univ.View Profile , P. A. Beardsley MERL - A Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MA MERL - A Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MAView Profile , W. Freeman MERL - A Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MA MERL - A Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MAView Profile , S. Gibson MERL - A Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MA MERL - A Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MAView Profile , J. Hodgins Georgia Tech. Georgia Tech.View Profile , T. Kang CMU CMUView Profile , B. Mirtich MERL - A Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MA MERL - A Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MAView Profile , H. Pfister MERL - A Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MA MERL - A Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MAView Profile , W. Ruml MERL - A Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MA MERL - A Mitsubishi Electric Research Laboratory, 201 Broadway, Cambridge, MAView Profile , K. Ryall Harvard Univ. Harvard Univ.View Profile , J. Seims Univ. of Washington Univ. of WashingtonView Profile , S. Shieber Harvard Univ. Harvard Univ.View Profile Authors Info & Claims SIGGRAPH '97: Proceedings of the 24th annual conference on Computer graphics and interactive techniquesAugust 1997 Pages 389–400https://doi.org/10.1145/258734.258887Online:03 August 1997Publication History 346citation2,992DownloadsMetricsTotal Citations346Total Downloads2,992Last 12 Months156Last 6 weeks16 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

No abstract available.

In automated assembly lines, part feeders often impose a bottleneck that restricts throughput. To facilitate the design of parts and assembly lines, the authors estimate feedrates based on CAD models of parts. A previous paper (Golberg and Craig, 1995) described how to predict throughput for a vision-based robotic part feeder given the distribution of part poses when parts are randomly dropped on a conveyor belt. Estimating this distribution is also useful for the design of traditional feeders such as vibratory bowls. In this paper the authors describe three algorithms for estimating pose distributions. The authors review the quasi-static estimate reported in Wiegley et al. (1992) and introduce a refinement that takes into account some measure of dynamic stability. The perturbed quasi-static estimate can be computed very rapidly and is more accurate than the quasi-static. Still more accurate are estimates based on Monte Carlo simulation using Impulse, although the latter comes at the penalty of increased computation time. The authors compare estimates from all three algorithms with physical experiments.

We introduce a promising new approach to rigid body dynamic simulation called impulse-based simulation. The method is well suited to modeling physical systems with large numbers of collisions, or with contact modes that change frequently. All types of contact (colliding, rolling, sliding, and resting) are modeled through a series of collision impulses between the objects in contact, hence the method is simpler and faster than constraint-based simulation. We have implemented an impulse-based simulator that can currently achieve interactive simulation times, and real time simulation seems within reach. In addition, the simulator has produced physically accurate results in several qualitative and quantitative experiments. After giving an overview of impulse-based dynamic simulation, we discuss collision detection and collision response in this context, and present results from several experiments.

We consider the problem of finding optimum force closure grasps of two and three-dimensional objects. Our focus is on grasps which are useful in practice, namely grasps with a small number of fingers, with friction at the contacts. Assuming frictional contact and rounded finger tips-very mild assumptions in practice-we give new upper (and lower) bounds on the number of fingers necessary to achieve force closure grasps of 2-D and 3-D objects. We develop an optimality criterion based on the notion of decoupled wrenches, and use this criterion to derive optimum two and three finger grasps of 2-D objects, and optimum three finger grasps for 2-D objects. We present a simple O(n) algorithm for computing these optimum grasps for convex polygons, a O(n log n) algorithm for nonconvex polygons, and an O(n/sup 3/) algorithm for polyhedra. In studying these optimum grasps, we derive several interesting theoretical results concerning grasp geometry.>

The authors describe a practical path planner for nonholonomic robots in environments with obstacles. The planner is based on building a one-dimensional, maximal clearance skeleton through the configuration space of the robot. Rather than using the Euclidean metric to determine clearance, a special metric which captures information about the nonholonomy of the robot is used. The robot navigates from start to goal states by loosely following the skeleton. The resulting paths taken by the robot are of low complexity. Much of the computation can be done offline for a given robot, making for an efficient planner. The focus is on path planning for mobile robots, particularly the planar two-axle car, but the underlying ideas may be applied to planners for other nonholonomic robots.>