Slow Framerate with 800+ Voronoi Points

dusker1

Slow Framerate with 800+ Voronoi Points

in Contributed Library Questions • 1 years ago

Requires Lee Byrons Voronoi Mesh library.

Problem:

- Slow framerate once 800+ points are added.

Looking for optimization / suggestions to improve performance. As I am hoping to get it running very smoothly at the 1000 - 2000 point mark.

import megamu.mesh.*;
Voronoi voronoi;
float[][] points = new float[0][2];
int totalPoints = 800;
ArrayList<PVector> pointsList = new ArrayList<PVector>();
int selectDistance = 10;
boolean selected = false;
int index = 0;
void setup()
{
size(1800, 900);
//ImportPoints();
GenerateVoronoiPoints();
}
void draw()
{
background(255);
DrawVoronoi();
}
void ImportPoints()
{
String[] strLines = loadStrings("VoronoiPoints.txt");
for(int i=0;i<strLines.length;i++)
{
String[] strList = split(strLines[i], ',');
float x = new Float(strList[0]);
float y = new Float(strList[1]);
points = (float[][])append(points, new float[] {x, y});
}
}
void DrawVoronoi()
{
voronoi = new Voronoi(points);
MPolygon[] regions = voronoi.getRegions();
for(int r=0;r<regions.length;r++)
{
regions[r].draw(this);
stroke(0);
ellipse(points[r][0],points[r][1],5,5);
}
}
void GenerateVoronoiPoints()
{
PVector pv1;
float x;
float y;
for(int i=0;i<totalPoints;i++)
{
x = random(5,width);
y = random(5,height);
pv1 = new PVector(x,y);
if(!pointsList.contains(pv1))
{
pointsList.add(pv1);
}
}
for(int p=0;p<pointsList.size();p++)
{
x = pointsList.get(p).x;
y = pointsList.get(p).y;
points = (float[][])append(points, new float[] {x, y});
}
}
void mousePressed()
{
if(mouseButton == RIGHT)
{
points = (float[][])append(points, new float[] {mouseX, mouseY});
}
voronoi = new Voronoi(points);
}
void mouseDragged()
{
for(int i =0;i<points.length;i++)
{
if(!selected)
{
if (mouseX > points[i][0] - selectDistance
&& mouseX < points[i][0] + selectDistance
&& mouseY > points[i][1] - selectDistance
&& mouseY < points[i][1] + selectDistance)
{
selected = true;
index = i;
}
}
}
if(selected)
{
points[index][0] = mouseX;
points[index][1] = mouseY;
}
}
void mouseReleased()
{
selected = false;
index = -1;
}

So this is working, however once I hit 800+ points the framerate drops once you start dragging points around / adding points.

Can anyone help me with the framerate issues, possible suggestions for Optimization?

Thanks! This thing is kinda fun to play around with too.

Side note: This is part of a larger project, cut out in its simplest form to test for efficiency.

Replies(7)

PhiLho

Re: Slow Framerate with 800+ Voronoi Points

1 years ago

for(int p=0;p<pointsList.size();p++)
{
x = pointsList.get(p).x;
y = pointsList.get(p).y;
points = (float[][])append(points, new float[] {x, y});
}

can be done with:

points = new float[pointsList.size()][2];
for (int p = 0; p < pointsList.size(); p++)
{
points[p][0] = pointsList.get(p).x;
points[p][1] = pointsList.get(p).y;
}

(untested) At least, it will be more efficient, speed and memory wise.
The append() in mousePressed is a lesser evil, needed by the structure Voronoi expects, and happening only on user interaction.
The draw() itself can be hardly optimized, most of the work is done by the library...

Ah, yes, there is an obvious improvement! Why is there voronoi = new Voronoi(points); in DrawVoronoi()? It is already computed on start and each time a new point is added. You don't need to do this complex computing on each frame, do you? Just add the computation in mouseDragged(), perhaps. BTW, once you set set selected to true, just do break, no need to continue in the loop.

dusker1

Re: Slow Framerate with 800+ Voronoi Points

1 years ago

Hey thanks for the reply.

Some good points in Optimization for sure.

I'm using the break idea, thanks for that!

As for the voronoi = new Voronoi(points) in DrawVoronoi()

It still works when the calculation is switched over to mouseDragged() like you said, however, with 800+points when a cell is dragged around the framerate drops to as low as 6fps.

I've tried P2D,P3D, openGL, as well as increasing the amount of ram available.

Is there a possible line renderer or something that could assist with this calculation or am I hooped?

Thanks again for the suggestions, they are very helpful! A code review is always beneficial.

PhiLho

Re: Slow Framerate with 800+ Voronoi Points

1 years ago

You can avoid recomputing the Voronoi on each mouse dragging, ie. let dragging, then recompute only on mouse released. Less nice, but better performance.

dusker1

Re: Slow Framerate with 800+ Voronoi Points

1 years ago

that does increase fps for sure. Sadly it is not as nice, as mentioned.

I was hoping for some kind of faster renderer, poly renderer, or something that could help with the drawing process' as I do plan to do a lot of hand editing and seeing the points move around is almost a necessity for placement.

Thanks for your help thus far!

Any possible libraries to look at?

PhiLho

Re: Slow Framerate with 800+ Voronoi Points

1 years ago

I believe the issue isn't in the renderer, but in the Voronoi algorithm computing. Not sure if it can be improved, it is a time consuming, complex algorithm.

dusker1

Re: Slow Framerate with 800+ Voronoi Points

1 years ago

Yeah, that makes sense. Well thanks for your help, I'm going to try some other voronoi libraries see if I can increase performance.

dusker1

Re: Slow Framerate with 800+ Voronoi Points

1 year ago

So, I found the Voronoi2D class inside the Hemesh library.

It uses a basic fortunes algorithm.

Fortune's Algorithm - wiki

Basically it's the fastest way to generate Voronoi cells, even at high numbers it's quite smooth.

I can get upwards of 5000+ points running smoothly.

If anyone's interested in optimizing performance for live voronoi cell editing, I'd check out the Hemesh library, Voronoi2D class.

cheers.

Top Reply