Vector Fun: dot-product

Today I want to give some information on the dot-product and provide it’s implementation for out Vector-type in F# (this will be trivial).

The dot-product will be very important for our Raytracer-project because of it’s many uses in analytic-geometry. You can for example decide very easy (see below) if two vectors are perpendicular, you can project vectors on others, give a nice representation of affine-subspaces (planes in 3D space) and a lot more with it.

Indeed if you only remember it’s basic-properties you can easily derive all mentioned above by yourself in case you forgot.

But before looking at those we have to give the definition: The dot-product of two vectors will be a scalar-value (a float-value). You compute it by summing the product of coordinates:

For vectors a = (a_{x}, a_{y}, a_{z}) and b = (b_{x}, b_{y}, b_{z}) we will define the dot-product to be

 a \cdot b = a_{x}b_{x} + a_{y}b_{y} + a_{z}b_{z}

this translate directly to the following F#-operation for our Vector3-struct:

    static member (<*>) (a : Vector3, b : Vector3) = a.X*b.X + a.Y*b.Y + a.Z*b.Z

Basic properties of the dot-product

1 – it’s Commutative

this just states that for vectors a and b we have

 a \cdot b = b \cdot a

Proof

There is not much to say – both multiplication and addition (for real numbers) are commutative so the sum of the products will be too.

Test case

    [< Test >]
    member test.``dot-product is symmetric``() =
        // ARRANGE
        let a = Vector.Create (-3.22, 2.25, -0.13)
        let b = Vector.Create (0.0, -6.7, 10.0)
        // ACT
        let prod1 = a <*> b
        let prod2 = b <*> a
        // ASSERT
        prod1 |> should equal prod2

2 – it’s linear in the first factor

For vectors a, b and c and a scalar r this says that

 a \cdot ( rb + c) = r (a \cdot b) + (a \cdot c)

Remark:

Because of the first property the same is true for the second component – so we can call it bilinear.

Proof:

A simple exercise in “algebra”:

 a \cdot ( rb + c) = a_{x} (r b_{x} + c_{x}) + a_{y} (r b_{y} + c_{y}) + a_{z} (r b_{z} + c_{z})  = r ( a_{x} b_{x} + a_{y} b_{y} + a_{z} b_{z}) + ( a_{x} c_{x} + a_{y} c_{y} + a_{z} c_{z})  = r (a \cdot b) + (a \cdot c)

Test case

    [< Test >]
    member test.``dot-product is linear for the first factor``() =
        // ARRANGE
        let a = Vector.Create (-3.22, 2.25, -0.13)
        let b = Vector.Create (0.0, -6.7, 10.0)
        let c = Vector.Create (12.4, -1.7, 3.15)
        let r = 0.22
        // ACT
        let prod1 = a <*> (r*b + c)
        let prod2 = r * (a <*> b) + (a <*> c)
        // ASSERT
        prod1 |> should equal prod2

Some Corollaries

Is one of the factors zero will the dot-product be zero

So is v a vector then  v \cdot 0 = 0 = 0 \cdot v (note: the zeroes left and right are vectors – the zero in the middle is a scalar Zwinkerndes Smiley )

Test case

    [< Test >]
    member test.``dot-product by a zero-vector will always be 0``() =
        // ARRANGE
        let v = Vector.Create (-3.22, 2.25, -0.13)
        let zero = Vector.Zero
        // ACT
        let prod1 = v <*> zero
        let prod2 = zero <*> v
        // ASSERT
        prod1 |> should equal 0.0
        prod2 |> should equal 0.0

Proof

Is almost to easy to bother writing down if we use the definition:

 (v_{x}, v_{y}, v_{z}) \cdot (0,0,0) = v_{x}*0 + v_{y}*0+v_{z}*0 = 0

but it follows from the properties above as well (I will put the arrows on top of vectors for now to make it more clear):

As  \vec{0} = 0 \vec{0} we have:  \vec{v} \cdot \vec{0} = 0 (\vec{v} \cdot \vec{0}) = 0 by the second property – using the first we see that this holds for zero as the first factor as well.

The dot-product of different base-vectors is zero

As a proof just use the definition of the dot-product

