Archived

This topic is now archived and is closed to further replies.

jgarcia

Binary Calculation

Recommended Posts

jgarcia    122
Hi All, I''m woking with an excellent tutorial of Digiben about loading the bsp Quake 3 files. I have a big trouble only in one section, the section of the visibility. In this file the visibility information is saved in bytes numbers when each bit of the byte represents one cluster. I don''t understand the algorithm : int visible = pBitsets[currentCluster*bytesPerCluster + ( testCluster/8 )] & (1 << (testCluster & 7)) this part to be more precise: " & (1 << (testCluster & 7)) " Why ????? Examples please !!! I''m sending all the text of the tutorial. Regards, J.Martin =============================================== (Text extracted from "Digiben" tutorial) [...] The visibility information is comprised of a bunch of bitsets that store a bit for every cluster. This is because the information is so massive that this way makes it faster to access and a smaller memory footprint. There is only one instance of this structure, but you calculate how much needs to be read in bytes by either: numOfClusters * bytesPerCluster, or minute the size of 2 integers from this lumps length. The pBitsets is then dynamically allocated and stores the calculate bytes. This is probably one of the most confusing parts about the .bsp file format, the visibilty. I will try and explain the important parts of it and give some code. struct tBSPVisData { int numOfClusters; // The number of clusters int bytesPerCluster; // Bytes (8 bits) in the cluster''s bitset byte *pBitsets; // Array of bytes holding the cluster vis. }; To demonstrate what a cluster is and what we need to do with it, let''s start with a simple example. When rendering, first we want to find which leaf we are in. Once again, a leaf is an end node of the BSP tree that holds a bunch of information about the faces, brushes and the cluster it''s in. Once that leaf is founding by checking the camera position against all of the planes, we then want to go through all of the leafs and check if their cluster is visible from the current cluster we are in. If it is, that means that we need to check if that leaf''s bounding box is inside of our frustum before we draw it. Say we have cluster A, B and C. Each cluster is stored as a bit in bitset. A bitset is just a huge list of binary numbers next to each other. Each cluster has their own list of bits that store a 1 or a 0 to tell if the cluster in that bit is visible (1) or not visible (0). Since there is most likely more than 32 clusters in a level, you can''t just use an integer (32-bits) to store the bits for all the clusters. This is why there are many bytes assigned to each cluster. So, here is how it works: With cluster A, B and C, here is how they would be represented in binary (a bitset): ABC 000 Each 0 represents a slot that is assigned to a cluster. Let''s assume that: - Cluster A can see cluster B and not C - Cluster B can see cluster A and C - Cluster C can see cluster B and not A Below is a representation of each one of their bitsets: - A 110 - B 111 - C 011 Does that make sense? Notice for A there is a 1 in the first slot which means it can see itself, and also in the second slot which means it can see cluster B. The last slot is a 0, which tells us that cluster A can not see what''s in cluster C because some walls or whatever are blocking it. This is where the good spatial partition speed comes in. If you are in the very bottom corner of the level in a small little room, you just cut out probably 95% percent of the polygons that need to be rendered because you can only most likely see the cluster that is right outside of that room. To test if a cluster is visible from another cluster, there is obviously going to have to be some bit-shifting and other binary math involved. The basic algorithm to test a cluster against another cluster is as follows: int visible = pBitsets[currentCluster*bytesPerCluster + ( testCluster/8 )] & (1 << (testCluster & 7)) If the result of visible isn''t 0, then the testCluster can be seen from the currentCluster. We divide and % (mod) by 8 because we are using bytes which are 8 bits. Basically, the first part is indexing into the array of clusters to find the correct bitset, then we do a binary & (and) with the cluster we are testing to get the result. Here is some basic code to do a cluster to cluster test: inline int IsClusterVisible(tBSPVisData *pPVS, int current, int test) { if(!pPVS->pBitsets || current < 0) return 1; byte visSet = pPVS->pBitsets[(current*pPVS->bytesPerCluster) + (test/8)]; int result = visSet & (1 << (test & 7)); return ( result ); }

Share this post


Link to post
Share on other sites
em5    122
if the & is your problem, it means bitvise and.
example: 7 & 3
7 is 1011 in bits and 3 is 0011

Now put the first number on top of the other
Look at the vertical pars of ones and zeros
Draw a line below, if any of the two ones and zeros in a par is not 1, put 0, else 1.

1011
0011
----
0011

I hope I understood the point of your problem

Share this post


Link to post
Share on other sites
jgarcia    122
em5,
Thanks for your help but I know how works the "&" operator and the "<<" operator.
Tell me if I''m wrong, the result of 1<<5 is "100000", am I rigth ?.

My question is Why he do that ? ... Why we need to made that calculation, How it works FOR THIS CASE ?...

Regards,
J.Martin

Share this post


Link to post
Share on other sites
Neosmyle    144
quote:
Original post by em5
if the & is your problem, it means bitvise and.
example: 7 & 3
7 is 1011 in bits and 3 is 0011

Now put the first number on top of the other
Look at the vertical pars of ones and zeros
Draw a line below, if any of the two ones and zeros in a par is not 1, put 0, else 1.

1011
0011
----
0011

I hope I understood the point of your problem




Actually 7 is 0111

Share this post


Link to post
Share on other sites
UfoZ    150
int visible = pBitsets[currentCluster*bytesPerCluster + ( testCluster/8 )] & (1 << (testCluster & 7));

It''s just a way of finding a bit in a string of bytes.

There are 8 bits in a byte, right? So first he divides the value by 8 to find which byte in the string to check. Then he checks for the appropriate bit, this is done by a binary and. He masks out the lower 3 bits of the address to do an effective modulo 8, and using a left shift moves a single bit into the appropriate position. Then he checks if this bit is set with a binary and.

(the compiler will probably optimize the /8 into a >>3 anyway)

Share this post


Link to post
Share on other sites