00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041 #include <stdio.h>
00042 #include <math.h>
00043 #include "memvirtu.h"
00044 #include "lowparam.h"
00045 #include "lowmacro.h"
00046 #include "lowsolid.h"
00047 #include "vectorop.h"
00048 #include "splsplit.h"
00049 #include "lowgeome.h"
00050
00051
00052 int MSD_lowVtxVtxContainment(VPTYPE v1, VPTYPE v2)
00053 {
00054 vector vv1, vv2;
00055
00056 veccopy(vv1, VerVCoord(v1));
00057 veccopy(vv2, VerVCoord(v2));
00058 return(vecequal(vv1, vv2));
00059 }
00060
00061
00062 int MSD_lowEdgVtxIntersection(VPTYPE v1, VPTYPE v2, VPTYPE v3, real *t)
00063 {
00064 #ifndef __VIRTUAL_MEM
00065 VTYPE v4;
00066 #else
00067 VPTYPE v4;
00068 int flag;
00069 #endif
00070 vector r1, r2, vv1, vv2;
00071 real r1r1;
00072
00073 veccopy(vv1, VerVCoord(v1));
00074 veccopy(vv2, VerVCoord(v2));
00075 vecminus(r1, vv2, vv1);
00076 if ((r1r1 = dot(r1, r1)) < EPS * EPS)
00077 {
00078 *t = 0.0;
00079 return(MSD_lowVtxVtxContainment(v1, v3));
00080 }
00081 else
00082 {
00083 vecminus(r2, VerVCoord(v3), vv1);
00084 #ifndef __VIRTUAL_MEM
00085 vecpe(r1, vv1, v4.vcoord, (*t = dot(r1, r2) / r1r1));
00086 return(MSD_lowVtxVtxContainment(&v4, v3));
00087
00088 #else
00089 v4 = MSD_getMemVirtual(VERTEX);
00090 vecpe(r1, vv1, VerVCoord(v4), (*t = dot(r1, r2) / r1r1));
00091 flag = MSD_lowVtxVtxContainment(v4, v3);
00092 MSD_putMemVirtual(v4, VERTEX);
00093 return(flag);
00094 #endif
00095
00096 }
00097 }
00098
00099
00100 int MSD_lowEdgVtxContainment(VPTYPE v1, VPTYPE v2, VPTYPE v3)
00101 {
00102 real t;
00103
00104 if (MSD_lowEdgVtxIntersection(v1, v2, v3, &t))
00105 {
00106 if ((t >= -EPS) && (t <= 1.0 + EPS))
00107 {
00108 return(TRUE);
00109 }
00110 }
00111 return(FALSE);
00112 }
00113
00114
00115
00116
00117 int MSD_lowFacVtxContainment(FPTYPE f, VPTYPE v)
00118 {
00119 if (FaceEqNOK(f))
00120 {
00121 MSD_lowFaceEq(FacFLOut(f), FacFeq(f));
00122 }
00123 return(MSD_lowFacVtxCoordContainment(f, v, getdrop(FacFeq(f))));
00124 }
00125
00126 int MSD_lowFacVtxCoordContainment(FPTYPE f, VPTYPE v, int drop)
00127 {
00128 LPTYPE l;
00129 int cont;
00130
00131 if ((cont = MSD_lowLooVtxContainment(FacFLOut(f), v, drop)) != 1)
00132 {
00133 return(cont);
00134 }
00135 for (AllLoopsFace(f, l))
00136 {
00137 if (l != FacFLOut(f))
00138 {
00139 if ((cont = MSD_lowLooVtxContainment(l, v, drop)) == 1)
00140 {
00141 return(0);
00142 }
00143 if (cont != 0)
00144 {
00145 return(cont);
00146 }
00147 }
00148 }
00149 return(1);
00150 }
00151
00152
00153 int MSD_lowLooVtxBoundary(LPTYPE l, VPTYPE v)
00154 {
00155 HPTYPE he;
00156
00157 he = LooLEdg(l);
00158 do
00159 {
00160 if (MSD_lowVtxVtxContainment(HalVtx(he), v))
00161 {
00162 hitvertex = HalVtx(he);
00163 hithe = HNIL;
00164 return(3);
00165 }
00166 } while ((he = HalNxt(he)) != LooLEdg(l));
00167 he = LooLEdg(l);
00168 do
00169 {
00170 if (MSD_lowEdgVtxContainment(HalVtx(he), HalVtx(HalNxt(he)), v))
00171 {
00172 hitvertex = VNIL;
00173 hithe = he;
00174 return(2);
00175 }
00176 } while ((he = HalNxt(he)) != LooLEdg(l));
00177 return(0);
00178 }
00179
00180 int MSD_lowEdgEdgIntersection(VPTYPE v1, VPTYPE v2, VPTYPE v3, VPTYPE v4,
00181 int drop, real *t1, real *t2)
00182 {
00183 real D, a1, a2, b1, b2, c1, c2;
00184
00185 switch (drop)
00186 {
00187 case X:
00188 a1 = VerVCoord(v2)[1] - VerVCoord(v1)[1];
00189 a2 = VerVCoord(v2)[2] - VerVCoord(v1)[2];
00190 b1 = VerVCoord(v3)[1] - VerVCoord(v4)[1];
00191 b2 = VerVCoord(v3)[2] - VerVCoord(v4)[2];
00192 c1 = VerVCoord(v1)[1] - VerVCoord(v3)[1];
00193 c2 = VerVCoord(v1)[2] - VerVCoord(v3)[2];
00194 break;
00195
00196 case Y:
00197 a1 = VerVCoord(v2)[0] - VerVCoord(v1)[0];
00198 a2 = VerVCoord(v2)[2] - VerVCoord(v1)[2];
00199 b1 = VerVCoord(v3)[0] - VerVCoord(v4)[0];
00200 b2 = VerVCoord(v3)[2] - VerVCoord(v4)[2];
00201 c1 = VerVCoord(v1)[0] - VerVCoord(v3)[0];
00202 c2 = VerVCoord(v1)[2] - VerVCoord(v3)[2];
00203 break;
00204
00205 case Z:
00206 a1 = VerVCoord(v2)[0] - VerVCoord(v1)[0];
00207 a2 = VerVCoord(v2)[1] - VerVCoord(v1)[1];
00208 b1 = VerVCoord(v3)[0] - VerVCoord(v4)[0];
00209 b2 = VerVCoord(v3)[1] - VerVCoord(v4)[1];
00210 c1 = VerVCoord(v1)[0] - VerVCoord(v3)[0];
00211 c2 = VerVCoord(v1)[1] - VerVCoord(v3)[1];
00212 break;
00213 }
00214
00215 if (comp(D = a1 * b2 - a2 * b1, 0.0, EPS) == 0)
00216 {
00217 return(0);
00218 }
00219 *t1 = (c2 * b1 - c1 * b2) / D;
00220 *t2 = (a2 * c1 - a1 * c2) / D;
00221 return(1);
00222 }
00223
00224
00225 int MSD_lowLooVtxContainment(LPTYPE l, VPTYPE v, int drop)
00226 {
00227 HPTYPE he1;
00228 HPTYPE he2;
00229 VPTYPE v1;
00230 VPTYPE v2;
00231
00232 #ifndef __VIRTUAL_MEM
00233 VTYPE aux;
00234 #else
00235 VPTYPE aux;
00236 #endif
00237 real t1, t2;
00238 int count, intr, c1, c2, ip;
00239 vector vv1, vv2;
00240
00241 if ((intr = MSD_lowLooVtxBoundary(l, v)) > 0)
00242 {
00243 return(intr);
00244 }
00245 he2 = LooLEdg(l);
00246
00247 #ifdef __VIRTUAL_MEM
00248 aux = MSD_getMemVirtual(VERTEX);
00249 #endif
00250
00251 do
00252 {
00253 he1 = LooLEdg(l);
00254 v1 = HalVtx(he2);
00255 v2 = HalVtx(HalNxt(he2));
00256 veccopy(vv1, VerVCoord(v1));
00257 veccopy(vv2, VerVCoord(v2));
00258
00259 #ifndef __VIRTUAL_MEM
00260 vecplus(aux.vcoord, vv1, vv2);
00261 vecesc(aux.vcoord, aux.vcoord, 0.5);
00262 #else
00263 vecplus(VerVCoord(aux), vv1, vv2);
00264 vecesc(VerVCoord(aux), VerVCoord(aux), 0.5);
00265 #endif
00266
00267 count = 0;
00268 do
00269 {
00270 ip = 1;
00271 v1 = HalVtx(he1);
00272 v2 = HalVtx(HalNxt(he1));
00273
00274 #ifndef __VIRTUAL_MEM
00275 if ((intr = MSD_lowEdgEdgIntersection(v, &aux, v1, v2, drop, &t1, &t2)) == 1)
00276 {
00277 #else
00278 if ((intr = MSD_lowEdgEdgIntersection(v, aux, v1, v2, drop, &t1, &t2)) == 1)
00279 {
00280 #endif
00281
00282 c1 = comp(t2, 0.0, EPS);
00283 c2 = comp(t2, 1.0, EPS);
00284 if ((c1 == 0) || (c2 == 0))
00285 {
00286 ip = 0;
00287 }
00288 if ((c1 == 1) && (c2 == -1))
00289 {
00290 if (t1 >= 0.0)
00291 {
00292 count++;
00293 }
00294 }
00295 }
00296 if (ip == 1)
00297 {
00298 he1 = HalNxt(he1);
00299 }
00300 } while (he1 != LooLEdg(l) && ip == 1);
00301 } while ((he2 = HalNxt(he2)) != LooLEdg(l) && ip == 0);
00302
00303 #ifdef __VIRTUAL_MEM
00304 MSD_putMemVirtual(aux, VERTEX);
00305 #endif
00306
00307 if (ip == 0)
00308 {
00309 return(ERROR);
00310 }
00311 return(count % 2);
00312 }
00313
00314
00315 int MSD_lowLooBoxContainment(LPTYPE l, VPTYPE v, int drop)
00316 {
00317 HPTYPE he;
00318 VPTYPE vtx;
00319 real umin, umax, vmin, vmax;
00320
00321 umin = vmin = 1e10;
00322 umax = vmax = -1e10;
00323
00324 he = LooLEdg(l);
00325 do
00326 {
00327 vtx = HalVtx(he);
00328 switch (drop)
00329 {
00330 case X:
00331 if (umin < VerVCoord(vtx)[1])
00332 {
00333 umin = VerVCoord(vtx)[1];
00334 }
00335 if (vmin < VerVCoord(vtx)[2])
00336 {
00337 vmin = VerVCoord(vtx)[2];
00338 }
00339 if (umax > VerVCoord(vtx)[1])
00340 {
00341 umax = VerVCoord(vtx)[1];
00342 }
00343 if (vmax > VerVCoord(vtx)[2])
00344 {
00345 vmax = VerVCoord(vtx)[2];
00346 }
00347 break;
00348
00349 case Y:
00350 if (umin < VerVCoord(vtx)[0])
00351 {
00352 umin = VerVCoord(vtx)[0];
00353 }
00354 if (vmin < VerVCoord(vtx)[2])
00355 {
00356 vmin = VerVCoord(vtx)[2];
00357 }
00358 if (umax > VerVCoord(vtx)[0])
00359 {
00360 umax = VerVCoord(vtx)[0];
00361 }
00362 if (vmax > VerVCoord(vtx)[2])
00363 {
00364 vmax = VerVCoord(vtx)[2];
00365 }
00366 break;
00367
00368 case Z:
00369 if (umin < VerVCoord(vtx)[0])
00370 {
00371 umin = VerVCoord(vtx)[0];
00372 }
00373 if (vmin < VerVCoord(vtx)[1])
00374 {
00375 vmin = VerVCoord(vtx)[1];
00376 }
00377 if (umax > VerVCoord(vtx)[0])
00378 {
00379 umax = VerVCoord(vtx)[0];
00380 }
00381 if (vmax > VerVCoord(vtx)[1])
00382 {
00383 vmax = VerVCoord(vtx)[1];
00384 }
00385 break;
00386 }
00387 } while ((he = HalNxt(he)) != LooLEdg(l));
00388
00389 umin -= CONTBVEPS;
00390 umax += CONTBVEPS;
00391 vmin -= CONTBVEPS;
00392 vmax += CONTBVEPS;
00393
00394 switch (drop)
00395 {
00396 case X:
00397 if ((VerVCoord(v)[1] < umin) || (VerVCoord(v)[1] > umax))
00398 {
00399 return(0);
00400 }
00401 if ((VerVCoord(v)[2] < vmin) || (VerVCoord(v)[2] > vmax))
00402 {
00403 return(0);
00404 }
00405 break;
00406
00407 case Y:
00408 if ((VerVCoord(v)[0] < umin) || (VerVCoord(v)[0] > umax))
00409 {
00410 return(0);
00411 }
00412 if ((VerVCoord(v)[2] < vmin) || (VerVCoord(v)[2] > vmax))
00413 {
00414 return(0);
00415 }
00416 break;
00417
00418 case Z:
00419 if ((VerVCoord(v)[0] < umin) || (VerVCoord(v)[0] > umax))
00420 {
00421 return(0);
00422 }
00423 if ((VerVCoord(v)[1] < vmin) || (VerVCoord(v)[1] > vmax))
00424 {
00425 return(0);
00426 }
00427 break;
00428 }
00429 return(1);
00430 }
00431
00432 int MSD_lowSolVtxContainment(SPTYPE s, VPTYPE v)
00433 {
00434 DPTYPE d;
00435 FPTYPE f;
00436
00437 #ifndef __VIRTUAL_MEM
00438 VTYPE auxv, testv;
00439 #else
00440 VPTYPE auxv, testv;
00441 #endif
00442
00443 real t, d1, d2, min_t, min_d;
00444
00445 #ifndef __VIRTUAL_MEM
00446 auxv.vcoord[0] = VerVCoord(v)[0];
00447 auxv.vcoord[1] = VerVCoord(v)[1];
00448 auxv.vcoord[2] = VerVCoord(v)[2] + 1.0;
00449 #else
00450 auxv = MSD_getMemVirtual(VERTEX);
00451 testv = MSD_getMemVirtual(VERTEX);
00452 VerVCoord(auxv)[0] = VerVCoord(v)[0];
00453 VerVCoord(auxv)[1] = VerVCoord(v)[1];
00454 VerVCoord(auxv)[2] = VerVCoord(v)[2] + 1.0;
00455 #endif
00456
00457 min_t = 1e6;
00458 min_d = 1.0;
00459
00460
00461 for (AllShellsSolid(s, d))
00462 {
00463 for (AllFacesShell(d, f))
00464 {
00465 if (comp(MSD_lowDistancePlanePoint(FacFeq(f), v), 0.0, EPS) == 0)
00466 {
00467 if (MSD_lowFacVtxContainment(f, v) > 0)
00468 {
00469 return(0);
00470 }
00471 }
00472 }
00473 }
00474
00475 for (AllShellsSolid(s, d))
00476 {
00477 for (AllFacesShell(d, f))
00478 {
00479 if (FaceEqNOK(f))
00480 {
00481 MSD_lowFaceEq(FacFLOut(f), FacFeq(f));
00482 }
00483 d1 = MSD_lowDistancePlanePoint(FacFeq(f), v);
00484
00485 #ifndef __VIRTUAL_MEM
00486 d2 = MSD_lowDistancePlanePoint(FacFeq(f), &auxv);
00487 #else
00488 d2 = MSD_lowDistancePlanePoint(FacFeq(f), auxv);
00489 #endif
00490
00491 if (comp(d1 - d2, 0.0, EPS) != 0)
00492 {
00493 t = d1 / (d1 - d2);
00494 if ((t >= 0.0) && (t < min_t))
00495 {
00496 #ifndef __VIRTUAL_MEM
00497 testv.vcoord[0] = VerVCoord(v)[0];
00498 testv.vcoord[1] = VerVCoord(v)[1];
00499 testv.vcoord[2] = VerVCoord(v)[2] +
00500 t * (auxv.vcoord[2] - VerVCoord(v)[2]);
00501 if (MSD_lowFacVtxContainment(f, &testv))
00502 {
00503 #else
00504 VerVCoord(testv)[0] = VerVCoord(v)[0];
00505 VerVCoord(testv)[1] = VerVCoord(v)[1];
00506 VerVCoord(testv)[2] = VerVCoord(v)[2] +
00507 t * (VerVCoord(auxv)[2] - VerVCoord(v)[2]);
00508 if (MSD_lowFacVtxContainment(f, testv))
00509 {
00510 #endif
00511
00512 if ((comp(t, min_t, EPS) == 0) && (min_d > d1))
00513 {
00514 min_d = d1;
00515 }
00516 if (t < min_t)
00517 {
00518 min_t = t;
00519 min_d = d1;
00520 }
00521 }
00522 }
00523 }
00524 }
00525 }
00526 #ifdef __VIRTUAL_MEM
00527 MSD_putMemVirtual(testv, VERTEX);
00528 MSD_putMemVirtual(auxv, VERTEX);
00529 #endif
00530
00531 return(comp(-min_d, 0.0, EPS));
00532 }
00533
00534
00535 int MSD_lowFacFacIdentical(FPTYPE f1, FPTYPE f2)
00536 {
00537 LPTYPE l1;
00538 LPTYPE l2;
00539 HPTYPE he1;
00540 HPTYPE he2;
00541 int flag;
00542
00543 l1 = FacFLOut(f1);
00544 l2 = FacFLOut(f2);
00545 if (LooLength(l1) != LooLength(l2))
00546 {
00547 return(0);
00548 }
00549
00550 flag = 0;
00551 he1 = LooLEdg(l1);
00552 he2 = LooLEdg(l2);
00553 do
00554 {
00555 if (MSD_lowVtxVtxContainment(HalVtx(he1), HalVtx(he2)))
00556 {
00557 flag = 1;
00558 }
00559 } while ((he2 = HalNxt(he2)) != LooLEdg(l2));
00560 if (flag == 0)
00561 {
00562 return(0);
00563 }
00564
00565 do
00566 {
00567 if (!MSD_lowVtxVtxContainment(HalVtx(he1), HalVtx(he2)))
00568 {
00569 return(0);
00570 }
00571 he2 = HalPrv(he2);
00572 } while ((he1 = HalNxt(he1)) != LooLEdg(l1));
00573 return(1);
00574 }
00575
00576
00577 int MSD_lowFacFacContainment(FPTYPE f1, FPTYPE f2)
00578 {
00579 LPTYPE l;
00580 HPTYPE he;
00581
00582 for (AllLoopsFace(f2, l))
00583 {
00584 he = LooLEdg(l);
00585 do
00586 {
00587 if (MSD_lowLooVtxContainment(FacFLOut(f1), HalVtx(he), getdrop(FacFeq(f1))) == FALSE)
00588 {
00589 return(FALSE);
00590 }
00591 } while ((he = HalNxt(he)) != LooLEdg(l));
00592 }
00593 return(TRUE);
00594 }
00595
00596
00597 int MSD_lowFacFacEqualEqs(FPTYPE f1, FPTYPE f2)
00598 {
00599 vector vf1, vf2;
00600
00601 veccopy(vf1, FacFeq(f1));
00602 veccopy(vf2, FacFeq(f2));
00603 if (comp(vf1[3], vf2[3], EPS) == 0)
00604 {
00605 return(vecequal(vf1, vf2));
00606 }
00607 return(FALSE);
00608 }
00609
00610
00611 int MSD_lowFacFacOppositeEqs(FPTYPE f1, FPTYPE f2)
00612 {
00613 vector tmp, vf1, vf2;
00614
00615 veccopy(vf1, FacFeq(f1));
00616 veccopy(vf2, FacFeq(f2));
00617 if (comp(vf1[3], -vf2[3], EPS) == 0)
00618 {
00619 vecplus(tmp, vf1, vf2);
00620 return(vecnull(tmp, EPS));
00621 }
00622 return(0);
00623 }
00624
00625
00626 int MSD_lowEdgEdgColinear(EPTYPE e1, EPTYPE e2)
00627 {
00628 vector dir1, dir2, cr, ve11, ve12, ve21, ve22;
00629
00630 veccopy(ve21, VerVCoord(HalVtx(EdgHe2(e1))));
00631 veccopy(ve11, VerVCoord(HalVtx(EdgHe1(e1))));
00632 veccopy(ve22, VerVCoord(HalVtx(EdgHe2(e2))));
00633 veccopy(ve12, VerVCoord(HalVtx(EdgHe1(e2))));
00634 vecminus(dir1, ve21, ve11);
00635 vecminus(dir2, ve22, ve12);
00636 cross(cr, dir1, dir2);
00637 if (vecnull(cr, EPS))
00638 {
00639 return(1);
00640 }
00641 return(0);
00642 }
00643
00644
00645 int MSD_lowNullEdge(HPTYPE h)
00646 {
00647 return(MSD_lowVtxVtxContainment(HalVtx(h), HalVtx(HalNxt(h))));
00648 }