Using Constructive Solid Geometry (CSG) to build a TIndexedFaceSetNode

[DSK]

Hello,

In short: How could / should I access the triangulation of a TAbstractGeometryNode?

I’m in the early stages of planning my (as much as possible) cross platform game, and getting used to Lazarus having come from older versions of Delphi. I do have a background in real time machinery control systems, and not games programming. But I believe much of my experience will be applicable / transferable. I’m developing in Windows 10, using the latest version of Lazarus. I have started exploring Castle Game Engine (about a week ago), compiled the Castle_Base package, and run a few demo programs.

I have looked at the Castle editor which looks all good, and I have used it to view demo’s, but I don’t think it will be applicable for the game I have in mind as this will not be based on imported assets and level designs etc.

I must say that what I have seen so far with the development of the engine - this is an awesome project! The code is easy to read and very well documented throughout everything that I have seen so far.

Here is some background on what I want to do:

In what I plan to develop for my game, I want the player to be able to edit / modify the world by using simplified 3D editing tools built into the game. The world will be an underground environment and will store the data in a simple axis aligned cubic grid, with the cells representing 10 metre spatial divisions. The cells will connect to each other where their contents allow a route through free space. In a way this is a simplified version of the old portal rendering systems, but is not portal rendering per se.

From what I have seen so far in the engine, each of my world “cells” would encapsulate a (at least one) TCastleScene object (except if the cell represents empty space). Where cells connect, any contained graphics that straddles the boundary will be contained in two separate TCastleScene objects, but will coincide at the boundary seamlessly. The “cells” in the world can go in and out of scope depending on whether they have a chance of being visible or not. This is just a very simple scheme not based on exact visibility, but simple criteria like distance from the viewpoint etc. Cells that go out of scope will have their TCastleScene removed from the viewport but will not necessarily be freed if memory is not an issue. This would allow in memory TCasleScene’s to be re-added to the viewport quickly if the cell comes back into scope. Where cells come into scope that are not currently in memory then these would need to be loaded from files on the local computer. This might result in needing to free some least recently used cells so that memory and graphics resources are released.

Each cell will have a hash code. This code can be checked against a corresponding code from a server to see if the local copy is dirty, and if so re-load a new cell from the server. When a player modifies the graphics in a cell that they “own”, then when they commit the changes these will be up-loaded to the server. The server will then inform any other players which have that cell in their scope so they can download the changes. All of which will happen transparently.

My understanding is that the TCastleScene root node contains an X3D node graph representing the actual geometry and materials etc.

Now for my actual question :

I want the player to be able to edit the “world”. One of the editing abilities I want is to be able to perform something similar to CSG operations. Say for example the player want to make a tunnel through a solid piece of “ground”,. They would draw a 2D section cut of the tunnel and then extrude this through the ground. Behind the scenes the system will need to “subtract” the tunnel from the ground graphics. This will require finding the intersection of those graphics and deleting everything that would have appeared inside the tunnel.

For this I imagine a method call that takes as parameters a pair of TAbstractGeometryNodes and returns a TIndexedFaceSetNode
which is the result of subtracting the first parameter from the second parameter. This would involve something like intersecting all of the triangles in the two sets of geometry to produce new vertices and edges at the intersect. New faces will need to be generated , and vertices and edges inside the tunnel deleted.

I already know how to intersect pairs of arbitrary triangles in 3D space and compute the line segment intersect in terms of the maths. But what I don’t know is how to access a list of triangles from a TAbstractGeometryNode. I have seen methods that are to do with how an X3D node is triangulated for internal use, and that “OverTriangulation” can be used in order to produce better shading.

But how can I access the triangulation which is already performed by the engine? It would seem better to do this than to re-triangulate myself…

[michalis]

Thank you very much for the good words!

What you describe makes sense, although I would say:

• Still use the editor. To design user interface, setup basic stuff like viewport, cameras, test 3D models etc. Even if you will construct most of your 3D levels by code, I’m sure there will still be a lot of things that are just easier to design visually using the editor.

  Also, you can construct designs in .castle-transform files that can group a number of TCastleScene, TCastleTransform etc. together. It may be a useful thing to you to define “cells”. See how examples/advanced_editor demo uses it to define soldier_with_cape.castle-transform – which is a reusable design that combines 2 glTF models. You can make such designs in the editor.

