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