Как сделать разделение пространства чайника в Юте?

Question

Имея дело с преобразованием патчей Безье в треугольники, мне нужно сделать бинарное пространство, чтобы нарисовать спроецированные треугольники, используя алгоритм Painter.

Я реализовал алгоритм из Википедии с большой помощью по математике.

Но это делает дерево Чарли Брауна! То есть большинство узлов имеют одну ветвь полностью пустую. Вся стратегия неверна. Поскольку чайник по существу сферический, вся форма находится только на одной "стороне" любого конкретного компонента треугольника.

Поэтому я думаю, что мне нужны плоскости разбиения, расположенные больше как ядро ​​яблока: все они проходят через линию оси Y. Но я вроде как схожу с книги, понимаешь? Какой лучший способ разделить чайник?

Вот мой генератор BSP-дерева. Он использует другие функции, размещенные в связанном вопросе.

Изменить: Дополнительное жонглирование, чтобы избежать переполнения. Полная программа доступна здесь (требуется mat.ps и чайник). Числовой вывод показывает глубину строящегося узла дерева.

% helper functions to insert and remove triangles in lists
/unshift { % [ e1 .. eN ] e0  .  [ e0 e1 .. eN ]
    exch aload length 1 add array astore
} def
/shift { % [ e0 e1 .. eN ]  .  [ e1 .. eN ] e0
    aload length 1 sub array astore exch
} def


/makebsp { % [ triangles ]  .  bsptree
    count =
%5 dict  %This is the tree node data structure
<</P[]/PM[]/plane[]/front[]/behind[]/F<<>>/B<<>>>>
begin

    dup length 1 le{ % If 0 or 1 triangles
        dup length 0 eq { % If 0 triangles
            pop           %    discard
        }{                % If 1 triangle
            aload pop /P exch def  % put triangle in tree node
        }ifelse
    }{ % length>1

    shift /P exch def  % P: Partitioning Polygon (triangle)
    P transpose aload pop
    [1 1 1] 4 array astore % make column vectors of homogeneous coords
    /PM exch def

    [ % Compute equation of the plane defined by P
      PM 0 3 getinterval det
      [ PM 0 get PM 2 get PM 3 get ] det
      [ PM 0 get PM 1 get PM 3 get ] det
      PM 1 3 getinterval det 3 mul
    ] /plane exch def

    % iterate through remaining triangles, testing against plane, adding to lists
    /front [] def
    /behind [] def
    { %forall  [P4 P5 P6] = [[x4 y4 z4][x5 y5 z5][x6 y6 z6]]
        /T exch def
        T transpose % [[x4 x5 x6][y4 y5 y6][z4 z5 z6]]
        {aload pop add add} forall % (x4+x5+x6) (y4+y5+y6) (z4+z5+z6)

        plane 2 get mul 3 1 roll % z|C| (x) (y)
        plane 1 get mul 3 1 roll % y|B| z|C| (x)
        plane 0 get mul          % y|B| z|C| x|A|
        plane 3 get add add add  % Ax+By+Cz+D

        0 le { /front front
        }{ /behind behind
        } ifelse
        T unshift def
    } forall

    %front == ()= behind == flush (%lineedit)(r)file pop

    % recursively build F and B nodes from front and behind lists
    %/F front makebsp def
    front currentdict end exch
        makebsp
    exch begin /F exch def
    %/B behind makebsp def
    behind currentdict end exch
        makebsp
    exch begin /B exch def
    /front [] def
    /behind [] def

    } ifelse
currentdict end
} def

Выход:

Answer 1

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

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

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

Answer 2

Я не совсем выполнил октре, но я изменил конструктор bsp-tree, чтобы использовать явный список плоскостей, который я заполнил плоскостями, выровненными по оси, разрезая пространство -4

/planelist [
    0 .2 4 { /x exch def
        [ 1 0 0 x ]
        [ 1 0 0 x neg ]
        [ 0 1 0 x ]
        [ 0 1 0 x neg ]
        [ 0 0 1 x ]
        [ 0 0 1 x neg ]
    } for
] def

Постскриптумная программа доступна здесь (требуется mat.ps).

Светло-зеленый артефакт является результатом "предварительного просмотра", показанного во время строительства BSP. После создания последующие страницы (изображения) рисуются быстро и без артефактов, поскольку камера вращается вокруг чайника.

Соединение корпуса с носиком и ручками (не показано под этим углом) все еще нуждается в работе.

С bsp лучше себя вести, отбраковка задней грани не является строго необходимой. Но это делает предварительный просмотр приятнее.

Answer 3

Другой способ улучшить BSP для этого изображения - использовать иерархическую декомпозицию. Чайник - это не просто набор более изящных поверхностей, у него есть некоторые поверхности, которые описывают тело, некоторые другие, которые описывают ручку, носик, крышку (, дно?).

Таким образом, первые несколько уровней дерева должны быть частями верхнего уровня. Ручка находится перед или позади тела? Носик перед телом? Ответы на эти вопросы были бы полезным руководством для алгоритма художника.