Real Flash Quake

[Baker]

Supposedly vis is just a database, the functions Mod_DecompressVis and Mod_LeafPVS in the engine source read it and Mod_PointInLeaf does a node walk.

Needless to say, if it were easy -- then it wouldn't have taken someone like John Carmack to make Doom and Quake. Quake's BSP format was a fairly big deal back at the time --- or so I've read.

[MadGypsy]

I'm not looking for easy, bro. Any game engine, even 2d, can become incredibly complicated. The fact is, all the other languages I know are a snoozefest of possibilities. I never got my php/sql projects off the ground because it was too easy. Once my mind put all the pieces together, my interest went to 0. If this project becomes a,b,c it will get left in the dust too. I'm either heavily challenged or completely bored.

That's why I like spikes way of answering. I know the truth is in his reply but the reply is generally a cipher in itself. When he told me how to walk geometry I was like "sigh...what the hell does this mean" but I knew the answer was there if I just applied myself. So, I applied myself and one thing is for sure, I figured out what he was saying.

This project is at the very cusp of my skills for programming and figuring. Pray it stays that way if you ever want to see it completed. Cause as soon as my brain has no more questions, this is a done deal. The only thing that could override that is having so much progress that I simply can't let go.

[Spike]

that screenshot I gave earlier uses an opengl extension called 'bindless textures'. combined with 32bit indexes and another nvidia-only extension that allows the textures to not be dynamically uniform, the program is able to draw the ENTIRE world in a SINGLE draw call. which is quite awesome.
it has 4 modes. the default uses multidrawindirect (which is kinda cheating) to avoid the use of that nvidia extension so it works on ati too - this mode generates a new index list whenever the camera moves into a different leaf, so has pvs culling but no frustum checks. another still uses that nv-only extension, but is otherwise the same (and actually runs a bit slower because of it). another walks the bsp tree frustum culling a bit like quake (but lightmaps are still hangled purely by glsl), and the last mode just draws the entire world without and pvs or frustum.
each method has its advantages, and only one is cpu limited...
I'd give you the sourcecode, but I'm too selfish to share my crappy code. I even got it to play nq demos and connect to nq servers!

turns out that using just the pvs is sufficient to reduce overdraw.
even drawing the entire world is a speedup compared to doing frustum checks.
they might have helped at one point, especially if you're uploading new lighting each frame, but on modern gpus its easier and faster to just batch everything than it is to do any complex bsp walking.

essentially, figure out the current leaf. if its different from the last frame decompress that leaf's pvs, walk the leaf list (ignoring leafs not in the pvs, thread it if possible) and insert the indexes from the various surfaces (note: surfaces can be in multiple leafs - use a framecount in the surface structure to avoid doing it twice per surface per frame) into their respective batch (pre-generate these based on texture state or whatever). draw the surfaces using that new index list. easy, right?

this means you'll need to do something fancy with glsl / hlsl for lightmaps, but then you'll need to be using that if you want sky or water to work properly / efficiently too.
if you have no lit support, you can just build each of the 4 possible per-surface lightmaps into each channel of a texture and select from that using a dotproduct of a flat varying set up within your vertex shader according to a styles uniform table and a vertex attribute that says which styles to use.
alternatively if you want lit support, you can rebuild the light map any time its changed all on the cpu, copying and scaling huge amounts of data and then syncing with the gpu to upload in a really slow way. gah, what am I saying? just use up to four lightmap textures. or three if you want to be weird.

with texture arrays, huge maps like jam6_deya devolve into just 8 'shapes', aka pre-subdivided batches. meaning you can draw the entire world in just 8 draw-calls. yay batching.
you can also use texture arrays with lightmaps. this improves batch sizes too, and means you don't have to be so careful.

... you ARE atlasing your lightmaps, right?..

