# [Bf-committers] Particle experiments - looking for feedback

Alex Mole bf-committers@blender.org
Sun, 02 May 2004 11:32:51 +0100

```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

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

```