[Bf-committers] Particle experiments - looking for feedback

[Alex Mole]

Hi Leon

[apologies for huge post...]

reblended.com is back up again now :)

I have a few optimisation tips for this code, which should easily speed 
it up enough that you'll be able to treat all quads as tris.

For every particle, every deflection mesh gets converted to world 
coordinates. This means potentially a lot of duplicated effort [not too 
much for single quads, but to bounce it off interesting meshes and use 
it to its full potential, there will be a lot]. Have you considered 
transforming each particle by the inverse of the object's matrix and 
carrying out the calculations in object-local space [and then 
transforming back again once you're done]? That means at most 4 matrix 
mults per mesh, and most likely only 2. This would probably speed it up 
by an order of magnitude :)

The other point I'd make is that pointintriangle() uses an algorithm 
that is easy to understand, but has been shown to be much slower than 
what is possible. Möller&Trumbore presented this much faster technique 
for testing whether a line segment crosses a triangle [in this case the 
line segment is the line from the old position to the new position]. You 
can have a look to find others at
http://www.acm.org/pubs/tog/editors/erich/ptinpoly/

pseudocode:
params: o = start pos, b = end pos, v0,v1,v2 = triangle vertices
def LineTriIntersect (o, b, v0, v1, v2)
[returns ({REJECT,INTERSECT}, u, v, t)]
	e1 = v1 - v0
	e2 = v2 - v0
	d = b - o
	p = d x e2
	a = e1 . p
	if (a > -E and a < E) return (REJECT, 0, 0, 0)
	f = 1 / a
	s = o - v0
	u = f * (s . p)
	if (u < 0.0 or u > 1.0) return (REJECT, 0, 0, 0)
	q = s x e1
	t = f * (e2 . q)
	if (t < 0.0 or t > 1.0) return (REJECT, 0, 0, 0)
	v = f * (d . q)
	if (v < 0.0 or v > 1.0) return (REJECT, 0, 0, 0)
	return (INTERSECT, u, v, t)

u&v are the barycentric coordinates of intersection on the triangle, and 
t is the parametric point of intersection on the line, so that:
point_of_intersection = start_point + t*(end_point-start_point)

There are almost certainly faster methods of doing this still, but the 
above will be substantially better than the angle-summing method :)


I'm happy to help with the implementation of this stuff [and I'm happy 
for you to just ignore it, as you probably have better things to do than 
reimplement your work ;)]

One other tip, that applies to all graphics coders, is to get hold of a 
copy of Real Time Rendering by Möller and Haines 
(http://www.amazon.com/exec/obidos/tg/detail/-/1568811829/qid=1083493711/sr=8-1/ref=pd_ka_1/104-4857886-1060759?v=glance&s=books&n=507846)
It is *by far* the best book I've seen on the topic, and covers all 
manner of rendering techniques, intersection tests, higher-order 
surfaces, etc. etc.). I really can't reccommend it enough :)


Cheers-

Alex