667 |
|
double pd; |
668 |
|
int type; |
669 |
|
|
670 |
< |
point_on_sphere(p0,v0,orig); |
671 |
< |
point_on_sphere(p1,v1,orig); |
672 |
< |
point_on_sphere(p2,v2,orig); |
673 |
< |
|
670 |
> |
VSUB(p0,v0,orig); |
671 |
> |
VSUB(p1,v1,orig); |
672 |
> |
VSUB(p2,v2,orig); |
673 |
> |
|
674 |
|
if(point_in_stri(p0,p1,p2,dir)) |
675 |
|
{ |
676 |
|
/* Intersect the ray with the triangle plane */ |
736 |
|
ffar[3][2] = width*nhv[2] - height*nvv[2] + far*ndv[2] + vp[2] ; |
737 |
|
} |
738 |
|
|
739 |
+ |
int |
740 |
+ |
max_index(v,r) |
741 |
+ |
FVECT v; |
742 |
+ |
double *r; |
743 |
+ |
{ |
744 |
+ |
double p[3]; |
745 |
+ |
int i; |
746 |
|
|
747 |
+ |
p[0] = fabs(v[0]); |
748 |
+ |
p[1] = fabs(v[1]); |
749 |
+ |
p[2] = fabs(v[2]); |
750 |
+ |
i = (p[0]>=p[1])?((p[0]>=p[2])?0:2):((p[1]>=p[2])?1:2); |
751 |
+ |
if(r) |
752 |
+ |
*r = p[i]; |
753 |
+ |
return(i); |
754 |
+ |
} |
755 |
|
|
756 |
+ |
int |
757 |
+ |
closest_point_in_tri(p0,p1,p2,p,p0id,p1id,p2id) |
758 |
+ |
FVECT p0,p1,p2,p; |
759 |
+ |
int p0id,p1id,p2id; |
760 |
+ |
{ |
761 |
+ |
double d,d1; |
762 |
+ |
int i; |
763 |
+ |
|
764 |
+ |
d = DIST_SQ(p,p0); |
765 |
+ |
d1 = DIST_SQ(p,p1); |
766 |
+ |
if(d < d1) |
767 |
+ |
{ |
768 |
+ |
d1 = DIST_SQ(p,p2); |
769 |
+ |
i = (d1 < d)?p2id:p0id; |
770 |
+ |
} |
771 |
+ |
else |
772 |
+ |
{ |
773 |
+ |
d = DIST_SQ(p,p2); |
774 |
+ |
i = (d < d1)? p2id:p1id; |
775 |
+ |
} |
776 |
+ |
return(i); |
777 |
+ |
} |
778 |
|
|
779 |
+ |
|
780 |
|
int |
781 |
|
sedge_intersect(a0,a1,b0,b1) |
782 |
|
FVECT a0,a1,b0,b1; |
838 |
|
a = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1); |
839 |
|
coord[0] = ((x2 - px) * (y3 - py) - (x3 - px) * (y2 - py)) / a; |
840 |
|
coord[1] = ((x3 - px) * (y1 - py) - (x1 - px) * (y3 - py)) / a; |
841 |
< |
coord[2] = 1.0 - coord[0] - coord[1]; |
841 |
> |
coord[2] = ((x1 - px) * (y2 - py) - (x2 - px) * (y1 - py)) / a; |
842 |
|
|
843 |
|
} |
844 |
|
|
1051 |
|
} |
1052 |
|
} |
1053 |
|
|
1054 |
< |
int |
1055 |
< |
max_index(v) |
1056 |
< |
FVECT v; |
1054 |
> |
|
1055 |
> |
baryi_parent(coord,i) |
1056 |
> |
BCOORD coord[3]; |
1057 |
> |
int i; |
1058 |
|
{ |
1020 |
– |
double a,b,c; |
1021 |
– |
int i; |
1059 |
|
|
1060 |
< |
a = fabs(v[0]); |
1061 |
< |
b = fabs(v[1]); |
1062 |
< |
c = fabs(v[2]); |
1063 |
< |
i = (a>=b)?((a>=c)?0:2):((b>=c)?1:2); |
1064 |
< |
return(i); |
1060 |
> |
switch(i) { |
1061 |
> |
case 0: |
1062 |
> |
/* update bary for child */ |
1063 |
> |
coord[0] = (coord[0] >> 1) + MAXBCOORD2; |
1064 |
> |
coord[1] >>= 1; |
1065 |
> |
coord[2] >>= 1; |
1066 |
> |
break; |
1067 |
> |
case 1: |
1068 |
> |
coord[0] >>= 1; |
1069 |
> |
coord[1] = (coord[1] >> 1) + MAXBCOORD2; |
1070 |
> |
coord[2] >>= 1; |
1071 |
> |
break; |
1072 |
> |
|
1073 |
> |
case 2: |
1074 |
> |
coord[0] >>= 1; |
1075 |
> |
coord[1] >>= 1; |
1076 |
> |
coord[2] = (coord[2] >> 1) + MAXBCOORD2; |
1077 |
> |
break; |
1078 |
> |
|
1079 |
> |
case 3: |
1080 |
> |
coord[0] = MAXBCOORD2 - (coord[0] >> 1); |
1081 |
> |
coord[1] = MAXBCOORD2 - (coord[1] >> 1); |
1082 |
> |
coord[2] = MAXBCOORD2 - (coord[2] >> 1); |
1083 |
> |
break; |
1084 |
> |
#ifdef DEBUG |
1085 |
> |
default: |
1086 |
> |
eputs("baryi_parent():Invalid child\n"); |
1087 |
> |
break; |
1088 |
> |
#endif |
1089 |
> |
} |
1090 |
|
} |
1091 |
|
|
1092 |
+ |
baryi_from_child(coord,child,next) |
1093 |
+ |
BCOORD coord[3]; |
1094 |
+ |
int child,next; |
1095 |
+ |
{ |
1096 |
+ |
#ifdef DEBUG |
1097 |
+ |
if(child <0 || child > 3) |
1098 |
+ |
{ |
1099 |
+ |
eputs("baryi_from_child():Invalid child\n"); |
1100 |
+ |
return; |
1101 |
+ |
} |
1102 |
+ |
if(next <0 || next > 3) |
1103 |
+ |
{ |
1104 |
+ |
eputs("baryi_from_child():Invalid next\n"); |
1105 |
+ |
return; |
1106 |
+ |
} |
1107 |
+ |
#endif |
1108 |
+ |
if(next == child) |
1109 |
+ |
return; |
1110 |
|
|
1111 |
+ |
switch(child){ |
1112 |
+ |
case 0: |
1113 |
+ |
coord[0] = 0; |
1114 |
+ |
coord[1] = MAXBCOORD - coord[1]; |
1115 |
+ |
coord[2] = MAXBCOORD - coord[2]; |
1116 |
+ |
break; |
1117 |
+ |
case 1: |
1118 |
+ |
coord[0] = MAXBCOORD - coord[0]; |
1119 |
+ |
coord[1] = 0; |
1120 |
+ |
coord[2] = MAXBCOORD - coord[2]; |
1121 |
+ |
break; |
1122 |
+ |
case 2: |
1123 |
+ |
coord[0] = MAXBCOORD - coord[0]; |
1124 |
+ |
coord[1] = MAXBCOORD - coord[1]; |
1125 |
+ |
coord[2] = 0; |
1126 |
+ |
break; |
1127 |
+ |
case 3: |
1128 |
+ |
switch(next){ |
1129 |
+ |
case 0: |
1130 |
+ |
coord[0] = 0; |
1131 |
+ |
coord[1] = MAXBCOORD - coord[1]; |
1132 |
+ |
coord[2] = MAXBCOORD - coord[2]; |
1133 |
+ |
break; |
1134 |
+ |
case 1: |
1135 |
+ |
coord[0] = MAXBCOORD - coord[0]; |
1136 |
+ |
coord[1] = 0; |
1137 |
+ |
coord[2] = MAXBCOORD - coord[2]; |
1138 |
+ |
break; |
1139 |
+ |
case 2: |
1140 |
+ |
coord[0] = MAXBCOORD - coord[0]; |
1141 |
+ |
coord[1] = MAXBCOORD - coord[1]; |
1142 |
+ |
coord[2] = 0; |
1143 |
+ |
break; |
1144 |
+ |
} |
1145 |
+ |
break; |
1146 |
+ |
} |
1147 |
+ |
} |
1148 |
|
|
1032 |
– |
/* |
1033 |
– |
* int |
1034 |
– |
* traceRay(FVECT orig, FVECT dir,FVECT v0,FVECT v1,FVECT v2,FVECT r) |
1035 |
– |
* |
1036 |
– |
* Intersect the ray with triangle v0v1v2, return intersection point in r |
1037 |
– |
* |
1038 |
– |
* Assumes orig,v0,v1,v2 are in spherical coordinates, and orig is |
1039 |
– |
* unit |
1040 |
– |
*/ |
1149 |
|
int |
1150 |
< |
traceRay(orig,dir,v0,v1,v2,r) |
1151 |
< |
FVECT orig,dir; |
1044 |
< |
FVECT v0,v1,v2; |
1045 |
< |
FVECT r; |
1150 |
> |
baryi_child(coord) |
1151 |
> |
BCOORD coord[3]; |
1152 |
|
{ |
1047 |
– |
FVECT n,p[3],d; |
1048 |
– |
double pt[3],r_eps; |
1153 |
|
int i; |
1050 |
– |
int which; |
1154 |
|
|
1155 |
< |
/* Find the plane equation for the triangle defined by the edge v0v1 and |
1156 |
< |
the view center*/ |
1157 |
< |
VCROSS(n,v0,v1); |
1158 |
< |
/* Intersect the ray with this plane */ |
1159 |
< |
i = intersect_ray_plane(orig,dir,n,0.0,&(pt[0]),p[0]); |
1160 |
< |
if(i) |
1161 |
< |
which = 0; |
1155 |
> |
if(coord[0] > MAXBCOORD2) |
1156 |
> |
{ |
1157 |
> |
/* update bary for child */ |
1158 |
> |
coord[0] = (coord[0]<< 1) - MAXBCOORD; |
1159 |
> |
coord[1] <<= 1; |
1160 |
> |
coord[2] <<= 1; |
1161 |
> |
return(0); |
1162 |
> |
} |
1163 |
|
else |
1164 |
< |
which = -1; |
1164 |
> |
if(coord[1] > MAXBCOORD2) |
1165 |
> |
{ |
1166 |
> |
coord[0] <<= 1; |
1167 |
> |
coord[1] = (coord[1] << 1) - MAXBCOORD; |
1168 |
> |
coord[2] <<= 1; |
1169 |
> |
return(1); |
1170 |
> |
} |
1171 |
> |
else |
1172 |
> |
if(coord[2] > MAXBCOORD2) |
1173 |
> |
{ |
1174 |
> |
coord[0] <<= 1; |
1175 |
> |
coord[1] <<= 1; |
1176 |
> |
coord[2] = (coord[2] << 1) - MAXBCOORD; |
1177 |
> |
return(2); |
1178 |
> |
} |
1179 |
> |
else |
1180 |
> |
{ |
1181 |
> |
coord[0] = MAXBCOORD - (coord[0] << 1); |
1182 |
> |
coord[1] = MAXBCOORD - (coord[1] << 1); |
1183 |
> |
coord[2] = MAXBCOORD - (coord[2] << 1); |
1184 |
> |
return(3); |
1185 |
> |
} |
1186 |
> |
} |
1187 |
|
|
1188 |
< |
VCROSS(n,v1,v2); |
1189 |
< |
i = intersect_ray_plane(orig,dir,n,0.0,&(pt[1]),p[1]); |
1190 |
< |
if(i) |
1191 |
< |
if((which==-1) || pt[1] < pt[0]) |
1192 |
< |
which = 1; |
1188 |
> |
/* convert barycentric coordinate b in [-eps,1+eps] to [0,MAXLONG], |
1189 |
> |
dir unbounded to [-MAXLONG,MAXLONG] |
1190 |
> |
*/ |
1191 |
> |
bary_dtol(b,db,bi,dbi,t) |
1192 |
> |
double b[3],db[3][3]; |
1193 |
> |
BCOORD bi[3]; |
1194 |
> |
BDIR dbi[3][3]; |
1195 |
> |
TINT t[3]; |
1196 |
> |
{ |
1197 |
> |
int i,id,j; |
1198 |
> |
double d; |
1199 |
|
|
1200 |
< |
VCROSS(n,v2,v0); |
1201 |
< |
i = intersect_ray_plane(orig,dir,n,0.0,&(pt[2]),p[2]); |
1202 |
< |
if(i) |
1203 |
< |
if((which==-1) || pt[2] < pt[which]) |
1204 |
< |
which = 2; |
1200 |
> |
for(i=0; i < 2;i++) |
1201 |
> |
{ |
1202 |
> |
if(b[i] <= 0.0) |
1203 |
> |
{ |
1204 |
> |
bi[i]= 0; |
1205 |
> |
} |
1206 |
> |
else |
1207 |
> |
if(b[i] >= 1.0) |
1208 |
> |
{ |
1209 |
> |
bi[i]= MAXBCOORD; |
1210 |
> |
} |
1211 |
> |
else |
1212 |
> |
bi[i] = (BCOORD)(b[i]*MAXBCOORD); |
1213 |
> |
} |
1214 |
> |
bi[2] = MAXBCOORD - bi[0] - bi[1]; |
1215 |
|
|
1216 |
< |
if(which != -1) |
1216 |
> |
if(bi[2] < 0) |
1217 |
|
{ |
1218 |
< |
/* Return point that is K*eps along projection of the ray on |
1219 |
< |
the sphere to push intersection point p[which] into next cell |
1078 |
< |
*/ |
1079 |
< |
normalize(p[which]); |
1080 |
< |
/* Calculate the ray perpendicular to the intersection point: approx |
1081 |
< |
the direction moved along the sphere a distance of K*epsilon*/ |
1082 |
< |
r_eps = -DOT(p[which],dir); |
1083 |
< |
VSUM(n,dir,p[which],r_eps); |
1084 |
< |
/* Calculate the length along ray p[which]-dir needed to move to |
1085 |
< |
cause a move along the sphere of k*epsilon |
1086 |
< |
*/ |
1087 |
< |
r_eps = DOT(n,dir); |
1088 |
< |
VSUM(r,p[which],dir,(20*FTINY)/r_eps); |
1089 |
< |
normalize(r); |
1090 |
< |
return(TRUE); |
1218 |
> |
bi[2] = 0; |
1219 |
> |
bi[1] = MAXBCOORD - bi[0]; |
1220 |
|
} |
1221 |
< |
else |
1221 |
> |
for(j=0; j< 3; j++) |
1222 |
|
{ |
1223 |
< |
/* Unable to find intersection: move along ray and try again */ |
1224 |
< |
r_eps = -DOT(orig,dir); |
1225 |
< |
VSUM(n,dir,orig,r_eps); |
1226 |
< |
r_eps = DOT(n,dir); |
1227 |
< |
VSUM(r,orig,dir,(20*FTINY)/r_eps); |
1228 |
< |
normalize(r); |
1229 |
< |
#ifdef DEBUG |
1230 |
< |
eputs("traceRay:Ray does not intersect triangle\n"); |
1231 |
< |
#endif |
1103 |
< |
return(FALSE); |
1223 |
> |
if(t[j]==0) |
1224 |
> |
continue; |
1225 |
> |
if(t[j] == HUGET) |
1226 |
> |
max_index(db[j],&d); |
1227 |
> |
for(i=0; i< 3; i++) |
1228 |
> |
if(t[j] != HUGET) |
1229 |
> |
dbi[j][i] = (BDIR)(db[j][i]*MAXBDIR); |
1230 |
> |
else |
1231 |
> |
dbi[j][i] = (BDIR)(db[j][i]/d*MAXBDIR); |
1232 |
|
} |
1233 |
|
} |
1234 |
|
|
1235 |
|
|
1108 |
– |
int |
1109 |
– |
closest_point_in_tri(p0,p1,p2,p,p0id,p1id,p2id) |
1110 |
– |
FVECT p0,p1,p2,p; |
1111 |
– |
int p0id,p1id,p2id; |
1112 |
– |
{ |
1113 |
– |
double d,d1; |
1114 |
– |
int i; |
1115 |
– |
|
1116 |
– |
d = DIST_SQ(p,p0); |
1117 |
– |
d1 = DIST_SQ(p,p1); |
1118 |
– |
if(d < d1) |
1119 |
– |
{ |
1120 |
– |
d1 = DIST_SQ(p,p2); |
1121 |
– |
i = (d1 < d)?p2id:p0id; |
1122 |
– |
} |
1123 |
– |
else |
1124 |
– |
{ |
1125 |
– |
d = DIST_SQ(p,p2); |
1126 |
– |
i = (d < d1)? p2id:p1id; |
1127 |
– |
} |
1128 |
– |
return(i); |
1129 |
– |
} |
1236 |
|
|
1237 |
|
|
1238 |
|
|