How to get every face of a mesh that intersects with a given collider

Help
1

Godot Version

4.5

Question

image
image1019×804 183 KB

I have a collider shaped like the one in the image (it is actually a proper sphere shape collider but I’m using this mesh because the sphere shape is hard to see on screen), and I’m trying to get every face of every collider that intersects with it. The idea is to use this information to make a locomotion system, which is going to need more than just the information about the ground directly in front of it.

Once I have the mesh faces I will cull them with various different criteria depending on the use-case (walking, climbing, jumping, wall-running, tight-squeezes, etc), but to do that I need a list of faces.

So is there a good way to do this, or a library or addon that can achieve it? I assume it will look something like populating a list of colliders, getting their triangles, then testing them against the volume? This will only be using collider meshes and shapes, so it shouldn’t be too many features to track I wouldn’t think, especially if I’m only doing it for the player controller. I also don’t know if there’s some part of the physics API that I can use to achieve this, since I assume it’s already checking this information somewhere, is it actually creating a list of all collisions between shapes, or does it just stop at the first collision and call it a day?

“No, don’t do that; you’re doing it wrong; do this other thing instead”

A quick aside to pre-empt anybody who wants to say, “No, don’t do that; you’re doing it wrong; do this other thing instead”: I have considered my options, I have considered using a bunch of raycasts, or a capsule collider which already exists, and this is the system I want to try. Maybe it won’t work, but none of us will know that it won’t work until I try it, and to try it, I want to have this information, so thank you for your concern but I won’t be disuaded from this foolish course of action.

2

Define “intersects”.

3

If the face of the mesh and the sphere occupy a common region of space then they are intersecting.

EDIT: If any part of the face of the mesh is inside the sphere, they are intersecting.

I’m sorry, I really didn’t expect that to be ambiguous in any way so if it is I’d like to understand how.

4

Technically, not necessarily. It depends on the type of the collider you use. For concave colliders only actual triangle/triangle intersection is registered. On the other hand, convex colliders may “know” if something is inside their convex hull. So the shape of the collider matters. Is it always a sphere or can be anything? The former simplifies the problem the latter complicates is. What kind of colliders are expected to enter it. Can they be concave or can you do only with convex or even just parametric ones? Etc…

If you want a viable solution you’ll have to describe your use case in more details. The problem, not your imagined solution. Otherwise we’ll likely be entering the xy problem zone.

People telling you you’re doing it wrong - might be right :smile:

5

Thank you so much for that link about the XY problem. Reading it I can see that the advice is:

What to do about it?

  • Always include information about a broader picture along with any attempted solution.

The idea is to use this information to make a locomotion system, which is going to need more than just the information about the ground directly in front of it.

  • If someone asks for more information, do provide details.

If any part of the face of the mesh is inside the sphere, they are intersecting.

  • If there are other solutions you’ve already ruled out, share why you’ve ruled them out. This gives more information about your requirements.

I have considered my options, I have considered using a bunch of raycasts, or a capsule collider which already exists, and this is the system I want to try. Maybe it won’t work, but none of us will know that it won’t work until I try it, and to try it, I want to have this information, so thank you for your concern but I won’t be disuaded from this foolish course of action.

It looks like I’ve already followed all of their advice before you gave me that link, so can you please explain why you’re directing me to that page?

6

No, you described your attempted solution, not the problem. Describe what are you trying to make. How is that locomotion system supposed to look and function from the player/user perspective. Don’t use abstractions and technicalities that belong into solution domain.

Technically, the answer to your question is simple:

  • Register every collider that entered/exited the spherical area.
  • As long as the collider is inside, every time it or sphere moves, iterate through its faces and do a triangle/sphere check to determine which of its faces are inside sphere.

There are probably better solutions to your actual problem but it’s hard to suggest them because we don’t know your actual problem. You only provided your reduction of the problem to some half-solution that doesn’t work or would be inneficient. It’s a textbook example of an XYproblem situation.

3 Likes
7

It might be good to examine why this is so important to you. You pre-emptively said “I know this is going to be viewed as the X-Y problem, but ignore that.”

Ok.

Make it a RigidBody3D and use the body_entered signal.

I know you think you provided everything we’d need to help, but there is a lot of information that would make the difference between getting an unhelpful answer and a specific one that solves your problem.

  • What kind of node is this CollisionShape3D attached to? (Different nodes handle collisions differently.)
  • Is this sphere the player? A vehicle? An Indiana Jones style rolling boulder trap?
  • What kinds of things is it intersecting? Convex or concave polygons? What node types is it colliding with?
  • Does your game have gravity? No gravity? Does it have multiple gravities? (Ground collisions cannot be detected without gravity pushing the object down every frame.)
  • What is the Up Direction set to?
8

Okay, I appreciate that you’re both trying to help, but I feel like there’s a basic misunderstanding here.

