Oh no- not this question again >.< (Octrees and Collision Detection)

[Alerion]

Hello everyone! I'm a regular reader to these forums, and I've learned a lot from the discussions many of you have had over the past few years.

I've spent the majority of my programming career treating it as it was - a hobby - and focused mostly on making 2d sprite based games. It's been great!

But I'm going to graduate from college soon, and lets face it, a portfolio full of 80's clones just doesn't have the spice it used to. Even mobile phones are starting to go 3d.

So I'm a dinosaur. But I'm not a dummy (mostly sorta kinda). I've spent 2 months now reading and researching, I own like 10 brand new books on 3d programming design, and I've made some great progress! It looks like it's from the 90's (better than the 80s though!) but boy am I proud of it! It's just that now I'm stuck at a place it seems a lot of people do. And it surprises me just how vague all the tutorials can be =(

So here's my situation, I have a handful of vertex data, assume I can figure out how to push and move and fit it anywhere I need to... I can't find a good tutorial on the actual nuts and bolts of implementing an octree on my data. I have lots of theory, just like school gave me, I can recite the definition and I can explain it to a layman without much difficulty. But I must a fool because I can't seem to figure out how to get my triangle data in there.

I thought I found the answer at xbdev.net - fully sourced octree example, but there were some fatal flaws in the code (The included source file craps out at around 1000 verticies.) Everything else seems to be integrated with a hundred thousand other things that not only have no bearing on building the octree, but serve to confuse this small brain of mine. (This one very nice one had all this code making doors and god knows what for occlusion, but I really don't need that right now...)

The forums here, after searching for the past hour and half haven't yielded much help =/

Similarly, Collision detection seems to get such a glossed over approach in everything. This one book I have says "don't worry about how it works, just include this header file based off this paper you can find on the internet" (in not so many words).

I really want to know how it works, and I'd really like to see some code that just focuses on the task at hand. It's so hard to navigate through 12 source files cross referencing various data types.

But I'll worry about collision detection later (I'm just mentioning it in case somebody here can give me a good smack on the head and make it all sensical.)

I'm using DirectX but OpenGL code works too, or whatever you want. It's really a platform independent code. Or maybe an explanation of the implementation and not the theory.

vertex(x,y,z). octree (or some other data type like kt-tree i think it's called and someone recommended in here). and putting them together.

I know it sounds dumb. And I've been here long enough to know that the next 3 posts are probably going to be 2 or three sentences passively aggressively insulting my intelligence... and I probably deserve it.

But I could really just use a kick in the right direction.

Thanks guys, sorry for the long post.
-Ally

[Alerion]

I did some more research into KD Trees and it seems to be the better way to go. If anyone bothered to read this, or had the same problem as me:

http://www.devmaster.net/forums/showthread.php?t=9764

I hope this helps someone haha. Thanks for not laughing at my stupid questions.

[Reedbeta]

Hmm...did you paste the right link? That thread you linked to has nothing to do with either octrees or kd-trees...

As for constructing an octree, it's basically a recursive process. You first find an AABB that bounds the whole scene (i.e., find the minimum and maximum X, Y, Z coordinates over all vertices of all triangles). This becomes the root node of the octree. Then you split the bounding box along the middle in each axis, creating 8 children. Each leaf node of the octree contains a list of the geometry in that node, so loop through all your triangles and assign each one to one or more child nodes depending on which boxes it overlaps. Now you have an octree one level deep. You can repeat the process on each of the 8 boxes, recursively splitting them and re-assigning the geometry to the leaf nodes (internal nodes don't have any geometry, just a bounding box). You need to have a criterion for deciding when to stop subdividing, for instance, don't bother splitting a node if it has fewer than N triangles in it where N is some number you'll have to tweak to optimize your implementation.

The construction process for a kd-tree is similiar but you must decide where to place the splitting plane at each step, which can be done in a variety of ways from median cut to SAH (surface-area heuristic).

[Alerion]

Yeah sorry wrong link.

I think I have it working but I am not sure the best way to check if the data is correct. Do you know an easy way to draw a cube around a defined area? I'm sorting through the data dump of my octree but I can't really tell if it's right or not visually haha.

[Reedbeta]

What do you mean, how do you draw a cube around a defined area? You just draw a quad for each side...