Frustum Culling – Is this ok?

[PakzParticipant]

I was not really able to understand how frustum culling works with the way I keep finding it described or coded online. They use a AABB system and I really do not understand this yet.

My own take on it right now is to use a point in triangle approach and find visible meshes using that way. I coded this test to see if it would work and it seems to do.

Am I right that this is usable also?

 

Monkey

#Import "<std>" #Import "<mojo>" ' Frustum Culling ' Every tile would be a mesh. The frustum culling would ' find what is visible in the camera and what not would not ' be drawn. ' Using std.. Using mojo.. Class MyWindow Extends Window ' Our camera angle Field angle:Float Method New() End method Method OnRender( canvas:Canvas ) Override App.RequestRender() ' Activate this method ' Our base coordinates ' and left side and right side coordinates ' of triangle Local b:Vec2i Local l:Vec2i Local r:Vec2i ' base is the center of the screen b.X = 320 b.Y = 240 ' left and right side coordinates l.X=b.X+(Cos(angle-Pi/4)*250) l.Y=b.Y+(Sin(angle-Pi/4)*250) r.X=b.X+(Cos(angle+Pi/4)*250) r.Y=b.Y+(Sin(angle+Pi/4)*250) ' Draw our frustrum lines canvas.DrawLine(b.X,b.Y,l.X,l.Y) canvas.DrawLine(b.X,b.Y,r.X,r.Y) ' Here we draw our map. The green tiles ' would be visible and the red ones would ' not be visible ' For Local y:Int=0 Until 20 For Local x:Int=0 Until 20 If pointintriangle2d(x*32,y*32,b.X,b.Y,l.X,l.Y,r.X,r.Y) canvas.Color = Color.Green Else canvas.Color = Color.Red End if canvas.DrawRect(x*32,y*32,32,32) Next Next ' Move the camera angle If Keyboard.KeyDown(Key.Left) Then angle-=.1 If Keyboard.KeyDown(Key.Right) Then angle+=.1 canvas.Color = Color.White canvas.DrawText("Use cursor left and right to move camera angle.",0,0) ' if key escape then quit If Keyboard.KeyReleased(Key.Escape) Then App.Terminate() End Method End Class ' Here is the point in triangle collision function ' by RaGR (Ralph G. Roeske). from blitzbasic.com ' px,py = pixel x and y to test collision with ' x1,y1,x2,y2,x3,y3 = The triangle points Function pointintriangle2d:bool(px:Float,pz:Float, x1:Float,y1:Float,x2:Float,y2:Float,x3:Float,y3:Float) Local bc:Float,ca:Float,ab:Float,ap:Float,bp:Float,cp:Float,abc:Float bc = x2*y3 - y2*x3 ca = x3*y1 - y3*x1 ab = x1*y2 - y1*x2 ap = x1*pz - y1*px bp = x2*pz - y2*px cp = x3*pz - y3*px abc = Sgn(bc + ca + ab) If (abc*(bc-bp+cp)>=0) And (abc*(ca-cp+ap)>=0) And (abc*(ab-ap+bp)>=0) Return True Return False End Function Function Main() New AppInstance New MyWindow App.Run() End Function

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97

