--- ray/src/common/objutil.c	2020/04/02 20:44:15	2.2
+++ ray/src/common/objutil.c	2021/03/03 18:53:08	2.13
@@ -1,5 +1,5 @@
 #ifndef lint
-static const char RCSid[] = "$Id: objutil.c,v 2.2 2020/04/02 20:44:15 greg Exp $";
+static const char RCSid[] = "$Id: objutil.c,v 2.13 2021/03/03 18:53:08 greg Exp $";
 #endif
 /*
  *  Basic .OBJ scene handling routines.
@@ -19,7 +19,7 @@ static const char RCSid[] = "$Id: objutil.c,v 2.2 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))
@@ -44,7 +44,7 @@ clearSelection(Scene *sc, int set)
 void
 selectGroup(Scene *sc, const char *gname, int invert)
 {
-	int     gid = findName(gname, (const char **)sc->grpname, sc->ngrps);
+	int     gid = getGroupID(sc, gname);
 	Face    *f;
 
 	if (gid < 0)
@@ -62,7 +62,7 @@ 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);
+	int     mid = getMaterialID(sc, mname);
 	Face    *f;
 	
 	if (mid < 0)
@@ -180,7 +180,7 @@ 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);
@@ -203,7 +203,7 @@ 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);
@@ -259,13 +259,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 +290,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 +315,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++) {
@@ -432,10 +432,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 +460,8 @@ findDuplicateFaces(Scene *sc)
 			++nfound;
 		}
 	}
+	if (verbose)
+		fprintf(stderr, "Found %d duplicate faces\n", nfound);
 	return(nfound);
 }
 
@@ -486,10 +488,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 +549,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 +588,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 */
@@ -599,10 +614,107 @@ newScene(void)
 	return(sc);
 }
 
-/* Duplicate a scene */
+/* Add a vertex to a scene */
+int
+addVertex(Scene *sc, double x, double y, double z)
+{
+	sc->vert = chunk_alloc(Vertex, sc->vert, sc->nverts);
+	sc->vert[sc->nverts].p[0] = x;
+	sc->vert[sc->nverts].p[1] = y;
+	sc->vert[sc->nverts].p[2] = z;
+	sc->vert[sc->nverts].vflist = NULL;
+	return(sc->nverts++);
+}
+
+/* Add a texture coordinate to a scene */
+int
+addTexture(Scene *sc, double u, double v)
+{
+	sc->tex = chunk_alloc(TexCoord, sc->tex, sc->ntex);
+	sc->tex[sc->ntex].u = u;
+	sc->tex[sc->ntex].v = v;
+	return(sc->ntex++);
+}
+
+/* Add a surface normal to a scene */
+int
+addNormal(Scene *sc, double xn, double yn, double zn)
+{
+	FVECT   nrm;
+
+	nrm[0] = xn; nrm[1] = yn; nrm[2] = zn;
+	if (normalize(nrm) == .0)
+		return(-1);
+	sc->norm = chunk_alloc(Normal, sc->norm, sc->nnorms);
+	VCOPY(sc->norm[sc->nnorms], nrm);
+	return(sc->nnorms++);
+}
+
+/* Set current (last) group */
+void
+setGroup(Scene *sc, const char *nm)
+{
+	sc->lastgrp = getGroupID(sc, nm);
+	if (sc->lastgrp >= 0)
+		return;
+	sc->grpname = chunk_alloc(char *, sc->grpname, sc->ngrps);
+	sc->grpname[sc->lastgrp=sc->ngrps++] = savqstr((char *)nm);
+}
+
+/* Set current (last) material */
+void
+setMaterial(Scene *sc, const char *nm)
+{
+	sc->lastmat = getMaterialID(sc, nm);
+	if (sc->lastmat >= 0)
+		return;
+	sc->matname = chunk_alloc(char *, sc->matname, sc->nmats);
+	sc->matname[sc->lastmat=sc->nmats++] = savqstr((char *)nm);
+}
+
+/* Add new face to a scene */
+Face *
+addFace(Scene *sc, VNDX vid[], int nv)
+{
+	Face    *f;
+	int     i;
+	
+	if (nv < 3)
+		return(NULL);
+	f = (Face *)emalloc(sizeof(Face)+sizeof(VertEnt)*(nv-3));
+	f->flags = 0;
+	f->nv = nv;
+	f->grp = sc->lastgrp;
+	f->mat = sc->lastmat;
+	for (i = 0; i < nv; i++) {		/* add each vertex */
+		int     j;
+		f->v[i].vid = vid[i][0];
+		f->v[i].tid = vid[i][1];
+		f->v[i].nid = vid[i][2];
+		f->v[i].fnext = NULL;
+		for (j = i; j-- > 0; )
+			if (f->v[j].vid == vid[i][0])
+				break;
+		if (j < 0) {			/* first occurrence? */
+			f->v[i].fnext = sc->vert[vid[i][0]].vflist;
+			sc->vert[vid[i][0]].vflist = f;
+		} else if (nv == 3)		/* degenerate triangle? */
+			f->flags |= FACE_DEGENERATE;
+	}
+	f->next = sc->flist;			/* push onto face list */
+	sc->flist = f;
+	sc->nfaces++;
+						/* check face area */
+	if (!(f->flags & FACE_DEGENERATE) && faceArea(sc, f, NULL) <= FTINY*FTINY)
+		f->flags |= FACE_DEGENERATE;
+	return(f);
+}
+
+/* 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;
@@ -651,6 +763,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) +
@@ -661,26 +775,66 @@ dupScene(const Scene *osc)
 		sc->flist = f;
 		sc->nfaces++;
 	}
+	deleteUnreferenced(sc);		/* jetsam */
 	return(sc);
 }
 
