about how to calculate candidate triangles from a mesh

Question

0.00/5 (No votes)

See more:

I am trying to calculate the distance between a point and the triangles in the triangular mesh for collision handling for a CFD software.I have already coded for the minimum distance calculation between a particular triangle and point.Now the problem is to find the candidate triangles(the triangles with which i calculate the distance from the given point for possible collision).What can i do to find the candidate triangles?Is there an algorithm for it? what do the CFD softwares do in these cases.Do they actually find the candidate triangles or they find the distances of the point from all the triangles in the mesh?
please help..

Posted 25-Jul-13 22:49pm

pramithas dhakal

Updated 29-Jul-20 1:57am

v3

Add a Solution

Comments

Stefan_Lang 29-Jul-13 10:24am

A point by itself doesn't collide, unless it moves. You don't need to find the distance of a point, you need to find the intersection of the trajectory it moves along with the triangles.

pramithas dhakal 4-Aug-13 6:11am

ok.but how to find which triangles are the candidate triangles for intersection? Or we have to check all the triangles for intersection with a particle.

The_Inventor 4-Aug-13 12:43pm

Once you have your data in an array, it will relatively simple to check one array of point against an array of triangles.

Stefan_Lang 5-Aug-13 3:22am

My answer wasn't entirely accurate: if your goal is to check whether a point lies inside a _solid_ object that is described by its outer surface, then, technically, you don't need to know about the trajectory of the point. If you just want to know whether a moving point is going to collide with a _surface_ (or a moving surface going to collide with a point), then you need it.

Either way, yes, you need to check every triangle.

See my solution below for details.

3 solutions

Solution 1

Presume x,y,z cords, for the three point that make the triangle, and the center of your particle. If your particle has a volume, then you add the radius to the center, find the maxima box, and the see if your triangle is in there.

Posted 4-Aug-13 7:16am

The_Inventor

Solution 3

I had an almost similar scenario where I wanted to optimize a list of triangles coming from a Tria mesh to check if they were intersecting a cell in my grid. Typically the brute force way of doing it would be to check all triangles in the mesh against all cells in the grid resulting in O(n^2) time complexity if there were n triangles and n cells. Although I'm still looking for solutions, I'm convinced its going to be hidden amongst the different solutions available for "culling" primitives to check during collision detection in Game engines. You might want to look into topics related to Broad phase/range collision detection, Quadtree/Octree, Cell hashing and other related techniques.

Posted 29-Jul-20 1:57am

Member 14901987

Updated 29-Jul-20 1:58am

v2

Comments

Patrice T 29-Jul-20 8:07am

Ask your own question to get help: https://www.codeproject.com/Questions/ask.aspx[^]
and delete this

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Stefan_Lang · Accepted Answer · 2013-08-04T21:28:00

Solution 2

First, you need to check every triangle. You can speed up that check by building an octree that partitions your 3D-space into managable grid cells. (see http://en.wikipedia.org/wiki/Octree[^] or google for tutorials and code how to use it)

For each octree cell, you can precalculate which triangle intersects it and which don't. Then, when you want to check a point, just check which octree cell it is in, and then go on to check which triangles you know intersect that same cell: if you built your octree well, there may only be 3-5 triangles that you actually need to check.

If you want to check whether a point is inside a solid or outside, you need to define a line through that point. If the point is moving, you may use the current direction of movement to define the direction of the line; this will provide additional information. Otherwise the direction is irrelevant, but the calculations will be easier if you use one of the axes, e. g. (1,0,0).

For this line, determine all cells of the octree that it hits. Then, for each cell, check which triangles intersect the cell. For these triangles, intersect the line with the triangle, then check whether the point of intersection actually is inside the boundaries of the triangle.

Count the number of intersection points that lie on one side of your starting point along the line. If that number is odd, then your point is inside the solid. If it is even, then it is outside.

Posted 4-Aug-13 21:28pm

Stefan_Lang

Updated 4-Aug-13 22:54pm

v2

Comments

pramithas dhakal 7-Aug-13 4:48am

thanks for the idea of octree..I am working on it now...

pramithas dhakal 23-Aug-13 12:07pm

Stefan_lang,
i have created an octree with each leaf containing one particle each.now i need to find out the neighbouring particle.i have calculated the neighbouring particle in this way. i have taken a cube to start with and found out all the cubes that are in contact with it in any way. is this the right way to find the neghbouring particle.what is the general approach taken for this problem. expecting your advise.

Stefan_Lang 27-Aug-13 3:03am

I have never implemented an Octree myself, I'm only planning a similar structure and I have past experience using one. So take the following with a grain of salt and use your own judgement:

For finding neighbouring particles, depending on your definition of neighbouring, there are two ways and their (dis-)advantages:

1. Implement some functionality to find geometrical neighbour-cubes
- may require building and maintaining additional data for neighbourhood properties
- probably non-trivial code to determine all neighbour
- depending on neighbour cube size, may require more than one step of neighbour-finding
+ minimal number of cubes to check
+ apparently you already implemented (some of) it

2. determine geometrical measurements of neighbourhood range (usually a sphere or cube centered on your starting particle), then determine all cubes touching that range
- need to check all cubes to find out which is touching the range
+ trivial code, especially if you use a cube to define the neighbourhood range
+ you may be able to find octree implementations that already contain such a function

The second method is more in the spirit of the octree, but is probably worse in performance, depending on the percentage of cubes that are neighbours by your definition, and the number of neighbour operation you need to perform. OTOH, if performance is a criterium, the second algo is relatively easy to implement in parallel on a GPU.

Personally I like the first method (yours) better, but if I were to implement an octree for the first time, I'd probably start with the second, since finding cubes touched by a geometric range is a standard functionality that you'll need anyway.

pramithas dhakal 23-Oct-13 22:40pm

thanks for your advice...i successfully did the finding of neighbouring particles...but now the problem is to store the triangles in an octree and find the neighbouring triangles of a particles...storing the triangle seems a difficult task given the variable size of the triangle from very small to very big....storing the vertex only does not seem a solution since it does not always give the location of the triangle since a large triangle may be contained in multiple octree cubes...do you have idea how it is generally done...

Stefan_Lang 28-Oct-13 4:09am

As described in the solution, for every octree cell you must determine all triangles that intersect it. So for each triangle, you need to check the entire triangular surface, not just the corners or edges. It is possible - even likely - that there is a triangle that intersects an octree cube even though all of it's edges are outside! (and this is true even if all your triangles are smaller than the cubes!)

I suggest you google for "intersect cube triangle" to find a suitable algorithm - since I've never needed such an algo myself I cannot provide advice in that area.