Quake 3 BSP Loader

I wasn’t sure which forum to post this in, but I figured General is just as good as any.

I have started the long process of porting my Quake 3 BSP/PK3/MD3 loader/viewer to use the jME engine, in the hopes that the 3rd time will be the one where I find an engine with long-term support. :slight_smile:

Anyway, to get to the point, the program I have loads almost all of the info stored in the bsp files, including quadratic patches, BSP brushes, nodes, leaves, leaf faces, splitter planes and clusters, lightmaps, etc. It also parses shader script files, and handles the multi-texture and texture animation shaders (had a hard time figuring out the skybox shaders). The shaders work for animated textures in the MD3 files and in the BSP files. I also have code for rendering all these, using ByteBuffers and glDrawElements.

I have all this code sitting in a dev.java.net project that I was a part of, but haven’t done much with in about a year. I was wondering how it might be used to both contribute to jme, and get me interested in working on this with an actively developed engine.

Thanks, and the java.net project site is: http://arkanae.dev.java.net


This is so awesome you are the man.  I was wondering though why you think the performance fluctuates, like when the program is first loaded, the fps is around 30 for me and then it jumps up when i go into the rooms… I mean I don't really think that it should ever go 30fps since I have loaded way more triangles than that and had it go in the high hundreds…  There just seems to be a bottleneck somewhere, maybe its the java interpreter im not sure, but if thats the case we really need to figure out JIT compiling for the jme engine so we can make this optimal.  Anyways can you tell me where the code is for this, im really excited to see how I can load in .bsp files into the engine.  Thanks a lot man.


Ok, well wait no longer:


The first row in that list has a link to the jnlp file to run it via web start.


Be sure to use the dropdown for the renderer and choose "Partition LWJGL", otherwise things will crash and it's a pain to find that config file (the app is set up to only run the properties selector if no config file exists).

Anyway, you can choose one of the two maps from the first screen (I recommend the second, since the first one was done by me a loooong time ago).  You can also Load a pk3 file, for example the pak0.pk3 from the quake 3 demo.  If you do that, be patient and a new menu will pop up with the maps available in that pk3, and then be REAALLY patient until the rendering window shows up with the map in view.

Once I get some feedback from this, I'll discuss the structure of the BSP tree used and some other questions regarding performance.

Oh, and once again, be kind to my server, if it's downloading slow, it's probably due to traffic, so don't stop the download and try again right away.  :slight_smile:

Hm… I didn't get the property selector at all. Wouldn't it be nice to just enable by default so you can test different resolutions and such?

Welcome, Bakchuda. Your work looks good (I gave your link a glance, and flipped through the code a bit). I should mention that some people have played with BSP loaders here as well, Cep21 and I believe batman.ac. They had some success, but the biggest problem they ran into was having BSPNode extend Spatial (there was a big memory issues, Spatial is adding a ton of overhead that’s not needed). I would suggest chatting with those folks. Renanse and I have talked about ways to minimize the impact of Spatial, but it’s been a long time coming. So, it may come down to just putting the heads down and trudging through. I know Cep21 had some ideas to resolve memory and BSP, but we never did formalize them.

Anyways, keep that in mind as you play with jME and your work. Make sure you post ideas, troubles, breakthroughs, we all love to hear progress or help where we can.

As far as contributing it to jME, it will come down to producing something you are happy with. Showing us, making changes here and there (bug fixes, improvements, etc). Then when everyone is happy we can give it its own jmex package.

Again, welcome! Cant wait to see your first results.

Hi Bakchuda,

sorry for posting late, couldn’t respond quicker…

In fact, as Mojo stated, I had also started a small porting project for q3 bsp files, only to see, how it could fit into jME. I experienced the problems Mojo mentioned, because in a first attempt I stupidly converted each triangle into a single Spatial - which is no good idea.

After that, Mojo and Renanse planned to carefully to a refactoring of some of the parts of jME to make the codebase more stable for what is yet to come and after that is completed we wanted to talk about indoor map rendering again. I had some ideas, but I am currently “on hold”, waiting for the next release since I would like to wait for the stable code base.

Anyway, here’s some of the results I found:

As already meantioned, you don’t want too many Spatials, so it would be best to keep the numbers low. Could be done by combining triangles, which use the same textures and reside in the same bsp region into one Spatial. But, could also be done by putting the whole map into one single special type of jME scenegraph node.

The bsp information is only used for the pvs, i.e. finding out which region you’re currently at. It is a data structure not related to the jME tree.

Hope, that helps. Have a look here :http://www.jmonkeyengine.com/jmeforum/viewtopic.php?t=1149

From what I recall about the quake 3 bsp (been a while, but I’m digging back through it) is that the BSP info consists of structures that could be used as spatials…they are used for visibility and collision detection, so I would assume you could use them to represent the “volume” each part of the map takes up, and I am pretty sure that those structures have a lot fewer triangles.

I’m going to try to convert what I have to use jme in this way, and I’ll post my findings.

IIRC, the BSP is used to quickly find the region where the cam is currently in and then you use the PVS information to recursively iterate through all other regions. That is where you have to break up with the “normal” scenegraph behaviour in jME.

