We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.
IndexProgramming Questions & HelpSyntax Questions › optimizing distance
Page Index Toggle Pages: 1
optimizing distance (Read 1091 times)
optimizing distance
Jul 15th, 2009, 6:35am
 
Hi is there any diference in terms of cpu consumption between using the dist() function or calculating the distance using the formula  sqrt(x1 - x2 ) * (x1 - x2 )  +  (y1 - y2) * (y1 - y2) ? which is better in terms of cpu consumption?

In the program im working on each agent calculates the distance between itself and a point, im using this distance for calculating gravity so i dont need to have the exact distance. Is there any way of optimizing the distance? maybe theres a way of sacrifying precision for speed, do anything like this exist?

thanks


pun.
Re: optimizing distance
Reply #1 - Jul 15th, 2009, 8:32am
 
there's essentially no difference - some very minor overhead in calling dist() as opposed to inlining the formula yourself (tho of course you should precalc x2-x1 and y2-y1 just once).

there are many ways to calculate sqrt's, google it.  but beware - with a current jvm/cpu most of the tricks out there for twiddling int bits (or table lookups, or whatever) to calculate approximate sqrt's are actually slower than Math.sqrt()!

so, forget it, not worth the effort, better to optimize at a higher level.  perhaps reconsider if you need the sqrt at all, or if you could rework your equations to use distance-squared.

hth
Re: optimizing distance
Reply #2 - Jul 15th, 2009, 8:36am
 
if you don't need the real distance, you can remove the sqrt function which is the bottleneck there and just use squared distances.


have fun.
Re: optimizing distance
Reply #3 - Jul 15th, 2009, 8:53am
 
punchik wrote on Jul 15th, 2009, 6:35am:
is there any diference in terms of cpu consumption between using the dist() function or calculating the distance
No. dist() is using the same formula (with just a bit more function calls, but it should not make a measurable difference).

Quote:
Is there any way of optimizing the distance
Not sure how you want to use it, but a common optimization, mostly used to check circle collision, is to skip the sqrt computation: the test just checks if the squared distance is equal or below the squared combined radii. See if this trick works for you.
Re: optimizing distance
Reply #4 - Jul 20th, 2009, 9:56am
 
Dropping the sqrt() as others have said might save you a bit of time. This is especially the case if you are modelling gravity which will use a distance-squared function anyway.

Other optimisations might include excluding points greater than a threshold distance (squared) assuming their gravitational attraction is negligible.

You might also consider using a HashGrid if you are selecting a subset of points based on a given location. This can speed things up by an order of magnitude for large point collections. I have written a library for Processing that allows you to use HashGrids fairly easily. See www.soi.city.ac.uk/~jwo/processing/hashGrid.

Jo.
Re: optimizing distance
Reply #5 - Jul 21st, 2009, 8:12am
 

