1

I have a ParticleSystem with 1000s particles scattered all over the screen. As I zoom and pan using the OrbitControls I'd like to get the particle closest to the center of the viewable area.

I'm thinking there are two parts to this. First, we need to find the center vertex of the viewable area. Next, we need to run the distance formula over all the particles to find the one closest to the center vertex. Hopefully, there is a more efficient way than this. The second part is fairly simple using brute force. The first part, is what I'm not sure of. How do I find the center vertex of the viewable area?

gman
  • 100,619
  • 31
  • 269
  • 393
wwwuser
  • 6,282
  • 8
  • 52
  • 64
  • If you are using `OrbitControls`, then `controls.target` is the point the camera rotates around, and it is the point the camera looks at, so it is in the center of the viewable area. – WestLangley Oct 22 '13 at 19:43

3 Answers3

1

You should probably get a point that's straight ahead of you like 10 units and then get the closest particle to that.

This post helps me tell you this, I've done it all before btw.

Three.js Projector and Ray objects

Its for clicking a point on the screen, and getting a vector out of it.

projector = new THREE.Projector();

// This is like clicking on the center of the screen, 0, 0 is center
straight_ahead = new THREE.Vector3(0,0,.5);

// Now we have straight_ahead relative to the camera
projector.unprojectVector(straight_ahead, camera);

// Now straight_ahead is just the direction of the camera, since we're taking away the camera's position from it
straight_ahead.sub(camera.position)

// It's a direction of where the camera is looking, so lets make it 10 units away( pick your own number)
straight_ahead.normalize().multiplyScalar(10)

// Now we we have a length of 10 units, we can get 10 units in front of the camera
straight_ahead.add(camera.position)

// At this point, straight ahead is a point in space 10 units in front of you, so lets find the closest point to that

// here's where you put a simple loop in
min_point = null
min_distance = 999999999
_.each( my_particles, function(particle) {
  distance = particle.position.distanceTo(straight_ahead)
  if (distance < min_distance) {
    min_point = particle
    min_distance = distance
  }
});

// now you have min_point, which should be the closest point to 10 feet in front of your face
Community
  • 1
  • 1
dansch
  • 6,059
  • 4
  • 43
  • 59
0
lookAt = camera.lookAt;
pos = camera.position;

min = MAX_FLOAT, min_index = -1;
foreach(particle in particle_system) {
    d = distance(particle.position, lookAt, pos);
    if( min>d ) { min_index = particle.getIndex; min = d; }
}

Where distance function can be found around the net, for example: http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line

This is pseudo code. What it does, it finds the viewing ray (lookAt vector) and finds closest particle from it.

EDIT:

var cam_position = camera.position,
    cam_eyeVec = getEyeVec(camera.projectionMatrix);

var min_dist = 10000000,
    min_index = -1;

for(var i=0; i<particle_count; i++) {
    var d = distance(particle[i].position, cam_eyeVec, cam_position);
    if(min_dist > d) {
         min_index = i;
         min_dist = d;
    }
}

function getEyeVec(projMat) {
    return new THREE.Vector3(projMat[8], projMat[9], projMat[10]);
}

function distance(p, n, a) {
    n = n.normalize();
    var diff = new THREE.Vector3(a.x-p.x, a.y-p.y, a.z-p.z);
    var diff_n = diff.multiply(n);
    var d = ((diff.selfSubstract(diff_n)).selfMultiply(n)).length();
    return d;
}

Calculation for getEyeVec is based upon - eye and up vectors from viewMatrix. Caluclation for distance is based upon - Distance from a point to a line.

Dragan Okanovic
  • 7,509
  • 3
  • 32
  • 48
  • Can you explain this a little more? I realize this is pseudo code, but I'm unclear as to what you are trying to convey. The distance formula compares two points, not three. Furthermore, lookAt is a function. Why would you pass that into a distance function? – wwwuser Oct 22 '13 at 18:29
  • I pass lookAt vector of camera, position of the camera and each particle's position. There's a formula that can calculate distance between a point and a line given by it's origin point and vector. And that's what you use to get distance. Any more clear? – Dragan Okanovic Oct 22 '13 at 21:40
  • I've been looking at this for the best couple days and am still having an issue calculating the nearest particle in the center of the viewable area. I'm new to Three.js and calculating the distance between a point and a line. Is there anyway we could change the distance pseudo code to real code? – wwwuser Oct 27 '13 at 22:03
  • Edited. Hope it makes sense. – Dragan Okanovic Oct 28 '13 at 08:44
  • selfSubtract and selfMultiply don't exist for a Vector3. Are they called "sub" and "multiply" now? Also, looks like diff_n always returns a Vector3 = (0, 0, 0) – wwwuser Oct 28 '13 at 11:56
  • You get the point. Search through `Vector3` definition and find what exactly you need. I am not going to write the exact code that you need. Do some small research, look for code and solutions, figure it out. – Dragan Okanovic Oct 28 '13 at 12:17
0

I'm not a three.js person but I do have experience in optimization algorithms. It is a mistake to loop though all the particles each time.

Instead, the particles need to be "sorted" and then when you have your camera position, you just find where it goes in the sort and you'll immediately have the closest points. It's very much like an index on a database. Or think the library. If someone gives you a book called "sorting" and the whole library is in strict alphabetical order, you don't have to check every single book in the library, you just walk right to S then SO, then SOR, then manually compare for the rest. So in a few seconds you could find the closest book to your book, without looking at all the books.

The way this works in a 2d case, is you need to store a couple levels of a "grid", then just determine which grid you are in, and check particles in that grid. For example, let's say you have 1 million particles, and on each one, you store whether it's on the right, or left of the center. Now with one quick "if" you can check if your camera is on the right or left side, and with that one if, you've cut out 500,000 particles that you need to loop through. So in practice, you'd store maybe 2 levels of a 1-9 grid, on each particle, when they are created, and that will cut out 99% of the particles you have to check. once you figure out which quadrant your camera (exact center) is in, you just look in the array of particles stored in that "grid location". So your particles will be stored in particle[1-9][1-9][1-100] or something like that.

Now if your particles are moving a lot, you'll have to do some simple mod (%) type math to figure out which grid location they're in, as they move, etc.

futher optimization can be done by setting a threshold, ie, what is "close enough", so even if your have 1000 particles almost on top of each other, if you get it within 10 pixels, you'll get a decent result much faster.

AwokeKnowing
  • 7,728
  • 9
  • 36
  • 47