Therefore my idea was to have a map root node, which contains all the other information in the map. If a render call is made, the bsp information is used to find the region and then you have to manually call the render function of the appropriate regions. So we have MapRootNode and Region at least as new classes.

A single Geometry can only hold one set of textures (thinking of multitexturing), which means the texture of the triangle plus the light map. If a region consists of more than one “background” texture, you’d have to split it into several Geometry objects anyway. That’s why I mentioned that you may have to sort triangles of a region according to the texture(s) they are using.

Yes, that’s right, i looked through the code some more and now I see what you are talking about.

I can play around with the idea of a couple new classes (how does PartionedRootNode and Partion sound?) and extend Renderer and LWJGLRenderer to test this out.

I did see already that we would have to split up the region into multiple geometries, but that information is already stored in the quake 3 bsp (in the Face lump). So I think if I put the face information into a TriMesh, that should work out.

I think a bigger issue with using TriMesh is what you mentioned in your other post about memory. Since the Quake 3 data is set up to allocate one big list of floats to represent the verticies of all faces, maybe a SharedBufferTriMesh so that many TriMeshes uses slices of the one big vertex buffer (which is what I ended up doing).

Thanks for this feedback, after doing all this by myself for so long, it’s great to have somebody to bounce ideas around

One of my findings so far is that it is not easy to create content that shows up in jme by using only vertex buffers, a lot of information is derived from having an actual array of floats for verticies.

Yaaay, I got the polygons to load correctly…now it's on to aligning the texturecoords correctly…

I'll put a screenshot up when theres, um, something more recognizeable :slight_smile:

BTW, I had to make a bunch of hacks to have the system recognize a new Renderer…I just made a subclass of LWJGLRenderer to handle the PartitionMeshes differently, and it took a lot of changes to some pretty hard-coded if statements.  Any plans to make this less painful?

Yeah, probably around the time the jogl port officially goes in… 

Please try to be kind to my web server, but here is a screen shot of what I have so far, loading a test bsp file.  I have everything but the shaders working, and the only custom code I have in the renderer subclass I wrote is to handle buffer strides and geometry other than GL_TRIANGLES.

I hope to have this up as a JNLP app in the next couple days.


Wow, its looking good already!

well done. :smiley:

SICK!!!  I CANT WAIT!  :smiley:

As for the property selector, yes, will go back in and set it to always allow choosing.  I was doing so much testing at one point I just turned it off to get to the engine faster :slight_smile:

The source code is something I am more than willing to donate to the jme project.  A lot of the BSP loading code is straight out of various tutorials I have found on the net about the Quake 3 map file format, but a large portion of it (like the shader script interpreter) is original.  I will get a zip file ready of the source so that you all can look over it, but I would really like to clean it up so that it can be used as a part of the jme project.

Right now I have things set up using a subclass of LWJGLRenderer.  One of the problems I had with the standard LWJGL renderer is that the glDrawElements calls were hard coded to assume tightly packed verticies (stride of 0) and to use GL_TRIANGLES.  This is fine for using the TriMesh class to build byte buffers, but the quake 3 map files actually contain this data all ready to go, but with some different assumptions (some faces use GL_TRIANGLE_FAN, some GL_TRIANGLE_STRIP, etc).  I don't think it would be very hard to modify LWJGLRenderer to handle variable strides and geometry types.

As for the BSP tree itself, the data structure is a bit unique, mostly to save on space (visibility data is store in idividual bits, extracted using bitwise operators!)  To make this into something easier to use, some people (myself included) would have to make some tools to convert some user friendly information into this format, since it works really well.  And eventually, some kind of bsp compiler would be really nice, so that you can make a bsp tree from a scenegraph.

I don't know how useful the shader language is to anybody, it's pretty much just for use with the quake 3 tools, since it is a completely made up (and sometimes nonsensical) language.  It allows you to do some nice looking things, but most of the stuff it does can be accomplished with a lot better performance simply using multitextures and vertex programming.  But I wanted to get things as complete as I could, so, there it is.

By the way, I also have and MD3 loader I am going to work on porting to JME.  It uses the same shader parser, so that, for example, the rail gun model actually has the glowing energy cell showing up.

Thanks for the feedback everybody.

I too was pushed right past the selector.  So if you could add one… :stuck_out_tongue:

As for the BSP code, that sounds awesome.  Once you get things to a point where you are happy sharing it, please let us know.

Ok, for those who didn’t get it to work the first time, the BSP Test should work again. http://snipehunt.net/devel/

It will now always show the properties dialog, so you can choose the Partition LWJGL renderer.

Hey there, I am wondering how the bsp tree is stored in memory…? I mean if you use java's TreeSet<E> generic red black tree then you can get guaranteed log(n) time for adding/removing/searching nodes.  I was reading this article about bsp trees since, im totally unfamiliar with them, and apparently collision detection is cheap as f*ck with bsp… http://www.gamasutra.com/features/20000330/bobic_03.htm

Just thought I would share that with you, you probably know more than me about it though but anything to help right?


Collision detection is pretty cheap with this BSP, and I already have code that can handle it that has worked in the past, I just need to port it over into the jme framework.

As to how it's stored, it's not using any high level data structures like TreeSet.  It's all pre-compiled by the map builder, so there's no feasible way to add or remove nodes right now.