the root node is the node that contains the entire world. its plane is the first that splits that unlimited volume into two. with enough nodes (and thus planes), the various convex volumes gradually take form.
you can determine the volume of a leaf by walking the nodes up to the root. each node defines a plane that may define a boundary to the leaf (many will be irrelevant and outside the volume - ones that do not cross the geometry defined by clipping away the other planes are ones that do not contribute to that individual volume). of course, this isn't relevant to rendering.
if you want to do tracelines, 'all' you need to do is to walk the bsp tree, each time you cross a node you walk both of the children to see if that point is solid. if its solid on the far side but not the near side then you have an impact. if your ordering is correct, you'll stop after finding only one solid, but will still need to walk many non-solid leafs (dependingg on how many there are, but the starting point should always be empty, so always at least one).
there are 3 root nodes for each submodel. the format of the nodes is slightly different - tree 0 uses the renderable nodes, the others use the clip-only nodes instead. the planes are the same, but the clipnodes uses straight contents values instead of leafs, iirc.
alternatively you can use trisoup collision, but this will break clip brushes. third-party physics engines will generally demand trisoup, and will build their own kdtree from it, which is why ode/bullet in fte doesn't understand clip brushes.
q2 is much cleaner in this regard, the bsp tree is merely used as a way to find brushes quickly, with actual collisions being brush-based instead.

anyway. textual dihorea over.

[MadGypsy]

wow, that's all something I need to read when I get behind a computer... and I definitely will.

What do you mean by atlasing? I push each complete face lightmap into a vector (array...). When I go to texture the face the lightmap is added as another layer over the miptex with a second set of UV's.

in this way my lightmaps are essentially sealed in concrete (ie no blinky blinks) but face_t[n] corresponds to lightmapImage[sameN]

[Spike]

https://en.wikipedia.org/wiki/Texture_atlas

[MadGypsy]

Well, I have things working better. I had an epiphany on how the vislist works and I was able to alter that copy/paste code to what it really should be.

The main trouble was in this copy/paste line
if(visisz[v] == 0)
i += 8 * visisz[v+1]
v += 1

That line would be great if I unpacked all the bits but, I'm dealing with bytes
if(visisz[v] == 0)
i += visisz[++v]

All that is saying (due to run length encoding) is "skip ahead by the value after the 0". Since the loop begins a new iteration after, this it is technically positioned for the leaf right after the skips by this, which can be expressed in the formula

i = self
skip (self + RLEval -1/*for self*/) + 1 //next self to check
but expressed easier with
i += RLEval

It still doesn't entirely work but it doesn't work much better than it didn't before . I am convinced my findLeaf script is wrong and when I get it right vis is going to pop together like legos. I'm convinced it's wrong because one part of my map tells me I am in leaf 0 and that is impossible.

For non developers (As I understand it):



The vislist contains a slew of numbers from 0 to 255. If the number is 0 it will be followed by a number that says how many 0's to consider. 0 means invisible. However, if you get a number larger than 0 you then need to check it's value against bitmasks, 8 of them to be specific. The masks are 1,2,4,8,16,32,64,128. Which if you add all that together is the 255 max value I stated earlier. Lets say the vis value was 131. This would mean &1 = true show leaf, &2=true show next leaf, &4,8,16,32,64 = false do not show the next 5 leafs, &128 = true show leaf.

It's quite interesting how they went about designing this. You can manage all (in my case) 65 leaves from any of the 65 leaves with only 600 values. 65*65 is far far more than 600. This is a very compact way of doing things. However if I completely unpacked the vislist I should have 65*65 values. Luckily bitmasks make unpacking unnecessary.

I would like to add that, if my information is in some way wrong, and you're one of the smarties that can correct me. Correct me. My understanding of this is mostly based on observation. I have a high QQ for this stuff but, I am still wrapping my mind around BSP In generaI.

Alternately, if I am absolutely correct that would be nice to know too. Then I can chalk off this function as not part of any problems.

[Spike]

pvs is 1-based.
leaf 0 is the 'solid' leaf, and is invisible to all other leafs, yet can see into all others.
there are multiple paths through the bsp tree to this leaf, violating the whole convex thing, it may not contain any surfaces.
as a result, the decompressed pvs starts with leaf 1, not leaf 0.

