Posted on

Pixel perfect object movement

A standard feature of all 3D scene editors are object transform manipulation tools, i.e. translate, rotate and scale. Whilst there are articles that describe the behavior I couldn’t find a specific article on the implementation details so thought I’d write up the algorithm I use.

The Algorithm

The steps for the translation tool are as follows:

  • Axis selection
  • Movement plane selection
  • Ray / movement plane intersection
  • Move the objects

Axis selection

  • Obtain a list of visible objects (i.e. objects that have survived frustum and occlusion culling)
  • Next, with the perspective and view transforms applied I un-project the mouse position at the near and far clip planes to obtain a line segment that originates at the camera’s position and terminates at the far clip plane, we’ll call this the pick ray (even though it’s a line segment)
  • For each selected object cycle through each of its axis, form a bounding box that bounds the axis line (the length of the axis line is equal to the object bounding sphere’s diameter)
  • Perform a line / box intersection test between the pick ray and axis bounding box, this results in an intersection point. NB. For this test you can either translate the pick ray into object’s local coordinate system by multiplying it by the object’s inverse local-to-world transform or transform the axis bounding box into the world coordinate system by multiplying it by the object’s transform
  • Calculate the distance between the intersection point (in world coordinates) and the camera’s position
  • The intersection that is closest to the camera wins giving us both our object and selected axis

Movement Plane selection

Now we have our picked object and selected axis we can select an appropriate plane to ground the object movement.

  • We consider just 3 planes, i.e. the XY, XZ and YZ planes. The object’s bounding sphere origin will be coplanar with these three planes or in other words, the plane distance from the object’s local coordinate system will be zero
  • An axis lies on 2 of the 3 planes, so the X axis lies on the XY and XZ planes, the Y axis on the XY and YZ and the Z on the XZ and ZY
  • We take the two planes on which our axis line sits
  • I then translate these 2 planes (under consideration) into the world coordinate system (by multiplying each plane’s normal by the object’s local-to-world transform, setting the w component to zero as we don’t want to translate the normal as it’s a vector not a point) and setting the plane’s distance to be the dot product of the plane’s normal and the object’s bounding sphere’s center (expressed in world coordinates)
  • To decide which plane to use we need to select the most visible plane. To do this calculate the angle between the normalised pick ray and plane normal for each of the 2 planes selecting the plane that subtends the greatest angle when subtracted from pi / 2 (as and angle of 90 degrees indicates that the pick ray lies on the plane and so isn’t a good candidate for intersection testing below).

Pick ray / movement plane intersection

We now have our object, constraint axis and movement plane so now we can move the object.

  • Perform a intersection test using our pick ray and movement plane, assuming you are in world coordinates this is going to be used to determine the movement delta to be applied
  • Calculate the movement delta by subtracting the previous intersection point (from a previous frame) with this frame’s intersection point
  • Constrain the delta to the movement axis. To obtain the constraining axis basis vector I multiply the vector again by the object’s inverse local-to-world transform (again with w = 0 as the axis is a vector) and then multiply the delta by the vector
  • Move the objects by adding the delta to their positions

Alternative approaches

There are alternatives for each of the above steps. For instance, for the initial object / axis selection we could have performed this test in screen space by drawing the object’s axis boxes in a unique color. We can then obtain the color under the mouse cursor and use that to index into an array to obtain the selected object.