I am asking Question Q: “how do I conduct this test to see if this idea is going to work?” And, more broadly, “what can I learn from the attempt?”

You are attempting to answer the question behind the question, or Question P: “how do I make this locomotion system work?”

I am already pursuing other alternatives and if they are good enough then they will be good enough. They kind of work, they’re a bit hacky as most game dev is. They’re fine. If I have to use them then I can use them. I’ve already got a pretty interesting prototype that I’d love to share soon, but I really don’t need help with Question P which is why I didn’t ask for it and why I’m resistant to offering a bunch of details that will only distract towards solving a problem that I don’t have.

I’m not married to this one solution, I am just trying to learn something about how to do it. Maybe it will help with Question P, maybe it won’t, maybe it will give me the tools or inspiration to do something else interesting down the line.

I’m sure this looks like the X-Y problem to you, it certainly has a similar structure, but Question Q fundamentally cannot be answered by addressing Question P, because it doesn’t matter how good my locomotion system is, my understanding of how to parse the mesh will have gone nowhere. My purpose here is not purely instrumental, but learning. I really tried to head this issue off with my disclaimer but it seems to have struck the wrong chord.

And I will accept that only the other day I did have an X-Y Problem where I was asking about one solution but Normalized gave me the easier answer which I had discounted because I had trouble with it at first. That was very helpful, but that was a situation where my goals were instrumental, and the answer was simple. This is not such an occasion.

I hope you can understand this, but if not then I guess we won’t be able to do any more here, and I’ll just come back to the thread if and when I find something good. Either way I appreciate you trying to help.

For now I have found this, which I can work with, but I hope there is a better way: Get Face of Colliding Mesh - #2 by system

EDIT: Actually that’s just giving the face from a vector, which is the same as RayCast3D.GetCollisionFaceIndex. That’s useful, but requires a lot of guess about where faces might be, which is something I’m trying to avoid.

9

Your question was “How to get every face of a mesh that intersects with a given collider”, yet we later find out that you actually want faces that are inside a sphere. Do you want faces that “intersect a with given collider” or faces that are contained (fully or partially) within the volume of a sphere? Just this moment is totally XY, not even going into the real problem this is supposed to solve. Especially since “intersection” means different things for different kinds of colliders in Godot, as I already noted above. Generalized concave colliders don’t represent volumes, they are just triangle soups that can’t “contain” anything.

So, is the question about triangles of an arbitrary mesh inside a sphere, then? Or something else?

10

Based on the information given, I answered your question.

You can use that to trigger a check of all the collisions in your mesh. Alternately, you can do it in physics_process().

There are functions in RigidBody3D to detect number of collisions, and the position for each collision.

A long diatribe telling us why you do not need to answer the questions we are asking (to try and help you) does not get you a better answer. It gets you the same answer.

If you don’t like the answer, I recommend you respond specifically why the answer I gave you yesterday does not work for you, or how you do not understand it.

11

EDIT: This is not an LLM answer. Ask me about it and I can explain with my human brain.

The simple answer appears to be: there is no existing function available in Godot that will do this job, and if it is necessary then you will need to roll your own solution, which is a pretty big job.

The longer answer is:

There are functions in Jolt that will do it but they are not currently exposed via the Godot plugin: Is there a way to access the result of CollideSphereVsTriangles from Godot? · jrouwe/JoltPhysics · Discussion #1955 · GitHub

However there is probably a more efficient way. To get access to a mesh face in Godot, once you have a collision location and normal, you can use a very short RayCast3D against the normal direction and then use GetCollisionFaceIndex(): RayCast3D — Godot Engine (stable) documentation in English

If there’s another more efficient way to get a mesh face at a given location, I haven’t found it.

From there, to access the rest of the mesh via the adjacent faces, the most efficient method appears to be to use a half-edge mesh data structure: Half-edge data structure

This would require you to implement this data structure and then pre-cache it for each unique mesh in the game, and it would allow you to walk across the mesh and find every face that is within a sphere or any other collider shape that you can define either through the physics engine or just in your own code. You can also define any arbitrary set of tests that are needed, so this can do a lot more than just intersection tests.

The efficiency of this method depends on whatever the test is, but accessing the adjacent faces can be done in constant time, so that part is very fast.

This won’t necessarily get you every face that intersects with a collider, but it will get you every face that is contiguous with any detected collision. To get every single intersecting mesh face would require a full check of the mesh but that would be relatively slow and probably best done by extending the physics engine plugin, which would be a lot of work.

You can’t use this method to do collision detection from first principles; the built in methods are used for that; this is a step that can only occur after collisions have already been detected via whatever method has been chosen.

12

LLM hallucination alert! :rofl:

1 Like
13

I literally gave you the answer twice, and you ignored it. That was the simple answer.

