Vectors: GetLength() vs. GetLengthSquared()

There are a lot of situations where you need to get the length of a vector. For example, if you want to measure the distance between two objects. But there are also a lot of situations where you don’t need the actual length of the vector, because maybe you just want to find out which vector is the shortest. For example, if you want to determine which object – out of a group of objects – is closes to a given position; a common task if you deal with particle systems where particles have to interact with their closest neighbors.

Basics

As you probably know, the length of a vector can be determined using the function Vector::GetLength().

Vector v = Vector(RCO 1.0, RCO 2.0, RCO 3.0);
Real l = v.GetLength();

In the CINEMA 4D API, GetLength() is defined as follows:

// return the length of the vector
LReal	GetLength( void ) const
{
  return Sqrt( x*x + y*y + z*z );
}

This function is a 3D version of the Pythagorean theorem. It needs to calculate the square root to get the actual length. The problem with this is, the square root is rather slow to calculate.

So what if we just leave out the square root? We would then get the squared result. And that’s exactly what the function Vector::GetLengthSquared() does:

// return the length of the vector
LReal	GetLengthSquared( void ) const
{
  return x*x + y*y + z*z;
}

A comparitive benchmark

The following code performs a benchmark to compare the performance of Vector::GetLength() and Vector::GetLengthSquared(); and prints the results into the C4D console. Simply copy & paste it inside e.g. a command plugin:

// Allocate an array of 5 million vectors
const LONG count = 5000000;
Vector *v = GeAllocType(Vector, count);
if (!v) return FALSE;

// Some variables we need
Real r = RCO 0.0;
LONG i = 0;

// Fill the array with vector of random values
Random rnd;
rnd.Init(123);
LONG t = GeGetTimer();
for (i = 0; i < count; i++)
{
  v[i] = Vector(rnd.Get01(), rnd.Get01(), rnd.Get01());
}
GePrint("Filling Array: " + LongToString(GeGetTimer() - t) + " msec");

// Benchmark 1: Call GetLength() on each of the vectors
t = GeGetTimer();
for (i = 0; i < count; i++)
{
  r = v[i].GetLength();
}
LONG time1 = GeGetTimer() - t;
GePrint("GetLength(): " + LongToString(time1) + " msec");

// Benchmark 2: Call GetLengthSquared() on each of the vectors
t = GeGetTimer();
for (i = 0; i < count; i++)
{
  r = v[i].GetLengthSquared();
}
LONG time2 = GeGetTimer() - t;
GePrint("GetLengthSquared(): " + LongToString(time2) + " msec");
GePrint("Difference: " + LongToString(Abs(time1 - time2)) + " msec");
GeFree(v);

Practical application

Referring to the example mentioned at the beginning of this article, let’s iterate a flat hierarchy and find the object the is nearest to the position of a given reference object. This is done by iterating over the objects, getting the position of each object, subtracting that position from the reference position and then calculating the length (respectively the squared length) of the resulting distance vector. If the length is the shortest so far (or if we are still in the first iteration), then store it (for later comparison against the distances to the other objects) and also store a pointer to the object that gave the shortest length.

In addition to this, there is the optional parameter minDistance that can be used to filter out objects that are too near to the reference object. To be able to compare the minDistance to the measured distance between two objects, we simply square minDistance before use. One square is a lot faster to calculate than multiple square roots.

In the end, we will have a pointer that points to the object that is nearest to the reference position. We’ll return that pointer.

BaseObject* GetNearestObject(BaseObject* parent, BaseObject* ref, Real minDistance = RCO 0.0)
{
  if (!parent || !ref) return NULL;

  // Variables
  BaseObject* op = parent->GetDown();  // Get first child of parent
  BaseObject* result = NULL;
  Real distance = RCO 0.0;
  Real shortest = RCO 0.0;
  Real minDistanceSquared = minDistance * minDistance;  // Square the minimum distance
  Bool firstObject = TRUE;

  // Get global reference position
  Vector refpos = ref->GetMg().off;
  
  // Transform reference position to parent's local space
  refpos = refpos * !(parent->GetMg());

  // Iterate over all children of parent
  while (op)
  {
    // Measure squared distance between current op and refpos
    distance = (op->GetMl().off - refpos).GetLengthSquared();

   // If the squared distance is greator than or equals the minimum distance, and
   // if this is the first iteration or the shortest distance so far
    if (distance >= minDistanceSquared && (firstObject || distance < shortest))
    {
      // Memorize the current op
      result = op;

      // Memorize the distance
      shortest = distance;

      // Remember in the next iteration that it's not the first iteration anymore
      firstObject = FALSE;
    }

    // Continue with next object
    op = op->GetNext();
  }

  // Return the last memorized object
  return result;
}

A note about Python

Vector::GetLengthSquared() is also included in the CINEMA 4D Python API. For some reason, it does not provide any speed advantage. To check that, see the following script (copy & paste it into the Script Manager):

import random
import c4d

MAX_RANGE = 5000000

def bench_list(vectorlist):
    print "Benchmarking Vector::GetLength()..."
    
    count = len(vectorlist)

    # Start timer    
    t = c4d.GeGetTimer()

    # Benchmark GetLength()
    for v in range(0, count):
        r = vectorlist[v].GetLength()
        
    # Print out used time
    time1 = c4d.GeGetTimer() - t
    print str(time1) + " msec"
    
    print "Benchmarking Vector::GetLengthSquared()..."
    
    # Start timer    
    t = c4d.GeGetTimer()

    # Benchmark GetLengthSquared()
    for v in range(0, count):
        r = vectorlist[v].GetLengthSquared()
        
    # Print out used time
    time2 = c4d.GeGetTimer() - t
    print str(time2) + " msec"
    print "Difference: " + str(abs(time1 - time2)) + " msec"
    print " "
    
    
def fill_list(count):
    # Start timer    
    t = c4d.GeGetTimer()
    
    print "Filling array with " + str(count) + " vector elements."
    
    # Create & fill the array
    vectorlist = []
    random.seed(123)
    for i in range(0, count):
        vectorlist.append(c4d.Vector(random.random()))
        
    # Print out used time
    print str(c4d.GeGetTimer() - t) + " msec"
    
    return vectorlist
 

def benchmark(count):
    vectorlist = fill_list(count)
    bench_list(vectorlist)   
  

def main():
    benchmark(MAX_RANGE)


if __name__=='__main__':
    main()