Home Products Download Order Contacts


Subject: Re: A Geometry Problem

"Vector" wrote in message
> Give a set of points in 3D Space {Vi: 1 = 1,2,...,n}, find the point
> Va, a (- {1,2,...,n} to minimize
> distance = sum||Va-Vi||
> i=1,..n
> to design a O(n^2)algorithm is easy , is there fast algorighm, for
> example O(n*logn)

yay for kd trees.

once I used them to make my physics lib not slow (had screen shots showing
this one, 1500 objects sitting around a map at 10fps), but then it got slow
again for other reasons.

but, yeah, at the time 1500 objects was quite a bit better than about 200 as
I could pull off prior to implementing the algo.

for some tasks, another possibility is using a bsp tree (for example, one
representing the world geometry). which may be less efficient, but is more
likely to mix well with other things that may need to sort objects using the
bsp tree (eg: a renderer, where drawing objects in the correct order wrt
each other and the map geometry is useful, eg, for things like transparency
and culling).

eventually the physics lib got slow again, primarily, because of making some
collision handlers use culled points per volume and averaging to try to
compute contact information. this is hardly efficient and doesn't really
work better than more geometric approaches anyways. at the time it was in a
vain attempt to fix a problem that had more subtle causes: a single contact
point is insufficient for most cases, one needs to compute, eg, a contact

in a simple test done externally (a much simpler mock-up physics engine)
this approach worked effectively in giving good contact behavior between
convex polyhedra (objects would stack and otherwise deflect about right).

upon discovering it, I didn't bother to fix anything, as I had already
gotten burnt out on the amount of effort being required...

I haven't worked on it in quite a few months (and if I did, I would probably
first fix friction modeling, then the basic collision handlers, followed
maybe by implementing better collision handling...).

I now understand how some things could have been done better, but never got
to fixing it. not a whole lot presently uses the engine, so motivation is
lacking (for simple things it works, apart from the fact that when using
inches and pounds as the base unit, friction is way off so objects will
slide way too easily).

another point of comment:
though having back-force based friction is more "realistic" (according to
the books at least), friction based on absorbing a certain percentage of the
sliding velocity is a lot less error prone (which I guess is why it is used
in most libs I have been able to look at). in any case, it wont break hard
when one changes their units...

or whatever...


View All Messages in comp.graphics.algorithms

A Geometry Problem =>


Copyright 2006 WatermarkFactory.com. All Rights Reserved.