| 1 |
/* Copyright (c) 1998 Silicon Graphics, Inc. */ |
| 2 |
|
| 3 |
#ifndef lint |
| 4 |
static char SCCSid[] = "$SunId$ SGI"; |
| 5 |
#endif |
| 6 |
|
| 7 |
/* |
| 8 |
* sm.c |
| 9 |
*/ |
| 10 |
#include "standard.h" |
| 11 |
#include "sm_flag.h" |
| 12 |
#include "sm_list.h" |
| 13 |
#include "sm_geom.h" |
| 14 |
#include "sm_qtree.h" |
| 15 |
#include "sm_stree.h" |
| 16 |
#include "sm.h" |
| 17 |
|
| 18 |
|
| 19 |
SM *smMesh = NULL; |
| 20 |
double smDist_sum=0; |
| 21 |
#define S_INC 1000 |
| 22 |
int smNew_tri_cnt=0; |
| 23 |
int smNew_tri_size=0; |
| 24 |
T_DEPTH *smNew_tris= NULL; |
| 25 |
|
| 26 |
#define SM_MIN_SAMP_DIFF 1e-3 /* min edge length in radians */ |
| 27 |
|
| 28 |
/* Each edge extends .5536 radians - 31.72 degrees */ |
| 29 |
static FVECT icosa_verts[162] = |
| 30 |
{{-0.018096,0.495400,0.868477},{0.018614,-0.554780,0.831789}, |
| 31 |
{0.850436,0.011329,0.525956},{0.850116,0.048016,-0.524402}, |
| 32 |
{-0.850116,-0.048016,0.524402},{-0.850436,-0.011329,-0.525956}, |
| 33 |
{0.495955,0.867825,0.030147},{-0.555329,0.831118,0.029186}, |
| 34 |
{0.555329,-0.831118,-0.029186},{-0.495955,-0.867825,-0.030147}, |
| 35 |
{-0.018614,0.554780,-0.831789},{0.018096,-0.495400,-0.868477}, |
| 36 |
{0.000305,-0.034906,0.999391},{0.489330,0.297837,0.819664}, |
| 37 |
{0.510900,-0.319418,0.798094},{-0.488835,-0.354308,0.797186}, |
| 38 |
{-0.510409,0.262947,0.818744},{0.999391,0.034875,0.000914}, |
| 39 |
{0.791335,0.516672,0.326862},{0.791142,0.538234,-0.290513}, |
| 40 |
{0.826031,-0.460219,-0.325378},{0.826216,-0.481780,0.291985}, |
| 41 |
{-0.999391,-0.034875,-0.000914},{-0.826216,0.481780,-0.291985}, |
| 42 |
{-0.826031,0.460219,0.325378},{-0.791142,-0.538234,0.290513}, |
| 43 |
{-0.791335,-0.516672,-0.326862},{-0.034911,0.998782,0.034881}, |
| 44 |
{0.280899,0.801316,0.528194},{-0.337075,0.779739,0.527624}, |
| 45 |
{-0.337377,0.814637,-0.471746},{0.280592,0.836213,-0.471186}, |
| 46 |
{0.034911,-0.998782,-0.034881},{-0.280592,-0.836213,0.471186}, |
| 47 |
{0.337377,-0.814637,0.471746},{0.337075,-0.779739,-0.527624}, |
| 48 |
{-0.280899,-0.801316,-0.528194},{-0.000305,0.034906,-0.999391}, |
| 49 |
{0.510409,-0.262947,-0.818744},{0.488835,0.354308,-0.797186}, |
| 50 |
{-0.510900,0.319418,-0.798094},{-0.489330,-0.297837,-0.819664}, |
| 51 |
{0.009834,-0.306509,0.951817},{0.268764,-0.186284,0.945021}, |
| 52 |
{0.275239,-0.454405,0.847207},{-0.009247,0.239357,0.970888}, |
| 53 |
{0.244947,0.412323,0.877491},{0.257423,0.138235,0.956360}, |
| 54 |
{0.525850,-0.011345,0.850502},{0.696394,0.160701,0.699436}, |
| 55 |
{0.707604,-0.160141,0.688223},{-0.268186,0.119892,0.955878}, |
| 56 |
{-0.274715,0.394186,0.877011},{-0.244420,-0.472542,0.846737}, |
| 57 |
{-0.256843,-0.204627,0.944542},{-0.525332,-0.048031,0.849541}, |
| 58 |
{-0.695970,-0.209123,0.686945},{-0.707182,0.111718,0.698149}, |
| 59 |
{0.961307,0.043084,-0.272090},{0.941300,0.301289,-0.152245}, |
| 60 |
{0.853076,0.304715,-0.423568},{0.961473,0.024015,0.273848}, |
| 61 |
{0.853344,0.274439,0.443269},{0.941400,0.289953,0.172315}, |
| 62 |
{0.831918,0.554570,0.019109},{0.669103,0.719629,0.185565}, |
| 63 |
{0.669003,0.730836,-0.135332},{0.959736,-0.234941,0.153979}, |
| 64 |
{0.871472,-0.244526,0.425140},{0.871210,-0.214250,-0.441690}, |
| 65 |
{0.959638,-0.223606,-0.170573},{0.868594,-0.495213,-0.017555}, |
| 66 |
{0.717997,-0.671205,-0.184294},{0.718092,-0.682411,0.136596}, |
| 67 |
{-0.961307,-0.043084,0.272090},{-0.959638,0.223606,0.170573}, |
| 68 |
{-0.871210,0.214250,0.441690},{-0.961473,-0.024015,-0.273848}, |
| 69 |
{-0.871472,0.244526,-0.425140},{-0.959736,0.234941,-0.153979}, |
| 70 |
{-0.868594,0.495213,0.017555},{-0.718092,0.682411,-0.136596}, |
| 71 |
{-0.717997,0.671205,0.184294},{-0.941400,-0.289953,-0.172315}, |
| 72 |
{-0.853344,-0.274439,-0.443269},{-0.853076,-0.304715,0.423568}, |
| 73 |
{-0.941300,-0.301289,0.152245},{-0.831918,-0.554570,-0.019109}, |
| 74 |
{-0.669003,-0.730836,0.135332},{-0.669103,-0.719629,-0.185565}, |
| 75 |
{-0.306809,0.951188,0.033302},{-0.195568,0.935038,0.295731}, |
| 76 |
{-0.463858,0.837300,0.289421},{0.239653,0.970270,0.033802}, |
| 77 |
{0.403798,0.867595,0.290218},{0.129326,0.946383,0.296031}, |
| 78 |
{-0.029535,0.831255,0.555106},{0.136603,0.674019,0.725974}, |
| 79 |
{-0.184614,0.662804,0.725678},{0.129164,0.964728,-0.229382}, |
| 80 |
{0.403637,0.885733,-0.229245},{-0.464015,0.855438,-0.230036}, |
| 81 |
{-0.195726,0.953383,-0.229677},{-0.029855,0.867949,-0.495755}, |
| 82 |
{-0.185040,0.711807,-0.677562},{0.136173,0.723022,-0.677271}, |
| 83 |
{0.306809,-0.951188,-0.033302},{0.195726,-0.953383,0.229677}, |
| 84 |
{0.464015,-0.855438,0.230036},{-0.239653,-0.970270,-0.033802}, |
| 85 |
{-0.403637,-0.885733,0.229245},{-0.129164,-0.964728,0.229382}, |
| 86 |
{0.029855,-0.867949,0.495755},{-0.136173,-0.723022,0.677271}, |
| 87 |
{0.185040,-0.711807,0.677562},{-0.129326,-0.946383,-0.296031}, |
| 88 |
{-0.403798,-0.867595,-0.290218},{0.463858,-0.837300,-0.289421} |
| 89 |
,{0.195568,-0.935038,-0.295731},{0.029535,-0.831255,-0.555106}, |
| 90 |
{0.184614,-0.662804,-0.725678},{-0.136603,-0.674019,-0.725974}, |
| 91 |
{-0.009834,0.306509,-0.951817},{0.256843,0.204627,-0.944542}, |
| 92 |
{0.244420,0.472542,-0.846737},{0.009247,-0.239357,-0.970888}, |
| 93 |
{0.274715,-0.394186,-0.877011},{0.268186,-0.119892,-0.955878}, |
| 94 |
{0.525332,0.048031,-0.849541},{0.707182,-0.111718,-0.698149}, |
| 95 |
{0.695970,0.209123,-0.686945},{-0.257423,-0.138235,-0.956360}, |
| 96 |
{-0.244947,-0.412323,-0.877491},{-0.275239,0.454405,-0.847207}, |
| 97 |
{-0.268764,0.186284,-0.945021},{-0.525850,0.011345,-0.850502}, |
| 98 |
{-0.707604,0.160141,-0.688223},{-0.696394,-0.160701,-0.699436}, |
| 99 |
{0.563717,0.692920,0.449538},{0.673284,0.428212,0.602763}, |
| 100 |
{0.404929,0.577853,0.708603},{0.445959,-0.596198,0.667584}, |
| 101 |
{0.702960,-0.421213,0.573086},{0.611746,-0.681577,0.401523}, |
| 102 |
{-0.445543,0.548166,0.707818},{-0.702606,0.380190,0.601498}, |
| 103 |
{-0.611490,0.651895,0.448456},{-0.563454,-0.722602,0.400456}, |
| 104 |
{-0.672921,-0.469235,0.571835},{-0.404507,-0.625886,0.666814}, |
| 105 |
{0.404507,0.625886,-0.666814},{0.672921,0.469235,-0.571835}, |
| 106 |
{0.563454,0.722602,-0.400456},{0.611490,-0.651895,-0.448456}, |
| 107 |
{0.702606,-0.380190,-0.601498},{0.445543,-0.548166,-0.707818}, |
| 108 |
{-0.611746,0.681577,-0.401523},{-0.702960,0.421213,-0.573086}, |
| 109 |
{-0.445959,0.596198,-0.667584},{-0.404929,-0.577853,-0.708603}, |
| 110 |
{-0.673284,-0.428212,-0.602763},{-0.563717,-0.692920,-0.449538}}; |
| 111 |
static int icosa_tris[320][3] = |
| 112 |
{ {1,42,44},{42,12,43},{44,43,14},{42,43,44},{12,45,47},{45,0,46},{47,46,13}, |
| 113 |
{45,46,47},{14,48,50},{48,13,49},{50,49,2},{48,49,50},{12,47,43},{47,13,48}, |
| 114 |
{43,48,14},{47,48,43},{0,45,52},{45,12,51},{52,51,16},{45,51,52},{12,42,54}, |
| 115 |
{42,1,53},{54,53,15},{42,53,54},{16,55,57},{55,15,56},{57,56,4},{55,56,57}, |
| 116 |
{12,54,51},{54,15,55},{51,55,16},{54,55,51},{3,58,60},{58,17,59},{60,59,19}, |
| 117 |
{58,59,60},{17,61,63},{61,2,62},{63,62,18},{61,62,63},{19,64,66},{64,18,65}, |
| 118 |
{66,65,6},{64,65,66},{17,63,59},{63,18,64},{59,64,19},{63,64,59},{2,61,68}, |
| 119 |
{61,17,67},{68,67,21},{61,67,68},{17,58,70},{58,3,69},{70,69,20},{58,69,70}, |
| 120 |
{21,71,73},{71,20,72},{73,72,8},{71,72,73},{17,70,67},{70,20,71},{67,71,21}, |
| 121 |
{70,71,67},{4,74,76},{74,22,75},{76,75,24},{74,75,76},{22,77,79},{77,5,78}, |
| 122 |
{79,78,23},{77,78,79},{24,80,82},{80,23,81},{82,81,7},{80,81,82},{22,79,75}, |
| 123 |
{79,23,80},{75,80,24},{79,80,75},{5,77,84},{77,22,83},{84,83,26},{77,83,84}, |
| 124 |
{22,74,86},{74,4,85},{86,85,25},{74,85,86},{26,87,89},{87,25,88},{89,88,9}, |
| 125 |
{87,88,89},{22,86,83},{86,25,87},{83,87,26},{86,87,83},{7,90,92},{90,27,91}, |
| 126 |
{92,91,29},{90,91,92},{27,93,95},{93,6,94},{95,94,28},{93,94,95},{29,96,98}, |
| 127 |
{96,28,97},{98,97,0},{96,97,98},{27,95,91},{95,28,96},{91,96,29},{95,96,91}, |
| 128 |
{6,93,100},{93,27,99},{100,99,31},{93,99,100},{27,90,102},{90,7,101}, |
| 129 |
{102,101,30},{90,101,102},{31,103,105},{103,30,104},{105,104,10},{103,104,105}, |
| 130 |
{27,102,99},{102,30,103},{99,103,31},{102,103,99},{8,106,108},{106,32,107}, |
| 131 |
{108,107,34},{106,107,108},{32,109,111},{109,9,110},{111,110,33},{109,110,111}, |
| 132 |
{34,112,114},{112,33,113},{114,113,1},{112,113,114},{32,111,107},{111,33,112}, |
| 133 |
{107,112,34},{111,112,107},{9,109,116},{109,32,115},{116,115,36},{109,115,116}, |
| 134 |
{32,106,118},{106,8,117},{118,117,35},{106,117,118},{36,119,121},{119,35,120}, |
| 135 |
{121,120,11},{119,120,121},{32,118,115},{118,35,119},{115,119,36},{118,119,115}, |
| 136 |
{10,122,124},{122,37,123},{124,123,39},{122,123,124},{37,125,127},{125,11,126}, |
| 137 |
{127,126,38},{125,126,127},{39,128,130},{128,38,129},{130,129,3},{128,129,130}, |
| 138 |
{37,127,123},{127,38,128},{123,128,39},{127,128,123},{11,125,132},{125,37,131}, |
| 139 |
{132,131,41},{125,131,132},{37,122,134},{122,10,133},{134,133,40},{122,133,134}, |
| 140 |
{41,135,137},{135,40,136},{137,136,5},{135,136,137},{37,134,131},{134,40,135}, |
| 141 |
{131,135,41},{134,135,131},{6,65,94},{65,18,138},{94,138,28},{65,138,94}, |
| 142 |
{18,62,139},{62,2,49},{139,49,13},{62,49,139},{28,140,97},{140,13,46},{97,46,0}, |
| 143 |
{140,46,97},{18,139,138},{139,13,140},{138,140,28},{139,140,138},{1,44,114}, |
| 144 |
{44,14,141},{114,141,34},{44,141,114},{14,50,142},{50,2,68},{142,68,21}, |
| 145 |
{50,68,142},{34,143,108},{143,21,73},{108,73,8},{143,73,108},{14,142,141}, |
| 146 |
{142,21,143},{141,143,34},{142,143,141},{0,52,98},{52,16,144},{98,144,29}, |
| 147 |
{52,144,98},{16,57,145},{57,4,76},{145,76,24},{57,76,145},{29,146,92}, |
| 148 |
{146,24,82},{92,82,7},{146,82,92},{16,145,144},{145,24,146},{144,146,29}, |
| 149 |
{145,146,144},{9,88,110},{88,25,147},{110,147,33},{88,147,110},{25,85,148}, |
| 150 |
{85,4,56},{148,56,15},{85,56,148},{33,149,113},{149,15,53},{113,53,1}, |
| 151 |
{149,53,113},{25,148,147},{148,15,149},{147,149,33},{148,149,147},{10,124,105}, |
| 152 |
{124,39,150},{105,150,31},{124,150,105},{39,130,151},{130,3,60},{151,60,19}, |
| 153 |
{130,60,151},{31,152,100},{152,19,66},{100,66,6},{152,66,100},{39,151,150}, |
| 154 |
{151,19,152},{150,152,31},{151,152,150},{8,72,117},{72,20,153},{117,153,35}, |
| 155 |
{72,153,117},{20,69,154},{69,3,129},{154,129,38},{69,129,154},{35,155,120}, |
| 156 |
{155,38,126},{120,126,11},{155,126,120},{20,154,153},{154,38,155},{153,155,35}, |
| 157 |
{154,155,153},{7,81,101},{81,23,156},{101,156,30},{81,156,101},{23,78,157}, |
| 158 |
{78,5,136},{157,136,40},{78,136,157},{30,158,104},{158,40,133},{104,133,10}, |
| 159 |
{158,133,104},{23,157,156},{157,40,158},{156,158,30},{157,158,156},{11,132,121}, |
| 160 |
{132,41,159},{121,159,36},{132,159,121},{41,137,160},{137,5,84},{160,84,26}, |
| 161 |
{137,84,160},{36,161,116},{161,26,89},{116,89,9},{161,89,116},{41,160,159}, |
| 162 |
{160,26,161},{159,161,36},{160,161,159}}; |
| 163 |
static int icosa_nbrs[320][3] = |
| 164 |
{{3,208,21},{12,3,20},{14,209,3},{2,0,1},{7,12,17},{202,7,16},{201,13,7}, |
| 165 |
{6,4,5},{11,212,14},{198,11,13},{197,213,11},{10,8,9},{15,1,4},{9,15,6}, |
| 166 |
{8,2,15},{14,12,13},{19,224,5},{28,19,4},{30,225,19},{18,16,17},{23,28,1}, |
| 167 |
{250,23,0},{249,29,23},{22,20,21},{27,228,30},{246,27,29},{245,229,27}, |
| 168 |
{26,24,25},{31,17,20},{25,31,22},{24,18,31},{30,28,29},{35,261,53},{44,35,52}, |
| 169 |
{46,262,35},{34,32,33},{39,44,49},{197,39,48},{196,45,39},{38,36,37}, |
| 170 |
{43,265,46},{193,43,45},{192,266,43},{42,40,41},{47,33,36},{41,47,38}, |
| 171 |
{40,34,47},{46,44,45},{51,213,37},{60,51,36},{62,214,51},{50,48,49},{55,60,33}, |
| 172 |
{277,55,32},{276,61,55},{54,52,53},{59,217,62},{273,59,61},{272,218,59}, |
| 173 |
{58,56,57},{63,49,52},{57,63,54},{56,50,63},{62,60,61},{67,229,85},{76,67,84}, |
| 174 |
{78,230,67},{66,64,65},{71,76,81},{293,71,80},{292,77,71},{70,68,69}, |
| 175 |
{75,233,78},{289,75,77},{288,234,75},{74,72,73},{79,65,68},{73,79,70}, |
| 176 |
{72,66,79},{78,76,77},{83,309,69},{92,83,68},{94,310,83},{82,80,81},{87,92,65}, |
| 177 |
{245,87,64},{244,93,87},{86,84,85},{91,313,94},{241,91,93},{240,314,91}, |
| 178 |
{90,88,89},{95,81,84},{89,95,86},{88,82,95},{94,92,93},{99,234,117}, |
| 179 |
{108,99,116},{110,232,99},{98,96,97},{103,108,113},{192,103,112},{194,109,103}, |
| 180 |
{102,100,101},{107,226,110},{200,107,109},{202,224,107},{106,104,105}, |
| 181 |
{111,97,100},{105,111,102},{104,98,111},{110,108,109},{115,266,101}, |
| 182 |
{124,115,100},{126,264,115},{114,112,113},{119,124,97},{288,119,96}, |
| 183 |
{290,125,119},{118,116,117},{123,258,126},{296,123,125},{298,256,123}, |
| 184 |
{122,120,121},{127,113,116},{121,127,118},{120,114,127},{126,124,125}, |
| 185 |
{131,218,149},{140,131,148},{142,216,131},{130,128,129},{135,140,145}, |
| 186 |
{240,135,144},{242,141,135},{134,132,133},{139,210,142},{248,139,141}, |
| 187 |
{250,208,139},{138,136,137},{143,129,132},{137,143,134},{136,130,143}, |
| 188 |
{142,140,141},{147,314,133},{156,147,132},{158,312,147},{146,144,145}, |
| 189 |
{151,156,129},{272,151,128},{274,157,151},{150,148,149},{155,306,158}, |
| 190 |
{280,155,157},{282,304,155},{154,152,153},{159,145,148},{153,159,150}, |
| 191 |
{152,146,159},{158,156,157},{163,256,181},{172,163,180},{174,257,163}, |
| 192 |
{162,160,161},{167,172,177},{282,167,176},{281,173,167},{166,164,165}, |
| 193 |
{171,260,174},{278,171,173},{277,261,171},{170,168,169},{175,161,164}, |
| 194 |
{169,175,166},{168,162,175},{174,172,173},{179,304,165},{188,179,164}, |
| 195 |
{190,305,179},{178,176,177},{183,188,161},{298,183,160},{297,189,183}, |
| 196 |
{182,180,181},{187,308,190},{294,187,189},{293,309,187},{186,184,185}, |
| 197 |
{191,177,180},{185,191,182},{184,178,191},{190,188,189},{195,101,42}, |
| 198 |
{204,195,41},{206,102,195},{194,192,193},{199,204,38},{10,199,37},{9,205,199}, |
| 199 |
{198,196,197},{203,105,206},{6,203,205},{5,106,203},{202,200,201},{207,193,196}, |
| 200 |
{201,207,198},{200,194,207},{206,204,205},{211,138,0},{220,211,2},{222,136,211}, |
| 201 |
{210,208,209},{215,220,8},{48,215,10},{50,221,215},{214,212,213},{219,130,222}, |
| 202 |
{56,219,221},{58,128,219},{218,216,217},{223,209,212},{217,223,214}, |
| 203 |
{216,210,223},{222,220,221},{227,106,16},{236,227,18},{238,104,227}, |
| 204 |
{226,224,225},{231,236,24},{64,231,26},{66,237,231},{230,228,229},{235,98,238}, |
| 205 |
{72,235,237},{74,96,235},{234,232,233},{239,225,228},{233,239,230}, |
| 206 |
{232,226,239},{238,236,237},{243,133,90},{252,243,89},{254,134,243}, |
| 207 |
{242,240,241},{247,252,86},{26,247,85},{25,253,247},{246,244,245},{251,137,254}, |
| 208 |
{22,251,253},{21,138,251},{250,248,249},{255,241,244},{249,255,246}, |
| 209 |
{248,242,255},{254,252,253},{259,122,160},{268,259,162},{270,120,259}, |
| 210 |
{258,256,257},{263,268,168},{32,263,170},{34,269,263},{262,260,261}, |
| 211 |
{267,114,270},{40,267,269},{42,112,267},{266,264,265},{271,257,260}, |
| 212 |
{265,271,262},{264,258,271},{270,268,269},{275,149,58},{284,275,57}, |
| 213 |
{286,150,275},{274,272,273},{279,284,54},{170,279,53},{169,285,279}, |
| 214 |
{278,276,277},{283,153,286},{166,283,285},{165,154,283},{282,280,281}, |
| 215 |
{287,273,276},{281,287,278},{280,274,287},{286,284,285},{291,117,74}, |
| 216 |
{300,291,73},{302,118,291},{290,288,289},{295,300,70},{186,295,69}, |
| 217 |
{185,301,295},{294,292,293},{299,121,302},{182,299,301},{181,122,299}, |
| 218 |
{298,296,297},{303,289,292},{297,303,294},{296,290,303},{302,300,301}, |
| 219 |
{307,154,176},{316,307,178},{318,152,307},{306,304,305},{311,316,184}, |
| 220 |
{80,311,186},{82,317,311},{310,308,309},{315,146,318},{88,315,317}, |
| 221 |
{90,144,315},{314,312,313},{319,305,308},{313,319,310},{312,306,319}, |
| 222 |
{318,316,317}}; |
| 223 |
|
| 224 |
|
| 225 |
#ifdef TEST_DRIVER |
| 226 |
VIEW Current_View = {0,{0,0,0},{0,0,-1},{0,1,0},60,60,0}; |
| 227 |
int Pick_cnt =0; |
| 228 |
int Pick_tri = -1,Picking = FALSE,Pick_samp=-1; |
| 229 |
FVECT Pick_point[500],Pick_origin,Pick_dir; |
| 230 |
FVECT Pick_v0[500], Pick_v1[500], Pick_v2[500]; |
| 231 |
int Pick_q[500]; |
| 232 |
FVECT P0,P1,P2; |
| 233 |
FVECT FrustumNear[4],FrustumFar[4]; |
| 234 |
double dev_zmin=.01,dev_zmax=1000; |
| 235 |
#endif |
| 236 |
|
| 237 |
smDir(sm,ps,id) |
| 238 |
SM *sm; |
| 239 |
FVECT ps; |
| 240 |
int id; |
| 241 |
{ |
| 242 |
VSUB(ps,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm)); |
| 243 |
normalize(ps); |
| 244 |
} |
| 245 |
|
| 246 |
smDir_in_cone(sm,ps,id) |
| 247 |
SM *sm; |
| 248 |
FVECT ps; |
| 249 |
int id; |
| 250 |
{ |
| 251 |
|
| 252 |
VSUB(ps,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm)); |
| 253 |
normalize(ps); |
| 254 |
} |
| 255 |
|
| 256 |
smClear_flags(sm,which) |
| 257 |
SM *sm; |
| 258 |
int which; |
| 259 |
{ |
| 260 |
int i; |
| 261 |
|
| 262 |
if(which== -1) |
| 263 |
for(i=0; i < T_FLAGS;i++) |
| 264 |
bzero(SM_NTH_FLAGS(sm,i),FLAG_BYTES(SM_MAX_TRIS(sm))); |
| 265 |
else |
| 266 |
bzero(SM_NTH_FLAGS(sm,which),FLAG_BYTES(SM_MAX_TRIS(sm))); |
| 267 |
} |
| 268 |
|
| 269 |
/* Given an allocated mesh- initialize */ |
| 270 |
smInit_mesh(sm) |
| 271 |
SM *sm; |
| 272 |
{ |
| 273 |
/* Reset the triangle counters */ |
| 274 |
SM_NUM_TRI(sm) = 0; |
| 275 |
SM_SAMPLE_TRIS(sm) = 0; |
| 276 |
SM_FREE_TRIS(sm) = -1; |
| 277 |
SM_AVAILABLE_TRIS(sm) = -1; |
| 278 |
smClear_flags(sm,-1); |
| 279 |
} |
| 280 |
|
| 281 |
|
| 282 |
/* Clear the SM for reuse: free any extra allocated memory:does initialization |
| 283 |
as well |
| 284 |
*/ |
| 285 |
smClear(sm) |
| 286 |
SM *sm; |
| 287 |
{ |
| 288 |
smClear_samples(sm); |
| 289 |
smClear_locator(sm); |
| 290 |
smInit_mesh(sm); |
| 291 |
} |
| 292 |
|
| 293 |
static int realloc_cnt=0; |
| 294 |
|
| 295 |
int |
| 296 |
smRealloc_mesh(sm) |
| 297 |
SM *sm; |
| 298 |
{ |
| 299 |
int fbytes,i,max_tris,max_verts; |
| 300 |
|
| 301 |
if(realloc_cnt <=0) |
| 302 |
realloc_cnt = SM_MAX_TRIS(sm); |
| 303 |
|
| 304 |
max_tris = SM_MAX_TRIS(sm) + realloc_cnt; |
| 305 |
fbytes = FLAG_BYTES(max_tris); |
| 306 |
|
| 307 |
if(!(SM_TRIS(sm) = (TRI *)realloc(SM_TRIS(sm),max_tris*sizeof(TRI)))) |
| 308 |
goto memerr; |
| 309 |
|
| 310 |
for(i=0; i< T_FLAGS; i++) |
| 311 |
if(!(SM_NTH_FLAGS(sm,i)=(int4 *)realloc((char *)SM_NTH_FLAGS(sm,i),fbytes))) |
| 312 |
goto memerr; |
| 313 |
|
| 314 |
SM_MAX_TRIS(sm) = max_tris; |
| 315 |
return(max_tris); |
| 316 |
|
| 317 |
memerr: |
| 318 |
error(SYSTEM, "out of memory in smRealloc_mesh()"); |
| 319 |
} |
| 320 |
|
| 321 |
/* Allocate and initialize a new mesh with max_verts and max_tris */ |
| 322 |
int |
| 323 |
smAlloc_mesh(sm,max_verts,max_tris) |
| 324 |
SM *sm; |
| 325 |
int max_verts,max_tris; |
| 326 |
{ |
| 327 |
int fbytes,i; |
| 328 |
|
| 329 |
fbytes = FLAG_BYTES(max_tris); |
| 330 |
|
| 331 |
if(!(SM_TRIS(sm) = (TRI *)realloc(NULL,max_tris*sizeof(TRI)))) |
| 332 |
goto memerr; |
| 333 |
|
| 334 |
if(!(SM_VERTS(sm) = (VERT *)realloc(NULL,max_verts*sizeof(VERT)))) |
| 335 |
goto memerr; |
| 336 |
|
| 337 |
for(i=0; i< T_FLAGS; i++) |
| 338 |
if(!(SM_NTH_FLAGS(sm,i)=(int4 *)realloc(NULL,fbytes))) |
| 339 |
goto memerr; |
| 340 |
|
| 341 |
SM_MAX_VERTS(sm) = max_verts; |
| 342 |
SM_MAX_TRIS(sm) = max_tris; |
| 343 |
|
| 344 |
realloc_cnt = max_verts >> 1; |
| 345 |
|
| 346 |
smInit_mesh(sm); |
| 347 |
|
| 348 |
return(max_tris); |
| 349 |
memerr: |
| 350 |
error(SYSTEM, "out of memory in smAlloc_mesh()"); |
| 351 |
} |
| 352 |
|
| 353 |
|
| 354 |
int |
| 355 |
compress_set(os) |
| 356 |
OBJECT *os; |
| 357 |
{ |
| 358 |
int i,j; |
| 359 |
|
| 360 |
for (i = 1, j = os[0]; i <= j; i++) |
| 361 |
{ |
| 362 |
if(SM_T_ID_VALID(smMesh,os[i])) |
| 363 |
continue; |
| 364 |
if(i==j) |
| 365 |
break; |
| 366 |
while(!SM_T_ID_VALID(smMesh,os[j]) && (i < j)) |
| 367 |
j--; |
| 368 |
if(i==j) |
| 369 |
break; |
| 370 |
os[i] = os[j--]; |
| 371 |
} |
| 372 |
i--; |
| 373 |
|
| 374 |
os[0] = i; |
| 375 |
return(i); |
| 376 |
|
| 377 |
} |
| 378 |
|
| 379 |
int |
| 380 |
smAlloc_tri(sm) |
| 381 |
SM *sm; |
| 382 |
{ |
| 383 |
int id; |
| 384 |
|
| 385 |
/* First check if there are any tris on the free list */ |
| 386 |
/* Otherwise, have we reached the end of the list yet?*/ |
| 387 |
if(SM_NUM_TRI(sm) < SM_MAX_TRIS(sm)) |
| 388 |
return(SM_NUM_TRI(sm)++); |
| 389 |
if((id = SM_AVAILABLE_TRIS(sm)) != -1) |
| 390 |
{ |
| 391 |
SM_AVAILABLE_TRIS(sm) = T_NEXT_AVAILABLE(SM_NTH_TRI(sm,id)); |
| 392 |
return(id); |
| 393 |
} |
| 394 |
if((id = SM_FREE_TRIS(sm)) != -1) |
| 395 |
{ |
| 396 |
dosets(compress_set); |
| 397 |
SM_AVAILABLE_TRIS(sm) = T_NEXT_FREE(SM_NTH_TRI(sm,id)); |
| 398 |
SM_FREE_TRIS(sm) = -1; |
| 399 |
return(id); |
| 400 |
} |
| 401 |
/*Else: realloc */ |
| 402 |
smRealloc_mesh(sm); |
| 403 |
return(SM_NUM_TRI(sm)++); |
| 404 |
} |
| 405 |
|
| 406 |
smFree_mesh(sm) |
| 407 |
SM *sm; |
| 408 |
{ |
| 409 |
int i; |
| 410 |
|
| 411 |
if(SM_TRIS(sm)) |
| 412 |
free(SM_TRIS(sm)); |
| 413 |
if(SM_VERTS(sm)) |
| 414 |
free(SM_VERTS(sm)); |
| 415 |
for(i=0; i< T_FLAGS; i++) |
| 416 |
if(SM_NTH_FLAGS(sm,i)) |
| 417 |
free(SM_NTH_FLAGS(sm,i)); |
| 418 |
} |
| 419 |
|
| 420 |
|
| 421 |
/* Initialize/clear global smL sample list for at least n samples */ |
| 422 |
smAlloc(max_samples) |
| 423 |
register int max_samples; |
| 424 |
{ |
| 425 |
unsigned nbytes; |
| 426 |
register unsigned i; |
| 427 |
int total_points; |
| 428 |
int max_tris,n; |
| 429 |
|
| 430 |
n = max_samples; |
| 431 |
/* If this is the first call, allocate sample,vertex and triangle lists */ |
| 432 |
if(!smMesh) |
| 433 |
{ |
| 434 |
if(!(smMesh = (SM *)malloc(sizeof(SM)))) |
| 435 |
error(SYSTEM,"smAlloc():Unable to allocate memory\n"); |
| 436 |
bzero(smMesh,sizeof(SM)); |
| 437 |
} |
| 438 |
else |
| 439 |
{ /* If existing structure: first deallocate */ |
| 440 |
smFree_mesh(smMesh); |
| 441 |
smFree_samples(smMesh); |
| 442 |
smFree_locator(smMesh); |
| 443 |
} |
| 444 |
|
| 445 |
/* First allocate at least n samples + extra points:at least enough |
| 446 |
necessary to form the BASE MESH- Default = 4; |
| 447 |
*/ |
| 448 |
SM_SAMP(smMesh) = sAlloc(&n,SM_EXTRA_POINTS); |
| 449 |
|
| 450 |
total_points = n + SM_EXTRA_POINTS; |
| 451 |
|
| 452 |
max_tris = total_points*4; |
| 453 |
/* Now allocate space for mesh vertices and triangles */ |
| 454 |
max_tris = smAlloc_mesh(smMesh, total_points, max_tris); |
| 455 |
|
| 456 |
/* Initialize the structure for point,triangle location. |
| 457 |
*/ |
| 458 |
smAlloc_locator(smMesh); |
| 459 |
} |
| 460 |
|
| 461 |
|
| 462 |
|
| 463 |
smInit_sm(sm,vp) |
| 464 |
SM *sm; |
| 465 |
FVECT vp; |
| 466 |
{ |
| 467 |
|
| 468 |
smDist_sum = 0; |
| 469 |
smNew_tri_cnt = 0; |
| 470 |
|
| 471 |
VCOPY(SM_VIEW_CENTER(sm),vp); |
| 472 |
smInit_locator(sm,vp); |
| 473 |
smInit_samples(sm); |
| 474 |
smInit_mesh(sm); |
| 475 |
smCreate_base_mesh(sm,SM_DEFAULT); |
| 476 |
} |
| 477 |
|
| 478 |
/* |
| 479 |
* int |
| 480 |
* smInit(n) : Initialize/clear data structures for n entries |
| 481 |
* int n; |
| 482 |
* |
| 483 |
* This routine allocates/initializes the sample, mesh, and point-location |
| 484 |
* structures for at least n samples. |
| 485 |
* If n is <= 0, then clear data structures. Returns number samples |
| 486 |
* actually allocated. |
| 487 |
*/ |
| 488 |
|
| 489 |
int |
| 490 |
smInit(n) |
| 491 |
register int n; |
| 492 |
{ |
| 493 |
int max_vertices; |
| 494 |
|
| 495 |
|
| 496 |
/* If n <=0, Just clear the existing structures */ |
| 497 |
if(n <= 0) |
| 498 |
{ |
| 499 |
smClear(smMesh); |
| 500 |
return(0); |
| 501 |
} |
| 502 |
|
| 503 |
/* Total mesh vertices includes the sample points and the extra vertices |
| 504 |
to form the base mesh |
| 505 |
*/ |
| 506 |
max_vertices = n + SM_EXTRA_POINTS; |
| 507 |
|
| 508 |
/* If the current mesh contains enough room, clear and return */ |
| 509 |
if(smMesh && (max_vertices <= SM_MAX_VERTS(smMesh)) && SM_MAX_SAMP(smMesh) <= |
| 510 |
n && SM_MAX_POINTS(smMesh) <= max_vertices) |
| 511 |
{ |
| 512 |
smClear(smMesh); |
| 513 |
return(SM_MAX_SAMP(smMesh)); |
| 514 |
} |
| 515 |
/* Otherwise- mesh must be allocated with the appropriate number of |
| 516 |
samples |
| 517 |
*/ |
| 518 |
smAlloc(n); |
| 519 |
|
| 520 |
return(SM_MAX_SAMP(smMesh)); |
| 521 |
} |
| 522 |
|
| 523 |
|
| 524 |
smLocator_apply(sm,v0,v1,v2,func) |
| 525 |
SM *sm; |
| 526 |
FVECT v0,v1,v2; |
| 527 |
FUNC func; |
| 528 |
{ |
| 529 |
STREE *st; |
| 530 |
FVECT tri[3]; |
| 531 |
|
| 532 |
st = SM_LOCATOR(sm); |
| 533 |
|
| 534 |
VSUB(tri[0],v0,SM_VIEW_CENTER(sm)); |
| 535 |
VSUB(tri[1],v1,SM_VIEW_CENTER(sm)); |
| 536 |
VSUB(tri[2],v2,SM_VIEW_CENTER(sm)); |
| 537 |
stVisit(st,tri,func); |
| 538 |
|
| 539 |
} |
| 540 |
|
| 541 |
|
| 542 |
/* NEW INSERTION!!! ******************************************************/ |
| 543 |
QUADTREE |
| 544 |
insert_tri(argptr,root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale, |
| 545 |
s0,s1,s2,sq0,sq1,sq2,rev,f,n) |
| 546 |
int *argptr; |
| 547 |
int root; |
| 548 |
QUADTREE qt; |
| 549 |
BCOORD q0[3],q1[3],q2[3]; |
| 550 |
BCOORD t0[3],t1[3],t2[3]; |
| 551 |
BCOORD dt10[3],dt21[3],dt02[3]; |
| 552 |
unsigned int scale,s0,s1,s2,sq0,sq1,sq2,rev; |
| 553 |
FUNC f; |
| 554 |
int n; |
| 555 |
{ |
| 556 |
OBJECT *optr,*tptr,t_set[QT_MAXSET+1]; |
| 557 |
int i,t_id; |
| 558 |
TRI *t; |
| 559 |
FVECT tri[3]; |
| 560 |
BCOORD b0[3],b1[3],b2[3]; |
| 561 |
BCOORD tb0[3],tb1[3],tb2[3]; |
| 562 |
BCOORD db10[3],db21[3],db02[3]; |
| 563 |
BCOORD a,b,c,qa,qb,qc; |
| 564 |
FUNC tfunc; |
| 565 |
|
| 566 |
t_id = *argptr; |
| 567 |
|
| 568 |
/* If the set is empty - just add */ |
| 569 |
if(QT_IS_EMPTY(qt)) |
| 570 |
return(qtadduelem(qt,t_id)); |
| 571 |
|
| 572 |
/* If the set size is below expansion threshold,or at maximum |
| 573 |
number of quadtree levels : just add */ |
| 574 |
optr = qtqueryset(qt); |
| 575 |
if(QT_SET_CNT(optr) < QT_SET_THRESHOLD || (n > (QT_MAX_LEVELS-2))) |
| 576 |
return(qtadduelem(qt,t_id)); |
| 577 |
/* otherwise: expand node- and insert tri, and reinsert existing tris |
| 578 |
in set to children of new node |
| 579 |
*/ |
| 580 |
/* First tri compressing set */ |
| 581 |
#ifdef NEWSETS0 |
| 582 |
if(qtcompressuelem(qt,compress_set) < QT_SET_THRESHOLD) |
| 583 |
/* Get set: If greater than standard size: allocate memory to hold */ |
| 584 |
return(qtadduelem(qt,t_id)); |
| 585 |
#endif |
| 586 |
if(QT_SET_CNT(optr) > QT_MAXSET) |
| 587 |
{ |
| 588 |
if(!(tptr = (OBJECT *)malloc((QT_SET_CNT(optr)+1)*sizeof(OBJECT)))) |
| 589 |
goto memerr; |
| 590 |
} |
| 591 |
else |
| 592 |
tptr = t_set; |
| 593 |
qtgetset(tptr,qt); |
| 594 |
|
| 595 |
/* subdivide node */ |
| 596 |
qtfreeleaf(qt); |
| 597 |
qtSubdivide(qt); |
| 598 |
|
| 599 |
a = q1[0]; b = q0[1]; c = q0[2]; |
| 600 |
qa = q0[0]; qb = q1[1]; qc = q2[2]; |
| 601 |
/* First add current tri: have all of the information */ |
| 602 |
if(rev) |
| 603 |
qt = qtInsert_tri_rev(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale, |
| 604 |
s0,s1,s2,sq0,sq1,sq2,f,n); |
| 605 |
else |
| 606 |
qt = qtInsert_tri(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale, |
| 607 |
s0,s1,s2,sq0,sq1,sq2,f,n); |
| 608 |
|
| 609 |
/* Now add in all of the rest; */ |
| 610 |
F_FUNC(tfunc) = F_FUNC(f); |
| 611 |
for(optr = QT_SET_PTR(tptr),i=QT_SET_CNT(tptr); i > 0; i--) |
| 612 |
{ |
| 613 |
t_id = QT_SET_NEXT_ELEM(optr); |
| 614 |
t = SM_NTH_TRI(smMesh,t_id); |
| 615 |
if(!T_IS_VALID(t)) |
| 616 |
continue; |
| 617 |
F_ARGS(tfunc) = &t_id; |
| 618 |
VSUB(tri[0],SM_T_NTH_WV(smMesh,t,0),SM_VIEW_CENTER(smMesh)); |
| 619 |
VSUB(tri[1],SM_T_NTH_WV(smMesh,t,1),SM_VIEW_CENTER(smMesh)); |
| 620 |
VSUB(tri[2],SM_T_NTH_WV(smMesh,t,2),SM_VIEW_CENTER(smMesh)); |
| 621 |
convert_tri_to_frame(root,tri,b0,b1,b2,db10,db21,db02); |
| 622 |
|
| 623 |
/* Calculate appropriate sidedness values */ |
| 624 |
SIDES_GTR(b0,b1,b2,s0,s1,s2,a,b,c); |
| 625 |
SIDES_GTR(b0,b1,b2,sq0,sq1,sq2,qa,qb,qc); |
| 626 |
if(rev) |
| 627 |
qt = qtInsert_tri_rev(root,qt,q0,q1,q2,b0,b1,b2,db10,db21,db02,scale, |
| 628 |
s0,s1,s2,sq0,sq1,sq2,tfunc,n); |
| 629 |
else |
| 630 |
qt = qtInsert_tri(root,qt,q0,q1,q2,b0,b1,b2,db10,db21,db02,scale, |
| 631 |
s0,s1,s2,sq0,sq1,sq2,tfunc,n); |
| 632 |
} |
| 633 |
/* If we allocated memory: free it */ |
| 634 |
if( tptr != t_set) |
| 635 |
free(tptr); |
| 636 |
|
| 637 |
return(qt); |
| 638 |
memerr: |
| 639 |
error(SYSTEM,"expand_node():Unable to allocate memory"); |
| 640 |
|
| 641 |
} |
| 642 |
|
| 643 |
|
| 644 |
|
| 645 |
smLocator_add_tri(sm,t_id,v0_id,v1_id,v2_id) |
| 646 |
SM *sm; |
| 647 |
int t_id; |
| 648 |
int v0_id,v1_id,v2_id; |
| 649 |
{ |
| 650 |
FVECT tri[3]; |
| 651 |
FUNC f; |
| 652 |
|
| 653 |
#ifdef DEBUG |
| 654 |
if(T_NTH_NBR(SM_NTH_TRI(sm,t_id),0)== -1 || |
| 655 |
T_NTH_NBR(SM_NTH_TRI(sm,t_id),1)== -1 || |
| 656 |
T_NTH_NBR(SM_NTH_TRI(sm,t_id),2)== -1) |
| 657 |
error("Invalid tri: smLocator_add_tri()\n"); |
| 658 |
|
| 659 |
if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,t_id),0))) || |
| 660 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,t_id),1))) || |
| 661 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,t_id),2)))) |
| 662 |
error("Invalid tri: smLocator_add_tri()\n"); |
| 663 |
#endif |
| 664 |
|
| 665 |
VSUB(tri[0],SM_NTH_WV(sm,v0_id),SM_VIEW_CENTER(sm)); |
| 666 |
VSUB(tri[1],SM_NTH_WV(sm,v1_id),SM_VIEW_CENTER(sm)); |
| 667 |
VSUB(tri[2],SM_NTH_WV(sm,v2_id),SM_VIEW_CENTER(sm)); |
| 668 |
|
| 669 |
F_FUNC(f) = insert_tri; |
| 670 |
F_ARGS(f) = &t_id; |
| 671 |
stInsert_tri(SM_LOCATOR(sm),tri,f); |
| 672 |
} |
| 673 |
|
| 674 |
/* Add a triangle to the base array with vertices v1-v2-v3 */ |
| 675 |
int |
| 676 |
smAdd_tri(sm, v0_id,v1_id,v2_id) |
| 677 |
SM *sm; |
| 678 |
int v0_id,v1_id,v2_id; |
| 679 |
{ |
| 680 |
int t_id; |
| 681 |
TRI *t; |
| 682 |
#ifdef DEBUG |
| 683 |
if(v0_id==v1_id || v0_id==v2_id || v1_id==v2_id) |
| 684 |
error(CONSISTENCY,"smAdd_tri: invalid vertex ids\n"); |
| 685 |
#endif |
| 686 |
t_id = smAlloc_tri(sm); |
| 687 |
|
| 688 |
if(t_id == -1) |
| 689 |
return(t_id); |
| 690 |
|
| 691 |
t = SM_NTH_TRI(sm,t_id); |
| 692 |
|
| 693 |
T_CLEAR_NBRS(t); |
| 694 |
/* set the triangle vertex ids */ |
| 695 |
T_NTH_V(t,0) = v0_id; |
| 696 |
T_NTH_V(t,1) = v1_id; |
| 697 |
T_NTH_V(t,2) = v2_id; |
| 698 |
|
| 699 |
SM_NTH_VERT(sm,v0_id) = t_id; |
| 700 |
SM_NTH_VERT(sm,v1_id) = t_id; |
| 701 |
SM_NTH_VERT(sm,v2_id) = t_id; |
| 702 |
|
| 703 |
smClear_tri_flags(sm,t_id); |
| 704 |
if(SM_BASE_ID(sm,v0_id) || SM_BASE_ID(sm,v1_id) || SM_BASE_ID(sm,v2_id)) |
| 705 |
{ |
| 706 |
SM_SET_NTH_T_BASE(sm,t_id); |
| 707 |
} |
| 708 |
else |
| 709 |
{ |
| 710 |
S_SET_FLAG(T_NTH_V(t,0)); |
| 711 |
S_SET_FLAG(T_NTH_V(t,1)); |
| 712 |
S_SET_FLAG(T_NTH_V(t,2)); |
| 713 |
} |
| 714 |
SM_SET_NTH_T_ACTIVE(sm,t_id); |
| 715 |
|
| 716 |
SM_SAMPLE_TRIS(sm)++; |
| 717 |
|
| 718 |
/* return initialized triangle */ |
| 719 |
return(t_id); |
| 720 |
} |
| 721 |
|
| 722 |
|
| 723 |
void |
| 724 |
smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id,add_ptr) |
| 725 |
SM *sm; |
| 726 |
int t_id,t1_id; |
| 727 |
int e,e1; |
| 728 |
int *tn_id,*tn1_id; |
| 729 |
LIST **add_ptr; |
| 730 |
{ |
| 731 |
int verts[3],enext,eprev,e1next,e1prev; |
| 732 |
TRI *n,*ta,*tb,*t,*t1; |
| 733 |
FVECT p1,p2,p3; |
| 734 |
int ta_id,tb_id; |
| 735 |
/* form new diagonal (e relative to t, and e1 relative to t1) |
| 736 |
defined by quadrilateral formed by t,t1- swap for the opposite diagonal |
| 737 |
*/ |
| 738 |
enext = (e+1)%3; |
| 739 |
eprev = (e+2)%3; |
| 740 |
e1next = (e1+1)%3; |
| 741 |
e1prev = (e1+2)%3; |
| 742 |
verts[e] = T_NTH_V(SM_NTH_TRI(sm,t_id),e); |
| 743 |
verts[enext] = T_NTH_V(SM_NTH_TRI(sm,t_id),enext); |
| 744 |
verts[eprev] = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1); |
| 745 |
ta_id = smAdd_tri(sm,verts[0],verts[1],verts[2]); |
| 746 |
*add_ptr = push_data(*add_ptr,ta_id); |
| 747 |
verts[e1] = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1); |
| 748 |
verts[e1next] = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1next); |
| 749 |
verts[e1prev] = T_NTH_V(SM_NTH_TRI(sm,t_id),e); |
| 750 |
tb_id = smAdd_tri(sm,verts[0],verts[1],verts[2]); |
| 751 |
|
| 752 |
*add_ptr = push_data(*add_ptr,tb_id); |
| 753 |
ta = SM_NTH_TRI(sm,ta_id); |
| 754 |
tb = SM_NTH_TRI(sm,tb_id); |
| 755 |
t = SM_NTH_TRI(sm,t_id); |
| 756 |
t1 = SM_NTH_TRI(sm,t1_id); |
| 757 |
/* set the neighbors */ |
| 758 |
T_NTH_NBR(ta,e) = T_NTH_NBR(t1,e1next); |
| 759 |
T_NTH_NBR(tb,e1) = T_NTH_NBR(t,enext); |
| 760 |
T_NTH_NBR(ta,enext)= tb_id; |
| 761 |
T_NTH_NBR(tb,e1next)= ta_id; |
| 762 |
T_NTH_NBR(ta,eprev)=T_NTH_NBR(t,eprev); |
| 763 |
T_NTH_NBR(tb,e1prev)=T_NTH_NBR(t1,e1prev); |
| 764 |
|
| 765 |
|
| 766 |
#ifdef DEBUG |
| 767 |
if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,0))) || |
| 768 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,1))) || |
| 769 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,2))) || |
| 770 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,0))) || |
| 771 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,1))) || |
| 772 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,2)))) |
| 773 |
goto Ltri_error; |
| 774 |
/* |
| 775 |
if(SM_NTH_TRI(sm,T_NTH_NBR(ta,0))==SM_NTH_TRI(sm,T_NTH_NBR(ta,1)) || |
| 776 |
SM_NTH_TRI(sm,T_NTH_NBR(ta,0))==SM_NTH_TRI(sm,T_NTH_NBR(ta,2)) || |
| 777 |
SM_NTH_TRI(sm,T_NTH_NBR(ta,1))==SM_NTH_TRI(sm,T_NTH_NBR(ta,2)) || |
| 778 |
SM_NTH_TRI(sm,T_NTH_NBR(tb,0))==SM_NTH_TRI(sm,T_NTH_NBR(tb,1)) || |
| 779 |
SM_NTH_TRI(sm,T_NTH_NBR(tb,0))==SM_NTH_TRI(sm,T_NTH_NBR(tb,2)) || |
| 780 |
SM_NTH_TRI(sm,T_NTH_NBR(tb,1))==SM_NTH_TRI(sm,T_NTH_NBR(tb,2)) ) |
| 781 |
goto Ltri_error; |
| 782 |
*/ |
| 783 |
#endif |
| 784 |
/* Reset neighbor pointers of original neighbors */ |
| 785 |
n = SM_NTH_TRI(sm,T_NTH_NBR(t,enext)); |
| 786 |
#ifdef DEBUG |
| 787 |
if(!T_IS_VALID(n)) |
| 788 |
goto Ltri_error; |
| 789 |
#endif |
| 790 |
T_NTH_NBR(n,T_NTH_NBR_PTR(t_id,n)) = tb_id; |
| 791 |
n = SM_NTH_TRI(sm,T_NTH_NBR(t,eprev)); |
| 792 |
#ifdef DEBUG |
| 793 |
if(!T_IS_VALID(n)) |
| 794 |
goto Ltri_error; |
| 795 |
#endif |
| 796 |
T_NTH_NBR(n,T_NTH_NBR_PTR(t_id,n)) = ta_id; |
| 797 |
|
| 798 |
n = SM_NTH_TRI(sm,T_NTH_NBR(t1,e1next)); |
| 799 |
#ifdef DEBUG |
| 800 |
if(!T_IS_VALID(n)) |
| 801 |
goto Ltri_error; |
| 802 |
#endif |
| 803 |
T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = ta_id; |
| 804 |
n = SM_NTH_TRI(sm,T_NTH_NBR(t1,e1prev)); |
| 805 |
#ifdef DEBUG |
| 806 |
if(!T_IS_VALID(n)) |
| 807 |
goto Ltri_error; |
| 808 |
#endif |
| 809 |
T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = tb_id; |
| 810 |
|
| 811 |
#ifdef DEBUG |
| 812 |
T_VALID_FLAG(SM_NTH_TRI(sm,t_id))=-1; |
| 813 |
T_VALID_FLAG(SM_NTH_TRI(sm,t1_id))=-1; |
| 814 |
#endif |
| 815 |
|
| 816 |
remove_from_list(t_id,add_ptr); |
| 817 |
remove_from_list(t1_id,add_ptr); |
| 818 |
|
| 819 |
smDelete_tri(sm,t_id); |
| 820 |
smDelete_tri(sm,t1_id); |
| 821 |
|
| 822 |
*tn_id = ta_id; |
| 823 |
*tn1_id = tb_id; |
| 824 |
|
| 825 |
#ifdef DEBUG |
| 826 |
if(T_NTH_NBR(SM_NTH_TRI(sm,ta_id),0)== -1 || |
| 827 |
T_NTH_NBR(SM_NTH_TRI(sm,ta_id),1)== -1 || |
| 828 |
T_NTH_NBR(SM_NTH_TRI(sm,ta_id),2)== -1 || |
| 829 |
T_NTH_NBR(SM_NTH_TRI(sm,tb_id),0)== -1 || |
| 830 |
T_NTH_NBR(SM_NTH_TRI(sm,tb_id),1)== -1 || |
| 831 |
T_NTH_NBR(SM_NTH_TRI(sm,tb_id),2)== -1) |
| 832 |
goto Ltri_error; |
| 833 |
if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,ta_id),0))) || |
| 834 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,ta_id),1))) || |
| 835 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,ta_id),2)))) |
| 836 |
goto Ltri_error; |
| 837 |
if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tb_id),0))) || |
| 838 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tb_id),1))) || |
| 839 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tb_id),2)))) |
| 840 |
goto Ltri_error; |
| 841 |
#endif |
| 842 |
return; |
| 843 |
Ltri_error: |
| 844 |
error(CONSISTENCY,"Invalid tri: smTris_swap_edge()\n"); |
| 845 |
} |
| 846 |
|
| 847 |
add_new_tri(id) |
| 848 |
int id; |
| 849 |
{ |
| 850 |
if(smNew_tri_cnt == smNew_tri_size) |
| 851 |
{ |
| 852 |
smNew_tri_size += S_INC; |
| 853 |
smNew_tris=(T_DEPTH *)realloc(smNew_tris,sizeof(T_DEPTH)*smNew_tri_size); |
| 854 |
if(!smNew_tris) |
| 855 |
error(SYSTEM,"Out of memory in add_new_tris()\n"); |
| 856 |
} |
| 857 |
smNew_tris[smNew_tri_cnt++].tri = id; |
| 858 |
} |
| 859 |
|
| 860 |
smUpdate_locator(sm,add_list) |
| 861 |
SM *sm; |
| 862 |
LIST *add_list; |
| 863 |
{ |
| 864 |
int t_id,i; |
| 865 |
TRI *t; |
| 866 |
OBJECT *optr; |
| 867 |
LIST *list; |
| 868 |
|
| 869 |
list = add_list; |
| 870 |
while(list) |
| 871 |
{ |
| 872 |
t_id = LIST_DATA(list); |
| 873 |
add_new_tri(t_id); |
| 874 |
list = LIST_NEXT(list); |
| 875 |
} |
| 876 |
|
| 877 |
while(add_list) |
| 878 |
{ |
| 879 |
t_id = pop_list(&add_list); |
| 880 |
t = SM_NTH_TRI(sm,t_id); |
| 881 |
smLocator_add_tri(sm,t_id,T_NTH_V(t,0),T_NTH_V(t,1),T_NTH_V(t,2)); |
| 882 |
} |
| 883 |
} |
| 884 |
|
| 885 |
int |
| 886 |
smFix_tris(sm,id,tlist,add_list) |
| 887 |
SM *sm; |
| 888 |
int id; |
| 889 |
LIST *tlist,*add_list; |
| 890 |
{ |
| 891 |
TRI *t,*t_opp; |
| 892 |
FVECT p,p0,p1,p2; |
| 893 |
int e,e1,swapped = 0; |
| 894 |
int t_id,t_opp_id; |
| 895 |
LIST *del_list=NULL,*lptr; |
| 896 |
|
| 897 |
VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm)); |
| 898 |
while(tlist) |
| 899 |
{ |
| 900 |
t_id = pop_list(&tlist); |
| 901 |
#ifdef DEBUG |
| 902 |
if(t_id==INVALID || t_id > smMesh->num_tri) |
| 903 |
error(CONSISTENCY,"Invalid tri id smFix_tris()\n"); |
| 904 |
#endif |
| 905 |
t = SM_NTH_TRI(sm,t_id); |
| 906 |
e = T_WHICH_V(t,id); |
| 907 |
t_opp_id = T_NTH_NBR(t,e); |
| 908 |
#ifdef DEBUG |
| 909 |
if(t_opp_id==INVALID || t_opp_id > smMesh->num_tri) |
| 910 |
error(CONSISTENCY,"Invalid tri id smFix_tris()\n"); |
| 911 |
#endif |
| 912 |
t_opp = SM_NTH_TRI(sm,t_opp_id); |
| 913 |
#ifdef DEBUG |
| 914 |
if(!T_IS_VALID(t_opp)) |
| 915 |
error(CONSISTENCY,"Invalid trismFix_tris()\n"); |
| 916 |
#endif |
| 917 |
smDir_in_cone(sm,p0,T_NTH_V(t_opp,0)); |
| 918 |
smDir_in_cone(sm,p1,T_NTH_V(t_opp,1)); |
| 919 |
smDir_in_cone(sm,p2,T_NTH_V(t_opp,2)); |
| 920 |
if(point_in_cone(p,p0,p1,p2)) |
| 921 |
{ |
| 922 |
swapped = 1; |
| 923 |
e1 = T_NTH_NBR_PTR(t_id,t_opp); |
| 924 |
/* check list for t_opp and Remove if there */ |
| 925 |
remove_from_list(t_opp_id,&tlist); |
| 926 |
smTris_swap_edge(sm,t_id,t_opp_id,e,e1,&t_id,&t_opp_id, |
| 927 |
&add_list); |
| 928 |
tlist = push_data(tlist,t_id); |
| 929 |
tlist = push_data(tlist,t_opp_id); |
| 930 |
} |
| 931 |
} |
| 932 |
|
| 933 |
smUpdate_locator(sm,add_list); |
| 934 |
|
| 935 |
return(swapped); |
| 936 |
} |
| 937 |
|
| 938 |
/* Give the vertex "id" and a triangle "t" that it belongs to- return the |
| 939 |
next nbr in a counter clockwise order about vertex "id" |
| 940 |
*/ |
| 941 |
int |
| 942 |
smTri_next_ccw_nbr(sm,t,id) |
| 943 |
SM *sm; |
| 944 |
TRI *t; |
| 945 |
int id; |
| 946 |
{ |
| 947 |
int which; |
| 948 |
int nbr_id; |
| 949 |
|
| 950 |
/* Want the edge for which "id" is the destination */ |
| 951 |
which = T_WHICH_V(t,id); |
| 952 |
if(which== INVALID) |
| 953 |
return(which); |
| 954 |
|
| 955 |
nbr_id = T_NTH_NBR(t,(which + 1)% 3); |
| 956 |
return(nbr_id); |
| 957 |
} |
| 958 |
|
| 959 |
smClear_tri_flags(sm,id) |
| 960 |
SM *sm; |
| 961 |
int id; |
| 962 |
{ |
| 963 |
int i; |
| 964 |
|
| 965 |
for(i=0; i < T_FLAGS; i++) |
| 966 |
SM_CLR_NTH_T_FLAG(sm,id,i); |
| 967 |
|
| 968 |
} |
| 969 |
|
| 970 |
/* Locate the point-id in the point location structure: */ |
| 971 |
int |
| 972 |
smInsert_samp(sm,s_id,tri_id,on,which) |
| 973 |
SM *sm; |
| 974 |
int s_id,tri_id; |
| 975 |
int on,which; |
| 976 |
{ |
| 977 |
int v_id[3],topp_id,i; |
| 978 |
int t0_id,t1_id,t2_id,t3_id,replaced; |
| 979 |
int e0,e1,e2,opp0,opp1,opp2,opp_id; |
| 980 |
LIST *tlist,*add_list; |
| 981 |
FVECT npt; |
| 982 |
TRI *tri,*nbr,*topp; |
| 983 |
|
| 984 |
if(tri_id==18611 && s_id == 2243) |
| 985 |
sleep(1); |
| 986 |
if(s_id == 2649 && tri_id == 13302) |
| 987 |
sleep(1); |
| 988 |
add_list = NULL; |
| 989 |
for(i=0; i<3;i++) |
| 990 |
v_id[i] = T_NTH_V(SM_NTH_TRI(sm,tri_id),i); |
| 991 |
|
| 992 |
/* If falls on existing edge */ |
| 993 |
if(on == ON_E) |
| 994 |
{ |
| 995 |
tri = SM_NTH_TRI(sm,tri_id); |
| 996 |
topp_id = T_NTH_NBR(tri,which); |
| 997 |
e0 = which; |
| 998 |
e1 = (which+1)%3; |
| 999 |
e2 = (which+2)%3; |
| 1000 |
topp = SM_NTH_TRI(sm,topp_id); |
| 1001 |
opp0 = T_NTH_NBR_PTR(tri_id,topp); |
| 1002 |
opp_id = T_NTH_V(topp,opp0); |
| 1003 |
opp1 = (opp0+1)%3; |
| 1004 |
opp2 = (opp0+2)%3; |
| 1005 |
|
| 1006 |
/* Create 4 triangles */ |
| 1007 |
/* /|\ /|\ |
| 1008 |
/ | \ / | \ |
| 1009 |
/ * \ ----> /__|__\ |
| 1010 |
\ | / \ | / |
| 1011 |
\ | / \ | / |
| 1012 |
\|/ \|/ |
| 1013 |
*/ |
| 1014 |
t0_id = smAdd_tri(sm,s_id,v_id[e0],v_id[e1]); |
| 1015 |
add_list = push_data(add_list,t0_id); |
| 1016 |
t1_id = smAdd_tri(sm,s_id,v_id[e2],v_id[e0]); |
| 1017 |
add_list = push_data(add_list,t1_id); |
| 1018 |
t2_id = smAdd_tri(sm,s_id,v_id[e1],opp_id); |
| 1019 |
add_list = push_data(add_list,t2_id); |
| 1020 |
t3_id = smAdd_tri(sm,s_id,opp_id,v_id[e2]); |
| 1021 |
add_list = push_data(add_list,t3_id); |
| 1022 |
/* CAUTION: tri must be assigned after Add_tri: pointers may change*/ |
| 1023 |
tri = SM_NTH_TRI(sm,tri_id); |
| 1024 |
topp =SM_NTH_TRI(sm,topp_id); |
| 1025 |
|
| 1026 |
/* Set the neighbor pointers for the new tris */ |
| 1027 |
T_NTH_NBR(SM_NTH_TRI(sm,t0_id),0) = T_NTH_NBR(tri,e2); |
| 1028 |
T_NTH_NBR(SM_NTH_TRI(sm,t0_id),1) = t2_id; |
| 1029 |
T_NTH_NBR(SM_NTH_TRI(sm,t0_id),2) = t1_id; |
| 1030 |
T_NTH_NBR(SM_NTH_TRI(sm,t1_id),0) = T_NTH_NBR(tri,e1); |
| 1031 |
T_NTH_NBR(SM_NTH_TRI(sm,t1_id),1) = t0_id; |
| 1032 |
T_NTH_NBR(SM_NTH_TRI(sm,t1_id),2) = t3_id; |
| 1033 |
T_NTH_NBR(SM_NTH_TRI(sm,t2_id),0) = T_NTH_NBR(topp,opp1); |
| 1034 |
T_NTH_NBR(SM_NTH_TRI(sm,t2_id),1) = t3_id; |
| 1035 |
T_NTH_NBR(SM_NTH_TRI(sm,t2_id),2) = t0_id; |
| 1036 |
T_NTH_NBR(SM_NTH_TRI(sm,t3_id),0) = T_NTH_NBR(topp,opp2); |
| 1037 |
T_NTH_NBR(SM_NTH_TRI(sm,t3_id),1) = t1_id; |
| 1038 |
T_NTH_NBR(SM_NTH_TRI(sm,t3_id),2) = t2_id; |
| 1039 |
|
| 1040 |
/* Reset the neigbor pointers for the neighbors of the original */ |
| 1041 |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,e1)); |
| 1042 |
T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t1_id; |
| 1043 |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,e2)); |
| 1044 |
T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t0_id; |
| 1045 |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(topp,opp1)); |
| 1046 |
T_NTH_NBR(nbr,T_NTH_NBR_PTR(topp_id,nbr)) = t2_id; |
| 1047 |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(topp,opp2)); |
| 1048 |
T_NTH_NBR(nbr,T_NTH_NBR_PTR(topp_id,nbr)) = t3_id; |
| 1049 |
#ifdef DEBUG |
| 1050 |
T_VALID_FLAG(SM_NTH_TRI(sm,tri_id))=-1; |
| 1051 |
T_VALID_FLAG(SM_NTH_TRI(sm,topp_id))=-1; |
| 1052 |
#endif |
| 1053 |
tlist = push_data(NULL,t0_id); |
| 1054 |
tlist = push_data(tlist,t1_id); |
| 1055 |
tlist = push_data(tlist,t2_id); |
| 1056 |
tlist = push_data(tlist,t3_id); |
| 1057 |
} |
| 1058 |
else |
| 1059 |
{ |
| 1060 |
/* Create 3 triangles */ |
| 1061 |
/* / \ /|\ |
| 1062 |
/ \ / | \ |
| 1063 |
/ * \ ----> / | \ |
| 1064 |
/ \ / / \ \ |
| 1065 |
/ \ / / \ \ |
| 1066 |
/___________\ //_________\\ |
| 1067 |
*/ |
| 1068 |
|
| 1069 |
t0_id = smAdd_tri(sm,s_id,v_id[0],v_id[1]); |
| 1070 |
add_list = push_data(add_list,t0_id); |
| 1071 |
t1_id = smAdd_tri(sm,s_id,v_id[1],v_id[2]); |
| 1072 |
add_list = push_data(add_list,t1_id); |
| 1073 |
t2_id = smAdd_tri(sm,s_id,v_id[2],v_id[0]); |
| 1074 |
add_list = push_data(add_list,t2_id); |
| 1075 |
|
| 1076 |
/* CAUTION: tri must be assigned after Add_tri: pointers may change*/ |
| 1077 |
tri = SM_NTH_TRI(sm,tri_id); |
| 1078 |
/* Set the neighbor pointers for the new tris */ |
| 1079 |
T_NTH_NBR(SM_NTH_TRI(sm,t0_id),0) = T_NTH_NBR(tri,2); |
| 1080 |
T_NTH_NBR(SM_NTH_TRI(sm,t0_id),1) = t1_id; |
| 1081 |
T_NTH_NBR(SM_NTH_TRI(sm,t0_id),2) = t2_id; |
| 1082 |
T_NTH_NBR(SM_NTH_TRI(sm,t1_id),0) = T_NTH_NBR(tri,0); |
| 1083 |
T_NTH_NBR(SM_NTH_TRI(sm,t1_id),1) = t2_id; |
| 1084 |
T_NTH_NBR(SM_NTH_TRI(sm,t1_id),2) = t0_id; |
| 1085 |
T_NTH_NBR(SM_NTH_TRI(sm,t2_id),0) = T_NTH_NBR(tri,1); |
| 1086 |
T_NTH_NBR(SM_NTH_TRI(sm,t2_id),1) = t0_id; |
| 1087 |
T_NTH_NBR(SM_NTH_TRI(sm,t2_id),2) = t1_id; |
| 1088 |
|
| 1089 |
/* Reset the neigbor pointers for the neighbors of the original */ |
| 1090 |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,0)); |
| 1091 |
T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t1_id; |
| 1092 |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,1)); |
| 1093 |
T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t2_id; |
| 1094 |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,2)); |
| 1095 |
T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t0_id; |
| 1096 |
|
| 1097 |
tlist = push_data(NULL,t0_id); |
| 1098 |
tlist = push_data(tlist,t1_id); |
| 1099 |
tlist = push_data(tlist,t2_id); |
| 1100 |
} |
| 1101 |
/* Fix up the new triangles*/ |
| 1102 |
smFix_tris(sm,s_id,tlist,add_list); |
| 1103 |
|
| 1104 |
smDelete_tri(sm,tri_id); |
| 1105 |
if(on==ON_E) |
| 1106 |
smDelete_tri(sm,topp_id); |
| 1107 |
|
| 1108 |
return(TRUE); |
| 1109 |
|
| 1110 |
#ifdef DEBUG |
| 1111 |
Ladderror: |
| 1112 |
error(CONSISTENCY,"Invalid tri: smInsert_samp()\n"); |
| 1113 |
#endif |
| 1114 |
} |
| 1115 |
|
| 1116 |
int |
| 1117 |
smTri_in_set(sm,p,optr,onptr,whichptr) |
| 1118 |
SM *sm; |
| 1119 |
FVECT p; |
| 1120 |
OBJECT *optr; |
| 1121 |
int *onptr,*whichptr; |
| 1122 |
{ |
| 1123 |
int i,t_id,on0,on1,on2; |
| 1124 |
FVECT n,v0,v1,v2; |
| 1125 |
TRI *t; |
| 1126 |
double side; |
| 1127 |
|
| 1128 |
for (i = QT_SET_CNT(optr),optr = QT_SET_PTR(optr);i > 0; i--) |
| 1129 |
{ |
| 1130 |
/* Find the first triangle that pt falls */ |
| 1131 |
t_id = QT_SET_NEXT_ELEM(optr); |
| 1132 |
t = SM_NTH_TRI(sm,t_id); |
| 1133 |
if(!T_IS_VALID(t)) |
| 1134 |
continue; |
| 1135 |
VSUB(v0,SM_T_NTH_WV(sm,t,0),SM_VIEW_CENTER(sm)); |
| 1136 |
VSUB(v1,SM_T_NTH_WV(sm,t,1),SM_VIEW_CENTER(sm)); |
| 1137 |
VSUB(v2,SM_T_NTH_WV(sm,t,2),SM_VIEW_CENTER(sm)); |
| 1138 |
|
| 1139 |
if(EQUAL_VEC3(v0,p)) |
| 1140 |
{ |
| 1141 |
*onptr = ON_V; |
| 1142 |
*whichptr = 0; |
| 1143 |
return(t_id); |
| 1144 |
} |
| 1145 |
if(EQUAL_VEC3(v1,p)) |
| 1146 |
{ |
| 1147 |
*onptr = ON_V; |
| 1148 |
*whichptr = 1; |
| 1149 |
return(t_id); |
| 1150 |
} |
| 1151 |
if(EQUAL_VEC3(v2,p)) |
| 1152 |
{ |
| 1153 |
*onptr = ON_V; |
| 1154 |
*whichptr = 2; |
| 1155 |
return(t_id); |
| 1156 |
} |
| 1157 |
|
| 1158 |
on0 = on1 =on2 = 0; |
| 1159 |
VCROSS(n,v0,v1); |
| 1160 |
side = DOT(n,p); |
| 1161 |
if(ZERO(side)) |
| 1162 |
on2 = TRUE; |
| 1163 |
else |
| 1164 |
if(side >0.0) |
| 1165 |
continue; |
| 1166 |
|
| 1167 |
VCROSS(n,v1,v2); |
| 1168 |
side = DOT(n,p); |
| 1169 |
if(ZERO(side)) |
| 1170 |
on0 = TRUE; |
| 1171 |
else |
| 1172 |
if(side >0.0) |
| 1173 |
continue; |
| 1174 |
|
| 1175 |
VCROSS(n,v2,v0); |
| 1176 |
side = DOT(n,p); |
| 1177 |
if(ZERO(side)) |
| 1178 |
on1 = TRUE; |
| 1179 |
else |
| 1180 |
if(side >0.0) |
| 1181 |
continue; |
| 1182 |
if(on0) |
| 1183 |
{ |
| 1184 |
if(on1) |
| 1185 |
{ |
| 1186 |
*onptr = ON_P; |
| 1187 |
*whichptr = 2; |
| 1188 |
} |
| 1189 |
else |
| 1190 |
if(on2) |
| 1191 |
{ |
| 1192 |
*onptr = ON_P; |
| 1193 |
*whichptr = 1; |
| 1194 |
} |
| 1195 |
else |
| 1196 |
{ |
| 1197 |
*onptr = ON_E; |
| 1198 |
*whichptr = 0; |
| 1199 |
} |
| 1200 |
return(t_id); |
| 1201 |
} |
| 1202 |
if(on1) |
| 1203 |
{ |
| 1204 |
if(on2) |
| 1205 |
{ |
| 1206 |
*onptr = ON_P; |
| 1207 |
*whichptr = 0; |
| 1208 |
} |
| 1209 |
else |
| 1210 |
{ |
| 1211 |
*onptr = ON_E; |
| 1212 |
*whichptr = 1; |
| 1213 |
} |
| 1214 |
return(t_id); |
| 1215 |
} |
| 1216 |
if(on2) |
| 1217 |
{ |
| 1218 |
*onptr = ON_E; |
| 1219 |
*whichptr = 2; |
| 1220 |
return(t_id); |
| 1221 |
} |
| 1222 |
*onptr = IN_T; |
| 1223 |
return(t_id); |
| 1224 |
} |
| 1225 |
return(INVALID); |
| 1226 |
} |
| 1227 |
|
| 1228 |
int |
| 1229 |
smPointLocateTri(sm,p,onptr,whichptr) |
| 1230 |
SM *sm; |
| 1231 |
FVECT p; |
| 1232 |
int *onptr,*whichptr; |
| 1233 |
{ |
| 1234 |
QUADTREE qt,*optr; |
| 1235 |
FVECT tpt; |
| 1236 |
int tri_id; |
| 1237 |
|
| 1238 |
VSUB(tpt,p,SM_VIEW_CENTER(sm)); |
| 1239 |
qt = smPointLocateCell(sm,tpt); |
| 1240 |
if(QT_IS_EMPTY(qt)) |
| 1241 |
return(INVALID); |
| 1242 |
|
| 1243 |
optr = qtqueryset(qt); |
| 1244 |
tri_id = smTri_in_set(sm,tpt,optr,onptr,whichptr); |
| 1245 |
|
| 1246 |
return(tri_id); |
| 1247 |
} |
| 1248 |
|
| 1249 |
|
| 1250 |
/* |
| 1251 |
Determine whether this sample should: |
| 1252 |
a) be added to the mesh by subdividing the triangle |
| 1253 |
b) ignored |
| 1254 |
c) replace values of an existing mesh vertex |
| 1255 |
|
| 1256 |
In case a, the routine will return TRUE, for b,c will return FALSE |
| 1257 |
In case a, also determine if this sample should cause the deletion of |
| 1258 |
an existing vertex. If so *rptr will contain the id of the sample to delete |
| 1259 |
after the new sample has been added. |
| 1260 |
|
| 1261 |
ASSUMPTION: this will not be called with a new sample that is |
| 1262 |
a BASE point. |
| 1263 |
|
| 1264 |
The following tests are performed (in order) to determine the fate |
| 1265 |
of the sample: |
| 1266 |
|
| 1267 |
1) If the new sample is close in ws, and close in the spherical projection |
| 1268 |
to one of the triangle vertex samples: |
| 1269 |
pick the point with dir closest to that of the canonical view |
| 1270 |
If it is the new point: mark existing point for deletion,and return |
| 1271 |
TRUE,else return FALSE |
| 1272 |
2) If the spherical projection of new is < REPLACE_EPS from a base point: |
| 1273 |
add new and mark the base for deletion: return TRUE |
| 1274 |
3) If the addition of the new sample point would introduce a "puncture" |
| 1275 |
or cause new triangles with large depth differences:return FALSE |
| 1276 |
This attempts to throw out points that should be occluded |
| 1277 |
*/ |
| 1278 |
int |
| 1279 |
smTest_sample(sm,tri_id,dir,p,rptr) |
| 1280 |
SM *sm; |
| 1281 |
int tri_id; |
| 1282 |
FVECT dir,p; |
| 1283 |
int *rptr; |
| 1284 |
{ |
| 1285 |
TRI *tri; |
| 1286 |
double d,d2,dnear,dspt,d01,d12,d20,s0,s1,s2,ds,dv; |
| 1287 |
int vid[3],i,nearid,norm,dcnt,bcnt; |
| 1288 |
FVECT diff[3],spt,npt; |
| 1289 |
|
| 1290 |
*rptr = INVALID; |
| 1291 |
bcnt = dcnt = 0; |
| 1292 |
tri = SM_NTH_TRI(sm,tri_id); |
| 1293 |
vid[0] = T_NTH_V(tri,0); |
| 1294 |
vid[1] = T_NTH_V(tri,1); |
| 1295 |
vid[2] = T_NTH_V(tri,2); |
| 1296 |
|
| 1297 |
for(i=0; i<3; i++) |
| 1298 |
{ |
| 1299 |
if(SM_BASE_ID(sm,vid[i])) |
| 1300 |
bcnt++; |
| 1301 |
if(SM_DIR_ID(sm,vid[i])) |
| 1302 |
dcnt++; |
| 1303 |
|
| 1304 |
} |
| 1305 |
/* TEST 1: If the new sample is close in ws, and close in the spherical |
| 1306 |
projection to one of the triangle vertex samples |
| 1307 |
*/ |
| 1308 |
#if 0 |
| 1309 |
norm = FALSE; |
| 1310 |
VSUB(spt,p,SM_VIEW_CENTER(sm)); |
| 1311 |
ds = DOT(spt,spt); |
| 1312 |
dnear = FHUGE; |
| 1313 |
for(i=0; i<3; i++) |
| 1314 |
{ |
| 1315 |
d = DOT(diff[i],diff[i])/ds; |
| 1316 |
if(d < dnear) |
| 1317 |
{ |
| 1318 |
dnear = d; |
| 1319 |
nearid=vid[i]; |
| 1320 |
} |
| 1321 |
} |
| 1322 |
|
| 1323 |
if(dnear <= SM_MIN_SAMP_DIFF*SM_MIN_SAMP_DIFF) |
| 1324 |
{ |
| 1325 |
/* Pick the point with dir closest to that of the canonical view |
| 1326 |
if it is the new sample: mark existing point for deletion |
| 1327 |
*/ |
| 1328 |
if(SM_BASE_ID(sm,nearid)) |
| 1329 |
{ |
| 1330 |
*rptr = nearid; |
| 1331 |
return(TRUE); |
| 1332 |
} |
| 1333 |
if(SM_DIR_ID(sm,nearid)) |
| 1334 |
return(FALSE); |
| 1335 |
if(!dir) |
| 1336 |
{ |
| 1337 |
*rptr = nearid; |
| 1338 |
return(TRUE); |
| 1339 |
} |
| 1340 |
normalize(spt); |
| 1341 |
norm = TRUE; |
| 1342 |
VSUB(npt,SM_NTH_WV(sm,nearid),SM_VIEW_CENTER(sm)); |
| 1343 |
normalize(npt); |
| 1344 |
d = fdir2diff(SM_NTH_W_DIR(sm,nearid), npt); |
| 1345 |
d2 = 2. - 2.*DOT(dir,spt); |
| 1346 |
/* The existing sample is a better sample:punt */ |
| 1347 |
if(d2 > d) |
| 1348 |
return(FALSE); |
| 1349 |
else |
| 1350 |
{ |
| 1351 |
/* The new sample is better: mark the existing one |
| 1352 |
for deletion after the new one is added*/ |
| 1353 |
*rptr = nearid; |
| 1354 |
return(TRUE); |
| 1355 |
} |
| 1356 |
} |
| 1357 |
|
| 1358 |
/* TEST 3: If the spherical projection of new is < S_REPLACE_EPS |
| 1359 |
from a base point: Edge length is constrained to subtend <45 degrees: |
| 1360 |
original base mesh edges are approx 32 degrees- so have about 13 degrees |
| 1361 |
to work in: S_REPLACE_EPS is the square of the radian value |
| 1362 |
*/ |
| 1363 |
|
| 1364 |
if(bcnt) |
| 1365 |
{ |
| 1366 |
dnear = FHUGE; |
| 1367 |
if(!norm) |
| 1368 |
normalize(spt); |
| 1369 |
|
| 1370 |
for(i=0; i<3; i++) |
| 1371 |
{ |
| 1372 |
if(!SM_BASE_ID(sm,vid[i])) |
| 1373 |
continue; |
| 1374 |
VSUB(npt,SM_NTH_WV(sm,vid[i]),SM_VIEW_CENTER(sm)); |
| 1375 |
d = DIST_SQ(npt,spt); |
| 1376 |
if(dnear <= SM_MIN_SAMP_DIFF*SM_MIN_SAMP_DIFF && d< near) |
| 1377 |
{ |
| 1378 |
dnear = d; |
| 1379 |
nearid = vid[i]; |
| 1380 |
} |
| 1381 |
} |
| 1382 |
if(dnear != FHUGE) |
| 1383 |
{ |
| 1384 |
/* add new and mark the base for deletion */ |
| 1385 |
*rptr = nearid; |
| 1386 |
return(TRUE); |
| 1387 |
} |
| 1388 |
} |
| 1389 |
#else |
| 1390 |
{ |
| 1391 |
FVECT nearpt; |
| 1392 |
dnear = FHUGE; |
| 1393 |
VSUB(spt,p,SM_VIEW_CENTER(sm)); |
| 1394 |
ds = DOT(spt,spt); |
| 1395 |
normalize(spt); |
| 1396 |
|
| 1397 |
for(i=0; i<3; i++) |
| 1398 |
{ |
| 1399 |
|
| 1400 |
VSUB(npt,SM_NTH_WV(sm,vid[i]),SM_VIEW_CENTER(sm)); |
| 1401 |
|
| 1402 |
if(!SM_BASE_ID(sm,vid[i]) || !SM_DIR_ID(sm,vid[i])) |
| 1403 |
normalize(npt); |
| 1404 |
|
| 1405 |
d = DIST_SQ(npt,spt); |
| 1406 |
if(d < SM_MIN_SAMP_DIFF*SM_MIN_SAMP_DIFF && d < dnear) |
| 1407 |
{ |
| 1408 |
dnear = d; |
| 1409 |
nearid = vid[i]; |
| 1410 |
VCOPY(nearpt,npt); |
| 1411 |
} |
| 1412 |
|
| 1413 |
} |
| 1414 |
if(dnear != FHUGE) |
| 1415 |
{ |
| 1416 |
/* Pick the point with dir closest to that of the canonical view |
| 1417 |
if it is the new sample: mark existing point for deletion |
| 1418 |
*/ |
| 1419 |
if(SM_BASE_ID(sm,nearid)) |
| 1420 |
{ |
| 1421 |
*rptr = nearid; |
| 1422 |
return(TRUE); |
| 1423 |
} |
| 1424 |
if(SM_DIR_ID(sm,nearid)) |
| 1425 |
return(FALSE); |
| 1426 |
if(!dir) |
| 1427 |
{ |
| 1428 |
*rptr = nearid; |
| 1429 |
return(TRUE); |
| 1430 |
} |
| 1431 |
d = fdir2diff(SM_NTH_W_DIR(sm,nearid), nearpt); |
| 1432 |
d2 = 2. - 2.*DOT(dir,spt); |
| 1433 |
/* The existing sample is a better sample:punt */ |
| 1434 |
if(d2 > d) |
| 1435 |
return(FALSE); |
| 1436 |
else |
| 1437 |
{ |
| 1438 |
/* The new sample is better: mark the existing one |
| 1439 |
for deletion after the new one is added*/ |
| 1440 |
*rptr = nearid; |
| 1441 |
return(TRUE); |
| 1442 |
} |
| 1443 |
} |
| 1444 |
} |
| 1445 |
#endif |
| 1446 |
/* TEST 4: |
| 1447 |
If the addition of the new sample point would introduce a "puncture" |
| 1448 |
or cause new triangles with large depth differences:dont add: |
| 1449 |
*/ |
| 1450 |
if(bcnt || dcnt) |
| 1451 |
return(TRUE); |
| 1452 |
|
| 1453 |
/* If the new point is in front of the existing points- add */ |
| 1454 |
dv = DIST_SQ(SM_NTH_WV(sm,vid[0]),SM_VIEW_CENTER(sm)); |
| 1455 |
if(ds < dv) |
| 1456 |
return(TRUE); |
| 1457 |
|
| 1458 |
d01 = DIST_SQ(SM_NTH_WV(sm,vid[1]),SM_NTH_WV(sm,vid[0])); |
| 1459 |
VSUB(diff[0],SM_NTH_WV(sm,vid[0]),p); |
| 1460 |
s0 = DOT(diff[0],diff[0]); |
| 1461 |
if(s0 < S_REPLACE_SCALE*d01) |
| 1462 |
return(TRUE); |
| 1463 |
|
| 1464 |
d12 = DIST_SQ(SM_NTH_WV(sm,vid[2]),SM_NTH_WV(sm,vid[1])); |
| 1465 |
if(s0 < S_REPLACE_SCALE*d12) |
| 1466 |
return(TRUE); |
| 1467 |
d20 = DIST_SQ(SM_NTH_WV(sm,vid[0]),SM_NTH_WV(sm,vid[2])); |
| 1468 |
if(s0 < S_REPLACE_SCALE*d20) |
| 1469 |
return(TRUE); |
| 1470 |
d = MIN3(d01,d12,d20); |
| 1471 |
VSUB(diff[1],SM_NTH_WV(sm,vid[1]),p); |
| 1472 |
s1 = DOT(diff[1],diff[1]); |
| 1473 |
if(s1 < S_REPLACE_SCALE*d) |
| 1474 |
return(TRUE); |
| 1475 |
VSUB(diff[2],SM_NTH_WV(sm,vid[2]),p); |
| 1476 |
s2 = DOT(diff[2],diff[2]); |
| 1477 |
if(s2 < S_REPLACE_SCALE*d) |
| 1478 |
return(TRUE); |
| 1479 |
|
| 1480 |
/* TEST 5: |
| 1481 |
Check to see if triangle is relatively large and should therefore |
| 1482 |
be subdivided anyway. |
| 1483 |
*/ |
| 1484 |
dv *= DIST_SQ(SM_NTH_WV(sm,vid[1]),SM_VIEW_CENTER(sm)); |
| 1485 |
dv *= DIST_SQ(SM_NTH_WV(sm,vid[2]),SM_VIEW_CENTER(sm)); |
| 1486 |
if (d01*d12*d20/dv > S_REPLACE_TRI) |
| 1487 |
return(TRUE); |
| 1488 |
|
| 1489 |
return(FALSE); |
| 1490 |
} |
| 1491 |
|
| 1492 |
|
| 1493 |
int |
| 1494 |
smReplace_samp(sm,c,dir,p,s_id,t_id,o_id,on,which) |
| 1495 |
SM *sm; |
| 1496 |
COLR c; |
| 1497 |
FVECT dir,p; |
| 1498 |
int s_id,t_id,o_id,on,which; |
| 1499 |
{ |
| 1500 |
int tonemap,v_id,tri_id; |
| 1501 |
TRI *t,*tri; |
| 1502 |
|
| 1503 |
tri = SM_NTH_TRI(sm,t_id); |
| 1504 |
v_id = T_NTH_V(tri,which); |
| 1505 |
|
| 1506 |
/* If it is a base id, need new sample */ |
| 1507 |
if(SM_BASE_ID(sm,v_id)) |
| 1508 |
{ |
| 1509 |
tonemap = (SM_TONE_MAP(sm) > s_id); |
| 1510 |
sInit_samp(SM_SAMP(sm),s_id,c,dir,p,o_id,tonemap); |
| 1511 |
SM_NTH_VERT(sm,s_id) = t_id; |
| 1512 |
T_NTH_V(tri,which) = s_id; |
| 1513 |
if(!(SM_BASE_ID(sm,T_NTH_V(tri,(which+1)%3)) || |
| 1514 |
SM_BASE_ID(sm,T_NTH_V(tri,(which+2)%3)))) |
| 1515 |
{ |
| 1516 |
SM_CLR_NTH_T_BASE(sm,t_id); |
| 1517 |
|
| 1518 |
} |
| 1519 |
add_new_tri(t_id); |
| 1520 |
t_id = smTri_next_ccw_nbr(sm,tri,v_id); |
| 1521 |
while(t_id != INVALID) |
| 1522 |
{ |
| 1523 |
t = SM_NTH_TRI(sm,t_id); |
| 1524 |
which = T_WHICH_V(t,v_id); |
| 1525 |
T_NTH_V(t,which) = s_id; |
| 1526 |
/* Check if still a base triangle */ |
| 1527 |
if(!(SM_BASE_ID(sm,T_NTH_V(t,(which+1)%3)) || |
| 1528 |
SM_BASE_ID(sm,T_NTH_V(t,(which+2)%3)))) |
| 1529 |
{ |
| 1530 |
SM_CLR_NTH_T_BASE(sm,t_id); |
| 1531 |
} |
| 1532 |
add_new_tri(t_id); |
| 1533 |
t_id = smTri_next_ccw_nbr(sm,t,v_id); |
| 1534 |
} |
| 1535 |
return(s_id); |
| 1536 |
} |
| 1537 |
if(dir) |
| 1538 |
{ |
| 1539 |
/* If world point */ |
| 1540 |
/* if existing point is a dir: leave */ |
| 1541 |
if(SM_DIR_ID(sm,v_id)) |
| 1542 |
return(INVALID); |
| 1543 |
if(on == ON_V) |
| 1544 |
{ |
| 1545 |
tonemap = (SM_TONE_MAP(sm) > v_id); |
| 1546 |
sInit_samp(SM_SAMP(sm),v_id,c,dir,p,o_id,tonemap); |
| 1547 |
add_new_tri(t_id); |
| 1548 |
tri_id = smTri_next_ccw_nbr(sm,tri,v_id); |
| 1549 |
while(tri_id != t_id) |
| 1550 |
{ |
| 1551 |
t = SM_NTH_TRI(sm,tri_id); |
| 1552 |
add_new_tri(tri_id); |
| 1553 |
tri_id = smTri_next_ccw_nbr(sm,t,v_id); |
| 1554 |
} |
| 1555 |
return(v_id); |
| 1556 |
} |
| 1557 |
/* on == ON_P */ |
| 1558 |
else |
| 1559 |
{ |
| 1560 |
FVECT spt,npt; |
| 1561 |
double d,d2; |
| 1562 |
|
| 1563 |
/* Need to check which sample is preferable */ |
| 1564 |
VSUB(spt,p,SM_VIEW_CENTER(sm)); |
| 1565 |
normalize(spt); |
| 1566 |
|
| 1567 |
VSUB(npt,SM_NTH_WV(sm,v_id),SM_VIEW_CENTER(sm)); |
| 1568 |
normalize(npt); |
| 1569 |
d = fdir2diff(SM_NTH_W_DIR(sm,v_id), npt); |
| 1570 |
d2 = 2. - 2.*DOT(dir,spt); |
| 1571 |
/* The existing sample is a better sample:punt */ |
| 1572 |
if(d2 < d) |
| 1573 |
{ |
| 1574 |
/* The new sample has better information- replace values */ |
| 1575 |
tonemap = (SM_TONE_MAP(sm) > v_id); |
| 1576 |
sInit_samp(SM_SAMP(sm),v_id,c,dir,p,o_id,tonemap); |
| 1577 |
add_new_tri(t_id); |
| 1578 |
tri_id = smTri_next_ccw_nbr(sm,tri,v_id); |
| 1579 |
while(tri_id != t_id) |
| 1580 |
{ |
| 1581 |
t = SM_NTH_TRI(sm,tri_id); |
| 1582 |
add_new_tri(tri_id); |
| 1583 |
tri_id = smTri_next_ccw_nbr(sm,t,v_id); |
| 1584 |
} |
| 1585 |
} |
| 1586 |
return(v_id); |
| 1587 |
} |
| 1588 |
} |
| 1589 |
else |
| 1590 |
{ /* New point is a dir */ |
| 1591 |
return(INVALID); |
| 1592 |
} |
| 1593 |
} |
| 1594 |
|
| 1595 |
int |
| 1596 |
smAlloc_samp(sm) |
| 1597 |
SM *sm; |
| 1598 |
{ |
| 1599 |
int s_id,replaced,cnt; |
| 1600 |
SAMP *s; |
| 1601 |
FVECT p; |
| 1602 |
|
| 1603 |
s = SM_SAMP(sm); |
| 1604 |
s_id = sAlloc_samp(s,&replaced); |
| 1605 |
|
| 1606 |
cnt=0; |
| 1607 |
while(replaced) |
| 1608 |
{ |
| 1609 |
if(smRemoveVertex(sm,s_id)) |
| 1610 |
break; |
| 1611 |
s_id = sAlloc_samp(s,&replaced); |
| 1612 |
cnt++; |
| 1613 |
if(cnt > S_MAX_SAMP(s)) |
| 1614 |
error(CONSISTENCY,"smAlloc_samp():unable to find free samp\n"); |
| 1615 |
} |
| 1616 |
return(s_id); |
| 1617 |
} |
| 1618 |
|
| 1619 |
|
| 1620 |
/* Add sample to the mesh: |
| 1621 |
|
| 1622 |
the sample can be a world space or directional point. If o_id !=INVALID, |
| 1623 |
then we have an existing sample containing the appropriate information |
| 1624 |
already converted into storage format. |
| 1625 |
The spherical projection of the point/ray can: |
| 1626 |
a) coincide with existing vertex |
| 1627 |
i) conincides with existing sample |
| 1628 |
ii) projects same as existing sample |
| 1629 |
iii) hits a base vertex |
| 1630 |
b) coincide with existing edge |
| 1631 |
c) Fall in existing triangle |
| 1632 |
*/ |
| 1633 |
int |
| 1634 |
smAdd_samp(sm,c,dir,p,o_id) |
| 1635 |
SM *sm; |
| 1636 |
COLR c; |
| 1637 |
FVECT dir,p; |
| 1638 |
int o_id; |
| 1639 |
{ |
| 1640 |
int t_id,s_id,r_id,on,which,n_id; |
| 1641 |
double d; |
| 1642 |
FVECT wpt; |
| 1643 |
|
| 1644 |
r_id = INVALID; |
| 1645 |
|
| 1646 |
/* Must do this first-as may change mesh */ |
| 1647 |
s_id = smAlloc_samp(sm); |
| 1648 |
if(s_id== 2649) |
| 1649 |
r_id = INVALID; |
| 1650 |
/* If sample is a world space point */ |
| 1651 |
if(p) |
| 1652 |
{ |
| 1653 |
while(1) |
| 1654 |
{ |
| 1655 |
t_id = smPointLocateTri(sm,p,&on,&which); |
| 1656 |
if(t_id == INVALID) |
| 1657 |
{ |
| 1658 |
#ifdef DEBUG |
| 1659 |
eputs("smAddSamp(): unable to locate tri containing sample \n"); |
| 1660 |
#endif |
| 1661 |
smUnalloc_samp(sm,s_id); |
| 1662 |
return(INVALID); |
| 1663 |
} |
| 1664 |
/* If spherical projection coincides with existing sample: replace */ |
| 1665 |
if((on == ON_V || on == ON_P)) |
| 1666 |
{ |
| 1667 |
if((n_id = smReplace_samp(sm,c,dir,p,s_id,t_id,o_id,on,which))!= s_id) |
| 1668 |
smUnalloc_samp(sm,s_id); |
| 1669 |
return(n_id); |
| 1670 |
} |
| 1671 |
if((!(smTest_sample(sm,t_id,dir,p,&r_id)))) |
| 1672 |
{ |
| 1673 |
smUnalloc_samp(sm,s_id); |
| 1674 |
return(INVALID); |
| 1675 |
} |
| 1676 |
if(r_id != INVALID) |
| 1677 |
{ |
| 1678 |
smRemoveVertex(sm,r_id); |
| 1679 |
sDelete_samp(SM_SAMP(sm),r_id); |
| 1680 |
} |
| 1681 |
else |
| 1682 |
break; |
| 1683 |
} |
| 1684 |
/* If sample is being added in the middle of the sample array: tone |
| 1685 |
map individually |
| 1686 |
*/ |
| 1687 |
/* Initialize sample */ |
| 1688 |
sInit_samp(SM_SAMP(sm),s_id,c,dir,p,o_id,(SM_TONE_MAP(sm)>s_id)); |
| 1689 |
|
| 1690 |
} |
| 1691 |
/* If sample is a direction vector */ |
| 1692 |
else |
| 1693 |
{ |
| 1694 |
VADD(wpt,dir,SM_VIEW_CENTER(sm)); |
| 1695 |
while(1) |
| 1696 |
{ if(s_id == 2299) |
| 1697 |
t_id = INVALID; |
| 1698 |
t_id = smPointLocateTri(sm,wpt,&on,&which); |
| 1699 |
if(t_id == INVALID) |
| 1700 |
{ |
| 1701 |
#ifdef DEBUG |
| 1702 |
eputs("smAddSamp(): unable to locate tri containing sample \n"); |
| 1703 |
#endif |
| 1704 |
smUnalloc_samp(sm,s_id); |
| 1705 |
return(INVALID); |
| 1706 |
} |
| 1707 |
if(on == ON_V || on == ON_P) |
| 1708 |
{ |
| 1709 |
if((n_id=smReplace_samp(sm,c,NULL,wpt,s_id,t_id,o_id,on,which))!=s_id) |
| 1710 |
smUnalloc_samp(sm,s_id); |
| 1711 |
return(n_id); |
| 1712 |
} |
| 1713 |
if((!(smTest_sample(sm,t_id,NULL,wpt,&r_id)))) |
| 1714 |
{ |
| 1715 |
smUnalloc_samp(sm,s_id); |
| 1716 |
return(INVALID); |
| 1717 |
} |
| 1718 |
|
| 1719 |
if(r_id != INVALID) |
| 1720 |
{ |
| 1721 |
smRemoveVertex(sm,r_id); |
| 1722 |
sDelete_samp(SM_SAMP(sm),r_id); |
| 1723 |
} |
| 1724 |
else |
| 1725 |
break; |
| 1726 |
} |
| 1727 |
/* Allocate space for a sample and initialize */ |
| 1728 |
sInit_samp(SM_SAMP(sm),s_id,c,NULL,wpt,o_id,(SM_TONE_MAP(sm)>s_id)); |
| 1729 |
} |
| 1730 |
if(!SM_DIR_ID(sm,s_id)) |
| 1731 |
{ |
| 1732 |
/* If not a base or sky point, add distance from the |
| 1733 |
viewcenter to average*/ |
| 1734 |
d = DIST(SM_NTH_WV(sm,s_id),SM_VIEW_CENTER(sm)); |
| 1735 |
smDist_sum += 1.0/d; |
| 1736 |
} |
| 1737 |
smInsert_samp(sm,s_id,t_id,on,which); |
| 1738 |
|
| 1739 |
return(s_id); |
| 1740 |
} |
| 1741 |
|
| 1742 |
/* |
| 1743 |
* int |
| 1744 |
* smNewSamp(c, dir, p) : register new sample point and return index |
| 1745 |
* COLR c; : pixel color (RGBE) |
| 1746 |
* FVECT dir; : ray direction vector |
| 1747 |
* FVECT p; : world intersection point |
| 1748 |
* |
| 1749 |
* Add new sample point to data structures, removing old values as necessary. |
| 1750 |
* New sample representation will be output in next call to smUpdate(). |
| 1751 |
* If the point is a sky point: then v=NULL |
| 1752 |
*/ |
| 1753 |
int |
| 1754 |
smNewSamp(c,dir,p) |
| 1755 |
COLR c; |
| 1756 |
FVECT dir; |
| 1757 |
FVECT p; |
| 1758 |
{ |
| 1759 |
int s_id; |
| 1760 |
|
| 1761 |
/* First check if this the first sample: if so initialize mesh */ |
| 1762 |
if(SM_NUM_SAMP(smMesh) == 0) |
| 1763 |
{ |
| 1764 |
smInit_sm(smMesh,odev.v.vp); |
| 1765 |
sClear_all_flags(SM_SAMP(smMesh)); |
| 1766 |
} |
| 1767 |
/* Add the sample to the mesh */ |
| 1768 |
s_id = smAdd_samp(smMesh,c,dir,p,INVALID); |
| 1769 |
|
| 1770 |
return(s_id); |
| 1771 |
|
| 1772 |
} |
| 1773 |
int |
| 1774 |
smAdd_base_vertex(sm,v) |
| 1775 |
SM *sm; |
| 1776 |
FVECT v; |
| 1777 |
{ |
| 1778 |
int id; |
| 1779 |
|
| 1780 |
/* First add coordinate to the sample array */ |
| 1781 |
id = sAdd_base_point(SM_SAMP(sm),v); |
| 1782 |
if(id == INVALID) |
| 1783 |
return(INVALID); |
| 1784 |
/* Initialize triangle pointer to -1 */ |
| 1785 |
smClear_vert(sm,id); |
| 1786 |
return(id); |
| 1787 |
} |
| 1788 |
|
| 1789 |
|
| 1790 |
|
| 1791 |
/* Initialize a the point location DAG based on a 6 triangle tesselation |
| 1792 |
of the unit sphere centered on the view center. The DAG structure |
| 1793 |
contains 6 roots: one for each initial base triangle |
| 1794 |
*/ |
| 1795 |
|
| 1796 |
int |
| 1797 |
smCreate_base_mesh(sm,type) |
| 1798 |
SM *sm; |
| 1799 |
int type; |
| 1800 |
{ |
| 1801 |
int i,s_id,tri_id,nbr_id; |
| 1802 |
int p[SM_EXTRA_POINTS],ids[SM_BASE_TRIS]; |
| 1803 |
int v0_id,v1_id,v2_id; |
| 1804 |
FVECT d,pt,cntr,v0,v1,v2; |
| 1805 |
TRI *t; |
| 1806 |
|
| 1807 |
/* First insert the base vertices into the sample point array */ |
| 1808 |
|
| 1809 |
for(i=0; i < SM_EXTRA_POINTS; i++) |
| 1810 |
{ |
| 1811 |
VADD(cntr,icosa_verts[i],SM_VIEW_CENTER(sm)); |
| 1812 |
p[i] = smAdd_base_vertex(sm,cntr); |
| 1813 |
} |
| 1814 |
/* Create the base triangles */ |
| 1815 |
for(i=0;i < SM_BASE_TRIS; i++) |
| 1816 |
{ |
| 1817 |
v0_id = p[icosa_tris[i][0]]; |
| 1818 |
v1_id = p[icosa_tris[i][1]]; |
| 1819 |
v2_id = p[icosa_tris[i][2]]; |
| 1820 |
ids[i] = smAdd_tri(sm, v0_id,v1_id,v2_id); |
| 1821 |
/* Set neighbors */ |
| 1822 |
for(nbr_id=0; nbr_id < 3; nbr_id++) |
| 1823 |
T_NTH_NBR(SM_NTH_TRI(sm,ids[i]),nbr_id) = icosa_nbrs[i][nbr_id]; |
| 1824 |
|
| 1825 |
} |
| 1826 |
for(i=0;i < SM_BASE_TRIS; i++) |
| 1827 |
{ |
| 1828 |
t = SM_NTH_TRI(sm,ids[i]); |
| 1829 |
smLocator_add_tri(sm,ids[i],T_NTH_V(t,0),T_NTH_V(t,1),T_NTH_V(t,2)); |
| 1830 |
} |
| 1831 |
return(1); |
| 1832 |
|
| 1833 |
} |
| 1834 |
|
| 1835 |
|
| 1836 |
int |
| 1837 |
smNext_tri_flag_set(sm,i,which,b) |
| 1838 |
SM *sm; |
| 1839 |
int i,which; |
| 1840 |
int b; |
| 1841 |
{ |
| 1842 |
|
| 1843 |
for(; i < SM_NUM_TRI(sm);i++) |
| 1844 |
{ |
| 1845 |
|
| 1846 |
if(!T_IS_VALID(SM_NTH_TRI(sm,i))) |
| 1847 |
continue; |
| 1848 |
if(!SM_IS_NTH_T_FLAG(sm,i,which)) |
| 1849 |
continue; |
| 1850 |
if(!b) |
| 1851 |
break; |
| 1852 |
if((b==1) && !SM_BG_TRI(sm,i)) |
| 1853 |
break; |
| 1854 |
if((b==2) && SM_BG_TRI(sm,i)) |
| 1855 |
break; |
| 1856 |
} |
| 1857 |
|
| 1858 |
return(i); |
| 1859 |
} |
| 1860 |
|
| 1861 |
|
| 1862 |
int |
| 1863 |
smNext_valid_tri(sm,i) |
| 1864 |
SM *sm; |
| 1865 |
int i; |
| 1866 |
{ |
| 1867 |
|
| 1868 |
while( i < SM_NUM_TRI(sm) && !T_IS_VALID(SM_NTH_TRI(sm,i))) |
| 1869 |
i++; |
| 1870 |
|
| 1871 |
return(i); |
| 1872 |
} |
| 1873 |
|
| 1874 |
|
| 1875 |
|
| 1876 |
qtTri_from_id(t_id,v0,v1,v2) |
| 1877 |
int t_id; |
| 1878 |
FVECT v0,v1,v2; |
| 1879 |
{ |
| 1880 |
TRI *t; |
| 1881 |
|
| 1882 |
t = SM_NTH_TRI(smMesh,t_id); |
| 1883 |
if(!T_IS_VALID(t)) |
| 1884 |
return(0); |
| 1885 |
VSUB(v0,SM_T_NTH_WV(smMesh,t,0),SM_VIEW_CENTER(smMesh)); |
| 1886 |
VSUB(v1,SM_T_NTH_WV(smMesh,t,1),SM_VIEW_CENTER(smMesh)); |
| 1887 |
VSUB(v2,SM_T_NTH_WV(smMesh,t,2),SM_VIEW_CENTER(smMesh)); |
| 1888 |
return(1); |
| 1889 |
} |
| 1890 |
|
| 1891 |
|
| 1892 |
smRebuild_mesh(sm,v) |
| 1893 |
SM *sm; |
| 1894 |
VIEW *v; |
| 1895 |
{ |
| 1896 |
int i,j,cnt; |
| 1897 |
FVECT p,ov,dir; |
| 1898 |
double d; |
| 1899 |
|
| 1900 |
#ifdef DEBUG |
| 1901 |
fprintf(stderr,"smRebuild_mesh(): rebuilding...."); |
| 1902 |
#endif |
| 1903 |
/* Clear the mesh- and rebuild using the current sample array */ |
| 1904 |
/* Remember the current number of samples */ |
| 1905 |
cnt = SM_NUM_SAMP(sm); |
| 1906 |
/* Calculate the difference between the current and new viewpoint*/ |
| 1907 |
/* Will need to subtract this off of sky points */ |
| 1908 |
VCOPY(ov,SM_VIEW_CENTER(sm)); |
| 1909 |
/* Initialize the mesh to 0 samples and the base triangles */ |
| 1910 |
|
| 1911 |
/* Go through all samples and add in if in the new view frustum, and |
| 1912 |
the dir is <= 30 degrees from new view |
| 1913 |
*/ |
| 1914 |
smInit_sm(sm,v->vp); |
| 1915 |
for(i=0; i < cnt; i++) |
| 1916 |
{ |
| 1917 |
/* First check if sample visible(conservative approx: if one of tris |
| 1918 |
attached to sample is in frustum) */ |
| 1919 |
if(!S_IS_FLAG(i)) |
| 1920 |
continue; |
| 1921 |
|
| 1922 |
/* Next test if direction > 30 from current direction */ |
| 1923 |
if(SM_NTH_W_DIR(sm,i)!=-1) |
| 1924 |
{ |
| 1925 |
VSUB(p,SM_NTH_WV(sm,i),v->vp); |
| 1926 |
normalize(p); |
| 1927 |
decodedir(dir,SM_NTH_W_DIR(sm,i)); |
| 1928 |
d = 2. - 2.*DOT(dir,p); |
| 1929 |
if (d > MAXDIFF2) |
| 1930 |
continue; |
| 1931 |
VCOPY(p,SM_NTH_WV(sm,i)); |
| 1932 |
smAdd_samp(sm,NULL,dir,p,i); |
| 1933 |
} |
| 1934 |
else |
| 1935 |
{ |
| 1936 |
VSUB(dir,SM_NTH_WV(sm,i),ov); |
| 1937 |
VADD(SM_NTH_WV(sm,i),dir,SM_VIEW_CENTER(sm)); |
| 1938 |
smAdd_samp(sm,NULL,dir,NULL,i); |
| 1939 |
} |
| 1940 |
|
| 1941 |
} |
| 1942 |
#if 0 |
| 1943 |
smNew_tri_cnt = SM_SAMPLE_TRIS(sm); |
| 1944 |
#endif |
| 1945 |
|
| 1946 |
#ifdef DEBUG |
| 1947 |
fprintf(stderr,"smRebuild_mesh():done\n"); |
| 1948 |
#endif |
| 1949 |
} |
| 1950 |
|
| 1951 |
int |
| 1952 |
intersect_tri_set(t_set,orig,dir,pt) |
| 1953 |
OBJECT *t_set; |
| 1954 |
FVECT orig,dir,pt; |
| 1955 |
{ |
| 1956 |
OBJECT *optr; |
| 1957 |
int i,t_id,id,base; |
| 1958 |
int pid0,pid1,pid2; |
| 1959 |
FVECT p0,p1,p2,p; |
| 1960 |
TRI *t; |
| 1961 |
double d,d1; |
| 1962 |
|
| 1963 |
optr = QT_SET_PTR(t_set); |
| 1964 |
for(i = QT_SET_CNT(t_set); i > 0; i--) |
| 1965 |
{ |
| 1966 |
t_id = QT_SET_NEXT_ELEM(optr); |
| 1967 |
t = SM_NTH_TRI(smMesh,t_id); |
| 1968 |
if(!T_IS_VALID(t)) |
| 1969 |
continue; |
| 1970 |
pid0 = T_NTH_V(t,0); |
| 1971 |
pid1 = T_NTH_V(t,1); |
| 1972 |
pid2 = T_NTH_V(t,2); |
| 1973 |
if(base = SM_IS_NTH_T_BASE(smMesh,t_id)) |
| 1974 |
if(SM_BASE_ID(smMesh,pid0) && SM_BASE_ID(smMesh,pid1) && |
| 1975 |
SM_BASE_ID(smMesh,pid2)) |
| 1976 |
continue; |
| 1977 |
VCOPY(p0,SM_NTH_WV(smMesh,pid0)); |
| 1978 |
VCOPY(p1,SM_NTH_WV(smMesh,pid1)); |
| 1979 |
VCOPY(p2,SM_NTH_WV(smMesh,pid2)); |
| 1980 |
if(ray_intersect_tri(orig,dir,p0,p1,p2,p)) |
| 1981 |
{ |
| 1982 |
if(!base) |
| 1983 |
{ |
| 1984 |
d = DIST_SQ(p,p0); |
| 1985 |
d1 = DIST_SQ(p,p1); |
| 1986 |
if(d < d1) |
| 1987 |
{ |
| 1988 |
d1 = DIST_SQ(p,p2); |
| 1989 |
id = (d1 < d)?pid2:pid0; |
| 1990 |
} |
| 1991 |
else |
| 1992 |
{ |
| 1993 |
d = DIST_SQ(p,p2); |
| 1994 |
id = (d < d1)? pid2:pid1; |
| 1995 |
} |
| 1996 |
} |
| 1997 |
else |
| 1998 |
{ |
| 1999 |
if(SM_BASE_ID(smMesh,pid0)) |
| 2000 |
{ |
| 2001 |
if(SM_BASE_ID(smMesh,pid1)) |
| 2002 |
id = pid2; |
| 2003 |
else |
| 2004 |
if(SM_BASE_ID(smMesh,pid2)) |
| 2005 |
id = pid1; |
| 2006 |
else |
| 2007 |
{ |
| 2008 |
d = DIST_SQ(p,p1); |
| 2009 |
d1 = DIST_SQ(p,p2); |
| 2010 |
if(d < d1) |
| 2011 |
id = pid1; |
| 2012 |
else |
| 2013 |
id = pid2; |
| 2014 |
} |
| 2015 |
} |
| 2016 |
else |
| 2017 |
{ |
| 2018 |
if(SM_BASE_ID(smMesh,pid1)) |
| 2019 |
{ |
| 2020 |
if(SM_BASE_ID(smMesh,pid2)) |
| 2021 |
id = pid0; |
| 2022 |
else |
| 2023 |
{ |
| 2024 |
d = DIST_SQ(p,p0); |
| 2025 |
d1 = DIST_SQ(p,p2); |
| 2026 |
if(d < d1) |
| 2027 |
id = pid0; |
| 2028 |
else |
| 2029 |
id = pid2; |
| 2030 |
} |
| 2031 |
} |
| 2032 |
else |
| 2033 |
{ |
| 2034 |
d = DIST_SQ(p,p0); |
| 2035 |
d1 = DIST_SQ(p,p1); |
| 2036 |
if(d < d1) |
| 2037 |
id = pid0; |
| 2038 |
else |
| 2039 |
id = pid1; |
| 2040 |
} |
| 2041 |
} |
| 2042 |
} |
| 2043 |
if(pt) |
| 2044 |
VCOPY(pt,p); |
| 2045 |
#ifdef TEST_DRIVER |
| 2046 |
Pick_tri = t_id; |
| 2047 |
Pick_samp = id; |
| 2048 |
VCOPY(Pick_point[0],p); |
| 2049 |
#endif |
| 2050 |
return(id); |
| 2051 |
} |
| 2052 |
} |
| 2053 |
return(-1); |
| 2054 |
} |
| 2055 |
|
| 2056 |
/* OS is constrained to be <= QT_MAXCSET : if the set exceeds this, the |
| 2057 |
results of check_set are conservative |
| 2058 |
*/ |
| 2059 |
int |
| 2060 |
compare_ids(id1,id2) |
| 2061 |
OBJECT *id1,*id2; |
| 2062 |
{ |
| 2063 |
int d; |
| 2064 |
|
| 2065 |
d = *id2-*id1; |
| 2066 |
|
| 2067 |
if(d > 0) |
| 2068 |
return(-1); |
| 2069 |
if(d < 0) |
| 2070 |
return(1); |
| 2071 |
|
| 2072 |
return(0); |
| 2073 |
} |
| 2074 |
|
| 2075 |
ray_trace_check_set(qt,argptr,fptr) |
| 2076 |
QUADTREE qt; |
| 2077 |
RT_ARGS *argptr; |
| 2078 |
int *fptr; |
| 2079 |
{ |
| 2080 |
OBJECT tset[QT_MAXSET+1],*tptr; |
| 2081 |
double dt,t; |
| 2082 |
int found; |
| 2083 |
if(QT_IS_EMPTY(qt)) |
| 2084 |
return; |
| 2085 |
if(QT_LEAF_IS_FLAG(qt)) |
| 2086 |
{ |
| 2087 |
QT_FLAG_SET_DONE(*fptr); |
| 2088 |
#if DEBUG |
| 2089 |
eputs("ray_trace_check_set():Already visited this node:aborting\n"); |
| 2090 |
#endif |
| 2091 |
return; |
| 2092 |
} |
| 2093 |
else |
| 2094 |
QT_LEAF_SET_FLAG(qt); |
| 2095 |
|
| 2096 |
tptr = qtqueryset(qt); |
| 2097 |
if(QT_SET_CNT(tptr) > QT_MAXSET) |
| 2098 |
tptr = (OBJECT *)malloc((QT_SET_CNT(tptr)+1)*sizeof(OBJECT)); |
| 2099 |
else |
| 2100 |
tptr = tset; |
| 2101 |
if(!tptr) |
| 2102 |
goto memerr; |
| 2103 |
|
| 2104 |
qtgetset(tptr,qt); |
| 2105 |
/* Must sort */ |
| 2106 |
qsort((void *)(&(tptr[1])),tptr[0],sizeof(OBJECT),compare_ids); |
| 2107 |
/* Check triangles in set against those seen so far(os):only |
| 2108 |
check new triangles for intersection (t_set') |
| 2109 |
*/ |
| 2110 |
check_set_large(tptr,argptr->os); |
| 2111 |
|
| 2112 |
if(!QT_SET_CNT(tptr)) |
| 2113 |
return; |
| 2114 |
found = intersect_tri_set(tptr,argptr->orig,argptr->dir,NULL); |
| 2115 |
if(tptr != tset) |
| 2116 |
free(tptr); |
| 2117 |
if(found != INVALID) |
| 2118 |
{ |
| 2119 |
argptr->t_id = found; |
| 2120 |
QT_FLAG_SET_DONE(*fptr); |
| 2121 |
} |
| 2122 |
return; |
| 2123 |
memerr: |
| 2124 |
error(SYSTEM,"ray_trace_check_set():Unable to allocate memory"); |
| 2125 |
} |
| 2126 |
|
| 2127 |
|
| 2128 |
/* |
| 2129 |
* int |
| 2130 |
* smFindSamp(FVECT orig, FVECT dir) |
| 2131 |
* |
| 2132 |
* Find the closest sample to the given ray. Returns sample id, -1 on failure. |
| 2133 |
* "dir" is assumed to be normalized |
| 2134 |
*/ |
| 2135 |
|
| 2136 |
int |
| 2137 |
smFindSamp(orig,dir) |
| 2138 |
FVECT orig,dir; |
| 2139 |
{ |
| 2140 |
FVECT b,p,o; |
| 2141 |
OBJECT *ts; |
| 2142 |
QUADTREE qt; |
| 2143 |
int s_id,test; |
| 2144 |
double d; |
| 2145 |
|
| 2146 |
/* r is the normalized vector from the view center to the current |
| 2147 |
* ray point ( starting with "orig"). Find the cell that r falls in, |
| 2148 |
* and test the ray against all triangles stored in the cell. If |
| 2149 |
* the test fails, trace the projection of the ray across to the |
| 2150 |
* next cell it intersects: iterate until either an intersection |
| 2151 |
* is found, or the projection ray is // to the direction. The sample |
| 2152 |
* corresponding to the triangle vertex closest to the intersection |
| 2153 |
* point is returned. |
| 2154 |
*/ |
| 2155 |
|
| 2156 |
/* First test if "orig" coincides with the View_center or if "dir" is |
| 2157 |
parallel to r formed by projecting "orig" on the sphere. In |
| 2158 |
either case, do a single test against the cell containing the |
| 2159 |
intersection of "dir" and the sphere |
| 2160 |
*/ |
| 2161 |
/* orig will be updated-so preserve original value */ |
| 2162 |
if(!smMesh) |
| 2163 |
return; |
| 2164 |
#ifdef TEST_DRIVER |
| 2165 |
Picking= TRUE; |
| 2166 |
#endif |
| 2167 |
|
| 2168 |
if(EQUAL_VEC3(orig,SM_VIEW_CENTER(smMesh))) |
| 2169 |
{ |
| 2170 |
qt = smPointLocateCell(smMesh,dir); |
| 2171 |
if(QT_IS_EMPTY(qt)) |
| 2172 |
goto Lerror; |
| 2173 |
ts = qtqueryset(qt); |
| 2174 |
s_id = intersect_tri_set(ts,orig,dir,p); |
| 2175 |
#ifdef DEBUG_TEST_DRIVER |
| 2176 |
VCOPY(Pick_point[0],p); |
| 2177 |
#endif |
| 2178 |
#ifdef DEBUG |
| 2179 |
fprintf(stderr,"Simple pick returning %d\n",s_id); |
| 2180 |
#endif |
| 2181 |
|
| 2182 |
return(s_id); |
| 2183 |
} |
| 2184 |
d = point_on_sphere(b,orig,SM_VIEW_CENTER(smMesh)); |
| 2185 |
if(EQUAL_VEC3(b,dir)) |
| 2186 |
{ |
| 2187 |
qt = smPointLocateCell(smMesh,dir); |
| 2188 |
if(QT_IS_EMPTY(qt)) |
| 2189 |
goto Lerror; |
| 2190 |
ts = qtqueryset(qt); |
| 2191 |
s_id = intersect_tri_set(ts,orig,dir,p); |
| 2192 |
#ifdef DEBUG_TEST_DRIVER |
| 2193 |
VCOPY(Pick_point[0],p); |
| 2194 |
#endif |
| 2195 |
#ifdef DEBUG |
| 2196 |
fprintf(stderr,"Simple pick2 returning %d\n",s_id); |
| 2197 |
#endif |
| 2198 |
return(s_id); |
| 2199 |
} |
| 2200 |
if(OPP_EQUAL_VEC3(b,dir)) |
| 2201 |
{ |
| 2202 |
qt = smPointLocateCell(smMesh,orig); |
| 2203 |
if(QT_IS_EMPTY(qt)) |
| 2204 |
goto Lerror; |
| 2205 |
ts = qtqueryset(qt); |
| 2206 |
s_id = intersect_tri_set(ts,orig,dir,p); |
| 2207 |
#ifdef DEBUG_TEST_DRIVER |
| 2208 |
VCOPY(Pick_point[0],p); |
| 2209 |
#endif |
| 2210 |
if(s_id != INVALID) |
| 2211 |
{ |
| 2212 |
#ifdef DEBUG |
| 2213 |
fprintf(stderr,"Front pick returning %d\n",s_id); |
| 2214 |
#endif |
| 2215 |
return(s_id); |
| 2216 |
} |
| 2217 |
qt = smPointLocateCell(smMesh,dir); |
| 2218 |
if(QT_IS_EMPTY(qt)) |
| 2219 |
goto Lerror; |
| 2220 |
ts = qtqueryset(qt); |
| 2221 |
s_id = intersect_tri_set(ts,orig,dir,p); |
| 2222 |
#ifdef DEBUG_TEST_DRIVER |
| 2223 |
VCOPY(Pick_point[0],p); |
| 2224 |
#endif |
| 2225 |
#ifdef DEBUG |
| 2226 |
fprintf(stderr,"Back pick returning %d\n",s_id); |
| 2227 |
#endif |
| 2228 |
return(s_id); |
| 2229 |
} |
| 2230 |
{ |
| 2231 |
OBJECT t_set[QT_MAXCSET + 1]; |
| 2232 |
RT_ARGS rt; |
| 2233 |
FUNC func; |
| 2234 |
|
| 2235 |
/* Test each of the root triangles against point id */ |
| 2236 |
QT_CLEAR_SET(t_set); |
| 2237 |
VSUB(o,orig,SM_VIEW_CENTER(smMesh)); |
| 2238 |
ST_CLEAR_FLAGS(SM_LOCATOR(smMesh)); |
| 2239 |
rt.t_id = -1; |
| 2240 |
rt.os = t_set; |
| 2241 |
VCOPY(rt.orig,orig); |
| 2242 |
VCOPY(rt.dir,dir); |
| 2243 |
F_FUNC(func) = ray_trace_check_set; |
| 2244 |
F_ARGS(func) = (int *)(&rt); |
| 2245 |
stTrace_ray(SM_LOCATOR(smMesh),o,dir,func); |
| 2246 |
s_id = rt.t_id; |
| 2247 |
} |
| 2248 |
#ifdef DEBUG |
| 2249 |
fprintf(stderr,"Trace pick returning %d\n",s_id); |
| 2250 |
#endif |
| 2251 |
return(s_id); |
| 2252 |
|
| 2253 |
Lerror: |
| 2254 |
#ifdef DEBUG |
| 2255 |
eputs("smFindSamp(): point not found"); |
| 2256 |
#endif |
| 2257 |
return(INVALID); |
| 2258 |
|
| 2259 |
} |
| 2260 |
|
| 2261 |
|
| 2262 |
mark_active_tris(argptr,root,qt) |
| 2263 |
int *argptr; |
| 2264 |
int root; |
| 2265 |
QUADTREE qt; |
| 2266 |
{ |
| 2267 |
OBJECT *os,*optr; |
| 2268 |
register int i,t_id; |
| 2269 |
TRI *tri; |
| 2270 |
|
| 2271 |
if(QT_IS_EMPTY(qt) || QT_LEAF_IS_FLAG(qt)) |
| 2272 |
return; |
| 2273 |
|
| 2274 |
/* For each triangle in the set, set the which flag*/ |
| 2275 |
os = qtqueryset(qt); |
| 2276 |
|
| 2277 |
for (i = QT_SET_CNT(os), optr = QT_SET_PTR(os); i > 0; i--) |
| 2278 |
{ |
| 2279 |
t_id = QT_SET_NEXT_ELEM(optr); |
| 2280 |
/* Set the render flag */ |
| 2281 |
tri = SM_NTH_TRI(smMesh,t_id); |
| 2282 |
if(!T_IS_VALID(tri)) |
| 2283 |
continue; |
| 2284 |
SM_SET_NTH_T_ACTIVE(smMesh,t_id); |
| 2285 |
/* Set the Active bits of the Vertices */ |
| 2286 |
if(!SM_IS_NTH_T_BASE(smMesh,t_id)) |
| 2287 |
{ |
| 2288 |
S_SET_FLAG(T_NTH_V(tri,0)); |
| 2289 |
S_SET_FLAG(T_NTH_V(tri,1)); |
| 2290 |
S_SET_FLAG(T_NTH_V(tri,2)); |
| 2291 |
} |
| 2292 |
} |
| 2293 |
} |
| 2294 |
|
| 2295 |
|
| 2296 |
mark_tris_in_frustum(view) |
| 2297 |
VIEW *view; |
| 2298 |
{ |
| 2299 |
FVECT nr[4],far[4]; |
| 2300 |
FPEQ peq; |
| 2301 |
int debug=0; |
| 2302 |
FUNC f; |
| 2303 |
|
| 2304 |
F_FUNC(f) = mark_active_tris; |
| 2305 |
F_ARGS(f) = NULL; |
| 2306 |
|
| 2307 |
/* Mark triangles in approx. view frustum as being active:set |
| 2308 |
LRU counter: for use in discarding samples when out |
| 2309 |
of space |
| 2310 |
Radiance often has no far clipping plane: but driver will set |
| 2311 |
dev_zmin,dev_zmax to satisfy OGL |
| 2312 |
*/ |
| 2313 |
|
| 2314 |
/* First clear all the quadtree node and triangle active flags */ |
| 2315 |
qtClearAllFlags(); |
| 2316 |
smClear_flags(smMesh,T_ACTIVE_FLAG); |
| 2317 |
/* Clear all of the active sample flags*/ |
| 2318 |
sClear_all_flags(SM_SAMP(smMesh)); |
| 2319 |
|
| 2320 |
|
| 2321 |
/* calculate the world space coordinates of the view frustum */ |
| 2322 |
calculate_view_frustum(view->vp,view->hvec,view->vvec,view->horiz, |
| 2323 |
view->vert, dev_zmin,dev_zmax,nr,far); |
| 2324 |
|
| 2325 |
#ifdef TEST_DRIVER |
| 2326 |
VCOPY(FrustumFar[0],far[0]); |
| 2327 |
VCOPY(FrustumFar[1],far[1]); |
| 2328 |
VCOPY(FrustumFar[2],far[2]); |
| 2329 |
VCOPY(FrustumFar[3],far[3]); |
| 2330 |
VCOPY(FrustumNear[0],nr[0]); |
| 2331 |
VCOPY(FrustumNear[1],nr[1]); |
| 2332 |
VCOPY(FrustumNear[2],nr[2]); |
| 2333 |
VCOPY(FrustumNear[3],nr[3]); |
| 2334 |
#endif |
| 2335 |
/* Project the view frustum onto the spherical quadtree */ |
| 2336 |
/* For every cell intersected by the projection of the faces |
| 2337 |
|
| 2338 |
of the frustum: mark all triangles in the cell as ACTIVE- |
| 2339 |
Also set the triangles LRU clock counter |
| 2340 |
*/ |
| 2341 |
|
| 2342 |
if(EQUAL_VEC3(view->vp,SM_VIEW_CENTER(smMesh))) |
| 2343 |
{/* Near face triangles */ |
| 2344 |
|
| 2345 |
smLocator_apply(smMesh,nr[0],nr[2],nr[3],f); |
| 2346 |
smLocator_apply(smMesh,nr[2],nr[0],nr[1],f); |
| 2347 |
return; |
| 2348 |
} |
| 2349 |
/* Test the view against the planes: and swap orientation if inside:*/ |
| 2350 |
tri_plane_equation(nr[0],nr[2],nr[3], &peq,FALSE); |
| 2351 |
if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) |
| 2352 |
{/* Near face triangles */ |
| 2353 |
smLocator_apply(smMesh,nr[3],nr[2],nr[0],f); |
| 2354 |
smLocator_apply(smMesh,nr[1],nr[0],nr[2],f); |
| 2355 |
} |
| 2356 |
else |
| 2357 |
{/* Near face triangles */ |
| 2358 |
smLocator_apply(smMesh,nr[0],nr[2],nr[3],f); |
| 2359 |
smLocator_apply(smMesh,nr[2],nr[0],nr[1],f); |
| 2360 |
} |
| 2361 |
tri_plane_equation(nr[0],far[3],far[0], &peq,FALSE); |
| 2362 |
if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) |
| 2363 |
{ /* Right face triangles */ |
| 2364 |
smLocator_apply(smMesh,far[0],far[3],nr[0],f); |
| 2365 |
smLocator_apply(smMesh,nr[3],nr[0],far[3],f); |
| 2366 |
} |
| 2367 |
else |
| 2368 |
{/* Right face triangles */ |
| 2369 |
smLocator_apply(smMesh,nr[0],far[3],far[0],f); |
| 2370 |
smLocator_apply(smMesh,far[3],nr[0],nr[3],f); |
| 2371 |
} |
| 2372 |
|
| 2373 |
tri_plane_equation(nr[1],far[2],nr[2], &peq,FALSE); |
| 2374 |
if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) |
| 2375 |
{ /* Left face triangles */ |
| 2376 |
smLocator_apply(smMesh,nr[2],far[2],nr[1],f); |
| 2377 |
smLocator_apply(smMesh,far[1],nr[1],far[2],f); |
| 2378 |
} |
| 2379 |
else |
| 2380 |
{ /* Left face triangles */ |
| 2381 |
smLocator_apply(smMesh,nr[1],far[2],nr[2],f); |
| 2382 |
smLocator_apply(smMesh,far[2],nr[1],far[1],f); |
| 2383 |
} |
| 2384 |
tri_plane_equation(nr[0],far[0],nr[1], &peq,FALSE); |
| 2385 |
if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) |
| 2386 |
{/* Top face triangles */ |
| 2387 |
smLocator_apply(smMesh,nr[1],far[0],nr[0],f); |
| 2388 |
smLocator_apply(smMesh,far[1],far[0],nr[1],f); |
| 2389 |
} |
| 2390 |
else |
| 2391 |
{/* Top face triangles */ |
| 2392 |
smLocator_apply(smMesh,nr[0],far[0],nr[1],f); |
| 2393 |
smLocator_apply(smMesh,nr[1],far[0],far[1],f); |
| 2394 |
} |
| 2395 |
tri_plane_equation(nr[3],nr[2],far[3], &peq,FALSE); |
| 2396 |
if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) |
| 2397 |
{/* Bottom face triangles */ |
| 2398 |
smLocator_apply(smMesh,far[3],nr[2],nr[3],f); |
| 2399 |
smLocator_apply(smMesh,far[3],far[2],nr[2],f); |
| 2400 |
} |
| 2401 |
else |
| 2402 |
{ /* Bottom face triangles */ |
| 2403 |
smLocator_apply(smMesh,nr[3],nr[2],far[3],f); |
| 2404 |
smLocator_apply(smMesh,nr[2],far[2],far[3],f); |
| 2405 |
} |
| 2406 |
tri_plane_equation(far[2],far[0],far[1], &peq,FALSE); |
| 2407 |
if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) |
| 2408 |
{/* Far face triangles */ |
| 2409 |
smLocator_apply(smMesh,far[0],far[2],far[1],f); |
| 2410 |
smLocator_apply(smMesh,far[2],far[0],far[3],f); |
| 2411 |
} |
| 2412 |
else |
| 2413 |
{/* Far face triangles */ |
| 2414 |
smLocator_apply(smMesh,far[1],far[2],far[0],f); |
| 2415 |
smLocator_apply(smMesh,far[3],far[0],far[2],f); |
| 2416 |
} |
| 2417 |
|
| 2418 |
} |
| 2419 |
|
| 2420 |
|
| 2421 |
|
| 2422 |
|
| 2423 |
|
| 2424 |
|
| 2425 |
|
| 2426 |
|
| 2427 |
|
| 2428 |
|
