# Get vertices of a terrain mesh affected by a brush or placement shape

I have the following mesh, it has very simple structure. You can think of it as a terrain from top-down view: each vertex (red and numbered) is a fixed distance away from its four neighbours in the horizontal xz plane (e.g 1 unit); only y (height) is different.

How could I get the vertices affected by a given overlaid shape?

By "Affected" I mean vertices that are inside or on the border of the shape, and any vertices that share a triangle with them.

Here I've drawn a pink rectangle on my mesh, and circled in green the vertices that should be considered "affected" by that shape.

I know:

• The constant distance between vertices
• The center of the mesh as a Vector3 (mesh is a square)
• The mesh's width/height (any corner could be calculated easily)

Some context, for what?

• Flatten terrain on when building a structure, road, etc
• Edit terrain with a brush (circle and other brushes)
• Vertex/texture painting, etc
• Are the pink objects simple shapes like rectangles, circles etc, at worst a composition of such simple shapes? Commented May 31, 2021 at 13:17
• @htmlcoderexe Yes, only simple shapes.
– Sir
Commented May 31, 2021 at 13:24

This is actually a problem that GIS software can help you with. The easiest way to solve it is to just use the NetTopologySuite library instead of you implementing the algorithms that it uses. The best way to figure out how to use it is by looking at the tests.

I'm thinking it might look something like this.

var fact = new NetTopologySuite.Geometries.GeometryFactory();

var polygonSelect = fact.CreatePolygon(
new NetTopologySuite.Geometries.Coordinate[] {
new NetTopologySuite.Geometries.Coordinate(0, 0),
new NetTopologySuite.Geometries.Coordinate(0, 3),
new NetTopologySuite.Geometries.Coordinate(3, 3),
new NetTopologySuite.Geometries.Coordinate(3, 0)
});

var mpt = fact.CreateMultiPointFromCoords(
new NetTopologySuite.Geometries.Coordinate[] {
new NetTopologySuite.Geometries.Coordinate(1, 1),
new NetTopologySuite.Geometries.Coordinate(2, 2),
});

var pointCollectionSelected = mpt.Intersection(polygonSelect);


This answer assumes simple shapes as per OP's comment, as well as the terrain being broken up into smaller, manageable chunks (you should probably be doing this anyway).

First of all, treat the whole thing as 2D for the purpose of these calculations.

Then implement a common Shape or similar class (perhaps better an interface) that has a function that takes some points and returns a list of points the Shape contains. The exact struct/class of the points doesn't matter and probably depends on the framework/engine you're using if any.

Circles are straightforward, just check every point in your terrain chunk against the centre of the circle - anything with smaller distance than its radius is inside.

Rectangles are easy if aligned to the coordinate grid - but if you want arbitrary rotation, it is not hard. If you know your rectangle's centre and its rotation, you can rotate the rectangle and the points the opposite way, then use the axis aligned algoritm - any point that has its X coord more than rectangle's origin X and less than rectangle's origin X + width, same for its Y (Z) coord. In your case you are probably using X-Z as the "flat" directions and Y as the "ignored" height, so keep that in mind.

Any other stuff, probably the same, just rotate to axis align and calculate from that.

You'll probably be returning indices anyway, so not really needed to "unrotate" stuff after you're done with it as you're working on a copy of the vertex data anyway.

It might even be simpler to never touch the vertex data at all and use some "fixed" constant grid that you just copy and rotate to axis align, calculate indices and then dispose the copy at the end.

Your function then would look something like this in pseudocode:

for (x, y)
generate point P for index x,y
rotate by inverse of Shape's rotation if needed
check if  it's inside the inverse rotated Shape
add to list of indices if true


Once you have found the vertices that the Shape contains, you can also add any vertices that share a triangle with it by simply checking for each vertex as this is pretty fixed for such a grid.