упаковки неправильной формы кругов на поверхности сферы

Question

Я использую three.js для создания точек на сфере, подобно periodic table of elements example

набор Мои данные представляют собой круги неодинакового размера, и я хочу, чтобы равномерно распределить их вокруг поверхности сферы. После нескольких часов работы в Интернете я понимаю, что это много сложнее, чем кажется.

Вот примеры этой идеи в действии:

vimeo

pic

circlePack java applet

Может кто-нибудь помочь мне точку в направлении нахождения алгоритма, который позволит мне делать это? Соотношение упаковки не должно быть супер высоким, и в идеале это было бы что-то быстрое и легкое для вычисления в javascript для рендеринга в THREE.js (декартовой или координатной системе). Здесь важна эффективность.

Редактировать: радиус окружности может варьироваться в широких пределах. Вот пример использования кода периодической таблицы:

Answer 1

Здесь вы можете построить, возможно. Он будет беспорядочно распределять ваши сферы по сфере. Позже мы перейдем к этой отправной точке, чтобы получить равномерное распределение.

//random point on sphere of radius R 
var sphereCenters = [] 
var numSpheres = 100; 
for(var i = 0; i < numSpheres; i++) { 
    var R = 1.0; 
    var vec = new THREE.Vector3(Math.random(), Math.random(), Math.random()).normalize(); 
    var sphereCenter = new THREE.Vector3().copy(vec).multiplyScalar(R); 
    sphereCenter.radius = Math.random() * 5; // RANDOM SPHERE SIZE, plug in your sizes here 
    sphereCenters.push(sphereCenter); 
    //Create a THREE.js sphere at sphereCenter 
    ... 

} 

Затем запустите приведенный ниже код несколько раз, чтобы эффективно упаковать сферы:

for(var i = 0; i < sphereCenters.length; i++) { 
    for(var j = 0; j < sphereCenters.length; j++) { 
     if(i === j) continue; 
     //calculate the distance between sphereCenters[i] and sphereCenters[j] 
     var dist = new THREE.Vector3().copy(sphereCenters[i]).sub(sphereCenters[j]); 
     if(dist.length() < sphereSize) { 
      //move the center of this sphere to to compensate 
      //how far do we have to move? 
      var mDist = sphereSize - dist.length(); 
      //perturb the sphere in direction of dist magnitude mDist 
      var mVec = new THREE.Vector3().copy(dist).normalize(); 
      mVec.multiplyScalar(mDist); 
      //offset the actual sphere 
      sphereCenters[i].add(mVec).normalize().multiplyScalar(R); 

     } 
    } 
} 

Запуск Во втором разделе несколько раз будет «сходиться» на решение, которое вы ищете. Вы должны выбрать, сколько раз он должен запускаться, чтобы найти лучший компромисс между скоростью и точностью.

Обновлено для точности

Answer 2

Вы можете использовать тот же код, что и в таблице периодических таблиц. Прямоугольники там не касаются, поэтому вы можете получить тот же эффект с кругами, фактически используя тот же код.

Вот код, у них есть:

  var vector = new THREE.Vector3(); 

      for (var i = 0, l = objects.length; i < l; i ++) { 

       var phi = Math.acos(-1 + (2 * i)/l); 
       var theta = Math.sqrt(l * Math.PI) * phi; 

       var object = new THREE.Object3D(); 

       object.position.x = 800 * Math.cos(theta) * Math.sin(phi); 
       object.position.y = 800 * Math.sin(theta) * Math.sin(phi); 
       object.position.z = 800 * Math.cos(phi); 

       vector.copy(object.position).multiplyScalar(2); 

       object.lookAt(vector); 

       targets.sphere.push(object); 

      } 

Answer 3

Вот метод, чтобы попробовать: итеративный поиск, используя имитацию отталкивающую силу.

Алгоритм

Сначала инициализировать набор данных за счет расположения кругов по всей поверхности в любом виде алгоритма. Это просто для инициализации, поэтому она не должна быть большой. Периодический код таблицы будет хорошо. Кроме того, присвойте каждому кругу «массу», используя его радиус в качестве значения массы.

Теперь запустите итерацию, чтобы сходиться по решению. Для каждого прохода через главный контур выполните следующие действия:

1. Вычислить силы отталкивания для каждого круга. Моделируйте свою силу отталкивания после формулы для силы тяжести с двумя настройками: (a) объекты должны быть сдвинуты в сторону друг от друга, не притягиваются друг к другу, и (b) вам нужно будет настроить «силовую константу», чтобы соответствовать масштабу вашей модели. В зависимости от вашей математической способности вы сможете рассчитывать хорошую постоянную стоимость во время планирования; другие мудрые просто экспериментируют сначала, и вы найдете хорошее значение.

2. После вычисления общих сил на каждом круге (пожалуйста, посмотрите на проблему n-body, если вы не знаете, как это сделать), переместите каждый круг вдоль вектора его общей расчетной силы, используя длину вектор как расстояние до перемещения. Здесь вы можете обнаружить, что вам нужно настроить значение постоянной силы. Сначала вам понадобятся движения с длиной, которая составляет менее 5% от радиуса сферы.

3. Движения на шаге 2 будут вытолкнуть круги с поверхности сферы (потому что они отталкивают друг друга). Теперь переместите каждый круг назад на поверхность сферы, в направлении к центру сферы.

4. Для каждого круга вычислите расстояние от старого положения круга до его нового положения. Наибольшее перемещение расстояния - это длина движения для этой итерации в основном цикле.

Продолжайте повторять через основной цикл на некоторое время. Со временем длина движения должна становиться все меньше и меньше, поскольку относительные положения кругов стабилизируются в соответствии с вашими критериями. Выйдите из цикла, когда движение ноги упадет ниже некоторого очень небольшого значения.

Tweaking

Вы можете обнаружить, что вы должны настроить расчет силы, чтобы получить алгоритм сходиться на растворе. Как вы настраиваете, зависит от типа результата, который вы ищете. Начните с настройки постоянной силы. Если это не сработает, вам может потребоваться изменить значения массы вверх или вниз. Или, возможно, изменить показатель радиуса в вычислении силы. Например, вместо этого:

f = (k * m[i] * m[j])/(r * r); 

Вы можете попробовать это:

f = (k * m[i] * m[j])/pow(r, p); 

Тогда вы можете экспериментировать с различными значениями р.

Вы также можете поэкспериментировать с различными алгоритмами для первоначального распределения.

Количество проб и ошибок будет зависеть от ваших целей дизайна.