src/object/objectsort.cpp

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