Código:
//==============================================================================
// mundano.
// motor de multimedios.
//.
// copyright (c) 2005-2009 marco Antonio Alvarado Pérez.
//.
// mchoque, pas (ch_).
// detecta colisiones entre gráficos.
//==============================================================================
// notas.
//.
// los algoritmos están basados en el libro:
// * real-time collision detection.
//==============================================================================
{$include mdefine, inc}.
Unit mchoque.
Interface.
//------------------------------------------------------------------
Uses.
// mundano:
Mdepura.
Marreglo.
Mcomun.
Mcalculo.
Mgráfico.
// Delphi:
{$ifdef cmp_delphi}.
{$ifdef plt_windows}.
Math.
{$endif}.
{$endif}.
// free pascal compiler:
{$ifdef cmp_fpc}.
{$ifdef plt_windows}.
{$endif}.
{$ifdef plt_unix}.
{$endif}.
{$ifdef plt_dos}.
{$endif}.
{$endif}.
//------------------------------------------------------------------
Type.
//.
// esferas (bounding Spheres).
Ch_resfera = récord.
C: gr_rvector3d; // centro.
R: single; // radio.
End.
//.
// cajas alineadas al eje (axis-aligned bounding boxes, ab).
//.
// *------------ *------------ -.
// | | | | | |.
// | | | | | | | |.
// | | |<----+---->| | *---->|.
// | | | | | | |.
// | | | v | | |.
// -* - -.
// cajaeje1 cajaeje2 cajaeje3.
//.
Ch_rcajaeje1 = récord.
Menor, mayor: gr_rvector3d; // punto menor y punto mayor.
End.
Ch_rcajaeje2 = récord.
Menor: gr_rvector3d; // punto menor.
D: gr_rvector3d; // diámetro.
End.
Ch_rcajaeje3 = récord.
C: gr_rvector3d; // centro.
R: gr_rvector3d; // radio.
End.
//.
// cajas de orientación libre (oriented bounding boxes, ob).
Ch_arejescajalibre = array [0.2] of gr_rvector3d.
Ch_rcajalibre = récord.
C: gr_rvector3d; // centro.
U: ch_arejescajalibre; // ejes locales.
R: gr_rvector3d; // radios sobre cada eje.
End.
//.
// politopues de orientación discretea (discrete-orientation polytopes, k-dop).
Ch_rpolitopo = récord.
Menores, mayores: ar_adsingle; // distancias desde el origen sobre los.
// ejes 0 a 3.
End.
//.
// capsulas (sphere-swept volumes, sv).
Ch_rcapsula = packed récord.
A, b: gr_rvector3d; // inicio y fin del segmento.
R: single; // radio.
End.
//.
// segmentos.
Procedure ch_mascercapuntosegmento (const p1, s1, s2: gr_rvector3d.
Var t: single, VAR p: gr_rvector3d).
Function ch_mascercasegmentosegmento (const sa1, sa2, sb1, sb2: gr_rvector3d.
Var, t: single, VAR p1, p2: gr_rvector3d): single.
Function ch_distanciacuadradapuntosegmento (const, s1, s2: gr_rvector3d):
Single.
Function ch_distanciacuadradasegmentosegmento (const sa1, sa2, sb1, sb2:
Gr_rvector3d): single.
//.
// planos.
Function ch_mascercapuntoplano (const p1: gr_rvector3d, const p2: gr_rplano3d.
Var p: gr_rvector3d, planonormalizado: bolean = false): single.
Function ch_distanciapuntoplano (const p1: gr_rvector3d, const p2: gr_rplano3d.
Planonormalizado: bolean = false): single.
//.
// triángulos.
Function ch_puntoentriángulo (const, t1, t2, t3: gr_rvector3d): bolean.
Procedure ch_mascercapuntotriángulo (const p1, t1, t2, t3: gr_rvector3d.
Var p: gr_rvector3d).
//.
// rectángulos.
Function ch_mascercapuntorectángulo (const p1: gr_rvector3d, const r:
Gr_rrectánguloaxial3d, VAR p: gr_rvector3d): single.
Function ch_distanciacuadradapuntorectángulo (const p1: gr_rvector3d, const r:
Gr_rrectánguloaxial3d): single.
//.
// tetrahedro.
Procedure ch_mascercapuntotetrahedro (const p1, p1, p2, p3, p4:
Gr_rvector3d, VAR p: gr_rvector3d).
//.
// esferas.
Function ch_creaesfera (const c: ch_rcajaeje1): ch_resfera, overload.
Function ch_creaesfera (const e: ch_resfera, const p: gr_rvector3d): ch_resfera.
Overload.
Function ch_creaesferacajaeje (const puntos: gr_adrvector3d): ch_resfera.
Function ch_creaesferaritter(const puntos: gr_adrvector3d): ch_resfera.
Function ch_creaesferaeigen(const puntos: gr_adrvector3d): ch_resfera.
Function ch_creaesferarittereigen(const puntos: gr_adrvector3d): ch_resfera.
Function ch_creaesferaritteriterativa (const puntos: gr_adrvector3d):
Ch_resfera.
Function ch_esferaenplano (const e: ch_resfera, const p: gr_rplano3d): bolean.
//.
// cajas alineadas al eje (axis-aligned bounding boxes, ab).
Function ch_creacajaeje1: ch_rcajaeje1, overload.
Function ch_creacajaeje1(const p: gr_rvector3d): ch_rcajaeje1, overload.
Function ch_creacajaeje1(const p1, p2: gr_rvector3d): ch_rcajaeje1, overload.
Function ch_creacajaeje3(const c, r: gr_rvector3d): ch_rcajaeje3, overload.
Function ch_une (const c: ch_rcajaeje1, const p: gr_rvector3d):
Ch_rcajaeje1, overload.
Function ch_une (const c1, c2: ch_rcajaeje1): ch_rcajaeje1, overload.
Function ch_expande (const c: ch_rcajaeje1, a: single): ch_rcajaeje1.
Function ch_volumen(const c: ch_rcajaeje1): single.
Function ch_ejemayor(const c: ch_rcajaeje1): integer.
Function ch_transforma (const t: gr_rtransformación, const c: ch_rcajaeje1):
Ch_rcajaeje1, overload.
Function ch_actualizacajaeje1(const c: ch_rcajaeje1, const m: gr_rmatriz3x3.
Const t: gr_rvector3d): ch_rcajaeje1, overload.
Function ch_actualizacajaeje3(const c: ch_rcajaeje3, const m: gr_rmatriz3x3.
Const t: gr_rvector3d): ch_rcajaeje3, overload.
Procedure ch_puntosmasseparadoscajaeje (VAR menor, mayor: integer, const puntos:
Gr_adrvector3d).
Procedure ch_mascercapuntocajaeje (const p1: gr_rvector3d, const c:
Ch_rcajaeje1, VAR p: gr_rvector3d).
Function ch_distanciacuadradapuntocajaeje (const p1: gr_rvector3d, const c:
Ch_rcajaeje1): single.
//.
// cajas de orientación libre (oriented bounding boxes, ob).
Function ch_mascercapuntocajalibre (const p1: gr_rvector3d, const c:
Ch_rcajalibre, VAR p: gr_rvector3d): single.
Function ch_distanciacuadradapuntocajalibre (const p1: gr_rvector3d, const c:
Ch_rcajalibre): single.
//.
// politopues de orientación discretea (discrete-orientation polytopes, k-dop).
Function ch_creapolitopo8: ch_rpolitopo, overload.
Function ch_creapolitopo8(const puntos: gr_adrvector3d): ch_rpolitopo.
Overload.
//.
// pruebas de contenido (c), intersección (i) y traslapamiento (t):
//.
// c.
// u.
// a.
// t TD de p.
// s s r r re r c a p p o.
// e e i i i i i l c o o l.
// g g a ap l l e i a l l i.
// p m l p mp n n nl a í s n l p í i h.
// u e e í r l el g g ga te n f ce CI s g te e.
// n n n n a da u u un e de e a ab u o o d.
// te t2 te e y n in l2 l lo r r r jd jr l n p r.
// o od o a o o o od o os o o a After Effects a o o o.
// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+.
// punto | | | | | | | |c |c | | | | | | | |c | |t |.
// | | | | | | | | | | | | | | | | | | | |.
// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+.
// segmento | |t | | | | | | | | | | | | | | | | | |.
// 2d | | | | | | | | | | | | | | | | | | | |.
// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+.
// segmento | | | | | |i | | |i |i | |i | |t | | | | |i |.
// | | | | | | | | | | | | | | | | | | | |.
// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+.
// línea | | | | | | | | |i | |i | | | | | | | | |.
// | | | | | | | | | | | | | | | | | | | |.
// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+.
// rayo | | | | | | | | |i | | | |it|i | | | | | |.
// | | | | | | | | | | | | | | | | | | | |.
// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+.
// plano | | | | | |i | | | | | | | |t | | | | | |.
// | | | | | | | | | | | | | | | | | | | |.
// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+.
// triángulo | | | | | | | | |t | | | | |t | | | | | |.
// | | | | | | | | | | | | | | | | | | | |.
// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+.
// esfera | | | | | |t |t | |t | | | |t |t |t |t |t | | |.
// | | | | | | | | | | | | | | | | | | | |.
// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+.
// caja |c | | | | |t | | | | | | | |t | | | | | |.
// alienada | | | | | | | | | | | | | | | | | | | |.
// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+.
// caja | | | | | |t | | | | | | | | |t | | | | |.
// libre | | | | | | | | | | | | | | | | | | | |.
// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+.
// capsula | | | | | | | | | | | | | | | |t | | | |.
// | | | | | | | | | | | | | | | | | | | |.
// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+.
// politopo | | | | | | | | | | | | | | | | | |t | |.
// | | | | | | | | | | | | | | | | | | | |.
// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+.
//.
Function ch_contienepuntotriángulo2dcontrareloj(const, t1, t2, t3:
Gr_rvector2d): bolean.
Function ch_contienepuntotriángulo2d(const, t1, t2, t3: gr_rvector2d):
Bolean.
Function ch_contienepuntotriángulocontrareloj(const p: gr_rvector3d, t1, t2.
T3: gr_rvector3d): bolean.
Function ch_contienepuntopoligono (const p1: gr_rvector3d, const p2:
Gr_rpoligono3d): bolean.
Function ch_traslapapuntopolihedro (const p: gr_rvector3d, const planos:
Gr_adrplano3d, planonormalizado: bolean = false): bolean.
Function ch_traslapasegmento2dsegmento2d(const sa1, sa2, sb1, sb2:
Gr_rvector2d, VAR t: single, VAR p: gr_rvector2d): bolean.
Function ch_intersecasegmentoplano (const s1, s2: gr_rvector3d, const p1:
Gr_rplano3d, VAR t: single, VAR p: gr_rvector3d): bolean.
Function ch_intersecasegmentotriángulo (const s1, s2, t1, t2, t3: gr_rvector3d.
Var u, v, w, t: single): bolean.
Function ch_intersecasegmentotriánguloplanos(const s1, s2: gr_rvector3d, const.
T1: gr_rtriánguloplanar3d, VAR u, v, w, t: single, VAR s: gr_rvector3d):
Bolean.
Function ch_traslapasegmentocajaeje1(const s1, s2: gr_rvector3d, const c:
Ch_rcajaeje1): bolean.
Function ch_intersecasegmentocilindro (const s1, s2, c1, c2: gr_rvector3d, r:
Single, VAR t: single): bolean.
Function ch_intersecasegmentopolihedro (const s1, s2: gr_rvector3d, const planos:
Gr_adrplano3d, VAR tprimero, tultimo: single): bolean.
Function ch_intersecalineatriángulo (const l1, l2, t1, t2, t3: gr_rvector3d, VAR.
U, v, w: single): bolean.
Function ch_intersecalineacuadrilaterocontrareloj(const l1, l2, c1, c2, c3, c4:
Gr_rvector3d, VAR p: gr_rvector3d): bolean.
Function ch_intersecarayotriángulo (const o, d, t1, t2, t3: gr_rvector3d, VAR t.
U, v: single): bolean.
Function ch_intersecarayoesfera (const o: gr_rvector3d, const d: gr_rvector3d.
Const e: ch_resfera, VAR t: single, VAR p: gr_rvector3d): bolean.
Function ch_traslaparayoesfera (const o: gr_rvector3d, const d: gr_rvector3d.
Const e: ch_resfera): bolean.
Function ch_intersecarayocajaeje1(const o: gr_rvector3d, const d: gr_rvector3d.
Const c: ch_rcajaeje1, VAR tmenor: single, VAR p: gr_rvector3d): bolean.
Function ch_intersecaplanoplano (const p1, p2: gr_rplano3d, VAR p: gr_rvector3d.
Var d: gr_rvector3d): bolean.
Function ch_intersecaplanoplanoplano (const p1, p2, p3: gr_rplano3d, VAR p:
Gr_rvector3d): bolean.
Function ch_traslapaplanocajaeje3(const p: gr_rplano3d, const c: ch_rcajaeje3):
Bolean.
Function ch_intersecatriángulotriángulo (const ta1, ta2, ta3, tb1, tb2, tb3:
Gr_rvector3d): bolean.
Function ch_traslapatriángulocajaeje3(const t1, t2, t3: gr_rvector3d, const c:
Ch_rcajaeje3): bolean.
Function ch_traslapaesferaplano (const e: ch_resfera, const p: gr_rplano3d):
Bolean.
Function ch_traslapaesferamedioplano (const e: ch_resfera, const p:
Gr_rplano3d): bolean.
Function ch_traslapaesferatriángulo (const e: ch_resfera, const t1, t2, t3:
Gr_rvector3d, VAR p: gr_rvector3d): bolean.
Function ch_traslapaesferaesfera (const e1, e2: ch_resfera): bolean.
Function ch_traslapaesferacajaeje1(const e: ch_resfera, const c: ch_rcajaeje1):
Bolean, overload.
Function ch_traslapaesferacajaeje1(const e: ch_resfera, const c: ch_rcajaeje1.
Var p: gr_rvector3d): bolean, overload.
Function ch_traslapaesferacajalibre (const e: ch_resfera, const c:
Ch_rcajalibre, VAR p: gr_rvector3d): bolean.
Function ch_traslapaesferacapsula (const e: ch_resfera, const c: ch_rcapsula):
Bolean.
Function ch_traslapaesferapoligono (const e: ch_resfera, const p:
Gr_rpoligono3d): bolean.
Function ch_contienecajaeje1punto (const c: ch_rcajaeje1, const p:
Gr_rvector3d): bolean.
Function ch_traslapacajaeje1plano (const c: ch_rcajaeje1, const p: gr_rplano3d):
Bolean.
Function ch_traslapacajaeje1cajaeje1(const c1, c2: ch_rcajaeje1): bolean.
Function ch_traslapacajaeje2cajaeje2(const c1, c2: ch_rcajaeje2): bolean.
Function ch_traslapacajaeje3cajaeje3(const c1, c2: ch_rcajaeje3): bolean.
Function ch_traslapacajalibreplano (const c: ch_rcajalibre, const p:
Gr_rplano3d): bolean.
Function ch_traslapacajalibrecajalibre (const c1, c2: ch_rcajalibre): bolean.
Function ch_traslapacapsulacapsula (const c1, c2: ch_rcapsula): bolean.
Function ch_traslapapolitopopolitopo (const p1, p2: ch_rpolitopo): bolean.
Implementation.
//------------------------------------------------------------------
// segmentos.
//------------------------------------------------------------------
//------------------------------------------------------------------
Procedure ch_mascercapuntosegmento (.
Const p1, // punto.
S1, s2: gr_rvector3d; // puntos que limitan el segmento.
Var t: single; // posición del punto sobre el segmento.
Var p: gr_rvector3d // punto sobre el segmento, más cercano a p1).
Var.
Ab: gr_rvector3d.
Begin.
Ab := gr_resta (s2, s1).
T := gr_productopunto (gr_resta (p1, s1), ab)/gr_productopunto (ab, ab).
T := cc_limita (t, 0, 1).
P := gr_suma (s1, gr_multiplica (ab, t)).
End.
//------------------------------------------------------------------
Function ch_mascercasegmentosegmento (.
Const sa1, sa2, // puntos que limitan el segmento a.
Sb1, sb2: gr_rvector3d; // puntos que limitan el segmento b.
Var, t: single; // parámetros de los segmentos.
Var p1, p2: gr_rvector3d // puntos más cercanos.
): single; // distancia cuadrada entre s1(s) y s2(t).
Var.
D1, d2, r: gr_rvector3d.
A, f, c, b, d: single.
Begin.
D1 := gr_resta (sa2, sa1).
D2 := gr_resta (sb2, sb1).
R := gr_resta (sa1, sb1).
A := gr_productopunto (d1, d1).
E := gr_productopunto (d2, d2).
F := gr_productopunto (d2, r).
If (a <= gr_epsilon) and (e <= gr_epsilon) then.
Begin.
S := 0.
T := 0.
P1 := sa1.
P2 := sb1.
Result := gr_distanciacuadrada (p1, p2).
Exit.
End.
If a <= gr_epsilon then.
Begin.
S := 0.
T := f/e.
T := cc_limita (t, 0, 1).
End else.
Begin.
C := gr_productopunto (d1, r).
If e <= gr_epsilon then.
Begin.
T := 0.
S := cc_limita (-c/a, 0, 1).
End else.
Begin.
B := gr_productopunto (d1, d2).
D := a*e-b*b.
If d <> 0 then.
Begin.
S := cc_limita ((b*f-c*e)/d, 0, 1).
End else.
Begin.
S := 0.
End.
T := (b*s+f)/e.
If < 0 then.
Begin.
T := 0.
S := cc_limita (-c/a, 0, 1).
End else.
If > 1 then.
Begin.
T := 1.
S := cc_limita ((b-c)/a, 0, 1).
End.
End.
End.
P1 := gr_suma (sa1, gr_multiplica (d1, s)).
P2 := gr_suma (sb1, gr_multiplica (d2, t)).
Result := gr_distanciacuadrada (p1, p2).
End.
//------------------------------------------------------------------
Function ch_distanciacuadradapuntosegmento (.
Const, // punto.
S1, s2: gr_rvector3d // puntos que limitan el segmento.
): single.
Var.
Ab, ac, bc: gr_rvector3d.
E, f: single.
Begin.
Ab := gr_resta (s2, s1).
Ac := gr_resta (p, s1).
Bc := gr_resta (p, s2).
E := gr_productopunto (ac, ab).
If e <= 0 then.
Begin.
Result := gr_productopunto (ac, ac).
Exit.
End.
F := gr_productopunto (ab, ab).
If e >= f then.
Begin.
Result := gr_productopunto (bc, bc).
Exit.
End.
Result := gr_productopunto (ac, ac)-e*e/f.
End.
//------------------------------------------------------------------
Function ch_distanciacuadradasegmentosegmento (.
Const sa1, sa2, // puntos que limitan el segmento a.
Sb1, sb2: gr_rvector3d // puntos que limitan el segmento b.
): single.
Var.
S, t: single.
P1, p2: gr_rvector3d.
Begin.
Result := ch_mascercasegmentosegmento (sa1, sa2, sb1, sb2, t, p1, p2).
End.
//------------------------------------------------------------------
// planos.
//------------------------------------------------------------------
//------------------------------------------------------------------
Function ch_mascercapuntoplano (.
Const p1: gr_rvector3d.
Const p2: gr_rplano3d.
Var p: gr_rvector3d; // punto sobre el plano p2, más cercano a p1.
Planonormalizado: bolean.
): single; // distancia del punto más cercano al plano.
Begin.
If planonormalizado then.
Result := gr_productopunto (p2. N, p1)-p2. P else.
Result := (gr_productopunto (p2. N, p1)-p2. P)/gr_productopunto (p2. N, p2. N).
P := gr_resta (p1, gr_multiplica (p2. N, result)).
End.
//------------------------------------------------------------------
Function ch_distanciapuntoplano (.
Const p1: gr_rvector3d.
Const p2: gr_rplano3d.
Planonormalizado: bolean.
): single.
Begin.
If planonormalizado then.
Result := gr_productopunto (p2. N, p1)-p2. P else.
Result := (gr_productopunto (p2. N, p1)-p2. P)/gr_productopunto (p2. N, p2. N).
End.
//------------------------------------------------------------------
// triángulos.
//------------------------------------------------------------------
//------------------------------------------------------------------
Function ch_puntoentriángulo (.
Const, // punto.
T1, t2, t3: gr_rvector3d // puntos del triángulo.
): bolean.
Var.
U, v, w: single.
Begin.
Gr_baricentricas(t1, t2, t3, u, v, w).
Result := (v >= 0) and (w >= 0) and (v+w <= 1).
End.
//------------------------------------------------------------------
Procedure ch_mascercapuntotriángulo (.
Const p1, // punto.
T1, t2, t3: gr_rvector3d; // puntos del triángulo.
Var p: gr_rvector3d // punto en el triángulo, más cercano a p1).
Var.
Ab, ac, ap, bp, cp: gr_rvector3d.
D1, d2, d3, d4, d5, d6, v, w, va, vb, VC, d: single.
Begin.
Ab := gr_resta (t2, t1).
Ac := gr_resta (t3, t1).
Ap := gr_resta (p1, t1).
D1 := gr_productopunto (ab, ap).
D2 := gr_productopunto (ac, ap).
If (d1 <= 0) and (d2 <= 0) then.
Begin.
P := t1.
Exit.
End.
Bp := gr_resta (p1, t2).
D3 := gr_productopunto (ab, bp).
D4 := gr_productopunto (ac, bp).
If (d3 >= 0) and (d4 <= d3) then.
Begin.
P := t2.
Exit.
End.
Vc := d1*d4-d3*d2.
If (vc <= 0) and (d1 >= 0) and (d3 <= 0) then.
Begin.
V := d1/(d1-d3).
P := gr_suma (t1, gr_multiplica (ab, v)).
Exit.
End.
Cp := gr_resta (p1, t3).
D5 := gr_productopunto (ab, cp).
D6 := gr_productopunto (ac, cp).
If (d6 >= 0) and (d5 <= d6) then.
Begin.
P := t3.
Exit.
End.
Vb := d5*d2-d1*d6.
If (vb <= 0) and (d2 >= 0) and (d6 <= 0) then.
Begin.
W := d2/(d2-d6).
P := gr_suma (t1, gr_multiplica (ac, w)).
Exit.
End.
Va := d3*d6-d5*d4.
If (va <= 0) and (d4-d3 >= 0) and (d5-d6 >= 0) then.
Begin.
W := (d4-d3)/((d4-d3)+(d5-d6)).
P := gr_suma (t2, gr_multiplica (gr_resta (t3, t2), w)).
Exit.
End.
D := 1/(va+vb+vc).
V := vb*d.
W := VC*d.
P := gr_suma (t1, gr_suma (gr_multiplica (ab, v), gr_multiplica (ac, w))).
End.
//------------------------------------------------------------------
// rectángulos.
//------------------------------------------------------------------
//------------------------------------------------------------------
Function ch_mascercapuntorectángulo (.
Const p1: gr_rvector3d.
Const r: gr_rrectánguloaxial3d.
Var p: gr_rvector3d.
): single.
Var.
D: gr_rvector3d.
I: integer.
L: single.
Begin.
D := gr_resta (p1, r. C).
P := r. C.
For I := 0 todo 2 do.
Begin.
L := cc_limita (gr_productopunto (d, r. U[i]), -r. R. M[i], r. R. M[i]).
P := gr_suma (p, gr_multiplica (r. U[i], l)).
End.
D := gr_resta (p, p1).
Result := gr_productopunto (d, d).
End.
//------------------------------------------------------------------
Function ch_distanciacuadradapuntorectángulo (.
Const p1: gr_rvector3d.
Const r: gr_rrectánguloaxial3d.
): single.
Var.
P: gr_rvector3d.
Begin.
Result := ch_mascercapuntorectángulo (p1, r, p).
End.
//------------------------------------------------------------------
// tetrahedro.
//------------------------------------------------------------------
//------------------------------------------------------------------
Procedure ch_mascercapuntotetrahedro (.
Const p1.
P1, p2, p3, p4: gr_rvector3d.
Var p: gr_rvector3d).
Var.
Mejord, d: single.
Que: gr_rvector3d.
Begin.
P := p1.
Mejord := maxsingle.
If gr_puntofueraplano (p1, p1, p2, p3) then.
Begin.
Ch_mascercapuntotriángulo (p1, p1, p2, p3, que).
D := gr_productopunto (gr_resta (que, p1), gr_resta (que, p1)).
If d < mejord then.
Begin.
Mejord := d.
P := que.
End.
End.
If gr_puntofueraplano (p1, p1, p3, p4) then.
Begin.
Ch_mascercapuntotriángulo (p1, p1, p3, p4, que).
D := gr_productopunto (gr_resta (que, p1), gr_resta (que, p1)).
If d < mejord then.
Begin.
Mejord := d.
P := que.
End.
End.
If gr_puntofueraplano (p1, p1, p4, p2) then.
Begin.
Ch_mascercapuntotriángulo (p1, p1, p4, p2, que).
D := gr_productopunto (gr_resta (que, p1), gr_resta (que, p1)).
If d < mejord then.
Begin.
Mejord := d.
P := que.
End.
End.
If gr_puntofueraplano (p1, p2, p4, p3) then.
Begin.
Ch_mascercapuntotriángulo (p1, p2, p4, p3, que).
D := gr_productopunto (gr_resta (que, p1), gr_resta (que, p1)).
If d < mejord then.
Begin.
// mejord := d.
P := que.
End.
End.
End.
//------------------------------------------------------------------
// esferas.
//------------------------------------------------------------------
//------------------------------------------------------------------
Function ch_creaesfera (.
Const c: ch_rcajaeje1.
): ch_resfera.
Begin.
Result. C := gr_suma (.
Gr_multiplica (c. Menor, 0.5).
Gr_multiplica (c. Mayor, 0.5)).
Result. R := gr_distancia (result. C, c. Mayor).
End.
//------------------------------------------------------------------
Function ch_creaesfera (.
Const e: ch_resfera.
Const p: gr_rvector3d.
): ch_resfera.
Var.
D2, d, k: single.
Begin.
D2 := gr_distanciacuadrada (por ejemplo C).
If d2 > e. R*e. R then.
Begin.
D := sqrt(d2).
Result. R := (e. R+d)*0.5.
K := (result. R-e. R)/d.
Result. C := gr_suma (e. C, d*k).
End.
End.
//------------------------------------------------------------------
Function ch_creaesferacajaeje (.
Const puntos: gr_adrvector3d.
): ch_resfera.
Var.
Menor, mayor: integer.
Begin.
Ch_puntosmasseparadoscajaeje (menor, mayor, puntos).
Result. C := gr_multiplica (gr_suma (puntos[menor], puntos[mayor]), 0.5).
Result. R := gr_distancia (puntos[mayor], result. C).
End.
//------------------------------------------------------------------
Function ch_creaesferaritter(.
Const puntos: gr_adrvector3d.
): ch_resfera.
Var.
Ipunto: integer.
Begin.
Result := ch_creaesferacajaeje (puntos).
For ipunto := 0 todo high(puntos) do.
Result := ch_creaesfera (result, puntos[ipunto]).
End.
//------------------------------------------------------------------
Function ch_creaesferaeigen(.
Const puntos: gr_adrvector3d.
): ch_resfera.
Var.
Vaya, v: gr_rmatriz3x3.
E: gr_rvector3d.
Cmayor: integer.
Fmayor, emayor: single.
Imenor, imayor: integer.
Pmenor, pmayor: gr_rvector3d.
D: single.
Begin.
Vaya := gr_creamatriz3x3covariante (puntos).
Gr_jacobiano (m, v).
Cmayor := 0.
Emayor := abs(m. M11).
Fmayor := abs(m. M22).
If fmayor > emayor then cmayor := 1.
Fmayor := abs(m. M33).
If fmayor > emayor then cmayor := 2.
E.x := v. M[0,cmayor].
E. Y := v. M[1,cmayor].
E. Z := v. M[2,cmayor].
Gr_puntosextremosendireccion(e, puntos, imenor, imayor).
Pmenor := puntos[imenor].
Pmayor := puntos[imayor].
D := gr_distancia (pmayor, pmenor).
Result. R := d*0.5.
Result. C := gr_multiplica (gr_suma (pmenor, pmayor), 0.5).
End.
//------------------------------------------------------------------
Function ch_creaesferarittereigen(.
Const puntos: gr_adrvector3d.
): ch_resfera.
Var.
Ipunto: integer.
Begin.
Result := ch_creaesferaeigen(puntos).
For ipunto := 0 todo high(puntos) do.
Result := ch_creaesfera (result, puntos[ipunto]).
End.
//------------------------------------------------------------------
Function ch_creaesferaritteriterativa (.
Const puntos: gr_adrvector3d.
): ch_resfera.
Var.
E: ch_resfera.
I, k: integer.
Begin.
Result := ch_creaesferaritter(puntos).
E := result.
For k := 0 todo 7 do.
Begin.
E. R := e. R*0.95.
For I := 0 todo high(puntos) do.
Begin.
J := trunc(cc_aleatorio (i+1, high(puntos))).
Gr_intercambia (puntos[i], puntos[j]).
Ch_creaesfera (e, puntos[i]).
End.
If e. R < result. R then result := e.
End.
End.
//------------------------------------------------------------------
Function ch_esferaenplano (.
Const e: ch_resfera; // esfera.
Const p: gr_rplano3d // plano.
): bolean.
Begin.
Result := gr_productopunto (e. C, p. N)-p. P < -e. R.
End.
//------------------------------------------------------------------
// cajas alineadas al eje (axis-aligned bounding boxes, ab).
//------------------------------------------------------------------
//------------------------------------------------------------------
Function ch_creacajaeje1: ch_rcajaeje1.
Begin.
Result. Menor := gr_creavector3d(infinity, infinity, infinity).
Result. Mayor := gr_creavector3d(-infinity, -infinity, -infinity).
End.
//------------------------------------------------------------------
Function ch_creacajaeje1(.
Const p: gr_rvector3d.
): ch_rcajaeje1.
Begin.
Result. Menor := p.
Result. Mayor := p.
End.
//------------------------------------------------------------------
Function ch_creacajaeje1(.
Const p1, p2: gr_rvector3d.
): ch_rcajaeje1.
Begin.
Result. Menor := gr_creavector3d(.
Cc_menor(p1.x, p2.x).
Cc_menor(p1. Y, p2. Y).
Cc_menor(p1. Z, p2. Z)).
Result. Mayor := gr_creavector3d(.
Cc_mayor(p1.x, p2.x).
Cc_mayor(p1. Y, p2. Y).
Cc_mayor(p1. Z, p2. Z)).
End.
//------------------------------------------------------------------
Function ch_creacajaeje3(.
Const c, r: gr_rvector3d.
): ch_rcajaeje3.
Begin.
Result. C := c.
Result. R := r.
End.
//------------------------------------------------------------------
Function ch_une (.
Const c: ch_rcajaeje1.
Const p: gr_rvector3d.
): ch_rcajaeje1.
Begin.
Result. Menor.x := cc_menor(c. Menor.x, p.x).
Result. Menor. Y := cc_menor(c. Menor. Y, p. Y).
Result. Menor. Z := cc_menor(c. Menor. Z, p. Z).
Result. Mayor.x := cc_mayor(c. Mayor.x, p.x).
Result. Mayor. Y := cc_mayor(c. Mayor. Y, p. Y).
Result. Mayor. Z := cc_mayor(c. Mayor. Z, p. Z).
End.
//------------------------------------------------------------------
Function ch_une (.
Const c1, c2: ch_rcajaeje1.
): ch_rcajaeje1.
Begin.
Result. Menor.x := cc_menor(c1. Menor.x, c2. Menor.x).
Result. Menor. Y := cc_menor(c1. Menor. Y, c2. Menor. Y).
Result. Menor. Z := cc_menor(c1. Menor. Z, c2. Menor. Z).
Result. Mayor.x := cc_mayor(c1. Mayor.x, c2. Mayor.x).
Result. Mayor. Y := cc_mayor(c1. Mayor. Y, c2. Mayor. Y).
Result. Mayor. Z := cc_mayor(c1. Mayor. Z, c2. Mayor. Z).
End.
//------------------------------------------------------------------
Function ch_expande (.
Const c: ch_rcajaeje1.
A: single.
): ch_rcajaeje1.
Begin.
Result. Menor := gr_resta (c. Menor, gr_creavector3d(a, a)).
Result. Mayor := gr_suma (c. Mayor, gr_creavector3d(a, a)).
End.
//------------------------------------------------------------------
Function ch_volumen(.
Const c: ch_rcajaeje1.
): single.
Var.
D: gr_rvector3d.
Begin.
D := gr_resta (c. Mayor, c. Menor).
Result := d.x*d. Y*d. Z.
End.
//------------------------------------------------------------------
Function ch_ejemayor(.
Const c: ch_rcajaeje1.
): integer.
Var.
D: gr_rvector3d.
Begin.
D := gr_resta (c. Mayor, c. Menor).
If (d.x > d. Y) and (d.x > d. Z) then result := gr_eje_x else.
If (d. Y > d. Z) then result := gr_eje_y else.
Result := gr_eje_z.
End.
//------------------------------------------------------------------
Function ch_transforma (.
Const t: gr_rtransformación.
Const c: ch_rcajaeje1.
): ch_rcajaeje1.
Begin.
Result := ch_creacajaeje1(gr_transforma (gr_creavector3d(c. Menor.x, c. Menor. Y.
C. Menor. Z), t)).
Result := ch_une (result, gr_transforma (gr_creavector3d(c. Mayor.x, c. Menor. Y.
C. Menor. Z), t)).
Result := ch_une (result, gr_transforma (gr_creavector3d(c. Menor.x, c. Mayor. Y.
C. Menor. Z), t)).
Result := ch_une (result, gr_transforma (gr_creavector3d(c. Menor.x, c. Menor. Y.
C. Mayor. Z), t)).
Result := ch_une (result, gr_transforma (gr_creavector3d(c. Menor.x, c. Mayor. Y.
C. Mayor. Z), t)).
Result := ch_une (result, gr_transforma (gr_creavector3d(c. Mayor.x, c. Mayor. Y.
C. Menor. Z), t)).
Result := ch_une (result, gr_transforma (gr_creavector3d(c. Mayor.x, c. Menor. Y.
C. Mayor. Z), t)).
Result := ch_une (result, gr_transforma (gr_creavector3d(c. Mayor.x, c. Mayor. Y.
C. Mayor. Z), t)).
End.
//------------------------------------------------------------------
Function ch_actualizacajaeje1(.
Const c: ch_rcajaeje1.
Const m: gr_rmatriz3x3.
Const t: gr_rvector3d.
): ch_rcajaeje1.
Var.
I, j: integer.
E, f: single.
Begin.
For I := 0 todo 2 do.
Begin.
Result. Menor. M[i] := t. M[i].
Result. Mayor. M[i] := t. M[i].
For := 0 todo 2 do.
Begin.
E := m. M[i,j]*c. Menor. M[j].
F := m. M[i,j]*c. Mayor. M[j].
If e < f then.
Begin.
Result. Menor. M[i] := result. Menor. M[i]+e.
Result. Mayor. M[i] := result. Mayor. M[i]+f.
End else.
Begin.
Result. Menor. M[i] := result. Menor. M[i]+f.
Result. Mayor. M[i] := result. Mayor. M[i]+e.
End.
End.
End.
End.
//------------------------------------------------------------------
Function ch_actualizacajaeje3(.
Const c: ch_rcajaeje3.
Const m: gr_rmatriz3x3.
Const t: gr_rvector3d.
): ch_rcajaeje3.
Var.
I, j: integer.
Begin.
For I := 0 todo 2 do.
Begin.
Result. C. M[i] := t. M[i].
Result. R. M[i] := 0.
For := 0 todo 2 do.
Begin.
Result. C. M[i] := result. C. M[i]+m. M[i,j]*c. C. M[j].
Result. R. M[i] := result. R. M[i]+abs(m. M[i,j])*c. R. M[j].
End.
End.
End.
//------------------------------------------------------------------
Procedure ch_puntosmasseparadoscajaeje (.
Var menor, mayor: integer.
Const puntos: gr_adrvector3d).
Var.
Menorx, mayorx.
Menory, mayory.
Menorz, mayorz: integer.
Ipunto: integer.
D2x, d2y, d2z: single.
Begin.
Menorx := 0.
Mayorx := 0.
Menory := 0.
Mayory := 0.
Menorz := 0.
Mayorz := 0.
For ipunto := 0 todo high(puntos) do.
Begin.
If puntos[ipunto].x < puntos[menorx].x then menorx := ipunto.
If puntos[ipunto].x > puntos[mayorx].x then mayorx := ipunto.
If puntos[ipunto]. Y < puntos[menory]. Y then menory := ipunto.
If puntos[ipunto]. Y > puntos[mayory]. Y then mayory := ipunto.
If puntos[ipunto]. Z < puntos[menorz]. Z then menorz := ipunto.
If puntos[ipunto]. Z > puntos[mayorz]. Z then mayorz := ipunto.
End.
D2x := gr_distanciacuadrada (puntos[menorx], puntos[mayorx]).
D2y := gr_distanciacuadrada (puntos[menory], puntos[mayory]).
D2z := gr_distanciacuadrada (puntos[menorz], puntos[mayorz]).
Menor := menorx.
Mayor := mayorx.
If (d2y > d2x) and (d2y > d2z) then.
Begin.
Menor := menory.
Mayor := mayory.
End else.
If (d2z > d2x) and (d2z > d2y) then.
Begin.
Menor := menorz.
Mayor := mayorz.
End.
End.
//------------------------------------------------------------------
Procedure ch_mascercapuntocajaeje (.
Const p1: gr_rvector3d.
Const c: ch_rcajaeje1.
Var p: gr_rvector3d).
Var.
I: integer.
Menor, mayor: single.
Begin.
For I := 0 todo 2 do.
Begin.
Menor := c. Menor. M[i].
Mayor := c. Mayor. M[i].
P. M[i] := cc_limita (p1. M[i], menor, mayor).
End.
End.
//------------------------------------------------------------------
Function ch_distanciacuadradapuntocajaeje (.
Const p1: gr_rvector3d.
Const c: ch_rcajaeje1.
): single.
Var.
I: integer.
Menor, mayor: single.
Begin.
Result := 0.
For I := 0 todo 2 do.
Begin.
Menor := c. Menor. M[i].
Mayor := c. Mayor. M[i].
If menor > mayor then cm_intercambia (menor, mayor).
If p1. M[i] < menor then result := result+(menor-p1. M[i])*(menor-p1. M[i]).
If p1. M[i] > mayor then result := result+(p1. M[i]-mayor)*(p1. M[i]-mayor).
End.
End.
//------------------------------------------------------------------
// cajas de orientación libre (oriented bounding boxes, ob).
//------------------------------------------------------------------
//------------------------------------------------------------------
Function ch_mascercapuntocajalibre (.
Const p1: gr_rvector3d.
Const c: ch_rcajalibre.
Var p: gr_rvector3d.
): single.
Var.
D: gr_rvector3d.
I: integer.
L: single.
Begin.
D := gr_resta (p1, c. C).
P := c. C.
For I := 0 todo 2 do.
Begin.
L := cc_limita (gr_productopunto (d, c. U[i]), -c. R. M[i], c. R. M[i]).
P := gr_suma (p, gr_multiplica (c. U[i], l)).
End.
D := gr_resta (p, p1).
Result := gr_productopunto (d, d).
End.
//------------------------------------------------------------------
Function ch_distanciacuadradapuntocajalibre (.
Const p1: gr_rvector3d.
Const c: ch_rcajalibre.
): single.
Var.
P: gr_rvector3d.
Begin.
Result := ch_mascercapuntocajalibre (p1, c, p).
End.
//------------------------------------------------------------------
// politopues de orientación discretea (discrete-orientation polytopes, k-dop).
//------------------------------------------------------------------
//------------------------------------------------------------------
Function ch_creapolitopo8: ch_rpolitopo.
Var.
I: integer.
Begin.
Setlength(result. Menores.
Setlength(result. Mayores.
For I := 0 todo high(result. Menores) do.
Begin.
Result. Menores[i] := maxsingle.
Result. Mayores[i] := -maxsingle.
End.
End.
//------------------------------------------------------------------
Function ch_creapolitopo8(.
Const puntos: gr_adrvector3d.
): ch_rpolitopo.
Var.
V: single.
I: integer.
Begin.
Result := ch_creapolitopo8.
For I := 0 todo high(puntos) do.
Begin.
V := +puntos[i].x+puntos[i]. Y+puntos[i]. Z.
If v < result. Menores[0] then result. Menores[0] := v else.
If v > result. Mayores[0] then result. Mayores[0] := v.
V := +puntos[i].x+puntos[i]. Y-puntos[i]. Z.
If v < result. Menores[1] then result. Menores[1] := v else.
If v > result. Mayores[1] then result. Mayores[1] := v.
V := +puntos[i].x-puntos[i]. Y+puntos[i]. Z.
If v < result. Menores[2] then result. Menores[2] := v else.
If v > result. Mayores[2] then result. Mayores[2] := v.
V := -puntos[i].x+puntos[i]. Y+puntos[i]. Z.
If v < result. Menores[3] then result. Menores[3] := v else.
If v > result. Mayores[3] then result. Mayores[3] := v.
End.
End.
//------------------------------------------------------------------
Function ch_contienepuntotriángulo2dcontrareloj(.
Const p.
T1, t2, t3: gr_rvector2d // puntos del triángulo.
): bolean.
Begin.
Result := false.
If gr_productocruz(gr_resta (p, t1), gr_resta (t2, t1)) < 0 then exit.
If gr_productocruz(gr_resta (p, t2), gr_resta (t3, t2)) < 0 then exit.
If gr_productocruz(gr_resta (p, t3), gr_resta (t1, t3)) < 0 then exit.
Result := true.
End.
//------------------------------------------------------------------
Function ch_contienepuntotriángulo2d(.
Const p.
T1, t2, t3: gr_rvector2d // puntos del triángulo.
): bolean.
Var.
Pab, pbc, pca: single.
Begin.
Result := false.
Pab := gr_productocruz(gr_resta (p, t1), gr_resta (t2, t1)).
Pbc := gr_productocruz(gr_resta (p, t2), gr_resta (t3, t2)).
If sign(pab) <> sign(pbc) then exit.
Pca := gr_productocruz(gr_resta (p, t3), gr_resta (t1, t3)).
If sign(pab) <> sign(pca) then exit.
Result := true.
End.
//------------------------------------------------------------------
Function ch_contienepuntotriángulocontrareloj(.
Const p: gr_rvector3d.
T1, t2, t3: gr_rvector3d // puntos del triángulo.
): bolean.
Var.
Ab, ac, bc, c, b: single.
Begin.
Result := false.
T1 := gr_resta (t1, p).
T2 := gr_resta (t2, p).
T3 := gr_resta (t3, p).
Ab := gr_productopunto (t1, t2).
Ac := gr_productopunto (t1, t3).
Bc := gr_productopunto (t2, t3).
C := gr_productopunto (t3, t3).
If bc*ac-c*ab < 0 then exit.
B := gr_productopunto (t2, t2).
If ab*bc-ac*b < 0 then exit.
Result := true.
End.
//------------------------------------------------------------------
Function ch_contienepuntopoligono (.
Const p1: gr_rvector3d.
Const p2: gr_rpoligono3d.
): bolean.
Var.
Menor, mayor, medio: integer.
Begin.
Result := false.
Menor := 0.
Mayor := length(p2. V).
Repeat.
Medio := (menor+mayor) shr 1.
If gr_triángulocontrareloj(p2. V[0], p2. V[medio], p1) then.
Menor := medio else.
Mayor := medio.
Until menor+1 >= mayor.
If (menor = 0) or (mayor = length(p2. V)) then exit.
Result := gr_triángulocontrareloj(p2. V[menor], p2. V[mayor], p1).
End.
//------------------------------------------------------------------
Function ch_traslapapuntopolihedro (.
Const p: gr_rvector3d.
Const planos: gr_adrplano3d; // polihedro.
Planonormalizado: bolean.
): bolean.
Var.
I: integer.
Begin.
Result := false.
For I := 0 todo high(planos) do.
Begin.
If ch_distanciapuntoplano (p, planos[i], planonormalizado) > 0 then exit.
End.
Result := true.
End.
//------------------------------------------------------------------
Function ch_traslapasegmento2dsegmento2d(.
Const sa1, sa2, // puntos que limitan el segmento a.
Sb1, sb2: gr_rvector2d; // puntos que limitan el segmento b.
Var t: single; // valor de intersección sobre el segmento a.
Var p: gr_rvector2d // punto de intersección.
): bolean.
Var.
A1, a2, a3, a4: single.
Begin.
Result := false.
A1 := gr_areatriánguloconsigno (sa1, sa2, sb2).
A2 := gr_areatriánguloconsigno (sa1, sa2, sb1).
If a1*a2 < 0 then.
Begin.
A3 := gr_areatriánguloconsigno (sb1, sb2, sa1).
A4 := a3+a2-a1.
If a3*a4 < 0 then.
Begin.
T := a3/(a3-a4).
P := gr_suma (sa1, gr_multiplica (gr_resta (sa2, sa1), t)).
Result := true.
End.
End.
End.
//------------------------------------------------------------------
// basado en:
// real-time collision detection, p. 460 (p. 176 no maneja división entre 0).
Function ch_intersecasegmentoplano (.
Const s1, s2: gr_rvector3d; // puntos del segmento.
Const p1: gr_rplano3d.
Var t: single.
Var p: gr_rvector3d.
): bolean.
Var.
Ab: gr_rvector3d.
Tn, TD, k: int64.
V: gr_rvector3d.
Begin.
Result := false.
{ versión de la página 176:
Result := true.
Ab := gr_resta (s2, s1).
T := (p1. P-gr_productopunto (p1. N, s1))/gr_productopunto (p1. N, ab).
If (t >= 0) and (t <= 1) then.
Begin.
P := gr_suma (s1, gr_multiplica (ab, t)).
Exit.
End.
Result := false.
}.
Ab := gr_resta (s2, s1).
Tn := trunc(p1. P-gr_productopunto (p1. N, s1)).
Td := trunc(gr_productopunto (p1. N, ab)).
If TD = 0 then exit.
If TD < 0 then.
Begin.
Tn := -TN.
Td := -td.
End.
If (TN < 0) or (TN > td) then exit.
V := gr_creavector3d.
K := td-1.
If TD > 0 then k := -k.
If p1. N.x > 0 then v.x := +k else.
If p1. N.x < 0 then v.x := -k.
If p1. N. Y > 0 then v. Y := +k else.
If p1. N. Y < 0 then v. Y := -k.
If p1. N. Z > 0 then v. Z := +k else.
If p1. N. Z < 0 then v. Z := -k.
P := gr_suma (s1, gr_divide (gr_suma (gr_multiplica (ab, TN), v), td)).
Result := true.
End.
//------------------------------------------------------------------
Function ch_intersecasegmentotriángulo (.
Const s1, s2, // puntos del segmento.
T1, t2, t3: gr_rvector3d; // puntos del triángulo.
Var u, v, w, // coordenadas baricéntricas.
T: single.
): bolean.
Var.
Ab, ac, qp, ap, n: gr_rvector3d.
D, id: single.
Begin.
Result := false.
Ab := gr_resta (t2, t1).
Ac := gr_resta (t3, t1).
Qp := gr_resta (s1, s2).
N := gr_productocruz(ab, ac).
D := gr_productopunto (qp, n).
If d <= 0 then exit.
Ap := gr_resta (s1, t1).
T := gr_productopunto (ap, n).
If < 0 then exit.
If > d then exit.
E := gr_productocruz(qp, ap).
V := gr_productopunto (ac, e).
If (v < 0) or (v > d) then exit.
W := -gr_productopunto (ab, e).
If (w < 0) or (v+w > d) then exit.
Id := 1/d.
T := t+id.
V := v+id.
W := w+id.
U := 1-V-w.
Result := true.
End.
//------------------------------------------------------------------
Function ch_intersecasegmentotriánguloplanos(.
Const s1, s2: gr_rvector3d; // puntos del segmento.
Const t1: gr_rtriánguloplanar3d.
Var u, v, w, // coordenadas baricéntricas.
T: single.
Var s: gr_rvector3d // punto de intersección.
): bolean.
Var.
Dp, dq, d: single.
Begin.
Result := false.
Dp := gr_productopunto (s1, t1. P. N)-t1. P. P.
If DP < 0 then exit.
Dq := gr_productopunto (s2, t1. P. N)-t1. P. P.
If dq >= 0 then exit.
D := DP-dq.
T := DP/d.
S := gr_suma (s1, gr_multiplica (gr_resta (s2, s1), t)).
U := gr_productopunto (s, t1. Bordebc. N)-t1. Bordebc. P.
If (u < 0) or (u > 1) then exit.
V := gr_productopunto (s, t1. Bordeca. N)-t1. Bordeca. P.
If v < 0 then exit.
W := 1-u-v.
If w < 0 then exit.
Result := true.
End.
//------------------------------------------------------------------
Function ch_traslapasegmentocajaeje1(.
Const s1, s2: gr_rvector3d; // puntos del segmento.
Const c: ch_rcajaeje1.
): bolean.
Var.
C1, m: gr_rvector3d.
E, d: gr_rvector3d.
Adx, ady, adz: single.
Begin.
Result := false.
C1 := gr_multiplica (gr_suma (c. Menor, c. Mayor), 0.5).
E := gr_resta (c. Mayor, c1).
Vaya := gr_multiplica (gr_suma (s1, s2), 0.5).
D := gr_resta (s2, m).
Vaya := gr_resta (m, c1).
Adx := abs(d.x).
If abs(m.x) > e.x+adx then exit.
Ady := abs(d. Y).
If abs(m. Y) > e. Y+ady then exit.
Adz := abs(d. Z).
If abs(m. Z) > e. Z+adz then exit.
Adx := adx+gr_epsilon.
Ady := ady+gr_epsilon.
Adz := adz+gr_epsilon.
If abs(m. Y*d. Z-m. Z*d. Y) > e. Y*adz+e. Z*ady then exit.
If abs(m. Z*d.x-m.x*d. Z) > e.x*adz+e. Z*adx then exit.
If abs(m.x*d. Y-m. Y*d.x) > e.x*ady+e. Y*adx then exit.
Result := true.
End.
//------------------------------------------------------------------
Function ch_intersecasegmentocilindro (.
Const s1, s2, // puntos del segmento.
C1, c2: gr_rvector3d; // puntos del cilíndro.
R: single; // radio del cilíndro.
Var t: single.
): bolean.
Var.
D, n: gr_rvector3d.
Md, nd, d, n, mn, a, k, c, b, discr: single.
Begin.
Result := false.
D := gr_resta (c2, c1).
Vaya := gr_resta (s1, c1).
N := gr_resta (s2, s1).
Md := gr_productopunto (m, d).
Nd := gr_productopunto (n, d).
D := gr_productopunto (d, d).
If (md < 0) and (md+nd < 0) then exit.
If (md > d) and (md+nd > d) then exit.
N := gr_productopunto (n, n).
Mn := gr_productopunto (m, n).
A := d*n-nd*nd.
K := gr_productopunto (m, m)-r*r.
C := d*k-md*md.
If abs(a) < gr_epsilon then.
Begin.
If c > 0 then exit.
If md < 0 then := -mn/n else.
If md > d then := (nd-mn)/n else.
T := 0.
Result := true.
Exit.
End.
B := d*mn-nd*md.
Discr := b*b-a*c.
If discr < 0 then exit.
T := (-b-sqrt(discr))/a.
If (t < 0) or (t > 1) then exit.
If md+t*nd < 0 then.
Begin.
If nd <= 0 then exit.
T := -md/nd.
Result := k+2*t*(mn+t*n) <= 0.
Exit.
End else.
If md+t*nd > d then.
Begin.
If nd >= 0 then exit.
T := (d-md)/nd.
Result := k+d-2*md+t*(2*(mn-nd)+t*n) <= 0.
Exit.
End.
Result := true.
End.
//------------------------------------------------------------------
Function ch_intersecasegmentopolihedro (.
Const s1, s2: gr_rvector3d; // puntos del segmento.
Const planos: gr_adrplano3d; // planos del polihedro.
Var tprimero, tultimo: single.
): bolean.
Var.
D: gr_rvector3d.
I: integer.
Denom, Dist, t: single.
Begin.
Result := false.
D := gr_resta (s2, s1).
Tprimero := 0.
Túltimo := 0.
For I := 0 todo high(planos) do.
Begin.
Denom := gr_productopunto (planos[i]. N, d).
Dist := planos[i]. P-gr_productopunto (planos[i]. N, s1).
If denom = 0 then.
Begin.
If Dist > 0 then exit.
End else.
Begin.
T := Dist/denom.
If denom < 0 then.
Begin.
If > tprimero then tprimero := t.
End else.
Begin.
If < túltimo then túltimo := t.
End.
If tprimero > túltimo then exit.
End.
End.
Result := true.
End.
//------------------------------------------------------------------
Function ch_intersecalineatriángulo (.
Const l1, l2, // puntos sobre la línea.
T1, t2, t3: gr_rvector3d; // puntos del triángulo.
Var u, v, w: single // coordenadas baricéntricas de intersección.
): bolean.
Var.
Pq, pa, pb, PC: gr_rvector3d.
D: single.
Begin.
Result := false.
Pq := gr_resta (l2, l1).
Para := gr_resta (t1, l1).
Pb := gr_resta (t2, l1).
Pc := gr_resta (t3, l1).
U := gr_productotripleescalar(pq, PC, pb).
If u < 0 then exit.
V := gr_productotripleescalar(pq, pa, PC).
If v < 0 then exit.
W := gr_productotripleescalar(pq, pb, pa).
If w < 0 then exit.
D := 1/(u+v+w).
U := u*d.
V := v*d.
W := w*d.
Result := true.
End.
//------------------------------------------------------------------
Function ch_intersecalineacuadrilaterocontrareloj(.
Const l1, l2, // puntos de la línea.
C1, c2, c3, c4: gr_rvector3d; // puntos del cuadrilátero contra reloj.
Var p: gr_rvector3d // punto de intersección.
): bolean.
Var.
Pq, pa, pb, PC, pd, m: gr_rvector3d.
U, v, w, denom: single.
Begin.
Result := false.
Pq := gr_resta (l2, l1).
Para := gr_resta (c1, l1).
Pb := gr_resta (c2, l1).
Pc := gr_resta (c3, l1).
Vaya := gr_productocruz(pc, pq).
V := gr_productopunto (pa, m).
If v >= 0 then.
Begin.
U := -gr_productopunto (pb, m).
If u < 0 then exit.
W := gr_productotripleescalar(pq, pb, pa).
If w < 0 then exit.
Denom := 1/(u+v+w).
U := u*denom.
V := v*denom.
W := w*denom.
P := gr_suma (gr_suma (gr_multiplica (c1, u), gr_multiplica (c2, v)).
Gr_multiplica (c3, w)).
End else.
Begin.
Posdata := gr_resta (c4, l1).
U := gr_productopunto (pd, m).
If u < 0 then exit.
W := gr_productotripleescalar(pq, pa, pd).
If w < 0 then exit.
V := -v.
Denom := 1/(u+v+w).
U := u*denom.
V := v*denom.
W := w*denom.
P := gr_suma (gr_suma (gr_multiplica (c1, u), gr_multiplica (c4, v)).
Gr_multiplica (c3, w)).
End.
Result := true.
End.
//------------------------------------------------------------------
// basado en:
// http://www.cs.lth, se/home/tomas_akenine_moller/raytri/.
Function ch_intersecarayotriángulo (.
Const o, // origen del rayo.
D, // dirección del rayo tt1, t2, t3: gr_rvector3d; // puntos del triángulo.
Var t, // distancia del origen del rayo al punto de.
// intersección.
U, v: single // coordenadas baricéntricas.
): bolean.
Var.
B1, b2, televisión, pv, qv: gr_rvector3d.
D1, id1: single.
Begin.
Result := false.
B1 := gr_resta (t2, t1).
B2 := gr_resta (t3, t1).
Pv := gr_productocruz(d, b2).
D1 := gr_productopunto (b1, pv).
If d1 > gr_epsilon then.
Begin.
Tv := gr_resta (o, t1).
U := gr_productopunto (tv, pv).
If (u < 0) or (u > d1) then exit.
Qv := gr_productocruz(tv, b1).
V := gr_productopunto (d, qv).
If (v < 0) or (u+v > d1) then exit.
End else.
If d1 < -gr_epsilon then.
Begin.
Tv := gr_resta (o, t1).
U := gr_productopunto (tv, pv).
If (u > 0) or (u < d1) then exit.
Qv := gr_productocruz(tv, b1).
V := gr_productopunto (d, qv).
If (v > 0) or (u+v < d1) then exit.
End else.
Begin.
Exit.
End.
Id1 := 1/d1.
T := gr_productopunto (b2, qv)*id1.
U := u*id1.
V := v*id1.
Result := true.
End.
//------------------------------------------------------------------
Function ch_intersecarayoesfera (.
Const o: gr_rvector3d; // origen del rayo.
Const d: gr_rvector3d; // dirección del rayo.
Const e: ch_resfera.
Var t: single.
Var p: gr_rvector3d // punto de intersección.
): bolean.
Var.
M: gr_rvector3d.
B, c, ds: single.
Begin.
Result := false.
Vaya := gr_resta (o, e. C).
B := gr_productopunto (m, d).
C := gr_productopunto (m, m)-e. R*e. R.
If (c > 0) and (b > 0) then exit.
Ds := b*b-c.
If ds < 0 then exit.
T := -b-sqrt(ds).
If < 0 then := 0.
P := gr_suma (o, gr_multiplica (d, t)).
Result := true.
End.
//------------------------------------------------------------------
Function ch_traslaparayoesfera (.
Const o: gr_rvector3d; // origen del rayo.
Const d: gr_rvector3d; // dirección del rayo.
Const e: ch_resfera.
): bolean.
Var.
M: gr_rvector3d.
B, c, ds: single.
Begin.
Result := true.
Vaya := gr_resta (o, e. C).
C := gr_productopunto (m, m)-e. R*e. R.
If c <= 0 then exit.
Result := false.
B := gr_productopunto (m, d).
If b > 0 then exit.
Ds := b*b-c.
If ds < 0 then exit.
Result := true.
End.
//------------------------------------------------------------------
Function ch_intersecarayocajaeje1(.
Const o: gr_rvector3d.
Const d: gr_rvector3d.
Const c: ch_rcajaeje1.
Var tmenor: single.
Var p: gr_rvector3d.
): bolean.
Var.
Tmayor, id, t1, t2: single.
I: integer.
Begin.
Result := false.
Tmenor := 0.
Tmayor := maxsingle.
For I := 0 todo 2 do.
Begin.
If abs(d. M[i]) < gr_epsilon then.
Begin.
If (o. M[i] < c. Menor. M[i]) or (p. M[i] > c. Mayor. M[i]) then exit.
End else.
Begin.
Id := 1/d. M[i].
T1 := (c. Menor. M[i]-o. M[i])*id.
T2 := (c. Mayor. M[i]-o. M[i])*id.
If t1 > t2 then cm_intercambia (t1, t2).
Tmenor := maxvalue ([tmenor, t1]).
Tmayor := minvalue ([tmayor, t2]).
If tmenor > tmayor then exit.
End.
End.
P := gr_suma (o, gr_multiplica (d, tmenor)).
Result := true.
End.
//------------------------------------------------------------------
Function ch_intersecaplanoplano (.
Const p1, p2: gr_rplano3d.
Var p: gr_rvector3d.
Var d: gr_rvector3d.
): bolean.
Var.
D1: single.
Begin.
Result := false.
D := gr_productocruz(p1. N, p2. N).
D1 := gr_productopunto (d, d).
If d1 < gr_epsilon then exit.
P := gr_divide (gr_productocruz(gr_resta (.
Gr_multiplica (p2. N, p1. P), gr_multiplica (p1. N, p2. P)), d), d1).
Result := true.
End.
//------------------------------------------------------------------
Function ch_intersecaplanoplanoplano (.
Const p1, p2, p3: gr_rplano3d.
Var p: gr_rvector3d.
): bolean.
Var.
U: gr_rvector3d.
Denom: single.
Begin.
Result := false.
U := gr_productocruz(p2. N, p3. N).
Denom := gr_productopunto (p1. N, u).
If abs(denom) < gr_epsilon then exit.
P := gr_divide (gr_suma (gr_multiplica (u, p1. P), gr_productocruz(.
P1. N, gr_resta (gr_multiplica (p2. N, p3. P).
Gr_multiplica (p3. N, p2. P)))), denom).
Result := true.
End.
//------------------------------------------------------------------
// basado en:
// http://www.cs.lth, se/home/tomas_akenine_moller/code/.
Function ch_traslapaplanocajaeje3(.
Const p: gr_rplano3d.
Const c: ch_rcajaeje3.
): bolean.
Var.
I: integer.
Vmenor,vmayor: gr_rvector3d.
V: single.
Begin.
Result := false.
For I := 0 todo 2 do.
Begin.
V := c. C. M[i].
If p. N. M[i] > 0 then.
Begin.
Vmenor. M[i] := -c. R. M[i]-v.
Vmayor. M[i] := c. R. M[i]-v.
End else.
Begin.
Vmenor. M[i] := c. R. M[i]-v.
Vmayor. M[i] := -c. R. M[i]-v.
End.
End.
If gr_productopunto (p. N, vmenor) > 0 then exit.
If gr_productopunto (p. N, vmayor) < 0 then exit.
Result := true.
End.
//------------------------------------------------------------------
// basado en:
// http://jgt, akpeters.com/papers/moller97/.
Function ch_intersecatriángulotriángulo (.
Const ta1, ta2, ta3, // puntos del triángulo a.
Tb1, tb2, tb3: gr_rvector3d // puntos del triángulo b.
): bolean.
Var.
E1, e2, n1, n2, DV: gr_rvector3d.
Is1, is2: array [0.1] of single.
D1, d2, du0, du1, du2, dv0, DV 1, dv2: single.
Du01, du02, dv01, dv02: single.
Vp0, vp1, vp2: single.
Up0, up1, up2: single.
B, c, mayor: single.
A, b, c, x0, x1: single.
D, f, y0, y1: single.
Xx y, xxy, t: single.
I: integer.
Function calculaintervalos(.
Const v0, v1, v2, d0, d1, d2, d0d1, d0d2: single.
Var a, b, c, x0, x1: single.
Var resultado: bolean.
): bolean.
Begin.
Result := false.
If d0d1 > 0 then.
Begin.
A := v2.
B := (v0-v2)*d2.
C := (v1-v2)*d2.
X0 := d2-d0.
X1 := d2-d1.
End else.
If d0d2 > 0 then.
Begin.
A := v1.
B := (v0-v1)*d1.
C := (v2-v1)*d1.
X0 := d1-d0.
X1 := d1-d2.
End else.
If (d1*d2 > 0) or (d0 <> 0) then.
Begin.
A := v0.
B := (v1-v0)*d0.
C := (v2-v0)*d0.
X0 := d0-d1.
X1 := d0-d2.
End else.
If d1 <> 0 then.
Begin.
A := v1.
B := (v0-v1)*d1.
C := (v2-v1)*d1.
X0 := d1-d0.
X1 := d1-d2.
End else.
If d2 <> 0 then.
Begin.
A := v2.
B := (v0-v2)*d2.
C := (v1-v2)*d2.
X0 := d2-d0.
X1 := d2-d1.
End else.
Begin.
Result := true.
Resultado := gr_triánguloscoplanares(n1, ta1, ta2, ta3, tb1, tb2, tb3).
End.
End.
Begin.
Result := false.
E1 := gr_resta (ta2, ta1).
E2 := gr_resta (ta3, ta1).
N1 := gr_productocruz(e1, e2).
D1 := -gr_productopunto (n1, ta1).
Du0 := gr_productopunto (n1, tb1)+d1.
Du1 := gr_productopunto (n1, tb2)+d1.
Du2 := gr_productopunto (n1, tb3)+d1.
If abs(du0) < gr_epsilon then du0 := 0.
If abs(du1) < gr_epsilon then du1 := 0.
If abs(du2) < gr_epsilon then du2 := 0.
Du01 := du0*du1.
Du02 := du0*du2.
If (du01 > 0) and (du02 > 0) then exit.
E1 := gr_resta (tb2, tb1).
E2 := gr_resta (tb3, tb1).
N2 := gr_productocruz(e1, e2).
D2 := -gr_productopunto (n2, tb1).
Dv0 := gr_productopunto (n2, ta1)+d2.
Dv1 := gr_productopunto (n2, ta2)+d2.
Dv2 := gr_productopunto (n2, ta3)+d2.
If abs(dv0) < gr_epsilon then dv0 := 0.
If abs(DV 1) < gr_epsilon then DV 1 := 0.
If abs(dv2) < gr_epsilon then dv2 := 0.
Dv01 := dv0*DV 1.
Dv02 := dv0*dv2.
If (dv01 > 0) and (dv02 > 0) then exit.
Dv := gr_productocruz(n1, n2).
Mayor := abs(dv. M[0]).
I := 0.
B := abs(dv. M[1]).
C := abs(dv. M[2]).
If b > mayor then.
Begin.
Mayor := b.
I := 1.
End.
If c > mayor then.
Begin.
// mayor := c.
I := 2.
End.
Vp0 := ta1. M[i].
Vp1 := ta2. M[i].
Vp2 := ta3. M[i].
Up0 := tb1. M[i].
Up1 := tb2. M[i].
Up2 := tb3. M[i].
If calculaintervalos(vp0, vp1, vp2, dv0, DV 1, dv2, dv01, dv02, a, b, c.
X0, x1, result) then exit.
If calculaintervalos(up0, up1, up2, du0, du1, du2, du01, du02, d, f.
Y0, y1, result) then exit.
Xx := x0*x1.
Y := y0*y1.
Xxy := xx*y.
T := a*xxy.
Is1[0] := t+b*x1*y.
Is1[1] := t+c*x0*y.
T := d*xxy.
Is2[0] := t+e*xx*y1.
Is2[1] := t+f*xx*y0.
Cm_asciente (is1[0], is1[1]).
Cm_asciente (is2[0], is2[1]).
If (is1[1] < is2[0]) or (is2[1] < is1[0]) then exit.
Result := false.
End.
//------------------------------------------------------------------
// tomado de:
// http://www.cs.lth, se/home/tomas_akenine_moller/code/.
Function ch_traslapatriángulocajaeje3(.
Const t1, t2, t3: gr_rvector3d; // puntos del triángulo.
Const c: ch_rcajaeje3.
): bolean.
Var.
V1, v2, v3: gr_rvector3d.
Menor, mayor, p1, p2, p3, r, fex, fey, fez: single.
E1, e2, e3: gr_rvector3d.
Function pruebaejex01(.
A, b, fa, fb: single.
): bolean.
Begin.
P1 := a*v1. Y-b*v1. Z.
P3 := a*v3. Y-b*v3. Z.
If p1 < p3 then.
Begin.
Menor := p1.
Mayor := p3.
End else.
Begin.
Menor := p3.
Mayor := p1.
End.
R := fa*c. R. Y+fb*c. R. Z.
Result := (menor > r) or (mayor < -r).
End.
Function pruebaejex2(.
A, b, fa, fb: single.
): bolean.
Begin.
P1 := a*v1. Y-b*v1. Z.
P2 := a*v2. Y-b*v2. Z.
If p1 < p2 then.
Begin.
Menor := p1.
Mayor := p2.
End else.
Begin.
Menor := p2.
Mayor := p1.
End.
R := fa*c. R. Y+fb*c. R. Z.
Result := (menor > r) or (mayor < -r).
End.
Function pruebaejey02(.
A, b, fa, fb: single.
): bolean.
Begin.
P1 := -a*v1.x+b*v1. Z.
P3 := -a*v3.x+b*v3. Z.
If p1 < p3 then.
Begin.
Menor := p1.
Mayor := p3.
End else.
Begin.
Menor := p3.
Mayor := p1.
End.
R := fa*c. R.x+fb*c. R. Z.
Result := (menor > r) or (mayor < -r).
End.
Function pruebaejey1(.
A, b, fa, fb: single.
): bolean.
Begin.
P1 := -a*v1.x+b*v1. Z.
P2 := -a*v2.x+b*v2. Z.
If p1 < p2 then.
Begin.
Menor := p1.
Mayor := p2.
End else.
Begin.
Menor := p2.
Mayor := p1.
End.
R := fa*c. R.x+fb*c. R. Z.
Result := (menor > r) or (mayor < -r).
End.
Function pruebaejez12(.
A, b, fa, fb: single.
): bolean.
Begin.
P2 := a*v2.x-b*v2. Y.
P3 := a*v3.x-b*v3. Y.
If p3 < p2 then.
Begin.
Menor := p3.
Mayor := p2.
End else.
Begin.
Menor := p2.
Mayor := p3.
End.
R := fa*c. R.x+fb*c. R. Y.
Result := (menor > r) or (mayor < -r).
End.
Function pruebaejez0(.
A, b, fa, fb: single.
): bolean.
Begin.
P1 := a*v1.x-b*v1. Y.
P2 := a*v2.x-b*v2. Y.
If p1 < p2 then.
Begin.
Menor := p1.
Mayor := p2.
End else.
Begin.
Menor := p2.
Mayor := p1.
End.
R := fa*c. R.x+fb*c. R. Y.
Result := (menor > r) or (mayor < -r).
End.
Procedure extremos(.
X1, x2, x3: single).
Begin.
Menor := x1.
Mayor := x1.
If x2 < menor then menor := x2.
If x2 > mayor then mayor := x2.
If x3 < menor then menor := x3.
If x3 > mayor then mayor := x3.
End.
Begin.
Result := false.
V1 := gr_resta (t1, c. C).
V2 := gr_resta (t2, c. C).
V3 := gr_resta (t3, c. C).
E1 := gr_resta (v2, v1).
E2 := gr_resta (v3, v2).
E3 := gr_resta (v1, v3).
Fex := abs(e1.x).
Fey := abs(e1. Y).
Fez := abs(e1. Z).
If pruebaejex01(e1. Z, e1. Y, fez, fey) then exit.
If pruebaejey02(e1. Z, e1.x, fez, fex) then exit.
If pruebaejez12(e1. Y, e1.x, fey, fex) then exit.
Fex := abs(e2.x).
Fey := abs(e2. Y).
Fez := abs(e2. Z).
If pruebaejex01(e2. Z, e2. Y, fez, fey) then exit.
If pruebaejey02(e2. Z, e2.x, fez, fex) then exit.
If pruebaejez0(e2. Y, e2.x, fey, fex) then exit.
Fex := abs(e3.x).
Fey := abs(e3. Y).
Fez := abs(e3. Z).
If pruebaejex2(e3. Z, e3. Y, fez, fey) then exit.
If pruebaejey1(e3. Z, e3.x, fez, fex) then exit.
If pruebaejez12(e3. Y, e3.x, fey, fex) then exit.
Extremos(v1.x, v2.x, v3.x).
If (menor > c. R.x) or (mayor < -c. R.x) then exit.
Extremos(v1. Y, v2. Y, v3. Y).
If (menor > c. R. Y) or (mayor < -c. R. Y) then exit.
Extremos(v1. Z, v2. Z, v3. Z).
If (menor > c. R. Z) or (mayor < -c. R. Z) then exit.
If not ch_traslapaplanocajaeje3(gr_creaplano3d(gr_productocruz(e1, e2).
Gr_productopunto (e1, e2)), ch_creacajaeje3(v1, c. R)) then exit.
Result := true.
End.
//------------------------------------------------------------------
Function ch_traslapaesferaplano (.
Const e: ch_resfera.
Const p: gr_rplano3d.
): bolean.
Begin.
Result := abs(gr_productopunto (e. C, p. N)-p. P) <=
E. R.
End.
//------------------------------------------------------------------
Function ch_traslapaesferamedioplano (.
Const e: ch_resfera.
Const p: gr_rplano3d.
): bolean.
Begin.
Result := gr_productopunto (e. C, p. N)-p. P <= e. R.
End.
//------------------------------------------------------------------
Function ch_traslapaesferatriángulo (.
Const e: ch_resfera.
Const t1, t2, t3: gr_rvector3d; // puntos del triángulo.
Var p: gr_rvector3d.
): bolean.
Var.
V: gr_rvector3d.
Begin.
Ch_mascercapuntotriángulo (e. C, t1, t2, t3, p).
V := gr_resta (por ejemplo C).
Result := gr_productopunto (v, v) <= e. R*e. R.
End.
//------------------------------------------------------------------
Function ch_traslapaesferaesfera (.
Const e1, e2: ch_resfera.
): bolean.
Var.
D2, r: single.
Begin.
D2 := gr_distanciacuadrada (e1. C, e2. C).
R := e1. R+e2. R.
Result := d2 <= r*r.
End.
//------------------------------------------------------------------
Function ch_traslapaesferacajaeje1(.
Const e: ch_resfera.
Const c: ch_rcajaeje1.
): bolean.
Begin.
Result := ch_distanciacuadradapuntocajaeje (e. C, c) <= e. R*e. R.
End.
//------------------------------------------------------------------
Function ch_traslapaesferacajaeje1(.
Const e: ch_resfera.
Const c: ch_rcajaeje1.
Var p: gr_rvector3d.
): bolean.
Var.
V: gr_rvector3d.
Begin.
Ch_mascercapuntocajaeje (e. C, c, p).
V := gr_resta (por ejemplo C).
Result := gr_productopunto (v, v) <= e. R*e. R.
End.
//------------------------------------------------------------------
Function ch_traslapaesferacajalibre (.
Const e: ch_resfera.
Const c: ch_rcajalibre.
Var p: gr_rvector3d.
): bolean.
Var.
V: gr_rvector3d.
Begin.
Ch_mascercapuntocajalibre (e. C, c, p).
V := gr_resta (por ejemplo C).
Result := gr_productopunto (v, v) <= e. R*e. R.
End.
//------------------------------------------------------------------
Function ch_traslapaesferacapsula (.
Const e: ch_resfera.
Const c: ch_rcapsula.
): bolean.
Var.
D2, r: single.
Begin.
D2 := ch_distanciacuadradapuntosegmento (c. A, c. B, e. C).
R := e. R+c. R.
Result := d2 <= r*r.
End.
//------------------------------------------------------------------
Function ch_traslapaesferapoligono (.
Const e: ch_resfera.
Const p: gr_rpoligono3d.
): bolean.
Var.
M: gr_rplano3d.
I, k: integer.
T: single.
Que: gr_rvector3d.
Begin.
Result := false.
M. N := gr_normaliza (gr_productocruz(gr_resta (p. V[1], p. V[0]), gr_resta (.
P. V[2], p. V[0]))).
M. P := -gr_productopunto (m. N, p. V[0]).
If not ch_traslapaesferaplano (e, m) then exit.
K := length(p. V).
I := 0.
J := k-1.
While i < k do.
Begin.
If ch_intersecarayoesfera (p. V[j], gr_resta (p. V[i], p. V[j]), t, que) and.
(T <= 1) then exit.
J := i.
Inc(i).
End.
Ch_mascercapuntoplano (e. C, que).
Result := ch_contienepuntopoligono (que, p).
End.
//------------------------------------------------------------------
Function ch_contienecajaeje1punto (.
Const c: ch_rcajaeje1.
Const p: gr_rvector3d.
): bolean.
Begin.
Result :=
((p.x >= c. Menor.x) and (p.x <= c. Mayor.x)) and.
((p. Y >= c. Menor. Y) and (p. Y <= c. Mayor. Y)) and.
((p. Z >= c. Menor. Z) and (p. Z <= c. Mayor. Z)).
End.
//------------------------------------------------------------------
Function ch_traslapacajaeje1plano (.
Const c: ch_rcajaeje1.
Const p: gr_rplano3d.
): bolean.
Var.
C1, e: gr_rvector3d.
R, s: single.
Begin.
C1 := gr_multiplica (gr_suma (c. Mayor, c. Menor), 0.5).
E := gr_resta (c. Mayor, c1).
R := e.x*abs(p. N.x)+e. Y*abs(p. N. Y)+e. Z*abs(p. N. Z).
S := gr_productopunto (p. N, c1)-p. P.
Result := abs(s) <= r.
End.
//------------------------------------------------------------------
Function ch_traslapacajaeje1cajaeje1(.
Const c1, c2: ch_rcajaeje1.
): bolean.
Begin.
Result :=
(c1. Mayor.x >= c2. Menor.x) and (c1. Menor.x <= c2. Mayor.x) and.
(C1. Mayor. Y >= c2. Menor. Y) and (c1. Menor. Y <= c2. Mayor. Y) and.
(C1. Mayor. Z >= c2. Menor. Z) and (c1. Menor. Z <= c2. Mayor. Z).
End.
//------------------------------------------------------------------
Function ch_traslapacajaeje2cajaeje2(.
Const c1, c2: ch_rcajaeje2.
): bolean.
Var.
T: single.
Begin.
Result := false.
T := c1. Menor.x-c2. Menor.x.
If (t > c2. D.x) or (-t > c1. D.x) then exit.
T := c1. Menor. Y-c2. Menor. Y.
If (t > c2. D. Y) or (-t > c1. D. Y) then exit.
T := c1. Menor. Z-c2. Menor. Z.
If (t > c2. D. Z) or (-t > c1. D. Z) then exit.
Result := true.
End.
//------------------------------------------------------------------
Function ch_traslapacajaeje3cajaeje3(.
Const c1, c2: ch_rcajaeje3.
): bolean.
Begin.
Result :=
(abs(c1. C.x-c2. C.x) <= (c1. R.x+c2. R.x)) and.
(Abs(c1. C. Y-c2. C. Y) <= (c1. R. Y+c2. R. Y)) and.
(Abs(c1. C. Z-c2. C. Z) <= (c1. R. Z+c2. R. Z)).
End.
//------------------------------------------------------------------
Function ch_traslapacajalibreplano (.
Const c: ch_rcajalibre.
Const p: gr_rplano3d.
): bolean.
Var.
R, s: single.
Begin.
R :=
C. R.x*abs(gr_productopunto (p. N, c. U[0]))+.
C. R. Y*abs(gr_productopunto (p. N, c. U[1]))+.
C. R. Z*abs(gr_productopunto (p. N, c. U[2])).
S := gr_productopunto (p. N, c. C)-p. P.
Result := abs(s) <= r.
End.
//------------------------------------------------------------------
Function ch_traslapacajalibrecajalibre (.
Const c1, c2: ch_rcajalibre.
): bolean.
Var.
R1, r2: single.
R, ar: gr_rmatriz3x3.
I, j: integer.
T: gr_rvector3d.
Begin.
Result := false.
For I := 0 todo 2 do.
For := 0 todo 2 do.
R. M[i,j] := gr_productopunto (c1. U[i], c2. U[j]).
T := gr_resta (c2. C, c1. C).
T := gr_creavector3d(gr_productopunto (t, c1. U[0]), gr_productopunto (t.
C1. U[1]), gr_productopunto (t, c1. U[2])).
For I := 0 todo 2 do.
For := 0 todo 2 do.
Ar. M[i,j] := abs(r. M[i,j])+gr_epsilon.
For I := 0 todo 2 do.
Begin.
R1 := c1. R. M[i].
R2 := c2. R. M[0]*ar. M[i,0]+c2. R. M[1]*ar. M[i,1]+c2. R. M[2]*ar. M[i,2].
If abs(t. M[i]) > r1+r2 then exit.
End.
For I := 0 todo 2 do.
Begin.
R1 := c1. R. M[0]*ar. M[0,i]+c1. R. M[1]*ar. M[1,i]+c1. R. M[2]*ar. M[2,i].
R2 := c2. R. M[i].
If abs(t. M[0]*r. M[0,i]+t. M[1]*r. M[1,i]+t. M[2]*r. M[2,i]) > r1+r2 then exit.
End.
R1 := c1. R. M[1]*ar. M[2,0]+c1. R. M[2]*ar. M[1,0].
R2 := c2. R. M[1]*ar. M[0,2]+c2. R. M[2]*ar. M[0,1].
If abs(t. M[2]*r. M[1,0]-t. M[1]*r. M[2,0]) > r1+r2 then exit.
R1 := c1. R. M[1]*ar. M[2,1]+c1. R. M[2]*ar. M[1,1].
R2 := c2. R. M[0]*ar. M[0,2]+c2. R. M[2]*ar. M[0,0].
If abs(t. M[2]*r. M[1,1]-t. M[1]*r. M[2,1]) > r1+r2 then exit.
R1 := c1. R. M[1]*ar. M[2,2]+c1. R. M[2]*ar. M[1,2].
R2 := c2. R. M[0]*ar. M[0,1]+c2. R. M[1]*ar. M[0,0].
If abs(t. M[2]*r. M[1,2]-t. M[1]*r. M[2,2]) > r1+r2 then exit.
R1 := c1. R. M[0]*ar. M[2,0]+c1. R. M[2]*ar. M[0,0].
R2 := c2. R. M[1]*ar. M[1,2]+c2. R. M[2]*ar. M[1,1].
If abs(t. M[0]*r. M[2,0]-t. M[2]*r. M[0,0]) > r1+r2 then exit.
R1 := c1. R. M[0]*ar. M[2,1]+c1. R. M[2]*ar. M[0,1].
R2 := c2. R. M[0]*ar. M[1,2]+c2. R. M[2]*ar. M[1,0].
If abs(t. M[0]*r. M[2,1]-t. M[2]*r. M[0,1]) > r1+r2 then exit.
R1 := c1. R. M[0]*ar. M[2,2]+c1. R. M[2]*ar. M[0,2].
R2 := c2. R. M[0]*ar. M[1,1]+c2. R. M[1]*ar. M[1,0].
If abs(t. M[0]*r. M[2,2]-t. M[2]*r. M[0,2]) > r1+r2 then exit.
R1 := c1. R. M[0]*ar. M[1,0]+c1. R. M[1]*ar. M[0,0].
R2 := c2. R. M[1]*ar. M[2,2]+c2. R. M[2]*ar. M[2,1].
If abs(t. M[1]*r. M[0,0]-t. M[0]*r. M[1,0]) > r1+r2 then exit.
R1 := c1. R. M[0]*ar. M[1,1]+c1. R. M[1]*ar. M[0,1].
R2 := c2. R. M[0]*ar. M[2,2]+c2. R. M[2]*ar. M[2,0].
If abs(t. M[1]*r. M[0,1]-t. M[0]*r. M[1,1]) > r1+r2 then exit.
R1 := c1. R. M[0]*ar. M[1,2]+c1. R. M[1]*ar. M[0,2].
R2 := c2. R. M[0]*ar. M[2,1]+c2. R. M[1]*ar. M[2,0].
If abs(t. M[1]*r. M[0,2]-t. M[0]*r. M[1,2]) > r1+r2 then exit.
Result := true.
End.
//------------------------------------------------------------------
Function ch_traslapacapsulacapsula (.
Const c1, c2: ch_rcapsula.
): bolean.
Var.
S, t, d2, r: single.
Pc1, pc2: gr_rvector3d.
Begin.
D2 := ch_mascercasegmentosegmento (c1. A, c1. B, c2. A, c2. B, t, pc1, pc2).
R := c1. R+c2. R.
Result := d2 <= r*r.
End.
//------------------------------------------------------------------
Function ch_traslapapolitopopolitopo (.
Const p1, p2: ch_rpolitopo // politopues del mismo orden par.
): bolean.
Var.
I: integer.
Begin.
Result := false.
For I := 0 todo (length(p1. Menores) shr 1)-1 do.
Begin.
If (p1. Menores[i] > p2. Mayores[i]) or (p1. Mayores[i] < p2. Menores[i]) then.
Exit.
End.
Result := true.
End.
End.
Mañana te explico, y te indico donde hay recursos que te puedan ayudar. Ya está un poco tarde por aquí.