🔒 Locked

Octrees-quadtrees

Started by Velochy Jul 19, 2002 at 3:40 PM 6 replies 750+ views

Original Post

Jul 19, 2002 at 3:40 PM

I have heared they are an efficient ways for geometry culling. Well the bsptrees are also considered efficient for some culling effects but i have not really seen much use for them beyond throwing large amounts of lines against them and calling it collision detection

. Anyways the texts on quad and octrees(havemt really decided which do use but im leaning towards quadtrees) basically suggest one uses a 4 point scan do determine weather the cube(or rectangle) is in fov. now from the top of my head i thought that wouldnt it be much faster to initally use the central point and the bounding circle to check it against the outer circle of fov(instead of back culling plane it uses a bounding sphere). now if the fov check is done after the sphere check and only if the previous test returns a collison. If the map is more or less square, the bounding circles will not be too far off and testing 2 spheres qequires 3 "-" and 4 "*" while one point - plane test requres 3 "*" and 3 "+". so testing against 4 points takes 24 units in which time it could do 3 and a half sphere tests (i created a small test program and on my amd id pretty much took the same time for multiplications, divisions, additions and subractions(subtractions taking a small marginal less i believe) one question - is this thinking sound... or is this thinking at all? If i managed to confuse somebody, let me know please cause i will try to make this thing a bit more understandable Oh and in case you are wondering why i write so ununderstandable text is because im a 10-th grader in the verge of mental breakdown [edited by - Velochy on July 19, 2002 4:43:08 PM]

Dirge

Jul 20, 2002 at 1:04 AM

Hmm, I''m having a hard time reading what you''re saying so it''s it''s too late and the caffiene is wearing out or you might be a little confused, so I''ll just tell you what I know.

Octree/QuadTree are subsets of BSP tree. Same technology, and I''m actually about to start a project where BSP trees are contained within Octree Nodes.

Why use Octree over QuadTree? If you have a lot of objects everywhere, not just restricted to 2 planes (liek xz plane). So if you have very high skyscrapers in your game, you might want Octree to divide up world more evenly, but with QuadTree, you just divided on 2 axis, which is simpler, but might leave a lot of overdraw.

A sphere is a lot like a cube in that a sphere has a radius, but in a sense so does a cube (it just has a size that is consistant on all axis, like a sphere). So testing spheres ti octree/quadtree cubes is simple. Just test the vertices to see if they are inside, although there are more complex algorithms.

I got a tut on my site on collision detection using Octree''s so you might wanna check that out.

p.s. Yeah 10th grade was pretty tough. Just remember it''ll be over soon then you can start regretting all the things you didn''t do.

"Love all, trust a few. Do wrong to none." - Shakespeare

Dirge - Aurelio Reis
www.CodeFortress.com
Current Causes:
Nissan sues Nissan

Velochy

Jul 20, 2002 at 3:00 AM

Thanks about the tutorial. Yeah mornings clear stuff up.. now that i think of it there might be some good formulae to test cube-plane collisions.. altho the 2d math learnt in 9-th grade wont really do.. i read some more tutorials... so far i have seen that sphere-plane or sphere-sphere is times more efficient than any cube-plane or cube-sphere collision. SO could you give the formula for that 3 * and 4 +. The best cube - anything collision i could think of off the top of my head is using 3 planes which intersect in the center and check anything againt the planes (making shure the absolute distance from the planes is half the lenght of one side of the cube or less) weilding total of 9 * 9 + and 3 fabs() (or skip the abs but still)
storage wouldnt take much more memory space than sphere tho - all you need are 3 distances or the central point coordinates(like sphere) and then half the lenght of the side (or the radius just like on spheres) - normals would always be 1,0,0 0,1,0 or 0,0,1. If there really is a 3*4+ formula i would really like to know it altho when storage is concerned, i could use both alternatively with quadtree(when sphere check returns ture, do the cube check(in quadtrees it is 6*6+) or something along these lines

[edited by - Velochy on July 20, 2002 4:02:30 AM]

PsyVision

Jul 20, 2002 at 4:16 PM

okay, cheers for the help at the other post btw. I have code to both compile BSP and Octree. The problem is i have been wanting to get collisions working for ages and could never do it on BSP so i eventually got some for Octrees and i think thats the way im going to head.

Personally i would use Octrees over Quadtrees coz you get the extra dimension of culling.

My current systsm is based on Octrees, i use frustrum culling, along with a distance check, so i find out whats in the frustrum, i then check if they are withn a certain distance, if so then i draw it. The distance changes base upon the frame rate and the optimum frame rate. If the FPS is below the optimum the draw distance lowers till its at the optimum (or near). I also have collisons going.

The only problem is my file format. Im currently using 3ds max and im trying to find some way to put entities and triggers in it.

I dont think the method of frustrum culling is too important. im using cube checks (seen as octrees are cubes).

Collisions methods, it find the octree that im currently in. It then runs throught the objects in the tree and checks the faces with the sphere of the camera. I think i should probably come up with a better solution than this though at the moment it is running fine.

The only problem is that it is overdrawing some already drawn so i gotta fix that

m only acheiveing around 60fps even with v-sync off so im thinking something is a bit broken, im using glDrawElements

Velochy

Jul 21, 2002 at 2:29 AM

well point is im gonna have an rpg... so if i do octree there will be alot of completely empty nodes on flat ground. Maybe i should try the same method i gave you to use octrees in cities and quadtrees in outdoors

anyways..
the cube-in-frustfrum takes(according to my calculation), (9*9+)*6=54* and 54+ (awfuil waste since ´with spheres one it is only 6*(3*2+2-) since additions , subtractions and multiplications take aobut the same amount(on my amd, maybe intels or cyrixes handle it differently)

ofcours if anyone knows what the man meant with ortographic cube/plane distance and how it can bedone with 3* and 4+ i would really like to know

[edited by - Velochy on July 21, 2002 8:30:46 AM]

PsyVision

Jul 21, 2002 at 3:10 AM

hmm, well im happy at the moment with my way of frustrum culling (cube).

But...

... how would you achieve a quadtree/octree hybrid, knowing whether it was terrain or city ? coz this would also help me!

Velochy

Jul 21, 2002 at 7:37 AM

well calculate the average y value for the node (for speeds sake use every second vertex instead of all of them or something) and check all the verts to see if they are in a certain range from that .. and if 75 orso % are then stop octdividing and start quaddividing, using the altitude starting form which you are quaddividing for central point y value. also note down weather node is oct or quaddivided somewhere(a bool octdiv maybe).

Implementing culling endine to use these things might get a bit complicated tho. it might save some room in memory but considering it i dont think it really would be worth it. Consider it tho cos im not a professional or anything(actually im a depressed 15-year old boy but thats beside the point

[edited by - Velochy on July 21, 2002 8:41:15 AM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.