Ripple algorithm optimization

Unity Engine
1

Hi there,

I’ve the following algorithm to generate ripples on a sphere’s surface. Technically, it works. However, it’s extremely slow, and I was wondering about how to best optimize it (apart from removing the obvious overhead of the dictionary).

Would it be better if I applied the algorithm to a plane and projected it somehow to the surface? Or is the elimination of the dictionaries be enough.

public class Ripple2D : MonoBehaviour
{
    private Vector3[] _vertices;
    private Edge[] _edges;
    private Mesh mesh;
    private Vector3 center;
    private Dictionary<Vector3, RipplePoint> _ripples = new Dictionary<Vector3, RipplePoint>();
    public int MaxHeight = 1;
    public float Dampening = 0.9f;
    public float WaveSize = 0.02f;

    // Use this for initialization
    void Start()
    {
        var mf = GetComponent<MeshFilter>();
        mesh = mf.mesh;
        _vertices = mesh.vertices;
        center = transform.position;
        _edges = GetMeshEdges(mesh);
    }

    // Update is called once per frame
    void Update()
    {
        var newVertices = new Vector3[_vertices.Length];
        CheckInput();
        var VertexChange = new Dictionary<Vector3, Vector3>();
        var newRipples = new List<RipplePoint>();
        var toRemove = (from ripple in _ripples where ripple.Value.Force.sqrMagnitude < 0.0000001 select ripple.Key).ToList();
        toRemove.ForEach(x => _ripples.Remove(x));
        foreach (var ripple in _ripples)
        {
            ripple.Value.Frame++;
            var vector = ripple.Key;
            var ripplePoint = ripple.Value;

            var nearby = NearbyVertices(vector);
            VertexChange.Add(vector, ripplePoint.Force);
            ripplePoint.Force = ripplePoint.Mul * ripplePoint.Force * Dampening;
            newRipples.AddRange(nearby.Where(vector3 => (!_ripples.ContainsKey(vector3) || _ripples[vector3].Force.magnitude < ripplePoint.Force.magnitude) && newRipples.All(x => x.Center != vector3)).Select(vector3 => new RipplePoint()
            {
                Center = vector3,
                Force = ripplePoint.Mul * ripplePoint.Force.magnitude * vector3.normalized * Dampening
            }));

            mesh.vertices = newVertices;
        }
        newRipples.ForEach(x =>
        {
            if (!_ripples.ContainsKey(x.Center)) _ripples.Add(x.Center, x);
            else
            {
                _ripples[x.Center].Force = x.Force;
                _ripples[x.Center].Frame = x.Frame;
            }
        });

        for (int i = 0; i < _vertices.Length; i++)
        {
            if (VertexChange.ContainsKey(_vertices[i]))
            {
                newVertices[i] = _vertices[i] + VertexChange[_vertices[i]];
            }
            else
            {
                newVertices[i] = _vertices[i];
            }
        }
        mesh.vertices = newVertices;
    }

    void CheckInput()
    {
        if (Input.GetMouseButton(0))
        {
            RaycastHit hit;
            if (Physics.Raycast(Camera.main.ScreenPointToRay(Input.mousePosition), out hit))
            {
                float minDistanceSqr = Mathf.Infinity;
                Vector3 nearestVertex = Vector3.zero;
                var point = hit.point;
                foreach (Vector3 vertex in _vertices)
                {
                    Vector3 diff = point - vertex;
                    float distSqr = diff.sqrMagnitude;

                    if (distSqr < minDistanceSqr)
                    {
                        minDistanceSqr = distSqr;
                        nearestVertex = vertex;
                    }
                }
                if (!_ripples.ContainsKey(nearestVertex))
                {
                    _ripples.Add(nearestVertex, new RipplePoint()
                    {
                        Center = nearestVertex,
                        Force = hit.normal * WaveSize,
                    });
                }
                else
                {
                    _ripples[nearestVertex].Force = hit.normal * WaveSize;
                }
            }
        }
    }

    private Vector3[] NearbyVertices(Vector3 vector)
    {
        return _edges.Where(x => x.v1 == vector || x.v2 == vector).Select(x => x.v1 == vector ? x.v2 : x.v1).ToArray();
    }

    private class RipplePoint
    {
        public Vector3 Center;
        public Vector3 Force;
        public float ChangeSpeed;
        public int Frame;

        public float Mul
        {
            get
            {
                Debug.Log(Frame / 10f);
                return Mathf.Cos((Frame/10f)*Mathf.PI);
            }
        }
    }

    public struct Edge
    {
        public Vector3 v1;
        public Vector3 v2;

        public Edge(Vector3 v1, Vector3 v2)
        {
            if (v1.x < v2.x || (v1.x == v2.x && (v1.y < v2.y || (v1.y == v2.y && v1.z <= v2.z))))
            {
                this.v1 = v1;
                this.v2 = v2;
            }
            else
            {
                this.v1 = v2;
                this.v2 = v1;
            }
        }
    }

