#define	MYPI	3.14159265358979323846264

/* two dimension */
typedef struct Point2	Point2;
typedef double		Rot2[2][2];
typedef struct Frame2	Frame2;
typedef struct sobj2	Sobj2;
typedef struct ssobj2	Ssobj2;
typedef struct snode2	Snode2;
typedef struct sprim2	Sprim2;	
typedef struct sdist2	Sdist2;

/* three dimensional */
typedef struct Point3	Point3;
typedef double		Rot3[3][3];
typedef struct Frame3	Frame3;
typedef struct sobj3	Sobj3;
typedef struct ssobj3	Ssobj3;
typedef struct snode3	Snode3;
typedef struct sprim3	Sprim3;	
typedef struct sdist3	Sdist3;

/*
 * types of snode2 and snode3
 */
enum {
	SNODE,		/* left != 0 && right != 0 */
	SSOBJ,		/* left == 0 && right != 0 */
	SLEAF,		/* left == 0 && right == 0 */
};

struct Point2 {
	double	x, y;
};

struct Frame2 {
	Rot2	r;
	Point2	p;
};

struct sobj2 {
	int n;
	Snode2 *p;
};

struct snode2 {
	Point2	p;
	double	r;
	Sprim2	*prim;
	Snode2	*left, *right;	/* right is also used to point to ssobj2 */
};

struct ssobj2 {
	Frame2	f;
	char	ignore;
	Snode2	*p;
	void	*a;
};

struct sprim2 {
	int	ref;
	Point2	*p;
	int	n;
	double	r;
	void	*a;
};

struct sdist2 {
	double	d;
	Point2	p[2];
	Ssobj2	*sobj[2];
	Frame2	f[2];
	Sprim2	*prim[2];
	int	n, npp;
};

struct Point3 {
	double	x, y, z;
};

struct Frame3 {
	Rot3	r;
	Point3	p;
};

struct sobj3 {
	int	n;
	Snode3	*p;
};

struct ssobj3 {
	Frame3	f;
	char	ignore;
	Snode3	*p;
	void	*a;
};

struct snode3 {
	Point3	p;
	double	r;
	Sprim3	*prim;
	Snode3	*left, *right;	/* right is also used to point to sobj3 */
};

struct sprim3 {
	int	ref;
	Point3	*p;
	int	n;
	double	r;
	void	*a;
};


struct sdist3 {
	double	d;
	Point3 	p[2];
	Ssobj3	*sobj[2];
	Frame3	f[2];
	Sprim3	*prim[2];
	int	n, npp;
};

extern int	snoline2;
extern int	snopoly3;

/* misc.c */
extern double	frand(void);

/* point2.c */
extern Point2	point2(double x, double y);
extern Point2	padd2(Point2, Point2);
extern Point2	psub2(Point2, Point2);
extern Point2	pmul2(double s, Point2);
extern Point2	pmax2(Point2, Point2);
extern Point2	pmin2(Point2, Point2);
extern int	peq2(Point2, Point2);
extern double	pdot2(Point2, Point2);
extern double	pabs2(Point2 p);
extern Point2	prand2(void);
extern Point2	pmid2(double s, Point2, Point2);
extern Point2	punit2(Point2);

/* rot2.c */
extern Point2	rmap2(Rot2 r, Point2 p);
extern Point2	rimap2(Rot2 r, Point2 p);
extern void	rinv2(Rot2 d, Rot2 s);
extern void	rmul2(Rot2 d, Rot2 s1, Rot2 s2);
extern void	rrot2(Rot2 d, double t);
extern void	rrand2(Rot2 d);
extern Rot2	irot2;

/* frame2.c */
extern void	ftrans2(Frame2 *d, Point2 p);
extern void	frot2(Frame2 *d, double t);
extern void	frame2(Frame2 *d, Point2 p, double t);
extern void	finv2(Frame2 *d, Frame2 *s);
extern void	fmul2(Frame2 *d, Frame2 *s1, Frame2 *s2);
extern Point2	fmap2(Frame2 *f, Point2 p);
extern Point2	fimap2(Frame2 *f, Point2 p);
extern void	frand2(Frame2 *f);
extern Frame2	iframe2[1];

/* bezier2.c */
extern Point2	beval2(Point2 b[4], double t);
extern double	bldev2(Point2 b[4]);
extern void	bsubdiv2(Point2 b[4],Point2 b0[4], Point2 b1[4]);

