Given two points (vector3s relative to the origin) A and B and another point C (not necessarily colinear), how do you find point D such that it is on line segment AB, is as close to A as possible, and has no obstructions between itself and point C as defined by GetLargestCutoffDistance with a custom ignore descendants list?
You can assume that there is at least one interval of points on line segment AB in which there is no obstruction to C and therefore, there is always a solution
I don’t understand. GetLargestCutoffDistance operates on CFrames, and you are talking about points and line segments.
If I understand correctly, then we have a setup like this:
In that case I’d find all the objects that could be blocking C’s view of the line. (Alternatively you could grab just geometry that could be blocking C’s view of the line between A and the midpoint of AB, or some other point close to A and progressively grab more until you find an open spot.) There are many ways to do this. If I weren’t in Roblox with the workspace’s method to find all the parts in a region 3, I’d use some form of spatial graph (I have a modified Octree to hold AABBs on my GitHub) to find all the geometry close to the operation, then a GJK implementation (here is mine) to make sure that all the geometry from the spatial graph intersects with the triangle formed by ABC. (You could extend this problem into 3D easily with a pyramid too.)
Next I’d define theta as the angle from the ray centered at C to A, increasing as a ray from C to any given point P on AB moves toward B. I’d then find the points on each geometry which have the minimum and maximum theta. I’d store these points in an ordered queue (I sadly deleted my binary heap implementation and I think I Fibonacci heap implementation is broken right now, but you should be able to find/create one yourself). Finally, I’d run through the queue poping off the start point and endpoints of the sections of the line covered by different geometry. When a minimum theta for a geometry is encountered, I increment a counter representing how many geometries are blocking c’s view in the given region. When I reach a maximum theta for a given geometry, I decrement the counter. When it reaches 0, then I find the intersection of the line CD where D is the point I just poped off the queue and the line AB. This point of intersection, R, is the point on AB visible to C closest to A. Most of this is a linear operation, excluding the queue that you use to store the minimum and maximum theta points. Your efficiency is based on the structures that you choose to use to implement it.
Now You will have to be careful to include all geometries that have a minimum or maximum theta between 0 and CB. If the minimum or maximum theta of a geometry are in range, clamp the other value to [-1, theta of CB + 1]. If you encounter a geometry that has a minimum theta less than 0 and a maximum theta greater than that of CB, then no point on AB is visible from C. If when going through the queue the first value is greater than or equal to 0, then A is directly visible from C. If the last item of the queue is past B and no result has been found, then there is no visible portion of the segment AB from C. Finally, note that if this is being done in 3D, then you will have to take a cross section of any 3D geometry intersecting with triangle ABC.
@suremark the points are vector3s and the end camera cframe will be ‘cf(D,B)’
@IdiomicLanguage that’s an awesome solution, should I be worried about meshes and csg not generalizing well to primitive shapes though? (Particularly when I need to add the start and end points of each geometry cross section into the queue)
Btw instead of using a priority queue I could just use an array and sort it at the end so that speeds it up by some constant factors xd
Depends on what it is used for. If you have a mesh and know the points of it and just need to do a visual check, then you will be fine. If you need to do a collision check, then you’d need the crosssectio. Of the collision mesh… Which I don’t know how to get. XD
I like your solution, but the amount of implementation specifics in the explanation may be confusing for some. I would explain the solution at a high level first like this:
All of the data structure stuff is just implementation detail for how you handle and optimize step 2, the merging of overlapping coverage intervals.
