Trying to implement BSP - any advice? (Solved)

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

+- Wings 3D Development Forum (http://www.wings3d.com/forum)
+-- Forum: Wings 3D (/forumdisplay.php?fid=1)
+--- Forum: Programming (/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 02:13 PM

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 09:28 PM

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 10:51 PM

Thanks for sharing nemyax

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

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.