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