It's time for another episode of Allcaps' Assumptions.

I have a very small map I made for testing. It has 13 leafs. The visibility lump for this map is 26 bytes.

This means that in order to store a bit for every leaf, each leaf's PVS will be two bytes of data. (13 bits needed, add 7 then divide by 8 to find the number of whole bytes needed) Right?

Parsing the lump, should each byte be interpreted as a char, or an integer? I know that it represents bitfields, but no matter how I read this in it doesn't look at all like I expect it to going by various docs I can find. Reading the small map above's vis lump as chars gives me this:

10 2 10 10 2 2 10 10 0 1 15 15 0 1 7 11 0 105 0 0 123 10 34 115 112 97

This looks kind of okay. So I break it into two-byte sets (since each leaf's pvs is 13 bits, needing two bytes) and get:

10 2
10 10
2 2
10 10
0 1
15 15
0 1
7 11
0 105
0 0
123 10
34 115
112 97

Now it looks less okay. How can there be a set that is 0 0? How can there be 0 105? So there's a hundred and five zero bytes in that set? I'm going wrong somewhere pivotal and I'm really lost as to where. 

For the thousandth time, tronyn's is NOT BSP2, it's 2PSB.

Heh.

heh heh heh.

:-D 

Yeah, people ARE still talking about rmq even if this bug is the only legacy. Congratulations. :-) 

 

Heh. =)

=) 

Honestly though, gb, why bully me? 

I've work on a few other things, like some groundwork for lightmap import, and BSP2 support, but I'm still totally lost on deciphering this PVS information.

C# has a bitarray datatype that would make this really easy to implement if I could just get the PVS data read and decompressed.

I feel like real doofus for asking but does anyone have a page with detailed information on reading and handling the PVS information? I've found so many pages that are just "here's how you do it" with a lump of C source that is a web of pointers, bitshifting, and variables with undescriptive names.

This is the last feature needed before the real fun stuff can begin. 

My only question is will it support bsp2 :>

Sorry, don't have a link for what you're looking for. 

leafs (... leaves ...) contain an arbitary offset into the compressed pvs lump. They don't start at predictable places, and the qbsp is free to overlap duplicate sequences.
Breaking it into 'two byte sets' is thus a silly thing to do.
That said, I have no idea why you would find a 0 0 pair anywhere in the data unless it was unused, which is a possibility. 

I think you're correct in identifying that the pairs after 7 11 do not parse correctly according to the decompression algorithm. Can you recheck the code that's getting the block of visdata? You may want to check if you get the same data by following the design of the original code more closely: reading each leaf, taking the visdata offset from that leaf, and then reading a pair of chars from that offset. 

Leaf 0's pvs is always "everything is visible". Is this handled as a special case, or does the vis lump contain an entry for leaf 0 as well? 

Okay.

This is the compressed vis data for my testing map.

VisData: (26 bytes) 255 10 255 2 207 10 207 10 243 2 243 2 255 10 255 10 0 1 15 255 15 0 1 7 205 11

I'm inclined to think it's good, because when I use it the level renders correctly. I currently do not decompress the zeros, I can get away with this on my test map because the leafs are so few. Every leaf renders correctly except for 9 and 11, which are the only two leafs to include a zero in their PVS. Fair enough, since I'm not handling the zeros yet. I'm about to, and want to make sure my thinking is correct.

Take leaf 9. It's compressed vis bytes are 0 1. Each leaf takes two bytes of data to have enough bits. After the 0 1 in the data is a 15.

To make sure I'm thinking correctly, this really means it's vis bytes would be 0 15, because it means 0 (starting zero run) 1 (add one zero, done with zero run) 15 (non-zero, add directly).

Is this correct? 

To make sure I'm thinking correctly, this really means it's vis bytes would be 0 15, because it means 0 (starting zero run) 1 (add one zero, done with zero run) 15 (non-zero, add directly).

Is this correct?

You are correct in how vis leaf 9 works. I think it does expose a problem though.

You started by calculating that each vis leaf requires 2 bytes to store the visibility data of 13 leaves. You then reported that this makes the size of the vis data 26 bytes. The crucial point is that 26 bytes is the size of the uncompressed vis data. We would expect the compressed data to be different in size, otherwise why bother with compression?

