make-movie

triangle.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <sys/time.h>

Classes

struct  otri
struct  osub
struct  badsubseg
struct  badtriang
struct  flipstacker
struct  event
struct  splaynode
struct  memorypool
struct  mesh
struct  behavior

Defines

#define REAL   double
#define INEXACT
#define FILENAMESIZE   512
#define INPUTLINESIZE   512
#define TRIPERBLOCK   4092
#define SUBSEGPERBLOCK   508
#define VERTEXPERBLOCK   4092
#define VIRUSPERBLOCK   1020
#define BADSUBSEGPERBLOCK   252
#define BADTRIPERBLOCK   4092
#define FLIPSTACKERPERBLOCK   252
#define SPLAYNODEPERBLOCK   508
#define INPUTVERTEX   0
#define SEGMENTVERTEX   1
#define FREEVERTEX   2
#define DEADVERTEX   -32768
#define UNDEADVERTEX   -32767
#define VOID   int
#define SAMPLEFACTOR   11
#define SAMPLERATE   10
#define PI   3.141592653589793238462643383279502884197169399375105820974944592308
#define SQUAREROOTTWO   1.4142135623730950488016887242096980785696718753769480732
#define ONETHIRD   0.333333333333333333333333333333333333333333333333333333333333
#define decode(ptr, otri)
#define encode(otri)   (triangle) ((unsigned long) (otri).tri | (unsigned long) (otri).orient)
#define sym(otri1, otri2)
#define symself(otri)
#define lnext(otri1, otri2)
#define lnextself(otri)   (otri).orient = plus1mod3[(otri).orient]
#define lprev(otri1, otri2)
#define lprevself(otri)   (otri).orient = minus1mod3[(otri).orient]
#define onext(otri1, otri2)
#define onextself(otri)
#define oprev(otri1, otri2)
#define oprevself(otri)
#define dnext(otri1, otri2)
#define dnextself(otri)
#define dprev(otri1, otri2)
#define dprevself(otri)
#define rnext(otri1, otri2)
#define rnextself(otri)
#define rprev(otri1, otri2)
#define rprevself(otri)
#define org(otri, vertexptr)   vertexptr = (vertex) (otri).tri[plus1mod3[(otri).orient] + 3]
#define dest(otri, vertexptr)   vertexptr = (vertex) (otri).tri[minus1mod3[(otri).orient] + 3]
#define apex(otri, vertexptr)   vertexptr = (vertex) (otri).tri[(otri).orient + 3]
#define setorg(otri, vertexptr)   (otri).tri[plus1mod3[(otri).orient] + 3] = (triangle) vertexptr
#define setdest(otri, vertexptr)   (otri).tri[minus1mod3[(otri).orient] + 3] = (triangle) vertexptr
#define setapex(otri, vertexptr)   (otri).tri[(otri).orient + 3] = (triangle) vertexptr
#define bond(otri1, otri2)
#define dissolve(otri)   (otri).tri[(otri).orient] = (triangle) m->dummytri
#define otricopy(otri1, otri2)
#define otriequal(otri1, otri2)
#define infect(otri)
#define uninfect(otri)
#define infected(otri)   (((unsigned long) (otri).tri[6] & (unsigned long) 2l) != 0l)
#define elemattribute(otri, attnum)   ((REAL *) (otri).tri)[m->elemattribindex + (attnum)]
#define setelemattribute(otri, attnum, value)   ((REAL *) (otri).tri)[m->elemattribindex + (attnum)] = value
#define areabound(otri)   ((REAL *) (otri).tri)[m->areaboundindex]
#define setareabound(otri, value)   ((REAL *) (otri).tri)[m->areaboundindex] = value
#define deadtri(tria)   ((tria)[1] == (triangle) NULL)
#define killtri(tria)
#define sdecode(sptr, osub)
#define sencode(osub)   (subseg) ((unsigned long) (osub).ss | (unsigned long) (osub).ssorient)
#define ssym(osub1, osub2)
#define ssymself(osub)   (osub).ssorient = 1 - (osub).ssorient
#define spivot(osub1, osub2)
#define spivotself(osub)
#define snext(osub1, osub2)
#define snextself(osub)
#define sorg(osub, vertexptr)   vertexptr = (vertex) (osub).ss[2 + (osub).ssorient]
#define sdest(osub, vertexptr)   vertexptr = (vertex) (osub).ss[3 - (osub).ssorient]
#define setsorg(osub, vertexptr)   (osub).ss[2 + (osub).ssorient] = (subseg) vertexptr
#define setsdest(osub, vertexptr)   (osub).ss[3 - (osub).ssorient] = (subseg) vertexptr
#define mark(osub)   (* (int *) ((osub).ss + 6))
#define setmark(osub, value)   * (int *) ((osub).ss + 6) = value
#define sbond(osub1, osub2)
#define sdissolve(osub)   (osub).ss[(osub).ssorient] = (subseg) m->dummysub
#define subsegcopy(osub1, osub2)
#define subsegequal(osub1, osub2)
#define deadsubseg(sub)   ((sub)[1] == (subseg) NULL)
#define killsubseg(sub)
#define tspivot(otri, osub)
#define stpivot(osub, otri)
#define tsbond(otri, osub)
#define tsdissolve(otri)   (otri).tri[6 + (otri).orient] = (triangle) m->dummysub
#define stdissolve(osub)   (osub).ss[4 + (osub).ssorient] = (subseg) m->dummytri
#define vertexmark(vx)   ((int *) (vx))[m->vertexmarkindex]
#define setvertexmark(vx, value)   ((int *) (vx))[m->vertexmarkindex] = value
#define vertextype(vx)   ((int *) (vx))[m->vertexmarkindex + 1]
#define setvertextype(vx, value)   ((int *) (vx))[m->vertexmarkindex + 1] = value
#define vertex2tri(vx)   ((triangle *) (vx))[m->vertex2triindex]
#define setvertex2tri(vx, value)   ((triangle *) (vx))[m->vertex2triindex] = value
#define STARTINDEX   1
#define Absolute(a)   ((a) >= 0.0 ? (a) : -(a))
#define Fast_Two_Sum_Tail(a, b, x, y)
#define Fast_Two_Sum(a, b, x, y)
#define Two_Sum_Tail(a, b, x, y)
#define Two_Sum(a, b, x, y)
#define Two_Diff_Tail(a, b, x, y)
#define Two_Diff(a, b, x, y)
#define Split(a, ahi, alo)
#define Two_Product_Tail(a, b, x, y)
#define Two_Product(a, b, x, y)
#define Two_Product_Presplit(a, b, bhi, blo, x, y)
#define Square_Tail(a, x, y)
#define Square(a, x, y)
#define Two_One_Sum(a1, a0, b, x2, x1, x0)
#define Two_One_Diff(a1, a0, b, x2, x1, x0)
#define Two_Two_Sum(a1, a0, b1, b0, x3, x2, x1, x0)
#define Two_Two_Diff(a1, a0, b1, b0, x3, x2, x1, x0)
#define Two_One_Product(a1, a0, b, x3, x2, x1, x0)

