Orientation Encoded as Quaternions

Use quaternions through the DLL, in the Network protocol, and to interface the Refresh/Renderer.

Benefits:
Cleaner design, architecture open for future improvements/added effects.

Replacing the current handling of rotations and orientation with a new representation will enforce removal of all legacy, and streamline the handling. The current handling of rotations and orientations in Q2 is really messy, stricken with legacy from DOOM and Q1. Remember rotating brushes, and movement directions set to either XY plane or plus/minus Z.
Quaternions are an efficient representation for network transmission, and can be expanded to a matrix fast.
Quaternions would allow for arbitrary rotations as axis and angular velocity, and later for interpolation of entity orientations between svc_frame.
Quaternions would allow for smooth spherical interpolation of player POV changes in client side prediction. They will also allow for improved camera mods.
Game DLLs using quaternions internally do not have to pay the performance penalty of converting the quaternion to a matrix and decomposing the matrix into Euler angles prior to edict/entity state update for network transmission.

The current Q2 description of model orientation and view orientation makes implementation of full 6 DoF very difficult, and raises client side prediction issues, too.

Problems:

The current handling is messy. Using quaternions will affect nearly every part of the player/client and entity handling with respect to movement and rotation, and collision response.
The network protocol will have to change in several parts.
Conversion to matrices and angular displacement is reasonably fast, but there might be performance penalties, maybe even with Lookup Tables.
Quaternions, while elegant and efficient, are still not known to every aspiring coder. Mod authors might suffer.

Feasibility: Corinne Yu of ION Strom claimed to have worked quaternion support into their copy of the licensed Q2 codebase earlier this year.

There will not be a problem interfacing the renderer. >From the original exchange with John Carmack:

The renderer now takes matrix values instead of
angles for more flexibility and less confusion.
I am considering a quaternion representation for the
game and network, but its not at the top of my 
priority list.

Implementation 1 - Minimal:
If quaternions were only introduced in the network protocol, the DLL could be changed later by anybody. Conversion of quaternions to matrix and (if needed) angles could be done in the Q2 client.

Add a new data type:

   In: q_shared.h:

   tyepdef vec_t    quats_t;     // Maybe fixed?
   typedef quats_t  quat_t[4];

Change entity_state_t, player_state_t, pmove_state_t and usercmd_t to use a quaternion wherever a triple of short/float is used for angles.

Change gi.Pmove appropriately.

Rework svc_playerinfo network command:

          short delta_angles[3]
          vec3_t viewangles
          vec3_t kick_angles
          vec3_t gunangles

Rework svc_packetentities/svc_spawnbaseline network command:

          byte angles[3];

Implications of byte orient[4] in terms of angle resolution, and isotropy/distribution to be resolved. Might require normalization to unit quaternion when converted back to float. This is already a bulk of work. Implementation 2 - Maximal: This is a sketchy and incomplete list, that adds to the minimal requirements listed above. This list can't say anything about server or client internals. It deals with network, MAP/BSP and Game DLL in parts, but not completely.

Add utility functions for quaternions. A module implementing the following could be provided on demand:

     #define QuatClear( q )\
     #define QuatSet( q, s, vx, vy, vz )\
     void QuatAdd( quat_t ql, quat_t qr, quat_t result );
     void QuatSub( quat_t ql, quat_t qr, quat_t result );
     void QuatCopy( quat_t src, quat_t dest );
     void QuatInverse( quat_t q );
     void QuatConjugate( quat_t q );
     void QuatScale( quat_t q, quats_t scale, quat_t result );
     vec_t QuatDotProduct( quat_t ql, quat_t qr );
     quats_t QuatLength( quat_t q );
     quats_t QuatNormalize( quat_t q );
     void QuatMul_HOWELL ( quat_t ql, quat_t qr, quat_t result );
     void QuatMul_HOWELL2( quat_t ql, quat_t qr, quat_t result );
     void QuatMul_SALAMIN( quat_t ql, quat_t qr, quat_t result );
     void QuatMul_LANDER ( quat_t ql, quat_t    qr, quat_t result );
     void QuatDiv( quat_t nom, quat_t denom, quat_t result );
     void QuatSqr( quat_t q, quat_t result );
     void QuatSqrt( quat_t q, quat_t result );

     /** Quaternion rotated UP vector, 6 MUL. */
     void Quat2VectorZ( quat_t q, vec3_t v );

     /** Quaternion classification, to major axises. */
     vector_type_t QuatClassify( quat_t q );

     /** Converts a quaternion to angular displacement. */
     void Quat2Axis ( quat_t q, axis_t* result );

     /** Converts quaternion to OpenGL::glRotate parameters. */
     void Quat2glRot( quat_t q, axis_t* glresult );

     void Axis2Quat ( axis_t* ad, quat_t result );
     void QuatScaleAngle( quat_t quat, float scale );
     void QuatSetAngle( quat_t quat, float angle );

     /** Conversion to matrix, 10 MUL */
     void Quat2Matrix_SALAMIN( quat_t q, mat_t result );
     void Quat2Matrix_WATT( quat_t q, mat_t result );
     void Quat2Matrix_BOBIC( quat_t     q, mat_t m );

     void Matrix2Quat_WATT( mat_t m, quat_t result );
     void Matrix2Quat_BOBIC( mat_t m, quat_t result );
     
     void EulerPYR2Quat( vec3_t angles, quat_t quat);
     void EulerPYR2Quat_LANDER( vec3_t angles, quat_t q );

     /** Convert two vectors to a quaternion. */
     void Vectors2Quat( vec3_t v1, vec3_t v2, quat_t result );

     /** Debug, dump a quaternion by components. */
     void DumpQuat( quat_t q );

     /** Quaternion lerp/slerp, q/-q, and normalizing. */
     void QuatLerp_WATT  ( quat_t p, quat_t q, float t, quat_t qt );
     void QuatLerp_BOBIC ( quat_t p, quat_t q, float t, quat_t qt );
     void QuatLerpNorm ( quat_t p, quat_t q, float t, quat_t    qt );
     void QuatSlerp_WATT  ( quat_t p, quat_t q, float t, quat_t qt );
     void QuatSlerp_BOBIC ( quat_t p, quat_t q, float t, quat_t qt );



     /** Quaternion Lerping, preset, Iterator,
          fast linearly interpolated renormalization. */
     typedef struct lerp_quat_t;
     qboolean QuatLerpInit( quat_t p, quat_t q, int steps, lerp_quat_t* desc );
     qboolean QuatLerpIter( lerp_quat_t* desc, quat_t result );

     /** Quaternion Slerping with preset and Iterator. */
     typedef struct slerp_quat_t;
     qboolean QuatSlerpInit( quat_t p, quat_t q, int steps, slerp_quat_t* desc );
     qboolean QuatSlerpIter( slerp_quat_t* desc, quat_t result );

