Author Topic: Realtime CSG... almost there!  (Read 9567 times)

0 Members and 1 Guest are viewing this topic.

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Realtime CSG... almost there!
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.





Quote from: the first post prior to editing
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.

:(
« Last Edit: April 30, 2010, 01:01:10 pm by Aardwolf »

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: Realtime CSG... how about no
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.

 

Offline Thaeris

  • Can take his lumps
  • 211
  • Away in Limbo
Re: Realtime CSG... how about no
...

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?
"trolls are clearly social rejects and therefore should be isolated from society, or perhaps impaled."

-Nuke


"The Windows Operating System: It can only get worse from here!"

-Me



"Look on the bright side, how many release dates have been given for Doomsday, and it still isn't out yet.

It's the Duke Nukem Forever of prophecies..."


"Jesus saves.

Everyone else takes normal damage.
"

-Flipside

"pirating software is a lesser evil than stealing but its still evil. but since i pride myself for being evil, almost anything is fair game."


"i never understood why women get the creeps so ****ing easily. i mean most serial killers act perfectly normal, until they kill you."


-Nuke

 

Offline Tomo

  • 28
Re: Realtime CSG... how about no
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.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: Realtime CSG... how about no
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.

 

Offline Liberator

  • Poe's Law In Action
  • 210
Re: Realtime CSG... how about no
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?
So as through a glass, and darkly
The age long strife I see
Where I fought in many guises,
Many names, but always me.

There are only 10 types of people in the world , those that understand binary and those that don't.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: Realtime CSG... how about no
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)

 

Offline Flipside

  • əp!sd!l£
  • 212
Re: Realtime CSG... how about no
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).
« Last Edit: April 07, 2010, 12:03:40 am by Flipside »

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: Realtime CSG... how about no
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.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: Realtime CSG... how about no
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.

 
Re: Realtime CSG... how about no
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.
STRONGTEA. Why can't the x86 be sane?

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: Realtime CSG... how about no
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 :D

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.

« Last Edit: April 12, 2010, 02:29:17 pm by Aardwolf »

 
Re: Realtime CSG... how about no
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?

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: Realtime CSG... how about no
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.
« Last Edit: April 17, 2010, 12:41:49 am by Aardwolf »

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: Realtime CSG... how about no
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.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: Realtime CSG... how about no
Finally got it working!

Screenshots:






 

Offline Flipside

  • əp!sd!l£
  • 212
Re: Realtime CSG... how about no
Nicely done! I won't pretend to understand the maths involved, but congratulations nonetheless, just shows that perseverance pays off ;)

 

Offline LordMelvin

  • emacs ftw
  • 28
  • VI OR DEATH! DOWN WITH EMACS!
Re: Realtime CSG... how about no
That's awesome. When can we expect it for beam damage and destructible stuff in in FSO? .14? .16?
Error: ls.rnd.sig.txt not found

 

Offline General Battuta

  • Poe's Law In Action
  • 214
  • i wonder when my postcount will exceed my iq
Re: Realtime CSG... how about no
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.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: Realtime CSG... how about no
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  :blah:
« Last Edit: April 24, 2010, 07:11:10 pm by Aardwolf »