PDA

View Full Version : What the heck is this?!!



adrian
03-23-2006, 05:43 AM
Hey L'wavers,

I was reading through the stuff about v9 NewtekEurope, and when talking about the new rendering engine it said:

"Implementation of BSP/KD Tree Algorithm"

Wow! I mean..... great :-) But what is a BSP/KD Tree Algorithm exactly? And why is it so good?

Not having a great aptitude for even the simplest of maths, this sounds like sci-fi babble to me, so if anyone could offer an explanation suitable for a math-o-phobe, that would be great :-)

Of course whether or not I find out what this is, is not going to affect my decision to buy v9 as it sounds rather good to say the least - but it would be nice to know. I might even make myself sound a bit clever when explaining it to someone else!!

DiedonD
03-23-2006, 05:50 AM
Hey L'wavers,

I was reading through the stuff about v9 NewtekEurope, and when talking about the new rendering engine it said:

"Implementation of BSP/KD Tree Algorithm"

Wow! I mean..... great :-) But what is a BSP/KD Tree Algorithm exactly? And why is it so good?

Not having a great aptitude for even the simplest of maths, this sounds like sci-fi babble to me, so if anyone could offer an explanation suitable for a math-o-phobe, that would be great :-)

Of course whether or not I find out what this is, is not going to affect my decision to buy v9 as it sounds rather good to say the least - but it would be nice to know. I might even make myself sound a bit clever when explaining it to someone else!!

Ahh this one is easy. The very best way to explain this is like so. Theres this implementation you see, and the implementation part occurs with the BSP and or KD. Of course all this is just an algorythm of the Tree type, and is extra great for all users in LW9.

Just kidding :) , I am as curious as you to find out what this exactly means. But maybe it may take someone from LW9 team to precisely explain it, hopefully nothing at all like I did :)

Weetos
03-23-2006, 06:16 AM
BSP stands for Binary Space Partitioning, see there (http://www.delphi3d.net/articles/viewarticle.php?article=bsptrees.htm)

dunno what KD is though :help:

adrian
03-23-2006, 07:02 AM
Thanks for the link - everything is as clear as mud now :D

My next question is, how is it some people are so intelligent that they actually think this stuff up?!!

Do you think these people incorporate the subject of algorithms in their chat-up lines when they're cruising for chicks/studs? "hey baby, I'd really like to get hold of your constructive solid geometry... and believe me, you'd love to climb my binary space partitioning tree! - so your place or mine?"

Dirk
03-23-2006, 10:19 AM
As far as I know, BSP Trees where first used in Quake. The game levels where created with a CSG modeller / editor like Worldcraft, and the finished levels where used to compute a BSP-Tree. In the game, the engine used the BSP tree so only the actual visible part of the level was rendered.

lardbros
03-23-2006, 10:30 AM
As far as I know, BSP Trees where first used in Quake. The game levels where created with a CSG modeller / editor like Worldcraft, and the finished levels where used to compute a BSP-Tree. In the game, the engine used the BSP tree so only the actual visible part of the level was rendered.

Yeah, i remember making BSP's for the quake levels and stuff. Blimey feels like 10 years ago... oh it was.

fyborg_1138
03-23-2006, 10:54 AM
I found this explanation for KD at Wiki:

In computer science, a kd-tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. kd-trees are a special case of BSP trees.

A kd-tree uses only splitting planes that are perpendicular to one of the coordinate system axes. This differs from BSP trees, in which arbitrary splitting planes can be used. In addition, every node of a kd-tree, from the root to the leaves, stores a point. This differs from BSP trees, in which leaves are typically the only nodes that contain points (or other geometric primitives). As a consequence, each splitting plane must go through one of the points in the kd-tree.

Technically, the letter k refers to the number of dimensions. A 3-dimensional kd-tree would be called a 3d-tree. However, the phrase "3-dimensional kd-tree" is more commonly used. (It is also more descriptive, since a 3-dimensional tree could be any of a variety of different things, but the term kd-tree refers to a specific type of space-partitioning tree.) The letters k and d are both lowercase, even when the term comes at the beginning of a sentence, and the k is in italics. However, variant spellings are common, such as KD-tree and Kd-tree.

http://en.wikipedia.org/wiki/Kd-tree

After reading it several times, I'm still not sure what it all means or why it's better. It makes my head hurt too.

Jarno
03-23-2006, 08:00 PM
Putting it in more user-friendly terms, BSP and KD trees allow LightWave to quickly answer the question: "What stuff is present in this region of space".

For example, if you want to know if a point is inside or outside an object, a BSP tree of the the object can help tell you that fast. As another example, if you want to know what polygon a ray hits during raytracing, a KD tree can very quickly eliminate all the stuff that is not near the ray, leaving only a few polygons to actually test, without having to even look at all those other millions of polygons.

---JvdL---

Silkrooster
03-23-2006, 08:22 PM
The way I took this thread is that anything outside of camera view is not rendered. Correct?
Silk

jeremyhardin
03-23-2006, 08:27 PM
It's a good thing. And as soon as LW get's some sort of script editor to view render process stuff, and a way to input parameters for the bsp stuff, it'll be even better. :thumbsup: