107 |
|
char *type,*which; |
108 |
|
{ |
109 |
|
int i,d,j,id; |
110 |
< |
QUADTREE *rootptr,qt; |
110 |
> |
QUADTREE *rootptr,*qtptr; |
111 |
|
FVECT v1,v2,v3; |
112 |
|
OBJECT os[MAXSET+1],*optr; |
113 |
|
char w; |
119 |
|
rootptr = ST_NTH_ROOT_PTR(st,i); |
120 |
|
stNth_base_verts(st,i,v1,v2,v3); |
121 |
|
/* Return tri that p falls in */ |
122 |
< |
qt = qtRoot_point_locate(rootptr,v1,v2,v3,npt,type,which); |
123 |
< |
if(QT_IS_EMPTY(qt)) |
122 |
> |
qtptr = qtRoot_point_locate(rootptr,v1,v2,v3,npt,NULL,NULL,NULL); |
123 |
> |
if(!qtptr) |
124 |
|
continue; |
125 |
|
/* Get the set */ |
126 |
< |
qtgetset(os,qt); |
126 |
> |
qtgetset(os,*qtptr); |
127 |
|
for (j = QT_SET_CNT(os),optr = QT_SET_PTR(os); j > 0; j--) |
128 |
|
{ |
129 |
|
/* Find the first triangle that pt falls */ |
147 |
|
return(EMPTY); |
148 |
|
} |
149 |
|
|
150 |
< |
int |
151 |
< |
stPoint_locate_cell(st,p,type,which) |
150 |
> |
QUADTREE |
151 |
> |
*stPoint_locate_cell(st,p,t0,t1,t2) |
152 |
|
STREE *st; |
153 |
|
FVECT p; |
154 |
< |
char *type,*which; |
154 |
> |
FVECT t0,t1,t2; |
155 |
|
{ |
156 |
|
int i,d; |
157 |
< |
QUADTREE *rootptr,qt; |
157 |
> |
QUADTREE *rootptr,*qtptr; |
158 |
|
FVECT v0,v1,v2; |
159 |
|
|
160 |
|
|
164 |
|
rootptr = ST_NTH_ROOT_PTR(st,i); |
165 |
|
stNth_base_verts(st,i,v0,v1,v2); |
166 |
|
/* Return tri that p falls in */ |
167 |
< |
qt = qtRoot_point_locate(rootptr,v0,v1,v2,p,type,which); |
167 |
> |
qtptr = qtRoot_point_locate(rootptr,v0,v1,v2,p,t0,t1,t2); |
168 |
|
/* NOTE: For now return only one triangle */ |
169 |
< |
if(!QT_IS_EMPTY(qt)) |
170 |
< |
return(qt); |
169 |
> |
if(qtptr) |
170 |
> |
return(qtptr); |
171 |
|
} /* Point not found */ |
172 |
< |
if(which) |
173 |
< |
*which = 0; |
174 |
< |
if(type) |
175 |
< |
*type = 0; |
176 |
< |
return(EMPTY); |
172 |
> |
return(NULL); |
173 |
|
} |
174 |
|
|
175 |
+ |
|
176 |
+ |
QUADTREE |
177 |
+ |
*stAdd_tri_from_pt(st,p,t_id) |
178 |
+ |
STREE *st; |
179 |
+ |
FVECT p; |
180 |
+ |
int t_id; |
181 |
+ |
{ |
182 |
+ |
int i,d; |
183 |
+ |
QUADTREE *rootptr,*qtptr; |
184 |
+ |
FVECT v0,v1,v2; |
185 |
+ |
|
186 |
+ |
|
187 |
+ |
/* Test each of the root triangles against point id */ |
188 |
+ |
for(i=0; i < 4; i++) |
189 |
+ |
{ |
190 |
+ |
rootptr = ST_NTH_ROOT_PTR(st,i); |
191 |
+ |
stNth_base_verts(st,i,v0,v1,v2); |
192 |
+ |
/* Return tri that p falls in */ |
193 |
+ |
qtptr = qtRoot_add_tri_from_point(rootptr,v0,v1,v2,p,t_id); |
194 |
+ |
/* NOTE: For now return only one triangle */ |
195 |
+ |
if(qtptr) |
196 |
+ |
return(qtptr); |
197 |
+ |
} /* Point not found */ |
198 |
+ |
return(NULL); |
199 |
+ |
} |
200 |
+ |
|
201 |
|
int |
202 |
|
stAdd_tri(st,id,v0,v1,v2) |
203 |
|
STREE *st; |
214 |
|
{ |
215 |
|
rootptr = ST_NTH_ROOT_PTR(st,i); |
216 |
|
stNth_base_verts(st,i,t0,t1,t2); |
217 |
< |
found |= qtAdd_tri(rootptr,id,v0,v1,v2,t0,t1,t2,0); |
217 |
> |
found |= qtRoot_add_tri(rootptr,id,v0,v1,v2,t0,t1,t2,0); |
218 |
|
} |
219 |
|
return(found); |
220 |
|
} |
268 |
|
|
269 |
|
|
270 |
|
|
271 |
+ |
#if 0 |
272 |
+ |
int |
273 |
+ |
stAdd_tri_opt(st,id,v0,v1,v2) |
274 |
+ |
STREE *st; |
275 |
+ |
int id; |
276 |
+ |
FVECT v0,v1,v2; |
277 |
+ |
{ |
278 |
+ |
|
279 |
+ |
int i,found; |
280 |
+ |
QUADTREE *qtptr; |
281 |
+ |
FVECT pt,t0,t1,t2; |
282 |
+ |
|
283 |
+ |
/* First add all of the leaf cells lying on the triangle perimeter: |
284 |
+ |
mark all cells seen on the way |
285 |
+ |
*/ |
286 |
+ |
/* clear all of the flags */ |
287 |
+ |
qtClearAllFlags(); /* clear all quadtree branch flags */ |
288 |
+ |
|
289 |
+ |
/* Now trace each triangle edge-marking cells visited, and adding tri to |
290 |
+ |
the leafs |
291 |
+ |
*/ |
292 |
+ |
stAdd_tri_from_pt(st,v0,id,t0,t1,t2); |
293 |
+ |
/* Find next cell that projection of ray intersects */ |
294 |
+ |
VCOPY(pt,v0); |
295 |
+ |
/* NOTE: Check if in same cell */ |
296 |
+ |
while(traceEdge(pt,v1,t0,t1,t2,pt)) |
297 |
+ |
{ |
298 |
+ |
stAdd_tri_from_pt(st,pt,id,t0,t1,t2); |
299 |
+ |
traceEdge(pt,v1,t0,t1,t2,pt); |
300 |
+ |
} |
301 |
+ |
while(traceEdge(pt,v2,t0,t1,t2,pt)) |
302 |
+ |
{ |
303 |
+ |
stAdd_tri_from_pt(st,pt,id,t0,t1,t2); |
304 |
+ |
traceEdge(pt,v2,t0,t1,t2,pt); |
305 |
+ |
} |
306 |
+ |
while(traceEdge(pt,v0,t0,t1,t2,pt)) |
307 |
+ |
{ |
308 |
+ |
stAdd_tri_from_pt(st,pt,id,t0,t1,t2); |
309 |
+ |
traceEdge(pt,v2,t0,t1,t2,pt); |
310 |
+ |
} |
311 |
+ |
|
312 |
+ |
/* NOTE: Optimization: if <= 2 cells added: dont need to fill */ |
313 |
+ |
/* Traverse: follow nodes with flag set or one vertex in triangle */ |
314 |
+ |
|
315 |
+ |
} |
316 |
+ |
|
317 |
+ |
#endif |