[MadGypsy]

That's how I know my findLeaf script is incorrect. It keeps telling me that my little water/sky area is leaf 0 and that's impossible. I found part of the answer in webgl Quake and fitzplus

n = dot(playerXYZ, leaf_t[current]->normal)-leaf_t[current]->dist
n = (n>-1)?node_t[current]->children[0]:node_t[current]->children[1];

however I have no idea what to do with n after that. A simple Math.abs(n) is not enough. I found a script that subtracted 1 like -(n+1) but that doesn't seem to be giving me the proper results.

This is my exact current script. I'm a little lost on findLeaf or maybe I'm still lost on leaf manager?.. I have gone over it a thousand times and I don't see what else can be done there.


close, but where is my ramp?


I've checked and double , triple, infinitupley checked my numbers


It's not just the ramp though. Where is my hallway and the corners of my room?


This is pretty much the entire slew of information and control points of my situation. If anybody has an aHa! moment I would love to hear it. I am pretty stuck, albeit less stuck than before. Believe it or not this is a dramatic improvement to the results that I was getting. I was getting something more similar to the opposite. Like, let's say a ramp, corners and hall but, no room (more or less), but that is to be expected when you skip 8*RLEZeroCnt of leaves LOL! I told y'all I don't know what I'm doing . I didn't know what I was doing when I started writing QC tutorials either. I didn't know what I was doing when I first did all that radiant base file modification. Hell, I didn't know what I was doing, period, when I came here. This will all eventually come together. Actually, this BSP shit is the hardest part. Wait til I have to write some game code and watch how fast this starts growing. I will burn through that code.

[MadGypsy]

Hah hah, I can't believe this really exists! I googled it as a joke.

BSP technical details for Dummies

[Baker]

the root node is the node that contains the entire world. its plane is the first that splits that unlimited volume into two. with enough nodes (and thus planes), the various convex volumes gradually take form.

Sounds like each node is just a plane test ...

For plane Z -- probably defined by a point and perpendicular vector ... but my gut instinct without looking is that it instead uses a code # for the plane type.

A) Is on this side? YES --- goto node 1
B) Is on this side? NO --- goto node2 instead

[MadGypsy]

I'm bringing this entire project to HaXe. I'm starting from a different point though.

point 1: decompress lzma files (my chosen "pak") but, this only covers half of point 1 because I intend to manage an lzma zip against a game manifest. I have always hated how models are in the QC. A simple xml manifest could be used to describe each map from rotation to non-bmodel child entities. I expect to get point 1 done pretty quick. I have made similar scripts numerous times. Actually, my parsing delimiters stuff has almost the exact code. It's for regular zip, though and it's in pure AS3. I'm probably going to gut and port.

Once I can load my "pak" against the manifest. I can go back to getting my BSP correct. It will be my third script (lol). HaXe supports typedef and structs so, I'm basically going to rewrite bspfile.h, for starters.

I feel like, if I get my language closer to C(flavor) this will all probably come together easier. Funny side note: I'm halfway tempted to rename the entire quake source to originalName.hx, click build and simply fix every single error. There will be thousands of them but, I don't think I can get closer to success than a port guided by my syntax checker and eventually my stack which will more than likely give me error messages that I understand. That's the bottom line right? Bring it all to another language. Maybe I'll work on both ways. The way I would like things to work and spending ?weeks changing uint to UInt as well as other such mind numbingly boring things of a similar nature.

//Instead of making another post, I'll just add this here

