Potential bug in ListSort

1

Stack trace:

java.lang.UnsupportedOperationException: Compare function result changed! Make sure you do not modify the scene from another thread!
    at com.jme3.util.ListSort.mergeLow(ListSort.java:702)
    at com.jme3.util.ListSort.mergeRuns(ListSort.java:474)
    at com.jme3.util.ListSort.mergeCollapse(ListSort.java:407)
    at com.jme3.util.ListSort.sort(ListSort.java:233)
    at com.jme3.renderer.queue.GeometryList.sort(GeometryList.java:158)
    at com.jme3.renderer.queue.RenderQueue.renderGeometryList(RenderQueue.java:262)

Test case:

import com.jme3.app.SimpleApplication;
import com.jme3.material.Material;
import com.jme3.math.*;
import com.jme3.scene.*;
import com.jme3.scene.shape.Sphere;
import com.jme3.system.AppSettings;
import com.jme3.terrain.geomipmap.TerrainQuad;
import com.jme3.terrain.heightmap.HillHeightMap;

public class DebugTemplate extends SimpleApplication {
    public static void main(String[] args) {
        DebugTemplate t = new DebugTemplate();
        AppSettings settings = new AppSettings(true);

        settings.put("Width", 800);
        settings.put("Height", 600);
        settings.put("Title", "Tests");
        t.setSettings(settings);
        t.setShowSettings(false);
        t.start();
    }

    @Override
    public void simpleInitApp() {
        flyCam.setDragToRotate(true);
        testTerrain();
        
        for(int i = 0; i < 100; i++)
            for(int j = 0; j < 100; j++) {
                
//                float x = -25+i*0.5f;
//                float z = -25+j*0.5f;
                
                //error specific to position
                float x = i*0.5f;
                float z = j*0.5f;
                float y = this.terrain.getHeight(new Vector2f(x, z));
                
                rootNode.attachChild(
                    geomAt(new Sphere(7,7,0.1f), new Vector3f(x,y,z), ColorRGBA.Magenta)
                );
            }
    }

    float x = 0f;
    @Override
    public void simpleUpdate(float tpf) {
        x += tpf;
        cam.lookAt(new Vector3f(x,0,0), Vector3f.ZERO);
    }
    
    TerrainQuad terrain;
    HillHeightMap hill;
    Spatial testTerrain() {
        try {
            hill = new HillHeightMap(65, 50, 5, 20, 0);
            hill.normalizeTerrain(3f);
            hill.smooth(0.7f);
            
            terrain = new TerrainQuad(
            "my terrain",               // name
            33,                         // tile size
            65,                        // block size
            hill.getHeightMap());
        
            Material mat = new Material(assetManager, "Common/MatDefs/Light/Lighting.j3md");
            mat.setColor("Diffuse", ColorRGBA.Gray);
            
            terrain.setMaterial(mat);
        
            return terrain;
            
        } catch (Exception ex) {
            ex.printStackTrace();
        }
        
        return null;
    }
    public Geometry geomAt(Mesh m, Vector3f pos, ColorRGBA c) {
        Geometry g = new Geometry("", m);
        g.setLocalTranslation(pos);
        Material mat = new Material(assetManager, "Common/MatDefs/Misc/Unshaded.j3md");
        mat.setColor("Color", c);
        g.setMaterial(mat);
        return g;
    } 
}

The error is thrown by

private void mergeLow(int idxA, int lenA, int idxB, int lenB) {
   ...
   
   } else if(lengthA== 0){
            throw new UnsupportedOperationException(
   ...

lengthA is zero because of:

public void innerMergeLow(Comparator<T> comp, T[] arr, T[] tempArray) {
   ...
           do {                
                aWins = gallopRight(arr[iterB], tempArray, iterA, lengthA, 0, comp);
                if (aWins != 0) {
                    System.arraycopy(tempArray, iterA, arr, dest, aWins);
                    dest += aWins;
                    iterA += aWins;
                    lengthA -= aWins;
                    /* lengthA==0 is impossible now if the comparison
                    * function is consistent, but we can't assume
                    * that it is.
                    * a propper error will be thrown in mergeLow if lengthA == 0
                    */
                    if (lengthA <= 1){
                        return;
                    }
                }

thus, is the problem in method gallopRight?

2

The comment in this method states that the array[lastOffset] <= key < array[offset] However, while running it with a debugger, offset was 88 and when the method finished 88 was returned. thus key == array[offset] This might be where the problem is.

private int gallopRight(T key, T[] array, int idx, int length, int hint, Comparator<T> comparator) {
  ...
/* Now array[lastOffset] <= key < array[offset], so key belongs somewhere to the
 * right of lastOffset but no farther right than offset.  Do a binary
 * search, with invariant array[lastOffset-1] <= key < array[offset].
 */
  lastOffset++;
  while (lastOffset < offset) {
  int m = lastOffset + ((offset - lastOffset) >>> 1);
  if (comparator.compare(key, array[idx + m]) < 0) {
      offset = m;           //key < array[idx + m] 
  } else {
      lastOffset = m + 1;  // array[idx + m] <= key 
  }
}        
return offset;
3

Most likely, one of your spatials has an invalid transform. The error message is correct but it’s indication that threading is the cause is not always correct (though it can be).

If a spatial has an invalid quaternion then the distances used to calculate the sorting will be NaN… and NaN < NaN will always be false, no matter which order… so the sort is invalid.

Edit: note that this error message was updated recently (2 weeks ago or so) to reflect this and will be in the next release.

4

btw @pspeed and @Momoko_Fan now that we are based on java7 we could directly use arrays.sort as it’s based on TimSort since java7. Wouldn’t prevent those issues though and we wouldn’t be able to insert our own errors. But at least users wouldn’t doubt JRE code. :stuck_out_tongue:

5

Okay, finally I managed to realize that this.terrain.getHeight(new Vector2f(x, z));
can return NaN number.

Case closed. Bug was in test case. Thank you for the help. :slight_smile: