I implemented an inverse kinematics system using both analytic IK and cyclic-coordinate descent.
Analytic IK:
It's fairly simple, just like how it was derived in class. Given the lengths of the two joints, it is possible to directly calculate the angles needed to achieve a target position. In my application, it only works on the first two joints and will ignore the rest.
Cyclic-Coordinate Descent:
This works by figuring out the vector between the base of the joint and the end position and using that to figure out the amount of and direction of rotation to reach the target.
This is done for each joint, started from the end, and working back to the root.
In my application, CCD works quite well until getting to 5 joints, where it starts to break for unknown reasons. In the video I show several movements.
I used this website as a reference: http://www.darwin3d.com/gdm1998.htm
For the final project, I'll be working on an inverse kinematics system.
So far I have modified my joint system that I created in CSE 169. It involves a hierarchy so that moving the parents affects the children. It takes in a file containing joints, sizes, and poses and creates a skeleton hierarchy that creates a box for each joint.
offset: Distance from the parent joint
boxmin: Lower corner of the box
boxmax: Upper corner of the box
rot*limit: Limit on rotation.
pose: Rotations required to get to a certain position, in radians.
Earlier, the project was written using old openGL, so I spent time converting it to new openGL by loading a cube obj and using some shaders. From here all I need to do is figure out the various methods for inverse kinematics.
For the final I want to get an inverse kinematic system working in two ways. Analytically, for a two joint system and numerically for a 4 joint system. I also want to animate the joints reaching their appropriate positions, so I am also planning on adding either a simple lerp or rotational velocity to smoothly move the joints into position.
I want to import the Oculus and Touch controllers and be able to specify target points in 3d space that way. If there's time, I want to have a simple sword fighting system, where it will attempt to block your attacks.
Mesh simplification is an interesting technique that takes complex models and figures out which edges contribute the least detail and remove those to get a simpler mesh with as much of the original detail as possible.
3.1 Model Viewer
I used code from 167 to render the triangles.
To render it with per-face shading, I had to duplicate the vertices and triangles so that each vertex was only associated with one triangle. Then I could pass in the associated color and get flat shading. In the following examples, I use the indices of faces % 3 to determine colors.
index%3 == 0 -> red
index%3 == 1 -> green
index%3 == 2 -> blue
My shaders then just use this value for color.
This did not affect the mesh that was used in the computations, however as this debug mesh was generated after any edge collapse or vertex split.
The mouse can rotate the camera and scrolling can zoom in or out.
3.2 Mesh connectivity data structure
My data structure consists of vertices, faces, and edges.
The vertices have vectors of faces and edges, to keep track of which they're a part of. They also have an index and quadric matrix.
The triangles have a vector of 3 vertices that make up the triangle, an index, and a normal vector.
The edges have the two vertices that make it up and an error value that is used in the set.
The mesh has a vector of vertices and triangles and their index values correspond to their position in the vector.
The mesh also has a std::set of edges which works as a binary tree for logarithmic insertions and deletions.
The triangles needed to keep track of the vertex indices so that in the EBO, they'd know which vertices to use to draw. I, unfortunately, could not think of an efficient way to update these indices so after an operation, I loop through the vectors and update the indices.
I also have indices for the triangles so that with a vertex split, it would be easy to know which triangles belonged to the new triangle.
From the off file, I first create vertices by reading line by line and putting them into a vector. Then I just read all of the faces.
3.3 Mesh Decimation
This was quite a challenge making sure that everything was correctly updated! Here's a basic rundown of how I do it.
I start with two vertices (v0, v1) to collapse and first find where they should collapse to, just by taking their midpoint. I move v0 to the collapse position, it will remain while v1 is going to be deleted.
Then I loop through v1's triangles and change them so that they use v0. I also delete the degenerate triangles that occur when v0 and v1 were part of the same triangle.
I then loop over the affected triangles to update the normals of the triangles and vertices.
The tricky part I struggled to deal with was how to update the indices of vertices and triangles without iterating through everything. I couldn't figure this out and so I loop through both making sure that the indices are correct. This causes the program to run too slowly on larger meshes unfortunately.
Note that the red triangle above X and the red triangle below Y that were connected to the original v0 and v1 now have a connection to the midpoint, the new vertex there. That green triangle is actually two triangles that unfortunately had the same divisibility by 3.
3.4 Quadric Simplification
Adding quadric simplifications was challenging. The actual computation of error wasn't difficult, but keeping edges updated was difficult.
I added an Edge class just for this purpose and had each vertex keep track of its edges.
In the edge collapse method, after the work of setting vertex positions and updating triangles, I worked on edges. Unfortunately, I had trouble keeping my vertices' edges updated, so I ended up looping through all the edges to see if it would be affected by this edge collapsing.
As each modified edge updated, I removed it from the set and reinserted it to keep the set in the correct order so that getting the first element would be the best edge.
Then it was a matter of getting the first Edge in the set as it had the lowest error and using that for an edge collapse.
The video above demonstrates the quadric simplification as it as the structure of the patch is kept intact as long as possible.
The mug starts with 572 and each step removes or adds 10 edges. I remove most of the edges and then revert back to the original model. Note though that the first edges that are lost are on the handle as there is less error there than on the main part of the mug. Also, note that most of the structure is intact until near the end.
There does seem to be some strange connectivity issues though, I would expect the handle to "meld" and have a big triangle connecting to the mug. And same with the walls of the mug.
3.5 Progressive meshes
This was interesting to implement. In addition to which I do above for edge collapses, I made a struct, RemovedVertex, containing information needed to reconstruct the edge, the indices and original positions of the vertices, the indices of triangles that belong to v1, and the vertex indices of the triangles that were removed.
Every edge collapse then creates one of these structs and pushes it into a vector. I save all the collapses in memory for now.
I added a vertex split method which essentially does the opposite of a collapse, given a RemovedVertex struct.
First I create the new vertex and put the positions of v0 and v1 back to where they were. I update the vertex indices and then create new triangles to recreate the triangles that became degenerate on the collapses. I update those triangle indices and then move the triangles that originally belonged to v1 back to v1 from v0.
So now I have a time index so that I know which step I'm on. Reverting a collapse is as easy as decrementing my index and doing a split on the RemovedVertex at that point.
I also added an EdgeCollapse method that took in a RemovedVertex so that I could recreate the collapse without worrying about quadrics or my edges. It works the same way as the original EdgeCollapse but skips the work with updating edges.
My video shows how it works on the test patch.
Download the executable here: https://drive.google.com/file/d/0B6PLHdK7QrvjY0hmYVd1WGs1RGc/view?usp=sharing
Instructions in the README.
Overall, this was a challenging assignment, but I learned a lot about how meshes work!