• There are some involved things in your description of the mechanics – downloading, uploading modified cells, CSG, potentially infinite world loaded on-demand. From your description, you do seem to know your way around, so you are probably very well capable of executing this — still I would advise that this should not be your first game done using Castle Game Engine.

  Start with something simpler, e.g. explore a 3D world build from the cells you have in mind (but with cells set up using the editor, or simple code that doesn’t need to download them). I would definitely start with a simpler project, so that you will get familar with CGE in a simpler scenario. And once you’re happy with what you can achieve, then jump into bigger project, with network, editing, uploading, CSG, loading on-demand etc.

  I’m honestly saying this from experience People new to the engine often come with an idea to make a game based around infinite 3D world – but this is just a very difficult task to pull off (in CGE or any other game engine), and in the end nobody really achieved it. Your approach (cells loaded on demand) sounds good, but still I very advise to first try using CGE in a simpler setting.

To access the triangulation result: The answer depends a bit on how general you need your solution to be, which is – do you want to handle absolutely all geometries or not.

• If you want to design your cells in Blender and export to glTF ( Exporting from Blender | Creating Game Data | Castle Game Engine ), then the majority of your geometry will be an TIndexedTriangleSetNode, not a more general TAbstractGeometryNode. If it is possible to limit yourself to this – then you have a simpler job, and TIndexedTriangleSetNode is a simple triangle set that is already triangulated.

• If such limit is not possible, then you can load the model to TCastleScene, and iterate over Scene.Shapes and call Triangulate for each TShape. The TShape is a CGE class representing a particular instance of a geometry, at given transformation in the world, with given X3D TShapeNode.

  An example of using it to triangulate any model is in examples/3d_rendering_processing/triangulate_demo.lpr.

  So in this case, you would triangulate each shape to a list of triangles (e.g. you can store them on TTriangle3List). And the things like materials, textures etc. are defined in the relevant TShape instance.

• Finally, to go even deeper and have maximum possible efficiency, you can access GeometryArrays at each TShape. The CastleInternalGeometryArrays unit defines the TGeometryArrays type – it’s a class with information close to what we eventually send to the GPU to render given mesh. You could extract from it back the mesh, with indexes, with whatever primitive (triangle, line, quad) was most suitable.

As for OverTriangulate – I would not care about it much. It’s a technique that increases generated mesh density for some primitives like Box, Cone, Cylinder. It doesn’t affect “explicit” meshes provided as a set of triangles or polygons. And the better shading matters only for Gouraud shading. In most cases, you’ll be fine using OverTriangulate = false always.

[DSK]

Thank you, Michalis

Your comments on starting with something simpler are much appreciated - I understand very well where you are coming from. I do realise that I am apparently just the latest in a very long line of developers with somewhat unrealistic dreams - and that is something I do need to keep in check, but at the same time not get defeated by other peoples viewpoints.

I would run the project more or less in the way you describe anyway. I do not plan to start this as a project with an immediate end goal of producing an MMORPG. I just plan to start it and continue in a way that does not defeat that as an end goal. My initial testable systems wouldn’t even have networking built in - as you suggest, just testing and refining the “cells” system first, for example, but keeping in mind that it will be networked from the beginning. So, e.g. trying to develop game mechanics from the beginning that make it scalable and as immune as possible to network latency and unreliability etc.

Actually, I’m not even intending to create a “finished” game. The idea is more that it would be a sandbox environment which integrates everything in one so that “players” can unleash their creativity, and effectively create their own games within the “game” in one seamless world. It will use intuitive / easy to use 3D editing integrated in (much like how Sketchup is easy to use, but less featured than that), and my own “Pascal like” server side scripting language to create active content.

I’m thinking of what I write as more of a “bootstrap” process which eventually results in a game. When this reaches a useable initial level I will recruit as many close friends as possible to “play” it, producing the first content. At the same time refining the system in response, simulating as much load on the system as possible to test the scalability, and basically letting it grow before releasing it properly into the wild.

---

Thank you for your advice on using the editor and I will look more deeply into that. As you say, there will be user interface elements on top of this which may be applicable here. I will also look into .castle-transform files as a basis for serialising and storage of the cells which sounds like a good idea.

From your options on accessing the triangulation, the CastleInternalGeometryArrays unit immediately sounds attractive and I will look into that first.

Please do, if you would, continue with any observations / criticisms etc of what I say. It will all help to remain in the real world and avoid pitfalls going forward.

Thank you very much, Michalis

[DSK]

