144 lines
7.5 KiB
Plaintext
144 lines
7.5 KiB
Plaintext
From OKRA@max.tiac.net Thu Sep 22 23:19:28 1994
|
|
Path: ousrvr.oulu.fi!news.funet.fi!sunic!uunet!panix!ddsw1!redstone.interpath.net!news.sprintlink.net!sundog.tiac.net!max.tiac.net!OKRA
|
|
From: OKRA@max.tiac.net (Kimberley Burchett)
|
|
Newsgroups: comp.graphics.algorithms
|
|
Subject: Re: [Q] Generation of a list of 3D triangle
|
|
Date: 17 Sep 1994 18:45:49 GMT
|
|
Organization: The Internet Access Company
|
|
Lines: 129
|
|
Message-ID: <35fdgt$qjo@sundog.tiac.net>
|
|
References: <1994Sep15.182545.11111@leeds.ac.uk> <35asjh$rj2@sundog.tiac.net>
|
|
NNTP-Posting-Host: max.tiac.net
|
|
X-Newsreader: TIN [version 1.2 PL2]
|
|
|
|
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)
|
|
P
|
|
|
|
P 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 --E
|
|
|
|
You 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)
|
|
|