/* dist2.c */
extern double	dpp2(Point2, Point2);
extern double	dpl2(Point2, Point2[2]);
extern double	dll2(Point2[2], Point2[2]);
extern void	vpp2(Point2[2], Point2, Point2);
extern void	vpl2(Point2[2], Point2, Point2[2]);
extern void	vll2(Point2[2], Point2[2], Point2[2]);

/* sphere2.c */
extern void	bgnsobj2(void);
extern Sobj2	*endsobj2(void);
extern void	spoint2(Point2 p, double r, void *a);
extern void	sline2(Point2 p[2], double r, double rmax, void *a);
extern void	sbezier2(Point2 p[4], double r, double ld,
			double rmax, void *a);
extern Ssobj2	*ssobj2(Sobj2 *o, Frame2 *f, void *a);
extern void	sobjfree2(Sobj2 *o);

extern Sdist2	sdist2(Sobj2 *o1, Frame2 *f1, Sobj2 *o2, Frame2 *f2,
			double err);
extern Sdist2	scollide2(Sobj2 *o1, Frame2 *f1, Sobj2 *o2, Frame2 *f2);
extern int	scontact2(Sdist2 *d, int n, Sobj2 *o1, Frame2 *f1,
			Sobj2 *o2, Frame2 *f2, double cut);


/* point3.c */
extern Point3	point3(double x, double y, double z);
extern Point3	padd3(Point3, Point3);
extern Point3	psub3(Point3, Point3);
extern Point3	pmul3(double s, Point3);
extern Point3	pmax3(Point3, Point3);
extern Point3	pmin3(Point3, Point3);
extern int	peq3(Point3, Point3);
extern double	pdot3(Point3, Point3);
extern Point3	pcross3(Point3, Point3);
extern double	pabs3(Point3 p);
extern Point3	pmid3(double s, Point3, Point3);
extern Point3	prand3(void);
extern Point3	punit3(Point3);

/* rot3.c */
extern Point3	rmap3(Rot3 r, Point3 p);
extern Point3	rimap3(Rot3 r, Point3 p);
extern void	rinv3(Rot3 d, Rot3 s);
extern void	rmul3(Rot3 d, Rot3 s1, Rot3 s2);
extern void	rrot3(Rot3 d, Point3 w, double t);
extern void	rrand3(Rot3 d);
extern Rot3	irot3;

/* frame3.c */
extern void	ftrans3(Frame3 *d, Point3 p);
extern void	frot3(Frame3 *d, Point3 w, double t);
extern void	frame3(Frame3 *d, Point3 p, Point3 w, double t);
extern void	finv3(Frame3 *d, Frame3 *s);
extern void	fmul3(Frame3 *d, Frame3 *s1, Frame3 *s3);
extern Point3	fmap3(Frame3 *f, Point3 p);
extern Point3	fimap3(Frame3 *f, Point3 p);
extern void	frand3(Frame3 *f);
extern Frame3	iframe3[1];

/* dist3.c */
extern double	dpp3(Point3, Point3);
extern double	dpl3(Point3, Point3[2]);
extern double	dll3(Point3[2], Point3[2]);
extern double	dist3(Point3 *, int n, Point3 *, int m);
extern void	vpp3(Point3[2], Point3, Point3);
extern void	vpl3(Point3[2], Point3, Point3[2]);
extern void	vll3(Point3[2], Point3[2], Point3[2]);
extern void	vdist3(Point3[2], Point3 *, int n, Point3 *, int m);


/* gilbert C version */
extern void	gilbert(int nvi, int nvj, double (*z)[3], double (*zj)[3],
			double zisol[3], double zjsol[3]);

/* sphere3.c */
extern void	bgnsobj3(void);
extern void	spoint3(Point3 p, double r, void *a);
extern void	sline3(Point3[2], double r, double rmax, void *a);
extern void	stri3(Point3[3], double r, double rmax, void *a);
extern void	spoly3(Point3 *p, int n, double r, double rmax, void *a);
extern Ssobj3	*ssobj3(Sobj3 *o, Frame3 *f, void *a);
extern Sobj3	*endsobj3(void);
extern void	sobjfree3(Sobj3 *o);

extern Sdist3	sdist3(Sobj3 *o0, Frame3 *f0,
			Sobj3 *o1, Frame3 *f1, double err);
extern Sdist3	scollide3(Sobj3 *o0, Frame3 *f0,
			Sobj3 *o1, Frame3 *f1);
extern int	scontact3(Sdist3 *d, int n, Sobj3 *o0, Frame3 *f0,
			Sobj3 *o1, Frame3 *f1, double cut);

#define PC(p,i)	(((double *)&(p))[(i)])