--- ray/src/common/objutil.c	2020/05/02 00:12:45	2.5
+++ ray/src/common/objutil.c	2021/04/07 03:02:00	2.14
@@ -1,5 +1,5 @@
 #ifndef lint
-static const char RCSid[] = "$Id: objutil.c,v 2.5 2020/05/02 00:12:45 greg Exp $";
+static const char RCSid[] = "$Id: objutil.c,v 2.14 2021/04/07 03:02:00 greg Exp $";
 #endif
 /*
  *  Basic .OBJ scene handling routines.
@@ -19,7 +19,7 @@ static const char RCSid[] = "$Id: objutil.c,v 2.5 2020
 int
 findName(const char *nm, const char **nmlist, int n)
 {
-	register int    i;
+	int	i;
 	
 	for (i = n; i-- > 0; )
 		if (!strcmp(nmlist[i], nm))
@@ -31,7 +31,7 @@ findName(const char *nm, const char **nmlist, int n)
 void
 clearSelection(Scene *sc, int set)
 {
-	Face    *f;
+	Face	*f;
 	
 	for (f = sc->flist; f != NULL; f = f->next)
 		if (set)
@@ -44,8 +44,8 @@ clearSelection(Scene *sc, int set)
 void
 selectGroup(Scene *sc, const char *gname, int invert)
 {
-	int     gid = findName(gname, (const char **)sc->grpname, sc->ngrps);
-	Face    *f;
+	int	gid = getGroupID(sc, gname);
+	Face	*f;
 
 	if (gid < 0)
 		return;
@@ -62,8 +62,8 @@ selectGroup(Scene *sc, const char *gname, int invert)
 void
 selectMaterial(Scene *sc, const char *mname, int invert)
 {
-	int     mid = findName(mname, (const char **)sc->matname, sc->nmats);
-	Face    *f;
+	int	mid = getMaterialID(sc, mname);
+	Face	*f;
 	
 	if (mid < 0)
 		return;
@@ -80,7 +80,7 @@ selectMaterial(Scene *sc, const char *mname, int inver
 void
 invertSelection(Scene *sc)
 {
-	Face    *f;
+	Face	*f;
 	
 	for (f = sc->flist; f != NULL; f = f->next)
 		f->flags ^= FACE_SELECTED;
@@ -90,8 +90,8 @@ invertSelection(Scene *sc)
 int
 numberSelected(Scene *sc)
 {
-	int     nsel = 0;
-	Face    *f;
+	int	nsel = 0;
+	Face	*f;
 	
 	for (f = sc->flist; f != NULL; f = f->next)
 		nsel += ((f->flags & FACE_SELECTED) != 0);
@@ -103,9 +103,9 @@ int
 foreachFace(Scene *sc, int (*cb)(Scene *, Face *, void *),
 			int flreq, int flexc, void *c_data)
 {
-	int     fltest = flreq | flexc;
-	int     sum = 0;
-	Face    *f;
+	const int	fltest = flreq | flexc;
+	int		sum = 0;
+	Face		*f;
 	
 	if ((sc == NULL) | (cb == NULL))
 		return(0);
@@ -123,8 +123,8 @@ foreachFace(Scene *sc, int (*cb)(Scene *, Face *, void
 static int
 remFaceTexture(Scene *sc, Face *f, void *dummy)
 {
-	int     hadTexture = 0;
-	int     i;
+	int	hadTexture = 0;
+	int	i;
 	
 	for (i = f->nv; i-- > 0; ) {
 		if (f->v[i].tid < 0)
@@ -146,8 +146,8 @@ removeTexture(Scene *sc, int flreq, int flexc)
 static int
 remFaceNormal(Scene *sc, Face *f, void *dummy)
 {
-	int     hadNormal = 0;
-	int     i;
+	int	hadNormal = 0;
+	int	i;
 	
 	for (i = f->nv; i-- > 0; ) {
 		if (f->v[i].nid < 0)
@@ -169,7 +169,8 @@ removeNormals(Scene *sc, int flreq, int flexc)
 static int
 chngFaceGroup(Scene *sc, Face *f, void *ptr)
 {
-	int     grp = *(int *)ptr;
+	int	grp = *(int *)ptr;
+
 	if (f->grp == grp)
 		return(0);
 	f->grp = grp;
@@ -180,7 +181,8 @@ chngFaceGroup(Scene *sc, Face *f, void *ptr)
 int
 changeGroup(Scene *sc, const char *gname, int flreq, int flexc)
 {
-	int     grp = findName(gname, (const char **)sc->grpname, sc->ngrps);
+	int	grp = getGroupID(sc, gname);
+
 	if (grp < 0) {
 		sc->grpname = chunk_alloc(char *, sc->grpname, sc->ngrps);
 		sc->grpname[grp=sc->ngrps++] = savqstr((char *)gname);
@@ -192,7 +194,8 @@ changeGroup(Scene *sc, const char *gname, int flreq, i
 static int
 chngFaceMaterial(Scene *sc, Face *f, void *ptr)
 {
-	int     mat = *(int *)ptr;
+	int	mat = *(int *)ptr;
+
 	if (f->mat == mat)
 		return(0);
 	f->mat = mat;
@@ -203,7 +206,8 @@ chngFaceMaterial(Scene *sc, Face *f, void *ptr)
 int
 changeMaterial(Scene *sc, const char *mname, int flreq, int flexc)
 {
-	int     mat = findName(mname, (const char **)sc->matname, sc->nmats);
+	int	mat = getMaterialID(sc, mname);
+
 	if (mat < 0) {
 		sc->matname = chunk_alloc(char *, sc->matname, sc->nmats);
 		sc->matname[mat=sc->nmats++] = savqstr((char *)mname);
@@ -248,10 +252,10 @@ norm_diff(const Normal n1, const Normal n2, double eps
 static int
 replace_vertex(Scene *sc, int prev, int repl, double eps)
 {
-	int     repl_tex[10];
-	int     repl_norm[10];
-	Face    *f, *flast=NULL;
-	int     i, j=0;
+	int	repl_tex[10];
+	int	repl_norm[10];
+	Face	*f, *flast=NULL;
+	int	i, j=0;
 					/* check to see if it's even used */
 	if (sc->vert[prev].vflist == NULL)
 		return(0);