Your LLM answer is incorrect, but…it doesn’t matter because LLM answers are not allowed on this forum.

14

That is my own human writing. I posted it because I don’t like leaving a question unanswered. You can see from the first link that I had this conversation on the Jolt forums myself with the Jolt developer, and shockingly they were able to answer the question as asked without asking my life story, checking my forehead temperature, tucking me in for bed or fetching my binky.

I ignored what you were saying because you were ignoring the very clear boundaries I placed down and offering no actual help, demanding instead that I let you “help” me your way. Your answer telling me to get the collisions from a callback was incorrect because that returns a collider, not a mesh, but I didn’t expect you would listen since you both keep asking clarifying questions that are answered in the first post.

I don’t know what you think is wrong about my answer, but you haven’t explained, probably because you stopped reading when you “detected” AI, which kind of proves that you’re not really using your brains here.

And since we’re at it: your chosen solution of berating me to get me to agree that I want & need something that I told you right at the start I don’t, doesn’t appear to be effective. Perhaps you could clarify what problem you are attempting to solve by doing this?

15

How it the text you concocted a solution to the problem of “How to get every face of a mesh that intersects with a given collider”?

Getting all triangles in a sphere is entirely possible, and not complicated at all. You don’t need to make any Jolt calls whatsoever. Had you put some effort into formulating the problem correctly you could have even gotten the code.

If implemented in GDScript the performance might be an issue but not necessarily. It’d depend on the triangle counts per collider/mesh. So a scene setup is a factor for script performance. It could also be optimized by putting some acceptable constraints onto the system (like triangle edges always being shorter than the sphere diameter etc). You can also delegate processing to a thread, spreading it over the frames, and ultimately just move the critical triangle iteration and sphere-triangle check to native code via an extension.

This is generally more of an computational geometry problem than a physics problem, so Jolt hasn’t got much to do with it. Jolt certainly has a sphere-triangle intersection check implemented but this is rather simple to implement on your own anyway. The algorithm is known and straightforward, but it’s only a minor part of the problem. The key part is managing triangles and iterating over them.

The thing is totally doable in GDSscript. Sure, there is no single function call that does it, but why would you expect that?

1 Like
16

No, I actually gave you a clear answer and then gave you additional advice.

No, it returns collisions in space which can then be mapped to the mesh. Which I would have explained if you had asked about it.

So you felt ignored, so you ignored us? Ok. That’s fair.

For some funny reason, I didn’t think you’d read any reason I gave.

You’ve been very hostile from the start to help from people who are offering their time for free. If you don’t want our advice, that’s fine, but why does that make you so angry?

We did not berate you. We tried to help you. Your feelings appear to be hurt because you couldn’t control how we answered. We did the best we could with the information you offered. If the Jolt people gave you an answer you liked, great.

We are justs going to have to agree to disagree here. You believe you gave us enough information. So we answered based on what you gave us. You didn’t like that answer. You also thought that you’d already answered our questions when we asked for more information. At that point, we got no further.

Because you were so myopic on your problem, you still apparently can’t see any other solutions. You’ve answered your question to your satisfaction.

Our final replies were about using an LLM to answer questions on the forum. Editing an LLM answer after being called out on it doesn’t make it not an AI answer. You can’t prove it’s not an LLM, and we cannot prove it is. And so I am going to just agree to disagree.

I’m glad you got your answer. I’m sorry we couldn’t help you.

17

I was not hostile to you in any way prior to my previous post. I tried very hard to be patient and polite to people who insisted on ignoring my one clearly stated boundary, and then I tried to ignore you, but the point where you accuse me of using AI and flag the answer that I actually worked hard on for removal is the point where I stop caring about being nice.

This is gaslighting; you are lying to my face about something I did myself. It is edited with the extra sentence at the start and that is all, you can click on the edit history and see that for yourself. I had to edit it in order to undo the automatic removal that was triggered by one or both of you flagging it for removal.

You still haven’t told me why you thought my “LLM” answer was wrong. It isn’t by the way, that is the way to access adjacent mesh triangles which will allow me to find the triangles that I need in a performant manner, but you don’t seem familiar with the technique if you think it’s wrong. I used my own human brain to link course material from the CS dept at U of IL explaining the concept. You can even see if you read the other thread that I came up with a similar idea and then looked up the theory and gave its name after, which is not something you’d see if I was replacing my thinking with LLM slop. There is a lot of information there that you are free to review at your own pace.

And if you don’t know how to tell the difference between LLM writing and actual human words then that’s your own problem, but a lot of other people reading this will be able to tell and they will see that you falsely jumped on me for “using AI” and it should read pretty clearly as cope. You confused human writing for AI and proved that you can’t tell the difference. You can take the L or not, it doesn’t really impact me as long as my post doesn’t get taken down again, but you might want to think about what it looks like for you if you won’t admit it.