Cube equation and bitwise operators

510 Views Asked by At

I would like some help to understand that answer (copy from here Simplest equation for drawing a cube based on its center and/or other vertices)

A cube (the one with sides parallel to coordinate axes) centered at the point $P=(x_0,y_0,z_0)$ of "radius" $r$ (and edge length $d=2r$) has vertices $V_n=(x_0\pm r,y_0\pm r,z_0\pm r)$, which could be enumerated for $0\leq n\leq 7$ using the bitwise [AND][1] function (represented as the binary operation '&' familiar in C-like programming languages) as $$ V_n=(x_0+(-1)^{n\&1}r,y_0+(-1)^{n\&2}r,z_0+(-1)^{n\&4}r). $$ The number of edges between two vertices $V_j,V_k$ would then be the bit weight of [XOR][2]$(j,k)=j$^$k$, which is also known as the [hamming distance][3]. You could emulate cube rotation by making the opposite/inverse rotation in your perspective.

As column vectors, you could write $$ P=\left[\begin{matrix}x_0\\y_0\\z_0\end{matrix}\right],\quad R_n=r\left[\begin{matrix}\pm1\\\pm1\\\pm1\end{matrix}\right] =r\left[\begin{matrix}(-1)^{n\&1}\\(-1)^{n\&2}\\(-1)^{n\&4}\end{matrix}\right],\quad V_n=P+R_n $$ where $R_n$ are the radial vectors from the center $P$ to each vertex $V_n$. This would make it easier to rotate your cube. You'd just need a rotation matrix $M$, i.e. an [orthogonal][4] matrix (which means that its transpose equals its inverse: $M^T=M^{-1}$) with determinant $+1$ (also called special orthogonal), and then $V_n=P+M\cdot R_n$ would give you the rotated vertices.

To rotate it about an arbitrary axis, you would need a special orthogonal matrix $Q$ (for [change of basis][5]) with a unit vector parallel to the axis of rotation in say the $3^\text{rd}$ column (and the other two columns containing perpendicular unit vectors satisfying the [right-hand rule][6]), and a rotation matrix such as this, which rotates the $xy$-plane about the $z$-axis: $$ S= \left[ \begin{matrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{matrix} \right]. $$ Then you could take $M=QSQ^T$ (cf. [3D graphics approach][7]). Another excellent method for generating rotations, recommended by @J.M. and which you may prefer, uses [Rodrigues' rotation formula][8].

The modern computer graphics approach is usually a bit different than the [matrix][9] math of 3D linear transformations, because it uses [perspective projection][10], which uses a $4\times4$ matrix.

Since you mention OpenGL, for a cube you might want to look some place like [here][11] or [here][12].

Why do I need to use bitwise AND operators to enumerate vertices? Does someone can help me to understand its use? Some resources (pdf or website or book) that can help me would be nice too, didn't find anythings on google.

Thank you

1

There are 1 best solutions below

2
On

The idea behind the bitwise AND trick is that the bit patterns of the integers from $0$ to $7$ cover all possible combinations of three bits. By taking advantage of the fact that $(-1)^0=1$ and $(-1)^1=-1$, you can use them to generate the eight combinations of $\pm r$ that you need to produce all of the cube’s vertices. That is, the ones bit of $n$ tells you whether to take $+r$ or $-r$ along the $x$-axis, the twos bit controls the $y$-axis and the fours bit controls the $z$-axis.

Unfortunately, as presented here, this trick doesn’t quite work: n&1 is fine, since that produces either 000 or 001, but the other two bitwise AND expressions result in a power of two, and $-1$ raised to any power of two is $1$. Adding a right shift so that the bit that’s being tested ends up in the ones place will fix this bug. Using n>>m to represent a right-shift of $n$ by $m$ bits, we should really have something like $$V_n=(x_0+(-1)^{(n>>0)\&1}r,y_0+(-1)^{(n>>1)\&1}r,z_0+(-1)^{(n>>2)\&1}r).$$

On the other hand, right-shifting amounts to dividing by a power of two, and we just need an even or odd exponent for $-1$, so masking off the other bits is unnecessary. This leads to another way of expressing the same thing without using any bitwise operations at all: $$V_n=(x_0+(-1)^{\lfloor n/1\rfloor}r,y_0+(-1)^{\lfloor n/2\rfloor}r,z_0+(-1)^{\lfloor n/4\rfloor}r).$$