774 |
|
const MIGRATION *ej; |
775 |
|
RBFNODE *vother[2]; |
776 |
|
int im_rev; |
777 |
< |
/* find shared edge in mesh */ |
777 |
> |
/* find shared edge in mesh */ |
778 |
|
for (ej = pv->ejl; ej != NULL; ej = nextedge(pv,ej)) { |
779 |
|
const RBFNODE *tv = opp_rbf(pv,ej); |
780 |
|
if (tv == bv0) { |
788 |
|
break; |
789 |
|
} |
790 |
|
} |
791 |
< |
if (!get_triangles(vother, ej)) |
791 |
> |
if (!get_triangles(vother, ej)) /* triangle on same side? */ |
792 |
|
return(0); |
793 |
|
return(vother[im_rev] != NULL); |
794 |
|
} |
806 |
|
if (normalize(vejn) == 0 || normalize(vmid) == 0) |
807 |
|
return(NULL); |
808 |
|
/* XXX exhaustive search */ |
809 |
+ |
/* Find triangle with minimum rotation from perpendicular */ |
810 |
|
for (rbf = dsf_list; rbf != NULL; rbf = rbf->next) { |
811 |
|
if ((rbf == rbf0) | (rbf == rbf1)) |
812 |
|
continue; |
813 |
|
tri_orient(vp, rbf0->invec, rbf1->invec, rbf->invec); |
814 |
|
if (DOT(vp, vmid) <= FTINY) |
815 |
|
continue; /* wrong orientation */ |
816 |
< |
area2 = DOT(vp,vp); |
816 |
> |
area2 = .25*DOT(vp,vp); |
817 |
|
VSUB(vp, rbf->invec, rbf0->invec); |
818 |
|
dprod = -DOT(vp, vejn); |
819 |
< |
VSUM(vp, vp, vejn, dprod); |
819 |
> |
VSUM(vp, vp, vejn, dprod); /* above guarantees non-zero */ |
820 |
|
dprod = DOT(vp, vmid) / VLEN(vp); |
821 |
|
if (dprod <= bestdprod + FTINY*(1 - 2*(area2 < bestarea2))) |
822 |
|
continue; /* found better already */ |
874 |
|
#ifdef DEBUG |
875 |
|
#include "random.h" |
876 |
|
#include "bmpfile.h" |
877 |
< |
/* Hash pointer to byte value */ |
877 |
> |
/* Hash pointer to byte value (must return 0 for NULL) */ |
878 |
|
static int |
879 |
|
byte_hash(const void *p) |
880 |
|
{ |
896 |
|
hdr->compr = BI_RLE8; |
897 |
|
for (i = 256; --i; ) { /* assign random color map */ |
898 |
|
hdr->palette[i].r = random() & 0xff; |
899 |
< |
hdr->palette[i].r = random() & 0xff; |
900 |
< |
hdr->palette[i].r = random() & 0xff; |
899 |
> |
hdr->palette[i].g = random() & 0xff; |
900 |
> |
hdr->palette[i].b = random() & 0xff; |
901 |
> |
/* reject dark colors */ |
902 |
> |
i += (hdr->palette[i].r + hdr->palette[i].g + |
903 |
> |
hdr->palette[i].b < 128); |
904 |
|
} |
905 |
|
hdr->palette[0].r = hdr->palette[0].g = hdr->palette[0].b = 0; |
906 |
|
/* open output */ |
1041 |
|
return(1); /* this neighborhood done */ |
1042 |
|
} |
1043 |
|
|
1044 |
+ |
/* Insert vertex in ordered list */ |
1045 |
+ |
static void |
1046 |
+ |
insert_vert(RBFNODE **vlist, RBFNODE *v) |
1047 |
+ |
{ |
1048 |
+ |
int i, j; |
1049 |
+ |
|
1050 |
+ |
for (i = 0; vlist[i] != NULL; i++) { |
1051 |
+ |
if (v == vlist[i]) |
1052 |
+ |
return; |
1053 |
+ |
if (v < vlist[i]) |
1054 |
+ |
break; |
1055 |
+ |
} |
1056 |
+ |
for (j = i; vlist[j] != NULL; j++) |
1057 |
+ |
; |
1058 |
+ |
while (j > i) { |
1059 |
+ |
vlist[j] = vlist[j-1]; |
1060 |
+ |
--j; |
1061 |
+ |
} |
1062 |
+ |
vlist[i] = v; |
1063 |
+ |
} |
1064 |
+ |
|
1065 |
+ |
/* Sort triangle edges in standard order */ |
1066 |
+ |
static int |
1067 |
+ |
order_triangle(MIGRATION *miga[3]) |
1068 |
+ |
{ |
1069 |
+ |
RBFNODE *vert[7]; |
1070 |
+ |
MIGRATION *ord[3]; |
1071 |
+ |
int i; |
1072 |
+ |
/* order vertices, first */ |
1073 |
+ |
memset(vert, 0, sizeof(vert)); |
1074 |
+ |
for (i = 3; i--; ) { |
1075 |
+ |
if (miga[i] == NULL) |
1076 |
+ |
return(0); |
1077 |
+ |
insert_vert(vert, miga[i]->rbfv[0]); |
1078 |
+ |
insert_vert(vert, miga[i]->rbfv[1]); |
1079 |
+ |
} |
1080 |
+ |
/* should be just 3 vertices */ |
1081 |
+ |
if ((vert[3] == NULL) | (vert[4] != NULL)) |
1082 |
+ |
return(0); |
1083 |
+ |
/* identify edge 0 */ |
1084 |
+ |
for (i = 3; i--; ) |
1085 |
+ |
if (miga[i]->rbfv[0] == vert[0] && |
1086 |
+ |
miga[i]->rbfv[1] == vert[1]) { |
1087 |
+ |
ord[0] = miga[i]; |
1088 |
+ |
break; |
1089 |
+ |
} |
1090 |
+ |
if (i < 0) |
1091 |
+ |
return(0); |
1092 |
+ |
/* identify edge 1 */ |
1093 |
+ |
for (i = 3; i--; ) |
1094 |
+ |
if (miga[i]->rbfv[0] == vert[1] && |
1095 |
+ |
miga[i]->rbfv[1] == vert[2]) { |
1096 |
+ |
ord[1] = miga[i]; |
1097 |
+ |
break; |
1098 |
+ |
} |
1099 |
+ |
if (i < 0) |
1100 |
+ |
return(0); |
1101 |
+ |
/* identify edge 2 */ |
1102 |
+ |
for (i = 3; i--; ) |
1103 |
+ |
if (miga[i]->rbfv[0] == vert[0] && |
1104 |
+ |
miga[i]->rbfv[1] == vert[2]) { |
1105 |
+ |
ord[2] = miga[i]; |
1106 |
+ |
break; |
1107 |
+ |
} |
1108 |
+ |
if (i < 0) |
1109 |
+ |
return(0); |
1110 |
+ |
/* reassign order */ |
1111 |
+ |
miga[0] = ord[0]; miga[1] = ord[1]; miga[2] = ord[2]; |
1112 |
+ |
return(1); |
1113 |
+ |
} |
1114 |
+ |
|
1115 |
|
/* Find edge(s) for interpolating the given incident vector */ |
1116 |
|
static int |
1117 |
|
get_interp(MIGRATION *miga[3], const FVECT invec) |
1137 |
|
{ /* else use triangle mesh */ |
1138 |
|
unsigned char floodmap[GRIDRES][(GRIDRES+7)/8]; |
1139 |
|
int pstart[2]; |
1140 |
+ |
RBFNODE *vother; |
1141 |
+ |
MIGRATION *ej; |
1142 |
+ |
int i; |
1143 |
|
|
1144 |
|
pos_from_vec(pstart, invec); |
1145 |
|
memset(floodmap, 0, sizeof(floodmap)); |
1150 |
|
return(0); /* should never happen */ |
1151 |
|
if (miga[1] == NULL) |
1152 |
|
return(1); /* on edge */ |
1153 |
< |
return(3); /* else in triangle */ |
1153 |
> |
/* verify triangle */ |
1154 |
> |
if (!order_triangle(miga)) { |
1155 |
> |
#ifdef DEBUG |
1156 |
> |
fputs("Munged triangle in get_interp()\n", stderr); |
1157 |
> |
#endif |
1158 |
> |
vother = NULL; /* find triangle from edge */ |
1159 |
> |
for (i = 3; i--; ) { |
1160 |
> |
RBFNODE *tpair[2]; |
1161 |
> |
if (get_triangles(tpair, miga[i]) && |
1162 |
> |
(vother = tpair[ is_rev_tri( |
1163 |
> |
miga[i]->rbfv[0]->invec, |
1164 |
> |
miga[i]->rbfv[1]->invec, |
1165 |
> |
invec) ]) != NULL) |
1166 |
> |
break; |
1167 |
> |
} |
1168 |
> |
if (vother == NULL) { /* couldn't find 3rd vertex */ |
1169 |
> |
#ifdef DEBUG |
1170 |
> |
fputs("No triangle in get_interp()\n", stderr); |
1171 |
> |
#endif |
1172 |
> |
return(0); |
1173 |
> |
} |
1174 |
> |
/* reassign other two edges */ |
1175 |
> |
for (ej = vother->ejl; ej != NULL; |
1176 |
> |
ej = nextedge(vother,ej)) { |
1177 |
> |
RBFNODE *vorig = opp_rbf(vother,ej); |
1178 |
> |
if (vorig == miga[i]->rbfv[0]) |
1179 |
> |
miga[(i+1)%3] = ej; |
1180 |
> |
else if (vorig == miga[i]->rbfv[1]) |
1181 |
> |
miga[(i+2)%3] = ej; |
1182 |
> |
} |
1183 |
> |
if (!order_triangle(miga)) { |
1184 |
> |
#ifdef DEBUG |
1185 |
> |
fputs("Bad triangle in get_interp()\n", stderr); |
1186 |
> |
#endif |
1187 |
> |
return(0); |
1188 |
> |
} |
1189 |
> |
} |
1190 |
> |
return(3); /* return in standard order */ |
1191 |
|
} |
1192 |
|
} |
1193 |
|
|
1266 |
|
return(NULL); /* pro forma return */ |
1267 |
|
} |
1268 |
|
|
1154 |
– |
/* Insert vertex in ordered list */ |
1155 |
– |
static void |
1156 |
– |
insert_vert(RBFNODE **vlist, RBFNODE *v) |
1157 |
– |
{ |
1158 |
– |
int i, j; |
1159 |
– |
|
1160 |
– |
for (i = 0; vlist[i] != NULL; i++) { |
1161 |
– |
if (v == vlist[i]) |
1162 |
– |
return; |
1163 |
– |
if (v < vlist[i]) |
1164 |
– |
break; |
1165 |
– |
} |
1166 |
– |
for (j = i; vlist[j] != NULL; j++) |
1167 |
– |
; |
1168 |
– |
while (j > i) { |
1169 |
– |
vlist[j] = vlist[j-1]; |
1170 |
– |
--j; |
1171 |
– |
} |
1172 |
– |
vlist[i] = v; |
1173 |
– |
} |
1174 |
– |
|
1175 |
– |
/* Sort triangle edges in standard order */ |
1176 |
– |
static void |
1177 |
– |
order_triangle(MIGRATION *miga[3]) |
1178 |
– |
{ |
1179 |
– |
RBFNODE *vert[4]; |
1180 |
– |
MIGRATION *ord[3]; |
1181 |
– |
int i; |
1182 |
– |
/* order vertices, first */ |
1183 |
– |
memset(vert, 0, sizeof(vert)); |
1184 |
– |
for (i = 0; i < 3; i++) { |
1185 |
– |
insert_vert(vert, miga[i]->rbfv[0]); |
1186 |
– |
insert_vert(vert, miga[i]->rbfv[1]); |
1187 |
– |
} |
1188 |
– |
/* identify edge 0 */ |
1189 |
– |
for (i = 0; i < 3; i++) |
1190 |
– |
if (miga[i]->rbfv[0] == vert[0] && |
1191 |
– |
miga[i]->rbfv[1] == vert[1]) { |
1192 |
– |
ord[0] = miga[i]; |
1193 |
– |
break; |
1194 |
– |
} |
1195 |
– |
/* identify edge 1 */ |
1196 |
– |
for (i = 0; i < 3; i++) |
1197 |
– |
if (miga[i]->rbfv[0] == vert[1] && |
1198 |
– |
miga[i]->rbfv[1] == vert[2]) { |
1199 |
– |
ord[1] = miga[i]; |
1200 |
– |
break; |
1201 |
– |
} |
1202 |
– |
/* identify edge 2 */ |
1203 |
– |
for (i = 0; i < 3; i++) |
1204 |
– |
if (miga[i]->rbfv[0] == vert[0] && |
1205 |
– |
miga[i]->rbfv[1] == vert[2]) { |
1206 |
– |
ord[2] = miga[i]; |
1207 |
– |
break; |
1208 |
– |
} |
1209 |
– |
miga[0] = ord[0]; miga[1] = ord[1]; miga[2] = ord[2]; |
1210 |
– |
} |
1211 |
– |
|
1269 |
|
/* Partially advect between recorded incident angles and allocate new RBF */ |
1270 |
|
static RBFNODE * |
1271 |
|
advect_rbf(const FVECT invec) |
1281 |
|
return(NULL); |
1282 |
|
if (miga[1] == NULL) /* advect along edge? */ |
1283 |
|
return(e_advect_rbf(miga[0], invec)); |
1227 |
– |
/* put in standard order */ |
1228 |
– |
order_triangle(miga); |
1284 |
|
#ifdef DEBUG |
1285 |
|
if (miga[0]->rbfv[0] != miga[2]->rbfv[0] | |
1286 |
|
miga[0]->rbfv[1] != miga[1]->rbfv[0] | |