[SOLVED]vector perpendecular to normal vector

Question

I am stuck vector related problem.

I need to find a perpendicular vector(V) of fixed lentgh say 20 to other Normal vector(N) whose lentgh is unknown only direction.

for N and V I know intersecting co-ordinates. all this is happening in 3D space

After finding the perpendicular vector (V) I need to rotate that around every 15 degree to make a circle.

I want to do the thing shown in Image.

Algorithm Image (Point Signatures: A New Representation for 3D Object Recognition)

Complete article is here

Edit I have calculated new values on the basis of normal vector being

(0.121881, 0.572628, -1.636642)

I found unit vectors

a = (0.070118, 0.941570, 0.329436)

e = (0.070118, 0.329436, -0.941570)

vector t = (0.069774, 0.839384, 0.037374)

normalized t = b1 = (0.082758, 0.70769, 0.03151)

b2 = (0.676719, -0.080131, 0.022358)

and after plotting all that stuff it look something like [i.stack.imgur.com/0PGM0.png] , the selected red line is the normal to the surface.

Answer 1

Let's say you have vector $\vec{n} = (x_n, y_n, z_n)$. (I like to use $\vec{v}$ for vectors, but $\hat{v}$ for unit vectors.)

The first basis vector is parallel to $\vec{n}$, but length 1. Because we only use this one to construct the two interesting basis vectors, I'll number this 3: $$\hat{e}_3 = (x_3, y_3, z_3) = \frac{\vec{n}}{\left\lVert\vec{n}\right\rVert}$$

We need an auxiliary vector which is not parallel to $\hat{e}_3$. If this auxiliary vector is also of unit length, the math in the following steps is simpler. There are many ways to construct one, but we need to be careful to not produce a vector too close to $\hat{e}_3$ (or its opposite!), or this approach will fail.

One interesting way to construct such $\hat{a}$ is to find out which two of the three components are largest in magnitude. Then, negate the largest in magnitude, and swap it with the second largest in magnitude. This yields an auxiliary vector at $70°$ to $90°$ angle to the basis vector, and keeps the vector length unchanged.

In pseudocode, this can be done as follows:

# Return an auxiliary vector, at 70 to 90 degree angle to
# the given vector, keeping length unchanged.
#
Function Auxiliary(x3, y3, z3):
    xm = abs(x3)
    ym = abs(y3)
    zm = abs(z3)

    If (xm >= ym), Then
        # |x3| >= |y3|
        If (ym >= zm), Then
            # |x3| >= |y3| >= |z3|
            xa =  y3
            ya = -x3
            za =  z3
        Else,
        If (xm >= zm), Then
            # |x3| >= |z3| > |y3|
            xa =  z3
            ya =  y3
            za = -x3
        Else,
            # |z3| > |x3| >= |y3|
            xa = -z3
            ya =  y3
            za =  x3
        End If
    Else,
        # |y| > |x|
        If (xm >= zm), Then
            # |y| > |x| >= |z|
            xa = -y3
            ya =  x3
            za =  z3
        Else,
        If (ym >= zm), Then
            # |y| >= |z| >= |x|, |y| > |x|
            xa =  x3
            ya =  z3
            za = -y3
        Else,
            # |z| > |y| > |x|
            xa =  x3
            ya = -z3
            za =  y3
        End If
    End If

    Return (xa, ya, za)
End Function

It does not actually matter how you construct $\hat{a}$, as long as it is not parallel to (or have a very small angle with) $\hat{e}_3$. The above is nice -- although it is very dense to read and maintain, hopefully it only needs to be written and tested thoroughly once! -- because it yields an "almost" perpendicular vector, no matter what the input vector, with just three absolute values, three comparisons, and assignments.

In any case, with $\hat{a}$ not parallel to $\hat{e}_3$ we can now easily construct a vector $\vec{t}$ perpendicular to $\hat{e}_3$: $$\vec{t} = \hat{a} - \hat{e}_3 \left ( \hat{a} \cdot \hat{e}_3 \right )$$ Because both vectors on the right side are of unit length, we don't need to divide by their lengths.

We have our first interesting basis vector if we normalize the perpendicular vector $\vec{t}$ to unit length: $$\hat{e}_1 = \frac{\vec{t}}{\left\lVert\vec{t}\right\rVert}$$

The final basis vector is simply a cross product of the two other unit basis vectors. Because the two are of unit length and perpendicular, the result will be perpendicular to both, and also of unit length: $$\hat{e}_2 = \hat{e}_3 \times \hat{e}_1$$

To generate $N$ points, $\vec{p}_1 \ldots \vec{p}_N$, at distance $r$ from $\vec{o}$, in a circle perpendicular to $\vec{n}$, use $$\vec{p}_i = \vec{o} + r \hat{e}_1 \cos\left(\frac{2 \pi i}{N}\right) + r \hat{e}_2 \sin\left(\frac{2 \pi i}{N}\right)$$ with either $i = 1\ldots N$ or $i = 0 \ldots N-1$.

Answer 2

@Nominal-Animal's answer is probably right, but I wanted to warn you:

If you want the formula that generates the perpendicular vector to be continuous (e.g. give perpendiculars that are close to each other for the original vectors that are close to each other), then there is no solution.

You can easily create solutions that have 2 "special" points where the continuous perpendicular function turns zero vector (which is not perpendicular to anything). You can patch these points with some other non-zero perpendicular vector.

There can be a solution with only one "special point". Again, it can be patched, but the function won't be continuous at that point.

The fully continuous mapping is impossible. See Hairy ball theorem - Application to computer graphics

An example solution that has 2 special points:

The cross product of any two non-zero and non-collinear vectors is non-zero and perpendicular to both of those vectors. Thus, just take the cross product of your normal vector with some other constant vector e.g. $(0,0,1)$.

$\vec{N}(x,y,z) \times (0,0,1) = \vec{P_1}(y,-x,0)$.

For rotated vectors you'd need another perpendicular vector:

$\vec{N}(x,y,z) \times \vec{P_1}(y,-x,0) = \vec{P_2}(xz, yz, -x^2-y^2)$.

And finally here is the formula for the rotated vectors.

$\vec{p}_i = \vec{o} + r \frac{\vec{P_1}}{|\vec{P_1}|} \cos\left(\frac{2 \pi i}{n}\right) + r \frac{\vec{P_2}}{\vec{P_2}} \sin\left(\frac{2 \pi i}{n}\right)$ where $n$ is the number of rotated vectors you want (n = 24 for the angle of 15 degrees between vectors); $i$ is the rotated vector index which goes from $1$ to $n-1$.

P.S. As I mentioned, this formula fails for 2 special points/directions. In particular, for the normal vectors that only have a z coordinate non-zero $(0,0,z)$, you'd need to provide some special result answer.