-/* Transform entire scene */
 #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;
+
+	if ((sc == NULL) | (xac <= 0) | (xav == NULL))
+		return(0);
+					/* compute matrix */
+	if (xf(&myxf, xac, xav) < xac)
+		return(0);
+					/* transform vertices */
+	for (i = 0; i < sc->nverts; i++) {
+		VCOPY(vec, sc->vert[i].p);
+		multp3(vec, vec, myxf.xfm);
+		VCOPY(sc->vert[i].p, vec);
+	}
+					/* transform normals */
+	for (i = 0; i < sc->nnorms; i++) {
+		VCOPY(vec, sc->norm[i]);
+		multv3(vec, vec, myxf.xfm);
+		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 */
+int
 xfmScene(Scene *sc, const char *xfm)
 {
 	char	*xav[MAXAC+1];
 	int	xac, i;
-	XF	myxf;
-	FVECT	vec;
 
 	if ((sc == NULL) | (xfm == NULL))
 		return(0);
-	while (isspace(*xfm))		/* find first word */
+					/* skip spaces at beginning */
+	while (isspace(*xfm))
 		xfm++;
 	if (!*xfm)
 		return(0);
-					/* break into words for xf() */
+					/* parse string into words */
 	xav[0] = strcpy((char *)malloc(strlen(xfm)+1), xfm);
 	xac = 1; i = 0;
 	for ( ; ; ) {
@@ -691,33 +845,111 @@ xfmScene(Scene *sc, const char *xfm)
 			xav[0][i++] = '\0';
 		if (!xfm[i])
 			break;
-		if (xac >= MAXAC-1)
-			goto bad_xform;
+		if (xac >= MAXAC-1) {
+			free(xav[0]);
+			return(0);
+		}
 		xav[xac++] = xav[0] + i;
 	}
 	xav[xac] = NULL;
-	if (xf(&myxf, xac, xav) < xac)
-		goto bad_xform;
+	i = xfScene(sc, xac, xav);
 	free(xav[0]);
-					/* transform vertices */
-	for (i = 0; i < sc->nverts; i++) {
-		VCOPY(vec, sc->vert[i].p);
-		multp3(vec, vec, myxf.xfm);
-		VCOPY(sc->vert[i].p, vec);
+	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++;
 	}
-					/* transform normals */
-	for (i = 0; i < sc->nnorms; i++) {
-		VCOPY(vec, sc->norm[i]);
-		multv3(vec, vec, myxf.xfm);
-		vec[0] /= myxf.sca; vec[1] /= myxf.sca; vec[2] /= myxf.sca;
-		VCOPY(sc->norm[i], vec);
+	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++;
 	}
-	return xac;			/* finito */
-bad_xform:
-	free(xav[0]);
-	return(0);
+	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);
 }
-#undef MAXAC
 
 /* Free a scene */
 void