Ok, so I’m thinking that TCastleScenes’s can be triangulated along the lines of this. This iterates over a TCastleScene for OperandA which produces TShapes. The TShapes are iterated over which produces triangles. OperandB then needs to be searched for triangles that have a chance of intersecting a given triangle:

  procedure TCSGOperations.PerOpATriangleCallback(Shape: TObject;
                                            const Position : TTriangle3;
                                            const Normal : TTriangle3;
                                            const TexCoord : TTriangle4;
                                            const Face : TFaceIndex);

  var OpBPossibleIntersects : { A list of triangles from the OperandB scene }
  begin
    { Process a single triangle from FOperandA }

    { Find a subset of the triangles from the OperandB scene, possibly using its
      acceleration structure (is an octree available?), by searching on the position
      of this triangle from OperandA. }

    { Perform precise intersection tests of this triangle from OperandA with the triangles
      found from OperandB. For triangles that intersect produce line segments at the intersect. }

    { Add the intersection segments to an "intersection path". It is not guarranteed that the segments
      will arive in any particular order, or whether they will connect together. The "intersection path"
      should contain functionality to order the segments to form continuity. It should also store with
      each segment exactly which triangles it intersects. }

  end;

  procedure TCSGOperations.PerOpAShapeCallBack(const Shape : TShape);
  begin
    { Process a single shape }
    Shape.Triangulate(false, PerOpATriangleCallback);
  end;

  function TCSGOperations.SubtractScene(SubScene, FromScene : TCastleScene): TCastleScene;
  begin
    FOperandA := SubScene;
    FOperandB := FromScene;
    FOperandA.Shapes.Traverse(PerOpAShapeCallback, false);

    { At this point an "intersection path" will have been populated with line
      segments everywhere that the triangles from OperandA intersect the triangles
      from OperandB. }

    FResultScene := TCastleScene.Create(FromScene.Owner);

    { Populate the result scene with triangles from the two operands depending
      on the CSG operation (in this case, subtraction). This will involve checking
      if triangles from OperandA fall inside the solid parts of OperandB or not.

      Where triangles have intersections, they will need to be truncated, each
      creating a quad and a triangle. What to do with these will depend on the
      specific CSG operation. }

    result := FResultScene;
  end;

Does that make sense?

If this is along the right lines in the engine, then there are a couple more facilities needed from the engine:

1. To efficiently find triangles that are at least near a search triangle.
2. To efficiently determine whether a triangle is inside a solid region, or straddling the boundary (= near a triangle), or fully outside.

[michalis]

Yeah, the outline of the algorithm makes sense.

I would pay special attention to the statement you made:

Where triangles have intersections, they will need to be truncated, each creating a quad and a triangle.

In general, difficult cases may happen, as one triangle may cut the other triangle only partially. You have 3 cases:

1. Triangle A is cut completely into triangle + quad:

2. Triangle A is cut, but the cut doesn’t go all the way:

3. Triangle A is cut, but the cut is inside:

Case 3 is just like case 1, but with different order of operands.

In all cases, splitting triangle A into new triangle (NewAT) + new quad (NewAQ) makes sense as a first step… But in case of 2 and 3, this is not yet the end of wok – you will have to connect the cut with more incoming cuts. You can detect them as “more triangles from scene B cut triangle A”, but applying them creates more interesting shapes, and assumption “triangle A is split into NewAT + NewAQ” seems to fail. If you need a general CSG solution, you need to account that the “cuts” draw any polygonal chain (connected line segments) on the surface of A. That is, imagine you have:

(I hope 2D screens from Blender illustrates what I’m thinking about in 3D )

So you need to

• collect all “incoming cuts” for each triangle from A,
• then connect these incoming cuts into a polygonal chain APoly at each triangle (if they cannot be connected, it means that B is not properly closed volume → so a typical CSG algorithm would answer “this is not possible”)
• and then run triangulation of 2 possibly non-convex shapes, created by the APoly, and the corners of A. You can use our low-level triangulation routines from CastleTriangulate. One of these non-convex shapes is “inside B”, one is “outside B” – depending on the operation (difference/union/intersection), you will want to discard one of them.

To make things more complicated, you will want to track the same thing at B.

Depending on the details, starting iteration from A or B may be more efficient. Once you have the algorithm correct, I would look into that. In case of a symmetric operation like union or intersection, it may be beneficial to swap the operands, to easily gain speed.

So, these are my thoughts

Disclaimer: I have never implemented a general CSG mesh<->mesh operation myself (in CGE or otherwise). So these thoughts are just “what I would watch for, how I would approach this if I would implement this myself”. But I did not research how others do CSG, and whether my above description corresponds to what others are doing. It is possible I overlooked some critical problem or critical solution in this

I see you made separate forum threads about the 2 questions at the end (that is indeed helpful, thank you) so I’ll answer there.

[DSK]

Hi, Michalis,

I am sorry - I had got shifted to “other” responsibilities last year and this all ended up very much on the back burner. Hope you can understand that things in general haven’t been normal in recent times.

I very much appreciate your detailed explanation above and the time it must have taken you.

I am now getting back to this, and I do have other questions for you as well.

kind regards

David.

[michalis]

No worries, hello back