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

Leon Turner bf-committers@blender.org
Mon, 3 May 2004 22:17:20 +0900

```Hi All,

I've updated the patch and the windows binary (same links as before):

http://reblended.com/www/leon/bfpatch.txt
http://reblended.com/www/leon/bf-blender.zip

There are a few improvements:

1) I've changed the triangle intersection routine to the one suggested
by Alex below. It also checks both triangles of a quad, so non-planar
quads should no longer be a problem. Calculation times are a little
slower (but not too much, and the result is better), so any speed
improvement suggestions welcome!

2) I've added a "contact force" element which kicks in when particles
are moving in contact with the surface. The result is that leaks
should be pretty much gone, unless the deflector itself is moving.

Alex - I wasn't sure whether transforming the particle co-ordinates /
velocities to object space would help much, given that I need to cycle
through many possible deflection objects. What do you think?

Cheers

Leon

On Sun, 02 May 2004 11:32:51 +0100, Alex Mole <nal@blueyonder.co.uk> wrote:
>=20
> Hi Leon
>=20
> [apologies for huge post...]
>=20
> reblended.com is back up again now :)
>=20
> 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.
>=20
> 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 :)
>=20
> 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=F6ller&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/
>=20
> pseudocode:
> params: o =3D start pos, b =3D end pos, v0,v1,v2 =3D triangle vertices
> def LineTriIntersect (o, b, v0, v1, v2)
> [returns ({REJECT,INTERSECT}, u, v, t)]
>         e1 =3D v1 - v0
>         e2 =3D v2 - v0
>         d =3D b - o
>         p =3D d x e2
>         a =3D e1 . p
>         if (a > -E and a < E) return (REJECT, 0, 0, 0)
>         f =3D 1 / a
>         s =3D o - v0
>         u =3D f * (s . p)
>         if (u < 0.0 or u > 1.0) return (REJECT, 0, 0, 0)
>         q =3D s x e1
>         t =3D f * (e2 . q)
>         if (t < 0.0 or t > 1.0) return (REJECT, 0, 0, 0)
>         v =3D f * (d . q)
>         if (v < 0.0 or v > 1.0) return (REJECT, 0, 0, 0)
>         return (INTERSECT, u, v, t)
>=20
> 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 =3D start_point + t*(end_point-start_point)
>=20
> There are almost certainly faster methods of doing this still, but the
> above will be substantially better than the angle-summing method :)
>=20
> 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
>=20
> One other tip, that applies to all graphics coders, is to get hold of a
> copy of Real Time Rendering by M=F6ller and Haines
> (http://www.amazon.com/exec/obidos/tg/detail/-/1568811829/qid=3D108349371=
1/sr=3D8-1/ref=3Dpd_ka_1/104-4857886-1060759?v=3Dglance&s=3Dbooks&n=3D50784=
6)
> 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 :)
>=20
> Cheers-
>=20
> Alex
>=20
>=20
> _______________________________________________
> Bf-committers mailing list
> Bf-committers@blender.org
> http://www.blender.org/mailman/listinfo/bf-committers
>

```