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

 Home / 3D Theory & Graphics / CSG tutorials Account Manager
 
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.
 
JeroenNL

May 09, 2005, 03:15 PM

Hi there,

I'm trying to implement CSG into our editor (DeleD - http://www.delgine.com) using BSP trees. I'm using the tutorial found at http://www.delphi3d.net/articles/viewarticle.php?article=csg.htm but I can't help thinking that tutorial is not telling me everything I need to know.

Does anybody know of other good tutorials like the one mentioned? I've googled but have not been able to find something useful yet.

Thanks,
JeroenNL

 
Paul Holverda

May 09, 2005, 04:52 PM

Hi Jeroen,

I've bet you from the Netherlands :D,

i've got a fully working csg compiler, that can handle brush based volumes, like the ones found in quake etc.

send me a line at paulholverda( @ ) gmail.com

i can send you the code if you wanted.

pics of the csg can be found here home.hccnet.nl/pj.holverda/jid2

cheers

Paul

 
Paul Holverda

May 09, 2005, 04:54 PM

sorry i meant this site

http://home.hccnet.nl/pj.holverda/JiD2/

cheers,

Paul

 
JeroenNL

May 10, 2005, 01:57 AM

Thanks, mail sent! :D

Of course, if anybody else knows of additional tutorials/help, please do tell. :)

 
Gerald Knizia (cgk)

May 11, 2005, 08:49 AM

If you have specific questions about CSG, you could still ask these in the forums here. There are several regulars on this board who have worked with and used CSG.

Also note that there is not one single way to do it, there are many different ones. And a tutorial would only show you one way anyway. The article link you posted is most probably also not what you are looking for. It gives you an hint on how you might approach the atomistic splitting operations, but everything that is complicated (like handling coplanar cases, rounding, how to avoid unnecessary splits/join split polygons, how to do the high level csg loops) is left out.

 
Kanda

May 11, 2005, 10:55 AM

I strongly recommend you the course on gameinstitute. Maybe little expensive, but very instructive, all you need to know about bsp, portals and csg are in the BSP course. So if you are stuck and have the money for the course, i recommend you to enroll this course, it will help you quite a lot.

 
JeroenNL

May 12, 2005, 04:36 PM

Also note that there is not one single way to do it, there are many different ones. And a tutorial would only show you one way anyway. The article link you posted is most probably also not what you are looking for. It gives you an hint on how you might approach the atomistic splitting operations, but everything that is complicated (like handling coplanar cases, rounding, how to avoid unnecessary splits/join split polygons, how to do the high level csg loops) is left out.


That is exactly the reason why I'm looking for more than just that tutorial. I've managed to implement CSG using BSP trees in the way that tutorial is suggesting (see http://www.delgine.com/forum/viewtopic.php?t=637) but I'm not done yet. I know there are a number of cases my implementation can't handle yet and I'm sure I will be asking a few more questions around here. Still, if you know of other methods to perform CSG and have relevant info/links to share, please step forward. :)

 
Gerald Knizia (cgk)

May 13, 2005, 02:55 AM

Well, I made a fairly complete and working implementation of "Level Editor CSG" algorithms (http://wh12.tu-dresden.de/~cgk/, Projects [1]). But I kind of figured it out all by myself, so there are not really any links or tutorials I can suggest you. However, I can answer or give hints to solutions on specific questions most probably.

[1] Please ignore the text of the old homepage, if you should go there :]

After reading though the original link you posted again, I noticed that I misread something and the article is actually okay (it even does handle the coplanar cases in a manner that looks kind of right) for a description of the atomic splitting operations. I do that in a similar way. There are some hints that are not meantioned there, but imo should be:
a) You really should join polygons after CSGing. Keeping around the original polygons and using them if nothing was split is probably not a good idea, as you will usually have a lot of splits that can be removed and some that can't. For this task, just give each "source" polygon a unique id and replicate this among all split fragments. This way, all fragments with the same id can be joined. In my projects I allowed concave polygons. It makes some things easier and some quite a bit harder tho.
b) Write your code in a way in which you can easily replace number formats of positions and normals (i.e. float32 by float64 or fixed point). Also, _never_ hardcode epsilons. Think a lot about how large epsilon values for specific tasks should be and where you should use additive and where modulative epsilon tests (i.e. |a/b-1| approx 0 instead of |a-b| approx 0)
c) When CSGing, you _never_ need to generate new polygons, only split polygons which have been there previously. But it seems you have figured that out by yourself already :]

 
JeroenNL

May 13, 2005, 08:56 AM

a) You really should join polygons after CSGing. Keeping around the original polygons and using them if nothing was split is probably not a good idea, as you will usually have a lot of splits that can be removed and some that can't. For this task, just give each "source" polygon a unique id and replicate this among all split fragments. This way, all fragments with the same id can be joined. In my projects I allowed concave polygons. It makes some things easier and some quite a bit harder tho.


I am sort of joining polys after CSG. In short, for each original polygon, I'm keeping count of how many times it is split + the number of times a polygonfragment is added to the final result. If those numbers are the same, I can use the original polygon instead of the fragment. This is giving me good results as you can see here http://www.delgine.com/forum/viewtopic.php?t=191.

I am, however, not yet joining polygonfragments together as I don't know how to go about that yet. I can imagine other cases where some fragments can very well be joined together. What would be a good algorihm to join fragments?

 
Rui Martins

May 13, 2005, 01:45 PM

You have a real problem in your hands !

You shouldn't have any T junctions in the final result, that wll most certainly result in rendering artifacts, since there is no garantee that the larger poly (the one over the T) will raster to the exact same pixel(s) has the two neighbours (on each side of the T).

The output should look more like 4 fans with their centers in each of the 4 corners. You will also have 4 tris or quads which will make the orignal wall edges collate with one of the cilinders sides.

Hope you get the ideia.

 
Gerald Knizia (cgk)

May 13, 2005, 03:20 PM

What I do to join fragments is actually pretty simple (from the idea point of view): whenever two fragments contain an edge that partially overlaps, they are joined by removing the overlap and merging the rest of both fragments. This will of course result in concave polygons usually. So in the scene you posted, my editor would produce one single (concave) polygone for the front side (i.e. the quad with the hole), which gets triangluated in the final geometry processing (using libtess, i.e. the gluTess* functions of glu. This does not even bind to the OpenGL DLLs.)

Therefore my results would look like this:
http://wh12.tu-dresden.de/~cgk/one_hole.png
http://wh12.tu-dresden.de/~cgk/two_holes.png

Rui Martins has a very strong point with the T-Junctions. T-Junctions are very evil and should be avoided if possible. But imo this is not a task that should be consided in the initial CSG pass (not even sure if this would be possible at all). T-Junctions can be fixed at a later point--and you probably need a more CSG-independent way of doing this anyway, for example if you want to implement subdiv surfaces.

 
JeroenNL

May 20, 2005, 09:39 AM

Thanks very much for your helpfull replies. I've reached the stage where I will be joining polygons (and possibly triangulating them again) and I'm sure I will come across a few other questions shortly. ;)

 
M.Knuth

May 24, 2005, 06:50 AM

There exists a library, which can do the boolean Operations for you, since CSG with bsp-trees is a error-prone method.

gts.sourceforge.net

Besides it solves the retriangulation of the geometry for you :)

 
JeroenNL

May 27, 2005, 08:56 AM

I'd rather code things myself. ;) What would be a good algorithm to determine if two edges (partially) overlap?

 
This thread contains 14 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.