CS 6650 Computational Motion (Fall 2013)

Assignment #1: Recursive simulation algorithms

DEADLINE: Monday, October 28, 2013
IN-CLASS DEMO DAY: Tuesday, October 29, 2013

In this assignment you will implement a simulator from scratch for a tree-structured rigid or elastic body system. Your simulator will make use of efficient recursive algorithms for forward dynamics (or quasi-statics) to estimate the motion of the structure. To support a wider range of student projects, you can choose to do one of four assignments:
  1. Implement forward robot dynamics using RNEA and CRBA: This combination leads to an O(N^3) algorithm for forward-dynamics of rigid-body systems, which is very fast for small N. Use this approach to build a fast simulator for a simple robot mechanism. Your interactive system should support the application of external forces, such as contact (modeled via penalty forces), or user-applied forces.
  2. Implement forward robot dynamics using Featherstone's algorithm: This option produces an O(N) forward-dynamics implementation, that is faster than option 1 for large systems. If you implement this version, you should apply it to a very large problem.
  3. Implement a quasi-static elastic rod simulation using the STRANDS algorithm [Pai 2002]: Implement a single quasi-static elastic rod solver for the "standard BVP" discussed in that paper. You may assume either that the rod is inextensible, or allows extension. In your interactive implementation, you should manipulate the free end of the rod using an applied wrench, which may be estimated by using a virtual coupling (a generalized 6-dof spring) to your animated tool.
  4. Implement a dynamic elastic rod simulation: As a final and more challenging option, one can attempt an implementation of "Discrete Elastic Rods" [Bergou et al. 2008].  Simplifications should be taken to avoid implementing all features given the limited time frame, e.g., a good target is to implement an isotropic, naturally straight rod.

General Guidelines

Modeling component: The main two tasks of this assignment are to (1) implement the core algorithm, and (2) apply it to a nontrivial example that you will model. The simplest example for robot dynamics algorithms (option 1 or 2) is a non-branching chain (or serial manipulator) with single-dof revolute joints, and should be used to debug your implementation.  Please also try at least one nontrivial, creative example of your choosing. Depending on what you attempt to model, you may decide to use rigid body links of various shapes. You can find the inertia tensors of common primitives, such as spheres, ellipsoids, boxes, cylinders, available in common rigid-body dynamics texts. 

Benchmark your results: Run examples with varying number of links/nodes, N, to determine its performance. Verify that your algorithm achieves the expected theoretical performance.

Groups: You must may not form groups to complete this assignment. You are free and encouraged to discuss equations and ideas with other students, however all software implementations must be conducted on your own.
   
Programming language: You are free to use any programming language and environment that you like for this project (C++, Java, Matlab, python, processing, etc.).

Animate your results: Use 3D (or 2D) graphics to generate an interactive animation of your simulation results. Demonstrate the response of your simulator to user-controlled forces. Feel free to use existing low-level graphics libraries, such as OpenGL, GLUT, or DirectX, or a more high-level graphics library, such as SFML (Simple and Fast Multimedia Library), Processing, Qt, etc. Building the graphical component first, even if it is simple, is also an excellent way to debug your implementation.  In cases where the simulation runs very slowly (such as for very large models, e.g., of a large botanical tree), you can dump frames and generate a video offline.

External library usage: Feel free to use external libraries for basic matrix-vector computations, as well as matrix solvers, e.g., a Cholesky solver for factoring the joint-space inertia matrix in option 1. You may not use external libraries for simulation, e.g., of robot dynamics, elastic rods, etc.

Written report and videos: You should submit a brief report detailing the approach that you took, including implementation challenges encountered. Your report should also describe any findings, performance analyses, and creative artifacts generated. Video artifacts are also strongly encouraged to demonstrate findings and creative artifacts. Videos can be generated using screen capture software, videos made from dumped frames, or even video shot off the screen using a hand-held video recorder.

Document external sources: You should list all significant external sources that you used to arrive at your final submission. This includes webpages, technical papers, other software implementations, as well as discussions with other students in the class.

Live demonstration: You will get the chance to demonstrate your results in a show-and-tell class on Tuesday, October 29. A demonstration is especially important for cases in which the results of your algorithm are not easily demonstrated in print or video. Note that although you are required to submit your software implementation, you are responsible for providing evidence that your project works via your report, videos, and live demonstration. The grader should not be required to run and interrogate your code to determine that your implementation works.

Hand-in using CMS: Please submit via CMS a brief written report (in txt or PDF format) describing your approach and any findings, in addition to your implementation, simulation artifacts, videos, etc. 

On collaboration and academic integrity: You are allowed to collaborate on the assignments to the extent of formulating ideas as a group, and derivation of physical equations. However, you must conduct your programming and write up completely on your own, and understand what you are writing. Please also list the names of people that you discussed the assignment with. You are expected to maintain the utmost level of academic integrity in the course. Any violation of the code of academic integrity will be penalized severely.  

References