next
to problems where the material has been covered in class or that you should be
able to solve through your own personal research or design.Exploration Questions Pool
CSE 872, Charles B. Owen Instructor
Here's the rules. Select one of the following questions to answer for each of the 4 exploration due dates. For each due date you are to provide a written solution in ACM SIG proceeding format. Your paper must include a title, references, and sections. One paper can be supplied for all problems you solve in written form. It should look like a paper and read like a paper, not the answer to a homework problem. Please include two abstracts, one for each of the problems. Be sure to indicate the problem number in the abstract.
Notice: The following will result in an automatic rejection of your exploration submission: improper format, lack of references, lack of abstracts, lack of proper section format. If you paper is rejected, you will be allowed a chance to revise and resubmit it within one week. Resubmission will incur a 20% points penalty.
This document will be subject to additions during the
semester. Some questions concern material that has not been covered yet.
I'll put a check mark next
to problems where the material has been covered in class or that you should be
able to solve through your own personal research or design.
I'll add more questions later, but for now good choices to start with would be 1 (look up some simple physics for graphics for ideas here or consider using curves), 2 (look for free-form deformations), 3 (read up on the midpoint method), 8 (should be pretty obvious). These are more basic questions.
"Just keep swimming. Just keep swimming. Just keep swimming, swimming, swimming. What do we do We swim, swim." Dory in Finding Nemo
1. The movie Phantasm
had these lovely little spheres that could fly through the air in arbitrary trajectories
and with arbitrary orientations, but with a clearly physics-based trajectory. If you
didn't manage to destroy it before it hit
you, it jabbed spikes into your head and drilled a hole into your scull (with
suitable gushing blood special effects). Phantasm was made in
1979 and used fishing line to fly the spheres. Were you to redo Phantasm
and create the spheres using computer graphics, describe exactly how you will
compute the position and orientation of a sphere at any point in time during
its flight. Indicate all data you will require for any control points,
manipulation methods, etc. and all equations you will use. Remember, you must
be able to specify where the ball will stop. Assume the sphere follows a
ballistic path, obeying the laws of physics (in conjunction with some alien
thrust mechanism). You'll have
to decide how changes in course are to be described. (Note: is orientation an
issue)
2.
Its fairly common
that we start out with a high-resolution polygon mesh that we wish to deform. In
Terminator 2, a head model was deformed to move through bars. In the Hellraiser
movies, models were deformed into cenobites. We might capture a polygon mesh
for a real model, and then expect that model to deform in strange ways. But
deformations are like curves, best handled by control points of some kind.
Provide me with a solution that will allow you to deform a polygon mesh model
using control points. You must be able to accommodate: huge noses, pregnancy
(by aliens, of course), extra large alien brains, and very large feet. (Note:
this is not skeletal animation, but the topics are related).
3.
In The Matrix, bullet trajectories are computed using a physics-based model and slowed-down time
("bullet time"). Provide a case where the results from using
Euler's method and the midpoint method yield significantly different bullet
trajectories (where significantly means positional errors in excess of 5%
and/or Neo dies). Demonstrate that the midpoint method result is closer to
accurate than the Euler method for your example. A problem with this question
is that the bullet travel is so fast and so short, it does not really curve
very much. So, assume Neo has created a local gravitational field that is strong
enough to pull the bullet away from his body.
4.
You are asked to
create animation for the body (everything but the fins) of Marlin in Finding
Nemo. Indicate at least two alternatives for animating a fish and explore
the implementation of one of these alternatives in detail.
5. In the movie Titanic, the ocean waves were all produced using computer graphics. Assume you are creating a system to implement the water in Titanic. How will you handle the problems of a) displacement as the ship moves through the water and b) water rushing into flooding compartments
9. Devise an algorithm to convert particles into an isocontour for water surfaces.
6.
The fast BSSRDF algorithm
implements subsurface scattering in two passes. The first pass uses an
algorithm to place a uniform sampling of points on the polygon mesh. Devise an
alternative distribution of points on the mesh that is better. Indicate why your
method is better.
7.
The Hall color model assumes that the color of the specular highlights is
independent of the viewer and light, only the intensity varies. However, a
property of real materials is a color shift, wherein reflections where the light
direction is near the normal tend to be the surface color, whereas reflections
near the grazing angle, where the light is nearly parallel to the surface, tend
to be the color of the light source. Devise a revision of the color model
that takes the phenomena into effect. Be sure you indicate any additional
parameterizations you may need. Note: Assume the Hall color model as
presented in Lecture 2. There are extensions to that model, including
extensions by Roy Hall, some of which may or may not take care of this problem.
If you find such an extension, you must prove that it will achieve the color
shift effect.
8. Suppose f(s,t) is
the illumination of a square emitting light source in space, where s ranges from
0 to 1 in one dimension over the face of the light source and t ranges from 0 to
1 over the other dimension. Then, the light from this source emitted by
surface area hit by the ray would be:
where x is a two-dimensional variable and A is the area of the light surface hit by the ray. This is, in fact, how light works in nature. Show that a ray trace solution that really took into account this characteristic of the light would yield a ray illumination of zero. Then, show how multiple rays can be used to estimate a valid solution for I. (Hint: Monte-Carlo something or another...) It is not sufficient to say "bunch of rays" or just "average". You must support your argument mathematically.
9.
Newton's cradle is a fun toy with five balls hanging from string. Everyone
has seen one of these. I've included a picture as an example.
Normally we would assume e is close to 1 when
simulating the operation of one of these. What if we had a small
e, say 0.1. What would be the consequences?
Would starting the cradle operating by dropping one ball result in the
separation of the second and third balls? (Please, no empirical arguments
here or comments about preservation of energy. You must support your
answer with reasonable rigid body physics. Do not say "it will slow down".
Instead, say how much it will slow down.)
11. In ray tracing, the scene space is hierarchically subdivided to speed up rendering. One common structure used for scene subdivision is the kd-tree, in which planes that are perpendicular to one of the system axes are used to split the sub-cells. A "good" kd-tree can make ray tracing much more efficient than a mediocre kd-tree by significantly reducing the overall traversal and intersection cost. Building a kd-tree requires a decision as to the position of the splitting plane in each subdivision. Assuming the cost of a traversal step and the cost of intersecting a polygon are both constant, devise a way to decide the splitting plane that minimizes the overall traversal and intersection cost. What is the complexity of your method?
12. When simplifying arbitrary polygonal meshes the general technique is to check the screen-space extent of a cluster of vertices with a threshold value. If the screen-space extent is smaller than the threshold value we collapse the cluster into one vertex. This technique treats all the vertices similarly. However, we normally need more detail on the edges of an object than on the faces (the portion of the object facing the camera). Devise a simplification technique which allows us to have more detail on the edges to make them look smooth.
13. Principal components analysis (PCA) is commonly used in dataset analysis to determine the components that contribute the most to a given trend within the dataset. Describe the process of performing a PCA, including the calculations for eigenvalues, and how it could be used in a computer graphics environment, for example with skeletal modeling. Specifically indicate what the data source for the equations will be, the equations that must be solved, and the method for computing PCA specifically for an example computer graphics problem.
14. Rather than using specialized motion capture equipment (magnetic sensors or multiple calibrated cameras), it is possible to get reasonable human motion data from a single video stream. You have at your disposal motion capture data that describe a good variety of motion. Assuming that on-screen positions of markers on a video clip can be accurately determined, how would you derive the 3-D motion?
15. In collision detection oriented bounding boxes are used to reduce the number of times 3D collision detection between objects must be performed. The intervals of these bounding boxes must then be sorted to determine if they intersect. In general this will take O(n log(n)) time where n is the number of objects. If there are a great number of objects, this may be too slow, how can the fact that objects will move relatively little between frames be used to achieve a better time complexity? What algorithm will you use to ensure the bounding box intervals are sorted? Under what conditions can a time complexity of O(n) be ensured?
16. Describe how you would go about coding a snow storm using these particle techniques. Be sure to explain how the particles are created, how they are affected on their way down, and how they are shown on the ground.
17. How do you model and render animal fur for animated characters?