Trying to implement BSP - any advice? (Solved)

Trying to implement BSP - any advice? (Solved) - Printable Version

+- Wings 3D Development Forum (https://www.wings3d.com/forum)
+-- Forum: Wings 3D (https://www.wings3d.com/forum/forumdisplay.php?fid=1)
+--- Forum: Programming (https://www.wings3d.com/forum/forumdisplay.php?fid=7)
+--- Thread: Trying to implement BSP - any advice? (Solved) (/showthread.php?tid=922)

Trying to implement BSP - any advice? (Solved) - nemyax - 10-29-2014

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?

RE: Trying to implement BSP - any advice? - nemyax - 01-08-2015

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.

RE: Trying to implement BSP - any advice? (Solved) - micheus - 01-08-2015

Thanks for sharing nemyax

RE: Trying to implement BSP - any advice? (Solved) - nemyax - 01-12-2015

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.