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 ); }

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

Hi UfoZ,
Thank you very much, it''s clear now.