Calculate 2d polyline 'perimeter' of 3d scene?

1

Given a TCastleScene with a loaded 3d model, how might one go about getting a precise 2d polyline output of the perimeter of the object (flattening Y)? I use the outline polylines to see if placing a building or road in my world intersects an existing building. I build this polyline for buildings currently from the bounds box corners, but that isn’t accurate enough to place things that are on an angle closely next to each other.

wyrd-forest_screen_169
wyrd-forest_screen_1691920×1200 217 KB

(red wireframe on the building means it failed validation because it thinks it intersects the road)

2

We don’t have a ready utility to get a 2D polyline perimeter of an object. You’d have to write it yourself.

How I would approach it:

  1. Iterate over Scene.Shapes , for each shape get the coordinates. Like

    var
  ShapeList: TShapeList;
  Shape: TShape;
  CoordField: TSFNode;
  AllSceneVertexes, ShapeVertexList: TVector3List;
begin
  AllSceneVertexes := TVector3List.Create;
  ShapeList := MyScene.Shapes.TraverseList(true);
  for Shape in ShapeList do
  begin
    CoordField :=  Shape.Geometry.CoordField;
    if CoordField is TCoordinateNode then // also effectively checks CoordField <> nil
    begin
      ShapeVertexList := TCoordinateNode(CoordField).FdPoint.Items;
      AllSceneVertexes.AddRange(ShapeVertexList);
    end;
  end;
  // ... now act on AllSceneVertexes, see below
end;

    Note that code above only gets the coordinates, not line segments. That’s enough for my next point, using convex hull.

    Alternatively, if you go with a different approach, and you need lines, you can e.g. use Triangulate to get all triangles. See the example examples\viewport_and_scenes\test_triangulate\ for a simple code. Hm, but this will give you 3 edges for all triangles, with no information which edges are shared between triangles…

    So alternatively you can use BorderEdges: for each shape get Shape.InternalShadowVolumes.BorderEdges. Though this is internal, for a different purpose (shadow volumes) and not that easy to parse. But if you really want perimiter, this is a start.

  2. Anyhow, for my approach, actually just AllSceneVertexes can be enough. Because then I can use ConvexHullIndexes defined in CastleCurves. It’s not public in that unit – just take the implementation and copy it for your purposes. It calculates a convex hull in 2D, just ignoring 1 coordinate.

  3. Finally you can make “convex hull intersection” to determine if the (projection in 2D of) your 2D buildings intersects.

    Luckily for this case there are efficient + simple algorithms, see e.g. answers in geometry - How do I determine if two convex polygons intersect? - Stack Overflow .

Note that I indeed made a simplification of the problem that you didn’t say: I assume it is enough to have “convex hulls of 2D projections of 2 objects”. If convex hull is not enough, I guess things are more complicated. You can triangulate each projected polygon using CastleTriangulate, though this gets both slower and more complicated. Looking at your screen, considering just convex hulls may be good enough.

1 Like