Typedefs

typedef REAL ** triangle
typedef REAL ** subseg
typedef REAL * vertex

Enumerations

enum  wordtype { POINTER, FLOATINGPOINT }
enum  locateresult { INTRIANGLE, ONEDGE, ONVERTEX, OUTSIDE }
enum  insertvertexresult { SUCCESSFULVERTEX, ENCROACHINGVERTEX, VIOLATINGVERTEX, DUPLICATEVERTEX }
enum  finddirectionresult { WITHIN, LEFTCOLLINEAR, RIGHTCOLLINEAR }

Functions

char * readline ()
char * findfield ()
int triunsuitable (vertex triorg, vertex tridest, vertex triapex, REAL area)
VOID * trimalloc (int size)
void trifree (VOID *memptr)
void syntax ()
void info ()
void internalerror ()
void parsecommandline (int argc, char **argv, struct behavior *b)
void printtriangle (struct mesh *m, struct behavior *b, struct otri *t)
void printsubseg (struct mesh *m, struct behavior *b, struct osub *s)
void poolrestart (struct memorypool *pool)
void poolinit (struct memorypool *pool, int bytecount, int itemcount, int firstitemcount, enum wordtype wtype, int alignment)
void pooldeinit (struct memorypool *pool)
VOID * poolalloc (struct memorypool *pool)
void pooldealloc (struct memorypool *pool, VOID *dyingitem)
void traversalinit (struct memorypool *pool)
VOID * traverse (struct memorypool *pool)
void dummyinit (struct mesh *m, struct behavior *b, int trianglewords, int subsegwords)
void initializevertexpool (struct mesh *m, struct behavior *b)
void initializetrisubpools (struct mesh *m, struct behavior *b)
void triangledealloc (struct mesh *m, triangle *dyingtriangle)
triangle * triangletraverse (struct mesh *m)
void subsegdealloc (struct mesh *m, subseg *dyingsubseg)
subseg * subsegtraverse (struct mesh *m)
void vertexdealloc (struct mesh *m, vertex dyingvertex)
vertex vertextraverse (struct mesh *m)
void badsubsegdealloc (struct mesh *m, struct badsubseg *dyingseg)
badsubseg * badsubsegtraverse (struct mesh *m)
vertex getvertex (struct mesh *m, struct behavior *b, int number)
void triangledeinit (struct mesh *m, struct behavior *b)
void maketriangle (struct mesh *m, struct behavior *b, struct otri *newotri)
void makesubseg (struct mesh *m, struct osub *newsubseg)
void exactinit ()
int fast_expansion_sum_zeroelim (int elen, REAL *e, int flen, REAL *f, REAL *h)
int scale_expansion_zeroelim (int elen, REAL *e, REAL b, REAL *h)
REAL estimate (int elen, REAL *e)
REAL counterclockwiseadapt (vertex pa, vertex pb, vertex pc, REAL detsum)
REAL counterclockwise (struct mesh *m, struct behavior *b, vertex pa, vertex pb, vertex pc)
REAL incircleadapt (vertex pa, vertex pb, vertex pc, vertex pd, REAL permanent)
REAL incircle (struct mesh *m, struct behavior *b, vertex pa, vertex pb, vertex pc, vertex pd)
REAL orient3dadapt (vertex pa, vertex pb, vertex pc, vertex pd, REAL aheight, REAL bheight, REAL cheight, REAL dheight, REAL permanent)
REAL orient3d (struct mesh *m, struct behavior *b, vertex pa, vertex pb, vertex pc, vertex pd, REAL aheight, REAL bheight, REAL cheight, REAL dheight)
REAL nonregular (struct mesh *m, struct behavior *b, vertex pa, vertex pb, vertex pc, vertex pd)
void findcircumcenter (struct mesh *m, struct behavior *b, vertex torg, vertex tdest, vertex tapex, vertex circumcenter, REAL *xi, REAL *eta, REAL *minedge, int offcenter)
void triangleinit (struct mesh *m)
unsigned long randomnation (unsigned int choices)
void checkmesh (struct mesh *m, struct behavior *b)
void checkdelaunay (struct mesh *m, struct behavior *b)
void enqueuebadtriang (struct mesh *m, struct behavior *b, struct badtriang *badtri)
void enqueuebadtri (struct mesh *m, struct behavior *b, struct otri *enqtri, REAL angle, vertex enqapex, vertex enqorg, vertex enqdest)
badtriang * dequeuebadtriang (struct mesh *m)
int under60degrees (struct osub *sub1, struct osub *sub2)
int clockwiseseg (struct mesh *m, struct osub *thissub, struct osub *nextsub)
int counterclockwiseseg (struct mesh *m, struct osub *thissub, struct osub *nextsub)
int splitpermitted (struct mesh *m, struct osub *testsubseg, REAL iradius)
int checkseg4encroach (struct mesh *m, struct behavior *b, struct osub *testsubseg, REAL iradius)
void testtriangle (struct mesh *m, struct behavior *b, struct otri *testtri)
void makevertexmap (struct mesh *m, struct behavior *b)
enum locateresult preciselocate (struct mesh *m, struct behavior *b, vertex searchpoint, struct otri *searchtri, int stopatsubsegment)
enum locateresult locate (struct mesh *m, struct behavior *b, vertex searchpoint, struct otri *searchtri)
void insertsubseg (struct mesh *m, struct behavior *b, struct otri *tri, int subsegmark)
void flip (struct mesh *m, struct behavior *b, struct otri *flipedge)
void unflip (struct mesh *m, struct behavior *b, struct otri *flipedge)
enum insertvertexresult insertvertex (struct mesh *m, struct behavior *b, vertex newvertex, struct otri *searchtri, struct osub *splitseg, int segmentflaws, int triflaws, REAL iradius)
void triangulatepolygon (struct mesh *m, struct behavior *b, struct otri *firstedge, struct otri *lastedge, int edgecount, int doflip, int triflaws)
void deletevertex (struct mesh *m, struct behavior *b, struct otri *deltri)
void undovertex (struct mesh *m, struct behavior *b)
void vertexsort (vertex *sortarray, int arraysize)
void vertexmedian (vertex *sortarray, int arraysize, int median, int axis)
void alternateaxes (vertex *sortarray, int arraysize, int axis)
void mergehulls (struct mesh *m, struct behavior *b, struct otri *farleft, struct otri *innerleft, struct otri *innerright, struct otri *farright, int axis)
void divconqrecurse (struct mesh *m, struct behavior *b, vertex *sortarray, int vertices, int axis, struct otri *farleft, struct otri *farright)
long removeghosts (struct mesh *m, struct behavior *b, struct otri *startghost)
long divconqdelaunay (struct mesh *m, struct behavior *b)
void boundingbox (struct mesh *m, struct behavior *b)
long removebox (struct mesh *m, struct behavior *b)
long incrementaldelaunay (struct mesh *m, struct behavior *b)
void eventheapinsert (struct event **heap, int heapsize, struct event *newevent)
void eventheapify (struct event **heap, int heapsize, int eventnum)
void eventheapdelete (struct event **heap, int heapsize, int eventnum)
void createeventheap (struct mesh *m, struct event ***eventheap, struct event **events, struct event **freeevents)
int rightofhyperbola (struct mesh *m, struct otri *fronttri, vertex newsite)
REAL circletop (struct mesh *m, vertex pa, vertex pb, vertex pc, REAL ccwabc)
void check4deadevent (struct otri *checktri, struct event **freeevents, struct event **eventheap, int *heapsize)
splaynode * splay (struct mesh *m, struct splaynode *splaytree, vertex searchpoint, struct otri *searchtri)
splaynode * splayinsert (struct mesh *m, struct splaynode *splayroot, struct otri *newkey, vertex searchpoint)
splaynode * circletopinsert (struct mesh *m, struct behavior *b, struct splaynode *splayroot, struct otri *newkey, vertex pa, vertex pb, vertex pc, REAL topy)
splaynode * frontlocate (struct mesh *m, struct splaynode *splayroot, struct otri *bottommost, vertex searchvertex, struct otri *searchtri, int *farright)
long sweeplinedelaunay (struct mesh *m, struct behavior *b)
long delaunay (struct mesh *m, struct behavior *b)
long reconstruct (struct mesh *m, struct behavior *b, char *elefilename, char *areafilename, char *polyfilename, FILE *polyfile)
enum finddirectionresult finddirection (struct mesh *m, struct behavior *b, struct otri *searchtri, vertex searchpoint)
void segmentintersection (struct mesh *m, struct behavior *b, struct otri *splittri, struct osub *splitsubseg, vertex endpoint2)
int scoutsegment (struct mesh *m, struct behavior *b, struct otri *searchtri, vertex endpoint2, int newmark)
void conformingedge (struct mesh *m, struct behavior *b, vertex endpoint1, vertex endpoint2, int newmark)
void delaunayfixup (struct mesh *m, struct behavior *b, struct otri *fixuptri, int leftside)
void constrainededge (struct mesh *m, struct behavior *b, struct otri *starttri, vertex endpoint2, int newmark)
void insertsegment (struct mesh *m, struct behavior *b, vertex endpoint1, vertex endpoint2, int newmark)
void markhull (struct mesh *m, struct behavior *b)
void formskeleton (struct mesh *m, struct behavior *b, FILE *polyfile, char *polyfilename)
void infecthull (struct mesh *m, struct behavior *b)
void plague (struct mesh *m, struct behavior *b)
void regionplague (struct mesh *m, struct behavior *b, REAL attribute, REAL area)
void carveholes (struct mesh *m, struct behavior *b, REAL *holelist, int holes, REAL *regionlist, int regions)
void tallyencs (struct mesh *m, struct behavior *b)
void precisionerror ()
void splitencsegs (struct mesh *m, struct behavior *b, int triflaws)
void tallyfaces (struct mesh *m, struct behavior *b)
void splittriangle (struct mesh *m, struct behavior *b, struct badtriang *badtri)
void enforcequality (struct mesh *m, struct behavior *b)
void highorder (struct mesh *m, struct behavior *b)
char * readline (char *string, FILE *infile, char *infilename)
char * findfield (char *string)
void readnodes (struct mesh *m, struct behavior *b, char *nodefilename, char *polyfilename, FILE **polyfile)
void readholes (struct mesh *m, struct behavior *b, FILE *polyfile, char *polyfilename, REAL **hlist, int *holes, REAL **rlist, int *regions)
void finishfile (FILE *outfile, int argc, char **argv)
void writenodes (struct mesh *m, struct behavior *b, char *nodefilename, int argc, char **argv)
void numbernodes (struct mesh *m, struct behavior *b)
void writeelements (struct mesh *m, struct behavior *b, char *elefilename, int argc, char **argv)
void writepoly (struct mesh *m, struct behavior *b, char *polyfilename, REAL *holelist, int holes, REAL *regionlist, int regions, int argc, char **argv)
void writeedges (struct mesh *m, struct behavior *b, char *edgefilename, int argc, char **argv)
void writevoronoi (struct mesh *m, struct behavior *b, char *vnodefilename, char *vedgefilename, int argc, char **argv)
void writeneighbors (struct mesh *m, struct behavior *b, char *neighborfilename, int argc, char **argv)
void writeoff (struct mesh *m, struct behavior *b, char *offfilename, int argc, char **argv)
void quality_statistics (struct mesh *m, struct behavior *b)
void statistics (struct mesh *m, struct behavior *b)
int main (int argc, char **argv)

Variables

REAL splitter
REAL epsilon
REAL resulterrbound
REAL ccwerrboundA
REAL ccwerrboundB
REAL ccwerrboundC
REAL iccerrboundA
REAL iccerrboundB
REAL iccerrboundC
REAL o3derrboundA
REAL o3derrboundB
REAL o3derrboundC
unsigned long randomseed
int plus1mod3 [3] = {1, 2, 0}
int minus1mod3 [3] = {2, 0, 1}

Define Documentation

#define Absolute (  a   )     ((a) >= 0.0 ? (a) : -(a))
 

#define apex (  otri,
vertexptr   )     vertexptr = (vertex) (otri).tri[(otri).orient + 3]
 

#define areabound (  otri   )     ((REAL *) (otri).tri)[m->areaboundindex]
 

#define BADSUBSEGPERBLOCK   252
 

#define BADTRIPERBLOCK   4092
 

#define bond (  otri1,
otri2   ) 
 

Value:

(otri1).tri[(otri1).orient] = encode(otri2);                                \
  (otri2).tri[(otri2).orient] = encode(otri1)

#define deadsubseg (  sub   )     ((sub)[1] == (subseg) NULL)
 

#define deadtri (  tria   )     ((tria)[1] == (triangle) NULL)
 

#define DEADVERTEX   -32768
 

