[Aardwolf]

Updating the first post and retitling the thread:

Thread for discussing my CSG thingy.

I also created an IRC channel on esper (same network as #hard-light), it's #aard-csg.

So I wanted to implement CSG (Constructive Solid Geometry), and I wanted it to be efficient enough to do it in real time (in a game, or at least in a level editor with tolerably un-slow results.

But it's not exactly fast enough. It took about a minute (<< a "guesstimate") just to find the edge/triangle intersections, and that was only for a 148-tri mesh and a 180-tri mesh.

That's unacceptably slow. In fact, it's so slow I can't start working on the re-triangulation code, or the part to get rid of the triangles that are on the wrong sides.

[Aardwolf]

I wrote a clustering algorithm for the triangles. It took a lot of additional infrastructure to make it possible, but now it (semi-randomly) selects regions of neighboring triangles with similar normals (maybe just using position would have been better?). Except that's still a separate system from the edge test stuff, and I still have nothing toward cutting the triangles or tossing the bad ones.

Nobody cares? Bah.

[Thaeris]

...

Aard, are you saying that you've essentially implemented booleans into a sim environment? If so, I do think that's quite interesting. Do you have any images you can show us?

[Tomo]

It can definitely be done, as Solidworks uses it and I know that runs in near real-time on my (rather old) PC.
(Definitely generates the mesh in a few seconds)

Algorithm-wise, I dunno. Too much pure mathematics for me to wrap my head around quickly.

[Aardwolf]

No Thaeris, unfortunately I'm not there yet. And I don't know for sure if I'm going to be able get it working any time soon, either... especially considering classes for the new term have just started up.

[Liberator]

For the idiots who stand in awe(like me), a clarification...

this would, if it comes to fruition, allow beam fire to bore holes and chop things into pieces without predetermination on the part of the model creator?

[Aardwolf]

Well, the same concept could hypothetically be applied to FreeSpace, yes... or any game, for that matter. To clarify, though, what I've been doing here has not been related to FS2Open (and in fact has not even been in the same programming language)

[Flipside]

I've seen a few programs that can do CSG very well indeed, but most of them are not speed-critical, Lightwave, Vue D'Esprit etc all have powerfull boolean setups, but the problems arise, from what little I can remember, when trying to do this with optimised graphics data, I seem to recall that FS2's lack of geomodding is to do, in part, with the way the models are stored, but this was mentioned several years ago, so I can't remember the details.

Vue in particular is good, because it's a real-time CSG, similar, I think, to 3DS Max, if you create a boolean with two objects, the system doesn't just subtract one from the other (or whatever the operation is) and store the results, it actually keeps the two objects that are interacting, and you can alter the boolean effect by moving/resizing the objects involved. The negative side of this is that it only works with basic shapes, i.e. Spheres, Cubes etc, whereas Lightwave can boolean anything with anything else as long as there are no points that are in precisely the same place in both sides of the operation (and with the usual problem associated with CSG operations, like problems with complex objects).

[Aardwolf]

I noticed while doing some research on the subject: some programs use the stencil buffer to do screen-space CSG. A depth buffer is all that's really needed to do a Boolean Union (although you still have lots of overdraw, and hidden/wasted geometry), and for "cut" surfaces, that's where the stencil buffer comes in.

As I haven't made much progress on my implementation, I'm not how (or if!) I will proceed now.

[Aardwolf]

A little more work (you might even call it "progress"!) and a thread bump.

I wrote a little sub-algorithm to do some pre-processing in order to figure out which parts of the meshes are nowhere near intersecting, and which are closer. I think it might not be as efficient as it could be, and it didn't cull as much as I would have hoped...

Here's what it determined "might intersect" out of a pair of 180-faced geospheres:



The way I'm doing it is I'm computing a 3d grid (for each mesh), where each point's value is the (shortest) distance to the object. I then check the other mesh's vertices against that mesh, and see how far they are. If the edge lengths of that mesh's triangles exceeds the distance, it's a "maybe intersecting" triangle. Otherwise, it's safe (not in need of intersection tests / cuts, but possibly one of the triangles that must ultimately be removed). Unfortunately, the computation of the distance is more expensive than I'd like (with a 16x16x16 grid, the whole thing takes a second or so), and the amount of culling that's getting done might not be worth it.

I'm thinking I could store additional data somewhere (specifying which triangles are near others) to speed up the process, but I'm not sure... maybe I'll just try to do the cutting/intersection tests with what I've got here, and get that working.

[portej05]

Can you give more information on how you're 1) Doing the collision and 2) Applying the collision information.
There are thousands of papers out there on this kind of thing - ACM Digital Portal is a really good place to start.

Collision and vertex level operations are some of the most difficult to do quickly and efficiently.

I think you've got yourself a fairly brute force algorithm - they're always slow unless they're optimal (d'oh!).
Maybe try something along the lines of BSPs? Precomputed, of course.

[Aardwolf]

Originally I was trying to brute-force it, but I realized that was silly and tried doing something with clustering, but I dropped that approach...

Currently I'm planning on just getting some reasonably un-slow output, and then I'll tweak the steps between the input and that. By 'tweak' I of course mean using better algorithms, not funroll-loops (lol)

Edit, rather than yet another shameless double-post:

I've redone that part of the algorithm once again... it now uses an octree (evenly split, though, rather than using some 'intelligent' splitting, and it's got a predetermined max depth of 5 IIRC) where each node contains a list of all the triangles from each object (so two lists really) (by index) whose bounding boxes (i.e. the bounding box of the triangle) intersected that cell of the octree. I also realized that the only place any intersections were going to happen was within the intersection of the two objects' bounding boxes, so I set that as the initial bounds for the octree (i.e. the root 'box' of the octree)...

