src/com/jme/renderer/RenderQueue.java

   1 /*
   2  * Copyright (c) 2003-2009 jMonkeyEngine
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met:
   8  *
   9  * * Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  *
  12  * * Redistributions in binary form must reproduce the above copyright
  13  *   notice, this list of conditions and the following disclaimer in the
  14  *   documentation and/or other materials provided with the distribution.
  15  *
  16  * * Neither the name of 'jMonkeyEngine' nor the names of its contributors
  17  *   may be used to endorse or promote products derived from this software
  18  *   without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  22  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  23  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  24  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  25  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  26  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  27  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  28  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  29  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  30  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  */
  32
  33 package com.jme.renderer;
  34
  35 import java.util.Arrays;
  36 import java.util.Comparator;
  37
  38 import com.jme.math.Vector3f;
  39 import com.jme.scene.Geometry;
  40 import com.jme.scene.Spatial;
  41 import com.jme.scene.state.CullState;
  42 import com.jme.scene.state.RenderState;
  43 import com.jme.scene.state.TextureState;
  44 import com.jme.scene.state.ZBufferState;
  45 import com.jme.system.JmeException;
  46 import com.jme.util.SortUtil;
  47
  48 /**
  49  * This optional class supports queueing of rendering states that are drawn when
  50  * displayBackBuffer is called on the renderer. All spatials in the opaque
  51  * bucket are rendered first in order closest to farthest. Then all spatials in
  52  * the opaque bucket are rendered in order farthest to closest. Finally all
  53  * spatials in the ortho bucket are rendered in ortho mode from highest to
  54  * lowest Z order. As a user, you shouldn't need to use this class directly. All
  55  * you'll need to do is call Spatial.setRenderQueueMode .
  56  *
  57  * @author Joshua Slack
  58  * @author Jack Lindamood (javadoc + SpatialList only)
  59  * @see com.jme.scene.Spatial#setRenderQueueMode(int)
  60  *
  61  */
  62 public class RenderQueue {
  63
  64     /** List of all transparent object to render. */
  65     private SpatialList transparentBucket;
  66     private SpatialList transparentBackBucket;
  67
  68     /** List of all opaque object to render. */
  69     private SpatialList opaqueBucket;
  70     private SpatialList opaqueBackBucket;
  71
  72     /** List of all ortho object to render. */
  73     private SpatialList orthoBucket;
  74     private SpatialList orthoBackBucket;
  75
  76     /** The renderer. */
  77     private Renderer renderer;
  78
  79     /** CullState for two pass transparency rendering. */
  80     private CullState tranCull;
  81
  82     /** ZBufferState for two pass transparency rendering. */
  83     private ZBufferState tranZBuff;
  84
  85     /** boolean for enabling / disabling two pass transparency rendering. */
  86     private boolean twoPassTransparent = true;
  87
  88     private Vector3f tempVector = new Vector3f();
  89
  90     /**
  91      * Creates a new render queue that will work with the given renderer.
  92      *
  93      * @param r
  94      */
  95     public RenderQueue(Renderer r) {
  96         this.renderer = r;
  97         tranCull = r.createCullState();
  98         tranZBuff = r.createZBufferState();
  99         tranZBuff.setWritable(false);
 100         tranZBuff.setFunction(ZBufferState.TestFunction.LessThanOrEqualTo);
 101         setupBuckets();
 102     }
 103
 104     /**
 105      * Enables/Disables two pass transparency rendering. If enabled, objects in
 106      * the TRANSPARENT queue will be rendered in two passes. On the first pass,
 107      * objects are rendered with front faces culled. On the second pass, objects
 108      * are rendered with back faces culled.
 109      *
 110      * This allows complex transparent objects to be rendered whole without
 111      * concern as to the order of the faces drawn.
 112      *
 113      * @param enabled
 114      *            set true to turn on two pass transparency rendering
 115      */
 116     public void setTwoPassTransparency(boolean enabled) {
 117         twoPassTransparent = enabled;
 118     }
 119
 120     /**
 121      * @return true if two pass transparency rendering is enabled.
 122      */
 123     public boolean isTwoPassTransparency() {
 124         return twoPassTransparent;
 125     }
 126
 127     /**
 128      * Creates the buckets needed.
 129      */
 130     private void setupBuckets() {
 131         opaqueBucket = new SpatialList(new OpaqueComp());
 132         opaqueBackBucket = new SpatialList(new OpaqueComp());
 133         transparentBucket = new SpatialList(new TransparentComp());
 134         transparentBackBucket = new SpatialList(new TransparentComp());
 135         orthoBucket = new SpatialList(new OrthoComp());
 136         orthoBackBucket = new SpatialList(new OrthoComp());
 137     }
 138
 139     /**
 140      * Add a given Spatial to the RenderQueue. This is how jME adds data tothe
 141      * render queue. As a user, in 99% of casees you'll want to use the function
 142      * Spatail.setRenderQueueMode and let jME add the item to the queue itself.
 143      *
 144      * @param s
 145      *            Spatial to add.
 146      * @param bucket
 147      *            A bucket type to add to.
 148      * @see com.jme.scene.Spatial#setRenderQueueMode(int)
 149      * @see com.jme.renderer.Renderer#QUEUE_OPAQUE
 150      * @see com.jme.renderer.Renderer#QUEUE_ORTHO
 151      * @see com.jme.renderer.Renderer#QUEUE_TRANSPARENT
 152      */
 153     public void addToQueue(Spatial s, int bucket) {
 154         switch (bucket) {
 155         case Renderer.QUEUE_OPAQUE:
 156             opaqueBucket.add(s);
 157             break;
 158         case Renderer.QUEUE_TRANSPARENT:
 159             transparentBucket.add(s);
 160             break;
 161         case Renderer.QUEUE_ORTHO:
 162             orthoBucket.add(s);
 163             break;
 164         default:
 165             throw new JmeException("Illegal Render queue order of " + bucket);
 166         }
 167     }
 168
 169     /**
 170      * Calculates the distance from a spatial to the camera. Distance is a
 171      * squared distance.
 172      *
 173      * @param spat
 174      *            Spatial to distancize.
 175      * @return Distance from Spatial to camera.
 176      */
 177     private float distanceToCam(Spatial spat) {
 178         if (spat.queueDistance != Float.NEGATIVE_INFINITY)
 179                 return spat.queueDistance;
 180         Camera cam = renderer.getCamera();
 181         spat.queueDistance = 0;
 182
 183         Vector3f camPosition = cam.getLocation();
 184         Vector3f spatPosition = null;
 185         Vector3f viewVector = cam.getDirection();
 186
 187         if (Vector3f.isValidVector(cam.getLocation())) {
 188             if (spat.getWorldBound() != null && Vector3f.isValidVector(spat.getWorldBound().getCenter()))
 189                 spatPosition = spat.getWorldBound().getCenter();
 190             else if (spat instanceof Spatial && Vector3f.isValidVector(((Spatial)spat).getWorldTranslation()))
 191                 spatPosition = ((Spatial) spat).getWorldTranslation();
 192         }
 193
 194         if (spatPosition != null) {
 195             spatPosition.subtract(camPosition, tempVector);
 196
 197             float retval = Math.abs(tempVector.dot(viewVector)
 198                     / viewVector.dot(viewVector));
 199             tempVector = viewVector.mult(retval, tempVector);
 200
 201             spat.queueDistance = tempVector.length();
 202         }
 203
 204         return spat.queueDistance;
 205     }
 206
 207     /**
 208      * clears all of the buckets.
 209      */
 210     public void clearBuckets() {
 211         transparentBucket.clear();
 212         opaqueBucket.clear();
 213         orthoBucket.clear();
 214     }
 215
 216     /**
 217      * swaps all of the buckets with the back buckets.
 218      */
 219     public void swapBuckets() {
 220         SpatialList swap = transparentBucket;
 221         transparentBucket = transparentBackBucket;
 222         transparentBackBucket = swap;
 223
 224         swap = orthoBucket;
 225         orthoBucket = orthoBackBucket;
 226         orthoBackBucket = swap;
 227
 228         swap = opaqueBucket;
 229         opaqueBucket = opaqueBackBucket;
 230         opaqueBackBucket = swap;
 231     }
 232
 233     /**
 234      * Renders the opaque, clone, transparent, and ortho buckets in that order.
 235      */
 236     public void renderBuckets() {
 237         renderOpaqueBucket();
 238         renderTransparentBucket();
 239         renderOrthoBucket();
 240     }
 241
 242     /**
 243      * Renders the opaque buckets. Those closest to the camera are rendered
 244      * first.
 245      */
 246     private void renderOpaqueBucket() {
 247         opaqueBucket.sort();
 248         for (int i = 0; i < opaqueBucket.listSize; i++) {
 249             opaqueBucket.list[i].draw(renderer);
 250         }
 251         opaqueBucket.clear();
 252     }
 253
 254     /**
 255      * Renders the transparent buckets. Those farthest from the camera are
 256      * rendered first. Note that any items in the transparent bucket will
 257      * have their cullstate values overridden. Therefore, any settings assigned
 258      * to the cullstate of the rendered object will not be used.
 259      */
 260     private void renderTransparentBucket() {
 261         transparentBucket.sort();
 262             for (int i = 0; i < transparentBucket.listSize; i++) {
 263                 Spatial obj = transparentBucket.list[i];
 264
 265                 if (twoPassTransparent
 266                     && obj instanceof Geometry
 267                     && (((Geometry) obj).states[RenderState.StateType.Cull.ordinal()] != null
 268                                 && !((Geometry) obj).states[RenderState.StateType.Cull.ordinal()].isEnabled())) {
 269                     Geometry geom = (Geometry)obj;
 270                     RenderState oldCullState = geom.states[RenderState.StateType.Cull.ordinal()];
 271                     geom.states[RenderState.StateType.Cull.ordinal()] = tranCull;
 272                     ZBufferState oldZState = (ZBufferState)geom.states[RenderState.StateType.ZBuffer.ordinal()];
 273                     geom.states[RenderState.StateType.ZBuffer.ordinal()] = tranZBuff;
 274
 275                     // first render back-facing tris only
 276                     tranCull.setCullFace(CullState.Face.Front);
 277                     obj.draw(renderer);
 278
 279                     // then render front-facing tris only
 280                     geom.states[RenderState.StateType.ZBuffer.ordinal()] = oldZState;
 281                     tranCull.setCullFace(CullState.Face.Back);
 282                     obj.draw(renderer);
 283                     geom.states[RenderState.StateType.Cull.ordinal()] = oldCullState;
 284                 } else {
 285                     // draw as usual
 286                     obj.draw(renderer);
 287                 }
 288                 obj.queueDistance = Float.NEGATIVE_INFINITY;
 289             }
 290         transparentBucket.clear();
 291     }
 292
 293     /**
 294      * Renders the ortho buckets. Those will the highest ZOrder are rendered
 295      * first.
 296      */
 297     private void renderOrthoBucket() {
 298         orthoBucket.sort();
 299         if (orthoBucket.listSize > 0) {
 300             renderer.setOrtho();
 301             for (int i = 0; i < orthoBucket.listSize; i++) {
 302                 orthoBucket.list[i].draw(renderer);
 303             }
 304             renderer.unsetOrtho();
 305         }
 306         orthoBucket.clear();
 307     }
 308
 309     /**
 310      * This class is a special function list of Spatial objects for render
 311      * queueing.
 312      *
 313      * @author Jack Lindamood
 314      * @author Three Rings - better sorting alg.
 315      */
 316     private class SpatialList {
 317
 318         Spatial[] list, tlist;
 319
 320         int listSize;
 321
 322         private static final int DEFAULT_SIZE = 32;
 323
 324         private Comparator<Spatial> c;
 325
 326         SpatialList(Comparator<Spatial> c) {
 327             listSize = 0;
 328             list = new Spatial[DEFAULT_SIZE];
 329             this.c = c;
 330         }
 331
 332         /**
 333          * Adds a spatial to the list. List size is doubled if there is no room.
 334          *
 335          * @param s
 336          *            The spatial to add.
 337          */
 338         void add(Spatial s) {
 339             if (listSize == list.length) {
 340                 Spatial[] temp = new Spatial[listSize * 2];
 341                 System.arraycopy(list, 0, temp, 0, listSize);
 342                 list = temp;
 343             }
 344             list[listSize++] = s;
 345         }
 346
 347         /**
 348          * Resets list size to 0.
 349          */
 350         void clear() {
 351             for (int i = 0; i < listSize; i++)
 352                 list[i] = null;
 353             if (tlist != null)
 354                 Arrays.fill(tlist, null);
 355             listSize = 0;
 356         }
 357
 358         /**
 359          * Sorts the elements in the list acording to their Comparator.
 360          */
 361         void sort() {
 362             if (listSize > 1) {
 363                 // resize or populate our temporary array as necessary
 364                 if (tlist == null || tlist.length != list.length) {
 365                     tlist = list.clone();
 366                 } else {
 367                     System.arraycopy(list, 0, tlist, 0, list.length);
 368                 }
 369                 // now merge sort tlist into list
 370                 SortUtil.msort(tlist, list, 0, listSize, c);
 371             }
 372         }
 373     }
 374
 375     private class OpaqueComp implements Comparator<Spatial> {
 376
 377         public int compare(Spatial o1, Spatial o2) {
 378             if (o1 instanceof Geometry && o2 instanceof Geometry) {
 379                 return compareByStates((Geometry) o1, (Geometry) o2);
 380             }
 381
 382             float d1 = distanceToCam(o1);
 383             float d2 = distanceToCam(o2);
 384             if (d1 == d2)
 385                 return 0;
 386             else if (d1 < d2)
 387                 return -1;
 388             else
 389                 return 1;
 390         }
 391
 392         /**
 393          * Compare opaque items by their texture states - generally the most
 394          * expensive switch. Later this might expand to comparisons by other
 395          * states as well, such as lighting or material.
 396          */
 397         private int compareByStates(Geometry g1, Geometry g2) {
 398             TextureState ts1 = (TextureState)g1.states[RenderState.StateType.Texture.ordinal()];
 399             TextureState ts2 = (TextureState)g2.states[RenderState.StateType.Texture.ordinal()];
 400             if (ts1 == ts2) return 0;
 401             else if (ts1 == null && ts2 != null) return -1;
 402             else if (ts2 == null && ts1 != null) return  1;
 403
 404             for (int x = 0, nots = Math.min(ts1.getNumberOfSetTextures(), ts2.getNumberOfSetTextures()); x < nots; x++) {
 405
 406                 int tid1 = ts1.getTextureID(x);
 407                 int tid2 = ts2.getTextureID(x);
 408                 if (tid1 == tid2)
 409                     continue;
 410                 else if (tid1 < tid2)
 411                     return -1;
 412                 else
 413                     return 1;
 414             }
 415
 416             if (ts1.getNumberOfSetTextures() != ts2.getNumberOfSetTextures()) {
 417                 return ts2.getNumberOfSetTextures() - ts1.getNumberOfSetTextures();
 418             }
 419
 420             return 0;
 421         }
 422     }
 423
 424     private class TransparentComp implements Comparator<Spatial> {
 425
 426         public int compare(Spatial o1, Spatial o2) {
 427             float d1 = distanceToCam(o1);
 428             float d2 = distanceToCam(o2);
 429             if (d1 == d2)
 430                 return 0;
 431             else if (d1 < d2)
 432                 return 1;
 433             else
 434                 return -1;
 435         }
 436     }
 437
 438     private class OrthoComp implements Comparator<Spatial> {
 439         public int compare(Spatial o1, Spatial o2) {
 440             if (o2.getZOrder() == o1.getZOrder()) {
 441                 return 0;
 442             } else if (o2.getZOrder() < o1.getZOrder()) {
 443                 return -1;
 444             } else {
 445                 return 1;
 446             }
 447         }
 448     }
 449 }
 450