Нарисуйте все воксели, которые проходят через 3D-линию в пространстве 3D-вокселей.

Я хочу нарисовать трехмерную вокселизированную линию, то есть найти все воксели, через которые проходит линия. 3D брезенхем всегда пропускает некоторые воксели. Как показано на рисунке, воксели, сгенерированные 3D-брезенхэмом, не могут полностью содержать линию между начальным вокселем и целевым вокселем.

3D-линия, сгенерированная 3D-брезенхэмом

Алгоритм по этой ссылке: Алгоритм рисования 4-связной линии может решить мою задачу на 2D-плоскости, но мне не удалось улучшить ее до 3D.


3d graphics voxel bresenham
person yaqian chen    schedule 20.03.2019    source источник
comment
Несколько раз назад я использовал этот документ, чтобы сделать что-то вроде того, что вы пытаетесь сделать: cs.yorku.ca/~amana/research/grid.pdf   -  person Pierre Baret    schedule 20.03.2019
comment
Большое спасибо. Я внес некоторые изменения в этот метод в статье и решил свою проблему.   -  person yaqian chen    schedule 21.03.2019
comment
использовать DDA проще, быстрее, чем брезенхем, и легко переносим на любую размерность. Также взгляните на это: DDA + субпиксельная точность   -  person Spektre    schedule 21.03.2019
comment
Ваша цель — нарисовать все воксели, проходящие через 3D-линию?   -  person Peter O.    schedule 22.03.2019
comment
@ПитерО. да. Я решил свою проблему следующим методом. Если у вас есть лучшее решение, я попробую его.   -  person yaqian chen    schedule 22.03.2019
comment
@Spektre Большое спасибо за ваш ответ. Я пробовал, но этот метод будет генерировать некоторые ячейки, не пересекающиеся с линией.   -  person yaqian chen    schedule 22.03.2019

Ответы (1)


arrow_upward
0
arrow_downward

Метод в ссылке Пьера Баре может решить мою проблему. Когда линия проходит только вершины определенного вокселя, посещать ли текущий воксель — очень расплывчатый вопрос, поэтому я внес небольшие изменения в метод. Когда два или более значений в tMaxX, tMaxY и tMaxZ равны, воксели, сгенерированные описанным в статье методом, выглядят так, как показано на рис. Я сделал небольшое изменение, чтобы сгенерировать результат в b. Более нормальное состояние показано на c, где сравниваются линии, созданные с помощью 3D-брезенхэма и этого метода соответственно.

введите здесь описание изображения

Код, реализованный С++:

void line3D(int endX, int endY, int endZ, int startX, int startY, int startZ, void draw){
int x1 = endX, y1 = endY, z1 = endZ, x0 = startX, y0 = startY, z0 = startZ;
int dx = abs(x1 - x0);
int dy = abs(y1 - y0);
int dz = abs(z1 - z0);
int stepX = x0 < x1 ? 1 : -1;
int stepY = y0 < y1 ? 1 : -1;
int stepZ = z0 < z1 ? 1 : -1;
double hypotenuse = sqrt(pow(dx, 2) + pow(dy, 2) + pow(dz, 2));
double tMaxX = hypotenuse*0.5 / dx;
double tMaxY = hypotenuse*0.5 / dy;
double tMaxZ = hypotenuse*0.5 / dz;
double tDeltaX = hypotenuse / dx;
double tDeltaY = hypotenuse / dy;
double tDeltaZ = hypotenuse / dz;
while (x0 != x1 || y0 != y1 || z0 != z1){
    if (tMaxX < tMaxY) {
        if (tMaxX < tMaxZ) {
            x0 = x0 + stepX;
            tMaxX = tMaxX + tDeltaX;
        }
        else if (tMaxX > tMaxZ){
            z0 = z0 + stepZ;
            tMaxZ = tMaxZ + tDeltaZ;
        }
        else{
            x0 = x0 + stepX;
            tMaxX = tMaxX + tDeltaX;
            z0 = z0 + stepZ;
            tMaxZ = tMaxZ + tDeltaZ;
        }
    }
    else if (tMaxX > tMaxY){
        if (tMaxY < tMaxZ) {
            y0 = y0 + stepY;
            tMaxY = tMaxY + tDeltaY;
        }
        else if (tMaxY > tMaxZ){
            z0 = z0 + stepZ;
            tMaxZ = tMaxZ + tDeltaZ;
        }
        else{
            y0 = y0 + stepY;
            tMaxY = tMaxY + tDeltaY;
            z0 = z0 + stepZ;
            tMaxZ = tMaxZ + tDeltaZ;

        }
    }
    else{
        if (tMaxY < tMaxZ) {
            y0 = y0 + stepY;
            tMaxY = tMaxY + tDeltaY;
            x0 = x0 + stepX;
            tMaxX = tMaxX + tDeltaX;
        }
        else if (tMaxY > tMaxZ){
            z0 = z0 + stepZ;
            tMaxZ = tMaxZ + tDeltaZ;
        }
        else{
            x0 = x0 + stepX;
            tMaxX = tMaxX + tDeltaX;
            y0 = y0 + stepY;
            tMaxY = tMaxY + tDeltaY;
            z0 = z0 + stepZ;
            tMaxZ = tMaxZ + tDeltaZ;

        }
    }
    draw(x0, y0, z0);
}

}
person yaqian chen    schedule 21.03.2019