Undergraduate Research | George R. Brown School of Engineering

Undergraduate Research | George R. Brown School of Engineering | Rice University

Undergraduate Research in Engineering at Rice

Jeff Phillips, Senior Computer Science and Mathematics student
Modeling Automated Knot Tying
with Dr. Lydia Kavraki
Since July 2001 I have been working on a research project to model rope and perform automated knot tying with it. I am working together with Andrew Ladd a graduate student in the Computer Science department at Rice and under Dr. Lydia E. Kavraki an Associate Professor of Computer Science and Bioengineering at Rice.
Simulated knot tying has been a challenge in physical simulations recently, especially surgical simulations. We attempt to solve this problem by modeling rope. In order to tie a knot, the rope needs to be physically realistic so that it moves in a reasonable way, numerically stable so that it does not explode (this can be a problem), and have complete collision detection so that it does not pass through itself, and this all needs to be done in a computationally efficient way. Knot tying presents tough cases of these issues because of the high expressiveness and contact in the relatively small portion of rope which is in the knot.
Our model uses a spline of linear springs with the mass pushed to the control points to represent the rope. A sphere is placed on each contol point to give rope volume and to be used in collision detection. We chose this model because it is similar to what groups attempting to make surgical simulations have been using and because it is simple and should be easy to simulate. We developed the way to accurately control and operate in such a model.
We need to adaptively insert and remove control points within the spline by subdividing and joining springs in order to allow for adaptive expressiveness and lengths without losing the ability to ensure we find all collisions. This required that we handle the control points as representing two separate parts of the rope (the left half of the right spring and the right half of the left spring) in order to avoid numerical computational and symmetry errors.
To handle all collisions (as well as insertion and removal events) correctly, we need to run a discrete events simulator. At every time step, we calculate the order of all events that will occur. They are then handled in order, with the correct time information. After an event is handled, stale events are dequeued and secondary events are queued.
We tested our model by tying square knots and reef knots. We start with just a handleful of control points and it subdivides the structure until the rope has a continuous volume.

If you have a certain browser/mpeg player you may be able to see these mpegs we made of the simulation in action: knot.mpeg reef.mpeg

I am advised on this project by Lydia E. Kavraki and Andrew Ladd of the Physical Computing Group at Rice University.
Department of Computer Science
Back to Undergraduate Research page

George R. Brown School of Engineering, Rice University grbsoe@rice.edu