Jump to content
  • Advertisement
Sign in to follow this  
twopint32oz

[.net] BSP tree problem

This topic is 3646 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This is going to be used strictly in 2D (on images to be specific) not 3D. I need to be able to divide the image until an end criteria is met using linear lines in any orientation (360 degree range). The internal nodes store the dividing lines, while the leaf nodes contain the average intensity of the region that the node is referring to. My problem is that I dont know how to store a line segment that is on a specific place. Of course, i need to store the line as well as its location. The leaf nodes just contain a value that will be used to "color" in the region by a BSP tree decoder, but the problem is to store the dividing lines. Would the lines be stored as functions? if so how? Some background info on BSP tree: ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html#6.txt The binary tree that I'm using: http://msdn.microsoft.com/en-us/library/ms379572(VS.80).aspx

Share this post


Link to post
Share on other sites
Advertisement
This is probably out of my league, but why can't you store the line as two endpoints? The image is of finite size, so you don't really need an infinite line, just a finite line segment.

Share this post


Link to post
Share on other sites
Quote:
Original post by Gage64
This is probably out of my league, but why can't you store the line as two endpoints? The image is of finite size, so you don't really need an infinite line, just a finite line segment.

Hmm how could one go about doing that? Theres gonna be hundreds of lines so I will have to come up with a method to store the points in more efficient way.

Share this post


Link to post
Share on other sites
Say you are representing a point as two doubles (floats might suffice, this is just for the sake of argument). A double is 8 bytes, so a point is 16 bytes and a line segment, which has 2 end-points, takes 32 bytes. If you have 10,000 lines, that will occupy about 320 kilobytes. Is that really a lot? Are you under a very constrained memory budget?

I've heard that there are some methods to more efficiently store BSP trees, but before looking at that, make sure you really need them. Why complicate the code for nothing?

Share this post


Link to post
Share on other sites
But does it really require double or float? I mean think about it this way: a pixel represents 1x1 blocks and suppose theres a 512x512 image. Then i could set up a coordinate plane that starts from (0,0) to (512,512), which would mean that every 1 unit is between two pixels. Hence you could use something like short, which would reduce the amount stored to 1/2 or 1/4 when using float or double respectively. You cant really "divide" a pixel. Or can you?

Since the tree is generic, i can create a constructor to create a tree using byte or short depending on the size of the image. Im not sure if im making sense.

As for other questions: 1) No. atm im working on a computer so memory and processing is "unlimited"
2)I would say 320 KB is alot. Remember, this is a method of image compression. The point is to use as little space as possible. Plus the fact that i have to store average intensity of the regions created by the lines require space too (it's limited to greyscale images).

Share this post


Link to post
Share on other sites
Ok how about this? An image has four vertices (or corners) so there are four points to begin with. If i add two more points on the borders of the image, then i would have a total of six points, 4 of which can be used to define two separate polygons.

So basically, i create two new polygons by adding two points. Instead of bothering with lines, I create REGIONS to store in the leaf nodes. I started to look into System.Drawing + System.Drawing.Graphics. Should I use pointers for this since I have to reference the same points over and over again?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!