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


    [prev]
    Image of the Day Gallery
    www.flipcode.com

    [next]

     
    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.
     
    Oligopod

    March 21, 2001, 04:12 AM

    Nice ones. I guess I'm much more lousy than you at internet research :) Looking forward to your code :)

    Greets,
    Nikolay

     
    Zemedelec

    March 21, 2001, 06:15 AM

    Zdravej zemliak,
    Vsushtnost CSG-to ti e preprocess a ne dynamic? Probval li si da go pravish realtime? V smisul che ako shte vkarvash towa neshto na praktika e dosta interesno ako towa se pravi na miasto i dinamichno, t.e. poluchenata forma da se promenia kato geometria (towa imam v predvid pod realtime, a ne proivane na dupki v steni, koeto sushto ne e losho...). Interesuvam se ponege sum si mislel za neshto takova, no niamah vreme za eksperiment. Keep the brutality!

     
    L.e.Denninger

    March 21, 2001, 06:47 AM

    Hey, stelletje buitenlandse flapdrollen, als je messages post is het wel de bedoeling dat je in het Engels schrijft zodat andere mensen het ook kunnen volgen.

     
    Frans Bouma

    March 21, 2001, 07:03 AM

    Zeg binnenlandse koeievlaai, waarom post jij dan in het NL, zodat je overbodige opmerking van generlei nut is? :)

    To all: post in english, so we all can enjoy your wisecracks and in depth POV's :)

     
    Oligopod

    March 21, 2001, 07:34 AM

    Zdrasti,

    (shte karam na angliiski horata da ne se iznervqt :))

    With O(n^2) worst-case I wouldn't dare go real-time :)

    Pozdravi,
    Niki

     
    Zemedelec

    March 21, 2001, 08:57 AM

    So, you don't know bulgarian?? Hell, I learn it when I was 3 years old :)
    Ok, sorry...

     
    L.e.Denninger

    March 21, 2001, 09:04 AM

    Christ, I think Mr. Bouma is a real rocket-scientist..!
    Frans - didn't you understand the joke or do you just lack a sense of humor ?

     
    kewldude

    March 21, 2001, 10:40 AM

    How does one define whats inside and whats outside, if the object isn't solid?

     
    L.e.Denninger

    March 21, 2001, 11:40 AM

    There's a general misunderstanding here about the terms 'convex' and 'solid' I think.

     
    idadesub

    March 21, 2001, 12:31 PM

    Are you using the definition of a solid to be an object with holes in it? Because that, in itself, is still a solid. Say you cut a cylinder out of a box. Sure, that creates a hole in the box, but that doesnt mean that the box does not have a clear inside/outside anymore. Those cylinder polys that are inside the box are added to that box's geometry. Therefore, those new polys define the boundary.

    The side benefit of using BSP, specifically Leafy BSPs, is that there is a real easy way of segmenting an object into empty, and non-empty spaces. I'll try to throw something up soon, the only prob is that its built into some other old code so it'll be kinda messy.

     
    Nexus

    March 21, 2001, 02:58 PM

    Yeah, we discovered that in this subthread - http://www.flipcode.com/cgi-bin/msg.cgi?showThread=03-20-2001&forum=iotd&id=21

    At my best I can manage English, Dutch, German and French... I think Bulgarian would be asking a bit too much from most of us, so yes, do please stick to English as much as you can.

    Out of interest, why is the main graphic on the index page of Lostboys games a picture of some combined metaballs? They make me go 'what the heck?' rather than 'ahhh nice'. I hope that an artist din't go running off at a tangent with some strange ideas...

     
    L.e.Denninger

    March 21, 2001, 03:06 PM

    You took the words right out of my keyboard :)
    I don't like it a single bit myself.

     
    m a d r i g a l

    March 21, 2001, 03:30 PM

    Looking forward to that ...

    Actually I mean 'not perfect' objects (without the means to repair them), as operands to boolean operations. I would like to cut or intersect a part of such an object with help of a pure solid object.
    I was wondering if Nayler's algorithm could segment the 'not perfect' object as such that the resulting boudary representation would at least contain a result (some errors are acceptable).

    - Ron

     
    m a d r i g a l

    March 21, 2001, 03:39 PM

    Continueing the discussion about solid/convex/csg:

    Actually I mean 'not perfect' objects (without the means to repair them), as operands to boolean operations. I would like to cut or intersect a part of such an object with help of a pure solid object.
    I was wondering if Nayler's algorithm could segment the 'not perfect' object as such that the resulting boudary representation would at least contain a result (some errors are acceptable).

    I have seen a program called 'Peak3D' do this to some acceptable extend (http://www.peakwork.de). Does anyone know how they managed to use intersection and difference operations on 'not perfect objects' using solid ones as the second operand?

    Any help would be appreciated.

    - Ron


     
    idadesub

    March 21, 2001, 03:45 PM

    Hmm, then I guess I dont understand what you mean by a "non-perfect" object. Can you give an example?

     
    m a d r i g a l

    March 21, 2001, 04:06 PM

    With a non-perfect object .. I mean an object that is not closed. The objects I have to work with sometimes have cracks, or some polygons are drawn too large. They are mostly constructed from NURBS surfaces or a mixture of them together with polygon techniques.

    A good example of such an object is a ship. The sides are constructed through some sort of NURBS surfaces and the other parts may be contructed through polygonal planes (like the deck for example).
    There exist t-junctions and some holes in the model, through this type of modelling. The model I would receive would me converted to a single mesh (triangles).

    Intuitively the object is solid to the eye.

    The question is if naylor algorithm can partition the object as such that I can retreive a subsection from the model by performing intersection and decrease the model by the subsection I've taken. The last step would imply a difference operation. The second operand would allways be a solid cube (probably triangulated).

    Any help would be welcome.

    - Ron

     
    Oligopod

    March 21, 2001, 04:08 PM

    Naylor's algo does roughly the following

    - make bsp trees out of the objects (say A, B)
    - push down the polygons of bsp tree A down bsp tree B and the polygons in B down A's tree, splitting when necessary. For each boolean operation, you know which bits of polygons to keep - either those that land on a front or back leaf. E.g. for addition (A+B) you would keep those that end on a front leaf. Also, for subtraction (A-B), you will need also to reverse the normal and vertex ordering of the polygons of B.

    So for example, if you add a cube and a single plane, whether you get "correct" result depends on where the plane's normal is pointing at. I think Naylor's algo wouldn't help you very much in the general case.

    Hope that cleared things a bit.

    Greets,
    Nikolay

     
    m a d r i g a l

    March 21, 2001, 04:12 PM

    I got that general idea ... some errors would be acceptable. The smaller the results get, the easier it is to repair them.

    Looking forward to some code ... as naylor's paper is still financially unattractive to buy :~)

    - Ron

     
    idadesub

    March 21, 2001, 06:43 PM

    Ooooh, ok I got ya now.

    Im not sure about nurbs and other implicit surfaces, but YES Naylor's algorithm will work. What wont work is if you try to do PVS stuff (I believe. I havent played with that yet).

     
    Sheep

    March 21, 2001, 06:46 PM

    BSP operations are inherently quite robust if you don't need a perfectly accurate result.
    Don't worry about it and it'll be mostly OK.
    Just remember to use a numerical error value or 'epsilon' value when comparing vertices against a clip plane.

    I've programmed BSP's and CSG stuff quite a bit but I wouldn't be able to prove that what I've just typed is in any way correct :)

     
    idadesub

    March 21, 2001, 06:53 PM

    Hey, check up a few msgs, i posted the link to the paper...

     
    Oligopod

    March 22, 2001, 03:44 AM

    I think it will work in this case, since you are missing just a small part of the polygon - the plane will still cover up for it. The problem arises when you don't have a plane - in this case the front-back test will screw up.

    Greets,
    Nikolay

     
    Angel Popov

    March 22, 2001, 03:51 AM

    Heh, dosta bulgari stanahme w tozi IOTD - da se razpisha i az.
    Dosta sym se zanimawal s BSP-style CSG - imam redaktor na niwa za 3D Engine, kojto mejdu drugoto prawi i bulewi operacii. Mojesh da widish screenshot na http://thegeleto.tripod.com/editor.jpg
    Ako se porazrowish w syshtata direktorija shte namerish i demo.

     
    Stu Milsten

    March 22, 2001, 03:54 AM

    Ok. This just blew.

    What a waste of time. It sucked ass. Thought I'd let you know.

    Don't quit your day job.

    Stu

     
    Numero27

    March 22, 2001, 07:05 AM

    Dont FEED THE TROLL.

     
    Jrz

    March 22, 2001, 07:28 AM

    hmm?
    I don't understand: )
    where does this come from

     
    L.e.Denninger

    March 22, 2001, 08:08 AM

    I think it was a hint not to reply on Stu's ignorant comment.

     
    Oligopod

    March 22, 2001, 10:21 AM

    Editor-a izglejda mnogo yako. Vsyshtnost zapochnah da se zanimavam s CSG, za da moga da pravq PVS i portali :-)
    A veche trqbva da iziskame i http://flipcode.bg mai :)

    Pozdravi,
    Niki

     
    Pierre Terdiman

    March 22, 2001, 11:14 AM


    www.codercorner.com/csg.zip

    Cute and useless.

     
    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.