Hi I am using an octree to hold the objects in my universe. Now i need to do some collision detection, but one object that collides with the objects in the tree is a beam (one start point and a end point connected by a line). This beam is sometimes very long, so it goes through many nodes in the tree. Now i wan''t the first collision between the beam and any object in the universe. The collision that is the nearest to the start point. Now to the question: Is it usefull to test the beam against the tree, and when how to do that efficiently. Cause it would be stupid to recursive test in all the nodes if there already is an very optimal collision found very early. So maybe it is just simpler to test all objects against the beam (simple tests with bounding boxes). Thanks in advance Lars

When you recurse you dont test all the nodes.

I used a line-box overlap test and recursed that on the tree. Starting at the rootbox, check if it has subnodes, if so what octants is the line overlapping, then recursively continue on with those subnodes until getting to a leafbox.

Works for me.

I know that i don''t need to look at all nodes, but after i traversed the line thru my tree i have many leafs where the line goes through. And i have to find the one that is the nearest to the start point.
And i hoped there is a way to stop traversing on a early point to reduce the number of checks. Because the line would end up in about 20 Leaves in a regular case. Which means at least 20 line box intersection testes. But if i have only about 10 to 30 objects in my Universe it would by cheaper to check against those objects (their bounding boxes) directly.
The other point is, that it is very expensive to let the line traverse through the tree (compared to a point for example). Or am i thinking to complicated here.

For a little Background, i have a Spacecombat game, and represent the projectiles just by points. But i need Beam Weapons and also need to represent some of the other shots as lines because they move to fast for the framerate so they go thru objects without hitting them.

Lars

Oh.. Well.. Why do you have an octtree for your objects?. Dont you need to rebuild it if the objects are moving?.

Yes, it would probably be faster to directly check the objects bounding box. Atleast when you got fewer objects then leafs to check anyway.

But perhaps something like this:

1. Get the leafbox that the lines starting point is in
2. If the line collide with some object in this leafbox stop
3. else clip away the part of the line thats in this leafbox
4. if there is something left of this new line, go to 1

Not sure it got some advantage over the direct approach though. I did something like this a while ago, but ditched the idea because some inaccuracies in my clipping functions.

And when you get to step 1 the second time and ever after, you might do some backtraversing in the tree to faster get the leafbox somehow. I.e checking the previous leafbox parents other leafboxes, instead of beginning at the root again.

Thanks alot

Your idea sounds very good, i will try this. This way the tree isn''t useless for this case.

For rebuilding the tree, that is true in most cases, but if the recursion level isn''t to deep it is relatively fast, and i can change the recursive level dynamically.
The tree improves collision detection and frustrum culling so i get a speed increase when i use the tree, even if there are only 5 space ships in it, cause the larger ships are subdivided into parts which get inserted sperately. This way there are about 3 to 6 times more objects then ships in the tree.

I hope it gets more usefull when i have a large amount of fighters flying around :-)

Lars