Generation of a list of 3D triangle
I got a lot of letters asking for a copy of my post on connecting points into a shape. So, instead of mailing a bunch of letters, I'm going to just post it here.
I lost the original so I'm going to re-write the post from my notes. The algorithm is one I made up on my own, having done no reading on the subject. I haven't implemented it yet, so I'm not sure how well it works. In the time since my original post, I have modified it a little so it is now simpler and requires no human help.
The basic idea is based on a "curtain" that falls from the top of the shape to the bottom, connecting points into triangles as it goes. The curtain is a ring of connected points. Above the curtain, the shape has been connected with triangles. Below the curtain, there is nothing but points waiting to be connected.
First thing you have to do is organize your points from top to bottom (or left to right, front to back, whatever). Now you'll go through the points one by one starting at the top and going down. The first three points will form the first triangle and they will start off the curtain.
Now you want to add the next point. What you do is you go through all the points in the curtain (3 right now), looking for the two that are closest to the point you want to add. When you find the two closest points, you may find that other points are in between them. Something like this:
B-----C (assuming an 80x25 screen here)
/ \
/ \
/ \
<---A D---> (the arrows mean the curtain keeps going)
PP is the point you want to add. The closest two points are A and D. So you'll want to connect point P by making triangle APD. But that would leave a hole ABCD. So you'll have to get B and C out of the curtain first. I'll go into detail about how to remove B and C later. Anyway, once they're gone, you can connect point P and now your curtain looks like this:
<--A-__ ___--D-->
-P--P is inserted into the curtain, and you've successfully assimilated one more point into the shape. In my original idea, every time you added a point, the curtain got one point bigger and you had to figure out a way to get rid of an old point to keep the size of the curtain down. It also had a lot of problems with skinny triangles and other special cases. But if you just connect the new point with the two points in the curtain that are closest, these problems go away. At least I think they do. The only disadvantage is that finding the closest points involves a sqrt.... However, there usually aren't too many points in the curtain so you don't have to do that many sqrts.
Now, what happens once you've added all the points you have? You have a shape with a hole in the bottom. :)
So, all we need to do is close up the hole. It turns out that closing the hole is the exact same problem as getting rid of points B and C above. So, I think it would be best to put that part in a separate function - you pass it the two points on the end (A and D) and it gets rid of all the points in between.
I should say something about what kind of data structures I'm using in this. For the curtain, I'm using a linked list with a beginning and an end. Even though the curtain is better modeled as a circularly linked list, I think it would be easier to scan through each point in the curtain one by one if the ends didn't meet. That's a minor difference, though.
I'm assuming the list of points is an array of (x,y,z) coordinates, sorted along one axis. Once this array of points is sorted, it won't be changed.
The produced shape is a list of triangles. To define a triangle, you only need three points, and since each point can be represented by just one number (its index into the array), each triangle only needs three numbers. In order to make it possible to calculate normal vectors after the shape is generated, I would store the three points in a specific order so you can tell which way is clockwise and therefore which side of the triangle is out. It doesn't matter which order you use, just as long as you're consistent.
You know ahead of time how many triangles you'll have based on how many points you started with. Every time you add or remove a point from the curtain, you create a triangle (except for the first and last 3 points). So the number of triangles you will generate is 2*(num_points-3)+2. Of course, that assumes you're starting with more than 3 points (otherwise you won't have a shape anyway).
Now I cover how to remove points from the curtain.
Suppose your curtain looks like this and you want to remove all the points in between A and E.
B
/ \ __--D--__
/ C-- --__
A --EYou can remove them according to their order in the curtain: first ABC, then ACD, then ADE. However, if you've got a lot of points to remove, this leads to a bunch of triangles that all have one point at A and it looks like a fan or something. You might like that effect, but just in case you don't, you can try removing them by height. B is highest so you remove ABC, D is next so you remove CDE, then finally you remove ACE. You might find that that has strange effects, too, but I can't think of them offhand. Another approach would be to remove triangles with the smallest sides first. There are plenty of different ways to remove the points, so I encourage you to think up your own way - maybe even have a few methods that your algorithm could choose between.
I didn't mention this: be sure to realize that when you remove a point, you generate a triangle. That's why I removed point ACE instead of just C.
Now, as I say, I haven't implemented this yet. And I didn't go through any complicated math proofs, either. So it's possible that you'll get some rather awkward looking shapes. However, I think the fact that you are adding points in order from top to bottom will keep any polygons from intersecting. I'm not sure of that, but I'd be willing to bet a few dollars on it. :)
However, no matter how weird the shapes you get are, the fact is that this is a pretty quick algorithm - and speed is what I like most. If you do it all in integer coordinates, you can use an integer square root. And I have an integer square root that goes like lightning. The big O is friendly, too - sorting the points can be done with shellsort or something, and then generating the point is somewhere between O(n) and O(n^2) (but the n^2 is the absolute upper bound - extremely special case and easily gotten rid of by sorting along a different axis, bringing it down to O(log n) or so).
So, there you are. If you think of any weak spots in the algorithm, or you find out that it's already been described and has a name, or you have any questions on it, or you actually want to implement it, please email me.
--
Kimberley (OKRA@max.tiac.net)
