Results 1 to 10 of 10

Thread: What the heck is this?!!

  1. #1
    Audere-Est-Facere adrian's Avatar
    Join Date
    Mar 2003
    Location
    Brighton, UK
    Posts
    2,472

    What the heck is this?!!

    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!!
    Adrian.

    "Dreams are good, but memories are better"

  2. #2
    User.
    Join Date
    Nov 2005
    Location
    Prizren, Dardania
    Posts
    2,374
    Quote Originally Posted by adrian
    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

  3. #3
    Back from Monkey Island Weetos's Avatar
    Join Date
    May 2003
    Location
    France
    Posts
    943
    BSP stands for Binary Space Partitioning, see there

    dunno what KD is though

  4. #4
    Audere-Est-Facere adrian's Avatar
    Join Date
    Mar 2003
    Location
    Brighton, UK
    Posts
    2,472
    Thanks for the link - everything is as clear as mud now

    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?"
    Adrian.

    "Dreams are good, but memories are better"

  5. #5
    Eingetragenes Mitglied Dirk's Avatar
    Join Date
    Apr 2003
    Location
    Germany, Hessia
    Posts
    920
    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.
    "The rule is, jam to-morrow and jam yesterday - but never jam to-day." "It MUST come sometimes to "jam to-day,"" Alice objected.

    My stuff at YouTube

  6. #6
    Not so newbie member lardbros's Avatar
    Join Date
    Apr 2003
    Location
    England
    Posts
    6,049
    Quote Originally Posted by Dirk
    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.
    LairdSquared | 3D Design & Animation

    Desk Work:
    HP Z840, Dual Xeon E5-2690 v2, 32GB RAM, Quadro K5000 4GB
    Desk Home:
    HP Z620, Dual Xeon E5-2680, 80GB RAM, Geforce 1050 Ti 4GB

  7. #7
    Newbie Member fyborg_1138's Avatar
    Join Date
    Feb 2006
    Location
    Illinois corn fields
    Posts
    59
    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.

  8. #8
    LightWave Engineer Jarno's Avatar
    Join Date
    Aug 2003
    Location
    New Zealand
    Posts
    625
    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---

  9. #9
    Super Member Silkrooster's Avatar
    Join Date
    Mar 2004
    Location
    Northern New York
    Posts
    5,254
    The way I took this thread is that anything outside of camera view is not rendered. Correct?
    Silk
    Silkrooster.com - temporarily offline due to updating...
    Spinquad Forum - Closed Sorry...
    lightwave-resources.pdf - - temporarily offline due to updating...

  10. #10
    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.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •