How do i generate triangles from points on a plane? (in 3D)

Newbie & Debugging Questions
#1

Hello everyone!

I have a question, for that i can’t seem to find a good answer for on Google.

The question is this:
I have a plane in 3-dimensional space, that is stored as a object containing a plane-equation,position and a surface-Normal.
And I have a set of n 3D-points, that all are lying on the plane.


// Probably important: Im using Vector's as Point's and vice-versa.
class Vector
{
 float x,y,z;
 
 -snippedTheRestOfTheClass-
}



class Plane
{
 float d;
 Vector position;
 Vector normal;
 
 -snippedTheRestOfTheClass-
}

Now i wan’t to generate Triangle’s from these points-on-the-plane.
Im somewhat unable to successfully implement a algorythm that does that for me.
My math-teacher told me I should try to ‘2D-project’ the point’s onto the plane and connect them then using 2D logic.
Too bad I don’t know how to do this right.

Please help!

  • Longor1996

PS: Im (still) sick, so please write in a way that i don’t have problems to understand the things you write.
PPS: Also, i wan’t to generate as few triangle’s as possible, if that is possible.
PPPS: The generation of these triangle’s is for ‘offline’-use, so it doesn’t have to be fast.

#2

You’re teacher’s correct, since all the points are on a plane it’s a 2D problem. But to get an answer to your question you’ll have to provide more details. Like what are you attempting to do.

EDIT: Well, assuming that there’s an outer perimeter of whatever it is you’re doing, then you need to find the convex hull…well assuming you want convex containment.

#3

Okay, how does one project points onto a plane and then connect them to make triangle’s?
Maybe I have luck searching for “project points onto plane and connect hem to triangle’s”.
And I already said what I wan’t to do, if you wan’t to know for what exactly:
It’s for a CSG-Raytracer based on triangle-meshe’s. I already know how to do everything, the only missing part is the triangle generation.
And don’t tell me that I can raytrace CSG-body’s directly, i already know that.
It’s just that I would like to use the triangle-generator for some other thing’s later too.

  • Longor1996
#4

We’re already having a communication problem: You say that all the point are on a plane. If that is the case there’s no projection needed.

search: “mesh from point cloud”.

#5

Okay, I found something called “Delaunay triangulation”, wich seems like the best solution to my problem.
Actually, not all point’s are on the plane, but these non-plane point’s are getting sorted out by a very simple point-on-plane test before they are put into the trinalge generator.

Thank’s for the advice.

  • Longor1996
#6

In that case: I’m pretty sure that there is a java version of qhull which probably has the code that you need.

#7

Delaunay’s is a pretty good algo. There are other algos you might want to try like seidels to generate voronoi diagrams.

If you just want a convex hull, I used grahams.

I have some code here but google would probably give you better examples in java since mine is in another language.