#define decode (  ptr,
otri   ) 
 

Value:

(otri).orient = (int) ((unsigned long) (ptr) & (unsigned long) 3l);         \
  (otri).tri = (triangle *)                                                   \
                  ((unsigned long) (ptr) ^ (unsigned long) (otri).orient)

#define dest (  otri,
vertexptr   )     vertexptr = (vertex) (otri).tri[minus1mod3[(otri).orient] + 3]
 

#define dissolve (  otri   )     (otri).tri[(otri).orient] = (triangle) m->dummytri
 

#define dnext (  otri1,
otri2   ) 
 

Value:

sym(otri1, otri2);                                                          \
  lprevself(otri2);

#define dnextself (  otri   ) 
 

Value:

symself(otri);                                                              \
  lprevself(otri);

#define dprev (  otri1,
otri2   ) 
 

Value:

lnext(otri1, otri2);                                                        \
  symself(otri2);

#define dprevself (  otri   ) 
 

Value:

lnextself(otri);                                                            \
  symself(otri);

#define elemattribute (  otri,
attnum   )     ((REAL *) (otri).tri)[m->elemattribindex + (attnum)]
 

#define encode (  otri   )     (triangle) ((unsigned long) (otri).tri | (unsigned long) (otri).orient)
 

#define Fast_Two_Sum (  a,
b,
x,
y   ) 
 

Value:

x = (REAL) (a + b); \
  Fast_Two_Sum_Tail(a, b, x, y)

#define Fast_Two_Sum_Tail (  a,
b,
x,
y   ) 
 

Value:

bvirt = x - a; \
  y = b - bvirt

#define FILENAMESIZE   512
 

#define FLIPSTACKERPERBLOCK   252
 

#define FREEVERTEX   2
 

#define INEXACT
 

#define infect (  otri