ray casting

This is a discussion on ray casting within the Game Programming forums, part of the General Programming Boards category; well the idea is to know how to read in a bsp so you can create a world using a ...

  1. #16
    Shadow12345
    Guest
    well the idea is to know how to read in a bsp so you can create a world using a bsp tool (q3 radiant which i have never used or possibly worldcraft, although technically you aren't supposed to use the latter) and then convert it to your own format. I find that 'formats' in game development barely differ from one to the other. order and then some original stuff, but it's all mostly a change in order.

  2. #17
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Yeah, but then you don't have any envolvement with the actual partitioning, you just depend on how other programs partitioned the level. There's no fun in that :/ You don't really learn anything about the BSP process, just how to deal with the results.

    In my method of BSP, I developed a way to handle BSP without splitting polygons between sectors. Instead, the shared group is stored in another location and when it comes time to drawing it flags the group as being drawn so it knows whether or not it should draw it if two or more sectors are visible which have that shared group. That way, you avoid redraw and can keep the exact geometry from the original map.

    Usually people (including Carmack) actually split the polygons so that none span past 1 sector. I don't think that's very intuitive. Not like I'm sayng that I think my concept is better, but I haven't yet run into a reason why my implementation is bad, and if I had used Carmack's BSP, I wouldn't have ever been able to do something like that.

  3. #18
    Shadow12345
    Guest
    i haven't written anything for bsp loaders myself, i've only barely looked at them and it is obvious you know more about them than I do. So you are saying the main difference between your implementation of bsp is you have shared polygons between sectors in a completely different 'group' so you don't have to clip away parts of polygons when drawing. Does this mean it only draws these shared polygons when both sectors that share them are visible? You said your implementation cuts down on redraw, I assume you mean your implementation avoids drawing the same polygons more than once. However I don't think the 'carmack' process draws more than once, does it? I mean it calculates what is clipped away and draws only what is visible.

    What is the visible portion (the portion that isn't clipped away) called? Is that called a leaf? I am not up-to-date on my .bsp terminology.

  4. #19
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Originally posted by Shadow12345
    i haven't written anything for bsp loaders
    I'm talking about an actual Binary Space Pertitioner -- it actually does the partitioning, not the loading, but I have also created a loader for it as well. Carmack's BSP format is probably very different.

    Originally posted by Shadow12345
    So you are saying the main difference between your implementation of bsp is you have shared polygons between sectors in a completely different 'group' so you don't have to clip away parts of polygons when drawing.
    So I don't split parts while partitioning (IE when the file is created), You never should have to split polygons during draw phase in either implementation.

    Originally posted by Shadow12345
    Does this mean it only draws these shared polygons when both sectors that share them are visible?
    No, the group is drawn when any of the sectors that contain it are visible, but as soon as it's drawn, the group is flagged with the current frame number so that if it finds that another sector is visible it knows not to draw that group again. Each sector has pointers to all of it's "shared" polygon groups.

    Originally posted by Shadow12345
    However I don't think the 'carmack' process draws more than once, does it? I mean it calculates what is clipped away and draws only what is visible.
    Correct, Carmack avoids redraw as well -- only he avoids it by physically splitting the polygons (which is exactly what I avoid). That way, he draws everything in a sector once he knows it's visible -- without performing any other checks. He doesn't have to test for redraw because that's all implicit. But the problem with that is -- anytime a partition goes through a polygon, it has to split it into pieces (and it's rarely 2 pieces because we're talking triangles, not quads). So when he is doing the actual partitioning of the level, one thing he has to look out for is how many polygons he is splitting -- more is bad because you don't want to draw an extra 10 or 20 polygons per sector. Since I don't actually physically split the polygons, I don't have to worry about that, and I can be more concerned about creating a balanced tree than about avoiding polygon splits.

    Originally posted by Shadow12345
    What is the visible portion (the portion that isn't clipped away) called? Is that called a leaf? I am not up-to-date on my .bsp terminology.
    I dont really use standard terminology because my implementation is quite different, but the leaves in my implementation are the actual unpartitioned sectors. Everything "above" them in the tree are dividers, while the leaves are the result of all the partitioniong.
    Last edited by Polymorphic OOP; 12-08-2002 at 05:01 PM.

  5. #20
    Banned frenchfry164's Avatar
    Join Date
    Oct 2001
    Posts
    1,552
    gosh you're smart

  6. #21
    Registered User
    Join Date
    Aug 2001
    Posts
    380

    Re: Re: ray casting

    Originally posted by Magos
    I'm not sure why you would like to do a raycaster. With Direct3D or OpenGL it would probably be easier to make a 'real' 3D program/game.

    http://www.gamedev.net/reference/art...article872.asp

    http://www.cs.unc.edu/~hoff/projects...t/raycast.html
    I would like to create a ray casting game engine for an education purpose. Plus my video card doesn't support Direct3D or OpenGL. Would it be wise to use dos mode 13h for this project?
    Don't you dare hit me on the head, you know I'm not normal.
    A Stooge Site
    Green Frog Software

  7. #22
    Visionary Philosopher Sayeh's Avatar
    Join Date
    Aug 2002
    Posts
    212
    Originally posted by Polymorphic OOP
    BSP trees don't have anything (directly) to do with ray casting/tracing, except ruling out where you shouldn't be tracing to. Just because something uses BSP trees doesn't mean it doesn't use casting.
    Not quite. Although your meaning is somewhat correct, fundamentally the reason the two are compared the way I did is because each is a method of determining intersections. Nothing more, nothing less.

    When you cast a ray, you are looking for intersections at regular intervals, as in a ray-casting engine. When you intersect a view frustrum with a vector as in a BSP engine, you are looking for intersections. The fact that BSP lends itself extremely well to HSR (Hidden surface removal) is a secondary benefit of using the BSP method.

    Don't confuse drawing slices with casting/tracing.
    It is not the spoon that bends, it is you who bends around the spoon.

  8. #23
    Shadow12345
    Guest
    I'm talking about an actual Binary Space Pertitioner -- it actually does the partitioning, not the loading, but I have also created a loader for it as well. Carmack's BSP format is probably very different.
    I guess that is what I was getting hung up on. I thought you meant you were loading an already partitioned bsp and that the way the other people did it was by splitting up 'shared' polygons among groups, and that you somehow found a way to put these back together or something
    So I don't split parts while partitioning (IE when the file is created), You never should have to split polygons during draw phase in either implementation.
    Doesn't standard frustum culling require you to split polygons before they are drawn, i.e create a new, smaller polygon that fits within the viewing volume (all of this determined mathematically). Or does it just calculate whether it is 'mostly' in or 'mostly' out of the viewing volume and either draw it or not draw it, but completely avoid the splitting.

    I was re-reading your post poly explaining what bsp is. The part i don't really understand is
    Usually when one would make a BSP tree they'd keep partitioning until all of the leaves of the tree were concave.
    what exactly is a leaf and how would they become concave? I don't know if this is an appropriate question, but how does a world get partitioned, i.e is it split up in a pie form with all of the partitioning boundaries intersecting at the middle? Erm...yeah...

  9. #24
    Shadow12345
    Guest
    this is what I was asking, maybe you could add/change to my drawing to make it corrrect.
    Attached Images Attached Images  

  10. #25
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Originally posted by Sayeh
    Not quite. Although your meaning is somewhat correct, fundamentally the reason the two are compared the way I did is because each is a method of determining intersections. Nothing more, nothing less.
    It may sound anal, but the point of BSP is NOT finding intersections, it's for calculating partitions. They are not really the same thing -- it's just that BSP makes working with intersections easier.

    Doesn't standard frustum culling require you to split polygons before they are drawn, i.e create a new, smaller polygon that fits within the viewing volume (all of this determined mathematically). Or does it just calculate whether it is 'mostly' in or 'mostly' out of the viewing volume and either draw it or not draw it, but completely avoid the splitting.
    No, that would take too long because it would require you to check every polygon in the visible sectors and then you'd have to figure out which to cull out and which to split. It would take more time to do that than it would to accept drawing what's not visible. You basically just draw visible sectors and don't do any further than that. Otherwise it becomes counter-productive.

    what exactly is a leaf and how would they become concave? I don't know if this is an appropriate question, but how does a world get partitioned, i.e is it split up in a pie form with all of the partitioning boundaries intersecting at the middle? Erm...yeah...
    The leaves are where the geometry for all of the sectors go, the rest of the tree is all of the partitions that lead up to the leaves. You don't partition in a pie form -- at least not in BSP. The reason BSP is called binary space partitioning is the fact that with each action you partition the current sector into 2 parts. You usually try to do this having equal polygon counts on each side.

    If you understand binary trees, this shouldn't be a difficult concept.

    So you start with a full world. Then you split it in half -- then, you split those 2 into 2 more halves, etc. and you keep going until you are left with a bunch of small sectors.

    A concave sector is a sector made of polygons all facing inward with no overlap (IE a box). The reason for this is -- from within the box, no 2 walls can ever overlap each other. When you make all of your sectors concave like this, you only have to worry about drawing the furthest sector first, etc. and not have to worry about the order of drawing polygons within the sector because they themselves will never overlap.

    Again, that's not as necissary with z-buffers, but z-buffers are only so accurate while the former concept is 100% accurate and fast.

    The reason you used to want to always have concave sectors (and many times you still want to).

  11. #26
    Shadow12345
    Guest
    The leaves are where the geometry for all of the sectors go, the rest of the tree is all of the partitions that lead up to the leaves. You don't partition in a pie form -- at least not in BSP. The reason BSP is called binary space partitioning is the fact that with each action you partition the current sector into 2 parts. You usually try to do this having equal polygon counts on each side.
    technically the pie thing fits that definition, but i guess it ends up looking like a grid. now that i think about it i already knew that because the 'vis' portion of the compile process calculates everything that can be seen at each block of the bsp

    You basically just draw visible sectors and don't do any further than that. Otherwise it becomes counter-productive.
    The debate is over whether or not polygons get split. I am posting on gamedev.net to find out. splitting polygons does seem like extra unnecessary work, so you are probably correct. You probably know this already but I am going to be a butthead and say it anyway: in order for a polygon to be 'visible' it has to pass the viewing volume test, this means checking polygons to see if they intersects with or are in front the six (or five, depending if you have back face culling) sides of a viewing volume.
    Last edited by Shadow12345; 12-10-2002 at 05:01 PM.

  12. #27
    Shadow12345
    Guest
    is this more what the partitioning process looks like? (mind my inability to draw parallel lines)
    Attached Images Attached Images  

  13. #28
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Originally posted by Shadow12345
    (mind my inability to draw parallel lines)
    If you're using paint, hold Shift when drawing lines .
    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.

  14. #29
    Shadow12345
    Guest
    Originally posted by Magos
    If you're using paint, hold Shift when drawing lines .
    DUDE! SWEET! OMG!!! I DIDN'T KNOW YOU COULD DO THAT!!! WOOHOO!!!

    thx lol

  15. #30
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Originally posted by Shadow12345
    technically the pie thing fits that definition, but i guess it ends up looking like a grid.
    It's possible that BSP can result in a "pie" cut, but it all depends on the geometry.


    Originally posted by Shadow12345
    The debate is over whether or not polygons get split. I am posting on gamedev.net to find out. splitting polygons does seem like extra unnecessary work, so you are probably correct.
    Polygons DO get split -- just not during the draw phase, they get split while the level is being partitioned.

    Originally posted by Shadow12345
    You probably know this already but I am going to be a butthead and say it anyway: in order for a polygon to be 'visible' it has to pass the viewing volume test, this means checking polygons to see if they intersects with or are in front the six (or five, depending if you have back face culling) sides of a viewing volume.
    That's how you'd know if it MIGHT be visible.

    If it is visible is a whole 'nother story, because polygons can be behind other polygons depending on the angle -- which is the whole reason people often make "possible visible sectors" for each sector -- to limit the checking for which sector is visible by the ones that can only possibly visible from within side that sector. This is also handled by clipping the view frustum through portals depending on implementation.

    Originally posted by Shadow12345
    is this more what the partitioning process looks like? (mind my inability to draw parallel lines)
    No -- each partition barrier should NOT go through other barriers -- it should stop when it hits one because each recursive split in BSP represents a split ONLY for that sector. It's extremely different from a partition grid. I'll draw up a quick example of a partitioned level.

Page 2 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