Project P1b for CS4496, instructor Jarek Rossignac.
Purpose of P1b:
The purpose of this phase of project #1 was to think about techniques for resampling a curve such that it can be easily parameterized.
This parameterization allows the animator’s/artist’s needs to be met by allowing them to do things like indicate where a particular animation
should be at certain times. It’s worth noting that the parameter may not always be time.
Code and implementation.
|
Final Resampling
|
|
Computing Arc Length
In order to compute the total arc length, we treated the segments of the four-point subdivision curve as vectors.
For each vector, we computed it’s length and added it to a running total length. Assuming we have enough samples and the frequency
of the curve’s changes is reasonable in relation to the number of samples, this gives a good (not error free) estimate of the total arc length.
float compute_arc_length() {
float len = 0.0;
for (int i=0; i < svn; i++) {
len += C[i].disTo(C[sn(i)]);
}
return len;
}
|
|
Evenly Spaced Samples
To calculate a sampling of the arc length that had equal distances (on the arc) between samples, we took the total arc length
and divided it by the number of evenly spaced samples that we wished to achieve; this yielded the desired segment length.
To place the samples, we advanced around the curve following the vectors running from one of the initial samples to the next.
The evenly spaced points were almost always between the samples from the original curve. The only complexity here was moving
by an appropriately scaled vector along that path to place the point. When this happened, we also had to start from this
“mid-vector” position.
An example of our evenly spaced samples:
 The length of the arc is shown when the user presses ‘E’. The segment length between samples is also shown (numerically & as a small blue bar beneath the stats text). As a side note: once you run our evenly-spaced algorithm, you are no longer guaranteed to go through the control point. |
|
Implementing sampleAt()
The sampleAt function was easy to implement once we had the evenly spaced sample points!
With inputs clamped to [0.0,1.0], we multipled this t by the total arc length to get the desired distance traveled along the arc.
In order to locate this position, we divided this length by segment interval length. The floor function of this value then gives the maximal
evenly spaced sample point which is less than our desired total arc distance. To find the final value we simple travel along the vector
from here to the next sample by an amount scaled by the decimal portion of the earlier result.
The section of the curve traveled to reach by parameter t is visualized in our implementation by the blue circles at the sample points. The final position is a blue circle with a magenta fill setting. To animate a changing simply hold down ‘b’ and drag the mouse left and right. Mouse positions outside the window (left or right) get clamped to [0,1] range.
void sampleAt(float t) {
// lock to range
if (t > 1.0)
t=1.0;
if (t < 0.0)
t=0.0;
float segments = t * arc_len / seg_len; // the dist to travel in units of segments
segs_complete = floor(segments);
float seg_partial = segments - (float)segs_complete;
segs_complete %= svn;
// create the sample point
sample.setFromPt(C[segs_complete]);
vec travel_dir = sample.vecTo(C[(segs_complete+1)%svn]);
sample.addScaledVec(seg_partial,travel_dir);
show_sampleAt();
}
|
|
Naïve vs Evenly Spaced sampling
Naïve sampling gives sample points which have uneven distances between them. This makes it difficult to parameterize the curve being traveled.
A step of preprocessing the the samples to calculate their arc length positions would allow for at least a logarithmic time placement of samples
along the curve (via a binary search of the table to find the sample prior or equal to the position desired)*. In contrast, evenly spaced
sampling makes this a constant time operation – a matter of a few divides and adds.Naïve sampling also yields a poor animation if we advance the animation by one segment length per unit time. This is because in portions of the curve that were more heavily sampled the speed of the animation would appear to slow. This means that in order to give a constant speed animation we would need to utilize a method like that I discussed above – log time to get arc length travel. Unsatisfying. 
One downside of the evenly spaced sampling is that it may lose high frequency corners of the curve if the evenly spaced samples fall on opposite
sides of the curve. Some screenshots we have taken show this effect. This can be mitigated by taking more samples or possibly by flagging samples
in the region of high frequency curve sections. These flagged regions could then be sampled more heavily to retain the original curve.
Access time for this kind of idea will become a constant function of how much high frequency information we try to capture. Given enough
determination to capture the details of the curve, preprocessing to gather the points may also become a computational cost worth consideration.* There would be a constant time component here similar to our implementation of the sampleAt function (the moving along a vector to get the last little bit of arc distance). |
|
Equidistant Sampling
The sampling that we implemented is equidistant sampling along the curve. To sample according to equidistant spatial constraints
could be done via inscribing a circle around the sample point of radius r. The circle would intersect the curve at two places –
the previous sample and what would now be identifiable as your next sample!This would have several significant drawbacks as a method. First, in the even of some high frequency changes in the curve it is possible that there could be numerous circle intersections rather than simply a prev & next pair. With many intersections, it might be hard to discern which one to pick next. Second, the technique does not guarantee that the circle will intersect with the start point (ie, a parameter of 0.1 and 1.1 may have different locations on the curve). This can be confusing for any user. How to fix this? Well, at the limit of screen resolution (very small circles), high frequency noise won’t really matter and the error on how much we miss with the last circle coming round to the start point should be minimal (ie, 0.1 and 1.1 will look so similar position-wise that the eye probably won’t care). We should be able to improve this somewhat via running some quantitative tests to see where slightly larger circle sizes begin to trade off the needed visual quality versus data & computation. We did not implement this method. |