fast intersection detection for 10s of thousands of lines?

Hello, i have a project where i render up to 10,000+ individual lines, each made of around 50-60 points.

right now, i’m using a Mesh with MeshTopology.Lines to render my lines (i have to break up my dataset of 10,000+ lines into several different meshes, because each mesh can only hold 64,000 points).

what i want to do now is use some kind of selection object (a simple sphere for example) that the user can move about the scent, to select which lines will be rendered on the screen - i only want to show lines that intersect with the selection object (sphere).

however, i’m having trouble finding a way to detect which lines are intersecting with the selection object. obviously, i could just do a giant for loop over all my points, and set any lines whose points intersect with the sphere to 0, but this is not feasible for a real time application.

anyone know how i can quickly detect which lines (or points) in multiple meshes intersect with another game object?


ps here’s an example of one of my meshes with ~64000 points - i will have dozens of these active in the scene at any one time.

        Mesh mesh = new Mesh();
        mesh.vertices = verts;
        mesh.SetIndices(inds, MeshTopology.Lines, 0);

There are several things not clear. You said you render lines. However a line is a straight connection between two points. How can a line have 50 to 60 points? That sounds more like you draw “line strips”. In this case you have much more individual lines. Probably around 50k

Next thing is Unity’s Mesh class now supports 32 bit index buffers so you can have more than 64k vertices in a single mesh. You just have to set the index format before you assign your data.

Do you want to draw the whole line (or line strip) when any part is intersecting your sphere or do you only want to draw the line parts which are inside your sphere? In the second case you can simply use a shader where you define your sphere parameters in global parameters and simply cull your fragments based on the distance from the sphere center.

If you want to draw the whole line / line strip there’s no way around checking the intersection on the CPU. If the lines / points are static you can speed up the intersection testing by using some spatial structure (like an octree). However it depends on how those lines are distributed in space.

I’m happy to extend my answer with a more detailed solution once it’s clear what exact behaviour you want and how the lines are distributed. A screenshot would help.