Physically Based Computer Animation
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMS W4167: Physically Based Computer Animation
Except where explicitly stated otherwise, you may work out equations in writing on paper or a whiteboard. You are encouraged to use Piazza to converse with other students, the TAs, and the instructor. HOWEVER, you may NOT share source code or hard copies of source code. Refrain from activities or the sharing materials that could cause your source code to APPEAR TO BE similar to another student’s enrolled in this or previous years. We will be monitoring source code for individuality. Cheating will be dealt with severely. Source code should be yours and yours only. Do not cheat. For more details, please refer to the full academic honesty policy on the departmental website and on Piazza. 1 Introduction In Theme 2 Milestone 3, you will design your own algorithm to accelerate collision detection in scenes containing a large number of particles or edges. Test scenes for this milestone are located in a new directory, assets/t2m3. 2 New XML Features This milestone adds the following new feature: 1. The new collisiondetection node specifies how collision detection is performed during the simulation:
The valid values for type are “allpairs” (the default) and “contest”. allpairs is already implemented in
the starter code, and performs a brute-force check of all pairs of objects to see if any two of them are
colliding. You will be implementing the contest algorithm in this milestone.
3 Required Features for Milestone 3
3.1 Collision Detection Contest
Edit ContestDetector.cpp and implement any algorithm you like to speed up collision detection, when col-
lisions are handled using the penalty method with thickness 0. In other words, given start-of-timestep
positions, you are to return all particle–particle, particle–edge, and particle–halfplane pairs that might be
overlapping at those positions. You do not need to perform any continuous-time collision detection, and you
do not need to check if particles are approaching, since the penalty method only cares about the overlap
at the start of the time step. The penalty force will then take your list of potentially overlapping pairs,
compute a force for that pair, and apply it to the system. Note that if a pair is not actually overlapping,
the computed penalty force between that pair will be zero.
One solution is to simply return all pairs of objects in the scene as potentially overlapping. This is the
solution that is implemented as “allpairs” collision detection type in the starter code. It is very slow – O(n2)
– since a gradient has to be computed for all of these pairs, even for those that aren’t overlapping.
1
Another solution is to compute the distance between all pairs of objects, and only return those that are
actually overlapping. No time is wasted on computing unnecessary gradients, but the detection itself is now
very slow – again O(n2). You want to design an algorithm in between these two extremes – one that can
quickly determine all pairs that are likely to be overlapping, without including too many false positives.
We will run your alogrithm on five very large test scenes for the leaderboard, and measure the total time
it takes for your code to simulate the scenes. We will compare your algorithm’s time against that of other’s
submissions, and your milestone grade will be determined by how well your algorithm performs relatively.
Here are the details of the competition.
• You must not sacrifice correctness for speed. In other words, your collision detection must be conser-
vative. If two objects actually overlap during a time step, you must include that pair in your list of
detected pairs. If they do not overlap, you may include that pair in the list. The oracle can be used
to check that your code does not miss collisions.
• You must not change any files in the starter code except ContestDetector.cpp and ContestDetector.h
(you may also create new source files containing helper code to be included as headers in ContestDe-
tector.cpp or ContestDetector.h, if you’d like). We will overwrite all other files with those supplied in
the starter code before compiling your contest entry. There are many inefficiencies in the starter code
that could be optimized – but the focus of this milestone is solely on collision detection.
• You are encouraged to use the internet, class notes, research papers, etc. to find potentially useful ideas
or algorithms. However, all non-starter code you submit must be entirely your own. You may
not link to any external libraries except for those already used by the starter code (e.g. Eigen).
• The five test scenes will include
– The box-of-balls scene included with the starter code,
– A scene very similar to the box-of-balls scene included with the starter code,
–
– The ribbon-pile scene included with the starter code,
– A scene very similar to the ribbon-pile scene included with the starter code,
– A scene very similar to the best submitted creative scene; see Section 5.
You should strive to design a well-rounded algorithm that performs well for the two aforementioned
scenes, as we will only announce and release the best submitted creative scene after the competition
is over.
• For each of the five test scenes, we will run your code and record the time taken. If any of the following
occurs, we will use the time taken by the oracle’s implementation of “allpairs” instead:
– your code fails the oracle due to unacceptably large residual (e.g., you miss a collision),
– your code fails to compile,
– your code takes longer than the time taken by the oracle’s implementation of “allpairs”,
– your code crashes or fails to complete the simulation for any other reason.
– your code uses more than 20GB of RAM during execution.
Each scene is worth 20% of your milestone grade. For each scene, your grade is determined as follows:
if T is your total time, A is the total time of the oracle running “allpairs”, M is the fastest total time
in the class, r the number of submissions slower than yours, and N the total number of submissions,
your grade is given by the formula
10
(
A− T
A−M
)1/3
+ 10
r
N − 1 .
This will give a number between 0− 20 for each scene, which sums up to give your grade.
2
4 Leader Board
We provide a leader board that you can use to compare the performance of your code against other students’.
Submission to the leader board is not required but it’s strongly recommended as it provides a consistent
system environment to evaluate the performance of all submissions fairly. Additionally, you may earn up
to 10 bonux points for your submission on the leaderboard, depending on your position and how long your
submissions stay on the leaderboard.
To submit an assignment, export your Codio Box as a zip file (Project > Export as Zip). Rename your
zip file to youruni.zip and directly upload that zip file on the leader board. Please do not modify the
zipfile after downloading it from codio. Safari will unzip immediately after you download a zip file. Do not
try to rezip it. Use Chrome or Firefox instead. Zip files greater than 30 MB will not be accepted. It’s
recommended that you remove the build/ folder on Codio before exporting the zip file. You should have
received an email from the TAs with your token to use for the leaderboard. Use this token to submit your
zip file, and you’ll get a submission ID. Use this submission ID to find your rank in the leaderboard. The
link to the leaderboard will be posted on Piazza. If accessing the leaderboard gives “Your connection is not
private”, please click on Advanced and proceed to the leaderboard.
You may challenge the Champion of Year 2013, whose binary code is provided in your Codio box as
FOSSSim2013Champion.
5 Creative Scene
As part of your final submission for this milestone, please include a scene of your design that best shows off
your program. Based on the quality of your scene, you will have the opportunity to earn up to 10% extra
credit. Your scene will be judged by a secret committee of top scientists using the highly refined criteria of:
1. How well the scene shows off this milestone’s ‘magic ingredients’ (a la Iron Chef ).
2. Aesthetic considerations. The more beautiful, the better.
3. Originality.
Top examples will be posted to Piazza.
To submit this scene, place the XML file in the assets/Creative/ directory of your submission, and
submit a video of the scene to Courseworks.
To export PNGs of your scene, run
path/to/FOSSSim -s path/to/creativescene.xml -m path/to/output/dir/
This will output a PNG file for each frame of the simulation. The program will output black frames if you
pass it -d 0 so leave that flag out.
Then, create a video from your PNGs using ffmpeg
ffmpeg -r 24 -f image2 -i pngs/frame%05d.png -vcodec libx264 -pix_fmt yuv420p out.mp4
Please download and submit the mp4 file to Courseworks.
Remember to generate videos of your creative scene before submitting, as the Codio box will become
read-only after you submit.
6 FAQ
Theme 2 Milestone 3 FAQ:
Q: Is there any way to change my algorithm over time?
A: Sure, use static variables.
3
Q: If I am using Axis-Aligned Bounding Box (AABB) on edges, should I use the edge radius
or particle radius?
A: The edge radius. If the edge radius is larger you will correctly capture collisions. If it is smaller than
the particle radius than particle-particle collisions will detect collisions before it reaches the edge.
Q: What exactly are we being asked to do?
A: You need to prune the O(n2) algorithm from checking every pair of objects using some higher level
(broad) algorithm and pass down a reduced list of pairs (through ParticleParticleCallback, ParticleEdgeCall-
back, ParticleHalfplaneCallback) for last weeks collision detection routines to determine/handle collisions.
Q: My algorithm needs bounds on the positions of scene elements. For example, I want to
know the X coordinate range of all particles. How do I obtain this?
A: By adversary arguments, the only sure way to do this is to look at all scene particles and determine
the max/min of their X and Y coordinates.
Q: How do we test our algorithm and submit it?
A: Test your algorithm on codio and submit it the usual way. You can also test the performance of your
algorithm against others using the leader board.
Q: How can I verify the test scenes are passing correctly?
A: Just as before use the oracle. Run the oracle with your scene’s output and get a visual display of
every missed collision. Missed collisions are highlighted by the oracle in red circles.
Q: How long does it take for the results to go up to the leader board after I submit my
code?
A: It depends on how many students submit to the leader board in a certain timeframe (i.e. how busy
the leader board server is). We don’t measure wall clock time. We measure only processor time used by the
FOSSSim process. So, the heavier the load (the more students are using the autograder), the more time it
will take until your result is posted to the board.
Q: Should our code handle half-planes?
A: Yes.
Q: Should there be an acceptable trade-off between correctness and performance?
A: No. We cannot even start talking about the performance of an algorithm without first confirming its
correctness. In other words, no matter how fast a collision detector runs, if it ever misses one legitimate
collision, it is not acceptable.
7 Extra Reading
There have been a lot of research papers about collision detection and culling. You may implement one of
them or design your own algorithm inspired by them. Here are some examples:
Fuchang Liu, Takahiro Harada, Youngeun Lee, and Young J. Kim. 2010. Real-time collision culling of
a million bodies on graphics processing units.