buckytree: implicit spatial data structure back
(L) [2007/05/07] [bmcnett] [buckytree: implicit spatial data structure] Wayback!Hi all,
Syoyo Fujita recommended I visit this forum. In 2002 I developed an implicit spatial data structure. It is similar to "BIH" in concept, but requires no storage of object indices or pointers.
If this is your sort of thing, please check it out here: [LINK http://www.mcnett.org/]
Thanks!
Bryan McNett
(L) [2007/05/07] [trh] [buckytree: implicit spatial data structure] Wayback!Very interesting! Have you tried to benchmark it against a kd-tree or bih-tree?
_________________
You can't see California without Marlon Brando's eyes.
(L) [2007/05/07] [bmcnett] [buckytree: implicit spatial data structure] Wayback!Five years ago I did run tests comparing it to brute force and quadtree, but BIH hadn't been released yet and at the time, I was not aware of k-d tree.
My tests showed that buckytree was an order of magnitude faster than brute force or quadtree, especially when 16 triangles were run in parallel with PS2 SIMD.
In the next week, I'd like to run some test cases and put comparative results up on the page.
That being said... I suspect buckytree outperforms BIH and k-d tree in the general case, mostly due to its simplicity and low memory footprint.
Bryan
(L) [2007/05/07] [MishoM] [buckytree: implicit spatial data structure] Wayback!Very interesting. This structure seems very efficient when searching for objects at a specific location in space. And it can be made almost branchless. But have you tried using it for searching for objects along a line like when tracing rays?
_________________
--------
MishoM
(L) [2007/05/07] [toxie] [buckytree: implicit spatial data structure] Wayback!Interesting indeed! But i don't know if this is suited for ray tracing, at least i can't think of a clever ray traversal yet(!).
Do you have any thoughts on that?
_________________
The box. You opened it. We came.
(L) [2007/05/07] [bmcnett] [buckytree: implicit spatial data structure] Wayback!yes, buckytree traces rays efficiently. enough people have asked about this that i should write up a page on it.
i'll briefly explain here:
before buckysearch, clip ray to the boundaries of the world. now it's a line segment.
at each step,
1. recurse left
2. if line segment MAX < median MIN, stop now
3. if line segment intersects median MIN, clip line segment to median MIN and recalculate line segment MAX
4. test for intersection with median object
5. recurse right
(L) [2007/05/07] [beason] [buckytree: implicit spatial data structure] Wayback!wow thats pretty cool. i don't totally understand it after just one quick read through but the gist of it seems to be that you are using a simpler primitive to bound space. Actually it's the simplest, aka a simplex. Can't wait for someone with more time (or just more productive) to code it up and post benchmarks [SMILEY Smile]
(L) [2007/05/08] [bmcnett] [buckytree: implicit spatial data structure] Wayback!I just updated the article and its sample source code:
[LINK http://www.mcnett.org/]
I outlined how to perform efficient raytracing of a buckytree in the notes on the bottom.
And, it turns out that my focus on tetrahedra amounts to a rhetorical flourish - AABB is likely to perform better for most object databases, as proven by recent tests.
That being said, any convex hull will do, so if your application is called "pentagonal prismania" your buckytree can be all pentagonal prisms, and you will get better performance than AABB.
Thank you all,
Bryan McNett
(L) [2007/05/16] [egodeath] [buckytree: implicit spatial data structure] Wayback!Hey, I have been trying to understand your algorithm. I'm currently implementing this in Sci-lab.
One thing I'm confused about is when doing ray traversal:
First, assume that we have a median divider with a minB computed from the triangular basis. So to the left of the median are objects with MinB smaller than the medium, and to the right with minB greater or equal to minB.
But what is minB (bare with me as I'm trying to understand this geometrically)?
Objects in the array to the left of the median are objects to the RIGHT of the median geometrically. Maybe I'm very wrong about this, but my thinking is this:
Since
(L) [2007/05/16] [egodeath] [buckytree: implicit spatial data structure] Wayback!Okay I get it now. It don't really matter since the efficiency is always log(n).
Suppose that we have L mentioned above. So when given a median, we always recurse left. Even tho the objects are to the left of the median, by recursing left we are always going to be dividing the size of the array in half. So this is log(n).
Suppose we don't find anything on the left recursion, so what? Who cares, we spent log(n) time looking left.
Now we recurse right, which is looking at object to the LEFT of the median. Again this is log(N).
(L) [2007/05/16] [egodeath] [buckytree: implicit spatial data structure] Wayback!Sorry for being such a noob [SMILEY Smile]
Hmm but according to the ray-tracing algorithm given above,
We always recurse left first. If line segment MAX > Median, we cannot stop. So we have to examine the other half. So it is conceivable that MAX > Median Min at every recursive step, therefore we have to recurse right at every step. If we do that do we not end up examining every element in the array?
(L) [2007/05/16] [egodeath] [buckytree: implicit spatial data structure] Wayback!sorry it's me again.
After thinking about it some more I don't think the situation I described can happen.
Precisely because the way buckytree works, most of the time (probably all) you will stop at step 2. Because it is very likely that Max will be less than one of the Min A, B, C.
(L) [2007/05/17] [egodeath] [buckytree: implicit spatial data structure] Wayback!also have to remember that buckytree is a non-dimensional, don't get confused on that like I did.
(L) [2007/05/18] [Siker] [buckytree: implicit spatial data structure] Wayback!Did you try to implement the algorithm yet, egodeath?
(L) [2007/05/18] [bmcnett] [buckytree: implicit spatial data structure] Wayback!It's true that if your search query MAX is always >= the database MIN, you will never reject anything. But in practical terms, this means that the search query is really big and contains everything in the database. In that case, no algorithm will help you to reject objects - because they can't be rejected.
I am now trying to figure out how to apply SAH to buckytree. Buckytree as originally explained is perfectly balanced, but it's well known that unbalanced trees perform better, and SAH is the popular metric for determining how to unbalance a tree.
It's possible to unbalance a buckytree (or any tree) by way of an auxiliary data structure, stored as a left-balanced tree ( N's left child is N*2+1, N's right child is N*2+2 ) that stores only where to split the main tree, perhaps as a U8 or U16.
Bryan
(L) [2007/05/18] [egodeath] [buckytree: implicit spatial data structure] Wayback!yeah I did... But it's running very slowly. Obviously I have lots of bugs!! It's slower than brute force method!!! I'm a noob at doing ray-tracing [SMILEY Smile], my implementation is obviously not very good. I'm trying to to learn so I can re-implement in the near future with a better design.
Here are two screen shots: The first one is with Buckytree, notice there are some missing objects. 2nd one is with brute force. Again I did this last night and have not had time to crush teh bugs yet.
[img]
[LINK http://bp2.blogger.com/_8rAMzmhmSSY/Rk3r-ORbisI/AAAAAAAAABM/QzFUliBtDt8/s1600-h/hack1.png]
[/img]
[img]
[LINK http://bp0.blogger.com/_8rAMzmhmSSY/Rk3sIuRbitI/AAAAAAAAABU/8ZEY-C3D1mA/s1600-h/hack2.png]
[/img]
I'm having some trouble still with the ray-tracing.
My current understanding of Buckytree is this:
Since on some axis, those objects to the left of the median have min(object) < min(median), but geometrically they are to the "right" of the median. That is, they are on the other side of where the ray origin resides.
So with the ray-tracing algorithm, you recurse left. Then if we can trivially reject the right stop. Else clip the ray to the median, recompute max, and check to see if the median bounds the ray, if so then ADD the median to the potential intersection set and recurse right. Other wise continue recurse right.
That is, it is "hard" to have an intersection that will terminate the recursion early. This is due to the fact that recursing left means looking at objects on the other side of the plane from which the origin of the ray resides, so if you have an intersection you cannot trivially stop the recursion. You have to find ALL potentials.
For objects searching, this is is not a big deal. For most objects have small hulls and they do not overlap the median.Objects can terminate recursion most of the time after recursing left. AND it does not matter really which side of the plane an object reside. This is not so for rays, since by definition rays have to intersect, i.e they overlap lots of things.
For BIH (sorry but don't quote me, I barely glanced at the BIH paper) since you actually traverse those children near the origin, and that you can eliminate children once you find an intersection...
Again this is probably mostly due to my misunderstanding of the alogrithm. You know I've had many already in this post here [SMILEY Smile]
(L) [2007/05/18] [egodeath] [buckytree: implicit spatial data structure] Wayback!okay I need to think about this some more...
After clipping the ray, I don't recurse right with the new line, but with the old line...
I need to think about this some more.
(L) [2007/05/18] [egodeath] [buckytree: implicit spatial data structure] Wayback!sorry, my bad.
I wsa thinking that the line is bounded at a single point, when it is not! I'm doing this calculation in my code, but I'm not recursing with the new bound values...
Say yeah I will make the changes.
(L) [2007/05/18] [egodeath] [buckytree: implicit spatial data structure] Wayback!Yeah that's a big mistake man. Even tho I kind of understood the importance of computing the max for an object to get a max bounding hull, when I hear "a line," I automatically think that it's max is at the end point!!! Which is not true! Since we're talking about a max bounding "hull". The bounding hull is not a single point!!!
Silly me.
(L) [2007/05/18] [Siker] [buckytree: implicit spatial data structure] Wayback!This is a little bit off topic... Looking at your pictures it looks like you have some very strong perspective distortion. Is that intentional? What's your field of view there?
(L) [2007/05/18] [egodeath] [buckytree: implicit spatial data structure] Wayback!Probably. I was trying to get a wide screen thing working so it's probably not right.
Right now it's all just hacked together. I will properly design it later by properly implementing a rendering pipeline. I have a little bit of experience with OpenGL but this is my first time implementing a software renderer.
Yeah it looks distorted. I have not touch this code for half an year and I don't have a clue why it's doing that LOL [SMILEY Smile]
I will check it.
(L) [2007/05/19] [egodeath] [buckytree: implicit spatial data structure] Wayback!Hey I got rid of some bugs with buckysearch (ray-tracing).
It's slightly faster than bruteforce.
By slightly faster I mean to render the below picture for brute force it took 512 seconds, while buckysearch too 200.
I think there is probably some more bugs. When I print out the Min(A) from the buckysorted objects they appear not to be sorted...
Weird.
[LINK http://bp0.blogger.com/_8rAMzmhmSSY/Rk6QTeRbivI/AAAAAAAAABk/c0jMVt_o4fw/s1600-h/hack5.png]
(L) [2007/05/19] [egodeath] [buckytree: implicit spatial data structure] Wayback!An update:
My bad, it is buckysorted properly. I just mis-read the number. I was thinking that it should be SORTED, i.e sorted in ascending order...
Whether or not if it is bucky searching properly I don't know.
I'm going to do some testings, I will run the regular none ray tracing bucky search to see how fast that runs and compare it with Mcnett's sample implementation.
The weird thing is that say when the spheres are in a position off screen, i.e only the "box" is on screen, it still takes the same amount of time to render.
I will think about choosing an axis depending on scene distribution.
(L) [2007/05/24] [egodeath] [buckytree: implicit spatial data structure] Wayback!I'm still working on this, although I have not had time to really work on it for the past week.
It certainly is faster than brute force for large amount of objects. But the problem is my implementation is still not correct. I'm getting some rendering problems. I think the problem is that I forgot about the case where the line segment does not intersect the median. For some reason I assumed that it's always going to intersect the median, a wrong assumption.
By intersecting I'm assuming a line intersecting the plane of the divider. What I'm doing is check which side the ray origin resides on the plane (dotproduct(raydir,axis)) then recurse with either the (rayorgin,newpointondividerplane) or (newpointondivierplane,oldtail).
Although I need to reexamine whether I can do this some other way.
Another thing is after I correct the bugs I will do a rewrite. My current codebase was initially designed as a quick hack to getting my feet wet with ray-tracing.
Got a lot of work ahead me hehe [SMILEY Smile]
(L) [2007/05/24] [Siker] [buckytree: implicit spatial data structure] Wayback!Yeah, definitely consider trying it with a larger scene. I think in general terms any spatial optimization algorithm will add a certain amount of overhead in exchange for making your algorithm O(log N) like. You won't reap the benefits until your N is big enough that the overhead of the algorithm is dwarfed by the gain of the logarithmic growth versus linear growth.
Keep the progress reports coming, they're very interesting. [SMILEY Smile]
(L) [2007/05/25] [egodeath] [buckytree: implicit spatial data structure] Wayback!I'm going ahead with the rewrite. Also I'm going to implement BIH for now. I will come back to this later. I'm not giving up, I just need a change of scenery [SMILEY Smile]
[img]
[LINK http://bp3.blogger.com/_8rAMzmhmSSY/RlZurORbiwI/AAAAAAAAABs/qZXl5Y1IZC8/s1600-h/hackfinal.png]
[/img]
(L) [2007/05/25] [egodeath] [buckytree: implicit spatial data structure] Wayback!Ahh i fixed the bug...
So it works, not very fast, but that's my implementation problem. At least it's faster than brute force hey!
[LINK http://bp3.blogger.com/_8rAMzmhmSSY/RlaGhORbixI/AAAAAAAAAB0/c4hI3YUrh94/s1600-h/finalfinalhack.png]
BTW what appears to be wrong shadows are really random small balls in the air [SMILEY Smile] Not bug!
I was going to implement (hmm hack) a snow flake fractal, but I'm too tired. I guess I will just have to wait for the re-write.
(L) [2007/05/25] [Phantom] [buckytree: implicit spatial data structure] Wayback!Egodeath, your journal is nice to read. [SMILEY Smile] May I make a suggestion? Once you get it working, delete everything, and start over again, and this time produce a series of articles. There are a lot of people out there that really appreciate that kind of stuff.
_________________
--------------------------------------------------------------
Whatever
(L) [2007/05/26] [egodeath] [buckytree: implicit spatial data structure] Wayback!Yeah that's a great idea! I think I will do that. It's going to take awhile tho, I have classes to attend starting next week. I'm taking complex and vector analysis.
At this point everything is working, maybe? LOL! THe shadow ray traversal also uses buckytree.
The performance is really bad. The following sphere flake level 6 was rendered in 1000 seconds!!! My intersection codes are not optimized at all, they are mostly hacks tell you the truth. I know I know I can make it run faster with a rewrite.
[LINK http://bp1.blogger.com/_8rAMzmhmSSY/RlfkEeRbizI/AAAAAAAAACE/yrVKUVmi6cU/s1600-h/morehacks1.png]
[LINK http://bp0.blogger.com/_8rAMzmhmSSY/RldssORbiyI/AAAAAAAAAB8/e6IIJQ7F4EY/s1600-h/flakeyhack.png]
back