The following are exercises to help you internalise the ideas covered in class. They are not typical examination questions.
Introduction
Linear Geometry
Parametric Curve Definitions
Parametric Curve Interrogations
Parametric Surface Definitions
Parametric Surface Interrogations
Subdivision Curve Definitions - Box Splines
Subdivision Curve Definitions - Interpolating
Subdivision Curve Interrogations
Subdivision Curve Analysis
Subdivision Surface Definitions - Box Splines
Subdivision Surface Definitions - Interpolating
Subdivision Surface Interrogations
Subdivision Surface Analysis
Don't read the discussion about a question until you have written down something in the way of an answer, or at least identified why the particular question is hard.
Equally, don't spend longer than half an hour on any example.
What is the limit of Pi as i tends to infinity ?
What properties of the polygons in the sequence are invariant as i increases ?
What can you say about the shape of Pi for large finite i ?
Which of these properties are still true if the vertices of P0 do not all lie in one plane ?
Don't read the discussion until you have written down something in the way of an answer, or at least identified why the particular question is hard.
Equally, don't spend longer than half an hour on any example.
What is the limit of Pi as i tends to infinity ?
Don't read the discussion until you have written down something in the way of an answer, or at least identified why the particular question is hard.
Equally, don't spend longer than half an hour on any example.
In this particular case, `what is the limit' should be read as `what can you say about the limit', as the full answer is fairly complicated.
How are the following operations implemented ?
Don't read the discussion until you have written down something in the way of an answer, or at least identified why the particular question is hard.
Equally, don't spend longer than half an hour on any example.
Q is a point on the plane and N is a normal vector.
Q is a point on the plane and U and V are displacements lying in the plane.
Q, R and S are all points lying in the plane.
Don't read the discussion until you have written down something in the way of an answer, or at least identified why the particular question is hard.
Equally, don't spend longer than half an hour on any example.
In system building it is good practice to build a small kernel of methods which actually depend on the internal representation of an object (this is called the API), and then implement the bulk of the function of the software being built by calling those kernel functions.
Can you implement a routine to calculate the line perpendicular to two lines by calling the incidence routines defined for linear geometry ?
If not, why not ?
Don't read the discussion until you have written down something in the way of an answer, or at least identified why the particular question is hard.
Equally, don't spend longer than half an hour on any example.
Devise an algorithm which will report whether two triangles in E3 intersect or not.
The algorithm should still work when the planes of the triangles are parallel or coincident.
Don't read the discussion until you have written down something in the way of an answer, or at least identified why the particular question is hard.
Equally, don't spend longer than half an hour on any example.
Prove that the first derivative of a parametric curve whose basis functions are the Bernstein polynomials of degree n is itself a Bernstein polynomial of one degree lower, whose coefficients are n times the first differences of the original control points.
Don't read the discussion until you have written down something in the way of an answer, or at least identified why the particular question is hard.
Equally, don't spend longer than half an hour on any example.
Consider the situation where 21 equally spaced points are to be interpolated.
Sketch the basis function corresponding to the central point in the case of Lagrange interpolation and in the case of cubic spline interpolation.
Don't read the discussion until you have written down something in the way of an answer, or at least identified why the particular question is hard.
Equally, don't spend longer than half an hour on any example.
These discussions are not complete proofs, although they point towards places where proofs may be found.
What is the limit of Pi as i tends to infinity ?
All vertices of Pi converge to the centroid of the vertices of P0
What properties of the polygons in the sequence are invariant as i increases ?
What can you say about the shape of Pi for large finite i ?
This is a much harder one to get a handle on. The methods described in Bachman and Schmidt's book, 'n-gons', show that it tends to an affine image of a regular polygon. These methods involve taking the Fourier transform of the sequence of vertices and considering the effect of the function f(P) on the terms of different frequencies.
Which of these properties are still true if the vertices of P0 do not all lie in one plane ?
Almost all, provided that you reword them properly. The sum of the exterior angles decreases but never drops below 2\pi. The convexity property is true of any projection of the polygon on to a plane. This is because the coordinates of the new vertices are weighted means of the old ones. This is a property invariant with respect to the coordinate system chosen for the computation, and so we can choose a coordinate system aligned with the projection plane and then ignore one coordinate to give a 2D problem.
What is the limit of Pi as i tends to infinity ?
It is tempting to jump to the conclusion from the similarity with Taster(1) that the polyhedron converges to the centroid of the vertices. It doesn't. It converges to a smooth (C1) surface which contains parametric polynomial pieces. This is not obvious and will be treated later in the course.
However, it is possible to see that each original face is a polygon in the sense of Taster(1), which must shrink towards the centroid of that face. Thus if there is a limit surface it must contain the centroids of all the original faces and cannot therefore collapse to a single point.
How are the following operations implemented ?
These are all trivial. In each case a simple loop through the coordinates/components gives a simple-to-code solution. The compiler will probably unroll the loop for you, but if you want fast code and have a dumb compiler it is probably the same number of lines of code to write the loop in unrolled form initially.
Two examples follow, one using a loop and the other unrolled. Count from 1 convention is used for the arrays used to hold the displacements A, B and C.
(D+D) => D
for each i in [1..3] do C[i] := A[i]+B[i]; enddo
(r*D) => D
C[1] := R*A[1]; C[2] := R*A[2]; C[3] := R*A[3];
Q is a point on the plane and N is a normal vector.
Q is a point on the plane and U and V are displacements lying in the plane.
Q, R and S are all points lying in the plane.
The easy conversions are between the generative forms and to the less redundant implicit form.
Note that representation 3 can be recast by noting that w=1-u-v, so that P = (1-u-v)Q + uR + vS = Q + u(R-Q) + v(S-Q).
R := Q+U
S:= Q+V
U := R-Q
V := S-Q
N := U x V (vector cross product)
The conversion from the implicit form to the parametric requires the arbitrary choice of a direction within the plane.
This can be computed by taking an arbitrary vector G not collinear with the given N (a possible choice is the axis vector making the largest angle with N), and then using the cross product with N to give a vector in the plane.
U := N x G
V := N x U
In each case, normalisation of N, or U and V, as is appropriate, can follow the computation of the unnormalised vectors.
The conversions between 1 and 3 can go via representation 2.
In system building it is good practice to build a small kernel of methods which actually depend on the internal representation of an object (this is called the API), and then implement the bulk of the function of the software being built by calling those kernel functions.
Can you implement a routine to calculate the line perpendicular to two lines by calling the incidence routines defined for linear geometry ?
If not, why not ?
It is not possible to implement this function in terms of those primitives.
This latter is an example of a very powerful mathematical principle, probably known earlier, but articulated by Sophus Lie, that identifying the group under which a property is invariant is the most important step in studying that property.
Devise an algorithm which will report whether two triangles in E3 intersect or not.
The algorithm should still work when the planes of the triangles are parallel or coincident.
There are two issues here, robustness and performance.
Near coincidence of the planes of the triangles is going to be a problem whatever. We also have potential difficulty if edges are close to collinear.
We can, however, avoid problems with non-coincident parallelism by first making certain checks which detect non-intersecting triangles for sure.
These are a good standard first stage, especially in any context where the bounding boxes of the triangles are pre-computed and stored with the triangles.
A good second stage is to check that each of the triangles spans the plane of the other. If either of the triangles has all three vertices on the same side of the plane of the other triangle, there cannot be an intersection (because triangles are convex). These tests can be carried out by the evaluation of the volumes of the tetrahedra formed by the three vertices of one triangle and one vertex of the other. The sign of the determinant giving the volume is positive if the odd vertex lies on one side of the plane of the other and negative if it lies on the other side.
|
Once these checks have been made we can then proceed by checking whether the triangles are actually coplanar, and using separate methods if they are. If the triangles have distinct planes, those two planes intersect in a line, and that line intersects each triangle in at most a line segment. The two line segments can finally be compared for overlap. Not a trivial piece of programming.
If the triangles are coplanar, the actual intersection can be an area rather than a line segment. Note how important reading the question is, which asked only for an algorithm to check whether an intersection existed, not to actually evaluate it.
A recent idea which looks promising is the use of linear programming to find the size of the smallest axis-aligned cube containing one point in each of the triangles. This appears to be extremely robust, not being sensitive at all to the singularities which plague methods based on intersection of the triangles' planes.
This problem is unlikely to be found in isolation. It is much more likely to be part of the finding of intersections between large triangulated surfaces, and in this context it is absolutely essential to compare only those triangles which stand a chance of intersecting, because almost all pairs don't.
The key to this selectivity is to use spatial indexing which find quickly which other triangles are close to a given one. There are two fairly simple techniques:
In a oct tree, the space containing the entire triangulation(s) is bisected in all three directions into octants, and then each octant into its own octants and so on recursively. If we know which octant one triangle lives in, we need only look at that octant and neighbouring ones for nearby triangles.
If the triangles are sorted into sequence on some direction, and then projected into a set of 2D boxes in the plane perpendicular to that direction, we need only compare each triangle with the ones in the same and adjacent boxes. The size of the box needs to be at least as large as the largest triangle. The sorting means that triangles can be forgotten once the sweeping process has left them behind.
I do not have any quantitative information on which of these two methods is faster. It probably depends on the shape which the triangulations represent.
Prove that the first derivative of a parametric curve whose basis functions are the Bernstein polynomials of degree n is itself a Bernstein polynomial of one degree lower, whose coefficients are n times the first differences of the original control points.
Given a parametric curve P(t) = Sumi=0..n Ai s(n-i)ti n! /(i! (n-i)!) where s = 1-t
To Prove that dP(t)/dt is also of the same form, but of one degree lower, and that its coefficients are the differences Ai+1-Ai.
Proof
dP(t)/dt = Sumi=0..n Ai d(s(n-i)ti)/dt n! /(i! (n-i)!)
d(sn-iti)/dt =
sn-id(ti)/dt - d(sn-i)/ds ti
= isn-iti-1 - (n-i)sn-1-iti
dP(t)/dt = Sumi=0..n Ai isn-iti-1 n! /(i! (n-i)!) - Sumi=0..n Ai (n-i)sn-i-1ti n! /(i! (n-i)!)
= Sumi=1..n Ai sn-iti-1 n! /((i-1)! (n-i)!) - Sumi=0..n-1 Ai sn-1-iti n! /(i!(n-i-1)!)
= n [Sumi=1..n Ai sn-iti-1 (n-1)! /((i-1)! (n-i)!)
- Sumi=0..n-1 Ai sn-i-1ti (n-1)! /(i! (n-i-1)!)]
Writing i'+1 for i in the first term and i' for
i in the second, and n' for n-1 in both, we
have dP(t)/dt = n Sumi'=0..n' Ai'+1
sn'-i'ti' n'! /(i'! (n'-i')!)
- Sumi'=0..n' Ai' sn'-i'ti' n'! /(i'! (n'-i')!)
= n Sumi'=0..n' [Ai'+1-Ai'] si'tn'-i' n'! /(i'! (n'-i')!)
which is exactly the form we sought to prove.
Consider the situation where 21 equally spaced points are to be interpolated.
Sketch the basis function corresponding to the central point in the case of Lagrange interpolation and in the case of cubic spline interpolation.
It is easiest to let the points be at integer coordinates centred about zero.
The required basis function is given by
f(t) = Producti=1..10 (t-i)(t+i) / (-i2)
= Producti=1..10 (t2-i2) / (-i2)
= Producti=1..10 (1 - t2/i2)
Clearly this has roots at t = -10..-1, 1..10
Near t = 0 it is given by
f(t) = 1 - t2 Sum (1/i2) + O(t4)
~ 1 - 1.57 t2
At t = sqrt(90) (~9.5) it takes the value
(1-90)(1-90/4)(1-90/9)(1-90/16)...(1-90/64)(1-90/81)(1-90/100)
~(-89)(-21)(-9)(-4)...(-1/2)(-1/9)(1/10)
The value there is negative and its magnitude greater than 360.
Even with very rough arithmetic it can be seen that the effect of a unit change in the central control point has wildly disproportionate effects near the end of the [-10..10] interval.
To determine the basis function for the cubic spline we first calculate the coefficients of the B-splines which interpolate 1 at the central point and 0 elsewhere. Because we are omitting consideration of end-conditions, we will consider the case where there are zeroes out to infinity in both directions.
The values at the integer abscissae for the cubic B-spline basis function are [1, 4, 1]/6 and so we can solve the coefficients by exploiting symmetry about 0. Let the coefficients be B0 for the central B-spline and Bi for those centred a distance i from the centre. The top left hand corner of the matrix equation for these values is
|
|
= |
|
Solving this by Gaussian elimination is stable because the left hand side is so totally diagonally dominant, and the effect of the bottom right hand corner is soon seen to be almost irrelevant. The coefficients Bi die away rapidly with i (a factor of almost 4 per step), and it is intuitively clear that the ripples in the basis function must die away at the same rate.
The interpolating spline basis function has its maximum at the interpolated point, and has very little effect anywhere far from its centre.