Testing Ray and Triangle Intersections Efficiently -- Memory Data Structures

Vote count:

0

I have a large collection of "Rays" and "Lines" in 2D, integer space. Given this set, I want to store it in memory in such a way that the latency of the following methods/queries is minimal. I'm looking for a language independent data structure which most efficiently satisfies the following conditions, and why it's a good choice.

Definitions:

• Point -- A point is represented by a (X,Y) pair. These are Int64s


• Ray -- A pair of Points. Of these Points, one is "Start" and the other is "End"


• Triangle -- A set of Three Points, or could also be defined by three Rays, which form the simplest geometric shape

Operations

• IsPointInTriangle(Point) -- Return True/False if a given point is inside of ANY stored triangle


• IsPointOnRay(Point) -- Return True/False is a given point lies on a Ray


• DoesRayCrossOtherRays(Ray) -- Return True/False if a given ray would cross ANY other Rays


• GetPotentialTriangles(Ray) -- Returns a set of potential Triangles if this Ray was added to the set that would be created. That is return an array of 3 Points/Rays making up zero+ triangles.

Goals and Assumptions:

• Operations and data reside in memory. Storage cost is a non-issue


• Operations need not be thread safe. Each operation will take place sequentially


• No point will be stored which lies in an existing Triangle


• No point will be stored which lies on an existing Ray


• No Ray will be stored which crosses an existing Ray


• Reduction in latency for each calculation is the ultimate goal. All other concerns are secondary.

asked 2 mins ago

Oliver Kane

324

Testing Ray and Triangle Intersections Efficiently -- Memory Data Structures