Re: efficient vector math...
On 12/1/2010 8:09 PM, Kevin McMurtrie wrote:
In article<icvlii$db$1@news.albasani.net>, BGB<cr88192@hotmail.com>
wrote:
sorry if I am missing something obvious here, but I am hoping for
suggestions on a relatively efficient general-purpose way to handle
vector math and similar (in the sense of geometric vectors...).
I will likely be writing any code myself, so the request is for ideas
for a general design.
this is for a personal project (most of the rest of the project uses C,
but this will be for the Java part of the project). Java isn't really my
main language FWIW...
purposes and requirements:
performance should be good, and interface should also be nice (if possible);
the app will be soft real-time on a custom JVM (JavaME style), and the
GC is slow and so avoiding GC (by minimizing garbage) is preferable (so
user will not experience stalls);
it doesn't need to deal with arbitrary N-sized vectors, only 2, 3, and 4
element vectors (XYZW), and also Quaternions;
likely vector size and usage will be considered as part of the type (a
Vec2 is not a Vec3 which is not a Vec4 which is not a Quat);
the vectors will potentially be recalculated frequently and in large
numbers;
...
so, a few possibilities:
A, immutable vectors:
pros: clean interface, supports merging and sharing vectors, ...
cons: many vectors may be created, likely creating lots of garbage.
B, mutable vectors:
pros: likely to reduce garbage (most recalculation can reuse existing
vectors);
cons: vectors can't be shared (since they may change without warning),
and the interface is more awkward (vector values are copied, meaning
vectors need to be provided to use for storing temporary values, ...).
C, supporting both (as different types):
pros: can mix and match as needed;
cons: 2x or 3x as many types (mutable and immutable versions of each
size, 3x if both versions are subclasses of a common abstract type),
more awkward class names to distinguish them, more methods, ...
D, supporting both (as different operations on the same type):
pros: allows mixing and matching use-patterns (general);
cons: use-case ambiguity (need to infer intended use from context).
arrays and indices ("float[] vecs=new float[nvecs*4];" or similar):
pros: errm... likely compact memory...
cons: likely overly ugly/awkward.
I have been considering this matter over the past several days.
leaning at the moment is for option D.
example classes:
basic: Vec2, Vec3, Vec4, Quat
multi-typed (option C):
Vec2a, Vec3a, Vec4a, Quata //abstract
Vec2c, Vec3c, Vec4c, Quadc //constant/immutable
Vec2n, Vec3n, Vec4n, Quatn //mutable
Vec#c and Vec#n would be subtypes of Vec#a, so methods accepting the
abstract forms would accept both, with the mutable and immutable forms
differing in terms of their external behavior.
options B and D would likely use a "pool" for freed vectors of a given
type (garbage reduced by manually "freeing" spare vectors, whereas A
would likely try to do a lookup and on failure create a new vector).
matrix math may also be considered.
suggestions, opinions, or other options?...
Option A is the clean way but GC costs will completely dominate the CPU.
GC is indeed fast, but it's nowhere near as fast as small vector
operations.
Option B works but it brittle when caching and sharing is involved.
Mutable keys destroy many types of caches.
Option C: I've done mixed class types for bitmap rendering where
intermediate stages needed caching. Immutable was the special case
because caching and sharing were few compared to the many calculations.
The abstract base class for both supported all read operations and
defined methods getMutable() and getImmutable(). The
getMutable/getImmutable implementations returned the 'this' reference or
a new object as needed. No casting or 'instanceof' was needed.
D sounds messy.
yeah.
in my implementation (a custom-written mini-JVM with a slow GC and no
JIT), option B is probably the best overall...
although sadly I am busy enough recently that I haven't gotten around to
implementing it as of yet...
the revised 'Option C' is an interesting idea, I may consider it...
I will guess it does not support direct access: 'vec.x' (since one needs
to either make it final or not final, or rely on good graces that one
does not assign it in the immutable case...).
I guess, "vec.getX()" or "vec.x()" should also work.
(below is untested, just assuming that javac will not barf...).
idly thinking here:
public class Vec3
{
private static final int MAX=1024;
private static Vec3[] cache;
private static int nCache;
private double x, y, z;
static {
cache=new Vec3[MAX];
nCache=0;
}
public Vec3()
{ this(0, 0, 0); }
public Vec3(double x, double y, double z)
{ this.x=x; this.y=y; this.z=z; }
public float x() { return x; }
public float y() { return y; }
public float z() { return z; }
public void x(double v) { x=v; }
public void y(double v) { y=v; }
public void z(double v) { z=v; }
public void set(double x, double y, double z)
{ this.x=x; this.y=y; this.z=z; }
public void set(Vec3 v)
{ x=v.x; y=v.y; z=v.z; }
public void addn(Vec3 v)
{ x+=v.x; y+=v.y; z+=v.z; }
public void subn(Vec3 v)
{ x-=v.x; y-=v.y; z-=v.z; }
public Vec3 add(Vec3 v)
{ return Vec3.at(x+v.x, y+v.y, z+v.z); }
public Vec3 sub(Vec3 v)
{ return Vec3.at(x-v.x, y-v.y, z-v.z); }
public double dot(Vec3 v)
{ return x*v.x + y*v.y + z*v.z; }
....
public Vec3 at(double x, double y, double z)
{
Vec3 tmp;
if(nCache>0)
{
tmp=cache[--nCache];
tmp.set(x, y, z);
return tmp;
}
return new Vec3(x, y, z);
}
public void free()
{
if(nCache<MAX)
cache[nCache++]=this;
}
}
an immutable case (implicit subclass?) could possibly disallow the
destructive methods (they are no-op or throw an exception), and probably
an 'Vec3.at(x, y, z)' method could be used to cache immutable vectors
(likely merged by epsilon and hashed).
something like:
public int hash()
{
long ix, iy, iz, i; //long is overkill?...
ix=(long)(x/EPSILON);
iy=(long)(y/EPSILON);
iz=(long)(z/EPSILON);
i=((ix*4294967291L+iy)*4294967291L+iz)*4294967291L;
return (int)(i>>>32);
}
public Vec3 at(double x, double y, double z)
{
Vec3 tmp;
int h;
h=hash()&1023;
tmp=cache[h];
if(tmp && tmp.isAt(x, y, z))
return tmp;
tmp=new ImmutableVec3(x, y, z);
cache[h]=tmp;
return tmp;
}
or such...