A tool to explore B*H trees

Practical and theoretical implementation discussion.
Post Reply
voxel
Posts: 6
Joined: Tue Jun 12, 2012 7:21 pm
Location: New Jersey, USA
Contact:

A tool to explore B*H trees

Post by voxel » Wed Jul 25, 2012 10:40 am

I needed a way to sanity check my BVH/BIH libraries so I wrote a quick 2D tool to interactively display a tree's nodes and allow you to play with the cost constants:

http://jon-carlos.com/projects/bxh/exam ... w_bih.html

And:

http://jon-carlos.com/projects/bxh/exam ... w_bvh.html

They should work in most modern web browsers.

Jon

ingenious
Posts: 282
Joined: Mon Nov 28, 2011 11:11 pm
Location: London, UK
Contact:

Re: A tool to explore B*H trees

Post by ingenious » Wed Jul 25, 2012 4:33 pm

This is cool, I really like it! Can you please add some random object generator, where you can specify the number of objects? I'd love to experiment with a smaller number of objects.

Further suggestions would be to add non-axis-aligned geometry, to specify the distribution and shape of objects (as probability distributions), and maybe also to be able to draw a ray and the cost of this specific ray to be computed. Possibilities are endless, and this can become a really useful visual tool!

Cheers ;)
Image Click here. You'll thank me later.

voxel
Posts: 6
Joined: Tue Jun 12, 2012 7:21 pm
Location: New Jersey, USA
Contact:

Re: A tool to explore B*H trees

Post by voxel » Wed Jul 25, 2012 6:09 pm

ingenious wrote:Can you please add some random object generator, where you can specify the number of objects?


Of course! That is a really simple change.
ingenious wrote:Further suggestions would be to add non-axis-aligned geometry,
The B*H structures only know about AABBs so the trees would look similar. Though I can understand doing this in conjunction with:
ingenious wrote:maybe also to be able to draw a ray and the cost of this specific ray to be computed.
Because then you could see how the wasted space around non-axis aligned geometry costs in terms of wasted intersection tests.
ingenious wrote:to specify the distribution and shape of objects (as probability distributions)
This is the one I am a little foggy about. I understand the idea but I am not sure how to make it "user editable". Right now, the objects are just created by a function that is called X times.

What I am thinking is that I could provide a text area with the current function as-is and the user could then edit the function and recreate the objects. It would require that the user know a little JavaScript but that shouldn't be too difficult.

The real problem would be detecting errors and providing meaningful feedback to the user. I have to think about this one...
ingenious wrote: Possibilities are endless, and this can become a really useful visual tool!
Thanks for the great suggestions! Anything else you can think of to make this a useful learning tool (even interface changes)?

Jon

ingenious
Posts: 282
Joined: Mon Nov 28, 2011 11:11 pm
Location: London, UK
Contact:

Re: A tool to explore B*H trees

Post by ingenious » Wed Jul 25, 2012 8:14 pm

Indeed, the shape/orientation can be useful for "ray debugging" :) It would be really useful to be able to visually track the traversal/intersection process for a given ray step by step, highlighting the current voxels and ray intervals (and dimming all others). I'd love to play with this!

Regarding the distributions, it was just a wild idea, and I don't really have a good suggestion at this point about the positional distribution. As for the size of the objects, this can be some linear/Gaussian distribution from specified min and max size. Maybe in the beginning it's enough to have a single slider that controls the preference of large vs small objects, which would be mapped to a linear slope or standard deviation, respectively. Putting a text area with the code sound also like a good option. With own responsibility, of source; one can resorts to their browser's JavaScript browser debugger.
Image Click here. You'll thank me later.

voxel
Posts: 6
Joined: Tue Jun 12, 2012 7:21 pm
Location: New Jersey, USA
Contact:

Re: A tool to explore B*H trees

Post by voxel » Fri Jul 27, 2012 8:12 am

Update time! I managed to implement some of what ingenious had suggested within the BIH example.

http://jon-carlos.com/projects/bxh/exam ... w_bih.html

There is a slider for the number of objects and an input for a range of sizes. The size is a normal distribution within the range you select. The distribution of boxes in space has also been updated. But the real change is the inclusion of the very first version of the "ray debugger"! :lol:

You click on the Draw Ray to, ahem, draw a ray on the canvas. Click anywhere on the canvas to place a start point for the ray and then click again to place the end point. After that you can use the Step button to literally step through the traversal node-by-node. The green portion of the ray is the current trimmed segment for the highlighted node.

In the upper left corner is a running tally of the number of traversals and intersection tests performed. When you reach the end of the step, all the boxes traversed (including leafs) will be draw showing an overview of the ray's travels.

The Restart button can be used at any time to start stepping from the root. This is particularly useful if you change the settings for tree construction and want to re-test the same ray against the new tree.

Jon

spectral
Posts: 382
Joined: Wed Nov 30, 2011 2:27 pm
Contact:

Re: A tool to explore B*H trees

Post by spectral » Fri Jul 27, 2012 11:40 am

Wow,

Incredible usefull to analyse an algorithm :-P

It will be great to have it as :
a) open sourced, in order to modify and test to different strategies. Via plug ins
b) have a 3D version of it
c) for sure a standalone application, like a small soft with QT + OpenGL :-P
d) being able to import models and construct the related structure

Great work for research, I like... :-)
Spectral
OMPF 2 global moderator

voxel
Posts: 6
Joined: Tue Jun 12, 2012 7:21 pm
Location: New Jersey, USA
Contact:

Re: A tool to explore B*H trees

Post by voxel » Fri Jul 27, 2012 6:37 pm

Hello everyone!

I made the BVH version available. I haven't worked nearly as hard on optimizing the BVH as I have the BIH and it shows in the debugger! :oops: One of the more interesting results of this version is that you can plainly see the difference between the breadth-first search that I employ on the BVH as opposed to the depth-first search used in the BIH.

http://jon-carlos.com/projects/bxh/exam ... w_bvh.html
spectral wrote: Wow, Incredible usefull to analyse an algorithm :-P
Great work for research, I like... :-)
Thanks, you are all so kind!
spectral wrote:It will be great to have it as :
a) open sourced, in order to modify and test to different strategies. Via plug ins
The examples and the libraries ARE open source under an LGPL license: https://github.com/imbcmdth/bxh

This is just the guts of my JavaScript ray tracer. Eventually, the whole thing will be open sourced when the code gets somewhat closer to being less of a disaster! :lol:
spectral wrote: b) have a 3D version of it
c) for sure a standalone application, like a small soft with QT + OpenGL :-P
d) being able to import models and construct the related structure
This is all possible with the current code. The libraries themselves are dimensionally agnostic (I don't know if that is a real term but I am making it one!) and the ray tracer already has the code in place to read Wavefront OBJs and generate B*Hs from the polygonal soup.

The final version would likely employ WebGL (basically, OpenGL) and run in any fairly modern browser. There are libraries I could use to make it more of a stand-alone app as well once the web version is all done.

Anyway, I am taking a trip later today so any further development must wait a little while. Thanks again to everyone for the encouragement and great feature suggestions.

Jon

Post Reply