/****************************************************************************\ Copyright 1995 The University of North Carolina at Chapel Hill. All Rights Reserved. Permission to use, copy, modify and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice and the following three paragraphs appear in all copies. IN NO EVENT SHALL THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF NORTH CAROLINA HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. Permission to use, copy, modify and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice and the following three paragraphs appear in all copies. THE UNIVERSITY OF NORTH CAROLINA SPECIFICALLY DISCLAIM ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF NORTH CAROLINA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. The authors may be contacted via: US Mail: Jonathan Cohen Amitabh Varshney Department of Computer Science Department of Computer Science Sitterson Hall, CB #3175 State University of New York University of N. Carolina Stony Brook, NY 11794-4400, USA Chapel Hill, NC 27599-3175 Phone: (919)962-1749 Phone: (516)632-8446 EMail: cohenj@cs.unc.edu varshney@cs.sunysb.edu \****************************************************************************/ /*****************************************************************************\ plysimplify.c -- Description : Simplify an indexed, oriented PLY object with normals Jonathan Cohen - August 1995 ---------------------------------------------------------------------------- $Source: /cvs/RenderPark/SE/Simplify/plysimplify.c,v $ $Revision: 1.1.1.1 $ $Date: 2000/04/06 15:35:32 $ $Author: philippe $ $Locker: $ \*****************************************************************************/ /*----------------------------- Local Includes -----------------------------*/ #include #include #include #include #include #include #include #include /*----------------------------- Local Constants -----------------------------*/ #define BBOX_PERCENT 0 #define ABSOLUTE_DISTANCE 1 /*------------------------------ Local Macros -------------------------------*/ /*------------------------------- Local Types -------------------------------*/ /* user's vertex and face definitions for a polygonal object */ typedef struct PlyVertex { Point coord; /* coordinates of vertex */ Vector normal; /* normals of vertex */ #ifdef VERTEX_EPSILONS float epsilon; /* per-vertex epsilon approximation distance */ #endif unsigned char nfaces; /* number of face indices in list */ int *faces; /* face index list */ unsigned char nedges; /* number of edge indices in list */ int *edges; /* edge index list */ void *other_props; /* other properties */ } PlyVertex; typedef struct PlyFace { unsigned char nverts; /* number of vertex indices in list */ int *verts; /* vertex index list */ unsigned char nedges; /* number of edge indices in list */ int *edges; /* edge index list */ } PlyFace; typedef struct PlyEdge { int vert1, vert2; /* vertex indices */ int face1, face2; /* face indices */ } PlyEdge; /*------------------------ Local Function Prototypes ------------------------*/ void compute_bbox_epsilon(Surface *model, double bbox_epsilon, double *epsilon); void get_options(int argc, char *argv[]); void read_file(Surface *model); void write_file(Surface *model); void init_defaults(); void usage(char *progname); /*------------------------------ Local Globals ------------------------------*/ PlyProperty vert_props[] = { /* list of property information for a vertex */ {"x", PLY_FLOAT, PLY_DOUBLE, offsetof(PlyVertex,coord[X]), 0, 0, 0, 0}, {"y", PLY_FLOAT, PLY_DOUBLE, offsetof(PlyVertex,coord[Y]), 0, 0, 0, 0}, {"z", PLY_FLOAT, PLY_DOUBLE, offsetof(PlyVertex,coord[Z]), 0, 0, 0, 0}, {"nx", PLY_FLOAT, PLY_DOUBLE, offsetof(PlyVertex,normal[X]), 0, 0, 0, 0}, {"ny", PLY_FLOAT, PLY_DOUBLE, offsetof(PlyVertex,normal[Y]), 0, 0, 0, 0}, {"nz", PLY_FLOAT, PLY_DOUBLE, offsetof(PlyVertex,normal[Z]), 0, 0, 0, 0}, {"edge_indices", PLY_INT, PLY_INT, offsetof(PlyVertex,edges), 1, PLY_UCHAR, PLY_UCHAR, offsetof(PlyVertex,nedges)}, {"face_indices", PLY_INT, PLY_INT, offsetof(PlyVertex,faces), 1, PLY_UCHAR, PLY_UCHAR, offsetof(PlyVertex,nfaces)}, #ifdef VERTEX_EPSILONS {"epsilon", PLY_FLOAT, PLY_FLOAT, offsetof(PlyVertex,epsilon), 0, 0, 0, 0}, #endif }; PlyProperty face_props[] = { /* list of property information for a face */ {"vertex_indices", PLY_INT, PLY_INT, offsetof(PlyFace,verts), 1, PLY_UCHAR, PLY_UCHAR, offsetof(PlyFace,nverts)}, {"edge_indices", PLY_INT, PLY_INT, offsetof(PlyFace,edges), 1, PLY_UCHAR, PLY_UCHAR, offsetof(PlyFace,nedges)}, }; PlyProperty edge_props[] = { /* list of property information for an edge */ {"vert1", PLY_INT, PLY_INT, offsetof(PlyEdge,vert1), 0, 0, 0, 0}, {"vert2", PLY_INT, PLY_INT, offsetof(PlyEdge,vert2), 0, 0, 0, 0}, {"face1", PLY_INT, PLY_INT, offsetof(PlyEdge,face1), 0, 0, 0, 0}, {"face2", PLY_INT, PLY_INT, offsetof(PlyEdge,face2), 0, 0, 0, 0}, }; /*** the PLY object ***/ static PlyOtherElems *other_elements = NULL; static PlyOtherProp *vert_other,*face_other,*edge_other; static int nelems; static char **element_list; static int num_comments; static char **comments; static int num_obj_info; static char **obj_info; static int file_type; static int has_x, has_y, has_z; static int has_nx, has_ny, has_nz; static int has_vedges, has_vfaces; static int has_fverts, has_fedges; static int has_vert1, has_vert2; static int has_face1, has_face2; #ifdef VERTEX_EPSILONS static int has_epsilons; #endif static double epsilon, bbox_epsilon; static int epsilon_mode; /*---------------------------------Functions-------------------------------- */ /*****************************************************************************\ @ main() ----------------------------------------------------------------------------- description : Main program: plysimplify input : An indexed, oriented, PLY object with per-vertex normals and possibly per-vertex epsilons + arguments as listed in usage(). output : A simplified PLY object of the same type. notes : \*****************************************************************************/ int main(int argc, char *argv[]) { Surface original_model, *simplified_model; init_defaults(); get_options(argc, argv); read_file(&original_model); if (epsilon_mode == BBOX_PERCENT) compute_bbox_epsilon(&original_model, bbox_epsilon, &epsilon); simplify(&original_model, &simplified_model, epsilon); write_file(simplified_model); return 0; } /** End of main() **/ /*****************************************************************************\ @ init_defaults() ----------------------------------------------------------------------------- description : Set defaults to be used in the absence of command-line arguments input : none output : none notes : \*****************************************************************************/ void init_defaults() { epsilon_mode = BBOX_PERCENT; bbox_epsilon = 1.0; } /** End of init_defaults() **/ /*****************************************************************************\ @ get_options() ----------------------------------------------------------------------------- description : Parse the command-line options input : argc and argv as passed into main output : some mode variables may be set notes : \*****************************************************************************/ void get_options(int argc, char *argv[]) { char *s; char *progname; progname = argv[0]; while (--argc > 0 && (*++argv)[0]=='-') { for (s = argv[0]+1; *s; s++) switch (*s) { case 'e': ++argv; if (sscanf(*argv, "%lf", &epsilon) == 1) { epsilon_mode = ABSOLUTE_DISTANCE; argc -= 1; } else { usage(progname); exit(-1); } break; case 'E': ++argv; if (sscanf(*argv, "%lf", &bbox_epsilon) == 1) { epsilon_mode = BBOX_PERCENT; argc -= 1; } else { usage(progname); exit(-1); } break; default: usage (progname); exit (-1); break; } } } /** End of get_options() **/ /*****************************************************************************\ @ usage() ----------------------------------------------------------------------------- description : Print out usage information. input : program name (argv[0]) output : command-line options printed to stderr notes : \*****************************************************************************/ void usage(char *progname) { fprintf(stderr, "usage: %s [flags] out.ply\n", progname); fprintf(stderr, " -- optional flags -- \n"); fprintf(stderr, " -e : absolute epsilon distance to offset\n"); fprintf(stderr, " -E : percent of bbox diagonal distance to offset\n"); fprintf(stderr, "\n"); } /** End of usage() **/ /*****************************************************************************\ @ compute_bbox_epsilon() ----------------------------------------------------------------------------- description : Given a bounding box epsilon (as percent of bounding box diagonal), compute an absolute epsilon distance. input : Surface mesh, bounding box diagonal percent epsilon (1% == 1.0, not 0.01) output : Absolute epsilon notes : \*****************************************************************************/ void compute_bbox_epsilon(Surface *model, double bbox_epsilon, double *epsilon) { int i, j, k; Triangle *tri; Vertex *vert; Extents bbox; double diag; /* compute bounding box */ bbox[HI][X] = bbox[HI][Y] = bbox[HI][Z] = -MAXDOUBLE; bbox[LO][X] = bbox[LO][Y] = bbox[LO][Z] = MAXDOUBLE; for (i=0; inum_tris; i++) { tri = &(model->tris[i]); for (j=0; j<3; j++) { vert = tri->verts[j]; for (k=0; k<3; k++) { bbox[HI][k] = FMAX(bbox[HI][k], vert->coord[k]); bbox[LO][k] = FMIN(bbox[LO][k], vert->coord[k]); } } } diag = sqrt(SQ_DIST3(bbox[HI], bbox[LO])); *epsilon = diag * bbox_epsilon / 100.0; return; } /** End of compute_bbox_epsilon() **/ /*****************************************************************************\ @ read_file() ----------------------------------------------------------------------------- description : Read in the PLY file from standard in. input : PLY file from stdin output : Surface mesh notes : \*****************************************************************************/ void read_file(Surface *model) { int i,j; PlyFile *ply; int nprops; int num_elems; PlyProperty **plist; char *elem_name; float version; PlyVertex plyvertex; PlyEdge plyedge; PlyFace plyface; Vertex *vert; Edge *edge; Triangle *face; /*** Read in the original PLY object ***/ ply = ply_read (stdin, &nelems, &element_list); ply_get_info (ply, &version, &file_type); for (i = 0; i < nelems; i++) { /* get the description of the first element */ elem_name = element_list[i]; plist = ply_get_element_description (ply, elem_name, &num_elems, &nprops); if (equal_strings ("vertex", elem_name)) { /* create a vertex list to hold all the vertices */ ALLOCN(model->verts, Vertex, num_elems); model->num_verts = num_elems; /* set up for getting vertex elements */ /* verify which properties these vertices have */ has_x = has_y = has_z = has_nx = has_ny = has_nz = has_vedges = has_vfaces = FALSE; #ifdef VERTEX_EPSILONS has_epsilons = FALSE; #endif for (j=0; jname)) { ply_get_property (ply, elem_name, &vert_props[0]); /* x */ has_x = TRUE; } else if (equal_strings("y", plist[j]->name)) { ply_get_property (ply, elem_name, &vert_props[1]); /* y */ has_y = TRUE; } else if (equal_strings("z", plist[j]->name)) { ply_get_property (ply, elem_name, &vert_props[2]); /* z */ has_z = TRUE; } else if (equal_strings("nx", plist[j]->name)) { ply_get_property (ply, elem_name, &vert_props[3]); /* nx */ has_nx = TRUE; } else if (equal_strings("ny", plist[j]->name)) { ply_get_property (ply, elem_name, &vert_props[4]); /* ny */ has_ny = TRUE; } else if (equal_strings("nz", plist[j]->name)) { ply_get_property (ply, elem_name, &vert_props[5]); /* nz */ has_nz = TRUE; } else if (equal_strings("edge_indices", plist[j]->name)) { ply_get_property (ply, elem_name, &vert_props[6]); has_vedges = TRUE; } else if (equal_strings("face_indices", plist[j]->name)) { ply_get_property (ply, elem_name, &vert_props[7]); has_vfaces = TRUE; } #ifdef VERTEX_EPSILONS else if (equal_strings("epsilon", plist[j]->name)) { ply_get_property (ply, elem_name, &vert_props[8]); has_epsilons = TRUE; } #endif } vert_other = ply_get_other_properties (ply, elem_name, offsetof(PlyVertex,other_props)); /* test for necessary properties */ if ((!has_x) || (!has_y) || (!has_z)) { fprintf(stderr, "Vertices must have x, y, and z coordinates\n"); exit(-1); } if (!has_vedges) { fprintf(stderr, "Vertices must have edge indices\n"); exit(-1); } if (!has_vfaces) { fprintf(stderr, "Vertices must have face indices\n"); exit(-1); } if ((!has_nx) || (!has_ny) || (!has_nz)) { fprintf(stderr, "Vertices must have x, y, and z normal components\n"); exit(-1); } #ifdef VERTEX_EPSILONS if (!has_epsilons) { fprintf(stderr, "Vertices must have epsilons\n"); exit(-1); } #endif /* grab all the vertex elements */ for (j = 0; j < num_elems; j++) { ply_get_element (ply, (void *) (&plyvertex)); vert = &(model->verts[j]); vert->id = j; VEC3_ASN_OP(vert->coord, =, plyvertex.coord); VEC3_ASN_OP(vert->normal, =, plyvertex.normal); vert->num_tris = plyvertex.nfaces; ALLOCN(vert->tris, Triangle *, vert->num_tris); VEC_ASN_OP(vert->tris, =, ((Triangle **)plyvertex.faces), plyvertex.nfaces); vert->num_edges = plyvertex.nedges; ALLOCN(vert->edges, Edge *, vert->num_edges); VEC_ASN_OP(vert->edges, =, ((Edge **)plyvertex.edges), plyvertex.nedges); #ifdef VERTEX_EPSILONS vert->epsilon = plyvertex.epsilon; #endif vert->other_props = plyvertex.other_props; } } else if (equal_strings ("face", elem_name)) { /* create a list to hold all the face elements */ ALLOCN(model->tris, Triangle, num_elems); model->num_tris = num_elems; /* set up for getting face elements */ /* verify which properties these vertices have */ has_fverts = has_fedges = FALSE; for (j=0; jname)) { ply_get_property (ply, elem_name, &face_props[0]); /* vertex_indices */ has_fverts = TRUE; } if (equal_strings("edge_indices", plist[j]->name)) { ply_get_property (ply, elem_name, &face_props[1]); has_fedges = TRUE; } } /* test for necessary properties */ if (!has_fverts) { fprintf(stderr, "Faces must have vertex indices\n"); exit(-1); } if (!has_fedges) { fprintf(stderr, "Faces must have edge indices\n"); exit(-1); } /* grab all the face elements */ for (j = 0; j < num_elems; j++) { ply_get_element (ply, (void *) (&plyface)); if ((plyface.nverts != 3) || (plyface.nedges != 3)) { fprintf(stderr, "Faces must be triangulated\n"); fprintf(stderr, " face #%d\n", j); fprintf(stderr, " nverts = %d, nedges = %d\n", plyface.nverts, plyface.nedges); exit(-1); } face = &(model->tris[j]); face->id = j; VEC3_ASN_OP(face->verts, =, (Vertex *)plyface.verts); VEC3_ASN_OP(face->edges, =, (Edge *)plyface.edges); } } else if (equal_strings ("edge", elem_name)) { /* create a list to hold all the face elements */ ALLOCN(model->edges, Edge, num_elems); model->num_edges = num_elems; /* set up for getting face elements */ /* verify which properties these vertices have */ has_vert1 = has_vert2 = has_face1 = has_face2 = FALSE; for (j=0; jname)) { ply_get_property (ply, elem_name, &edge_props[0]); has_vert1 = TRUE; } if (equal_strings("vert2", plist[j]->name)) { ply_get_property (ply, elem_name, &edge_props[1]); has_vert2 = TRUE; } if (equal_strings("face1", plist[j]->name)) { ply_get_property (ply, elem_name, &edge_props[2]); has_face1 = TRUE; } if (equal_strings("face2", plist[j]->name)) { ply_get_property (ply, elem_name, &edge_props[3]); has_face2 = TRUE; } } /* test for necessary properties */ if ((!has_vert1) || (!has_vert2)) { fprintf(stderr, "Edges must have vertex indices\n"); exit(-1); } if ((!has_face1) || (!has_face2)) { fprintf(stderr, "Edges must have face indices\n"); exit(-1); } /* grab all the edge elements */ for (j = 0; j < num_elems; j++) { ply_get_element (ply, (void *) (&plyedge)); edge = &(model->edges[j]); edge->id = j; edge->verts[0] = (Vertex *)plyedge.vert1; edge->verts[1] = (Vertex *)plyedge.vert2; edge->tris[0] = (Triangle *)plyedge.face1; edge->tris[1] = (Triangle *)plyedge.face2; } } else other_elements = ply_get_other_element (ply, elem_name, num_elems); } comments = ply_get_comments (ply, &num_comments); obj_info = ply_get_obj_info (ply, &num_obj_info); ply_close (ply); /* now convert the vertex, edge, and triangle indices into real pointers */ for (i=0; inum_verts; i++) { vert = &(model->verts[i]); for (j=0; jnum_tris; j++) vert->tris[j] = &(model->tris[(int)vert->tris[j]]); for (j=0; jnum_edges; j++) vert->edges[j] = &(model->edges[(int)vert->edges[j]]); } for (i=0; inum_tris; i++) { face = &(model->tris[i]); for (j=0; j<3; j++) { face->verts[j] = &(model->verts[(int)face->verts[j]]); face->edges[j] = &(model->edges[(int)face->edges[j]]); } } for (i=0; inum_edges; i++) { edge = &(model->edges[i]); for (j=0; j<2; j++) { edge->verts[j] = &(model->verts[(int)edge->verts[j]]); if ((int)edge->tris[j] != -1) edge->tris[j] = &(model->tris[(int)edge->tris[j]]); else edge->tris[j] = NULL; } } /* now find triangle plane equations */ for (i=0; inum_tris; i++) { face = &(model->tris[i]); find_plane_eq(face->verts[0]->coord, face->verts[1]->coord, face->verts[2]->coord, face->plane_eq); } } /** End of read_file() **/ /*****************************************************************************\ @ write_file() ----------------------------------------------------------------------------- description : Write out the PLY file to standard out. input : Surface mesh output : PLY object written to stdout notes : \*****************************************************************************/ void write_file(Surface *model) { int i,j; PlyFile *ply; PlyVertex plyvert; PlyEdge plyedge; PlyFace plyface; Vertex *vert; Edge *edge; Triangle *face; /*** Write out the final PLY object ***/ ply = ply_write (stdout, nelems, element_list, file_type); /* describe what properties go into the vertex and face elements */ ply_element_count (ply, "vertex", model->num_verts); ply_describe_property (ply, "vertex", &vert_props[0]); ply_describe_property (ply, "vertex", &vert_props[1]); ply_describe_property (ply, "vertex", &vert_props[2]); ply_describe_property (ply, "vertex", &vert_props[3]); ply_describe_property (ply, "vertex", &vert_props[4]); ply_describe_property (ply, "vertex", &vert_props[5]); ply_describe_property (ply, "vertex", &vert_props[6]); ply_describe_property (ply, "vertex", &vert_props[7]); #ifdef VERTEX_EPSILONS ply_describe_property(ply, "vertex", &vert_props[8]); #endif ply_describe_other_properties (ply, vert_other, offsetof(PlyVertex,other_props)); ply_element_count (ply, "face", model->num_tris); ply_describe_property (ply, "face", &face_props[0]); ply_describe_property (ply, "face", &face_props[1]); ply_element_count (ply, "edge", model->num_edges); ply_describe_property (ply, "edge", &edge_props[0]); ply_describe_property (ply, "edge", &edge_props[1]); ply_describe_property (ply, "edge", &edge_props[2]); ply_describe_property (ply, "edge", &edge_props[3]); ply_describe_other_elements (ply, other_elements); for (i = 0; i < num_comments; i++) ply_put_comment (ply, comments[i]); for (i = 0; i < num_obj_info; i++) ply_put_obj_info (ply, obj_info[i]); ply_header_complete (ply); /* set up and write the vertex elements */ ply_put_element_setup (ply, "vertex"); for (i = 0; i < model->num_verts; i++) { vert = &(model->verts[i]); VEC3_ASN_OP(plyvert.coord, =, vert->coord); VEC3_ASN_OP(plyvert.normal, =, vert->normal); ALLOCN(plyvert.faces, int, vert->num_tris); for (j=0; jnum_tris; j++) plyvert.faces[j] = vert->tris[j]->id; plyvert.nfaces = vert->num_tris; ALLOCN(plyvert.edges, int, vert->num_edges); for (j=0; jnum_edges; j++) plyvert.edges[j] = vert->edges[j]->id; plyvert.nedges = vert->num_edges; #ifdef VERTEX_EPSILONS plyvert.epsilon = vert->epsilon; #endif plyvert.other_props = vert->other_props; ply_put_element (ply, (void *)&plyvert); FREE(plyvert.faces); FREE(plyvert.edges); } /* set up and write the face elements */ ply_put_element_setup (ply, "face"); ALLOCN(plyface.verts, int, 3); ALLOCN(plyface.edges, int, 3); for (i = 0; i < model->num_tris; i++) { face = &(model->tris[i]); for (j=0; j<3; j++) { plyface.verts[j] = face->verts[j]->id; plyface.edges[j] = face->edges[j]->id; } plyface.nverts = plyface.nedges = 3; ply_put_element (ply, (void *)&plyface); } FREE(plyface.verts); FREE(plyface.edges); /* set up and write the edge elements */ ply_put_element_setup (ply, "edge"); for (i = 0; i < model->num_edges; i++) { edge = &(model->edges[i]); plyedge.vert1 = edge->verts[0]->id; plyedge.vert2 = edge->verts[1]->id; plyedge.face1 = edge->tris[0]->id; if (edge->tris[1] != NULL) plyedge.face2 = edge->tris[1]->id; else plyedge.face2 = -1; ply_put_element (ply, (void *)&plyedge); } ply_put_other_elements (ply); /* close the PLY file */ ply_close (ply); } /** End of write_file() **/ /*****************************************************************************\ $Log: plysimplify.c,v $ Revision 1.1.1.1 2000/04/06 15:35:32 philippe Initial CVS release Revision 1.6 1997/04/10 20:10:46 cohenj Added Amitabh's name to credits Revision 1.5 1996/08/23 21:36:49 cohenj fixed handling of other vertex properties, removed any mention of other face or edge properties (since this program doesn't preserve the faces and edges anyway) * Revision 1.4 96/04/08 18:54:30 cohenj * added support for per-vertex epsilons, procedure comments, * and copyright notices * * Revision 1.3 1995/10/16 16:29:41 cohenj * Cleaned up. * * Revision 1.2 95/09/30 06:11:10 cohenj * almost done writing revision 1 -- just need the code to update * the model after a vertex is removed and finalize the model after removing * all vertices in the queue. * * Revision 1.1 95/09/15 16:28:21 cohenj * Initial revision * * Revision 1.1 1995/08/30 20:57:04 cohenj * Initial revision * * Revision 1.1 1995/08/30 20:57:04 cohenj * Initial revision * \*****************************************************************************/