src/object/objectsort.cpp

   1 /*
   2  * $Logfile: /Freespace2/code/Object/ObjectSort.cpp $
   3  * $Revision$
   4  * $Date$
   5  * $Author$
   6  *
   7  * Sorting code for objects.
   8  *
   9  * $Log$
  10  * Revision 1.1  2002/05/03 03:28:10  root
  11  * Initial revision
  12  *
  13  *
  14  * 12    8/30/99 5:01p Dave
  15  * Made d3d do less state changing in the nebula. Use new chat server for
  16  * PXO.
  17  *
  18  * 11    3/31/99 8:24p Dave
  19  * Beefed up all kinds of stuff, incluging beam weapons, nebula effects
  20  * and background nebulae. Added per-ship non-dimming pixel colors.
  21  *
  22  * 10    2/08/99 5:07p Dave
  23  * FS2 chat server support. FS2 specific validated missions.
  24  *
  25  * 9     12/10/98 1:25p Dan
  26  * Fixed fogging in fred.
  27  *
  28  * 8     12/10/98 11:16a Dan
  29  * Fixed problem where Fred tries to fog objects (which it can't because
  30  * it runs in the software renderer).
  31  *
  32  * 7     12/09/98 7:34p Dave
  33  * Cleanup up nebula effect. Tweaked many values.
  34  *
  35  * 6     12/08/98 9:36a Dave
  36  * Almost done nebula effect for D3D. Looks 85% as good as Glide.
  37  *
  38  * 5     12/07/98 5:51p Dave
  39  * Finally got d3d fog working! Now we just need to tweak values.
  40  *
  41  * 4     12/06/98 6:53p Dave
  42  *
  43  * 3     12/06/98 2:36p Dave
  44  * Drastically improved nebula fogging.
  45  *
  46  * 2     10/07/98 10:53a Dave
  47  * Initial checkin.
  48  *
  49  * 1     10/07/98 10:50a Dave
  50  *
  51  * 39    3/12/98 1:24p Mike
  52  * When weapons linked, increase firing delay.
  53  * Free up weapon slots for AI ships, if necessary.
  54  * Backside render shield effect.
  55  * Remove shield hit triangle if offscreen.
  56  *
  57  * 38    3/10/98 4:19p John
  58  * Cleaned up graphics lib.  Took out most unused gr functions.   Made D3D
  59  * & Glide have popups and print screen.  Took out all >8bpp software
  60  * support.  Made Fred zbuffer.  Made zbuffer allocate dynamically to
  61  * support Fred.  Made zbuffering key off of functions rather than one
  62  * global variable.
  63  *
  64  * 37    2/13/98 2:48p Lawrance
  65  * Don't modify max_z position for shockwaves
  66  *
  67  * 36    1/15/98 2:16p John
  68  * Made bitmaps zbuffer at center minus radius.
  69  * Made fireballs sort after objects they are around.
  70  *
  71  * 35    10/24/97 7:53p John
  72  * added new code to detect if object is in view cone to fix clipping
  73  * problems once and for all.
  74  *
  75  * 34    9/09/97 4:52p John
  76  * Almost done ship warp in code
  77  *
  78  * 33    8/05/97 1:46p Mike
  79  * Comment out code that shows spheres where wingmen should be.
  80  *
  81  * 32    7/16/97 5:51p Lawrance
  82  * make shockwaves translucent
  83  *
  84  * 31    6/30/97 1:58p John
  85  * made obj_render_all only sort objects in view cone.  Made physics_pause
  86  * pause movement.
  87  *
  88  * 30    6/27/97 4:44p John
  89  * changed sorting to be faster and sort by the real z depth (not the
  90  * rotated z) in preparation for speeding up collision detection by using
  91  * this.
  92  *
  93  * 29    6/24/97 6:22p John
  94  * added detail flags.
  95  * sped up motion debris system a bit.
  96  *
  97  * 28    6/20/97 4:54p John
  98  * added detail levels.  Started adding some code framework to optimize
  99  * many objects.
 100  *
 101  * 27    6/19/97 6:21p John
 102  * optimized object sorting.
 103  *
 104  * 26    5/12/97 12:27p John
 105  * Restructured Graphics Library to add support for multiple renderers.
 106  *
 107  * 25    5/02/97 10:57a John
 108  * moved non-ships zcheck out by radius.
 109  *
 110  * 24    5/02/97 10:56a John
 111  * put back in code that draws smaller objects that are within a larger
 112  * object's radius after the large object.
 113  *
 114  * 23    5/02/97 10:26a John
 115  * made non-ship objects use minimum z for z testing.
 116  *
 117  * 22    3/26/97 12:38p Hoffoss
 118  * JAS: made object sorting look at gr_zbuffering instead of
 119  * gr_zbufferinging
 120  *
 121  * 21    3/12/97 9:25a John
 122  * fixed a bug with zbuffering.  Reenabled it by default.
 123  *
 124  * 20    3/10/97 6:21p John
 125  * Simplified rendering code a bit.
 126  *
 127  * 19    3/06/97 5:07p Mike
 128  * turned in full zbuffering for now
 129  *
 130  * 18    3/04/97 12:09a Mike
 131  * Clean up code.  Make External_view_mode well-behaved.  Add
 132  * aip->repair_objnum to save/restore.  Add restore_int_if() in state.cpp.
 133  *
 134  * $NoKeywords: $
 135  */
 136
 137
 138 #include "pstypes.h"
 139 #include "object.h"
 140 #include "3d.h"
 141 #include "2d.h"
 142 #include "systemvars.h"
 143 #include "fireballs.h"
 144 #include "missionparse.h"
 145 #include "neb.h"
 146
 147 typedef struct sorted_obj {
 148         object                  *obj;                                   // a pointer to the original object
 149         float                           z, min_z, max_z;        // The object's z values relative to viewer
 150 } sorted_obj;
 151
 152 int Num_sorted_objects = 0;
 153 sorted_obj Sorted_objects[MAX_OBJECTS];
 154 int Object_sort_order[MAX_OBJECTS];
 155
 156
 157 // Used to (fairly) quicky find the 8 extreme
 158 // points around an object.
 159 vector check_offsets[8] = {
 160   { -1.0f, -1.0f, -1.0f },
 161   { -1.0f, -1.0f,  1.0f },
 162   { -1.0f,  1.0f, -1.0f },
 163   { -1.0f,  1.0f,  1.0f },
 164   {  1.0f, -1.0f, -1.0f },
 165   {  1.0f, -1.0f,  1.0f },
 166   {  1.0f,  1.0f, -1.0f },
 167   {  1.0f,  1.0f,  1.0f }
 168 };
 169
 170 // See if an object is in the view cone.
 171 // Returns:
 172 // 0 if object isn't in the view cone
 173 // 1 if object is in cone
 174 // This routine could possibly be optimized.  Right now, for an
 175 // offscreen object, it has to rotate 8 points to determine it's
 176 // offscreen.  Not the best considering we're looking at a sphere.
 177 int obj_in_view_cone( object * objp )
 178 {
 179         int i;
 180         vector tmp,pt;
 181         ubyte codes;
 182
 183 // Use this to hack out player for testing.
 184 // if ( objp == Player_obj ) return 0;
 185
 186 // OLD INCORRECT CODE!!!
 187 //      g3_rotate_vector(&tmp,&objp->pos);
 188 //      codes=g3_code_vector_radius(&tmp, objp->radius);
 189 //      if ( !codes )   {
 190 //              return 1;               // center is in, so return 1
 191 //      }
 192 //      return 0;
 193
 194 // This I commented out because it will quickly out for
 195 // objects in the center, but cause one more rotation
 196 // for objects outside the center.  So I figured it
 197 // would be best to slow down objects inside by a bit
 198 // and not penalize the offscreen ones, which require
 199 // 8 rotatations to throw out.
 200 //      g3_rotate_vector(&tmp,&objp->pos);
 201 //      codes=g3_code_vector(&tmp);
 202 //      if ( !codes )   {
 203 //              //mprintf(( "Center is in, so render it\n" ));
 204 //              return 1;               // center is in, so return 1
 205 //      }
 206
 207         // Center isn't in... are other points?
 208
 209         ubyte and_codes = 0xff;
 210
 211         for (i=0; i<8; i++ )    {
 212                 vm_vec_scale_add( &pt, &objp->pos, &check_offsets[i], objp->radius );
 213                 g3_rotate_vector(&tmp,&pt);
 214                 codes=g3_code_vector(&tmp);
 215                 if ( !codes )   {
 216                         //mprintf(( "A point is inside, so render it.\n" ));
 217                         return 1;               // this point is in, so return 1
 218                 }
 219                 and_codes &= codes;
 220         }
 221
 222         if (and_codes)  {
 223                 //mprintf(( "All points offscreen, so don't render it.\n" ));
 224                 return 0;       //all points off screen
 225         }
 226
 227         //mprintf(( "All points inside, so render it, but doesn't need clipping.\n" ));
 228         return 1;
 229 }
 230
 231
 232 // Sorts all the objects by Z and renders them
 233 extern int Fred_active;
 234 void obj_render_all(void (*render_function)(object *objp) )
 235 {
 236         object *objp;
 237         int i, j, incr;
 238         float fog_near, fog_far;
 239
 240         objp = Objects;
 241         Num_sorted_objects = 0;
 242         for (i=0;i<=Highest_object_index;i++,objp++) {
 243                 if ( (objp->type != OBJ_NONE) && (objp->flags&OF_RENDERS) )     {
 244                         objp->flags &= ~OF_WAS_RENDERED;
 245
 246                         if ( obj_in_view_cone(objp) )   {
 247                                 sorted_obj * osp = &Sorted_objects[Num_sorted_objects];
 248                                 Object_sort_order[Num_sorted_objects] = Num_sorted_objects;
 249                                 Num_sorted_objects++;
 250
 251                                 osp->obj = objp;
 252                                 vector to_obj;
 253                                 vm_vec_sub( &to_obj, &objp->pos, &Eye_position );
 254                                 osp->z = vm_vec_dot( &Eye_matrix.fvec, &to_obj );
 255 /*
 256                                 if ( objp->type == OBJ_SHOCKWAVE )
 257                                         osp->z -= 2*objp->radius;
 258 */
 259                                 // Make warp in effect draw after any ship in it
 260                                 if ( objp->type == OBJ_FIREBALL )       {
 261                                         //if ( fireball_is_warp(objp) ) {
 262                                         osp->z -= 2*objp->radius;
 263                                         //}
 264                                 }
 265
 266                                 osp->min_z = osp->z - objp->radius;
 267                                 osp->max_z = osp->z + objp->radius;
 268                         }
 269                 }
 270         }
 271
 272
 273         // Sort them by their maximum z value
 274         if ( Num_sorted_objects > 1 ) {
 275                 incr = Num_sorted_objects / 2;
 276                 while( incr > 0 )       {
 277                         for (i=incr; i<Num_sorted_objects; i++ )        {
 278                                 j = i - incr;
 279                                 while (j>=0 )   {
 280                                         // compare element j and j+incr
 281                                         if ( (Sorted_objects[Object_sort_order[j]].max_z < Sorted_objects[Object_sort_order[j+incr]].max_z)  ) {
 282                                                 // If not in correct order, them swap 'em
 283                                                 int tmp;
 284                                                 tmp = Object_sort_order[j];
 285                                                 Object_sort_order[j] = Object_sort_order[j+incr];
 286                                                 Object_sort_order[j+incr] = tmp;
 287                                                 j -= incr;
 288                                         } else {
 289                                                 break;
 290                                         }
 291                                 }
 292                         }
 293                         incr = incr / 2;
 294                 }
 295         }
 296
 297         gr_zbuffer_set( GR_ZBUFF_FULL );
 298
 299         // now draw them
 300         for (i=0; i<Num_sorted_objects; i++)    {
 301                 sorted_obj * os = &Sorted_objects[Object_sort_order[i]];
 302                 os->obj->flags |= OF_WAS_RENDERED;
 303
 304                 // if we're fullneb, fire up the fog - this also generates a fog table
 305                 if((The_mission.flags & MISSION_FLAG_FULLNEB) && (Neb2_render_mode != NEB2_RENDER_NONE) && !Fred_running){
 306                         // get the fog values
 307                         neb2_get_fog_values(&fog_near, &fog_far, os->obj);
 308
 309                         // only reset fog if the fog mode has changed - since regenerating a fog table takes
 310                         // a bit of time
 311                         if((fog_near != gr_screen.fog_near) || (fog_far != gr_screen.fog_far)){
 312                                 gr_fog_set(GR_FOGMODE_FOG, gr_screen.current_fog_color.red, gr_screen.current_fog_color.green, gr_screen.current_fog_color.blue, fog_near, fog_far);
 313                         }
 314
 315                         // maybe skip rendering an object because its obscured by the nebula
 316                         if(neb2_skip_render(os->obj, os->z)){
 317                                 continue;
 318                         }
 319                 }
 320
 321                 (*render_function)(os->obj);
 322         }
 323
 324         // if we're fullneb, switch off the fog effet
 325         if((The_mission.flags & MISSION_FLAG_FULLNEB) && (Neb2_render_mode != NEB2_RENDER_NONE)){
 326                 gr_fog_set(GR_FOGMODE_NONE, 0, 0, 0);
 327         }
 328
 329 /*      Show spheres where wingmen should be flying
 330         {
 331                 extern void render_wing_phantoms_all();
 332                 render_wing_phantoms_all();
 333         }
 334         */
 335 }
 336