Генерация точек равномерно на сфере

Question

Я заинтересован в создании точек, которые «равномерно» (и не случайно) распределены по сфере, очень похоже на углубления мяча для гольфа или вершины шестиугольников на футбольном мяче.Существуют ли четко определенные алгоритмы для этого?

Примечание: я знаю, что точки на самом деле не «равномерно» распределены по сфере, но они распределены таким образом, что распределение точек выглядит одинаково с любогонаправление, которое смотрит прямо в любую из точек - это то, что меня интересует.

Answer 1

Выберите u, v случайным образом из [0,1].2πu - долгота.asin (2v-1) - широта.Только две случайные переменные и никаких отклонений.

Кстати, у моей коллекции ссылок новый адрес: http://bendwavy.org/sphere.htm

И я скопировал его в http://cgafaq.info/wiki/Evenly_distributed_points_on_sphere

Answer 2

Подразделение октаэдра и нормализация вершин впоследствии дает очень хорошие результаты. Смотрите здесь для более подробной информации. У Пола Бурка есть много интересного.

Вот некоторый psuedo C ++ код, который я написал за пять минут:

/* Assume 'data' initially holds vertices for eight triangles (an octahedron) */
void GenerateSphere(float radius, std::vector<Vector3f>& data, int accum=10)
{
    assert( !(data.size() % 3) );

    std::vector<Vector3f> newData;

    for(int i=0; i<data.size(); i+=3){
        /* Tesselate each triangle into three new ones */
        Vector3f centerPoint = (data[i] + data[i+1] + data[i+2]) / 3.0f;

        /* triangle 1*/
        newData.push_back(data[i+0]);
        newData.push_back(data[i+1]);
        newData.push_back(centerPoint);
        /* triangle 2*/
        newData.push_back(data[i+1]);
        newData.push_back(data[i+2]);
        newData.push_back(centerPoint);
        /* triangle 3*/
        newData.push_back(centerPoint);
        newData.push_back(data[i+2]);
        newData.push_back(data[i+0]);
    }
    data = newData;
    if(!accum){
        /* We're done. Normalize the vertices,
             multiply by the radius and return. */
        for(int i=0; i<data.size(); ++i){
            data[i].normalize();
            data[i] *= radius;
        }
    } else {
        /* Decrease recursion counter and iterate again */
        GenerateSphere(radius, data, accum-1);
    }
    return;
}

Этот код будет работать с любым многогранником, состоящим из треугольников против часовой стрелки, но лучше всего использовать октаэдры.

Answer 3

Я однажды попробовал следующий алгоритм:

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

Это работает до тех пор, пока точность не нарушает однородность.Результирующие точки образуют фигуры, сродни геоду.

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

Answer 4

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

сначала распределить точки случайным образом и равномерно по сфере.Я подробно расскажу об этом на http://elenzil.com/progs/randompoints.я полагаю, что мой метод, по крайней мере, такой же эффективный, как и в Worlfram.

секунда, «ослабьте» распределение, рассматривая точки как систему частиц, где каждая частица отталкивает каждую другую частицу.трудность заключается в том, чтобы убедиться, что система не стала нестабильной, и решить, когда остановиться.у меня есть пример этого здесь: http://elenzil.com/progs/separate к сожалению, это были дни, прежде чем я включил исходный код в свои проекты, так что код потерян.

Answer 5

Вот простой способ сделать это.

1. Случайно, выборка из единичного куба, [0, 1] ^ 3

2. Тест на включение в сферу. Отклоните, если точка выборки не находится в сфере диаметра 1, которая содержится в единичном кубе, и перейдите к шагу 1.

3. Нормализуйте точку, находящуюся на поверхности сферы, проецируя точку наружу от центра сферы.

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

Answer 6

в зависимости от ваших потребностей http://iquilezles.untergrund.net/www/articles/patchedsphere/patchedsphere.htm может работать хорошо не точно равномерно, но очень быстро для вычисления.

Answer 7

Хотя в этой статье говорится о случайном выборе точек на сфере, речь идет также о рисовании точек из равномерного распределения с одновременным учетом характеристик сферы. Я думаю, что это все еще достойное чтение для вашего вопроса:

http://mathworld.wolfram.com/SpherePointPicking.html