Hi there,

Does anybody know the criteria to determine a point is inside a tetrahedral?

Thanks in adcance!

(1).A point is inside, when lines connecting the point and the vertices do not intersect the existing surfaces.

Then, How to determine the intersection? Any formular available?

Thanks!

It seems to me that if you define the (unit) normals to the faces consistently, then you should be able to decide whether a point is inside (or outside) by simply evaluating the normal distances from the point to the surfaces. If all the normal distances have the same sign - all positive (for outward-facing unit normals to the faces) or all negative (for inward facing unit normals to the faces) - then the point is inside the volume. If any normal distance is zero, then the point is on a surface, and if the normal distances have differing signs then the point is outside.

The normals are easily evaluated by the vertices of surfaces (and the linear shape function)

Adrin Gharakhani

find a computational geometry book

(1). By this time, you probably have the correct answer already. (2). The short answer I presented could not be considered as the correct answer. (3). "inside" means on the same side enclosed by all surfaces. The directional normal would be the right way to define it in the first place. I will use the concept of the local coordinate system of the surface to show how to do it.(4). So, each surface has two sides, one is pointing inward, the other pointing outward. (you have to define it in the first place .) And each surface divides the space into two parts. By transforming (constructing) the coordinate system to line up with the outward normal of the surface, one can determine whether a point is on the positive side (outside) or negative side (inside). (5). If the point is on the inside of the first surface, then move on to check if it is also on the inside of the second surface. If it is on the inside of the second surface again, then move on to the third surface and repeat the same checking. In this way, the point inside the Tet will be on the same side (inside) of each surface. (6). If you use local coordinate system on a surface so that positive x-coordinate is in the outward direction (you must determine which direction is toward the outside first.), then you can easily determine the positiveness of the point in question relative to this local coordinate system. Repeat the same test for each surface using its local coordinates. (7). Sine any two points define a line, any three points define a surface. The vector cross operation on the two edge lines will give you the third coordinate (local x-coordinate) of the surface local coordinate system. (8). To define a local coordinate system, first pick a vertex point as the origin. Then define the first two coordinates by using the edge line vectors (from the first vertex to the second vertex, from the first vertex to the third vertex, these are the two vectors with the origin defined at the first vertex on the surface). The third coordinate is just the vector cross operation of these two vectors. And it will be normal to the surface.(you will have to decide which direction is outward). (9). If you repeat the same processes, each surface will have its own local coordinates, and each will have a local x-coordinate pointing outward (same as the surface normal direction). Strictly speaking, the surface normal direction is arbitrary. But you have to be consistent in defining the Tet in the first place. (10). For example, negative x- of surface-1, negative x- of surface-2, and negative x- of surface-3 can be defined as the inside of the Tet. If the positive x- happen to be pointing toward the inside of the Tet, then the inside would be defined as: positive x- of surface-1, negative x- of surface-2, and negative x- of surface-3. In checking whether a point is inside a Tet, the consistent definition must be used to do the checking. So, both above definitions are legal, but it is less confusing when one define the outward normals all in the same positive x-coordinate direction. (11). Not all answers on Internet are correct. But, if you work harder, you will be able to find the right answer. I guess, I was not thinking when I presented the short answer. (12). By the way, "Xia" used to be "Hsia" and "He" used to be "Ho". The world is really very confusing, when "He" is not a he but a she.

Hi, Mr. Xia,

I am happened to be the person who is developing and maintaining a 3D code. I know the usual way to determine whether a point is inside a tetrahedron. It is as follows:

First the nodes of the element should be ordered in some format, such as NASTRAN or PATRAN format, then you need to calculate the volume of the tetrahedral element (actually the determinant of the Jacobian matrix). In the above format, the volume should be positive.

Then it's very easy to determine if any point is inside the tetrahedron. Calculate 4 determinant of the Jacobian matrix by replacing one node with that point (notice the order). If all 4 are positive, then that point is inside the tetrahedron. Actually you know these 4 determinants / volume are the local coordinates of the unit tetrahedron. And maybe you need these 4 local coordinates to do some intrepolations.

Hope you can understand what I mean.

Good luck,

yangang bao

Hi, Mr. Bao,

I think I have a way, which is very similar to yours. Since I am working on mesh adaptation, rather than generation, I am not familiar with the formats. The way I find is, for each triangular surface of the tetrahedral, calculate the volumes formed with the other node, and the new node. If the volumes are of the same signs, they are located at the same side of the tetradral surface. If for all the surfaces, the new node lies in the side of the surface, this node is inside the tetrahedral. Does this seem to be right for you?

Thank you for your kind help!

Guoping Xia

Hi, Mr. Chien,

Thank you for your kind help! I think I have found an way, which is easier to implement in the code. I described it in the message below, Do you think there is anything wrong?

Guoping Xia

Hi, Mr. Xia,

Your idea is exactly the same as what I mentioned. But I suggest that you use a fixed format since it's convenient for you determine the meaning of the sign when you calculate the volume.

You know all meshes have 2 kinds of information. One is the node coordinates, the other is the node connectivity for each element. The format I mean is the rule of the order of the nodes in each element. With a fixed format, the signs of the volumes that you calculated have the same meaning so you can easily figure out the location of the points.

Good luck.

yangang bao

By the way, it's easy to get a fixed format for tetra case. Given a mesh, when you calculate the volume of each element (the determinant of the Jacobian matrix), if it's negative, just simply exchange any 2 nodes in that element.

(1). The distance and the volume are always defined as positive numbers. So, the volume and the distance both have no sign associated with them.

Hi,

When volume is evaluated by the determination of a matrix, which is associated with the order of the tetrahedral nodes, it can result in a negative value if the vectors are not right-handed. Think about it carefully.

Guoping

(1). But I don't think volume is related to the matrix, the volume of a tetrahedron is just the volume enclosed inside the four surfaces. (2). The sign in the matrix operation must be related to something else (that is whether it is inside or outside, a directional property), it should not be interpreted as part of the definition of the volume.

In 3-D space, volume of a tetrahedral is related to the determinator of a matrix with the right order of the nodes. With the wrong order it is not the volume, but its magnitude is equal to the volume, only with the wrong sign.

Hi,

I suggest the following algorithm:

bool inside = true; for each face of the tetrahedron {

Calculate the volume of the tetrahedron defined by

the face and the point;

if ( volume < 0.0 ) inside = false; }

Michael Aftosmis has a good web page on this:

http://george.arc.nasa.gov/~aftosmis...ersection.html

Regards,

Robert

Robert Schneiders MAGMA Giessereitechnologie GmbH D-52072 Aachen Kackertstr. 11 Germany Tel.: +49-241-88901-13 email: R.Schneiders@magmasoft.de www: http://www-users.informatik.rwth-aachen.de/~roberts/

(1). If you use the matrix method, then it is all right to talk about the sign. (2). Otherwise, for those who are not using the matrix method, the volume itself is always positive. (3). There is a relationship between the matrix method and the volume, but they are not identical object.