I need to find positions of all corners of a Part, Model, Union (CSG) or Mesh object of any shape. The shape may be either convex or concave, and have either orthogonal or diagonal slopes of any angle.
My current take is like this:
raycast in 8 directions from a selection of points located on a regular grid with a given step
find intersections with the part’s surfaces, get their normals and determine the surfaces
project surfaces onto a plane and find intersections of all the found lines
determine only those intersection points which are inside the object
calculate convex hull on those points; the points of a hull are the corners of the object
Notice there is an additional step required for treating the concave areas of the object, which most likely involves tracking a list of surface normals.
Is this algo feasible? What are the other possible solutions? Perhaps some sort of a pattern matching.
For what end result are you searching for an algorithm like this? The basic outline of your algorithm is feasible and could be used to identify vertices in some cases, however the degree of accuracy and confidence that all vertices have been found is limited by the step size of the 2D/3D raycast grid.
Mathematically speaking, it should be possible to calculate all vertices without the use of raycasting guesswork for all your inputs except PartOperation.
spoken about mathematics, whilst the question involves specific engine, namely roblox
i do understand there is no problem getting vertices when your object contains complete geometrical definition
do you know of any possible ways of getting at least surface coordinates from the roblox engine?
My question on your use case was an attempt to first of all see if the approach is even appropriate (or if I could provide an alternative). As I spoke of in my previous post, it is possible to calculate vertices for all your listed inputs except PartOperation (aka Unions, CSG).
I would highly recommend sharing more about your use case as there are other unknowns from your original post, such as how to handle overlapping parts (are interior vertices relevant), and whether you’re trying to find vertices in 3D or just on some 2D plane. Here’s a general overview of computing vertices in 3D on singular BasePart instances:
For Part (Shape = Enum.PartType.Block), you can compute the vertex corners with a basic understanding of CFrame/Vector operations. For example:
local backTopRight = part.CFrame * (0.5 * part.Size * Vector3.new(1, 1, 1)) --Change the signs of the X, Y, Z components of the last Vector3 for other corners
For Part (Shape other than Enum.PartType.Block), you would have to know the underlying geometry of each shape - the geometry is consistent regardless of the Size of the Part. Not impossible to backwards engineer, however, there is no official API to get this geometry.
For MeshPart, load the MeshContent into an EditableMesh and use the method GetVertices and GetPosition. You will need to convert these coordinates from the local mesh space if you need them in world space or some other frame of reference.
my use case aims at using surfaces of the given object as templates for walls
interior vertices are irrelevant and should be ignored
2d plane is sufficient for my usecase
getting vertices from primitive Parts is possible, but very cumbersome when rotation angles are involved, and besides, PartOperation is the number one priority here - therefore i do not want to use that approach cause it does not cover all cases
Ok, possibly starting to get an idea of what you’re looking for. If you’re still looking for further assistance, I’ll need clarification on what exactly this means:
using surfaces of the given object as templates for walls
My understanding right now is that you’re trying to essentially generate a bounding polygon, and as you mentioned, specifically around a PartOperation. Is this correct?
Alright cool. And what is your intended use of this bounding polygon? You mentioned only being concerned with a 2D plane. Depending on what you’re trying to do with it, the approach could change drastically. Also, circling back to the accuracy aspect, how concerned are you about getting every vertex: What about holes within a PartOperation? What about vertices that are extremely close (ex. <0.01 studs apart)?
holes in geometry may be either ignored altogether or filled with simple scripts on the post-processing stage
extremely closed vertices should be merged together; the minimum gap size is somewhere around 0.25 studs
after you have found your walls and their intersections, the main problem is to traverse by these corners in order; additionally, there is a problem arising when you begin working with this: CSGs in Roblox have inner walls inside them (traces of triangulation used internally, which are also counted as legitimate targets for any raycasting you’ve done; therefore, you have to filter them somehow; NOTICE: use PreciseConvexDecomposition mode for collision, otherwise you will get inaccurate results)
3 algos tried:
raycasting between points; failed
too many permutations even for vectorized version; final correct order is unguaranteed
concave-hull; failed; can’t get order of found points and triangles
but the algo fails at traversing narrow areas anyway (you have to specify maximum width of corridors beforehand, therefore trading either long or narrow ones between each other, can’t have both at the same time)
wall-walking; succeeded
you go by the wall, raycasting in many directions and filtering invalid candidates; those found points which have turn angles larger than given threshold are tagged as ‘corners’
some stages of development and the final result of working algo may be seen on screenshots; various shortcuts and optimizations used, such as removing duplicates cumulatively, optimized initial grid and so on
further improvements: dynamic grid stepsize; robust stop condition; fallback subroutines for when the algo fails (usually in very tight areas)