Wow jo wood thats amazing, i didnt know you wrote that library. Some days ago i used your class hashgrid and i adapted your ants.pde example  (http://www.soi.city.ac.uk/~jwo/processing/ants1/ ) to a program i been working on.

The program uses  the library glgraphics, this library has a class called glmodel that allows to use the gpu for drawing shapes or points(vertex buffer objects)


Using the hashgrid and the glmodel with collision i can run until 2400 of agents in my computer, the same program without the hashgrid stuff can run just 300 agents with collision.  The thing is that without collisions i can create up to 12000 agents  just using glmodel.
I also tried the change the dist(), but i cannont percieve any benefit.
Do you think is there any way of optimizing for having more agents?
if not which other options do i have if i want to have more agents?
And my last quesiton, is there any benefit of using the library hashgrid instead of using the class hashgrid as i did in terms of cpu consumption? Is it a good idea if i use the library instead the class?

thanks

here is the code
Re: optimizing distance
Reply #6 - Jul 21st, 2009, 8:15am
 
these code works with the hashgrid class:
Code:
Vector agents;
HashGrid hashGrid;
boolean useNSquaredSearch;
static final int NUM_ANTS = 156; //con esto se puede optimizar?

//**********<agentes>************

import processing.opengl.*;
import codeanticode.glgraphics.*;
import javax.media.opengl.GL;

GLCamera cam;
GLModel model;
float[] coords;
float[] colors;

float[] x;
float[] y;

float[] delta_x;
float[] delta_y;

float velocidad = 3;
float direccion = random(TWO_PI);

int numPoints = 4000;

float distance = 4200;

//***********</agentes>***************

void setup()
{
size(600,600, GLConstants.GLGRAPHICS);
cam = new GLCamera(this, 0, 0, distance, 0, 0, 0);
model = new GLModel(this, numPoints, POINTS, GLModel.DYNAMIC);
model.initColors();

agents = new Vector();
hashGrid = new HashGrid(width,height,round(width/Agent_values.SENSOR_DIST),round(height/Agent_values.SENSOR_DIST));
// for (int i=0; i<NUM_ANTS; i++)
// {
//ants.add(new Ant(random(0,width-1),random(0,width-1)));
// }

//*****************<agentes>

x = new float[numPoints];
y = new float[numPoints];

delta_x = new float[numPoints];
delta_y = new float[numPoints];

coords = new float[4 * numPoints];
colors = new float[4 * numPoints];

for (int i = 0; i < numPoints; i++)
{
//*************<agente>
float random_x = random(642) ; // esto lo hago para que el objeto comparta el mismo valor x que mi punto de glmodel
float random_y = random(482) ;
agents.add(new Agent_values(random_x, random_y));
//***************</agente>

x[i] = random_x;
y[i] = random_y;

colors[4 * i + 3] = 0.9;
}
model.updateVertices(coords);
model.updateColors(colors);
//******************</agentes>********

}


void draw()
{
//********************<glgraphics>*************************
GLGraphics renderer = (GLGraphics)g;
GL gl = renderer.beginGL();
// renderer.beginGL();
for (int i = 0; i < numPoints; i++){
x[i] = x[i] + random(-0.5,0.5)*3 + delta_x[i]/4 /4 ;

y[i] = y[i] + random(-0.5,0.5)*3 + delta_y[i]/4 / 4 ;

float x_para_gl_y_objeto = x[i]/6.5 - 48 ;
float y_para_gl_y_objeto = y[i]/6.5 * -1 + 38;

Agent_values agent = (Agent_values)agents.get(i);

agent.x = x[i];
agent.y = y[i];

//aca debo de pasarle x_para_gl_y_objeto y y_para_gl_y_objeto a cada objeto

coords[4 * i ] = x_para_gl_y_objeto;
coords[4 * i + 1 ] = y_para_gl_y_objeto ;

}
//******************************</glgraphics>************************

hashGrid.clear();

for (int i=0; i<agents.size(); i++)
{
Agent_values agent = (Agent_values)agents.get(i);
hashGrid.add(agent,agent.x,agent.y);

// Compare this ant with any others in the same grid cell
Vector antList = (Vector)hashGrid.get(agent.x, agent.y);
if (antList != null)
{
for (int j=0; j<antList.size(); j++)
{
Agent_values otherAnt = (Agent_values)antList.get(j);
if (agent != otherAnt)
{


if (agent.distToAnt(otherAnt) < Agent_values.SENSOR_DIST)
{
// agent.setAngry(true);
// otherAnt.setAngry(true);

//aca debo poner el punto gl model que cambiara de color?
for (int k = 0; k < 3; k++) {
colors[4 * i + k ]= 0.9 ;
}
}
else
{
for (int k = 0; k < 3; k++){
colors[4 * i + k ]= 0.0;
}
}

}
}
}

// Get each ant to draw itself.
// ant.display();
}
model.updateVertices(coords);
model.updateColors(colors);
//model.updateVertices(colors);
cam.feed();
cam.clear(255, 25 , 25);
gl.glPointSize(5);
model.render();
cam.done();
renderer.endGL();
println(frameRate);

}
class Agent_values
{
// float x,y; // Ant location.
float direction; // Direction of travel.
float speed; // Speed of ant.
boolean isAngry; // Indicates whether ant is angry or not.

float size; // Size of ant.
static final float SENSOR_DIST=2; // Distance within which ant can sense other beings.

//*************<agente>
float coords;
float colors;

float x;
float y;

float delta_x;
float delta_y;
float velocidad = 3;
float direccion = random(TWO_PI);
//*************</agente>************

// Creates a new ant.
Agent_values(float x, float y)
{
this.x = x;
this.y = y;
size = 10;
direction = random(-PI,PI);
speed = 1;
isAngry = false;
}

// Draws the ant at its current location.
void display()
{

if (isAngry)
{
//fill(150,50,50);
isAngry = false;
}
else
{
// fill(50);
}

}

// Determines whether or not ant is angry.
void setAngry(boolean isAngry)
{
this.isAngry = isAngry;
}

// Measures the distance between this and the given ant.
float distToAnt(Agent_values otherAnt)
{
return dist(x,y,otherAnt.x,otherAnt.y);
//return abs(x - otherAnt.x) + abs(y - otherAnt.y) ;

}
}
Page Index Toggle Pages: 1