View Full Version : Mathematician needs help programming

03 March 2005, 12:20 PM
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!

03 March 2005, 07:05 PM
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)

03 March 2005, 07:27 PM
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.

03 March 2005, 08:14 PM
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.

03 March 2005, 01:28 AM
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.

03 March 2005, 04:34 AM
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:)

CGTalk Moderation
03 March 2005, 04:34 AM
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.