Test case

    [< Test >]
    member test.``dot-product of different base-vectors is zero``() =
        // Helper
        let pairs ls =
            let rec pairs' ls acc =
                let pairOne l ls =
                    ls |> List.map (fun l' -> (l, l'))
                match ls with
                | []     -> acc
                | l::ls' -> let acc' = acc@(pairOne l ls')
                            pairs' ls' acc'
            pairs' ls []
        // ARRANGE
        let baseV = [Vector.E1; Vector.E2; Vector.E3]
        // ACT
        let pairProds = baseV |> pairs |> List.map (fun (a,b) -> a <*> b)
        // ASSERT
        let check v = v |> should equal 0.0
        pairProds |> List.iter check

The Dot-product of a Vector with itself is the square of it’s length

 v \cdot v = { \left| v \right| }^{2}

Proof

for proof just use the definition (very easy) or

 (v_{x}, v_{y}, v_{z}) \cdot (v_{x}, v_{y}, v_{z}) = (v_{x} \vec{E_{1}} + v_{y} \vec{E_{2}} + v_{z} \vec{E_{3}}) \cdot (v_{x} \vec{E_{1}} + v_{y} \vec{E_{2}} + v_{z} \vec{E_{3}})

and using the bilinearity and the fact just seen

 = v_{x}^2 \vec{E_{1}} \cdot \vec{E_{1}} + v_{y}^2 \vec{E_{2}} \cdot \vec{E_{2}} + v_{z}^2 \vec{E_{3}} \cdot \vec{E_{3}}

as (using the definition again) the dot-product of a base-vector with itself is just 1 this yields the result.

Test case

    [< Test >]
    member test.``dot-product of a vector by itself is the square of it's length``() =
        // ARRANGE
        let v = Vector.Create (-3.22, 2.25, -0.13)
        let len2 = Vector.Len2 v
        // ACT
        let prod = v <*> v
        // ASSERT
        prod |> should equal len2

Two vectors are perpendicular iFF their dot-product is zero

Ok – this only holds if none of the vectors is zero so please note this!

Test case

    [< Test >]
    member test.``dot-product of perpendicular vectors is zero``() =
        // ARRANGE
        let a = Vector.Create (2.0, 1.0, 4.0)
        let b = Vector.Create (1.0, -1.0, -0.25)
        // ACT
        let prod1 = a <*> b
        let prod2 = b <*> a
        // ASSERT
        prod1 |> should equal 0.0
        prod2 |> should equal 0.0

Proof

Depending on what you take as given this is hard or rather easy. I will take the same approach as the Wikipedia article and invoke the power of the law of cosines – of course you should know why this holds. Well I aside from the proofs mentioned in the wiki-article I immediate think of one using complex analysis (well it’s getting worse Zwinkerndes Smiley ) and one using the dot-product (doh – this one would use just what we want to proof) – so be beware of this.

You can get away with our approach if you look at the geometric definition of perpendicular and use the fact that the base-vectors are. Then you can find similar vectors on the axis (for which the dot-product will be zero) and you can use the fact that there is a matrix transforming your vectors to those similar. Using the definition of matrix-multiplication by forming the dot-product of it’s columns with your vector as the components of the final result will finally yield a proof that does not need the law of cosines but a lot of linear algebra …)

Having vectors a and b we are interested in the angle  \alpha between them. Together with the vector c = b-a those form a triangle like this:

KosineLaw

The law of cosines states that (using the square of length law we’ve seen right now):

 c \cdot c = a \cdot a + b \cdot b-2 \left| a \right| \left| b \right| cos( \alpha ) .

As c = b-a the left side is  (b-a) \cdot (b-a) = b \cdot b + a \cdot a-2 b \cdot a and cosine-law reduces to

 a \cdot b = \left| a \right| \left| b \right| cos( \alpha )

Now as both vectors have length greater 0 the left side will be zero IFF the cosine on the right is zero and this holds IFF the angle is 90° or 270° so the vectors are perpendicular.

Nice one huh?

Ok I think this is enough for now – next time we will start etching out a very simple ray-tracer by explaining the algorithm and rendering the shape of a 3D-sphere…