Anyone got any experience with BSP tree compilers?

Bit of a long shot this, but for something laser related I am working on I need some code to compile BSP trees from polygon lists.

I found some stuff on the ID software site used in their map editors, but that is kind of complicated and I would like something written to be easier to follow.
Because the models will usually not be that big, I probably don't need strictly optimal performance and a relatively low time complexity in the compile would be good (The tree is being used more for back face culling and bounding box tests then anything else).

I also have a simple 2D tree used in projection space to do the final hidden line removal, but that is less of a problem then the model space tree as it is typically far smaller (And what I have works well enough).

C++ would be good, but really I can convert from anything.

Anyone know of something floating around the net?

Regards, Dan.

what do you need basically? simple 3D engine code would do? if so, I can find some resources for you, written in C or C++, with any primitive you would need to get some simple 3D engine working

Hi shrad,
The engine itself does not look like being that much of a problem to pen (but code that someone else debugged is always good), the thing that is kicking my arse is finding a good way to partition the tree in a manner that both gives reasonable balance, does not split too many polygons AND runs in something a lot better then O(n!) which is what an exhaustive search takes.

I have the usual "Graphics black book", The "Gems" series and books on the appropriate algorithms and matrix math for both Quanterion and Sucessive rotation based approaches, but other references would be appreciated.

At the moment I have a simple minded approach based on balancing at each level with a penalty for splitting a polygon, but it does not produce particularly optimal trees (and is still O(n^2 log n)).

A lot of the freely available 3d engines out there seem to assume very high polygon counts, that the painters algorithm will remove hidden surfaces at scan conversion time and the availibility of an accelerated graphics pipeline (None of which really apply here, pulling polygons back out of a hardware pipeline is slower then computing them on the main processor).

My current code is reatively simple (BSP tree, bounding spheres for initial frustum cull, cull the reverse spaces courtesy of the tree and clip lines by using a 2D BSP in screen space), but the initial generation of the tree is painful....

Ideally I want to support import of models from 3ds, blender and a few other common 3d mesh editors, but most of these do not natively produce the desired tree structure in the file, hence the need to do it at load time.
The Radiant code from ID Software has a BSP compiler but it is complicated by the fact that that engine uses PVS sets (which are just not worth it for this (Besides calculating PVS data is for an arbitary geometry is **HARD**)).

If you know of anything dealing with the GENERATION of bsp trees (as opposed to their use once you have them) it would be really appreciated!

Regards, Dan.

Do you intend to use this for laser display, or computer graphics?????

Hi dan,

sadly I think I only have simple code references and they wouldn't be useful for what you want to do (nothing referring to these trees)

Laser display application, and thanks Shrad.

Turns out that the GLRadiant quake editor had some code from ID Software that could be re tasked to do more or less what is needed, as this is going out under the GPL, I could just crib it wholesale.

I now have the BSP compiler working (O(n^2 log n)), so better then O(n!) at the cost of about 15% excess polygon splits, and it now loads 3DS files and outputs appropriately clipped polygons for the area within the frustum from any camera position and geometry, still need to do some colour and vertex normal stuff for scene lighting.

Next up is to graft on the 2D plane clipper to handle the occlusion culling (hidden surface is handled by the tree automatically) at which point I will have a C++ vector of 2D polylines to pass to the point mapping code (Which should be **interesting** to write).

Basically I got fed up with the limitations of .ILDA and decided I wanted something that would actually work with more complex 3d scenes, and that could support stereoscopy and the like.

A picture of an earlier version which did simple minded 3d, before I decided that I needed a full 3d architecture....

Attachment 19130

The ILDA files are from the old ILDASwap FTP and I suspect have some copyright issues so they will NOT be distributed with the code....

There is also a sequence editor (Each sequence is a tree made up of sequencers, effects (geometry and colour (including time varying geometry and colour)) and frame source nodes that actually contain the raw images (And I suppose there will have to be a camera node now to handle the 3D data coming up the stack). Midi/OSC control is a work in progress, the basic infrastructure is there, but more work is needed (Nasty, Racy multi threaded crap).

Going to try and have something more or less working for UKLEM at the end of the month, we will see.

Regards, Dan.

is there a possibility to reuse an existing 3D engine and rewrite the drawing functions?

Not particularly easily...

The modern engines tend to assume that openGL will do all the math for you, including a lot of the polygon based stuff, which is clearly not the case for us (Theoretically you can pull transformed vertex data back out of hardware accelerated open GL but in practise it is not worth the pain).

Further modern engines tend to assume that some overdraw is acceptable and that the painters algorithm will solve it when rendering, which is manifestly not the case for our usage.

We are actually better off doing the polygon extraction the other way around to a conventional engine (most do it depth first so the front features overpaint any overdraw from earlier polygons, we want the front objects first so we can clip the rear objects exactly against them in 2D projection space).

Besides a lot of the obvious game engine choices have very high world compilation costs (PVS sets are expensive to compute), and often require a closed world (PVS compilation again). Not somewhere I am prepared to go for this application.

Regards, Dan.

Dan, this is exciting stuff!!
I wrote a 3D engine but point based and not polygon based!
I did however, write the whole thing from the ground up without using OpenGl.
See a demo of it here:
http://www.youtube.com/watch?v=cpD6atERJ08
What you see is realtime navigation through a simple 3D world (without hidden line removal etc.).
There is also a 4D object called a tesseract that came up in discussions on PL before, you may remember.

Hope you enjoy the demo.
Matthijs

Gl is naff all use for laser based things.

I have point based working, but you cannot easily do hidden line or occlusion culling without higher level information (normals and information about what constitutes a surface mainly), so I tore it up and am doing a polygon based one that should hopefully allow all that.

4D hypercubes/tori and the like make for some cool (and VERY weird) geometric primitives, but one piece of 4D that is seriously useful is the Quaternion, there is a way to map a click and drag on a circle to a rotation in a very intuitive way (Got it from one of the Graphics Gems books, cannot claim any originality there, but it is very neat in the camera controls).

Regards, Dan.