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

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

1 голос
/ 20 марта 2019

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

3D line generated by 3D bresenham

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

1 Ответ

0 голосов
/ 21 марта 2019

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

enter image description here

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

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);
}

}
...