Gpu Interpolation Pc

GPU-Accelerated Point Cloud Interpolation Bo Schwarzstein February 6, 2009

1

Solution

Assume there is a triangle T containes 3 vertrices R1 , R2 , R3 ∈ V , with a scalar value q(xi , yi ), i = 1, 2, 3 on each vertex. And we want to get interpolated value qin on a point (xin , yin ) in the convex hull. This form a linear interpolation function qin (x, y) = q1 φ1 (x, y) + q2 φ2 (x, y) + q3 φ3 (x, y).

(1)

The φi (x, y) = Ai /A is the area ratio, A1 is the area of triangle XR2 R3 . It’s very clear that there are also 3 condition, φ1 (x, y) + φ2 (x, y) + φ3 (x, y) = 1 x1 φ1 (x, y) + x2 φ2 (x, y) + x3 φ3 (x, y) = x y1 φ1 (x, y) + y2 φ2 (x, y) + y3 φ3 (x, y) = y. We re-write it as matrix form below 

1  x1 y1

1 x2 y2

    1 φ1 1 x3   φ2  =  x  . φ3 y3 y

(2) (3) (4)

(5)

The quadratic error basis function is f (x, y) = aφ1 φ2 + bφ2 φ3 + cφ3 φ1 .

(6)

Let Sj ∈ V, j = 1, . . . , m be the next m donor mesh points that are closest to X. Let φi (j) represent the value of φi at the data point Sj . Define a matrix   φ1 (1)φ2 (1) φ2 (1)φ3 (1) φ3 (1)φ1 (1)  φ1 (2)φ2 (2) φ2 (2)φ3 (2) φ3 (2)φ1 (2)    B= (7)  .. .. ..   . . . φ1 (m)φ2 (m) φ2 (m)φ3 (m) φ3 (m)φ1 (m) To get the coefficients we invert a 3 × 3 system, B T Ba = B T w

(8)

where a = (a, b, c)T and    w= 

q(1) − qlin (1) q(2) − qlin (2) .. .

    

(9)

q(m) − qlin (m) It’s very easy to get solutions in 3D case, q(x, y, z) = qlin (x, y, z) + f (x, y, z) and qlin (x, y, z) =

4 X i=1

1

qi φi (x, y, z)

(10)

(11)

Let’s back to (2) and (3), inverse this matrix would get the φi , i = 1, . . . , 4,      1 φ1 1 1 1 1  x1 x2 x3 x4   φ2   x        y1 y2 y3 y4   φ3  =  y  . z φ4 z1 z2 z3 z4

(12)

The quadratic error is f (x, y, z) = aφ1 φ2 + bφ1 φ3 + cφ1 φ4 + dφ2 φ3 + eφ2 φ4 + f φ3 φ4 .

(13)

The X is in a terahedron T , not planar triangle. Similar the (7) we can get 3D version of this linear system, C T Ca = C T w (14)   φ1 (1)φ2 (1) φ2 (1)φ3 (1) φ3 (1)φ1 (1) φ2 (1)φ3 (1) φ2 (1)φ4 (1) φ3 (1)φ4 (1)  φ1 (2)φ2 (2) φ (2)φ (2) φ φ2 (1)φ3 (1) φ2 (1)φ4 (1) φ3 (1)φ4 (1)  2 3 3 (2)φ1 (2)   (15) C= , .. .. ..   . . . φ1 (m)φ2 (m) φ2 (m)φ3 (m) φ3 (m)φ1 (m) φ2 (1)φ3 (1) φ2 (1)φ4 (1) φ3 (1)φ4 (1) after inverse the C T C we can easily obain the a. Third order and fourth order requires inverse 16 × 16 and 32 × 32 linear system.

2

Implementation

Current NVIDIA CUDA CUBLAS library has complete linear algebra support from BLAS1 to BLAS3. It’s high efficient to operate matrix and vector in parallel on GPU now, so nearly the all work could be mapped onto GPU.

2