The utility functions above relate to angular displacement and matrix data types, modules which could also be provided. Q2 does not have a globally visible matrix type.

Review the current handling of rotation and orientation:
- Global and Entity parameters, e.g. in p_view.c::SV_CalcRoll/p_view.c::SV_CalcViewOffset
```
  
          sv_rollangle
          sv_rollspeed
          run_pitch
          run_roll 
          bob_pitch
          bob_roll
          v_dmg_roll
          v_dmg_pitch
        
```
  There are also view pitching time parameters, viewpoint offsets, bob_up shift, and more involved. Per entity, ideal_yaw and yaw_speed is used to handle turns towards a target. There are also angular velocities, and rotational friction.
- Q2 Client left/right/lookup/lookdown handling, into clc_move and usercmd_t.angles.
- ClientThink call of gi.Pmove
- Angles stored in
```
         self->client->resp.cmd_angles
         self->client->pm.delta_angles
         self->client->pm.viewangles
         self->client->v_angle
         self->client->ps.viewangles
         self->client->ps.kick_angles
         self->client->ps.gunangles

         self->s.angles                // server visible

         self->avelocity               // these are not
         self->move_angles
         self->yaw_speed
         self->ideal_yaw

         self->angle                   // unused, Q1/QE3 leftover
       
```
- Q2 client interpolation/smoothing of kick angles between scv_frame events
- player spawning, p_client.c::SelectSpawnPoint
- player teleporting, g_misc.c::teleporter_touch
- dead player, p_view.c::SV_CalcViewOffset
- Player Intermission View, level_locals_t.intermission_angle
- Gun Bobbing, p_view.c::SV_CalcGunOffset.

Make sure that spawn angles are treated accordingly. To be comptabile, a new spawn line could be added in map files; spawn parameters there make it into BSP files:

   {
        "classname" "info_player_deathmatch"
        "origin" "56 -736 168"
        "angle" "0"              
        "angles" "0" "42" "22"
   }
  

   In g_spawn.c:

   // change this to handle 3 angles if available
   case F_ANGLEHACK:
        v = atof(value);
        ((float *)(b+f->ofs))[0] = 0;
        ((float *)(b+f->ofs))[1] = v;
        ((float *)(b+f->ofs))[2] = 0;
        break;

Change handling of sky rotation:
```
    In: g_local.h::spawn_temp_t

    quat_t    skyaxis;
       
    In: g_spawn.c::SP_worldspawn

    gi.configstring 
             ( CS_SKYAXIS, 
               va("%f %f %f %f",
                st.skyaxis[0], 
                st.skyaxis[1], 
                st.skyaxis[2],
                st.skyaxis[3] ) );
    
```
For now, this would simply encode the orientation as a quaternion. The Q2 Client could respond to changes (submitted as config strings) during a game by spherically interpolating between orientations, resuming the st.skyrotate constant rotation when the new orientation is reached. Updates of the CS_SKYROTATE configstring durign game should also be possible.
This is a minimal extension of the API offering for runtime sky rotation changes.

This is missing handling of rotational friction, rotation in collision response, angles used in monster AI for movement/targetting, and probably a load of other issues. In summary, the implementation would be a major change, and could scarcely be considered an evolutinary change within the DLL.

Related Proposals:
A reworked client side prediction of player POV movements, and/or a reworked client side interpolation/extrapolation of entity updates would be affected by introducing quaternions to the network protocol.
The alternative of using an OpenGL::glRotate axis/angle representation, which also uses four numbers for three degrees of freedom, has not been proposed formally. It shares most of the problems, while being less generic.
Some details depend on when the client handles updates transfered by configstring changes.

Submitted 980321, revised 980328, revised 980420, comments to Bernd Kreimeier.