C2 Cubic Piecewise Interpolation with Different Parameterization Methods

0 comments

On the previous geometric modelling class assignment, we were given some points in dimension 2, and then asked to implement a C2 cubic interpolation with 3 different parameterization methods.


Here I will try to explain briefly everything related to the image above as much as I can in layman terms. 

Interpolation

Remember in junior high when mathematics was very basic, where we were given 2 points $(x_1, y_1); (x_2,y_2)$ and then we were asked to find a line passing these points? This is what interpolation means. Only that we would want a spline instead of a line, which means that it will involve polynomial equations. A line $f(x)=ax+b$ itself is a degree one polynomial.

Piecewise

Piecewise means that we want the interpolation to be done separately by considering only 2 points at one time. And then we connect those pieces into one complete spline.

C2 Continuity

Above we also see the terms C2 cubic interpolation. What C2 means is that we want the spline segments to be connected in the way such that their second derivative are the same. Here I call a spline between 2 points as a spline segment. 

Cubic

For this term we may refer to Bézier curve where it indicates that the curve will have 4 control points. Here is the equation for Bézier representation:
$p(u)=\sum_{i=0}^n c_i B^n_i(u)$ where $B^n_i(x)=\binom{n}{i}t^n (1-x)^{n-i}$

Parameterization

The image above was drawn using 3 different parameterization methods:
  • uniform for $\mu=0$
  • chordal for $\mu=1$
  • centripetal for $\mu=0.5$
The $\mu$ was used to calculate the length of each parameter in their sequence $t_0,t_1, ..., t_n$ by using $t_{i+1}-t_i=\|x_{i+1}-x_i\|^\mu$

To make it easier to imagine how these $\mu$ values will affect the shape of the spline, I made up a little story by looking the points as the racing game where the driver were required to pass these points in order to complete the race. Here we have 3 different drivers with different driving style.

Racer #1 drives with the same speed all the way, this is why he made sharp turn when he has to pass points that are closed to each other. This causes the ^ section which is called as cusp.

And then moving on to racer #2 who adjusts his speed extremely based from time to time by observing how far away the next point is. If the next point is near then he will slow down, otherwise if it is still far away then he will increase speed. This causes the last turn to be a late apex.
In racing, a driver will often use a "late apex," turning into the corner a little later than normal in order to straighten out the last part of the corner. This allows the driver to accelerate earlier and harder, gaining maximum speed down the next straight.
Lastly racer #3 is also the type who adjusts speed based on how far away the next point is. But he does not make too much extreme changes of speed along the way. So here we can see that the driving path he made is the one passing those points elegantly.

The question now is which racers complete the trip the earliest?
They completed it in the same amount of time!

Cubic Spline Interpolation in Matlab

0 comments

This was a homework in my geometric modeling class. Later I modified it to receive input with mouse click and a button to clear and redraw, and also a drop down to choose parametrization method.

Take a look at the spiral I made!!



Bezier representation:
$$
p(t)=\sum_{i=0}^{n} c_i B^n_i(t)
$$


function [ ] = draw( )
figure
hold on; box on;
grid;
uicontrol('Style', 'pushbutton', 'String', 'Try me again!',...
        'Position', [20 20 50 20],...
        'Callback', @draw_new);  
uicontrol('Style', 'popup',...
           'String', 'uniform|centripetal|chordal',...
           'Position', [20 340 100 50],...
           'Callback', @setmethod); 
draw_new ('','');
end

function [] = setmethod (hObj,event)
axis([0 10 0 10]);
global PARAMETER;
PARAMETER=get(hObj,'Value');
draw_spline();
end

function[]=draw_spline()
cla;
global XY;
global PARAMETER;
if PARAMETER ==1
    interpolate(XY, 0, 'r');
elseif PARAMETER == 2
    interpolate(XY, 0.5, 'g');
elseif PARAMETER == 3
    interpolate(XY, 1, 'b');
else
    interpolate(XY, 0, 'r');   
end
end

function [] = draw_new (hObj,event) %#ok
global XY;
cla;
axis([0 10 0 10]);
% Initially, the list of points is empty.
XY = [];
n = 0;
% Loop, picking up the points.
disp('Left mouse button picks points.')
disp('Right mouse button picks last point.')
but = 1;
while but == 1
    [xi,yi,but] = ginput(1);
    plot(xi,yi,'ro')
    n = n+1;
    XY(:,n) = [xi;yi];
    if (length(XY(1,:)) > 1)
        draw_spline;
    end
end
draw_spline();
end

function [] = interpolate(x, mu, color)
n=length(x);
t=parameterize(x,mu);
h(1:n-1) = t(2:n)-t(1:n-1);
mi=get_cubic_slope(x,t);
for i=1:n-1
    a=x(1,i);
    b=x(1,i+1);

    p(1,:)=x(:,i);
    p(2,:)=x(:,i)+(h(i)).*mi(:,i)/3;
    p(3,:)=x(:,i+1)-(h(i)).*mi(:,i+1)/3;
    p(4,:)=x(:,i+1);

    [q_bez] = deCasteljau(0,1,p,linspace(0,1,100));

    plot(q_bez(:,1),q_bez(:,2),[color,'-'],'LineWidth',3);
    plot(p(:,1),p(:,2),[color,'--o'], 'MarkerSize',3);
end

plot(x(1,:),x(2,:),'ro', 'MarkerSize',5,'MarkerFaceColor','r');
xlabel('x'), ylabel('y'),title(['Cubic Spline Interpolation']);
end