I just got a haxe (pronounced hex btw) project up and running and I used a basic example from the away3d engine to test all these targets before I start writing a bunch of code. The Neko target is really fast (well at least for this example) and works great. The c++ target is soooooooooo friggin slow the first time. That's why I'm rambling here for a minute. I'm waiting for it to finish. Hopefully that will work great and my final target will be android. If all 3 compile properly, it is a done deal that haxe is my "new" language. Actually, I need to do a flash build too, but, I already know that will work cause, this is not my very first time playing with haxe. It is my first time adding an entire game engine API into the mix. Away3D is in haxe too. So is the starling 2d engine which was used for many many mobile games and may be best known for angry birds. I can get interoperability between these two engines. I've done it before on a small scale. Starling could sit on top of away 3d (visibly) giving me a pretty sweet engine for the hud/items/etc layer. I don't know if I will really go that far but, I could.

[easily 10 or so minutes have passed]
....wow, still building the c++ source. It hasn't even started compiling yet.

[MadGypsy]

Neko port works, flash port works... both the c++ and android ports seem to compile fine but the resultant file crashes upon execution. I know this is a "me" problem in some way. I say this because I can't find anywhere on the internet where someone else is having the same problem.

I'm sure this has something to do with me still being a bit of a noob with lime/nme/openfl/whatever else is being used. Neko and flash aren't bad working targets though. Neko covers all your major OS's as long as the neko VM is installed and flash is going to look sweet on the webpage I'm eventually going to have to build. I absolutely still intend to get the c++ and android versions working but, for now I can probably just roll with neko til I get enough results where making these other ports is even necessary. NOTHING compiles faster than neko, not even flash. It's basically instantaneous. My last build took 1.037.... seconds. Flash is at least 2 or 3 seconds. Everything else is a couple-few minutes.

oh wait... I may have fixed the c++ build. I ran "prompt>lime setup windows" and it dl/installed vis studio 2010 express. I then built the project again. It was using gcc to compile, now it's using vis studio which is apparently recommended...maybe the result will be proper. I'll let you know in like 20 mins (sigh). It's rebuilding the source again.

Edit: I also learned that when compiling to the c++ target. It does not use any of the flash gl stuff. It doesn't use the flash VM at all. That's really nice. My exe's and apk's will be real device "root" level executables, as opposed to captive environments wrapped in such.

[MadGypsy]

tadaa! The upper left is flash (obv) and the other 2 are neko.exe and cpp.exe. I think the window with current focus is the cpp.exe. I got them mixed up while opening all of them.

[MadGypsy]

...and just for fun. Here is the html5 version.


if I size the browser down to this size or smaller I get the 60fps back.


I still can't get android to work but, I'm getting closer. That shell on the left in my last image is a direct build (ie...bypass flashDevelop). Maybe it will work. I'll find out when it finishes in 400 years.

Obviously this 60fps stuff is hardcoded into one of these apis. I'm getting max 61 fps even if I open 10 instances. I have yet to open enough instances to slow down any of the other instances.

[MadGypsy]

OK so the tally is in. Haxe is fuckin hard! That's not discouraging me but, it is very true. The complexity comes in that, even with openfl, it is not as "simple" as porting flash code to haxe. Mainly this has to do with loading external files. I have to write the c++ way, the neko way, keep the flash way for flash and I'd be willing to bet I have to write an android way. There is no one-script-to-rule-them-all for file management. At least none that I can find. However, when I get past this part I should be able to work directly through openfl for all targets. Unfortunately this part is a very hard part because it isn't as simple as writing 4 ways to load the files. I also have to write 4 ways to manage the files from a "zip". Basically, this is a big octopus and I need to work my way up each tentacle before I can share a trunk.

There is also a steep learning curve for optimization. Generally you don't start off worrying about optimizations but, I can save a lot of future time by knowing things like haxe.io.Bytes is faster than openfl.utils.ByteArray, and other such things. Of course, there is nothing easy about writing a complete bsp parser but, trying to do it in a language that can be ported to like 10 platforms makes it infinitely harder. I'm pretty sure when I'm denoobed on haxe I will probably be able to program in any language. Mainly because you aren't getting jack done in haxe if you don't understand the languages you are going to be porting to. I've read like 5 or 6 c++ tutorials to get something done in haxe. Which is akin to watching a 3dsmax video to learn how to model in blender... it bes like that, sometimes.