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

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.

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

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;
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