function[m] = get_cubic_slope(x,t)
%cublic spline interpolation
n=length(x);
h(2:n) = t(2:n)-t(1:n-1);
A=zeros(n-1,n-1);
b=zeros(2,n-1);
b(:,1)= 3*((h(1)/h(2)*(x(:,2)-x(:,1))));

for i=1:n-1
    A(i,i)=2*(h(i)+h(i+1));
end

for i=2:n-1
    b(:,i)=3*((h(i+1)/h(i)*(x(:,i)-x(:,i-1)))+(h(i)/h(i+1)*(x(:,i+1)-x(:,i))));
    A(i,i-1)=h(i+1);
    A(i-1,i)=h(i);
end

m=A\b';
m=m';
m(:,n)=0;
end

function[m] = get_hermite_slope(x,t)
n=length(x);
%piecewise hermite interpolation
m(:,1)=(x(:,2)-x(:,1))./(t(2)-t(1));
m(:,n)=(x(:,n)-x(:,n-1))./(t(n)-t(n-1));
m(1,2:n-1)=(x(1,3:n)-x(1,1:n-2))./(t(3:n)-t(1:n-2));
m(2,2:n-1)=(x(2,3:n)-x(2,1:n-2))./(t(3:n)-t(1:n-2));
end

function [t] = parameterize(x, mu)
t=zeros(1,length(x));
for i=2:length(x)
    t(i)=sqrt((x(1,i) - x(1,i-1))^2 + (x(2,i) - x(2,i-1))^2)^mu + t(i-1);
end
end

function [p_t] = deCasteljau(a,b,p,t)
n = size(p,1);
m = length(t);
p_t = zeros(m,2);
X(:,1) = p(:,1);
Y(:,1) = p(:,2);

for j = 1:m
    for i = 2:n
        X(i:n,i) = (t(j)-a)/(b-a)*X(i-1:n-1,i-1) + (b-t(j)-a)/(b-a)*X(i:n,i-1);
        Y(i:n,i) = (t(j)-a)/(b-a)*Y(i-1:n-1,i-1) + (b-t(j)-a)/(b-a)*Y(i:n,i-1);
    end

    p_t(j,1) = X(n,n);
    p_t(j,2) = Y(n,n);
end

end


Browsers Add-ons

0 comments

WOT

WOT gives warning whenever we are about to enter websites with bad reputations, rated by the community. WOT categorises those bad websites as either: scam, phishing, adult content, illegal, Malwares/viruses. 


Adblock

I totally understand that ads is a way to gain traffic and customers. But I sincerely prefer to not have flashy adult site ads, or promotions that actually requires you to do sacrifice for them before they will give you a piece of cake. So go ahead and install this Adblock add-on.


Google Translate

This is especially useful for someone who is living in a foreign country. You might be thinking that English is an international language and most websites must have the option for English. This is partially true because some websites are not multi-lingual and even if they do, some of the times it sucks. Here it is: for Firefox, and for Chrome.

XPath Helper

It might be out of topic, but I found this useful for web application development. XPath Helper also gives a console where we can test Xpath command, and it also displays HTML element inspect and another couple of useful things.



VOIP with Skype from a Local phone

0 comments

If you are someone living far from family and being lazy to buy telephone cards, perhaps you are like me too, to end up using Skype for calling home. And then if you think 3G connection is not good enough to make phone call, then perhaps you have already known that Skype offered a VOIP feature.

So I've just recently tried the 'Call To Go' feature from Skype. Long story short, this feature makes it available to set up our own private VOIP number specified for our favorite contacts. And then to call that person we just need to dial the private VOIP number from a telephone. The VOIP number will appear as a local toll-free number. Other than that as a bonus, you do not have to get online in Skype in order to make a phone call.

The pro of this method, I don't have to say no more, is that you are going to have a phone call with better and stable quality. And then about the pricing, it has no different with how much if will cost if the call was made through Internet connection via Skype client. Of course to be able to make use of the toll-free, you might need a fixed line telephone. Maybe it is free as well if made from a mobile phone.

So below are the steps to setup the to-go number.


1. Login to Skype, and then under your profile, click Skype To Go.


2. To set up a new Skype To Go number, click on "Add a contact". If you have not set up any registered phone, at this point Skype will have you register one, which could be either a local phone or a mobile phone.


3. And then, fill in contact's name, country, type, and phone number or Skype ID. On the right side you are going to see a local phone number started with (315). In Singapore, this is a phone number format reserved for VOIP purpose.


4. You could also set up a PIN number if you wish to protect your Skype balance, especially when you have auto reload being set up.


5. To make the phone call by using your Skype credit, directly dial the number specified for the contact, and you phone number where you made the call from, will appear as the Caller ID.


*Unfortunately, Skype has not yet support all countries for this feature. Fortunately, Singapore is one of the country that has this feature ready.


How to Set to Always Open a Similar File with a Preferred Application in Mac OS X

0 comments

The Wrong Way to Do This

  1. Right click on the file
  2. Select "Open With", and then select "Other...", choose the application
Doing #1 and #2 will lead to always open rand-anthem.epub with Adobe Digital Editions, instead of setting to always open epub file with Adobe Digital Editions.



The RightWay to Do This
  1. Right click on the file, choose "Get Info"
  2. A left panel will show up.  Select "Open with:" and then check the specified application.
  3. Click on "Change All.."
  4. Click "Continue", and now you have a MAC OS which always open epub file with Adobe Digital Editions.
Why a blog post was made to explain this
Because the way to do this in MAC OS is ridiculously against the common sense.