To complicate things further, there's an issue of map size. Your map, being unusually small, exposes a rare corner case of the compression algorithm. Leaf 9 has compressed vis data 0 1 15 - that's three bytes. Even if the other 12 leaves lacked zero bytes, that's 12 * 2 bytes + 3 bytes = 27 bytes. The algorithm has made the "compressed" data longer than the uncompressed data!

The important takeaway lesson is that we can't calculate how long the compressed vis data for a map will be from the number of leaves. In most real levels it will be smaller that the uncompressed data, in small box levels it will be larger. The only way to get the correct size is to parse it byte by byte from the file. 

That's what I was doing. Sorry I didn't mean to make it look like I was trying to calculate the size of the compressed data using the number of leafs. It was only by chance that the number of bytes in the compressed data was twice the number of leafs, and that it was two bytes to store the uncompressed pvs for a leaf.

Great to have reassurance though :)

I think I may have it working, it works correctly on my tiny test map, and on Stalwart, a small-ish dm map. Time to get some bigger maps and see what happens. 

Alright, I have PVS working for the world itself. How are models other than 0 (the world) handled? Does a leaf's PVS information contain info on every leaf, or just leafs in the same bsp tree/model? It looks like it's just in that leaf's own tree/model.

Are other models just handled via frustum checks? 

pvs is used for 3 things:
bsp rendering (drawing less bsp faces).
entity(net) culling (reducing network traffic).
gamecode logic (trivially skipping tracelines).

the renderer might want to cull submodel faces based upon view position.
or it might batch the entire submodel and be faster if it doesn't then try to split it up.

the other two situations generally use positions relative to the world. submodel pvs information is likely not useful, although it might be handy if both positions are expressed relative to a submodel. such cases are both awkward and minor, as well as infrequent.

phs next? :P 

Don't think Quake 1 has PHS, I think Q2 started that :)

My implementation is still a little buggy, due to way I'm handling, or rather not handling, the different models in the .bsp.

Do I need to find the player's position in every model's bsp tree? Right now I find what leaf the player is in starting at node 0, which works but all the non-map models (like doors and elevators and the like) are not marked as visible.

Should my process be to walk the bsp tree for every model? Does each model's head node point to a tree that can be traversed using the .bsp's planes, and end in a leaf for that model? Does this mean there's going to be a set to render for each model in the level?

I was so focused on getting pvs for the map working, I didn't stop to consider what the overall process should be. 

QuakeWorld has phs.

submodels are completely separate objects from the world model. they all have their own separate bsp tree. they just share indexes. node 0 is generally the world's root node, but you'll need to check the submodel lump to find the root node for all the others (and ideally world too).

the view leaf(s) will be different for each submodel, if only because each model has a unique set of leafs.
Either way, translations and rotations would mean you'd need to find the view leaf for each submodel even if they shared leafs. 

That should be simple now that I have methods for vis/pvs and bsp walking going. Good to know I wasn't barking up the wrong tree.

I think I'll actually take a break from this and work on lightmaps. Graphics stuff is more fun. :) 

I've got the tree1.mdl and I'm trying to give it a BBOX size of

setsize(self, '-8 -8 -16', '8 8 96');

But in game the bbox is the size of the entire mesh, which makes it too big to use.

What am I missing here? I've experimented with different collision types and so on and nothing seems to work. Does the mesh itself have some sort of hidden flag forcing this behaviour from qc?

I've got other objects which allow me to manipulate their physical dimensions no problem using the same method... 

This is probably not the issue, but have you made sure the setsize call happens after you set the model? 

I was being 'clever' and made a little subroutine to do that for me, leaving it at the end.

So... with that out of the way, if I do this on purpose will the collision be both the right size and orientation? 

I was being 'clever' and made a little subroutine to do that for me, leaving it at the end.

So... with that out of the way, if I do this on purpose will the collision be both the right size and orientation? 

bbox+bbox collisions fully comply with specified sizes. bbox+bsp collisions have weird offsets+discrete supported sizes.

bbox+bsp collisions are based upon the mins of the bbox rather than the origin of it.
this means you can increase the mins_z to move it up off the ground or decrease it to let droptofloor/walkmove/etc position the base of the tree further into the ground or whatever. it also means you should really try to keep the x+y set to the size of a bsp hull.

if you never use walkmove/droptofloor/tracebox/movetogoal/pushers on your tree then none of that applies and you can set the size to whatever the smeg you want. movetype_none, woo. 

That clarifies things. I've noticed different behavior in different engines as well, but it all seems to come back to not knowing the ins and outs of the format to begin with.

Let's do map objects!