Trying to implement BSP - any advice? (Solved)

[nemyax]

In an export plugin that I'm writing, I want to implement face slicing and sorting, based on a BSP tree. If I use the e3d mesh format, building a tree-like structure is easy enough:

Code:

bsp([H|T]) ->
    {Front,Back} = split(H, T),
    {H,{bsp(Back),bsp(Front)}};
bsp([]) ->
    nil.

However, I'd prefer to process the WEDS instead, because its splitting tools are free and produce valid meshes that have good normals and import well. My problem is that I can't branch the recursion with a WEDS and have to essentially iterate over it. What would you suggest I use to make the BSP tree? Should it even be a tree in this case, or would I be better off using a proplist or something to store the branching?

[nemyax]

I ended up with this:

Code:

walk([], Order, [], Data) -> % Data is {We,SplitPlaneNormal}
    {Order,Data};
walk([], Before, [H|T], Data) ->
    walk(H, Before, T, Data);
walk(A, Before, After, Data) ->
    {F,L1,L2,Data0} = distribute(A, Data),
    walk(L1, [F|Before], [L2|After], Data0).

It seems to flatten the "tree" just the way I need.

[micheus]

Thanks for sharing nemyax

[nemyax]

Turns out that this "in-place" sorting (which is in essence reverse pre-order traversal) produces adequate results only on very simple objects. I now create a linked structure instead:

Code:

branch_out(Fs, We) ->
    {_,A,We0} = distribute(Fs, We),
    branch_out(orddict:new(), [A], We0).
branch_out(Lookup, [], We) ->
    {flatten_tree(Lookup, []),We};
branch_out(Lookup, [{F,L,R}|T], We)->
    {F0,A0,We0} = distribute(L, We),
    {F1,A1,We1} = distribute(R, We0),
    branch_out(
        orddict:store(F, {F0,F1}, Lookup), [A0,A1|T], We1);
branch_out(Lookup, [_|T], We) ->
    branch_out(Lookup, T, We).

I still haven't found a suitable flattening principle though.