Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

3D point rotation algorithm

I'm currently working on a JavaScript project which involves 3D point rotation. Using simple trigonometry, I have sketched my own 3D point rotation algorithm, but I have to deal with a huge amount of data (+300 000 points) and my function slows down the runtime substantially (the FPS rate drops from 60 to 12).

I'm looking for another 3D point rotation ALGORITHM which...

  1. rotates points around origin by X, Y and Z axes' angles (PITCH, YAW and ROLL)
  2. has a quite good efficiency (don't worry about this too much, it will always be faster than mine)
  3. is written in JavaScript, C-like code or pseudo-code

Any help will be greatly appreciated :)

Context: 3D point cloud renderer (I want every point to be rotated)

like image 777
BrainOverflow Avatar asked Dec 02 '15 19:12

BrainOverflow


People also ask

How do you rotate a 3D point cloud?

2)Rotation: 3D point clouds use a 3x3 rotation matrix for rotation. This is done by multiplying the point cloud with the rotation matrix. To make this task more user friendly, open3D has a utility to generate this rotation matrix by providing the angle by which x,y,z axis are to be rotated by.

What are the 4 types of rotations?

The balance factor is calculated by subtracting the heights of the right subtree from the left subtree of a particular node. There are four types of Rotations in the AVL tree: Left rotation, Right rotation, Left-Right rotation, Right-Left rotation.


1 Answers

A rotated vector can be described as a product of a rotation matrix with that vector. The German Wikipedia page on pitch, roll and yaw describes the rotation matrix for given Euler rotation angles.

With that information, the rotation of all points with the same angles can be written as JavaScript function, where the points array is global:

function rotate(pitch, roll, yaw) {
    var cosa = Math.cos(yaw);
    var sina = Math.sin(yaw);

    var cosb = Math.cos(pitch);
    var sinb = Math.sin(pitch);

    var cosc = Math.cos(roll);
    var sinc = Math.sin(roll);

    var Axx = cosa*cosb;
    var Axy = cosa*sinb*sinc - sina*cosc;
    var Axz = cosa*sinb*cosc + sina*sinc;

    var Ayx = sina*cosb;
    var Ayy = sina*sinb*sinc + cosa*cosc;
    var Ayz = sina*sinb*cosc - cosa*sinc;

    var Azx = -sinb;
    var Azy = cosb*sinc;
    var Azz = cosb*cosc;

    for (var i = 0; i < points.length; i++) {
        var px = points[i].x;
        var py = points[i].y;
        var pz = points[i].z;

        points[i].x = Axx*px + Axy*py + Axz*pz;
        points[i].y = Ayx*px + Ayy*py + Ayz*pz;
        points[i].z = Azx*px + Azy*py + Azz*pz;
    }
}

Most of that is setting up the rotation matrix as described in the article. The last three lines inside the loop are the matrix multiplication. You have made a point of not wanting to get into matrices, but that's hardly intimidating, is it? Sooner or later you will encounter more matrices and you should be prepared to deal with them. The stuff you need – multiplication, mainly – is simple. The more complicated stuff like inverting matrices is not needed for your requirements.

Anyway, that performs reasonably fast for 300,000 points. I was able to rotate a point cloud of that size and render it on a 1000px &times 1000px canvas in about 10ms.

like image 106
M Oehm Avatar answered Oct 12 '22 23:10

M Oehm