HashMap issues...

Newbie & Debugging Questions
#1

What I’m Trying To Do:

Loop through all triangles {
if there is an intensity value assigned to the vertex in the HashMap already {
set the vertex’s intensity to the already calculated intensity
} else {
calculate the intensity and set it to the vertex
pair up the vertex and the intensity and add it to the HashMap
}
}

Therefore using this logic, I should have to only calculate the intensity of the vertex only once.

However, the body of the “if there is an intensity value assigned to the vertex in the HashMap already” statement never gets called because it never is null.

When I print out all the keys and values in the HashMap, I get repeated keys.

Anyone know the issue?

	private strictfp void calculateLight(int ambientIntensity, int intensity, Vector source) {
		Map<Vector, Integer> calculated = new HashMap<Vector, Integer>();
		for (Triangle tri : triangles) {
			
			Vector n = tri.normal();

			if (calculated.get(tri.v1) != null) {
				tri.i1 = calculated.get(tri.v1);
			} else {
				tri.i1 = calcIntensity(n, tri.v1, source, intensity, ambientIntensity);
				calculated.put(tri.v1, tri.i1);
			}

			if (calculated.get(tri.v2) != null) {
				tri.i1 = calculated.get(tri.v2);
			} else {
				tri.i2 = calcIntensity(n, tri.v2, source, intensity, ambientIntensity);
				calculated.put(tri.v2, tri.i2);
			}
			
			if (calculated.get(tri.v3) != null) {
				tri.i1 = calculated.get(tri.v3);
			} else {
				tri.i3 = calcIntensity(n, tri.v3, source, intensity, ambientIntensity);
				calculated.put(tri.v3, tri.i3);
			}
			
		}
		Iterator<Vector> keySetIterator = calculated.keySet().iterator();

		while (keySetIterator.hasNext()) {
			Vector key = keySetIterator.next();
			System.out.println("key: " + key + " value: " + calculated.get(key));
		}

	}
#2

Man that’s the first time I’ve seen strictfp actually being used.

You probably aren’t [correctly] overriding equals() and/or hashCode() for Vector.

#3

This is my Vector equals method.


	@Override
	public boolean equals(Object obj) {
		float epsilon = 0.0001f;
		Vector vec = (Vector) obj;
		return Math.abs(vec.x - x) < epsilon && Math.abs(vec.y - y) < epsilon && Math.abs(vec.z - z) < epsilon;
	}

And does hashCode need to be overridden to check for equality? I’ve never overridden it.

#4

Yes I believe so try this:


 @Override
    public int hashCode() {
        int hash = 7;
        hash = 59 * hash + Float.floatToIntBits(this.x);
        hash = 59 * hash + Float.floatToIntBits(this.y);
        hash = 59 * hash + Float.floatToIntBits(this.z);
        return hash;
    }

    
    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Vector3f other = (Vector3f) obj;
        return Float.floatToIntBits(this.x) == Float.floatToIntBits(other.x)
                && Float.floatToIntBits(this.y) == Float.floatToIntBits(other.y)
                && Float.floatToIntBits(this.z) == Float.floatToIntBits(other.z);
    }

Edit: cleaned looked ugly.

#5

Well it is a HashMap, isn’t it? :point:

But as a general rule: http://stackoverflow.com/a/2707554

[quote]If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
[/quote]

#6

Ahh, okay, thank you BurntPizza and thank you KudoDEV.

#7

The strictfp does nothing here.

#8

Yeah I know that, this method used to be completely different, full of floating point algorithms and such. I just copy and pasted the method and rewrote the contents within it to try out this HashMap idea I had.

#9

I also use hashmaps of vectors alot, looks like this :

@Override public int hashCode()
{
  // long hash = 1;
  int hash = 1;

  // trunc(); // truncating a vector is useful sometimes (for normals or colours)

  hash = hash*31 + floatToIntBits(x);
  hash = hash*31 + floatToIntBits(y);
  hash = hash*31 + floatToIntBits(z);

  // return(int)( hash ^ ( hash>>32 )); // uncomment this and the first line to use 64bit hash
  return hash;                          // 32bit hash is 'good enough' most time
}

