Not logged in, Join Here! or Log In Below:  
News Articles Search    

Submitted by Nikolay Stefanov, posted on March 20, 2001

Image Description, by Nikolay Stefanov

These are a couple of pictures from a CSG demo I've been working on for the past few days. Features include :
  • BSP-style CSG (Naylor's algo)
  • thick BSP planes
  • DirectX 8 rendering
  • loading of X files for primitives
  • command line interface
  • horrible asserts from time to time :-)
  • I plan to release the demo and the source in the next few days, as soon as I optimize the code a bit. Btw, the 1011 FPS are real :) This is what you get from TBird 800 / GeForce2 with a few vertices in a buffer.

    Nikolay Stefanov aka Oligopod

    Image of the Day Gallery


    Message Center / Reader Comments: ( To Participate in the Discussion, Join the Community )
    Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
    Richard Garand

    March 20, 2001, 09:27 AM

    looks really nice. Do you export the results?


    March 20, 2001, 10:55 AM

    Very nice!
    Do you plan to give your command line interface the ability to perform batch processing?

    Bemmu Sepponen

    March 20, 2001, 11:34 AM

    > load fly
    > load seth_brundle
    > add fly seth_brundle brundlefly
    Objects combined at molecular level.


    March 20, 2001, 11:37 AM

    Have you ever heard of Insect Politics?


    March 20, 2001, 11:50 AM

    Not yet because I'm still struggling with DirectX 8 interfaces :-) The final demo will have that ability.


    March 20, 2001, 11:52 AM

    I already have this ability, although it doesn't show from the picture. I plan to include several of these files in the demo so that people can tweak them.


    March 20, 2001, 12:15 PM

    Would be cool to have a mesh class that can encapsulates CSG operations ;-)



    March 20, 2001, 12:22 PM

    Nah, just add some operators to your meshes.
    Works really cool, so you can add meshes, subtract 'em, whatever.


    Mesh new_mesh = cube + pyramid;
    new_mesh -= cylinder;


    March 20, 2001, 12:34 PM

    Looks cool!

    What size of objects can you handle before you start grinding to a halt?

    I recently coded a CSG thing, and had it running at around 30fps with 2 objects each around 2-300 faces intersecting.. (just flatshading, on a GeForce2)..

    Tobias Franke

    March 20, 2001, 02:06 PM

    What the hell is a CSG?


    March 20, 2001, 02:11 PM

    I think CSG is Constructive Solid Geometry or something like that


    March 20, 2001, 02:29 PM

    Yup, it is.
    Basicly, it's just boolean operators on solid volume descriptions.


    March 20, 2001, 02:55 PM

    Stupid me tried to drag the window in the image to have a better look at the other images underneath..

    Anyhow - very cool - how does your engine handle epsillion sized triangle slivers when you've csg'd an object several times? Do you have any plans for a polygon "optimization" pass for this, to remove over tesselation?

    Mech game where you can literally melt holes through your opposition - now that'd be sweeeeeet.

    Good work man.


    March 20, 2001, 03:10 PM

    i'm very interested into coding boolean operations can anyone say me where i can find tutorial, source code, & all the things i need??


    March 20, 2001, 03:42 PM

    Actually, I am not descending the BSP tree every frame (not drawing correctly back-to-front), I just draw a static vertex buffer, which is filled by the "show" command. So even thousands of faces draw fast enough (>300fps)



    March 20, 2001, 03:47 PM

    I don't handle these ####ing holes (T-junctions or whatever) in any way still, because I don't really know how to :)
    I am now working on the code that merges coplanar polygons that are on the same node of the BSP tree. I have left that for the last moment, after I finish with the basic functionality



    March 20, 2001, 03:50 PM

    Here is a good place to start (and in fact the only one I know)

    I will release the source code to this demo soon. If you have any questions, feel free to ask :)


    m a d r i g a l

    March 20, 2001, 04:02 PM

    Can your algorithm (naylor) work with objects that have holes?
    I'm trying to find an algorithm that doesn't have the contraint of objects need to be solid.
    Looking forward to your demo (and the code of course)

    - Ron


    March 20, 2001, 04:15 PM

    Yes, there's no problem with objects that have holes in them. Check the link I posted in a previous reply for a tutorial on Naylor's algorithm. Unfortunately, I cannot find an electronic version of the original paper - siggraph 90-something.



    March 20, 2001, 04:45 PM

    "Yes, there's no problem with objects that have holes in them."

    How can you do CSG with objects that aren't solid? Intuitively what does that mean?



    March 20, 2001, 05:09 PM

    For example look at the yellow cube with the carved sides (small picture). You can add / subtract any primitive... I guess it's not "Solid" geometry anymore, though :)



    March 20, 2001, 05:49 PM

    I'd disagree there... it looks like a solid object, as does the rotated cube that seems to have been taken out of the cube to give it...

    A non-solid object is a pyramid with no base, or a simple plane...

    Back to my computer graphics and programming of graphics knowledge ->

    Normal boolean operations on solids are defined as such-
    A Union of two objects contains all the points that were contained in the two objects.
    An Intersection contains all the points that were contained in both objects, without including planes or points. (so if two cubes of size 2x2x2 were placed at (1,0,0) and (-1,0,0) the intersection would be empty)
    A Subtraction contains all the points of the first object, without any that were in the intersection of the two objects.

    An important aspect of this is that these operations are CLOSED on solid objects, you cannot get an object that doesn't have a volume - which is why you have to have the careful definition of Intersection.

    Another operation that isn't as common is Cut (although it may be known as something else to other people) where you remove any points on the faces of the first object which would lie within the second. It is NOT closed. As an example, take a 4x4x4 cube centered at (0,0,0), if you cut from this a sphere of radius 1 centered at (2,0,0) you get a cube with a circular hole in the top face. It is nolonger a solid object.

    I think you've simply got the wrong definition of what a solid object is.


    March 20, 2001, 05:52 PM

    Hi! Lookin' really good!

    I'm really looking forward to read the code :o).. I wont be able to run it, cause I'm on NT 4.0...(Opengl rulez *G*)..



    March 20, 2001, 06:15 PM

    I guess I was wrong with the definition of a "solid" object indeed. The objects I was talking about are really "non-convex", which means that if you take two points inside them, the line that connects them is not necessarily contained within the object.
    I really haven't tested with non-solid objects and I might just as well do that :)



    March 20, 2001, 08:02 PM

    Welll ... I can get 1500 fps. Of course, my screen in empty, but it is nicely cleared by any color you want. And yes, blue color looks nice ! it remembers me about win98


    March 20, 2001, 08:07 PM

    Zdrasti Niki,
    ami kude sa sorsovete?
    imash li web-page?



    March 20, 2001, 08:15 PM

    My firs post was derived from my impression about your frame rates.
    Now about CSG
    CSG is cool.
    but I use modified CSG approach which is way better than known so far. Well, I plan to use it ... so thanks for more info about that topic. I'll try to understand why programs work so bad to make better one. And most of them works bad, believe me


    March 21, 2001, 01:05 AM

    Heh, yeah, I was hunting for some good CSG info for a while now. Here's what I've found... was going to put up a tutorial using BSP trees, but odd happened, and now ALL of his great tutorials disapeared. Strange. Now it seems his page is gone, replaced now only by his bbs. That bbs though still is a great source though for CSG info.

    Here's Naylor's paper Merging BSP trees yields polyhedral set operations.

    and Merging BSP trees yields polyhedral set operations.

    Lets see...

    here's formal definition of Naylor's merging BSP algorithm.

    Cuban has an short, but easy-to-read explanation.

    and the last one I got is just a presentation by Naylor.

    And that's about all I've found (other than Midnight's here). I wish, though, there were tutorials out there on this stuff. Reading these papers can be rough...

    Note, I havent yet figured out how to implement Naylor's second paper. I did get the first one though. If you're interested, I'll post up my source code too.


    March 21, 2001, 01:06 AM

    hey, I posted the link to the papers up a post or so...


    March 21, 2001, 04:06 AM

    mi sorsovete i web-page kato dovyrsha poslednite raboti deto mi ostanaha - oprostqvaneto i t.n. a tuka edno takova lqtno vreme che edvam se zasedqvam pred komp-a :)


    This thread contains 59 messages.
    First Previous ( To view more messages, select a page: 0 1 ... out of 1) Next Last
    Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.