121 |
|
error(SYSTEM,"eNew_edge(): Unable to allocate memory"); |
122 |
|
} |
123 |
|
|
124 |
+ |
/* Return list of edges defining polygon formed by boundary of triangles |
125 |
+ |
adjacent to id. Return set of triangles adjacent to id to delete in delptr |
126 |
+ |
*/ |
127 |
|
LIST |
128 |
< |
*smVertex_star_polygon(sm,id,delptr) |
128 |
> |
*smVertexPolygon(sm,id,delptr) |
129 |
|
SM *sm; |
130 |
|
int id; |
131 |
|
QUADTREE *delptr; |
132 |
|
{ |
133 |
|
TRI *tri,*t_next; |
134 |
|
LIST *elist,*end; |
135 |
< |
int t_id,v_next,t_next_id; |
133 |
< |
int e; |
135 |
> |
int e,t_id,v_next,t_next_id,b_id,v_id; |
136 |
|
OBJECT del_set[2]; |
137 |
|
|
138 |
+ |
eClear_edges(); |
139 |
|
elist = end = NULL; |
140 |
+ |
|
141 |
|
/* Get the first triangle adjacent to vertex id */ |
142 |
|
t_id = SM_NTH_VERT(sm,id); |
143 |
|
tri = SM_NTH_TRI(sm,t_id); |
144 |
|
|
145 |
< |
if((e = eNew_edge()) == INVALID) |
146 |
< |
return(NULL); |
147 |
< |
|
148 |
< |
v_next = (T_WHICH_V(tri,id)+1)%3; |
149 |
< |
SET_E_NTH_VERT(e,0,T_NTH_V(tri,v_next)); |
145 |
> |
e = eNew_edge(); |
146 |
> |
/* Get the next vertex on the polygon boundary */ |
147 |
> |
v_id = T_WHICH_V(tri,id); |
148 |
> |
b_id = (v_id + 1)%3; |
149 |
> |
/* Create an edge */ |
150 |
> |
SET_E_NTH_VERT(e,0,T_NTH_V(tri,b_id)); |
151 |
|
SET_E_NTH_TRI(e,0,INVALID); |
152 |
< |
SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_next)); |
153 |
< |
v_next = (T_WHICH_V(tri,id)+2)%3; |
154 |
< |
SET_E_NTH_VERT(e,1,T_NTH_V(tri,v_next)); |
152 |
> |
SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_id)); |
153 |
> |
v_next = T_NTH_V(tri,(b_id+1)%3); |
154 |
> |
SET_E_NTH_VERT(e,1,v_next); |
155 |
|
elist = add_data_to_circular_list(elist,&end,e); |
151 |
– |
|
156 |
|
t_next_id = t_id; |
157 |
|
t_next = tri; |
158 |
|
|
159 |
< |
del_set[0] =1; del_set[1] = t_id; |
159 |
> |
/* Create a set to hold all of the triangles for deletion later */ |
160 |
> |
del_set[0] = 1; del_set[1] = t_id; |
161 |
|
*delptr = qtnewleaf(del_set); |
162 |
|
|
163 |
< |
while((t_next_id = T_NTH_NBR(t_next,v_next)) != t_id) |
164 |
< |
{ |
165 |
< |
if((e = eNew_edge()) == INVALID) |
161 |
< |
return(NULL); |
162 |
< |
|
163 |
> |
while((t_next_id = T_NTH_NBR(t_next,b_id)) != t_id) |
164 |
> |
{ |
165 |
> |
e = eNew_edge(); |
166 |
|
t_next = SM_NTH_TRI(sm,t_next_id); |
167 |
< |
v_next = (T_WHICH_V(t_next,id)+1)%3; |
165 |
< |
|
166 |
< |
SET_E_NTH_VERT(e,0,T_NTH_V(t_next,v_next)); |
167 |
> |
SET_E_NTH_VERT(e,0,v_next); |
168 |
|
SET_E_NTH_TRI(e,0,INVALID); |
169 |
< |
SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_next)); |
170 |
< |
v_next = (T_WHICH_V(t_next,id)+2)%3; |
171 |
< |
SET_E_NTH_VERT(e,1,T_NTH_V(t_next,v_next)); |
169 |
> |
v_id = T_WHICH_V(t_next,id); |
170 |
> |
b_id = (v_id + 1)%3; |
171 |
> |
SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_id)); |
172 |
> |
v_next = T_NTH_V(t_next,(b_id+1)%3); |
173 |
> |
SET_E_NTH_VERT(e,1,v_next); |
174 |
|
elist = add_data_to_circular_list(elist,&end,e); |
175 |
< |
|
173 |
< |
|
174 |
< |
if(qtinset(*delptr,t_next_id)) |
175 |
< |
{ |
176 |
< |
#ifdef DEBUG |
177 |
< |
eputs("smVertex_star_polygon(): id already in set\n"); |
178 |
< |
#endif |
179 |
< |
free_list(elist); |
180 |
< |
return(NULL); |
181 |
< |
} |
182 |
< |
else |
183 |
< |
qtaddelem(*delptr,t_next_id); |
175 |
> |
qtaddelem(*delptr,t_next_id); |
176 |
|
} |
177 |
|
return(elist); |
178 |
|
} |
179 |
|
|
180 |
+ |
|
181 |
|
int |
182 |
< |
smEdge_intersect_polygon(sm,v0,v1,l) |
182 |
> |
smTriangulate_add_tri(sm,id0,id1,id2,e0,e1,e2ptr) |
183 |
|
SM *sm; |
184 |
< |
FVECT v0,v1; |
192 |
< |
LIST *l; |
184 |
> |
int id0,id1,id2,e0,e1,*e2ptr; |
185 |
|
{ |
186 |
< |
FVECT e0,e1; |
187 |
< |
int e,id_e0,id_e1; |
196 |
< |
LIST *el,*eptr; |
197 |
< |
|
198 |
< |
/* Test the edges in l against v0v1 to see if v0v1 intersects |
199 |
< |
any other edges |
200 |
< |
*/ |
201 |
< |
|
202 |
< |
el = l; |
186 |
> |
int t_id; |
187 |
> |
int e2; |
188 |
|
|
189 |
< |
while(el) |
190 |
< |
{ |
191 |
< |
e = (int)LIST_DATA(el); |
207 |
< |
id_e0 = E_NTH_VERT(e,0); |
208 |
< |
id_e1 = E_NTH_VERT(e,1); |
209 |
< |
|
210 |
< |
VSUB(e0,SM_NTH_WV(sm,id_e0),SM_VIEW_CENTER(sm)); |
211 |
< |
VSUB(e1,SM_NTH_WV(sm,id_e1),SM_VIEW_CENTER(sm)); |
212 |
< |
if(sedge_intersect(v0,v1,e0,e1)) |
213 |
< |
return(TRUE); |
214 |
< |
|
215 |
< |
el = LIST_NEXT(el); |
216 |
< |
if(el == l) |
217 |
< |
break; |
218 |
< |
} |
219 |
< |
return(FALSE); |
220 |
< |
} |
221 |
< |
|
222 |
< |
int |
223 |
< |
smFind_next_convex_vertex(sm,id0,id1,v0,v1,l) |
224 |
< |
SM *sm; |
225 |
< |
int id0,id1; |
226 |
< |
FVECT v0,v1; |
227 |
< |
LIST *l; |
228 |
< |
{ |
229 |
< |
int e,id; |
230 |
< |
LIST *el; |
231 |
< |
FVECT v; |
232 |
< |
|
233 |
< |
/* starting with the end of edge at head of l, search sequentially for |
234 |
< |
vertex v such that v0v1v is a convex angle, and the edge v1v does |
235 |
< |
not intersect any other edges |
236 |
< |
*/ |
237 |
< |
id = INVALID; |
238 |
< |
el = l; |
239 |
< |
while(id != id0) |
240 |
< |
{ |
241 |
< |
e = (int)LIST_DATA(el); |
242 |
< |
id = E_NTH_VERT(e,1); |
243 |
< |
|
244 |
< |
smDir(sm,v,id); |
245 |
< |
|
246 |
< |
if(convex_angle(v0,v1,v) && !smEdge_intersect_polygon(sm,v1,v,l)) |
247 |
< |
return(id); |
248 |
< |
|
249 |
< |
el = LIST_NEXT(el); |
250 |
< |
if(el == l) |
251 |
< |
break; |
252 |
< |
} |
253 |
< |
return(INVALID); |
254 |
< |
} |
255 |
< |
|
256 |
< |
int |
257 |
< |
split_edge_list(id0,id_new,l,lnew) |
258 |
< |
int id0,id_new; |
259 |
< |
LIST **l,**lnew; |
260 |
< |
{ |
261 |
< |
LIST *list,*lptr,*end; |
262 |
< |
int e,e1,e2,new_e; |
263 |
< |
|
264 |
< |
e2 = INVALID; |
265 |
< |
list = lptr = *l; |
266 |
< |
|
267 |
< |
if((new_e = eNew_edge())==INVALID) |
268 |
< |
{ |
269 |
< |
#ifdef DEBUG |
270 |
< |
eputs("split_edge_list():Too many edges\n"); |
189 |
> |
#ifdef DEBUG |
190 |
> |
if(id0 == INVALID || id1==INVALID || id2==INVALID) |
191 |
> |
error(CONSISTENCY,"bad id- smTriangulate_add_tri()\n"); |
192 |
|
#endif |
193 |
< |
return(FALSE); |
194 |
< |
} |
195 |
< |
SET_E_NTH_VERT(new_e,0,id0); |
196 |
< |
SET_E_NTH_VERT(new_e,1,id_new); |
197 |
< |
SET_E_NTH_TRI(new_e,0,INVALID); |
198 |
< |
SET_E_NTH_TRI(new_e,1,INVALID); |
199 |
< |
|
200 |
< |
while(e2 != id_new) |
201 |
< |
{ |
202 |
< |
lptr = LIST_NEXT(lptr); |
203 |
< |
e = (int)LIST_DATA(lptr); |
204 |
< |
e2 = E_NTH_VERT(e,1); |
205 |
< |
if(lptr == list) |
285 |
< |
{ |
286 |
< |
#ifdef DEBUG |
287 |
< |
eputs("split_edge_list():cant find vertex\n"); |
288 |
< |
#endif |
289 |
< |
*lnew = NULL; |
290 |
< |
return(FALSE); |
291 |
< |
} |
193 |
> |
t_id = smAdd_tri(sm,id0,id1,id2); |
194 |
> |
if(*e2ptr == 0) |
195 |
> |
{ |
196 |
> |
e2 = eNew_edge(); |
197 |
> |
SET_E_NTH_VERT(e2,0,id2); |
198 |
> |
SET_E_NTH_VERT(e2,1,id0); |
199 |
> |
} |
200 |
> |
else |
201 |
> |
e2 = *e2ptr; |
202 |
> |
/* set appropriate tri for each edge*/ |
203 |
> |
SET_E_NTH_TRI(e0,0,t_id); |
204 |
> |
SET_E_NTH_TRI(e1,0,t_id); |
205 |
> |
SET_E_NTH_TRI(e2,0,t_id); |
206 |
|
|
207 |
< |
} |
208 |
< |
end = lptr; |
295 |
< |
lptr = LIST_NEXT(lptr); |
296 |
< |
list = add_data_to_circular_list(list,&end,-new_e); |
297 |
< |
*lnew = list; |
298 |
< |
|
299 |
< |
/* now follow other cycle */ |
300 |
< |
|
301 |
< |
list = lptr; |
302 |
< |
e2 = INVALID; |
303 |
< |
while(e2 != id0) |
304 |
< |
{ |
305 |
< |
lptr = LIST_NEXT(lptr); |
306 |
< |
e = (int)LIST_DATA(lptr); |
307 |
< |
e2 = E_NTH_VERT(e,1); |
308 |
< |
if(lptr == list) |
309 |
< |
{ |
310 |
< |
#ifdef DEBUG |
311 |
< |
eputs("split_edge_list():cant find intial vertex\n"); |
312 |
< |
#endif |
313 |
< |
*l = NULL; |
314 |
< |
return(FALSE); |
315 |
< |
} |
316 |
< |
|
317 |
< |
} |
318 |
< |
end = lptr; |
319 |
< |
list = add_data_to_circular_list(list,&end,new_e); |
320 |
< |
*l = list; |
321 |
< |
return(TRUE); |
207 |
> |
*e2ptr = e2; |
208 |
> |
return(t_id); |
209 |
|
} |
210 |
|
|
324 |
– |
|
211 |
|
int |
212 |
< |
smTriangulate_convex(sm,plist,add_ptr) |
212 |
> |
smTriangulateConvex(sm,plist,add_ptr) |
213 |
|
SM *sm; |
214 |
|
LIST *plist,**add_ptr; |
215 |
|
{ |
216 |
|
int t_id,e_id0,e_id1,e_id2; |
217 |
|
int v_id0,v_id1,v_id2; |
218 |
|
LIST *lptr; |
333 |
– |
int cnt; |
219 |
|
|
220 |
|
lptr = plist; |
221 |
|
e_id0 = (int)LIST_DATA(lptr); |
226 |
|
e_id1 = (int)LIST_DATA(lptr); |
227 |
|
v_id1 = E_NTH_VERT(e_id1,0); |
228 |
|
v_id2 = E_NTH_VERT(e_id1,1); |
344 |
– |
/* form a triangle for each triple of with v0 as base of star */ |
345 |
– |
t_id = smAdd_tri(sm,v_id0,v_id1,v_id2); |
346 |
– |
*add_ptr = push_data(*add_ptr,t_id); |
347 |
– |
|
348 |
– |
/* add which pointer?*/ |
349 |
– |
|
229 |
|
lptr = LIST_NEXT(lptr); |
230 |
|
|
231 |
< |
if(LIST_NEXT(lptr) != plist) |
232 |
< |
{ |
354 |
< |
e_id2 = eNew_edge(); |
355 |
< |
SET_E_NTH_VERT(e_id2,0,v_id2); |
356 |
< |
SET_E_NTH_VERT(e_id2,1,v_id0); |
357 |
< |
} |
231 |
> |
if(LIST_NEXT(lptr) != plist) |
232 |
> |
e_id2 = 0; |
233 |
|
else |
234 |
|
e_id2 = (int)LIST_DATA(lptr); |
235 |
< |
|
236 |
< |
/* set appropriate tri for each edge*/ |
362 |
< |
SET_E_NTH_TRI(e_id0,0,t_id); |
363 |
< |
SET_E_NTH_TRI(e_id1,0,t_id); |
364 |
< |
SET_E_NTH_TRI(e_id2,0,t_id); |
365 |
< |
|
235 |
> |
t_id = smTriangulate_add_tri(sm,v_id0,v_id1,v_id2,e_id0,e_id1,&e_id2); |
236 |
> |
*add_ptr = push_data(*add_ptr,t_id); |
237 |
|
e_id0 = -e_id2; |
238 |
|
} |
239 |
|
free_list(plist); |
240 |
|
return(TRUE); |
241 |
|
} |
242 |
< |
int |
243 |
< |
smTriangulate_elist(sm,plist,add_ptr) |
244 |
< |
SM *sm; |
374 |
< |
LIST *plist,**add_ptr; |
375 |
< |
{ |
376 |
< |
LIST *l,*el1; |
377 |
< |
FVECT v0,v1,v2; |
378 |
< |
int id0,id1,id2,e,id_next; |
379 |
< |
char flipped; |
380 |
< |
int done; |
381 |
< |
|
382 |
< |
l = plist; |
383 |
< |
|
384 |
< |
while(l) |
385 |
< |
{ |
386 |
< |
/* get v0,v1,v2 */ |
387 |
< |
e = (int)LIST_DATA(l); |
388 |
< |
id0 = E_NTH_VERT(e,0); |
389 |
< |
id1 = E_NTH_VERT(e,1); |
390 |
< |
l = LIST_NEXT(l); |
391 |
< |
e = (int)LIST_DATA(l); |
392 |
< |
id2 = E_NTH_VERT(e,1); |
393 |
< |
|
394 |
< |
smDir(sm,v0,id0); |
395 |
< |
smDir(sm,v1,id1); |
396 |
< |
smDir(sm,v2,id2); |
397 |
< |
/* determine if convex (left turn), or concave(right turn) angle */ |
398 |
< |
if(convex_angle(v0,v1,v2)) |
399 |
< |
{ |
400 |
< |
if(l == plist) |
401 |
< |
break; |
402 |
< |
else |
403 |
< |
continue; |
404 |
< |
} |
405 |
< |
/* if concave: add edge and recurse on two sub polygons */ |
406 |
< |
id_next = smFind_next_convex_vertex(sm,id0,id1,v0,v1,LIST_NEXT(l)); |
407 |
< |
if(id_next == INVALID) |
408 |
< |
{ |
409 |
< |
#ifdef DEBUG |
410 |
< |
eputs("smTriangulate_elist():Unable to find convex vertex\n"); |
242 |
> |
#ifdef TEST_DRIVER |
243 |
> |
FVECT Norm[500],B_V[500]; |
244 |
> |
int Ncnt,Bcnt,Del=0; |
245 |
|
#endif |
412 |
– |
return(FALSE); |
413 |
– |
} |
414 |
– |
/* add edge */ |
415 |
– |
el1 = NULL; |
416 |
– |
/* Split edge list l into two lists: one from id1-id_next-id1, |
417 |
– |
and the next from id2-id_next-id2 |
418 |
– |
*/ |
419 |
– |
split_edge_list(id1,id_next,&l,&el1); |
420 |
– |
/* Recurse and triangulate the two edge lists */ |
421 |
– |
done = smTriangulate_elist(sm,l,add_ptr); |
422 |
– |
if(done) |
423 |
– |
done = smTriangulate_elist(sm,el1,add_ptr); |
424 |
– |
return(done); |
425 |
– |
} |
426 |
– |
done = smTriangulate_convex(sm,plist,add_ptr); |
427 |
– |
return(done); |
428 |
– |
} |
246 |
|
|
430 |
– |
int |
431 |
– |
smTriangulate_add_tri(sm,id0,id1,id2,e0,e1,e2ptr) |
432 |
– |
SM *sm; |
433 |
– |
int id0,id1,id2,e0,e1,*e2ptr; |
434 |
– |
{ |
435 |
– |
int t_id; |
436 |
– |
int e2; |
247 |
|
|
248 |
< |
t_id = smAdd_tri(sm,id0,id1,id2); |
249 |
< |
if(*e2ptr == 0) |
250 |
< |
{ |
251 |
< |
e2 = eNew_edge(); |
252 |
< |
SET_E_NTH_VERT(e2,0,id2); |
443 |
< |
SET_E_NTH_VERT(e2,1,id0); |
444 |
< |
} |
445 |
< |
else |
446 |
< |
e2 = *e2ptr; |
447 |
< |
/* set appropriate tri for each edge*/ |
448 |
< |
SET_E_NTH_TRI(e0,0,t_id); |
449 |
< |
SET_E_NTH_TRI(e1,0,t_id); |
450 |
< |
SET_E_NTH_TRI(e2,0,t_id); |
248 |
> |
/* Triangulate the polygon defined by plist, and generating vertex p_id. |
249 |
> |
Return list of added triangles in list add_ptr. Returns TRUE if |
250 |
> |
successful, FALSE otherwise. This is NOT a general triangulation routine, |
251 |
> |
assumes polygon star relative to id |
252 |
> |
*/ |
253 |
|
|
452 |
– |
*e2ptr = e2; |
453 |
– |
return(t_id); |
454 |
– |
} |
254 |
|
int |
255 |
< |
smTriangulate_elist_new(sm,id,plist,add_ptr) |
255 |
> |
smTriangulate(sm,id,plist,add_ptr) |
256 |
|
SM *sm; |
257 |
|
int id; |
258 |
|
LIST *plist,**add_ptr; |
259 |
|
{ |
260 |
|
LIST *l,*prev,*t; |
261 |
|
FVECT v0,v1,v2,n,p; |
262 |
< |
int is_tri,loop,t_id,id0,id1,id2,e2,eprev,enext; |
262 |
> |
int is_tri,is_convex,cut,t_id,id0,id1,id2,e2,e1,enew; |
263 |
|
double dp; |
264 |
|
|
265 |
< |
smDir(sm,p,id); |
266 |
< |
enext=0; |
267 |
< |
is_tri= loop = FALSE; |
265 |
> |
VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm)); |
266 |
> |
enew = 0; |
267 |
> |
is_convex = TRUE; |
268 |
> |
cut = is_tri= FALSE; |
269 |
|
l = prev = plist; |
270 |
< |
/* get v0,v1,v2 */ |
271 |
< |
eprev = (int)LIST_DATA(l); |
272 |
< |
id0 = E_NTH_VERT(eprev,0); |
273 |
< |
id1 = E_NTH_VERT(eprev,1); |
274 |
< |
smDir(sm,v0,id0); |
275 |
< |
smDir(sm,v1,id1); |
270 |
> |
|
271 |
> |
/* get v0,v1 */ |
272 |
> |
e1 = (int)LIST_DATA(l); |
273 |
> |
id0 = E_NTH_VERT(e1,0); |
274 |
> |
id1 = E_NTH_VERT(e1,1); |
275 |
> |
VSUB(v0,SM_NTH_WV(sm,id0),SM_VIEW_CENTER(sm)); |
276 |
> |
VSUB(v1,SM_NTH_WV(sm,id1),SM_VIEW_CENTER(sm)); |
277 |
> |
#ifdef TEST_DRIVER |
278 |
> |
Del = TRUE; |
279 |
> |
VCOPY(B_V[0],v0); |
280 |
> |
VCOPY(B_V[1],v1); |
281 |
> |
Bcnt = 2; |
282 |
> |
Ncnt = 0; |
283 |
> |
#endif |
284 |
|
while(l) |
285 |
|
{ |
286 |
|
l = LIST_NEXT(l); |
287 |
+ |
/* Get v2 */ |
288 |
|
e2 = (int)LIST_DATA(l); |
289 |
|
id2 = E_NTH_VERT(e2,1); |
290 |
< |
/* Check if have a triangle */ |
290 |
> |
VSUB(v2,SM_NTH_WV(sm,id2),SM_VIEW_CENTER(sm)); |
291 |
> |
#ifdef TEST_DRIVER |
292 |
> |
VCOPY(B_V[Bcnt++],v2); |
293 |
> |
#endif |
294 |
|
if(LIST_NEXT(LIST_NEXT(l)) == prev) |
295 |
< |
{ |
296 |
< |
is_tri = TRUE; |
297 |
< |
break; |
295 |
> |
{/* Check if have a triangle */ |
296 |
> |
is_tri = TRUE; |
297 |
> |
break; |
298 |
|
} |
299 |
< |
if(LIST_NEXT(l) == plist) |
299 |
> |
|
300 |
> |
/* determine if v0-v1-v2 is convex:defined clockwise on the sphere- |
301 |
> |
so switch orientation |
302 |
> |
*/ |
303 |
> |
if(convex_angle(v2,v1,v0)) |
304 |
|
{ |
305 |
< |
if(!loop) |
306 |
< |
loop = 1; |
307 |
< |
else |
308 |
< |
loop++; |
309 |
< |
if(loop > 3) |
310 |
< |
break; |
305 |
> |
/* test if safe to cut off v0-v1-v2 by testing if p lies outside of |
306 |
> |
triangle v0-v1-v2: if so, because plist is the star polygon around p, |
307 |
> |
the new edge v2-v0 cannot intersect any existing edges |
308 |
> |
*/ |
309 |
> |
VCROSS(n,v0,v2); |
310 |
> |
dp = DOT(n,p); |
311 |
> |
if(dp <= 0.0) |
312 |
> |
{ |
313 |
> |
/* remove edges e1,e2 and add triangle id0,id1,id2 */ |
314 |
> |
enew = 0; |
315 |
> |
t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew); |
316 |
> |
cut = TRUE; |
317 |
> |
*add_ptr = push_data(*add_ptr,t_id); |
318 |
> |
/* Insert edge enew into the list, reuse prev list element */ |
319 |
> |
LIST_NEXT(prev) = LIST_NEXT(l); |
320 |
> |
LIST_DATA(prev) = e1 = -enew; |
321 |
> |
/* If removing head of list- reset plist pointer */ |
322 |
> |
if(l== plist) |
323 |
> |
plist = prev; |
324 |
> |
/* free list element for e2 */ |
325 |
> |
LIST_NEXT(l)=NULL; |
326 |
> |
free_list(l); |
327 |
> |
l = prev; |
328 |
> |
VCOPY(v1,v2); |
329 |
> |
id1 = id2; |
330 |
> |
continue; |
331 |
> |
} |
332 |
|
} |
333 |
< |
smDir(sm,v2,id2); |
334 |
< |
/* determine if convex (left turn), or concave(right turn) angle */ |
335 |
< |
if(!convex_angle(v0,v1,v2)) |
499 |
< |
{ |
500 |
< |
VCOPY(v0,v1); |
501 |
< |
VCOPY(v1,v2); |
502 |
< |
id0 = id1; |
503 |
< |
id1 = id2; |
504 |
< |
prev = l; |
505 |
< |
eprev = e2; |
506 |
< |
continue; |
507 |
< |
} |
508 |
< |
VCROSS(n,v0,v2); |
509 |
< |
dp = DOT(n,p); |
510 |
< |
if(loop <=1 && (!ZERO(dp) && dp < 0.0)) |
511 |
< |
{ |
512 |
< |
VCOPY(v0,v1); |
513 |
< |
VCOPY(v1,v2); |
514 |
< |
id0 = id1; |
515 |
< |
id1 = id2; |
516 |
< |
eprev = e2; |
517 |
< |
prev = l; |
518 |
< |
continue; |
519 |
< |
} |
520 |
< |
loop = FALSE; |
521 |
< |
|
522 |
< |
enext = 0; |
523 |
< |
t_id = smTriangulate_add_tri(sm,id0,id1,id2,eprev,e2,&enext); |
524 |
< |
*add_ptr = push_data(*add_ptr,t_id); |
525 |
< |
|
526 |
< |
LIST_NEXT(prev) = LIST_NEXT(l); |
527 |
< |
LIST_DATA(prev) = eprev = -enext; |
528 |
< |
LIST_NEXT(l)=NULL; |
529 |
< |
if(l== plist) |
530 |
< |
plist = prev; |
531 |
< |
free_list(l); |
532 |
< |
l = prev; |
333 |
> |
else |
334 |
> |
is_convex = FALSE; |
335 |
> |
VCOPY(v0,v1); |
336 |
|
VCOPY(v1,v2); |
337 |
+ |
id0 = id1; |
338 |
|
id1 = id2; |
339 |
+ |
e1 = e2; |
340 |
+ |
/* check if gone around circular list without adding any |
341 |
+ |
triangles: prevent infinite loop */ |
342 |
+ |
if(l == plist) |
343 |
+ |
{ |
344 |
+ |
if(LIST_NEXT(LIST_NEXT(l)) == prev) |
345 |
+ |
{/* Check if have a triangle */ |
346 |
+ |
is_tri = TRUE; |
347 |
+ |
break; |
348 |
+ |
} |
349 |
+ |
|
350 |
+ |
if(is_convex) |
351 |
+ |
break; |
352 |
+ |
if(!cut) |
353 |
+ |
{ |
354 |
+ |
#ifdef DEBUG |
355 |
+ |
eputs("smTriangulate():Unable to triangulate\n"); |
356 |
+ |
#endif |
357 |
+ |
free_list(l); |
358 |
+ |
while(*add_ptr) |
359 |
+ |
{ |
360 |
+ |
t_id = pop_list(add_ptr); |
361 |
+ |
smDelete_tri(sm,t_id); |
362 |
+ |
} |
363 |
+ |
return(FALSE); |
364 |
+ |
} |
365 |
+ |
cut = FALSE; |
366 |
+ |
is_convex = TRUE; |
367 |
+ |
} |
368 |
+ |
prev = l; |
369 |
|
} |
370 |
|
if(is_tri) |
371 |
|
{ |
372 |
|
l = LIST_NEXT(l); |
373 |
< |
enext = (int)LIST_DATA(l); |
374 |
< |
t_id = smTriangulate_add_tri(sm,id0,id1,id2,eprev,e2,&enext); |
373 |
> |
enew = (int)LIST_DATA(l); |
374 |
> |
t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew); |
375 |
|
*add_ptr = push_data(*add_ptr,t_id); |
376 |
|
free_list(l); |
377 |
< |
} |
377 |
> |
} |
378 |
|
else |
379 |
< |
{ |
546 |
< |
#ifdef DEBUG |
547 |
< |
eputs("smTriangulate_elist()Unable to triangulate\n"); |
548 |
< |
#endif |
379 |
> |
if(!smTriangulateConvex(sm,l,add_ptr)) |
380 |
|
return(FALSE); |
550 |
– |
} |
551 |
– |
return(TRUE); |
552 |
– |
} |
381 |
|
|
382 |
< |
int |
383 |
< |
smTriangulate(sm,p_id,plist,add_ptr) |
556 |
< |
SM *sm; |
557 |
< |
int p_id; |
558 |
< |
LIST *plist,**add_ptr; |
559 |
< |
{ |
560 |
< |
int e,id_t0,id_t1,e0,e1; |
561 |
< |
int test; |
562 |
< |
|
563 |
< |
test = smTriangulate_elist_new(sm,p_id,plist,add_ptr); |
564 |
< |
#if 0 |
565 |
< |
test = smTriangulate_elist(sm,plist,add_ptr); |
566 |
< |
#endif |
567 |
< |
|
568 |
< |
if(!test) |
569 |
< |
return(test); |
570 |
< |
|
571 |
< |
FOR_ALL_EDGES(e) |
382 |
> |
/* Set triangle adjacencies based on edge adjacencies */ |
383 |
> |
FOR_ALL_EDGES(enew) |
384 |
|
{ |
385 |
< |
id_t0 = E_NTH_TRI(e,0); |
386 |
< |
id_t1 = E_NTH_TRI(e,1); |
575 |
< |
if((id_t0==INVALID) || (id_t1==INVALID)) |
576 |
< |
{ |
577 |
< |
#ifdef DEBUG |
578 |
< |
eputs("smTriangulate(): Unassigned edge neighbor\n"); |
579 |
< |
#endif |
580 |
< |
continue; |
581 |
< |
} |
385 |
> |
id0 = E_NTH_TRI(enew,0); |
386 |
> |
id1 = E_NTH_TRI(enew,1); |
387 |
|
|
388 |
< |
e0 = T_WHICH_V(SM_NTH_TRI(sm,id_t0),E_NTH_VERT(e,0)); |
389 |
< |
T_NTH_NBR(SM_NTH_TRI(sm,id_t0),e0) = id_t1; |
390 |
< |
|
391 |
< |
e1 = T_WHICH_V(SM_NTH_TRI(sm,id_t1),E_NTH_VERT(e,1)); |
392 |
< |
T_NTH_NBR(SM_NTH_TRI(sm,id_t1),e1) = id_t0; |
388 |
> |
e1 = (T_WHICH_V(SM_NTH_TRI(sm,id0),E_NTH_VERT(enew,0))+2)%3; |
389 |
> |
T_NTH_NBR(SM_NTH_TRI(sm,id0),e1) = id1; |
390 |
> |
|
391 |
> |
e2 = (T_WHICH_V(SM_NTH_TRI(sm,id1),E_NTH_VERT(enew,1))+2)%3; |
392 |
> |
T_NTH_NBR(SM_NTH_TRI(sm,id1),e2) = id0; |
393 |
|
} |
394 |
< |
return(test); |
394 |
> |
return(TRUE); |
395 |
|
} |
396 |
|
|
397 |
|
eIn_tri(e,t) |
406 |
|
return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,2)==E_NTH_VERT(e,1)); |
407 |
|
else if(T_NTH_V(t,2)==E_NTH_VERT(e,0)) |
408 |
|
return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,1)==E_NTH_VERT(e,1)); |
409 |
+ |
|
410 |
|
return(FALSE); |
411 |
|
} |
412 |
|
|
413 |
< |
smFix_edges(sm,add_list,delptr) |
413 |
> |
/* Test the new set of triangles for Delaunay condition. 'Edges' contains |
414 |
> |
all of the new edges added. The CCW triangle assoc with each edge is |
415 |
> |
tested against the opposite vertex of the CW triangle. If the vertex |
416 |
> |
lies inside the circle defined by the CCW triangle- the edge is swapped |
417 |
> |
for the opposite diagonal |
418 |
> |
*/ |
419 |
> |
smFixEdges(sm,add_list,delptr) |
420 |
|
SM *sm; |
421 |
|
LIST *add_list; |
422 |
|
QUADTREE *delptr; |
425 |
|
int e,t0_id,t1_id,e_new,e0,e1,e0_next,e1_next; |
426 |
|
int i,v0_id,v1_id,v2_id,p_id,t0_nid,t1_nid; |
427 |
|
FVECT v0,v1,v2,p,np,v; |
428 |
+ |
TRI *t0,*t1; |
429 |
|
|
430 |
|
FOR_ALL_EDGES(e) |
431 |
|
{ |
434 |
|
if((t0_id==INVALID) || (t1_id==INVALID)) |
435 |
|
{ |
436 |
|
#ifdef DEBUG |
437 |
< |
eputs("smFix_edges: Unassigned edge nbr\n"); |
437 |
> |
error(CONSISTENCY,"smFix_edges: Unassigned edge nbr\n"); |
438 |
|
#endif |
626 |
– |
continue; |
439 |
|
} |
440 |
< |
e0 = T_WHICH_V(SM_NTH_TRI(sm,t0_id),E_NTH_VERT(e,0)); |
441 |
< |
e1 = T_WHICH_V(SM_NTH_TRI(sm,t1_id),E_NTH_VERT(-e,0)); |
442 |
< |
e0_next = (e0+2)%3; |
443 |
< |
e1_next = (e1+2)%3; |
440 |
> |
t0 = SM_NTH_TRI(sm,t0_id); |
441 |
> |
t1 = SM_NTH_TRI(sm,t1_id); |
442 |
> |
e0 = T_NTH_NBR_PTR(t1_id,t0); |
443 |
> |
e1 = T_NTH_NBR_PTR(t0_id,t1); |
444 |
> |
|
445 |
|
v0_id = E_NTH_VERT(e,0); |
446 |
|
v1_id = E_NTH_VERT(e,1); |
447 |
< |
v2_id = T_NTH_V(SM_NTH_TRI(sm,t0_id),e0_next); |
448 |
< |
p_id = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1_next); |
447 |
> |
v2_id = T_NTH_V(t0,e0); |
448 |
> |
p_id = T_NTH_V(t1,e1); |
449 |
|
|
450 |
|
smDir_in_cone(sm,v0,v0_id); |
451 |
|
smDir_in_cone(sm,v1,v1_id); |
458 |
|
smTris_swap_edge(sm,t0_id,t1_id,e0,e1,&t0_nid,&t1_nid,&add_list, |
459 |
|
delptr); |
460 |
|
|
461 |
+ |
/* Adjust the triangle pointers of the remaining edges to be |
462 |
+ |
processed |
463 |
+ |
*/ |
464 |
|
FOR_ALL_EDGES_FROM(e,i) |
465 |
|
{ |
466 |
|
if(E_NTH_TRI(i,0)==t0_id || E_NTH_TRI(i,0)==t1_id) |
488 |
|
SET_E_NTH_TRI(e_new,1,t1_id); |
489 |
|
} |
490 |
|
} |
491 |
+ |
/* Add/Delete the appropriate triangles from the stree */ |
492 |
|
smUpdate_locator(sm,add_list,qtqueryset(*delptr)); |
493 |
+ |
|
494 |
|
} |
495 |
|
|
496 |
+ |
/* Remove vertex "id" from the mesh- and retriangulate the resulting |
497 |
+ |
hole: Returns TRUE if successful, FALSE otherwise. |
498 |
+ |
*/ |
499 |
|
int |
500 |
< |
smMesh_remove_vertex(sm,id) |
500 |
> |
smRemoveVertex(sm,id) |
501 |
|
SM *sm; |
502 |
|
int id; |
503 |
|
{ |
504 |
+ |
LIST *b_list,*add_list; |
505 |
+ |
QUADTREE delnode=-1; |
506 |
|
int t_id; |
507 |
< |
LIST *elist,*add_list; |
508 |
< |
int cnt,debug; |
509 |
< |
QUADTREE delnode; |
687 |
< |
/* generate list of vertices that form the boundary of the |
688 |
< |
star polygon formed by vertex id and all of its adjacent |
689 |
< |
triangles |
507 |
> |
|
508 |
> |
/* generate list of edges that form the boundary of the |
509 |
> |
polygon formed by the triangles adjacent to vertex 'id' |
510 |
|
*/ |
511 |
< |
eClear_edges(); |
692 |
< |
elist = smVertex_star_polygon(sm,id,&delnode); |
511 |
> |
b_list = smVertexPolygon(sm,id,&delnode); |
512 |
|
|
694 |
– |
if(!elist) |
695 |
– |
{ |
696 |
– |
#ifdef DEBUG |
697 |
– |
eputs("smMesh_remove_vertex(): Unable to remove vertex"); |
698 |
– |
#endif |
699 |
– |
qtfreeleaf(delnode); |
700 |
– |
return(FALSE); |
701 |
– |
} |
513 |
|
add_list = NULL; |
514 |
< |
/* Triangulate spherical polygon */ |
515 |
< |
if(!smTriangulate(sm,id,elist,&add_list)) |
514 |
> |
/* Triangulate polygonal hole */ |
515 |
> |
if(!smTriangulate(sm,id,b_list,&add_list)) |
516 |
|
{ |
706 |
– |
while(add_list) |
707 |
– |
{ |
708 |
– |
t_id = pop_list(&add_list); |
709 |
– |
smDelete_tri(sm,t_id); |
710 |
– |
} |
517 |
|
qtfreeleaf(delnode); |
518 |
|
return(FALSE); |
519 |
|
} |
520 |
< |
/* Fix up new triangles to be Delaunay */ |
521 |
< |
smFix_edges(sm,add_list,&delnode); |
520 |
> |
/* Fix up new triangles to be Delaunay-delnode contains set of |
521 |
> |
triangles to delete,add_list is the set of new triangles to add |
522 |
> |
*/ |
523 |
> |
smFixEdges(sm,add_list,&delnode); |
524 |
> |
|
525 |
|
|
526 |
|
qtfreeleaf(delnode); |
527 |
|
return(TRUE); |