    private Edge[] GetMeshEdges(Mesh mesh)
    {
        HashSet<Edge> edges = new HashSet<Edge>();

        for (int i = 0; i < mesh.triangles.Length; i += 3)
        {
            var v1 = mesh.vertices[mesh.triangles[i]];
            var v2 = mesh.vertices[mesh.triangles[i + 1]];
            var v3 = mesh.vertices[mesh.triangles[i + 2]];
            edges.Add(new Edge(v1, v2));
            edges.Add(new Edge(v1, v3));
            edges.Add(new Edge(v2, v3));
        }

        return edges.ToArray();
    }
2

some ideas

  • Check with deep Profiler
  • You are re-creating the arrays inside update loop, could do that once in start
  • Remove debug logs
  • Foreach is probably littlebit slower than For
  • _vertices.Length value could be cached in start also
  • mesh.vertices = newVertices is assigned in 2 places, is that necessary?
3

I think you’ll be surprised how much speed you’ll gain by just removing the Debug.Log.

2 Likes
4

Exactly what mgear said^

I was doing some loops inside loops and speed dramatically increased when I changed from “var1 in var2” to the standard i = 0; i < length; i++

An easy way to speed things up without changing a ton of code could be this:

for (var i2 = 0; i2 < cachedRippleLength; i2++)
{
       var ripple = _ripples[i2];
       //leave the rest of the code
5

I was aware of the Debug.Log(), but didn’t notice the double mesh.vertices = newVertices assignment, thanks for that one, will see how much faster I can make this

6

Okay, here is the result:

Thanks for mgear about the deep profiler; I’ve never really used it before but it helped a lot tracking down the slow calls.
What helped the most, was caching the result of NearbyVertices() into a dictionary at start since the function got way too many hits for what it’s doing.

Changing the vertices foreach loop to a for loop actually resulted in slowdown due to the nature of the Dictionary. However, with the profiler I’ve found some other bottlenecks, like the unnecessary check in newRipples.AddRange() which was a huge overhead. (newRipples.All(x => x.Center!= vector3))

7

Noticed you are using a dictionary, in effect even a sphere can be viewed as a flat array of 2d points or even a 1d line of points.

You could also pre bake the network of points into a comparable node data structure that could really up performance.

Also you are using divide by 10 in Mul and accessing a Mathf.PI element (static const this value), you also have a debug.Log in here ouch! Replace any divisions by multiplications e.g. “x / 10” → “x * 0.1f” or better still multiply by a constant of PI * 0.1f.

8

RipplePoint is a class I think you could gain a performance boost from making it a struct.

Actually the RipplePoint Frame should be a static const and Mul should also use a static value calculated when Frame is changed.

9

But if you step back a bit lets face it the ripples should be calculated on the GPU, in effect what we really need is a Ripple Shader and a script that passes in new ripples.

1 Like
10

Indeed, however I’m a potato when it comes to shaders :3

11

Then your code will run like a potato.

1 Like
12

Making ripples via a shader is easy. I’ve written several shaders which generate various types or combinations of ripples. You just use the sine function.

13

Incredibly fast also - it’s unlikely it will change your framerate or register at all if in vertex. Lots of resources on the web for unity vertex shader fun.

14

Yup. I wrote a shader that produces an entire planet on-the-fly (including waves lapping up on shore, since we’re talking about ripples), and it runs without any noticeable effect on the framerate. And it animates even in Editor mode, since it’s running in the video card.
That’s why everything should be done with shaders if possible…

15

If it’s on the CPU then there’s a ton of speed to be gained by getting rid of the overloaded math ops and function calls.

http://www.performancesimulations.com/wp/how-to-get-big-speed-increases-in-unitys-physics-or-any-math-heavy-code/

16

Wow cool so if IL2CPP code ‘inlined’ all vector ops could Unity obtain a massive speed boost.

Or if we wrote a tool to automatically convert Vector ops to inline code!

17

I had a discussion with somebody about this once. I’m not sure, but from that it sounded like, inlining it might not really be an option because your code is a separate dll from the C++ stuff on Unity’s side (or something like this). I was told that for one reason or another this probably makes it impossible to inline the ops.

Again, I don’t really know for sure, this is just what somebody suggested. I’m one of those weirdos that has always written code the long way like this, expanding out the math, if for no other reason than it burned dot and cross and other operations into my brain. When I see this:

q3 = q2 + q1

it’s not always immediately obvious what type it is. This one the other hand:

q3.x = q2.x + q1.x;
q3.y = q2.y + q1.y;
q3.z = q2.z + q1.z;

to my eyes is more clear. The vector3 just jumps out at me. Most people around here don’t seem to agree with that, they see the second as less maintainable and harder to read. For me it’s the opposite. To each his own, I guess.

I do wonder though if a dll could be written that does large quantities of vector calculations in parallel using SIMD instructions or something. That’d be even better than inlining it, that way the x/y/z computations happen simultaneously the way they do in shaders. A couple of C++ friends are doing that in non-Unity projects and get substantial gains in performance in physics heavy code.