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)