TD 3 - B-splines/NURBS and ICP


(Luca Castelli Aleardi)


Votre opinion sur le cours: Votre opinion sur le TD:


Part I. B-splines and Nurbs

The goal of this section is to model curves and surfaces, via B-splines and NURBS.

Examples of Nurbs surfaces (control points are taken in a regular grid, with random y coordinate)

0. Getting started (a Processing frame for 2D and 3D rendering)

Files to download today

Here is the file to download (and extract to the /src folder of your Eclipse project):
  • geometry.zip: some classes for manipulating geometric objects (such as points, vectors and transformations in 2D).

For the computation and drawing of 2D curves:

  • Curve.java: abstract class defining main methods for computing the plot of the curve
  • DrawCurve.java: main drawing class, allowing to handle mouse events (adding, moving and deleting points).

For the computation and rendering of surfaces:

  • Surface.java: abstract class defining main methods for computing the plot of the a surface
  • DrawSurface.java: main drawing class, allowing to rotate the scene in 3D.
  • ArcBall.java: simple class allowing to rotate the 3D scene with mouse events.
  • Paraboloid.java: simple example of rendering an hyperbolic paraboloid

Java documentation

Here is the javaDoc concerning the packages and classes used today:


class drawCurve

class drawSurface
Class DrawCurve provides simple methods for drawing (points and segments), and handling mouse events (for adding/moving/deleting points).
Method setup() allows to select the preferred implementation of B-splines curves.
public void setup() {
	size(400,400); // size of the window
	// choose the scheme and curves to draw
	this.scheme=new Bezier(this, this.points);    
}

public void draw() {
	background(220);
	    
	if(points.isEmpty()) return; // no control points
	scheme.plotCurve(1./1000.);
}
Class DrawSurface provides simple methods for drawing surfaces in a 3D frame (using quad strips); it also provides a simple trackball (allowing to rotate the 3D scene with mouse events).
Method setup() allows to select the preferred implementation of the surface.
	public void setup() {
		  size(600,400,P3D);
		  ArcBall arcball = new ArcBall(this);
		  
		  //this.s=new Nurbs(this);
		  this.s=new Paraboloid(this);
	}

	public void draw() {
	  background(0);
	  this.lights();
		 
	  translate(width/2.f,height/2.f,-1*height/2.f);
	  this.strokeWeight(1);
	  stroke(150,150,150);
	  
	  this.s.plotSurface(0.01,  0.01);
	}





1. 3D with Processing


0 drawing surfaces with Processing: getting started

Class DrawSurface  allows to render a a surface in a 3D frame. You can choose your favourite implementation (of a parametric surface), by removing/adding comments in the method setup().
  • Test with class Paraboloid: this class extends class  Surface.

Remark: please observe that we have performed a scaling of the surface points, in order to obtain a better rendering of the 3D scene.
(take a look to method evaluate(u, v) of class Paraboloid)
Example: 3D rendering of an hyperbolic paraboloid of equations y=zu
The rendering is performed by Processing, using quad strips



Implement the computation of a Bézier patch.

1.1 Bézier patches (tensor product surfaces)

Re-use Bezier classes (from TD2) in order to design Bezier curves (coordinates must be computed in 3D), and then use the tensor product to compute the resulting surface (the Bézier patch)

You can also use the tensor product (compute separetely two curves)

1.2 Bézier patches (tensor product surfaces)


  • complete class BezierPatchDeCasteljau which extends class  Surface.
  • implement method Point_3 evaluate(double u, double v), which is required to plot the surface.


You can apply directly the De Casteljau algorithm:





where initial points are:

2. B-splines

You are asked to implement several types of B-splines: you can switch from a scheme to another using the key 's' in the
DrawSurface applet. You can also increase (or decrease) the degree k of the curve with keys '+' and '-' respectively.

2.1 Cubic B-Splines

Given a set of n points, we want to implement the cubic B-splines, with uniform knot vector [1, 2, 3, ...].
  • complete class CubicBSpline which extends class  Curve.
  • implement method Point_2 evaluate(double t).
  • implement method plotCurve(double dt) which draw the curve in the frame, by evaluating the curve with a given step.


2.2 General B-Splines

Given a set of n points, we want to implement the degree k B-splines (k between 2 and n), with uniform knot vector [1, 2, 3, ...].
  • complete class BSpline which extends class  Curve.
  • as before, implement methods Point_2 evaluate(double t) and method plotCurve(double dt).




3. Tensor product NURBS surfaces (optional: Bonus)


Implement the computation of a Nurbs surface.

3.1 Again on Tensor product surfaces

Re-use previous exercice 2 in order to design two plane curves (coordinates are computed in 2D), and then use the tensor product to compute the resulting surface
  • complete class Nurbs which extends class  Surface.
  • implement method Point_3 evaluate(double u, double v).
  • implement method plotSurface(double du, double dv) which perform the drawing of the surface in the 3D frame.
Example: computation of a Nurbs surface.
Points are taken on a regular grid in the xz plane. Heights are choosen at random.




Part II. Iterative closest point


The goal of this section is to implement the iterative closest point algorithm (using 3x3 matrices)

       

Two point clouds corresponding to a sphere
Point clouds corresponding to cylinder


1. Getting started (a Processing frame for rendering 3d point clouds)

Files to download for this section

Remark (important): please create a new Java project (e.g. TD3b) for this section, in order to avoid conflicts with the files used in the previous section.

Here are some files to download (and extract to the main folder of your Eclipse project):
  • OFF.zip: examples of points clouds.

Libraries to add (project /LIB):

  • Jcg.jar: library for the manipulation of 3d geometry

For the implementation of ICP:

  • src.zip: classes defining main methods for rendering point clouds and implementing ICP


TD6 documentation: instructions

Important: here is an interesting paper illustrating how to implement ICP (with both 3x3 matrices and quaternions).


1. Iterative closest point (with rotation matrices)

 

ICP with Matrices and SVD


Given two 3d point clouds P1 and P2 (class PointSet), we want to compute the rigid transformation that maps P2 to P1, by implementing the Iterative closest point method with rotation matrices.

Suggestion: in order to implement ICP, we suggest to you to follow the explanation given in this paper (section 3.1).







Initial point clouds
after 1 iteration
after 3 iterations
after 5 iterations


1.1 Rigid transformation for corresponded point clouds

  • complete methods getRotation(...) and getTranslation(...), for the case of two point clouds P and Q whose points are matching (so we can assume point q[i]=p[i]).

1.2 implement ICP

Now we want to solve the problem above (computing a rigid transformation), for two point clouds whose points are not matched.

  • modify methods getRotation(...) and getTranslation(...), for dealing with arbitrary point clouds P and Q (now we cannot assume point q[i]=p[i]).