Turtle geometry in 3D

Question

I'm undertaking a small project whereby I'm trying to recreate the educational programming language Logo.

For those who don't know it, Logo consists of a 'turtle' which starts at the (x, y) location (0, 0) and can then move forwards and backwards to draw lines. In addition, the turtle can turn to the right or left infinitely (I.E. the angle 'wraps' at 360 back to zero when turning clockwise, and has the same property in the counter-clockwise direction.)

Students can then use commands like FD to move the turtle forward, or RT to turn to the right. So, for example, the program FD 10 RT 90 FD 10 RT 90 FD 10 RT 90 FD 10 RT 90 would draw a square with sides of 10-units in length.

My turtle has x, y and angle properties, and when I supply d to specify the distance to travel, I can easily calculate the new values of x and y with the following:

old_x = x

old_y = y

r = angle * (pi / 180) # convert angle (in degrees) to radians

new_x = old_x + (d * cos(r))

new_y = old_y + (d * sin(r))

I then draw a line from (old_x, old_y) to (new_x, new_y). So far, so good. I'm able to move the turtle perfectly in two dimensions.

But, what I'd like to do now, is add UT and DT commands to my program, so that it is possible to move the turtle's nose up and down, so that we can now draw 3D shapes. For example, the program FD 10 UT 90 FD 10 UT 90 FD 10 UT 90 FD 10 UT 90 would still draw a square, only now it would standing vertically.

I know my graphics library (OpenGL) supports drawing lines in 3D, infact that's what I'm already doing, only I'm keeping the z dimension zero the whole time, and obviously I'll need to keep track of a second angle variable for up and down, but I've absolutely no idea of how to go about calculating the new x, y and z values given two angles.

Can anyone help? Many TIA.

Answer 1

You have to keep track of the orientation of the turtle nose in $3D$ using the two angles $\phi$ (horizontal) and $\theta$ (elevation angle from the horizontal)

The unit forward direction of the turtle is

$ N = \begin{bmatrix} \cos \theta \cos \phi \\ \cos \theta \sin \phi \\ \sin \theta \end{bmatrix} $

Let's assume that you start with the turtle in the $xy$ plane with its nose pointing in the positive $x$ axis direction, then the starting $\phi = 0$ and the starting $\theta = 0$

Using $RT \phi_1$ decrements $\phi$ by $\phi_1$ and $LT \phi_1$ increments $\phi$ by $\phi_1$. Similarly, $UT \theta_1$ increments $\theta$ by $\theta_1$ and $DT \theta_1$ decrements $\theta$ by $\theta_1$.

Then we moving forward, the new position is

$P_2 = P_1 + d N $

Answer 2

Angles quickly get difficult in higher dimensions, but there's a rather nice way around this.

Let's start by way of example in 2D. Here's the movement formula you gave: \begin{align*} x' &= x + d\cos r \\ y' &= y + d\sin r \end{align*} where $(x,y)$ is the point the turtle currently is and $(x',y')$ is the point the turtle is going to. (The primes are just part of the name -- there're not derivatives.) We can write this in vector notation: $$ \begin{bmatrix} x' \\ y'\end{bmatrix} = \begin{bmatrix} x \\ y\end{bmatrix} + d \begin{bmatrix} \cos r \\ \sin r\end{bmatrix}.$$ The vector $(\cos r, \sin r)$ is a unit vector, and in fact every unit vector can be written in this form (in many programming languages the function to do this is known as atan2). So, we can forget the angle completely and just assume we have a heading vector $\mathbf{u}$ that's a unit vector, and the update formula becomes $$ \mathbf{x'} = \mathbf{x} + d\mathbf{u}.$$ To implement RT and LT, it turns out that rather than needing to convert $\mathbf{u}$ back to an angle and adding an angle to it, we can rotate the vector itself. That is, supposing we want to rotate LT by $\theta$ radians, the update formula for the heading is $$ \mathbf{u'} = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}\mathbf{u}. $$ There's another piece of data we could consider, too, but it's derivable directly from $\mathbf{u}$, and that's the unit vector $\mathbf{v}$ ninety degrees counter-clockwise from $\mathbf{u}$. The vectors $\mathbf{u}$ and $\mathbf{v}$ form a coordinate system from the point of view of the turtle.