@@ -259,13 +263,13 @@ replace_vertex(Scene *sc, int prev, int repl, double e
 	repl_tex[0] = -1;
 	for (f = sc->vert[repl].vflist; f != NULL; f = f->v[j].fnext) {
 					/* make sure prev isn't in there */
-		for (j = 0; j < f->nv; j++)
+		for (j = f->nv; j-- > 0; )
 			if (f->v[j].vid == prev)
 				return(0);
-		for (j = 0; j < f->nv; j++)
+		for (j = f->nv; j-- > 0; )
 			if (f->v[j].vid == repl)
 				break;
-		if (j >= f->nv)
+		if (j < 0)
 			goto linkerr;
 		if (f->v[j].tid < 0)
 			continue;
@@ -290,7 +294,7 @@ replace_vertex(Scene *sc, int prev, int repl, double e
 					/* get replacement normals */
 	repl_norm[0] = -1;
 	for (f = sc->vert[repl].vflist; f != NULL; f = f->v[j].fnext) {
-		for (j = 0; j < f->nv; j++)
+		for (j = f->nv; j-- > 0; )
 			if (f->v[j].vid == repl)
 				break;
 		if (f->v[j].nid < 0)
@@ -315,14 +319,14 @@ replace_vertex(Scene *sc, int prev, int repl, double e
 	}
 					/* replace occurrences of vertex */
 	for (f = sc->vert[prev].vflist; f != NULL; f = f->v[j].fnext) {
-		for (j = 0; j < f->nv; j++)
+		for (j = f->nv; j-- > 0; )
 			if (f->v[j].vid == prev)
 				break;
-		if (j >= f->nv)
+		if (j < 0)
 			goto linkerr;
 		/* XXX doesn't allow for multiple references to prev in face */
 		f->v[j].vid = repl;     /* replace vertex itself */
-		if (faceArea(sc, f, NULL) <= FTINY)
+		if (faceArea(sc, f, NULL) <= FTINY*FTINY)
 			f->flags |= FACE_DEGENERATE;
 		if (f->v[j].tid >= 0)   /* replace texture if appropriate */
 			for (i = 0; repl_tex[i] >= 0; i++) {
@@ -360,12 +364,12 @@ linkerr:
 int
 coalesceVertices(Scene *sc, double eps)
 {
-	int     nelim = 0;
-	LUTAB   myLookup;
-	LUENT   *le;
-	char    vertfmt[32], vertbuf[64];
-	double  d;
-	int     i;
+	int	nelim = 0;
+	LUTAB	myLookup;
+	LUENT	*le;
+	char	vertfmt[32], vertbuf[64];
+	double	d;
+	int	i;
 	
 	if (eps >= 1.)
 		return(0);
@@ -412,11 +416,11 @@ coalesceVertices(Scene *sc, double eps)
 int
 findDuplicateFaces(Scene *sc)
 {
-	int     nchecked = 0;
-	int     nfound = 0;
-	Face    *f, *f1;
-	int     vid;
-	int     i, j;
+	int	nchecked = 0;
+	int	nfound = 0;
+	Face	*f, *f1;
+	int	vid;
+	int	i, j;
 						/* start fresh */
 	for (f = sc->flist; f != NULL; f = f->next)
 		f->flags &= ~FACE_DUPLICATE;
@@ -432,10 +436,10 @@ findDuplicateFaces(Scene *sc)
 						/* look for duplicates */
 		for (f1 = sc->vert[vid].vflist; f1 != NULL;
 					f1 = f1->v[j].fnext) {
-			for (j = 0; j < f1->nv; j++)
+			for (j = f1->nv; j-- > 0; )
 				if (f1->v[j].vid == vid)
 					break;
-			if (j >= f1->nv)
+			if (j < 0)
 				break;		/* missing link! */
 			if (f1 == f)
 				continue;       /* shouldn't happen */
@@ -460,6 +464,8 @@ findDuplicateFaces(Scene *sc)
 			++nfound;
 		}
 	}
+	if (verbose)
+		fprintf(stderr, "Found %d duplicate faces\n", nfound);
 	return(nfound);
 }
 
@@ -467,10 +473,10 @@ findDuplicateFaces(Scene *sc)
 int
 deleteFaces(Scene *sc, int flreq, int flexc)
 {
-	int     fltest = flreq | flexc;
-	int     orig_nfaces = sc->nfaces;
-	Face    fhead;
-	Face    *f, *ftst;
+	const int	fltest = flreq | flexc;
+	int		orig_nfaces = sc->nfaces;
+	Face		fhead;
+	Face		*f, *ftst;
 	
 	fhead.next = sc->flist;
 	f = &fhead;
@@ -486,10 +492,10 @@ deleteFaces(Scene *sc, int flreq, int flexc)
 					continue;
 				}
 				while (vf != NULL) {
-					for (j = 0; j < vf->nv; j++)
+					for (j = vf->nv; j-- > 0; )
 						if (vf->v[j].vid == vid)
 							break;
-					if (j >= vf->nv)
+					if (j < 0)
 						break;  /* error */
 					if (vf->v[j].fnext == ftst) {
 						vf->v[j].fnext =
@@ -547,6 +553,19 @@ addComment(Scene *sc, const char *comment)
 	sc->descr[sc->ndescr++] = savqstr((char *)comment);
 }
 
+/* Find index for comment containing the given string (starting from n) */
+int
+findComment(Scene *sc, const char *match, int n)
+{
+	if (n >= sc->ndescr)
+		return(-1);
+	n *= (n > 0);
+	while (n < sc->ndescr)
+		if (strstr(sc->descr[n], match) != NULL)
+			return(n);
+	return(-1);
+}
+
 /* Clear comments */
 void
 clearComments(Scene *sc)
@@ -573,10 +592,10 @@ add2facelist(Scene *sc, Face *f, int i)
 	for ( ; ; ) {				/* else find position */
 		if (fp == f)
 			return;			/* already in list */
-		for (j = 0; j < fp->nv; j++)
+		for (j = fp->nv; j-- > 0; )
 			if (fp->v[j].vid == vid)
 				break;
-		if (j >= fp->nv)
+		if (j < 0)
 			error(CONSISTENCY, "Link error in add2facelist()");
 		if (fp->v[j].fnext == NULL)
 			break;			/* reached the end */
@@ -589,7 +608,7 @@ add2facelist(Scene *sc, Face *f, int i)
 Scene *
 newScene(void)
 {
-	Scene   *sc = (Scene *)ecalloc(1, sizeof(Scene));
+	Scene	*sc = (Scene *)ecalloc(1, sizeof(Scene));
 						/* default group & material */
 	sc->grpname = chunk_alloc(char *, sc->grpname, sc->ngrps);
 	sc->grpname[sc->ngrps++] = savqstr("DEFAULT_GROUP");
@@ -625,7 +644,7 @@ addTexture(Scene *sc, double u, double v)
 int
 addNormal(Scene *sc, double xn, double yn, double zn)
 {
-	FVECT   nrm;
+	FVECT	nrm;
 
 	nrm[0] = xn; nrm[1] = yn; nrm[2] = zn;
 	if (normalize(nrm) == .0)
@@ -639,7 +658,7 @@ addNormal(Scene *sc, double xn, double yn, double zn)
 void
 setGroup(Scene *sc, const char *nm)
 {
-	sc->lastgrp = findName(nm, (const char **)sc->grpname, sc->ngrps);
+	sc->lastgrp = getGroupID(sc, nm);
 	if (sc->lastgrp >= 0)
 		return;
 	sc->grpname = chunk_alloc(char *, sc->grpname, sc->ngrps);
@@ -650,7 +669,7 @@ setGroup(Scene *sc, const char *nm)
 void
 setMaterial(Scene *sc, const char *nm)
 {
-	sc->lastmat = findName(nm, (const char **)sc->matname, sc->nmats);
+	sc->lastmat = getMaterialID(sc, nm);
 	if (sc->lastmat >= 0)
 		return;
 	sc->matname = chunk_alloc(char *, sc->matname, sc->nmats);
@@ -661,8 +680,8 @@ setMaterial(Scene *sc, const char *nm)
 Face *
 addFace(Scene *sc, VNDX vid[], int nv)
 {
-	Face    *f;
-	int     i;
+	Face	*f;
+	int	i;
 	
 	if (nv < 3)
 		return(NULL);
@@ -690,15 +709,16 @@ addFace(Scene *sc, VNDX vid[], int nv)
 	sc->flist = f;
 	sc->nfaces++;
 						/* check face area */
-	if (!(f->flags & FACE_DEGENERATE) && faceArea(sc, f, NULL) <= FTINY)
+	if (!(f->flags & FACE_DEGENERATE) && faceArea(sc, f, NULL) <= FTINY*FTINY)
 		f->flags |= FACE_DEGENERATE;
 	return(f);
 }
 
-/* Duplicate a scene */
+/* Duplicate a scene, optionally selecting faces */
 Scene *
-dupScene(const Scene *osc)
+dupScene(const Scene *osc, int flreq, int flexc)
 {
+	int     	fltest = flreq | flexc;
 	Scene		*sc;
 	const Face      *fo;
 	Face		*f;
@@ -747,6 +767,8 @@ dupScene(const Scene *osc)
 		sc->nnorms = osc->nnorms;
 	}
 	for (fo = osc->flist; fo != NULL; fo = fo->next) {
+		if ((fo->flags & fltest) != flreq)
+			continue;
 		f = (Face *)emalloc(sizeof(Face) +
 				sizeof(VertEnt)*(fo->nv-3));
 		memcpy((void *)f, (const void *)fo, sizeof(Face) +
@@ -757,13 +779,94 @@ dupScene(const Scene *osc)
 		sc->flist = f;
 		sc->nfaces++;
 	}
+	deleteUnreferenced(sc);		/* jetsam */
 	return(sc);
 }
 
+/* Add one scene to another, not checking for redundancies */
+int
+addScene(Scene *scdst, const Scene *scsrc)
+{
+	VNDX		my_vlist[4];
+	int		*vert_map = NULL;
+	int		*norm_map = NULL;
+	int		*tex_map = NULL;
+	VNDX		*vlist = my_vlist;
+	int		vllen = sizeof(my_vlist)/sizeof(VNDX);
+	int		cur_mat = 0;
+	int		cur_grp = 0;
+	int		fcnt = 0;
+	const Face	*f;
+	int		i;
+
+	if ((scdst == NULL) | (scsrc == NULL))
+		return(-1);
+	if (scsrc->nfaces <= 0)
+		return(0);
+					/* map vertices */
+	vert_map = (int *)emalloc(sizeof(int *)*scsrc->nverts);
+	for (i = 0; i < scsrc->nverts; i++) {
+		const Vertex	*v = scsrc->vert + i;
+		if (v->vflist == NULL) {
+			vert_map[i] = -1;
+			continue;
+		}
+		vert_map[i] = addVertex(scdst, v->p[0], v->p[1], v->p[2]);
+	}
+	if (scsrc->ntex > 0)		/* map texture coords */
+		tex_map = (int *)emalloc(sizeof(int *)*scsrc->ntex);
+	for (i = 0; i < scsrc->ntex; i++) {
+		const TexCoord	*t = scsrc->tex + i;
+		tex_map[i] = addTexture(scdst, t->u, t->v);
+	}
+	if (scsrc->nnorms > 0)		/* map normals */
+		norm_map = (int *)emalloc(sizeof(int *)*scsrc->nnorms);
+	for (i = 0; i < scsrc->nnorms; i++) {
+		const float	*n = scsrc->norm[i];
+		norm_map[i] = addNormal(scdst, n[0], n[1], n[2]);
+	}
+					/* add faces */
+	scdst->lastgrp = scdst->lastmat = 0;
+	for (f = scsrc->flist; f != NULL; f = f->next) {
+		if (f->grp != cur_grp)
+			setGroup(scdst, scsrc->grpname[cur_grp = f->grp]);
+		if (f->mat != cur_mat)
+			setMaterial(scdst, scsrc->matname[cur_mat = f->mat]);
+		if (f->nv > vllen) {
+			if (vlist == my_vlist)
+				vlist = (VNDX *)emalloc(
+						sizeof(VNDX)*(vllen = f->nv));
+			else
+				vlist = (VNDX *)erealloc((char *)vlist,
+						sizeof(VNDX)*(vllen = f->nv));
+		}
+		memset(vlist, 0xff, sizeof(VNDX)*f->nv);
+		for (i = f->nv; i-- > 0; ) {
+			if (f->v[i].vid >= 0)
+				vlist[i][0] = vert_map[f->v[i].vid];
+			if (f->v[i].tid >= 0)
+				vlist[i][1] = tex_map[f->v[i].tid];
+			if (f->v[i].nid >= 0)
+				vlist[i][2] = norm_map[f->v[i].nid];
+		}
+		fcnt += (addFace(scdst, vlist, f->nv) != NULL);
+	}
+					/* clean up */
+	if (vlist != my_vlist) efree((char *)vlist);
+	if (norm_map != NULL) efree((char *)norm_map);
+	if (tex_map != NULL) efree((char *)tex_map);
+	efree((char *)vert_map);
+	return(fcnt);
+}
+
+#define MAXAC	100
+
 /* Transform entire scene */
 int
 xfScene(Scene *sc, int xac, char *xav[])
 {
+	char	comm[24+MAXAC*8];
+	char	*cp;
 	XF	myxf;
 	FVECT	vec;
 	int	i;
@@ -786,11 +889,18 @@ xfScene(Scene *sc, int xac, char *xav[])
 		vec[0] /= myxf.sca; vec[1] /= myxf.sca; vec[2] /= myxf.sca;
 		VCOPY(sc->norm[i], vec);
 	}
+					/* add comment */
+	cp = strcpy(comm, "Transformed by:");
+	for (i = 0; i < xac; i++) {
+		while (*cp) cp++;
+		*cp++ = ' ';
+		strcpy(cp, xav[i]);
+	}
+	addComment(sc, comm);
 	return(xac);			/* all done */
 }
 
 /* Ditto, using transform string rather than pre-parsed words */
-#define MAXAC	100
 int
 xfmScene(Scene *sc, const char *xfm)
 {
@@ -805,7 +915,7 @@ xfmScene(Scene *sc, const char *xfm)
 	if (!*xfm)
 		return(0);
 					/* parse string into words */
-	xav[0] = strcpy((char *)malloc(strlen(xfm)+1), xfm);
+	xav[0] = strcpy((char *)emalloc(strlen(xfm)+1), xfm);
 	xac = 1; i = 0;
 	for ( ; ; ) {
 		while (!isspace(xfm[++i]))
@@ -823,10 +933,103 @@ xfmScene(Scene *sc, const char *xfm)
 	}
 	xav[xac] = NULL;
 	i = xfScene(sc, xac, xav);
-	free(xav[0]);
+	efree((char *)xav[0]);
 	return(i);
 }
 #undef MAXAC
+
+/* Delete unreferenced vertices, normals, texture coords */
+void
+deleteUnreferenced(Scene *sc)
+{
+	int     *vmap;
+	Face    *f;
+	int     nused, i;
+						/* allocate index map */
+	if (!sc->nverts)
+		return;
+	i = sc->nverts;
+	if (sc->ntex > i)
+		i = sc->ntex;
+	if (sc->nnorms > i)
+		i = sc->nnorms;
+	vmap = (int *)emalloc(sizeof(int)*i);
+						/* remap positions */
+	for (i = nused = 0; i < sc->nverts; i++) {
+		if (sc->vert[i].vflist == NULL) {
+			vmap[i] = -1;
+			continue;
+		}
+		if (nused != i)
+			sc->vert[nused] = sc->vert[i];
+		vmap[i] = nused++;
+	}
+	if (nused == sc->nverts)
+		goto skip_pos;
+	sc->vert = (Vertex *)erealloc((char *)sc->vert,
+				sizeof(Vertex)*(nused+(CHUNKSIZ-1)));
+	sc->nverts = nused;
+	for (f = sc->flist; f != NULL; f = f->next)
+		for (i = f->nv; i--; )
+			if ((f->v[i].vid = vmap[f->v[i].vid]) < 0)
+				error(CONSISTENCY,
+					"Link error in del_unref_verts()");
+skip_pos:
+						/* remap texture coord's */
+	if (!sc->ntex)
+		goto skip_tex;
+	memset((void *)vmap, 0, sizeof(int)*sc->ntex);
+	for (f = sc->flist; f != NULL; f = f->next)
+		for (i = f->nv; i--; )
+			if (f->v[i].tid >= 0)
+				vmap[f->v[i].tid] = 1;
+	for (i = nused = 0; i < sc->ntex; i++) {
+		if (!vmap[i])
+			continue;
+		if (nused != i)
+			sc->tex[nused] = sc->tex[i];
+		vmap[i] = nused++;
+	}
+	if (nused == sc->ntex)
+		goto skip_tex;
+	sc->tex = (TexCoord *)erealloc((char *)sc->tex,
+				sizeof(TexCoord)*(nused+(CHUNKSIZ-1)));
+	sc->ntex = nused;
+	for (f = sc->flist; f != NULL; f = f->next)
+		for (i = f->nv; i--; )
+			if (f->v[i].tid >= 0)
+				f->v[i].tid = vmap[f->v[i].tid];
+skip_tex:
+						/* remap normals */
+	if (!sc->nnorms)
+		goto skip_norms;
+	memset((void *)vmap, 0, sizeof(int)*sc->nnorms);
+	for (f = sc->flist; f != NULL; f = f->next)
+		for (i = f->nv; i--; )
+			if (f->v[i].nid >= 0)
+				vmap[f->v[i].nid] = 1;
+	for (i = nused = 0; i < sc->nnorms; i++) {
+		if (!vmap[i])
+			continue;
+		if (nused != i)
+			memcpy((void *)sc->norm[nused],
+					(void *)sc->norm[i],
+					sizeof(Normal));
+		vmap[i] = nused++;
+	}
+	if (nused == sc->nnorms)
+		goto skip_norms;
+	sc->norm = (Normal *)erealloc((char *)sc->norm,
+				sizeof(Normal)*(nused+(CHUNKSIZ-1)));
+	sc->nnorms = nused;
+	for (f = sc->flist; f != NULL; f = f->next)
+		for (i = f->nv; i--; )
+			if (f->v[i].nid >= 0)
+				f->v[i].nid = vmap[f->v[i].nid];
+skip_norms:
+						/* clean up */
+	efree((char *)vmap);
+}
 
 /* Free a scene */
 void