| blob | 89b81846dac124fa0ca613034169be83ac94fd25 |
1 /*\r
2 * Progressive Mesh type Polygon Reduction Algorithm\r
3 * by Stan Melax (c) 1998\r
4 * Permission to use any of this code wherever you want is granted..\r
5 * Although, please do acknowledge authorship if appropriate.\r
6 *\r
7 * See the header file progmesh.h for a description of this module\r
8 */\r
9 \r
10 #include <stdio.h>\r
11 #include <math.h>\r
12 #include <stdlib.h>\r
13 #include <assert.h>\r
14 //#include <windows.h>\r
15 \r
16 #include "vector.h"\r
17 #include "list.h"\r
18 #include "progmesh.h"\r
19 \r
20 #define min(x,y) (((x) <= (y)) ? (x) : (y))\r
21 #define max(x,y) (((x) >= (y)) ? (x) : (y))\r
22 \r
23 \r
24 /*\r
25 * For the polygon reduction algorithm we use data structures\r
26 * that contain a little bit more information than the usual\r
27 * indexed face set type of data structure.\r
28 * From a vertex we wish to be able to quickly get the\r
29 * neighboring faces and vertices.\r
30 */\r
31 class Triangle;\r
32 class Vertex;\r
33 \r
34 class Triangle {\r
35 public:\r
36 Vertex * vertex[3]; // the 3 points that make this tri\r
37 Vector normal; // unit vector othogonal to this face\r
38 Triangle(Vertex *v0,Vertex *v1,Vertex *v2);\r
39 ~Triangle();\r
40 void ComputeNormal();\r
41 void ReplaceVertex(Vertex *vold,Vertex *vnew);\r
42 int HasVertex(Vertex *v);\r
43 };\r
44 class Vertex {\r
45 public:\r
46 Vector position; // location of point in euclidean space\r
47 int id; // place of vertex in original list\r
48 List<Vertex *> neighbor; // adjacent vertices\r
49 List<Triangle *> face; // adjacent triangles\r
50 float objdist; // cached cost of collapsing edge\r
51 Vertex * collapse; // candidate vertex for collapse\r
52 Vertex(Vector v,int _id);\r
53 ~Vertex();\r
54 void RemoveIfNonNeighbor(Vertex *n);\r
55 };\r
56 List<Vertex *> vertices;\r
57 List<Triangle *> triangles;\r
58 \r
59 \r
60 Triangle::Triangle(Vertex *v0,Vertex *v1,Vertex *v2){\r
61 assert(v0!=v1 && v1!=v2 && v2!=v0);\r
62 vertex[0]=v0;\r
63 vertex[1]=v1;\r
64 vertex[2]=v2;\r
65 ComputeNormal();\r
66 triangles.Add(this);\r
67 for(int i=0;i<3;i++) {\r
68 vertex[i]->face.Add(this);\r
69 for(int j=0;j<3;j++) if(i!=j) {\r
70 vertex[i]->neighbor.AddUnique(vertex[j]);\r
71 }\r
72 }\r
73 }\r
74 Triangle::~Triangle(){\r
75 int i;\r
76 triangles.Remove(this);\r
77 for(i=0;i<3;i++) {\r
78 if(vertex[i]) vertex[i]->face.Remove(this);\r
79 }\r
80 for(i=0;i<3;i++) {\r
81 int i2 = (i+1)%3;\r
82 if(!vertex[i] || !vertex[i2]) continue;\r
83 vertex[i ]->RemoveIfNonNeighbor(vertex[i2]);\r
84 vertex[i2]->RemoveIfNonNeighbor(vertex[i ]);\r
85 }\r
86 }\r
87 int Triangle::HasVertex(Vertex *v) {\r
88 return (v==vertex[0] ||v==vertex[1] || v==vertex[2]);\r
89 }\r
90 void Triangle::ComputeNormal(){\r
91 Vector v0=vertex[0]->position;\r
92 Vector v1=vertex[1]->position;\r
93 Vector v2=vertex[2]->position;\r
94 normal = (v1-v0)*(v2-v1);\r
95 if(magnitude(normal)==0)return;\r
96 normal = normalize(normal);\r
97 }\r
98 void Triangle::ReplaceVertex(Vertex *vold,Vertex *vnew) {\r
99 assert(vold && vnew);\r
100 assert(vold==vertex[0] || vold==vertex[1] || vold==vertex[2]);\r
101 assert(vnew!=vertex[0] && vnew!=vertex[1] && vnew!=vertex[2]);\r
102 if(vold==vertex[0]){\r
103 vertex[0]=vnew;\r
104 }\r
105 else if(vold==vertex[1]){\r
106 vertex[1]=vnew;\r
107 }\r
108 else {\r
109 assert(vold==vertex[2]);\r
110 vertex[2]=vnew;\r
111 }\r
112 int i;\r
113 vold->face.Remove(this);\r
114 assert(!vnew->face.Contains(this));\r
115 vnew->face.Add(this);\r
116 for(i=0;i<3;i++) {\r
117 vold->RemoveIfNonNeighbor(vertex[i]);\r
118 vertex[i]->RemoveIfNonNeighbor(vold);\r
119 }\r
120 for(i=0;i<3;i++) {\r
121 assert(vertex[i]->face.Contains(this)==1);\r
122 for(int j=0;j<3;j++) if(i!=j) {\r
123 vertex[i]->neighbor.AddUnique(vertex[j]);\r
124 }\r
125 }\r
126 ComputeNormal();\r
127 }\r
128 \r
129 Vertex::Vertex(Vector v,int _id) {\r
130 position =v;\r
131 id=_id;\r
132 vertices.Add(this);\r
133 }\r
134 \r
135 Vertex::~Vertex(){\r
136 assert(face.num==0);\r
137 while(neighbor.num) {\r
138 neighbor[0]->neighbor.Remove(this);\r
139 neighbor.Remove(neighbor[0]);\r
140 }\r
141 vertices.Remove(this);\r
142 }\r
143 void Vertex::RemoveIfNonNeighbor(Vertex *n) {\r
144 // removes n from neighbor list if n isn't a neighbor.\r
145 if(!neighbor.Contains(n)) return;\r
146 for(int i=0;i<face.num;i++) {\r
147 if(face[i]->HasVertex(n)) return;\r
148 }\r
149 neighbor.Remove(n);\r
150 }\r
151 \r
152 \r
153 float ComputeEdgeCollapseCost(Vertex *u,Vertex *v) {\r
154 // if we collapse edge uv by moving u to v then how\r
155 // much different will the model change, i.e. how much "error".\r
156 // Texture, vertex normal, and border vertex code was removed\r
157 // to keep this demo as simple as possible.\r
158 // The method of determining cost was designed in order\r
159 // to exploit small and coplanar regions for\r
160 // effective polygon reduction.\r
161 // Is is possible to add some checks here to see if "folds"\r
162 // would be generated. i.e. normal of a remaining face gets\r
163 // flipped. I never seemed to run into this problem and\r
164 // therefore never added code to detect this case.\r
165 int i;\r
166 float edgelength = magnitude(v->position - u->position);\r
167 float curvature=0;\r
168 \r
169 // find the "sides" triangles that are on the edge uv\r
170 List<Triangle *> sides;\r
171 for(i=0;i<u->face.num;i++) {\r
172 if(u->face[i]->HasVertex(v)){\r
173 sides.Add(u->face[i]);\r
174 }\r
175 }\r
176 // use the triangle facing most away from the sides\r
177 // to determine our curvature term\r
178 for(i=0;i<u->face.num;i++) {\r
179 float mincurv=1; // curve for face i and closer side to it\r
180 for(int j=0;j<sides.num;j++) {\r
181 // use dot product of face normals. '^' defined in vector\r
182 float dotprod = u->face[i]->normal ^ sides[j]->normal;\r
183 mincurv = min(mincurv,(1-dotprod)/2.0f);\r
184 }\r
185 curvature = max(curvature,mincurv);\r
186 }\r
187 // the more coplanar the lower the curvature term\r
188 return edgelength * curvature;\r
189 }\r
190 \r
191 void ComputeEdgeCostAtVertex(Vertex *v) {\r
192 // compute the edge collapse cost for all edges that start\r
193 // from vertex v. Since we are only interested in reducing\r
194 // the object by selecting the min cost edge at each step, we\r
195 // only cache the cost of the least cost edge at this vertex\r
196 // (in member variable collapse) as well as the value of the\r
197 // cost (in member variable objdist).\r
198 if(v->neighbor.num==0) {\r
199 // v doesn't have neighbors so it costs nothing to collapse\r
200 v->collapse=NULL;\r
201 v->objdist=-0.01f;\r
202 return;\r
203 }\r
204 v->objdist = 1000000;\r
205 v->collapse=NULL;\r
206 // search all neighboring edges for "least cost" edge\r
207 for(int i=0;i<v->neighbor.num;i++) {\r
208 float dist;\r
209 dist = ComputeEdgeCollapseCost(v,v->neighbor[i]);\r
210 if(dist<v->objdist) {\r
211 v->collapse=v->neighbor[i]; // candidate for edge collapse\r
212 v->objdist=dist; // cost of the collapse\r
213 }\r
214 }\r
215 }\r
216 void ComputeAllEdgeCollapseCosts() {\r
217 // For all the edges, compute the difference it would make\r
218 // to the model if it was collapsed. The least of these\r
219 // per vertex is cached in each vertex object.\r
220 for(int i=0;i<vertices.num;i++) {\r
221 ComputeEdgeCostAtVertex(vertices[i]);\r
222 }\r
223 }\r
224 \r
225 void Collapse(Vertex *u,Vertex *v){\r
226 // Collapse the edge uv by moving vertex u onto v\r
227 // Actually remove tris on uv, then update tris that\r
228 // have u to have v, and then remove u.\r
229 if(!v) {\r
230 // u is a vertex all by itself so just delete it\r
231 delete u;\r
232 return;\r
233 }\r
234 int i;\r
235 List<Vertex *>tmp;\r
236 // make tmp a list of all the neighbors of u\r
237 for(i=0;i<u->neighbor.num;i++) {\r
238 tmp.Add(u->neighbor[i]);\r
239 }\r
240 // delete triangles on edge uv:\r
241 for(i=u->face.num-1;i>=0;i--) {\r
242 if(u->face[i]->HasVertex(v)) {\r
243 delete(u->face[i]);\r
244 }\r
245 }\r
246 // update remaining triangles to have v instead of u\r
247 for(i=u->face.num-1;i>=0;i--) {\r
248 u->face[i]->ReplaceVertex(u,v);\r
249 }\r
250 delete u;\r
251 // recompute the edge collapse costs for neighboring vertices\r
252 for(i=0;i<tmp.num;i++) {\r
253 ComputeEdgeCostAtVertex(tmp[i]);\r
254 }\r
255 }\r
256 \r
257 void AddVertex(List<Vector> &vert){\r
258 for(int i=0;i<vert.num;i++) {\r
259 new Vertex(vert[i],i);\r
260 }\r
261 }\r
262 void AddFaces(List<tridata> &tri){\r
263 for(int i=0;i<tri.num;i++) {\r
264 new Triangle(\r
265 vertices[tri[i].v[0]],\r
266 vertices[tri[i].v[1]],\r
267 vertices[tri[i].v[2]] );\r
268 }\r
269 }\r
270 \r
271 Vertex *MinimumCostEdge(){\r
272 // Find the edge that when collapsed will affect model the least.\r
273 // This funtion actually returns a Vertex, the second vertex\r
274 // of the edge (collapse candidate) is stored in the vertex data.\r
275 // Serious optimization opportunity here: this function currently\r
276 // does a sequential search through an unsorted list :-(\r
277 // Our algorithm could be O(n*lg(n)) instead of O(n*n)\r
278 Vertex *mn=vertices[0];\r
279 for(int i=0;i<vertices.num;i++) {\r
280 if(vertices[i]->objdist < mn->objdist) {\r
281 mn = vertices[i];\r
282 }\r
283 }\r
284 return mn;\r
285 }\r
286 \r
287 void ProgressiveMesh(List<Vector> &vert, List<tridata> &tri,\r
288 List<int> &map, List<int> &permutation)\r
289 {\r
290 AddVertex(vert); // put input data into our data structures\r
291 AddFaces(tri);\r
292 ComputeAllEdgeCollapseCosts(); // cache all edge collapse costs\r
293 permutation.SetSize(vertices.num); // allocate space\r
294 map.SetSize(vertices.num); // allocate space\r
295 // reduce the object down to nothing:\r
296 while(vertices.num > 0) {\r
297 // get the next vertex to collapse\r
298 Vertex *mn = MinimumCostEdge();\r
299 // keep track of this vertex, i.e. the collapse ordering\r
300 permutation[mn->id]=vertices.num-1;\r
301 // keep track of vertex to which we collapse to\r
302 map[vertices.num-1] = (mn->collapse)?mn->collapse->id:-1;\r
303 // Collapse this edge\r
304 Collapse(mn,mn->collapse);\r
305 }\r
306 // reorder the map list based on the collapse ordering\r
307 for(int i=0;i<map.num;i++) {\r
308 map[i] = (map[i]==-1)?0:permutation[map[i]];\r
309 }\r
310 // The caller of this function should reorder their vertices\r
311 // according to the returned "permutation".\r
312 }\r
313 \r