and you can derive the heading update formula by figuring out what the new heading would be inside this turtle coordinate system and converting it back into standard coordinates.

Going up to 3D, we can use these ideas very directly. Instead of this $\mathbf{u},\mathbf{v}$ turtle coordinate frame, we have a $\mathbf{u},\mathbf{v},\mathbf{w}$ turtle coordinate frame of three unit vectors, where $\mathbf{u}$ is the turtle's heading, $\mathbf{v}$ is directly to the left of the turtle (so, if the turtle were an airplane, it's pointing in the direction down the left wing), and $\mathbf{w}$ is pointing directly up from the turtle's point of view.

The $\mathbf{w}$ is the cross product of the other two, so it's not strictly necessary to keep around, but it also doesn't hurt to store it.

Given any 3D rotation written as a $3\times 3$ matrix $R$, the update formula for a coordinate frame is $$ \begin{bmatrix} & & \\ \mathbf{u'} & \mathbf{v'} & \mathbf{w'} \\ & & \end{bmatrix} = R \begin{bmatrix} & & \\ \mathbf{u} & \mathbf{v} & \mathbf{w} \\ & & \end{bmatrix} $$ where we are representing the coordinate frames as $3\times 3$ matrices themselves. The position update formula is still $\mathbf{x'} = \mathbf{x}+d\mathbf{u}$.

Here are two matrices for you. The first is for LT by $\theta$ radians (a.k.a. yaw): $$ \begin{bmatrix} & & \\ \mathbf{u'} & \mathbf{v'} & \mathbf{w'} \\ & & \end{bmatrix} = \begin{bmatrix} \cos\theta & -\sin\theta & 0\\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} & & \\ \mathbf{u} & \mathbf{v} & \mathbf{w} \\ & & \end{bmatrix} $$ And the second is for UT by $\theta$ radians (a.k.a. pitch): $$ \begin{bmatrix} & & \\ \mathbf{u'} & \mathbf{v'} & \mathbf{w'} \\ & & \end{bmatrix} = \begin{bmatrix} \cos\theta & 0 & -\sin\theta \\ 0 & 1 & 0 \\ \sin\theta & 0 & \cos\theta \end{bmatrix} \begin{bmatrix} & & \\ \mathbf{u} & \mathbf{v} & \mathbf{w} \\ & & \end{bmatrix} $$ You might also consider having commands to cause the turtle to roll around its heading.

To summarize, the "correct" notion of an angle in 3D is a $3\times 3$ matrix whose columns are orthogonal unit vectors and whose determinant is $1$ (the other possibility is $-1$, but having it be $1$ is what makes the vectors form a coordinate system satisfying the right-hand rule). This is also known as an element of the special orthogonal group $SO(3)$, if you want to look it up.

Others might suggest using quaternions, but both approaches are equivalent. Quaternions mostly just let you write this $3\times 3$ matrix using only four numbers rather than nine.

---

In the other answer, Potato suggests using Euler angles, but if you want all the commands to do rotations from the turtle's point of view this is not correct. Its RT and LT will always be with respect to the horizontal plane.

Answer 3

In my book

Edgar, Gerald A., Measure, topology, and fractal geometry, Undergraduate Texts in Mathematics. New York etc.: Springer-Verlag. ix, 230 p. DM 58.00/hbk (1990). ZBL0727.28003.

in Chapter 7 "Additional Topics" I propose a 3D turtle geometry. (This is in the First Edition of the book only. In the Second Edition, I included different additional topics.) In addition to the usual turns (yaw) and the turns you propose (pitch) there is also roll. Here is p. 196:

At the bottom is a code for a 3-dimensional dragon...