With my current test case, my algorithm now correctly culls the number of triangles that must be compared from 180x180 down to 97x8... that's a 4175% improvement

Edit! Stop the presses!

Upon closer inspection, there are 97 triangles from the first object which have 1 or more triangles to test against, and 8 from the second object. But the actual number of triangle pairs to test is only 213, meaning my algorithm only has to do 1 / 152.113 as many triangle pairs as I would if I were to brute-force it!

Edit, again (since I'm editing it's not bumping the thread, I hope people notice it anyway!) :

I've got the edge intersections thing working ok now, but the re-triangulation ... not so much. I think I'll maybe go ahead and put in the part to eliminate the ones on the wrong side, anyway, and then go back and fix up the problems with the re-triangulation.

[bobbtmann]

I don't know much about this stuff, but what's the difference between this and collision detection? Are they similar to each other and could your work here be used to improve collision detection in the game?

[Aardwolf]

No, it's not really similar to collision detection, although it does require some sort of collision detection to work. It's basically trimming two intersecting polygon meshes (or in my case, they are specifically triangle meshes)... cutting them at the intersections and removing the stuff that's outside/inside/whatever.

Technically, CSG is supposed to be about the actual solid region enclosed within the polygon meshes combining, but it's not feasible to deal with the volumes... much better to find the intersections of the polygon meshes, cut them there, and toss the junk.

Also, I've run into a bit of a snag with the retriangulation... my algorithm isn't working right, and I'm thinking now that I really want it to be working right before I move on to the removing-inside/outside/whatever triangles part.

Help would be appreciated!

Edit (technically edit 2):

I've formulated (in text) my problem:

Code: [Select]

BasicModelVert struct has:
* A Vec3 position
* A Vec3 unit normal vector
* A Vec2 texture coordinate

Given...
* The three vertices of a triangle, each with position, vertex normal vector, and texture coordinates
* A list of cuts through the triangle; each cut is a line segment stored as two vertices of the same type as above

...output is a list of triangles, such that:
* The only used vertices are those from the original triangle and the cuts through it
* All of the original triangle's edges (split where intersected by the 'cuts') are present as edges
* All of the line segments of the cuts are present as edges
* There are no degenerate triangles
* The entire surface of the original triangle is covered by the output triangles
* The output triangles do not overlap

Ideally, the output also has as little "squashing" of triangles as possible

So, any ideas?

Edit, again:

I've almost got it. But now I need to solve this graph theory problem:

I've got a graph. Each node has an associated boolean value. i'm trying to find all the possible setups (i.e. i want a list of bool[n]) such that: no true node neighbors another true node, and every false node neighbors at least one true node.

Alternative phrasing of the same problem:

I've got two colors (true and false) and a rule about how they can be placed in the graph; I need an algorithm to iterate through / list all of the colorings that satisfy this rule (given the uncolored graph).

And since people've gotten confused a lot about what I'm looking for:

Input: number of nodes, and which nodes have edges between 'em. Output: a list of each and every valid array of booleans.

[Aardwolf]

Yay! It's sort of working.

But as these screenshots will illustrate, it's still a little buggy:





Note that these are screenshots picked specifically to point out the bugs. It's not always made of fail.

Also, the normals for the 'cut out' region are inverted. I'll fix that eventually too.

[Aardwolf]

Finally got it working!

Screenshots:

[Flipside]

Nicely done! I won't pretend to understand the maths involved, but congratulations nonetheless, just shows that perseverance pays off

[LordMelvin]

That's awesome. When can we expect it for beam damage and destructible stuff in in FSO? .14? .16?

[General Battuta]

That's awesome. When can we expect it for beam damage and destructible stuff in in FSO? .14? .16?

Probably never. This isn't even written in the same programming language as FSOpen and isn't built for in-game use.

Take its awesomeness on its own terms.

[Aardwolf]

Haha, probably not any time soon. It's all written in C#, and the engine is in C++/C. It would be possible to port it, but it'd be a hassle, and I hear there are some issues with how the model formats work that might make it difficult as well.

Oo, batts beat me to it.

Edit: hm... I need to do some software engineering