/***************************************************************************** * Sph_Cone.c - gets a set of points on the unit sphere and preprocess them * * into several bounding cones that bound all possible directions on the unit * * sphere. * * Based on covering points on a unit sphere - data that was extracted from * * http://www.research.att.com/~njas/coverings/index.html * ****************************************************************************** * (C) Gershon Elber, Technion, Israel Institute of Technology * ****************************************************************************** * Written by: Gershon Elber Ver 0.2, Sep. 1997 * *****************************************************************************/ #include #include #include "irit_sm.h" #include "geom_loc.h" /* #define GM_SPH_CONE_PRINT_STAT 1 */ #define SPHERE_COVER_4CONES_ANGLE 70.5287794 STATIC_DATA VectorType SphereCoverVectors4[] = { { -0.798892958090, -0.274518427439, 0.535172563978 }, { 0.337674633600, -0.783974919468, -0.520921458490 }, { 0.717804165557, 0.325344236568, 0.615555282682 }, { -0.256585841067, 0.733149110340, -0.629806388170 }, }; #define SPHERE_COVER_20CONES_ANGLE 29.6230958 STATIC_DATA VectorType SphereCoverVectors20[] = { { 0.069410018623, -0.554192741401, -0.829489393160 }, { -0.645546816289, 0.649818608537, 0.401254385710 }, { -0.189475893043, -0.979971744120, -0.061272066087 }, { -0.587941868231, -0.433327506296, -0.683045848273 }, { -0.162770329975, 0.240317121148, 0.956950102933 }, { 0.797863067128, 0.591968133114, -0.113966018893 }, { 0.435625616461, -0.808459236287, 0.395757481456 }, { -0.289423919283, -0.582047158852, 0.759904531762 }, { -0.858185269870, 0.009189435281, 0.513257824816 }, { 0.635173379444, 0.086089192890, -0.767556791194 }, { 0.601977151819, -0.679923015647, -0.418722103350 }, { 0.102222725749, 0.914033205248, 0.392547846772 }, { -0.182979128323, 0.255640843883, -0.949297843501 }, { -0.829751488753, -0.546226003207, 0.114671786316 }, { -0.392055952922, 0.838563642465, -0.378289764747 }, { 0.507890692912, -0.273912347853, 0.816712353379 }, { 0.985778945498, -0.162279766053, 0.043647982180 }, { 0.619830289856, 0.387585375458, 0.682340081781 }, { 0.280884557404, 0.818915653974, -0.500480785035 }, { -0.898525779136, 0.228218304925, -0.374923762865 }, }; #define SPHERE_COVER_50CONES_ANGLE 18.3000226 STATIC_DATA VectorType SphereCoverVectors50[] = { { 0.190702792257, -0.981542113237, 0.014405687340 }, { -0.262428475544, -0.649809330702, -0.713357643224 }, { -0.757185248658, -0.608582364395, 0.237272003666 }, { -0.426304692402, -0.610978642479, 0.667060271837 }, { -0.189071986824, -0.218912631273, 0.957250772975 }, { 0.182211644948, -0.480793872848, -0.857692349702 }, { 0.634234739468, -0.476225292310, -0.609061378986 }, { 0.138573494740, -0.549335450865, 0.824031520635 }, { -0.850272424519, 0.111690244637, -0.514355996624 }, { 0.936054584570, -0.269206611440, -0.226560398005 }, { 0.492522636428, -0.774523432367, 0.396906669252 }, { 0.788703111932, 0.550208870322, 0.274258271791 }, { -0.664067581296, 0.737143325619, 0.125035848469 }, { 0.908638719469, 0.328001374379, -0.258439110592 }, { -0.006195661612, -0.877383494750, 0.479749742895 }, { -0.819451977499, 0.333629559726, 0.466036234051 }, { -0.696725696325, 0.591963326558, -0.405157651752 }, { 0.414521381259, 0.854920409620, 0.311902415007 }, { 0.384615663439, -0.031426819973, -0.922541676089 }, { -0.937710540369, -0.274158137850, -0.213392259553 }, { -0.430031680502, 0.658785398118, 0.617312361486 }, { -0.706191943958, -0.216149516404, 0.674219788052 }, { -0.677302779630, -0.673867987469, -0.295233598910 }, { 0.664067581296, -0.737143325619, -0.125035848469 }, { 0.780043087900, 0.018379859626, -0.625455801375 }, { 0.785617635585, 0.069047058932, 0.614847487770 }, { -0.385449560359, -0.908763646148, 0.159928955138 }, { -0.195297921076, -0.124718904495, -0.972781535238 }, { -0.173958390951, 0.950530200265, 0.257353481837 }, { 0.865198533051, -0.418355681002, 0.276423626579 }, { 0.537705024704, 0.487319524400, -0.688035599887 }, { -0.495700722560, 0.200530692004, 0.845025581308 }, { 0.185202008113, 0.976284513250, -0.112110496499 }, { 0.183002784848, 0.796911788173, -0.575709632598 }, { -0.959049434401, -0.117280879058, 0.257816554978 }, { 0.512413094752, 0.451499290764, 0.730466431938 }, { -0.210907729343, -0.928675550967, -0.305089577101 }, { -0.952798985876, 0.300218523480, -0.045198772103 }, { 0.261558843777, -0.832393043675, -0.488578336313 }, { -0.493113175035, 0.232372513972, -0.838356969878 }, { 0.984755155630, 0.069671915844, 0.159383517690 }, { 0.645784916356, 0.732241481543, -0.216296676546 }, { 0.077671655454, 0.342571749352, -0.936275444925 }, { -0.623813427053, -0.327840173617, -0.709491104819 }, { 0.306698252447, 0.001059786417, 0.951806208119 }, { -0.307305398397, 0.917119164951, -0.253881523386 }, { -0.278146702796, 0.658472941257, -0.699319522828 }, { 0.076424998231, 0.747313388623, 0.660062055103 }, { -0.030075983144, 0.348389756866, 0.936867125332 }, { 0.591635780409, -0.378209760413, 0.711986291222 }, }; #define SPHERE_COVER_100CONES_ANGLE 12.9360973 STATIC_DATA VectorType SphereCoverVectors100[] = { { -0.112709020264, -0.187858187594, -0.975707936101 }, { -0.274997733533, -0.842207519338, 0.463748573326 }, { 0.794647692703, -0.069662799127, -0.603060641326 }, { -0.003367249854, -0.428169246763, 0.903692291118 }, { -0.254936184734, -0.960666929372, 0.110120805912 }, { 0.021508052014, 0.409928643145, -0.911863975227 }, { -0.845720030367, 0.215559679084, 0.488151261583 }, { 0.419674285688, -0.883702892810, 0.207226181403 }, { -0.735421463847, 0.677169496194, 0.024428316392 }, { 0.310922819190, -0.782048773952, 0.540117315017 }, { -0.686039156280, 0.587705702521, 0.428896586411 }, { 0.166309669614, 0.549765643664, 0.818595644087 }, { 0.223928352818, -0.885883965530, -0.406282773241 }, { 0.923141430132, -0.384279596619, 0.011793682352 }, { 0.548515754752, 0.623983185738, -0.556574746966 }, { 0.307740814053, -0.632770568132, -0.710561044514 }, { 0.828030427918, -0.382206135429, -0.410224425606 }, { 0.061731097288, -0.940022130497, 0.335481242277 }, { -0.256233565509, 0.525474700145, 0.811308016069 }, { 0.581062704325, -0.389540442266, -0.714579859748 }, { 0.682073622942, 0.600054205395, 0.417983877473 }, { 0.206196905114, 0.976575344801, -0.061509604566 }, { 0.903504892252, 0.311559534632, 0.294295029715 }, { -0.640151913278, -0.427286589518, -0.638460410759 }, { -0.390669220127, 0.728524547070, 0.562698447146 }, { -0.791236991063, -0.611101450399, -0.022339205258 }, { -0.148728511296, 0.988598198630, 0.023525100201 }, { 0.861101279035, -0.044045059942, 0.506522081792 }, { -0.498510049656, 0.845847055316, 0.189816987142 }, { -0.785492052324, -0.091768437065, -0.612030055374 }, { -0.956324912608, -0.290385546163, 0.033449889161 }, { 0.746395405382, 0.286843657494, 0.600511959754 }, { -0.439732424915, 0.880113776773, -0.178983610123 }, { -0.671873629093, -0.009048549458, 0.740610524081 }, { 0.599514046684, -0.620704257861, 0.505281238817 }, { -0.896364149638, 0.407188375480, 0.175296710804 }, { 0.855645176023, -0.374678255059, 0.357053968124 }, { -0.308504587971, 0.490353529342, -0.815094064921 }, { -0.024115427397, 0.284349733032, 0.958417275921 }, { -0.072164548561, 0.741785931401, -0.666742760688 }, { -0.045737984590, -0.778996704146, -0.625357634388 }, { -0.487363124266, -0.853292930871, -0.185387046076 }, { 0.703195910901, -0.689748994075, 0.172516189516 }, { -0.368359509856, 0.146697840653, 0.918036499061 }, { -0.576592753641, -0.796652534977, 0.181343687698 }, { 0.408687869087, 0.331491863355, -0.850345441140 }, { 0.515660119243, 0.842984163202, 0.153206854127 }, { 0.163708799519, 0.939256357029, 0.301656962372 }, { -0.815116893500, -0.477288071066, 0.328299474902 }, { -0.896773251705, -0.139623109251, 0.419884651899 }, { -0.237762904726, 0.156901446171, -0.958567022346 }, { 0.985883112065, -0.031614961103, 0.164423179813 }, { 0.165257575922, 0.066886723042, -0.983979724348 }, { -0.400302214548, 0.760630113073, -0.511077260599 }, { 0.485896806233, 0.454497758299, 0.746549448930 }, { 0.968824286014, -0.118224599399, -0.217721029185 }, { -0.561287811026, -0.658361835405, 0.501513394527 }, { 0.009366997518, 0.768229912035, 0.640105507337 }, { -0.144460399635, -0.950108704157, -0.276450070553 }, { -0.077941730618, 0.932867182419, -0.351687226444 }, { 0.544239121489, -0.004606805742, -0.838917490095 }, { 0.287959951907, -0.272909772582, -0.917932089418 }, { 0.691350424662, 0.318322496489, -0.648618051782 }, { 0.007765733637, -0.509136282839, -0.860650880262 }, { -0.718862362206, 0.622464888729, -0.309474336915 }, { -0.922649954446, 0.343029527925, -0.176203867421 }, { 0.316887078807, 0.168398971669, 0.933394002728 }, { -0.609988544136, 0.485003081150, -0.626646620221 }, { -0.585871192627, 0.380432769656, 0.715559816919 }, { -0.683955607004, -0.629989984445, -0.367855060846 }, { -0.990185925737, 0.062839465216, 0.124832016416 }, { 0.965496608056, 0.253959376365, -0.057627546601 }, { -0.658771960065, -0.341395511292, 0.670424199663 }, { 0.561542293988, -0.673339718021, -0.480919821188 }, { -0.882674743421, -0.337714913301, -0.326854606159 }, { -0.470625923946, -0.173981519416, -0.865009635687 }, { 0.544206080027, 0.813990029506, -0.203125510365 }, { -0.571665641852, 0.165906078182, -0.803538154811 }, { -0.022318644449, -0.724908772856, 0.688483222388 }, { -0.967274561524, 0.000325002708, -0.253731780685 }, { 0.795924417675, 0.603232399561, 0.051136989146 }, { 0.646064177155, -0.308444628492, 0.698185496964 }, { 0.262168762274, 0.862321874127, -0.433207253926 }, { -0.179290877655, 0.915501178242, 0.360156038776 }, { 0.258992810734, 0.635203750804, -0.727625533938 }, { -0.336635880172, -0.549052573740, 0.764995132573 }, { 0.381136740558, 0.760132641532, 0.526244383305 }, { 0.794666264206, 0.531409771182, -0.293443661183 }, { 0.115314016119, -0.992813084275, -0.032013389282 }, { 0.473066538572, -0.868271218613, -0.149375831708 }, { -0.325802675448, -0.501604215242, -0.801402412355 }, { -0.828178982250, 0.254417341202, -0.499391017482 }, { 0.892252084799, 0.191528743133, -0.408904580399 }, { -0.022852162831, -0.072931425646, 0.997075115331 }, { 0.759662027471, -0.632952346466, -0.149281374179 }, { 0.331550352275, -0.519557020627, 0.787486421876 }, { 0.330153645948, -0.185311885551, 0.925558250397 }, { -0.358979819342, -0.216252501123, 0.907947324216 }, { -0.381458517164, -0.749844189733, -0.540576626547 }, { 0.602483247407, 0.047034345567, 0.796744441614 }, }; #define SPHERE_COVER_130CONES_ANGLE 11.3165625 STATIC_DATA VectorType SphereCoverVectors130[] = { { 0.111944892444, -0.042826107703, -0.992791148834 }, { 0.497848651372, -0.260554766282, 0.827198847197 }, { -0.857586830854, 0.500548738986, 0.118303787895 }, { 0.017818647437, 0.593056077138, 0.804963964038 }, { -0.410947711207, 0.383912497200, -0.826881594956 }, { -0.921896087937, -0.371954041533, -0.108433353715 }, { -0.749534781091, 0.006689881906, -0.661931157112 }, { -0.907257763669, -0.176018254831, -0.381969792768 }, { -0.131077783182, 0.921302899718, 0.366086849011 }, { 0.397952336818, 0.084746616893, 0.913483413868 }, { 0.142522958107, 0.579972969368, -0.802071418613 }, { 0.871781036258, -0.441797970794, -0.211689339019 }, { 0.333889371715, 0.610888379626, 0.717867169529 }, { 0.423202393577, -0.886085597798, -0.189082115889 }, { 0.531849688850, -0.506170233712, -0.678916490637 }, { 0.518354340456, -0.518815610558, 0.679808163084 }, { 0.881583253853, -0.462610239163, 0.093822877854 }, { -0.075738745742, -0.954108051956, 0.289726538584 }, { -0.687965055928, 0.651933499612, 0.318883665837 }, { -0.472037461586, 0.244812000543, 0.846904787235 }, { -0.542994119227, -0.088150071912, 0.835096970201 }, { 0.804261522368, -0.075985295698, -0.589397690259 }, { -0.061353203841, -0.632558465004, -0.772078733891 }, { 0.405794041231, 0.671146048233, -0.620398401283 }, { -0.729829886928, -0.301739742048, -0.613434155472 }, { 0.980442768894, 0.097432874143, 0.170993596315 }, { -0.523656332865, -0.221894513816, -0.822524691001 }, { 0.465959439054, -0.875608648174, 0.127245022915 }, { 0.281522436067, 0.878640605137, -0.385662810877 }, { -0.934329688549, 0.312868428417, -0.170708458871 }, { -0.370090511627, -0.816399328411, 0.443311570212 }, { -0.909493437968, 0.025025550276, 0.414964343421 }, { -0.218371314928, -0.167614830658, -0.961363217793 }, { 0.377957197838, -0.777256167494, -0.503012131900 }, { 0.720157421194, 0.691369893961, -0.058145998046 }, { -0.972580310889, -0.168664159253, 0.160124762915 }, { 0.319989992306, -0.303680028766, -0.897432361729 }, { -0.846336499788, -0.329793810844, 0.418270929717 }, { 0.476409339346, 0.867213228717, 0.144828715362 }, { 0.235675103031, -0.895029840991, 0.378653969616 }, { -0.671791055240, 0.302635137923, -0.676098180935 }, { -0.480064260773, 0.074515135027, -0.874062811956 }, { -0.544761600904, -0.745951673947, -0.383133002557 }, { 0.626174286939, 0.571738580242, 0.530113908462 }, { -0.992964669131, -0.019597611390, -0.116777988151 }, { 0.723091950640, 0.646600708365, 0.242992907763 }, { 0.066612465307, -0.830640683882, -0.552809942514 }, { -0.352995673195, -0.923585203476, 0.149614256807 }, { 0.493653857149, -0.738328765146, 0.459539445117 }, { -0.833169849589, 0.356088434346, 0.423118218780 }, { 0.754871224985, -0.487250715494, 0.439040057361 }, { 0.655037104152, 0.023455740884, 0.755232559517 }, { 0.412771471776, 0.033081952482, -0.910233648494 }, { -0.761153621599, 0.467932184227, -0.449093123898 }, { -0.787013402209, 0.591695437208, -0.174660852179 }, { 0.695991819724, -0.711728409864, -0.095068691298 }, { -0.464029544033, -0.876484962180, -0.128260253929 }, { 0.169929753989, 0.254154610448, -0.952118328772 }, { 0.880007768981, 0.037214539014, 0.473499107175 }, { -0.173955945298, 0.333591462113, 0.926529041491 }, { -0.760266860016, -0.130302502774, 0.636408326216 }, { 0.780295846052, -0.377734621987, -0.498452551663 }, { -0.362768277526, -0.633736529388, 0.683210938238 }, { -0.282041852362, -0.751347756013, -0.596597805619 }, { 0.046614479274, 0.073455683887, 0.996208488010 }, { -0.089082722552, -0.577255420387, 0.811689870432 }, { -0.351163306274, -0.341055191122, 0.871989499778 }, { 0.663182183169, 0.440971477889, -0.604759080335 }, { -0.646552641876, -0.614281734452, 0.452357856557 }, { 0.154426505789, 0.818896942772, 0.552775044926 }, { 0.438593968749, 0.790809189901, 0.426914692856 }, { -0.542962390929, -0.548965990543, -0.635474769399 }, { 0.907929630019, 0.418320779689, 0.025913526304 }, { 0.065304372460, 0.802278547548, -0.593367062509 }, { -0.620392642915, -0.762093706056, 0.185273178853 }, { 0.941412322223, -0.116009868681, -0.316677356139 }, { -0.261149016209, 0.846929578111, -0.463153840043 }, { -0.059665040113, -0.274187739007, 0.959823507816 }, { 0.695960289799, -0.684551157989, 0.216861673631 }, { 0.168299282901, 0.954753314145, 0.245196777396 }, { 0.218194453977, -0.714699248783, 0.664527022280 }, { -0.564462553710, 0.755205795169, -0.333235996775 }, { -0.610958792269, 0.494868573733, 0.617927542888 }, { 0.639529258944, -0.663975762203, -0.387477111071 }, { -0.316993019544, -0.464359018952, -0.826974078082 }, { -0.100097351708, 0.423265554011, -0.900459210388 }, { 0.016937620938, -0.371446909383, -0.928299687803 }, { 0.194628664292, 0.978918654844, -0.061951181851 }, { -0.338960304856, 0.538417457603, 0.771500195377 }, { -0.779586851597, -0.508080978878, -0.366194016300 }, { 0.165273777209, -0.984990561381, 0.049781232141 }, { -0.612950382754, -0.406936194748, 0.677270079032 }, { 0.180265543982, 0.346290043555, 0.920645174570 }, { -0.719577983953, 0.182025813498, 0.670129932463 }, { -0.427171969786, 0.754725726321, 0.497908811085 }, { -0.362765422091, 0.921614699997, -0.137940538116 }, { 0.866634511389, 0.366497758776, 0.338561686687 }, { -0.213523667306, -0.910513442010, -0.354080377147 }, { -0.037730016746, 0.956279543228, -0.290010136552 }, { 0.136536697857, -0.948609554209, -0.285477920435 }, { 0.606214066967, -0.208283706568, -0.767543094233 }, { -0.254922484979, -0.001416820101, 0.966960453428 }, { -0.847099758685, -0.502592220902, 0.172693532892 }, { -0.060472235084, -0.814729968086, 0.576678581536 }, { 0.476329696365, 0.865078063682, -0.157321209088 }, { 0.827560856007, 0.477329319343, -0.295465310104 }, { 0.987522639334, -0.155840543099, -0.022644217126 }, { 0.648538550362, 0.151072969660, -0.746039345860 }, { -0.424272619188, 0.880897684954, 0.209790400229 }, { 0.246304453351, -0.600951015018, -0.760389368981 }, { 0.212792438455, -0.479468770325, 0.851368941367 }, { -0.175547718070, 0.146524162963, -0.973505863920 }, { 0.732276768424, 0.290266491473, 0.616048778407 }, { -0.503717834130, 0.618000090122, -0.603609336540 }, { 0.493639541790, 0.362641082145, 0.790450153872 }, { -0.125061845407, -0.989972609095, -0.065679278225 }, { -0.730316644534, -0.677305591293, -0.088852304965 }, { 0.925160109997, -0.236301370896, 0.297052909620 }, { 0.971699635498, 0.172793581150, -0.161065811291 }, { 0.861132316291, 0.201736264862, -0.466640774161 }, { -0.152469491586, 0.761002171785, 0.630578105338 }, { -0.205447621644, 0.656640467234, -0.725682141259 }, { 0.602428598329, 0.695869821124, -0.390953929164 }, { -0.130700659007, 0.990425301716, 0.044441623613 }, { 0.422705520876, 0.387837441638, -0.819086173549 }, { 0.755601269193, -0.242660331540, 0.608426400460 }, { -0.970658748411, 0.193646385334, 0.142557600513 }, { -0.633850645274, 0.773400969803, 0.009181381203 }, { 0.233739932999, -0.175750482827, 0.956283122301 }, { -0.892947221175, 0.149838408455, -0.424492297694 }, }; STATIC_DATA RealType SphereCoverConesAngleArray[] = { SPHERE_COVER_4CONES_ANGLE, SPHERE_COVER_20CONES_ANGLE, SPHERE_COVER_50CONES_ANGLE, SPHERE_COVER_100CONES_ANGLE, SPHERE_COVER_130CONES_ANGLE, 0.0 }, SphereCoverConesAngle = SPHERE_COVER_4CONES_ANGLE; STATIC_DATA VectorType *SphereCoverVectorsArray[] = { SphereCoverVectors4, SphereCoverVectors20, SphereCoverVectors50, SphereCoverVectors100, SphereCoverVectors130, NULL }, *SphereCoverVectors = SphereCoverVectors4; STATIC_DATA int SphereCoverLengthArray[] = { 4, 20, 50, 100, 130, 0 }, SphereCoverLength = 4; typedef struct GMSphConeQueryUnitVectStruct { VectorType Vec; IPVertexStruct *V; } GMSphConeQueryUnitVectStruct; typedef struct GMSphConeQueryConeStruct { VectorType Vec; int *UnitVecIndices; int UnitVecLens; } GMSphConeQueryConeStruct; typedef struct GMSphConeStruct { GMSphConeQueryUnitVectStruct *UnitVecs; GMSphConeQueryConeStruct *Cones; int UnitVecLen, GetVecCount, *GetVecIndices; } GMSphConeStruct; /***************************************************************************** * DESCRIPTION: M * Sets the number of cones that will be distributed onto the sphere. M * Exact number of cones will be close the n but not exactly n. M * This function better be called before any other GMSphConeConeXXX M * function. M * * * PARAMETERS: M * n: Number of cones to distribute on the sphere (approximately). M * * * RETURN VALUE: M * void M * * * SEE ALSO: M * GMSphConeQueryInit, GMSphConeQueryFree, GMSphConeQueryGetVectors M * * * KEYWORDS: M * GMSphConeSetConeDensity M *****************************************************************************/ void GMSphConeSetConeDensity(int n) { int i, Index = 0, Diff = ABS(n - SphereCoverLengthArray[0]); for (i = 1; SphereCoverLengthArray[i] > 0; i++) { if (FABS(SphereCoverLengthArray[i] - n) < Diff) { Diff = ABS(SphereCoverLengthArray[i] - n); Index = i; } } /* Update local info on number of cones per sphere. */ SphereCoverConesAngle = SphereCoverConesAngleArray[Index]; SphereCoverVectors = SphereCoverVectorsArray[Index]; SphereCoverLength = SphereCoverLengthArray[Index]; } /***************************************************************************** * DESCRIPTION: M * Proeprocess the given set of points into the different bounding cones of M * the unit sphere. M * * * PARAMETERS: M * PObj: A point list object to preprocess. M * * * RETURN VALUE: M * VoidPtr: Processed data structure for fast cone queries. M * * * SEE ALSO: M * GMSphConeQueryFree, GMSphConeQueryGetVectors, GMSphConeSetConeDensity M * * * KEYWORDS: M * GMSphConeQueryInit M *****************************************************************************/ VoidPtr GMSphConeQueryInit(IPObjectStruct *PObj) { int i, j, Index, *VecIndices; RealType CosAngle; IPVertexStruct *V = PObj -> U.Pl -> PVertex; GMSphConeQueryUnitVectStruct *SQV; GMSphConeQueryConeStruct *SQC; GMSphConeStruct *SphCone = (GMSphConeStruct *) IritMalloc(sizeof(GMSphConeStruct)); #ifdef GM_SPH_CONE_PRINT_STAT int NumOfPts = IPVrtxListLen(V), NumOfHits = 0; #endif /* GM_SPH_CONE_PRINT_STAT */ SphCone -> GetVecCount = 1; SphCone -> UnitVecLen = IPVrtxListLen(V); if (SphCone -> UnitVecLen == 0) GEOM_FATAL_ERROR(GEOM_ERR_INVALID_POLYGON); SphCone -> UnitVecs = (GMSphConeQueryUnitVectStruct *) IritMalloc(sizeof(GMSphConeQueryUnitVectStruct) * SphCone -> UnitVecLen); SphCone -> GetVecIndices = (int *) IritMalloc(sizeof(int) * SphCone -> UnitVecLen); ZAP_MEM(SphCone -> GetVecIndices, sizeof(int) * SphCone -> UnitVecLen); /* Copy the vectors as well as their vertex of origin. */ for (i = 0, SQV = SphCone -> UnitVecs; V != NULL; V = V -> Pnext, i++, SQV++) { PT_COPY(SQV -> Vec, V -> Normal); PT_NORMALIZE(SQV -> Vec); SQV -> V = V; } /* Now process and insert all these unit vectors into the different */ /* cone that spans the entire unit sphere. */ SphCone -> Cones = (GMSphConeQueryConeStruct *) IritMalloc(sizeof(GMSphConeQueryConeStruct) * SphereCoverLength); CosAngle = cos(DEG2RAD(SphereCoverConesAngle)); VecIndices = (int *) IritMalloc(sizeof(int) * SphCone -> UnitVecLen); for (i = 0, SQC = SphCone -> Cones; i < SphereCoverLength; i++, SQC++) { PT_COPY(SQC -> Vec, SphereCoverVectors[i]); Index = 0; /* Find points that are contained in this cone and record in cone. */ for (j = 0, SQV = SphCone -> UnitVecs; j < SphCone -> UnitVecLen; j++, SQV++) { if (DOT_PROD(SQC -> Vec, SQV -> Vec) > CosAngle) { VecIndices[Index++] = j; # ifdef GM_SPH_CONE_PRINT_STAT NumOfHits++; # endif /* GM_SPH_CONE_PRINT_STAT */ } } if (Index > 0) { SQC -> UnitVecIndices = (int *) IritMalloc(sizeof(int) * Index); GEN_COPY(SQC -> UnitVecIndices, VecIndices, sizeof(int) * Index); } else SQC -> UnitVecIndices = NULL; SQC -> UnitVecLens = Index; } IritFree(VecIndices); #ifdef GM_SPH_CONE_PRINT_STAT fprintf(stderr, IRIT_EXP_STR("SphConeStat: Out of %d strokes, we got %d hits (%6.2f%%) (cone entries)\n"), NumOfPts, NumOfHits, (100.0 * NumOfHits) / NumOfPts); #endif /* GM_SPH_CONE_PRINT_STAT */ return SphCone; } /***************************************************************************** * DESCRIPTION: M * Release all data allocated by GMSphConeQueryInit function. M * * * PARAMETERS: M * SphConePtr: Cone data structure to free. M * * * RETURN VALUE: M * void M * * * SEE ALSO: M * GMSphConeQueryInit, GMSphConeQueryGetVectors, GMSphConeSetConeDensity M * * * KEYWORDS: M * GMSphConeQueryFree M *****************************************************************************/ void GMSphConeQueryFree(VoidPtr SphConePtr) { int i; GMSphConeStruct *SphCone = (GMSphConeStruct *) SphConePtr; IritFree(SphCone -> UnitVecs); for (i = 0; i < SphereCoverLength; i++) IritFree(SphCone -> Cones[i].UnitVecIndices); IritFree(SphCone -> Cones); IritFree(SphCone -> GetVecIndices); IritFree(SphCone); } /***************************************************************************** * DESCRIPTION: M * Invokes SQFunc with all vectors in the preprocessed data set that are M * at most Angle degrees for the prescibed Dir. Each such vector is M * guaranteed to be invoked once only. M * * * PARAMETERS: M * SphConePtr: Processed data struct for efficient Direction querying. M * Dir: Direction to query. M * Angle: Angular span to query. M * SQFunc: Function to invoke on detected elements. M * * * RETURN VALUE: M * void M * * * SEE ALSO: M * GMSphConeQueryInit, GMSphConeQueryFree, GMSphConeSetConeDensity M * GMSphConeQuery2GetVectors M * * * KEYWORDS: M * GMSphConeQueryGetVectors M *****************************************************************************/ void GMSphConeQueryGetVectors(VoidPtr SphConePtr, VectorType Dir, RealType Angle, GMSphConeQueryCallBackFuncType SQFunc) { int i, j; RealType ConeCosAngle = cos(DEG2RAD((Angle + SphereCoverConesAngle))), ExactCosAngle = cos(DEG2RAD(Angle)); GMSphConeQueryConeStruct *SQC; GMSphConeStruct *SphCone = (GMSphConeStruct *) SphConePtr; SphCone -> GetVecCount++; /* Increment the count of this traversal. */ for (i = 0, SQC = SphCone -> Cones; i < SphereCoverLength; i++, SQC++) { if (DOT_PROD(SQC -> Vec, Dir) > ConeCosAngle) { int *UVI = SQC -> UnitVecIndices; /* Test the all vectors in this cone. */ for (j = SQC -> UnitVecLens - 1; j >= 0; j--, UVI++) { if (DOT_PROD(SphCone -> UnitVecs[*UVI].Vec, Dir) > ExactCosAngle) { /* Found one - see if we visited this one before */ if (SphCone -> GetVecIndices[*UVI] != SphCone -> GetVecCount) { /* First time - invoke and mark as visited. */ SQFunc(SphCone -> UnitVecs[*UVI].V); SphCone -> GetVecIndices[*UVI] = SphCone -> GetVecCount; } } } } } } /***************************************************************************** * DESCRIPTION: M * Invokes SQFunc with all vectors in the preprocessed data set that the M * cone containing them satisfy the query function SQQuery. M * Each such vector is guaranteed to be invoked once only. M * * * PARAMETERS: M * SphConePtr: Processed data struct for efficient Direction querying. M * SQQuery: Query function to invoke. M * SQFunc: Function to invoke on detected elements. M * * * RETURN VALUE: M * void M * * * SEE ALSO: M * GMSphConeQueryInit, GMSphConeQueryFree, GMSphConeSetConeDensity M * GMSphConeQuery2GetVectors M * * * KEYWORDS: M * GMSphConeQuery2GetVectors M *****************************************************************************/ void GMSphConeQuery2GetVectors(VoidPtr SphConePtr, GMSphConeQueryDirFuncType SQQuery, GMSphConeQueryCallBackFuncType SQFunc) { int i, j; GMSphConeQueryConeStruct *SQC; GMSphConeStruct *SphCone = (GMSphConeStruct *) SphConePtr; SphCone -> GetVecCount++; /* Increment the count of this traversal. */ for (i = 0, SQC = SphCone -> Cones; i < SphereCoverLength; i++, SQC++) { if (SQQuery(SQC -> Vec, SphereCoverConesAngle)) { int *UVI = SQC -> UnitVecIndices; /* Invoke the all vectors in this cone not yet visited. */ for (j = SQC -> UnitVecLens - 1; j >= 0; j--, UVI++) { if (SphCone -> GetVecIndices[*UVI] != SphCone -> GetVecCount) { /* First time - invoke and mark as visited. */ SQFunc(SphCone -> UnitVecs[*UVI].V); SphCone -> GetVecIndices[*UVI] = SphCone -> GetVecCount; } } } } }