fast intersection detection for 10s of thousands of lines?

Question

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 w$$anonymous$$ch 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 w$$anonymous$$ch 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 t$$anonymous$$s is not feasible for a real time application.

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

thanks

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.SetColors(colors);
         mesh.SetIndices(inds, MeshTopology.Lines, 0);
         mesh.RecalculateBounds();

Answer 1

Best Answer

Answer by Bunny83 · Aug 10, 2018 at 06:35 PM

There are several t$$anonymous$$ngs 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 t$$anonymous$$s case you have much more individual lines. Probably around 50k

Next t$$anonymous$$ng 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 w$$anonymous$$ch 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.

1 Show 5 · Share

rustyruss1985 · Aug 10, 2018 at 07:10 PM 0

Share

thanks for the response Bunny83. you are correct, i am drawing curves, not lines, i should have specified that better (each curve has around 50-60 points).

good to know that a mesh can now support up to 4 billion vertices, this makes my job much easier in the future, although for now i think i will leave as is.

i want to exclude/include the entire line based on intersection with the sphere. so if any part of the line is touching the sphere, the entire line will be included/excluded. i'm trying to reproduce what you see in this youtube vid at 0:25 https://www.youtube.com/watch?v=tL2AjQ4XEn4 in unity.

the points are static in the sense that they don't move relative to one another, but they can be rotated/translated as a whole by the user changing the view (see the video above).

so basically, i need a fast way to access the points in my mesh and see if they intersect a sphere, and if they do, disable any line that the point is a part of.

i have a very slow solution working at the moment where i just loop all points in all my meshes, but it doesn't really perform well past a couple hundred lines, ideally i would want this running smoothly on 10k+ lines. if you could advise me on how to achieve that, it would be great.

thanks!

Bunny83 rustyruss1985 · Aug 10, 2018 at 08:09 PM 0

Share

Ok, well, if the line segments of one fiber is short enough you could just forget about calculating an actual intersection but just check which points are inside your selection volume. There might be some edge cases where a line segment actually crosses your selection volume but both endpoints are outside. Though if the size of your selection volume is rather large compared to the length of a single line segment it shouldn't matter.

Since the points are static (at least in the video you showed) you may store all points in an octree for faster intersection testing. As for selecting the right fibers i would probably use a dictionary. As key you could use the index of a point and map it to the fiber index the point belongs to.

rustyruss1985 Bunny83 · Aug 10, 2018 at 08:48 PM 0

Share

thanks. i'm not really familiar with octrees but i'll read up on them. how exactly would you store the points in the octree for my purposes, and how would that speed up intersection testing?

also, this is a bit off topic from the octree, but once i have my curves enabled/disabled, is there a faster way to set a few points in the mesh without using a loop over all points in the mesh and then using:

     mesh.SetVertices(newVertices);
     mesh.RecalculateBounds();

thanks again

Show more comments

fast intersection detection for 10s of thousands of lines?

1 Reply

Your answer

Welcome to Unity Answers

Follow this Question

Related Questions