RE: [Algorithms] Colliding against polygon soup
Brought to you by:
vexxed72
Menu
▾
▴
RE: [Algorithms] Colliding against polygon soup
|
From: Mitch W. <mi...@mi...> - 2000-12-05 22:23:45
|
For skeletal animated models, how about the way Half-Life( I think) did it?
A OOBB for the entire model, and individial OOBBs for each bone. Let's you
get fairly detailed for hit regions (head, left arm, etc), wo/ going to the
tri. level.
-----Original Message-----
From: Jonathan Mavor
Sent: Tue 12/5/2000 2:51 PM
To: gda...@li...
Cc:
Subject: Re: [Algorithms] Colliding against polygon soup
A sphere test actually works quite well assuming you aren't doing any
serious physics. Also, there is a lot to be gained from properly choosing
which triangles go into your collision database. For instance, running a
mesh decimation algorithm to reduce triangle count but still keep the
overall shape can speed up your collisions by reducing un-necessary detail.
Of course, you have to keep your collision and rendering databases seperate,
which IMHO is the way to go.
-Jon
----- Original Message -----
From: "Brian Hook" <bw...@wk...>
To: <gda...@li...>
Sent: Tuesday, December 05, 2000 8:53 AM
Subject: Re: [Algorithms] Colliding against polygon soup
> >All these are pretty easy to collide and deal with polygons, so you
> >shouldn't have much trouble.
>
> Sounds pretty straight forward. Subdivide the soup so that you can
quickly
> find a "potentially collidable set", then collide against that set. The
> collision against the subset can usually be as simple as a sphere test
(for
> a simple environment) vs each triangle I assume?
>
> Do people sweep the sphere or do they just test the desired destination
and
> back off until it no longer penetrates?
>
> Yes yes, I'm quite the neophyte, bear with me. =)
>
> Brian
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
<http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list>
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
<http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list>
begin 600 winmail.dat
M>)\^(AP6`0:0"``$```````!``$``0>0!@`(````Y`0```````#H``$%@`,`
M#@```-`'#``%``T`+0`!``(`)0$!"8`!`"$````R-C4T0C@P.$$T138Y1C0Q
M044U1#`W.4(Q.3$P,CA%-0`7!P$@@`,`#@```-`'#``%``X`%P`:``(`*0$!
M#8`$``(````"``(``0.0!@"$%P``.@```$``.0!%D(&>!%_``1\`,4`!````
M#@```#,`-@`V`#D`,0`X```````#`!I``````!\`,$`!````#@```#,`-@`V
M`#D`,0`X```````#`!E``````!\`20`!````8````%(`90`Z`"``6P!!`&P`
M9P!O`'(`:0!T`&@`;0!S`%T`(`!#`&\`;`!L`&D`9`!I`&X`9P`@`&$`9P!A
M`&D`;@!S`'0`(`!P`&\`;`!Y`&<`;P!N`"``<P!O`'4`<````$``3@"`1QVU
M]%[``0(!6P`!````/P````````"!*Q^DOJ,0&9UN`-T!#U0"`````$IO;F%T
M:&%N($UA=F]R`%--5%``:F]N0&MN;W=W;VYD97(N8V]M```?`&8``0````H`
M``!3`$T`5`!0```````?`&<``0```"8```!J`&\`;@!``&L`;@!O`'<`=P!O
M`&X`9`!E`'(`+@!C`&\`;0``````'P!:``$````>````2@!O`&X`80!T`&@`
M80!N`"``30!A`'8`;P!R```````?`#)``0```"8```!J`&\`;@!``&L`;@!O
M`'<`=P!O`&X`9`!E`'(`+@!C`&\`;0```````@%<``$````8````4TU44#I*
M3TY`2TY/5U=/3D1%4BY#3TT``P`=0``````"`5X``0```#\`````````@2L?
MI+ZC$!F=;@#=`0]4`@````!*;VYA=&AA;B!-879O<@!33510`&IO;D!K;F]W
M=V]N9&5R+F-O;0``'P!H``$````*````4P!-`%0`4```````'P!I``$````F
M````:@!O`&X`0`!K`&X`;P!W`'<`;P!N`&0`90!R`"X`8P!O`&T``````!\`
M70`!````'@```$H`;P!N`&$`=`!H`&$`;@`@`$T`80!V`&\`<@``````'P`S
M0`$````F````:@!O`&X`0`!K`&X`;P!W`'<`;P!N`&0`90!R`"X`8P!O`&T`
M``````(!7P`!````&````%--5%`Z2D].0$M.3U=73TY$15(N0T]-``,`'D``
M`````@%Q``$````;`````<!>^12>O8HTDE8A1PN&)GDKDB[?*``"S2[-`!\`
M=``!````4````&<`9`!A`&P`9P!O`'(`:0!T`&@`;0!S`"T`;`!I`',`=`!`
M`&P`:0!S`'0`<P`N`',`;P!U`'(`8P!E`&8`;P!R`&<`90`N`&X`90!T````
M`@$)$`$````K#@``)PX``(`X``!,6D9UHG10,P,`"@!R8W!G,3(U@C(#0VAT
M;6PQ`S`_`0,!]PJ``J0#XP(`8VC!"L!S970P(`<3`H#_$`,`4`16"%4'LA'5
M#E$#`=T0US(&``;#$=4S!$80V6\2ZQ'C".\)]SL8SPXP-3L1T@Q@8P!0"PD!
M9#,VDQ%@"Z4T(!`"*EP.LKT!D&<4\`JC$>,=Z#04\``\(41/0U194`!%($A4
M34P@4`!50DQ)0R`B+2`O+U<S0R&`1%0B1""4,RXR(8!%3IPB/A[M'H\CP3$X
M'_!O(*(C#R0?)I`S'8`E<$5\040ES0[Q)N\I;R3T-D$.\#Q-151!![!!,2Q@
M/2)'"?`$D&%T106P(A+03TY4(M!4$RSP!>%%>!#Q;F=E/092=A,Q+T$`D`(@
M(#9@+C`N-#0E0"*0,B<B_BK/)0,W-Q_P5$DX5$Q%)<XP4`?P93H@(%M!;&<%
ML&ET$&AM<UT2T6QL:;)D"X!G(":0"W%S!4!:<`;P>35``Z!S"&!P]21N-1_P
M+S-?,8\F132A+SC@*$\FGSRT-1%@/$*03T19(#8P<CT\T#YR/"`\DP`A`S`_
M,61OYP#@/S$*L5QQ&+`_,1#P/P,P/Y418#Q+'/$]3V<YXC8?\$1)5C]I``!!
MIUD\:38T1-]!\D8%L7/X:V5L$4`'0#9P`P``P`IT"8`@!&)L<RP@_&AO!^`!
MH`A@!4`U@"[P&'=A>2"0!T!F+4QA!I!E*"!)2K$+@&ON*3[A28`U<#\=G!V`
M0R3!+)!/3T)"(`(0!<#[2L()\'0_`"[P2:-*``!P\TRA4#!I=C8A2.%.<@0@
MO4["90#007`&X"TP+CQ+@C@=@"9N8G-P`H"9/X@G80%`0:<@3!%`^B<$('D(
M8$S_0S,NX`5`^F8+<'(W(#[@2,$#$$EQ;T["3"`%0!C09R_!!"`H>4K0861*
M`$BP`8`V<'(F;4H`$4!C*4H`=V]\+R`U0#9"+7!*LS]`:9XN5=]#,TBP+T!L
M+CQIOP'`/W<*HC]W"G$D?#`H$?\AX$2K7YA"+T,_1$,A$"`P<$M154\M\#[F
M-W!T!GE(L"XQ05)'24XP+5))1R"@-/`P</YX(O$_B`JQ$`)`E4$S0/'_08]C
M?Q\;51%D3T1_18]&GUMJ:$`0:1S2)'PT)5%&TRW1-W!I>F;@,F[;"^*U:EDM
M=E)/!1!9$&Y(X>I-!Y!S//!E=E-RO2P0[3Z!4C]K"X!E"H%J?U+6JSZ0;MMB
M:EE&`V$Z;9S-'^$O?!IB:2!*`B`M8/,NL070878%L5Q/;!]3(?]M;GC?>>]Z
M_WP/AG@&8`(P5WW_?P]4MU0*4"`.("\,-2\!T(U0(#(Z-?D.\%!-=_^%'X8O
MAS^(3_F0I51OB@^+'U2W@9^"K]F#M&=D!T`U1BTV$#;0\D"9XG,N-X%!4`$0
M!;#]+N`N+3`%0(X?CR^0/Y%/\Y)?GC1#8Y/OE/^6#YP?CYTOGC^?3XC>=6)J
M!9#_B?^B;U2H--*6GY>O@[0U'_\V+S<WI!^E+Z8_LH^SG[2O]236-6YQ+W/B
MJW]O[EZO_U^_8,^Y[[@O#B"V7FCSOZ]_P+_!S\+?:[]LSW!9'_!0_\1_<;EQ
M+W(_<T]T7W5M4E__4V]4>M#/T=_2[]/_U0]4QG\LD->P2M!/@4E@-M$`T'1.
M=0=`5[%:X')K!"!Q_G6P`$KA2*`#(*TOQS^#M/)A!!!U;;#25:(*P`GPSB<%
M0$!0L--N>;A?N6__HU^UK[:_U?_-O\[/=6T1,.\%$`A@!"#9H'D-T9IPUH__
MUY]4>]O_W0^#M*^P-X!*`-]*P4^!!`"Q`%G0;TJA6Y!^8B[PL2)80@-A-O`#
M8'#G!)!7L1#P;V\`D"[0X$__X5_B;^-_Y(_EG^:M"J-5(/OGG^BO=TP@06%;
M\2[!2+#_!""OT%!16X%5H07`&$&9X?\OPID@`9'><%(_ZZ]474A"?[%"#;":
MT$H`[:_NOX.T<OQU;A0PL.+SK_2_]<_VW]_W[_C_YJ_[C\_=;?Y007#]''!C
M23(OPIDW6W(8T1N`_UO3_A,$3P5?@Z480`;@FW`^8DJ1-M!8(&I`2)!E</]*
ML@=O"'\)CPJ?"Z\,OPW/^P[?S]UO+T':D3=P+K#RP/_S$($!`;`7,$F`-Z`3
MGQ2O]X.E_PSP\&)+(!*CL-(&X.XM+3":T'=1<E?&`'P8?_\9CQJ?&Z\<OQW/
M'M\?[\8`WD_5@"+/(]\5QW(`4$H`_U6B(:`A(%MR%R/_#5`BWU'_3]"9<+#A
M__;P\#'O,O^#M/<`4/+!25$L*$\I7RIO*W\_+(\MGRZO+[_\G_VB24W\2$_P
MTDK&6X&OT"@_/'__?]N\#[T5R?]`W[N4JS')P?_&+SE_R$_)7\O_S0]"/T-/
M_TP/`0\"'U:_5\]8WUGO6O_]V+HM@*%&KT>_2,])WTKO_UP?30].'T\O4#]1
M3U)?4V__5']5CW7Y,:!VO79$7^]@__\]GSZO/[]E3VTO;C]6#7VS)SA?:"^#
MI2)"_?(@2&GS0&LB7*\F:0!>"3PE=SAB_8!`=]L0;V96=$8`$J`N%B!M?Q]G
M_8`Z/G<_<F]S?W2/=9]VK_]WOWC/>=^327N_?,^8I8+/_X`OBL69'YHOFS.1
MCX/?BL__A?^'#X@?B2^*/XM/C%^-;S^I=-]@JB"._Y`/!F54=:O^4)0@>?!@
M1"=!;?&@.?\P,#7P8%8@IM`@..@Z-3/98$V9'YHOFS\_G$^=7YYOGW^@CZ&>
M=6+F:B=`HK%29:+/H]\&5D9;\""45ET@0S929-??T_'2VB%P-E!Y$?`B$?WI
M\'"GCZB?8@]C'V0OK,__9D_#;\G?O$]GGVBO:;]JS_]KWZVOKK^OSUR?EW^I
MS\JO_\N_\"`7`$7!`%#?,O*!)^#Z="909=YP1B/_4S=0-M/[-U!P\7>4@;&_
MPB^1%;8U_G/P8/!`WO*V_[@/J:^JO_^KS\FOQR_(/\E/S/_.#]B?#^`_F$L0
M\.GP;&1N)_L68#4C;1+0TG_3CY$&$Q#]Z?!B$W!&G]<?V"_9/]I/_][OW&_=
M?]Z/XC_C3_(/Z:__ZK_KS^S?[>_N__`/\1_ZG^OS/^%J4Q8Q9#A/YN_4E]_0
M5)4`(4!PL%XP()7Q@D&^9.CL78]>G[#QM6!VT7+_1<*VLM6B1<`1<#33(?'T
M___V#_<?`<\"W[XN^,_YW_KOI_O__0\2DW%U10!KME#_"H\+GPRO$#\13Q)?
M$V\4?V_]?_Z/_Y^Y=&9PT#<`8?P@(K8P.T"BH'YP-F`GL/\-;PY_-`:U,C?P
MZ,`$4-!@_B(TP$7!MI#1-[7%"<,G8?<%;P9_7LQ41=`6[Q?_&0__&A\;+Q_/
M'4TE([FP'C\?3_\IKR%ON5;1,S2`MH$HF`DAY[$`)V$*0B!U.J`CXZ9`Y[6@
M1:`T@&UP)S$\`2-`_RK01=#0$20_)4_H%:6`EGS_+9\NKR^_,,\QWS+O'A\U
M?_W!`"B5\4`O03]"3T-?1&__17]&CT>?-;\VSS??N70\T7\\1#UO/G]]Y**0
M"+#H@&[B;:*1*2!V`5#0L.7!Z^AP?G%G)S%)._$ZH%E@_C])WTKO2_]-#TX?
M4K]0/_]13U)?4V]4?V2/7"]=/U9__U>/#X]>_V`/9S]B+V,_;S^+95]4WT31
M$'!E;SQB\'-W964)<`D#/026`.O1X`FB9="0:CM0*/$_\?\(\VI/:U]]Y-&`
M<3#04-'2_[8`(P`)X#FA9V]H?VF/;1__;B]RSW!/<5]R;=&Q?.]]__]_#X`?
M@2^"/X-/A%]R;W-_KW2/B0]Y[VP*8EH`:W>0/F8K@`$@(\#/@-)0(&[UT1!L
MMH!GIE%V((N`!''_/^%;7X>/B)^)KXJ_CU^,W_^-[X[_D`^1'Z"?F#^93Y*/
M_Y.?;%^;#YP?HT^>/Y]/JT_SH6^B?R!9S\#5T,_`U9#X22=M%F(CD`CSJP!V
M0/QH>2.0U9`[T*=QTD-;,/`N(#TIHX^DGZ6OIK__I\^HWZGOJO^L#ZT?KB^]
M3_^P3Z+?M8^VG[>ONS^\3\-_W[YOOW_(_\&?L0]"6E+#K__$O\7/QM_'[\R/
M,R\T/\N__]6?S=_"[]!?T6_2?]./U)__W#_*7]@_X;_:7]MOM_^Y#_VZ%5_K
M#^P?[.K<?]V/WI__WZ_@O^5?XM_C[^3_Y@_G'P?P?^D_N<I'1$%L9V,%`+2!
M;7,M.7$$T&W[*+#RT6>64/UA[?_O#_`?__$O\C_VW_1?]6_V?_>/^)\O`._Z
MO_O/_-I`_5)S+L!S;W5R8V5)H9:0_BZ6\?YO_W\`CP&?`J\'3W\$SP7?!N\'
M_PD/$>\J4SR*0==&:'OP9CTB*R!@='`Z+R\.'P\B+SO]HOV@;AW3(P!)H"]G
M"R<`_+PB%QQI96QD#0J29B)P*,)[2%E0@$523$E.2R`=;V<>?Q^/()Q]?1?!
M(G!R`G,+`%QC9C%<=?^5X!@X)`\E'R8O_-H0_Q41TRW/%1XY,A!A01.`#V__
M$'\1CPK/"]\:%]=2,[@4B-<U4Q2/-,8W,2)0,7T8$;$U?V<R-%6Q-:TV'%'/
M.R$7.2YX%$`S-A4O%C__%T\YANSO16_M+S'?,N\S__\U#[FO$G\3CSE?03]"
M3T-?_PS__9]'GTBO2;]-3TY?3V__UJ]1'U(O4S\-_P\/5=]6[_]7_UD/6A];
M+U#O7;]G'QQ/_QU?*L\KWR"/(9\BKR._;:__;K]OSR?_*0]SOW3/==\M3_\N
M7R]O,'\QCV)_8X]*?TN/GS;?-^\X_SH/.Q\Q,&O!`"]"3$]#2U%5^$]418)_
MB2\\'XY_A"?&-6A!B^!/1%F`[8"0"Y`_/5$W@@%(5$U,!660?93P`!\`1Q`!
M````'@```&T`90!S`',`80!G`&4`+P!R`&8`8P`X`#(`,@```````P`F````
M```#`#8```````,`WC_I_0```P#Q/PD$```#`/T_Y`0``!\`<``!````6```
M`%L`00!L`&<`;P!R`&D`=`!H`&T`<P!=`"``0P!O`&P`;`!I`&0`:0!N`&<`
M(`!A`&<`80!I`&X`<P!T`"``<`!O`&P`>0!G`&\`;@`@`',`;P!U`'`````+
M`/(0`0```!\`\Q`!````;````%(`10`E`#,`00`@`%L`00!L`&<`;P!R`&D`
M=`!H`&T`<P!=`"``0P!O`&P`;`!I`&0`:0!N`&<`(`!A`&<`80!I`&X`<P!T
M`"``<`!O`&P`>0!G`&\`;@`@`',`;P!U`'``+@!%`$T`3`````L`]!``````
M"P#U$``````+`/80``````(!1P`!````,@```&,]55,[83U-0TD[<#UM<V9T
M.VP]0U)$+4U31RTP,BTP,#$R,#4R,30U,#%:+34W-3`````"`?D_`0```%$`
M````````W*=`R,!"$!JTN0@`*R_A@@$`````````+T\]34E#4D]33T94+T]5
M/4Y/4E1(04U%4DE#02]#3CU214-)4$E%3E13+T-./3,V-CDQ.``````?`/@_
M`0```!H```!-`&D`=`!C`&@`(`!7`&$`;`!K`&4`<@``````'P`X0`$````.
M````,P`V`#8`.0`Q`#@```````(!^S\!````40````````#<IT#(P$(0&K2Y
M"``K+^&"`0`````````O3SU-24-23U-/1E0O3U4]3D]25$A!345224-!+T-.
M/5)%0TE0245.5%,O0TX],S8V.3$X`````!\`^C\!````&@```$T`:0!T`&,`
M:``@`%<`80!L`&L`90!R```````?`#E``0````X````S`#8`-@`Y`#$`.```
M````0``',/125DD$7\`!0``(,,SCQ?P)7\`!'P`:``$````2````20!0`$T`
M+@!.`$\`5`!%```````?`#<``0```&````!2`$4`.@`@`%L`00!L`&<`;P!R
M`&D`=`!H`&T`<P!=`"``0P!O`&P`;`!I`&0`:0!N`&<`(`!A`&<`80!I`&X`
M<P!T`"``<`!O`&P`>0!G`&\`;@`@`',`;P!U`'`````?`#T``0````H```!2
M`$4`.@`@```````?`!T.`0```%@```!;`$$`;`!G`&\`<@!I`'0`:`!M`',`
M70`@`$,`;P!L`&P`:0!D`&D`;@!G`"``80!G`&$`:0!N`',`=``@`'``;P!L
M`'D`9P!O`&X`(`!S`&\`=0!P````'P`U$`$```"H````/``Y`#``1@!$`$8`
M0P!%`#$`0P!#`#``,@!"`#$`-``W`$(`-``Y`#0`.`!!`#$`1@`Q`#<`0P!#
M`#$`.``R`$8`,0`W`#8`.`!&`#``0`!C`'(`9``M`&T`<P!G`"T`,``R`"X`
M;@!O`'(`=`!H`&$`;0!E`'(`:0!C`&$`+@!C`&\`<@!P`"X`;0!I`&,`<@!O
M`',`;P!F`'0`+@!C`&\`;0`^````"P`I```````+`",```````,`!A#"7-)X
M`P`'$,L&```#`!`0``````,`$1`!````'@`($`$```!E````1D]24TM%3$54
M04Q!3DE-051%1$U/1$5,4RQ(3U=!0D]55%1(15=!64A!3$8M3$E&12A)5$A)
M3DLI1$E$250_04]/0D)&3U)42$5%3E1)4D5-3T1%3"Q!3D1)3D1)5DE$24%,
M3P`````"`7\``0```%0````\.3!&1$9#13%#0S`R0C$T-T(T.30X03%&,3=#
M0S$X,D8Q-S8X1C!`8W)D+6US9RTP,BYN;W)T:&%M97)I8V$N8V]R<"YM:6-R
-;W-O9G0N8V]M/@#L]@==
`
end
|