#Import "<std>" #Import "<mojo>"   ' Frustum Culling ' Every tile would be a mesh. The frustum culling would ' find what is visible in the camera and what not would not ' be drawn. '   Using std.. Using mojo..     Class MyWindow Extends Window   ' Our camera angle Field angle:Float   Method New()   End method Method OnRender( canvas:Canvas ) Override App.RequestRender() ' Activate this method ' Our base coordinates ' and left side and right side coordinates ' of triangle Local b:Vec2i Local l:Vec2i Local r:Vec2i ' base is the center of the screen b.X = 320 b.Y = 240 ' left and right side coordinates l.X=b.X+(Cos(angle-Pi/4)*250) l.Y=b.Y+(Sin(angle-Pi/4)*250) r.X=b.X+(Cos(angle+Pi/4)*250) r.Y=b.Y+(Sin(angle+Pi/4)*250) ' Draw our frustrum lines canvas.DrawLine(b.X,b.Y,l.X,l.Y) canvas.DrawLine(b.X,b.Y,r.X,r.Y) ' Here we draw our map. The green tiles ' would be visible and the red ones would ' not be visible ' For Local y:Int=0 Until 20 For Local x:Int=0 Until 20 If pointintriangle2d(x*32,y*32,b.X,b.Y,l.X,l.Y,r.X,r.Y) canvas.Color = Color.Green Else canvas.Color = Color.Red End if canvas.DrawRect(x*32,y*32,32,32) Next Next ' Move the camera angle If Keyboard.KeyDown(Key.Left) Then angle-=.1 If Keyboard.KeyDown(Key.Right) Then angle+=.1 canvas.Color = Color.White canvas.DrawText("Use cursor left and right to move camera angle.",0,0) ' if key escape then quit If Keyboard.KeyReleased(Key.Escape) Then App.Terminate() End Method   End Class       ' Here is the point in triangle collision function ' by RaGR (Ralph G. Roeske). from blitzbasic.com ' px,py = pixel x and y to test collision with ' x1,y1,x2,y2,x3,y3 = The triangle points Function pointintriangle2d:bool(px:Float,pz:Float, x1:Float,y1:Float,x2:Float,y2:Float,x3:Float,y3:Float)     Local bc:Float,ca:Float,ab:Float,ap:Float,bp:Float,cp:Float,abc:Float     bc = x2*y3 - y2*x3     ca = x3*y1 - y3*x1     ab = x1*y2 - y1*x2     ap = x1*pz - y1*px     bp = x2*pz - y2*px     cp = x3*pz - y3*px     abc = Sgn(bc + ca + ab)     If (abc*(bc-bp+cp)>=0) And (abc*(ca-cp+ap)>=0) And (abc*(ab-ap+bp)>=0) Return True Return False End Function   Function Main() New AppInstance New MyWindow App.Run() End Function

[coconParticipant]

Frustum culling is based on simple collision detection. The math in it are only the means to calculate the shape’s volume and then perform collision detection tests and figure if a point is inside this volume.

Your implementation in terms of frustum culling is right, also you take it to the next level which is about hierarchical organization of the scene. Here you use spaces of fixed size which looks like a grid.

One idea for using space partitioning:

Without space partitioning: your scene would look like this: sceneobjects = [1,2,3,4,5,6,7,8,9,10] every object is placed in a linear fashion and there's no degree of scene organization. if you want to find which objects are inside the frustum you would have to waste 10 iterations With space partitioning: your scene would look like this: sceneobjects = [ "A" : [1,2] , "B" : [3,4,5] , "C" : [6,7,8] , "D" : [9,10] , ] now if you imagine that the frustum hits spaces A + B you would simply iterate these two spaces and collect the objects found in them.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

Without space partitioning:   your scene would look like this: sceneobjects = [1,2,3,4,5,6,7,8,9,10]   every object is placed in a linear fashion and there's no degree of scene organization.   if you want to find which objects are inside the frustum you would have to waste 10 iterations     With space partitioning:   your scene would look like this:   sceneobjects = [ "A" : [1,2] , "B" : [3,4,5] , "C" : [6,7,8] , "D" : [9,10] , ]   now if you imagine that the frustum hits spaces A + B you would simply iterate these two spaces and collect the objects found in them.

This way of splitting up the scene would work fine in simple terms, I would not see something wrong about it. Most of the gaming industry has settled to nested space partions like binary/quadtree/octree. It means basically that a space contains many other spaces (in terms of hierarchical organization) – resulting to an actual tree structure. Each one is supposed to be an alternative way of managing the data structures. For example imagine that you would travel in a desert (which the environment is in the majority much empty) and then suddenly you would enter a small cave where it has lots of stuff in it. This would be a good case of using nested space partition.