float-to-int-bits can cause a little headache with [icode]0.0f[/icode] and [icode]-0.0f[/icode] :

public static int floatToIntBits(final float f)
{
  return f == 0.0f ? 0 : Float.floatToIntBits(f);
}

trunc can look like this, if you need it. precision like [icode]0.00001f[/icode] works fine :

public final vec3d trunc(final float precision)
{
  x = roundTo(x,precision);
  y = roundTo(y,precision);
  z = roundTo(z,precision);

  return this;
}

public static float roundTo(final float x, final float precision)
{
  return floor(x/precision + 0.5f)*precision;
}

public static int floor(final float v)
{
  return v >= 0 ? (int)v : (int)v - 1;
}

the equals method, again my prefered flavour :

@Override public boolean equals(final Object v)
{
  try
  {
    return equals((vec3d)v);
  }
  catch(final ClassCastException ignored)
  {
    return false;
  }
}

public final boolean equals(final vec3d v)
{
  try
  {
    return equals(x,v.x) && equals(y,v.y) && equals(z,v.z);
  }
  catch(final NullPointerException ignored)
  {
    return false;
  }
}

public static boolean equals(final float a,final float b)
{
  return Math.abs(a - b) < FLOAT_ERROR;
}

i use a fixed [icode]FLOAT_ERROR[/icode] around 4 * machine epsilon, which is good enough. more correct would be an error scaled with a and b.


compute machine eps can be done like this :

static
{
  float eps = 1.0f;

  do
  {
    eps = eps*0.5f;
  }
  while(eps + 1 > 1);

  MACHINE_EPS = eps;
}

then i just use [icode]FLOAT_ERROR = MACHINE_EPS*4.01f;[/icode] when comparing two floats, cos’ i’m lazy.

o/

#10

Instead of burdening Vec3.hashCode() and Vec3.equals() with error-margins, I think that for your use case it’s much better to transform the original data that is loaded from a model file, prior to shoving it into a HashMap.


Vec3 vec = new Vec3(parseFloat(x), parseFloat(y), parseFloat(z));

@@vec.trunc(0.001f); // 1mm resolution



class Vec3 {
   // ...

   public boolean equals(Vec3 that) {
      return (this.x == that.x) && (this.y == that.y) && (this.z == that.z);
   }

   @Override
   public int hashCode() {
      int hash = 1;
      hash = hash*31 + floatToIntBits(x);
      hash = hash*31 + floatToIntBits(y);
      hash = hash*31 + floatToIntBits(z);
      return hash;
   }
}
#11

As an aside: putting vertices into a hashmap (in general) seems like a really bad idea.

Otherwise…some points:

If you do, then having constant precision through the domain is probably better than direct FP (multiply by constant and covert to integer).

You’ll probably get better results using a modern hashing function than old school (the smaller the size of the map, the lesser the importance)


public static int floatToIntBits(final float f)
{
   Float.floatToIntBits(f+0.f); // adding zero flushes any negative zeroes.
}

With IEEE compliance, you never need to compute the epsilon.

#12

It’s useful to do deduplication. Like finding (almost) matching vertex-attributes, for when you’re indexing your vertex-data. [icode]HashMap<VertexAttr, Integer>[/icode]

I use it as ‘an algorithm’, as opposed to (meaningful) storage of data.

#13

Yeah that’s an example.

#14

@Roquen thanks for the [icode]Float.floatToIntBits(f+0.f)[/icode] neg-zero trick :slight_smile:

got a side-note too : i use http://fastutil.di.unimi.it/ alot, they provide all kinds of hashmaps. the interesting part is, some of them allow us to provide an implementation of equality and hashcodes to the hashmap.

means, with that we can turn the whole thing around and tell the hashmap how to compute hashcodes/equals and not code it into the objects stored. in the end it’s the same.

#15

That’s indeed the obvious way to go.

It’s just like the Comparable interface is a massive design flaw. Use Comparators, already! There is more than one way to order things, and natural order only really applies for numbers, not even strings (see: case sensitiveness).

Burdening every single class with the responsibility to make it usable for a rather specific datastructure is so backwards that it’s amazing it hasn’t been at least made pluggable in the Collection API.