ray casting

This is a discussion on ray casting within the Game Programming forums, part of the General Programming Boards category; Since it's tough to draw in 3D with paint, I made up a quick 2D example. In the example I ...

  1. #31
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Since it's tough to draw in 3D with paint, I made up a quick 2D example. In the example I only drew and split vertically and horizontally to make things simple, but in reality you wouldn't. Also notice that each divider lies on the same line as a wall -- this is because it would be impossible to check all of the planes, so you'd usually just use planes which a wall goes through. The other benefit of that is you won't split the polygon on which that plane lies.

    I'll post the process in 3 posts.

    Here's the original level:
    Attached Images Attached Images  
    Last edited by Polymorphic OOP; 12-10-2002 at 08:15 PM.

  2. #32
    Shadow12345
    Guest
    take your time man

    rest up a bit and do it tomorrow, I won't mind

  3. #33
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Here's the partition process:
    Attached Images Attached Images  
    Last edited by Polymorphic OOP; 12-10-2002 at 08:59 PM.

  4. #34
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    The partitioned level:
    Attached Images Attached Images  
    Last edited by Polymorphic OOP; 12-11-2002 at 01:19 AM.

  5. #35
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    The resultant binary tree:
    Attached Images Attached Images  
    Last edited by Polymorphic OOP; 12-11-2002 at 01:03 AM.

  6. #36
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Also notice that I took the process out until all of the sectors were convex!

    Each node that's not a leaf contains the data about the plane (in this case, line) that splits the sector into 2 parts.

    So, let's say you wanted to see what sector you were in.

    You take your position and first check to see what side of the dividing plane in the very TOP node you were on (or ON the divider).

    If you were on the positive side, you'd go to the node on the right, if youu were on the negative side you'd go to the node on the left.

    Then, from there you see what side of the divider you're on again and you go to the left or right if you're on the negative side or positive side.

    So you keep doing that until you're at a leaf. Once there, you know what sector you are in.

    You can use that data along with the possible visible sectors of that sector to easily calculate what you should draw. You can also use it to limit what you are checking collision with -- you only have to check collision with the polygons in that sector and adjacent ones (depending if your "body" extends between multiple sectors).

    Also note that in my version of BSP the tree would be slightly different in that anytime there was a split in a line, rather than splitting it, the line data would be stored at a different location being pointed to from the nodes.

    Actually, if you really wanna get into it, if a line is shared by 3 leaves in my form of BSP then

    leaf a would store all of the geometry that is SOLELY in a
    leaf b would store all of the geometry that is SOLELY in b
    leaf c would store all of the geometry that is SOLELY in c

    leaf 'a' would have a pointer to a 'a and b' group
    This 'a and b' group would store all of the geometry that is SOLELY in a and b

    leaf 'a' would also have a pointer to a 'a and c' group
    This 'a and c' group would store all of the geometry that is SOLELY in a and c

    leaf 'b' would have a pointer to the 'a and b' group that we talked about in leaf a

    leaf 'b' would also have a pointer to a 'b and c' group
    This 'b and c' group would store all of the geometry that is SOLELY in b and c

    leaf 'c' would have a pointer to the 'a and c' group that we talked about in leaf a
    leaf 'c' would also have a pointer to the 'a and c' group that we talked about in leaf b

    The 'a and b' group would have a pointer to a 'a and b and c' group
    This 'a and b and c' group would store all of the geometry that is SOLELY in a and b and c

    The 'b and c' group would have a pointer to the 'a and b and c' group that we talked about in the 'a and b' group

    So, when you are about to draw a sector, you go through the pointers drawing each group. As soon as you draw a group, you flag it with the frame number so that you know if you've drawn it already.

    Example:

    A is visible so you draw all the geometry solely in it.
    You go to draw the groups it is a part of as well.
    First, 'a and b' group:
    You flag 'a and b' group as you draw it.
    That group also points to 'a and b and c' group.
    You flag 'a and b and c' group as you draw it.
    These are all the groups pointed to from 'a and b' group

    Second, group 'a and c' is pointed to from 'a'
    We draw all of the geometry solely in 'a and c' group.
    Then, we notice that it points to 'a and b and c' group. Look it's already flagged -- that means we don't have to draw it!


    B is visible so you draw the geomtry solely in it.
    When you are about to draw 'a and b' group you check the flag -- it was drawn this frame so you don't have to draw it again! Since you know 'a and b' group was drawn then you don't even have to check group 'a and b and c' because you know that it was already drawn.
    B also has a pointer to group 'b and c'
    It's not flagged yet, so we draw it and flag it.
    Group 'b and c' has a pointer to 'a and b and c' group. It's already flagged so we don't have to draw it.

    C is also visible so you draw all the geometry solely in it.
    Then, we go to draw the groups it points to:
    group 'a and c' is already flagged so we don't draw it.
    group 'b and c' is already flagged so we don't draw it.

    And there you have it! Everything get's drawn. No polygons are split (unlike Carmack's method), and there is still no redraw!



    No watch as everyone starts implementing my version of a BSP tree hehe
    Last edited by Polymorphic OOP; 12-11-2002 at 01:53 AM.

  7. #37
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Oh come on, I took all that time to make those diagrams and there's not even a response!

  8. #38
    Shadow12345
    Guest
    actually i made a lengthy response quite some time ago but that was at school and i suspect it may have been blocked

    my response was at least a page

  9. #39
    Magos818
    Guest
    It was a nice explanation. I used to work alot in Worldcraft, making Quake and halfLife maps. It was informative to understand what a bsp file actually is.

    In the 'simple' figure you had, the making of sectors was pretty easy, but how does it work in a more complex map? I doubt you split it in every possible 'cube'.

  10. #40
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    That was me BTW, I really hate it when you're not getting logged in if going here from Hotmail...
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  11. #41
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Actually, it's done exactly the same way in 3-Dimensions. Whether or not the person chooses to make their implementation go all the way down into convex sets is another story, but it's highly beneficial if you do. Portals with convex partitions and possible visible sets can make culling extremely fast. Without completely convex sets, frustum culling becomes much more difficult because you are no longer just concerned about just the portals, but also all of the geometry that *might* be blocking your way to another sector.

    The reasons one wouldn't want completely convex sectors are

    1) It can cause a lot of polygons to be split in the partitioning process (though in my implementation no polygons get split so that is not an issue)

    2) What if you have a sphere in a room in your level -- that type of "inversely closed" structure, especially with complex geometry tosimulate curves, causes an extreme amount of unwanted partitions. The way you get around that is you don't make them a part of the partition process -- instead, you count its polygons as though the sphere was there but don't even look at its geometry in terms of the partitioning process, but you use a formula for a sphere for both lighting and for collision -- after all, It's supposed to model a sphere and even though you can't use polygons to make it perfect, you can use a formula to get much faster and much more accurate calculations for collission and lighting. The problem with that is it goes back to the problem with portal checking (if you are using portals, that is), so either you'd just pretend it wasn't there for that case -- basically just treating the sphere the same way you'd treat a player model, even though it's an actual part of the level (which is what I suggest), or you'd have to go out of your way to check collission with your frustum on the potentially high-polygon sphere, which is usually not a good idea because it introduces a lot of extra calculations that will most-likely take more time than if one were to just ignore it.

  12. #42
    Shadow12345
    Guest
    I really don't know what to say right at this moment. The post I tried posting before basically suggested you taking this and turn it into an online tutorial, because I haven't seen .bsp explained this well anywhere.

    Your posts went above and beyond and I'm really really happy that you took the time to explain how the bsp process works. I have a better idea now about it than I ever have before.

    I don't have anymore questions at the moment, I'd just like to thank you again for being cool because I haven't ever seen anyone put that much effort into teaching.

    EDIT:
    Is an octree necessary if you use the bsp format?
    Last edited by Shadow12345; 12-12-2002 at 07:52 AM.

  13. #43
    Visionary Philosopher Sayeh's Avatar
    Join Date
    Aug 2002
    Posts
    212
    It may sound anal, but the point of BSP is NOT finding intersections, it's for calculating partitions.
    I reread your description, and looked at your drawings again-- which are different from standard BSP. I think your viewpoint is slightly skewed by the way you are implementing your own version of BSP. I'm not faulting you, what you're doing is fine, it just is a variation on what I was expecting.

    I'm talking vector mathematics here (analytical geometry). The term "partition" is a gamer's term, not a math term. I'm talking about planes and their instersections. Described as vectors and associated normals.

    The whole point behind the BSP algorithm is to break an internal (ie. CONCAVE) space into it's smallest form (ideally a cube or oblong) where no planes overlap when viewed from within that "box".

    Carmack's method is very effecient in the sense that it had little actual decision making to perform (decisions take time). He would essentially determine on which leg of the tree the POV was, and then travel the opposite leg until it hit a leaf. Then without thinking, he'd simply draw the vectors (ie. "partitions") by traversing the tree in reverse back to the node the POV was in.

    It's an excellent 80% effecient method for anyone trying to learn and understand how to work with vector math, and the concept of BSPs.

    Carmack was way ahead of everyone else at that time.

    ---

    Nice drawings, by the way-- a lot of effort went into what you did.
    Last edited by Sayeh; 12-12-2002 at 03:28 PM.
    It is not the spoon that bends, it is you who bends around the spoon.

  14. #44
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078

    Angry

    Originally posted by Sayeh
    I reread your description, and looked at your drawings again-- which are different from standard BSP. I think your viewpoint is slightly skewed by the way you are implementing your own version of BSP.
    Actually, what I showed is about as pure as you can get in terms of the partitioning process without going into 3-Dimensions. Yes that's "Standard" (even though there really is no "standard" implementation." That's not a "skewed" interpretation.

    In fact, it's NOT like mine because I actually split polygons in that example and stored them in leaves. I don't do that in my implementation. Unless youare talking about my description of stored polygon "groups" in which case I was talking about my implementation. In fact, I made it a point to specifically state as such!

    If, for some reason you think that BSP is different, then post what you think it is (and I can tell you right now that you'd be wrong).

    Originally posted by Sayeh
    I'm talking vector mathematics here (analytical geometry). The term "partition" is a gamer's term, not a math term. I'm talking about planes and their instersections. Described as vectors and associated normals.
    Which leads me to believe youdon't know what a partition is. Plane intersection is not a partition and vectors have 1 normalized version and an infinite number of normals associated with them. Planar intersection can not be described by just vectors an normals because intersections have a location in space. Vectors don't. Also, normals don't mean anything at all with planar intersection because the intersection is line which has infinitely many normals -- just like a vector. A partition here is a sector, not a divider. If you don't understand that much, then you don't understand what BSP is. Go take a linear algebra course.

    Originally posted by Sayeh
    The whole point behind the BSP algorithm is to break an internal (ie. CONCAVE) space into it's smallest form (ideally a cube or oblong) where no planes overlap when viewed from within that "box".
    No, the original purpose was to break things down into concave partitions. If your level was completely concave from the start, then you most likely wouldn't use BSP. Also, if your level was concave from the start you'd have a pretty retarded level because it would be a closed figure with nothing obscuring your vision across the entire world. It would be a box or a pyramid or something similar. BSP was originally solely for draw order -- back before z-buffers. That was the original reason that you had to split polygons and get things into concave sectors -- like you said and I said before, no overlap.

    Either you are confused or you don't understand the word concave. Go look it up.

    Originally posted by Sayeh
    Carmack's method is very effecient in the sense that it had little actual decision making to perform (decisions take time). He would essentially determine on which leg of the tree the POV was, and then travel the opposite leg until it hit a leaf. Then without thinking, he'd simply draw the vectors (ie. "partitions") by traversing the tree in reverse back to the node the POV was in.
    Then you don't understand what Carmack is doing. For one, you're using POV in a silly sense -- what you most likely meant was the players position. His point of view doesn't have anything to do with traversing the tree, it's only looked at AFTER the sector in which the player lies is found. He traverses to a leaf and doesn't stop at a "leg." Even if he did, he'd have no way to determine which leg to stop at because the player exists "in" all of the nodes which go from the leaf to the whole. You aren't understanding the entire concept of BSP. Also, now you are calling a vector a partition. A partition is a sector, not a vector, not an intersection of planes (which are two very different things. Earlier you said it was the intersection of planes which is a line NOT a vector). On top of that, you said he draws the vectors which shows that youdon't even know what a vector is. You can't "draw" a vector because it has no location and takes up no space -- it's just a concept that represents direction with magnitude. And finally you are saying that he traverses back to where the POV was, which again, just shows that you don't understand the process. The player is in ALL of the nodes that lead up from the leaf where he lies to the original entire world (NOT leg). If he drew everything that lead all the way back to the master node, then he would have, in effect, draw the entire level, which would have accomplished absolutely nothing. You don't understand thewhole concept behind BSP or vector mathematics or even the proper terminology. Don't try to tell me I'm wrong when you obviously have absolutely no idea what you are talking about!

    Originally posted by Shadow12345
    Is an octree necessary if you use the bsp format?
    Octree is a completely different type of partitioning. It is not directly related to BSP in any way. I'd diagram that process as well, but it's pretty impossible to diagram in 2D.
    Last edited by Polymorphic OOP; 12-12-2002 at 05:39 PM.

  15. #45
    Shadow12345
    Guest
    Originally posted by Polymorphic OOP

    Octree is a completely different type of partitioning. It is not directly related to BSP in any way. I'd diagram that process as well, but it's pretty impossible to diagram in 2D.
    I understand that. The thing I don't understand is if octree is necessary if you already have bsp implemented in your game. I assume it isn't, but seeing as how I don't know the specifics of either i cannot be sure.

Page 3 of 5 FirstFirst 12345 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help designing a recursive function.
    By broli86 in forum C Programming
    Replies: 3
    Last Post: 07-24-2008, 01:45 PM
  2. Casting
    By morvick in forum C++ Programming
    Replies: 2
    Last Post: 06-18-2007, 12:06 AM
  3. Ray tracer and collision detection
    By hdragon in forum Game Programming
    Replies: 31
    Last Post: 01-19-2006, 11:09 AM
  4. question about casting pointers/other types also??
    By newbie02 in forum C++ Programming
    Replies: 3
    Last Post: 08-07-2003, 06:01 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21