Here is an example of space partitioning:

Java

/* OpenProcessing Tweak of *@*http://www.openprocessing.org/sketch/10796*@* */ /* !do not delete the line above, required for linking your tweak if you upload again */ // Quadtree containers demo // Click to make a point. As soon as more than binSize points are // inside of a quad, it subdivides. // Right-click to reset final static float dotSize = 2; final static int binSize = 5; final static color[] colors = new color[4]; Box b; FuzzyBin q; DLA dla1; void setup() { size(600, 600); frameRate(30); //smooth(); colors[0] = color(127,0,0); colors[1] = color(0,127,0); colors[2] = color(0,0,127); colors[3] = color(127,127,0); b = new Box(1, 1, width, height); q = new FuzzyBin(b, dotSize); dla1 = new DLA(q, binSize); dla1.addPoint(width/2, height/2); } void draw() { q.drawMe(); fill(0,0,0,0); if (mousePressed) { if (mouseButton == LEFT) { dla1.addPoint(mouseX, mouseY); ellipse(mouseX, mouseY, 4*dotSize, 4*dotSize); } else if (mouseButton == RIGHT) { q = new FuzzyBin(b, dotSize); dla1 = new DLA(q, binSize); background(255); } } stroke(0); } class Box { float Xl, Yl; float Xh, Yh; final static float zero = 1e-20; Box(float X_1, float Y_1, float X_2, float Y_2) { // Orient so (Xl,Yl) and (Xh,Yh) are min/max extent, respectively Xl = min(X_1, X_2); Xh = max(X_1, X_2); Yl = min(Y_1, Y_2); Yh = max(Y_1, Y_2); } boolean pointInside(float x, float y) { return x > Xl && x < Xh && y > Yl && y < Yh; } // Compute the intersection of the given ray (where x=R0x+Rdx*t and // y=R0y+Rdy*t) with this box; return two t values, Tnear and Tfar, // which give the entry and exit values of t (> 0) float[] intersectRay(float R0x, float R0y, float Rdx, float Rdy) { float Tnear = -1e30; float Tfar = 1e30; // First, check slab in X. if (abs(Rdx) < zero) { // Ray is parallel to X, but starts outside. Fail. if (R0x < Xl || R0x > Xh) { return null; } } else { float Ta = (Xl-R0x)/Rdx, Tb = (Xh-R0x)/Rdx; float T1 = min(Ta,Tb); float T2 = max(Ta,Tb); if (T1 > Tnear) Tnear = T1; if (T2 < Tfar) Tfar = T2; if (Tnear > Tfar) return null; if (Tfar < 0) return null; } // Then check slab in Y. if (abs(Rdy) < zero) { // Ray is parallel to X, but starts outside. Fail. if (R0y < Yl || R0y > Yh) { return null; } } else { float Ta = (Yl-R0y)/Rdy, Tb = (Yh-R0y)/Rdy; float T1 = min(Ta,Tb); float T2 = max(Ta,Tb); if (T1 > Tnear) Tnear = T1; if (T2 < Tfar) Tfar = T2; if (Tnear > Tfar) return null; if (Tfar < 0) return null; } // If we have survived this far, the test passed. return new float[] {Tnear, Tfar}; } // Divide this box down into 4 quadrants Box[] quarter() { return quarter(0); } // d = boundary "fuzziness" size Box[] quarter(float d) { float Xm = 0.5*(Xl+Xh); float Ym = 0.5*(Yl+Yh); Box[] quads = new Box[4]; quads[0] = new Box(Xm-d, Yh, Xh, Ym-d); quads[1] = new Box(Xl, Yh, Xm+d, Ym-d); quads[2] = new Box(Xl, Yl, Xm+d, Ym+d); quads[3] = new Box(Xm-d, Ym+d, Xh, Yl); return quads; } void drawMe() { rect(Xl, Yl, Xh-Xl, Yh-Yl); } } // QuadTree class. Subdivide it at will. class QuadTree { Box b; QuadTree[] children; int level; static final int maxLevel = 8; QuadTree(Box b) { this.b = b; children = null; level = 0; } QuadTree(Box b, int level) { this.b = b; children = null; this.level = level; } // Divide into 4 smaller quadtrees. // If this exceeds the recursion limit, it will just return null. QuadTree[] divide() { if (children == null && level < maxLevel) { children = new QuadTree[4]; Box[] b2 = b.quarter(); for(int i = 0; i < 4; ++i) { children[i] = new QuadTree(b2[i], level + 1); } } return children; } // Draw - recursively - the entire quadtree. void drawMe() { b.drawMe(); if (children == null) return; for(int i = 0; i < 4; ++i) { stroke(colors[i]); children[i].drawMe(); } } boolean isDivided() { return children != null; } // Find the smallest of the child quadtrees which contains the given point. // If none are found, return null. This won't subdivide any further. QuadTree getSmallestIntersect(float x, float y) { if (children == null) { if (b.pointInside(x,y)) { return this; } else { return null; } } for(int i = 0; i < 4; ++i) { QuadTree q = children[i].getSmallestIntersect(x, y); if (q != null) { return q; } } return null; } } // Basically QuadTree class, but with fuzzy boundaries. class FuzzyQuadTree extends QuadTree { float delta; FuzzyQuadTree(Box b, float delta) { super(b); this.delta = delta; } FuzzyQuadTree(Box b, int level, float delta) { super(b, level); this.delta = delta; } // Divide into 4 smaller quadtrees. // If this exceeds the recursion limit, it will just return null. QuadTree[] divide() { if (children == null && level < maxLevel) { children = new QuadTree[4]; Box[] b2 = b.quarter(delta); for(int i = 0; i < 4; ++i) { children[i] = (QuadTree) new FuzzyQuadTree(b2[i], level + 1, delta); } } return children; } } // A FuzzyQuadTree that can contain points in each quad. class FuzzyBin extends FuzzyQuadTree { ArrayList x_points = new ArrayList(); ArrayList y_points = new ArrayList(); FuzzyBin(Box b, float delta) { super(b, delta); } FuzzyBin(Box b, int level, float delta) { super(b, level, delta); } // Add a point to this quad if it's inside, _and_ to any other child // quads that contain it. Return the undivided child quads which // contains it. // If this point is outside of the quad, return null. ArrayList addPoint(float x, float y) { ArrayList tips = new ArrayList(); if (b.pointInside(x, y)) { x_points.add(x); y_points.add(y); // We've hit an undivided quad; we're done. if (children == null) { tips.add(this); return tips; } for(int i = 0; i < children.length; ++i) { FuzzyBin c = (FuzzyBin) children[i]; ArrayList tips_new = c.addPoint(x, y); tips.addAll(tips_new); } } return tips; } int countPoints() { return x_points.size(); } // Divide into 4 smaller quadtrees. // If this exceeds the recursion limit, it will just return null. // Any points contained are passed on. QuadTree[] divide() { if (children == null && level < maxLevel) { children = new QuadTree[4]; Box[] b2 = b.quarter(delta); for(int i = 0; i < 4; ++i) { children[i] = (QuadTree) new FuzzyBin(b2[i], level + 1, delta); for(int j = 0; j < x_points.size(); ++j) { FuzzyBin f = (FuzzyBin) children[i]; // Note that addPoint will only add it if it actually belongs. f.addPoint((Float)x_points.get(j), (Float)y_points.get(j)); } } } return children; } // Return an ArrayList of undivided quads (they'll be FuzzyBin objects) // which the given ray passes through and which are not empty (that is, // they contain some points inside that this ray could conceivably hit). ArrayList intersectRay(float r0x, float r0y, float rdx, float rdy) { ArrayList bins = new ArrayList(); // If this quad is empty, we're done. if (countPoints() == 0) return bins; // This quad has stuff in it. Do we intersect it? float[] hit = b.intersectRay(r0x, r0y, rdx, rdy); // If we don't hit it, we're done. if (hit == null) return bins; // Does it have children we can hit? // (That doesn't sound right, does it.) if (children == null) { // If not, we're done _and_ we have a result. bins.add(this); } else { // Otherwise, recursively see which children this ray hits. for(int i = 0; i < children.length; ++i) { FuzzyBin f = (FuzzyBin) children[i]; ArrayList bins_new = f.intersectRay(r0x, r0y, rdx, rdy); bins.addAll(bins_new); } } return bins; } // This function could be made much more clever be looking at the actual // entry and exit points (which Box.intersectRay returns) since there are // a lot of cases where it's obvious that it is impossible for an intersection // to occur, but I don't feel like applying this. } class DLA { FuzzyBin bin; int binSize; DLA(FuzzyBin bin) { this.bin = bin; binSize = 10; } DLA(FuzzyBin bin, int binSize) { this.bin = bin; this.binSize = binSize; } void addPoint(float x, float y) { // Two things happen here: // (1) We add the point to the bin. // (2) We make sure that every undivided quad contains at most // binSize points inside (i.e. we divide some if needed). ArrayList f = bin.addPoint(x, y); for(int i = 0; i < f.size(); ++i) { FuzzyBin bin = (FuzzyBin) f.get(i); if (bin.countPoints() > binSize) { bin.divide(); // Uncomment this to see them as they are added. //bin.drawMe(); } } } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345

/* OpenProcessing Tweak of *@*http://www.openprocessing.org/sketch/10796*@* */ /* !do not delete the line above, required for linking your tweak if you upload again */ // Quadtree containers demo // Click to make a point. As soon as more than binSize points are // inside of a quad, it subdivides. // Right-click to reset   final static float dotSize = 2; final static int binSize = 5; final static color[] colors = new color[4]; Box b; FuzzyBin q; DLA dla1;   void setup() {   size(600, 600);   frameRate(30);   //smooth();   colors[0] = color(127,0,0);   colors[1] = color(0,127,0);   colors[2] = color(0,0,127);   colors[3] = color(127,127,0);   b = new Box(1, 1, width, height);   q = new FuzzyBin(b, dotSize);   dla1 = new DLA(q, binSize);   dla1.addPoint(width/2, height/2); }   void draw() {   q.drawMe();   fill(0,0,0,0);   if (mousePressed) {     if (mouseButton == LEFT) {       dla1.addPoint(mouseX, mouseY);       ellipse(mouseX, mouseY, 4*dotSize, 4*dotSize);     } else if (mouseButton == RIGHT) {       q = new FuzzyBin(b, dotSize);       dla1 = new DLA(q, binSize);       background(255);     }   }   stroke(0); }   class Box {   float Xl, Yl;   float Xh, Yh;   final static float zero = 1e-20;   Box(float X_1, float Y_1, float X_2, float Y_2) {     // Orient so (Xl,Yl) and (Xh,Yh) are min/max extent, respectively     Xl = min(X_1, X_2);     Xh = max(X_1, X_2);     Yl = min(Y_1, Y_2);     Yh = max(Y_1, Y_2);   }      boolean pointInside(float x, float y) {     return x > Xl && x < Xh && y > Yl && y < Yh;   }      // Compute the intersection of the given ray (where x=R0x+Rdx*t and   //   y=R0y+Rdy*t) with this box; return two t values, Tnear and Tfar,   //   which give the entry and exit values of t (> 0)   float[] intersectRay(float R0x, float R0y, float Rdx, float Rdy) {     float Tnear = -1e30;     float Tfar = 1e30;          // First, check slab in X.     if (abs(Rdx) < zero) {       // Ray is parallel to X, but starts outside. Fail.       if (R0x < Xl || R0x > Xh) {         return null;       }     } else {       float Ta = (Xl-R0x)/Rdx, Tb = (Xh-R0x)/Rdx;       float T1 = min(Ta,Tb);       float T2 = max(Ta,Tb);       if (T1 > Tnear) Tnear = T1;       if (T2 < Tfar) Tfar = T2;       if (Tnear > Tfar) return null;       if (Tfar < 0) return null;     }          // Then check slab in Y.     if (abs(Rdy) < zero) {       // Ray is parallel to X, but starts outside. Fail.       if (R0y < Yl || R0y > Yh) {         return null;       }     } else {       float Ta = (Yl-R0y)/Rdy, Tb = (Yh-R0y)/Rdy;       float T1 = min(Ta,Tb);       float T2 = max(Ta,Tb);       if (T1 > Tnear) Tnear = T1;       if (T2 < Tfar) Tfar = T2;       if (Tnear > Tfar) return null;       if (Tfar < 0) return null;     }          // If we have survived this far, the test passed.     return new float[] {Tnear, Tfar};   }      // Divide this box down into 4 quadrants   Box[] quarter() {     return quarter(0);   }      // d = boundary "fuzziness" size   Box[] quarter(float d) {     float Xm = 0.5*(Xl+Xh);     float Ym = 0.5*(Yl+Yh);     Box[] quads = new Box[4];     quads[0] = new Box(Xm-d, Yh, Xh, Ym-d);     quads[1] = new Box(Xl, Yh, Xm+d, Ym-d);     quads[2] = new Box(Xl, Yl, Xm+d, Ym+d);     quads[3] = new Box(Xm-d, Ym+d, Xh, Yl);     return quads;   }      void drawMe() {     rect(Xl, Yl, Xh-Xl, Yh-Yl);   } }     // QuadTree class. Subdivide it at will. class QuadTree {   Box b;   QuadTree[] children;   int level;   static final int maxLevel = 8;      QuadTree(Box b) {     this.b = b;     children = null;     level = 0;   }     QuadTree(Box b, int level) {     this.b = b;     children = null;     this.level = level;   }     // Divide into 4 smaller quadtrees.   // If this exceeds the recursion limit, it will just return null.   QuadTree[] divide() {     if (children == null && level < maxLevel) {       children = new QuadTree[4];       Box[] b2 = b.quarter();       for(int i = 0; i < 4; ++i) {         children[i] = new QuadTree(b2[i], level + 1);       }     }     return children;   }      // Draw - recursively - the entire quadtree.   void drawMe() {     b.drawMe();     if (children == null) return;     for(int i = 0; i < 4; ++i) {       stroke(colors[i]);       children[i].drawMe();     }   }      boolean isDivided() {     return children != null;   }      // Find the smallest of the child quadtrees which contains the given point.   // If none are found, return null. This won't subdivide any further.   QuadTree getSmallestIntersect(float x, float y) {     if (children == null) {       if (b.pointInside(x,y)) {         return this;       }       else {         return null;       }     }     for(int i = 0; i < 4; ++i) {       QuadTree q = children[i].getSmallestIntersect(x, y);       if (q != null) {         return q;       }     }     return null;   } }   // Basically QuadTree class, but with fuzzy boundaries. class FuzzyQuadTree extends QuadTree {   float delta;      FuzzyQuadTree(Box b, float delta) {     super(b);     this.delta = delta;   }     FuzzyQuadTree(Box b, int level, float delta) {     super(b, level);     this.delta = delta;   }     // Divide into 4 smaller quadtrees.   // If this exceeds the recursion limit, it will just return null.   QuadTree[] divide() {     if (children == null && level < maxLevel) {       children = new QuadTree[4];       Box[] b2 = b.quarter(delta);       for(int i = 0; i < 4; ++i) {         children[i] = (QuadTree) new FuzzyQuadTree(b2[i], level + 1, delta);       }     }     return children;   }   }   // A FuzzyQuadTree that can contain points in each quad. class FuzzyBin extends FuzzyQuadTree {   ArrayList x_points = new ArrayList();   ArrayList y_points = new ArrayList();      FuzzyBin(Box b, float delta) {     super(b, delta);   }     FuzzyBin(Box b, int level, float delta) {     super(b, level, delta);   }     // Add a point to this quad if it's inside, _and_ to any other child   // quads that contain it. Return the undivided child quads which   // contains it.   // If this point is outside of the quad, return null.   ArrayList addPoint(float x, float y) {     ArrayList tips = new ArrayList();     if (b.pointInside(x, y)) {       x_points.add(x);       y_points.add(y);       // We've hit an undivided quad; we're done.       if (children == null) {         tips.add(this);         return tips;       }       for(int i = 0; i < children.length; ++i) {         FuzzyBin c = (FuzzyBin) children[i];         ArrayList tips_new = c.addPoint(x, y);         tips.addAll(tips_new);       }     }     return tips;   }      int countPoints() {     return x_points.size();   }     // Divide into 4 smaller quadtrees.   // If this exceeds the recursion limit, it will just return null.   // Any points contained are passed on.   QuadTree[] divide() {     if (children == null && level < maxLevel) {       children = new QuadTree[4];       Box[] b2 = b.quarter(delta);       for(int i = 0; i < 4; ++i) {         children[i] = (QuadTree) new FuzzyBin(b2[i], level + 1, delta);         for(int j = 0; j < x_points.size(); ++j) {           FuzzyBin f = (FuzzyBin) children[i];           // Note that addPoint will only add it if it actually belongs.           f.addPoint((Float)x_points.get(j), (Float)y_points.get(j));         }       }     }     return children;   }      // Return an ArrayList of undivided quads (they'll be FuzzyBin objects)   // which the given ray passes through and which are not empty (that is,   // they contain some points inside that this ray could conceivably hit).   ArrayList intersectRay(float r0x, float r0y, float rdx, float rdy) {     ArrayList bins = new ArrayList();     // If this quad is empty, we're done.     if (countPoints() == 0) return bins;     // This quad has stuff in it. Do we intersect it?     float[] hit = b.intersectRay(r0x, r0y, rdx, rdy);     // If we don't hit it, we're done.     if (hit == null) return bins;     // Does it have children we can hit?     // (That doesn't sound right, does it.)     if (children == null) {       // If not, we're done _and_ we have a result.       bins.add(this);     }     else {       // Otherwise, recursively see which children this ray hits.       for(int i = 0; i < children.length; ++i) {         FuzzyBin f = (FuzzyBin) children[i];         ArrayList bins_new = f.intersectRay(r0x, r0y, rdx, rdy);         bins.addAll(bins_new);       }     }     return bins;   }   // This function could be made much more clever be looking at the actual   // entry and exit points (which Box.intersectRay returns) since there are   // a lot of cases where it's obvious that it is impossible for an intersection   // to occur, but I don't feel like applying this. }   class DLA {   FuzzyBin bin;   int binSize;      DLA(FuzzyBin bin) {     this.bin = bin;     binSize = 10;   }      DLA(FuzzyBin bin, int binSize) {     this.bin = bin;     this.binSize = binSize;   }      void addPoint(float x, float y) {     // Two things happen here:     // (1) We add the point to the bin.     // (2) We make sure that every undivided quad contains at most     // binSize points inside (i.e. we divide some if needed).     ArrayList f = bin.addPoint(x, y);     for(int i = 0; i < f.size(); ++i) {       FuzzyBin bin = (FuzzyBin) f.get(i);       if (bin.countPoints() > binSize) {         bin.divide();         // Uncomment this to see them as they are added.         //bin.drawMe();       }     }   }      }

You can look at the OGRE source to see the Octree implementation. In Doom/Quake you can see the BSP implementation.

[Author]

Posts