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

Submitted by Paul Nettle, posted on November 13, 2000

Image Description, by Paul Nettle

This image shows the results from the CSG technique described in the accompanying Ask Midnight column entry.

The wireframe was provided to show the internals of the object. The polygons marked in red are the ones that were created as part of the Boolean Subtraction Operation.

Paul Nettle
Fluid Studios

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.
Douglas Cox

November 13, 2000, 11:21 AM

Is there a wireframe showing how many faces were added to the original box after the CSG op?

The flat shaded result looks nice though!


November 13, 2000, 11:29 AM

Boolean operations look pretty cool, and I consider them to be one of the best modelling tools available.

The Digital Bean

November 13, 2000, 11:31 AM

Nice... based on your post am I to assume that you took the Laidlaw approach ?


November 13, 2000, 12:14 PM

Nice I love boolean operators. I've implemented boolean for my to be 3d engine (actually it's a demo engine). I use superfast 2d projections of the objects to determine common points then I use octree to speed up interscetion calculations.
Digital Bean: What is the Laidlaw approach?
Paul: How do you do it?

Strepto / Astral

Kurt Miller

November 13, 2000, 12:18 PM

In case you missed the link in his IOTD description (and the one on the news page :), this IOTD goes along with Paul's Ask MidNight update about CSG which can be found right here.


November 13, 2000, 12:28 PM

Are these boolean operation done in realtime ? what is the goal of
this ?

Mark Friedenbach

November 13, 2000, 12:40 PM

The red lines in the model on the left.

Mark Friedenbach

November 13, 2000, 12:41 PM

Modelling and level design. Both UnrealEd and Worldcraft are based on this approach.

Douglas Cox

November 13, 2000, 01:06 PM

Uhm, that's not actually true. The original box would have several new faces creates with the subtractions. The image on the left shows the original wireframe box with the wireframes of the objects being subtracted.


November 13, 2000, 02:13 PM

Nah, I chose to take the snapshot with the interior edges turned off, because it really cluttered up the shot. It looks just like any other boolean object with a ton of fanned vertices out to the corner vertices.


November 13, 2000, 02:13 PM

Does the Laidlaw approach work for non-manifold solids?


November 13, 2000, 02:25 PM

The Digital Bean -
The laidlaw approach is described in the accompanying Ask Midnight column entry. You can find it here.
Strepto -
The Laidlaw approach, and how I did it (one in the same) are described in the accompanying Ask Midnight column entry. You can find it here.
mrz -
No. The requirements are described in the accompanying Ask Midnight column entry. You can find it here.
Is anybody seeing a pattern here? :)

- MidNight


November 13, 2000, 03:26 PM



November 13, 2000, 03:36 PM

Midnight - I've tried the BSP approach and found out that in several cases it adds a lot of polygons to the objects/scene.
I mean that in the sense that several planar polygons will be created by the splits and something like an optimizing phase to merge planar
polygons is needed or the polygon count goes through the roof. Is the Laidlaw method better in terms of not producing too many polygons
in your experience?


November 13, 2000, 04:23 PM

Having not coded the BSP technique, I'm not entirely sure that I understand all the details. Having said that...

In essense, the Laidlaw approach appears to be nothing more than a non-data-structure version of a BSP tree, where only the intersecting polygons are split. So, if your BSP code was written such that non-intersecting polygons were detected and the non-split polygons were placed into the resulting object, your results should be nearly identical (if not exactly like) the Laidlaw approach.

The Laidlaw approach does create t-junctions because polygons are split along [the arbitrary] planes of other polygons. Once the booleans are completed, I run the objects through an optimization process that removes the t-junctions and collapses polygons where it can. I didn't bother going into this, because that was part of a HUGE piece of very complex code that optimizes generic meshes into the "best set" of convex n-gons from a series of n-gons and/or tris.

A quick way to remove t-junctions is to simply slide the vertices down the the end of an edge, and collapse the polygon that lies between those vertices. If you do this continuously, you'll end up with no t-junctions. But you'll still end up with vertices in the middle of faces, so ideally, an optimization process beyond this is needed... maybe if somebody sent in an Ask MidNight question about this, I might try to explain the process. <hint hint :>

- MidNight


November 13, 2000, 04:32 PM

I didn't mean this to appear to be a realtime thing. It's meant to be done in the modelling stage. Each boolean operation (in this example, there were three) took about a half-second. I suppose with optimizations it could be done in realtime, but that wasn't my intention.

- MidNight


November 13, 2000, 09:50 PM

Ok, world of grief question :)

But is there any way to do CSG with bezier patches and what not...
In todays world of realtime 3d... an offline system such as that for level editing would have some definite plusses methinks


November 13, 2000, 10:58 PM

You got exe with that? :)


November 14, 2000, 12:00 AM

i reckon with a bit of clever coding, you can do fake realtime csg using a stencil/zbuffer technique, similar to stencil shadow volumes..

havent coded anything yet, but I think the biggest problem would be texture coordinate generation.

aside from that it's pretty simple.

downside would be you wouldn't actually be 'constructing' anything, but the plus would be all your brushes could be mobile.

I'll hopefully get an iotd of it up when exams are done... :)

thinking about it, that's be a great reason for 3d textures... (does Radeon do that, or are my wires crossed?)

anyone tried this?


November 14, 2000, 01:06 AM

Well, if you've seen the pictures of Red Faction--they seem to be doing some kind of simple realtime boolean subtraction from the world geometry. Check for the pictures.

Angel Popov

November 14, 2000, 05:19 AM

I keep a binary tree with the polygon split history, after the polygon is clipped to the BSP I perform a very fast merge using that tree (if the tree node has two children - delete the two splitted child polys and use the parent poly instead).
After the CSG is finished I do a general merge on all polygons.


November 14, 2000, 05:50 AM

That's kinda what gave me the idea...

there would be some interesting collision detection issues raised (projectiles going 'though' solid brushes, but something that I'm sure could be worked out...

the real problem I can see is when you start to want to do interesting physics things with the degenerate brushes.. since they're not truly changed, you've got to keep track of a whole bunch of crap...

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