# Mathematician needs help programming

#1

Hi folks!

First of all: I have no clue of computer graphics whatsoever and therefore ask your forgiveness if this post is out of place here. I do, however, have a mathematical programming problem with which I believe CG specialists might be able to help me.

And here goes: Assume we have four or more points in three-dimensional space, known by their coordinates (x,y,z), which are not all lying on a plane. Then those points, if connected, form a three-dimensional object of some kind with a clearly defined inside and outside.

What I need now is some kind of algorithm to determine, using only coordinates and no visualisation, whether a randomly chosen point in 3D space is inside or outside the 3D object described above.

Any help is greatly appreciated!
Nerkitt

#2

sounds like someones homework problem. this isn’t particularly advanced maths. however if you have no conection/polygons between the points you will need to calculate that first which can be complex. there are a number of ways of doing that as i’m sure you’re aware (for instance you could use a 3d Delaunay pattern to calculate the faces assuming closest=correct).

you need the polygons/faces/connection relation in order to determine in/out really, as an arbirary pointset could be connected in any arbitrary manner (i.e. the surface could be concave). once you have those you can calculate this a number of ways, from raycasting through to winding methods. an easy way for instance would be to expand the simple in/out polygon method and cast a single ray outwards in any direction counting the number of faces it hits, if the number is even or 0 then you’re outside, if it’s odd then you’re inside. of course this assumes that the volume is closed.

here’s one based on a winding/normals method (just see if the normals of the polygons face you or away from you) http://stevehollasch.com/cgindex/polygons/orienting.html

#3

This looks like those INtroduction to Calculus 3 kind of problem.

if connected, form a three-dimensional object of some kind with a clearly defined inside and outside.

I don’t know which book gave you that sentense, but you can never create a “clearly defined” hull when there are more than 3 vertices. Because 4+ vertices can create Convex and Concave hulls. That is why mathematics uses multiple curve to create Volumes which are more “clearly defined”.

Two methods to distingiush the problem (based on how much accuracy you want)

->A HULL (shape formed by 3D vertices connected together) is defined by the Normals in addition to the vertex coordinates. If you have the normals, then this will give you the most accurate answer. You can effectively calculate using the raycasting method (vertex to plane intersection method).

->Second method is the cheapest and less accurate. If you average the vertices, and find the center of the Volume, (Remember those Center of Volume problems???). If the vertex in question is x distance from the center and if x < the than the closest vertex that forms the hull, then x is inside the hull (convex). IF not, it might still be inside. But the only way to check is by Line Intersection method. That is if the vertex in question intersects a plane formed by the the hull connecting vertices. If there are exactly 4 vertices, then if the plane formed by the lines connecting the farthest vertex to the closest vertex is the one you should use for the line intersection query. Anything more than 4 vertices, will give you no garantee.

If you and anyone here finds the answer, I am very interested in the solution as well.

#4

if it’s such a specific case I assume it’s a classic homework.

this is a particular case that requires no complex point cloud reconstruction into an object, because 4 non co-planar points can only form one solid (since you haven’t been given any more info you can only create an explicitly faceted object), which is a pyramid with a triangular base, where every point is connected to all other points.

`````` all you need to do is resolve it into 4 triangles.
``````

take an arbitrary point (let’s say 1), calculate a triangle connecting that to 2 and 3, calculate another triangle connecting it to 3 and 4 and then create the last triangle from all points except the first (2, 3 and 4).

once you have these 3 triangles and the point you want to check for presence inside the object,cast a random ray from the point (in this case a ray will be just a vector starting from that point and of near infinite magnitude) and check this ray for intersection against all triangles.

`````` if this ray intersects once the point is inside the object, if it intersects 0 or twice it's outside.
``````

also remember to perform particular cases checks making sure the point isn’t sitting exactly on a vertex, on a triangle or that your random ray isn’t traveling exactly through one or more vertices.

also, for the sake of implementation and flooring the magnitude of the ray vector, the ray vector you use can be of a magnitude equal to the distance between the point you are checking and the furthest of the 4 vertices forming the solid (plus something for the sake of particular cases)

`````` if you're not familiar with rays here's a comparison of several ray2triangle algorithms
[http://wscg.zcu.cz/wscg2001/Papers_2001/R75.pdf](http://wscg.zcu.cz/wscg2001/Papers_2001/R75.pdf)
``````

edit:
almost forgot, if you also want normals on these triangles, for the sake of defining inside and outside in shading problems and not just in intersection problems, you can always calculate the normal finding the perpendicular to each triangle and sitting a normalized vector on it orienting it so that it points AWAY from the only point not in that triangle.

gotta love particular cases

#5

There is no correct answer to your problem and the question is ill-defined.

The question is ill defined first because you are not stating “how” you connect those points. Do you try to find and follow the convex hull? Do you just connect the points in the order given?
The question is also incorrect in that 4 points placed randomly in space will not always give you what you state: a “three-dimensional object of some kind with a clearly defined inside and outside”.
For example, those 4 points may just be lying along a line, in which case there will be no 2 or 3 dimensional shape to speak of and thus no interior/exterior.
If you connect points based on order, those 4 points may create a shape that not only can it be convex but it can also result in self-crossing. Again, no clear interior/exterior.
If your points don’t lie on a plane, you can also end up with something with no clear interior/exterior. The problem happens all the time in CG when artists pull points of 3+ sided polygons and create degenerate polygons or when they perform a deformation like skinning with incorrect weights on one of the vertices.

#6

if it was 4 points it would be valid, as 4 -non coplanar- points can only result in one kind of faceted object, a single triangular base pyramid with every point connected to all the other points.
in that case it’s also very easy to define the normals of this pyramid, because they will always be, for every triangle, a normalized vector, baricentric to the triangle, oriented perpendicular to that unique plane and facing away from the only point not included in that triangle.

however the problem IS weird because it says 4 or more, and when it becomes that “more” points there are no particular cases anymore that allow to resolve into a unique result.

#7

Ya, that is why I am really interested in this question if this question indeed come from a teacher or a book.

The moment someone finds a nice “little equation” to find a point intersection from that description, he should be awarded the Nobel Price:)

#8

This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.