
DIRECTORY G3dBasic, G3dOctree, G3dVector, ImplicitDefs, ImplicitPoints, ImplicitRayTrace, Rope, ViewerClasses, G3dRayCube;

ImplicitRayTraceImpl: CEDAR PROGRAM

IMPORTS G3dRayCube, G3dVector, ImplicitPoints
EXPORTS ImplicitRayTrace

~ BEGIN
Ray:				TYPE ~ G3dBasic.Ray;
Triple:			TYPE ~ G3dBasic.Triple;
Cube:				TYPE ~ G3dOctree.Cube;
Intersection:		TYPE ~ G3dOctree.Intersection;
IntersectionList:	TYPE ~ G3dOctree.IntersectionList;
Octree:			TYPE ~ G3dOctree.Octree;
ROPE:				TYPE ~ Rope.ROPE;
NormalProc:		TYPE ~ ImplicitDefs.NormalProc;
Target:			TYPE ~ ImplicitDefs.Target;
ValueProc:		TYPE ~ ImplicitDefs.ValueProc;
RayHit:			TYPE ~ ImplicitRayTrace.RayHit;
RayHitList:		TYPE ~ ImplicitRayTrace.RayHitList;
SurfacePoint:		TYPE ~ ImplicitRayTrace.SurfacePoint;
ClickProc:		TYPE ~ ViewerClasses.ClickProc;
Error: PUBLIC ERROR [reason: ROPE] = CODE;

recurseMax: NAT ~ 16;

Converge: PROC [
in, out: Intersection,
valueProc: ValueProc,
threshold: REAL м 1.0,
clientData: REF ANY,
epsilon: REAL,
depth: NAT м 0]
RETURNS [hit: RayHit]
~ {
Inner: PROC [in, out: Intersection, depth: NAT] ~ {
midPoint: Triple м G3dVector.Midpoint[in.point, out.point];
midValue: REAL м valueProc[midPoint, clientData];
midT: REAL м 0.5*(in.t+out.t);
IF G3dVector.SquareDistance[in.point, out.point] > epsilon AND depth < recurseMax
THEN {
IF midValue < threshold
THEN Inner[in, [,, midT, midPoint, midValue], depth+1]
ELSE  Inner[[,, midT, midPoint, midValue], out, depth+1];
}
ELSE hit м [midPoint, midValue, midT];
};
Inner[in, out, depth];
};

GetRayHit: PUBLIC PROC [
i0, i1: Intersection, 
valueProc: ValueProc,
threshold: REAL м 1.0,
clientData: REF ANY м NIL,
epsilon: REAL м 0.0]
RETURNS [hit: RayHit]
~ {
IF (i0.value > threshold) # (i1.value > threshold) THEN {	-- Bingo!
IF i0.value > threshold
THEN {
hit м Converge[i0, i1, valueProc, threshold, clientData, epsilon, 0];
hit.type м leaving;		-- i0.point is in, i1.point is out
}
ELSE {
hit м Converge[i1, i0, valueProc, threshold, clientData, epsilon, 0];
hit.type м entering;		-- i1.point is in, i0.point is out
};
};
};

GetRayHits: PUBLIC PROC [
i0, i1: Intersection, 
valueProc: ValueProc,
threshold: REAL м 1.0,
clientData: REF ANY м NIL,
epsilon: REAL м 0.0]
RETURNS [hits: RayHitList]
~ {
IF (i0.value > 0.0) # (i1.value > 0.0)
THEN RETURN[LIST[GetRayHit[i0, i1, valueProc, threshold, clientData, epsilon]]]
ELSE {
Test: PROC [i0, i1: Intersection, depth: NAT] RETURNS [found: BOOL м FALSE] ~ {
IF depth < recurseMax THEN {
midPoint: Triple м G3dVector.Midpoint[i0.point, i1.point];
midValue: REAL м valueProc[midPoint, clientData];
IF (midValue > 0.0) # (i0.value > 0.0)	-- Bingo!
THEN {
new: NAT м depth+1;
midI: Intersection м [,, 0.5*(i0.t+i1.t), midPoint, midValue];
hit0:RayHitмConverge[i0, midI, valueProc, threshold, clientData, epsilon, new];
hit1:RayHitмConverge[midI, i1, valueProc, threshold, clientData, epsilon, new];
IF i0.value > 0.0
THEN {hit0.type м leaving; hit1.type м entering}
ELSE  {hit0.type м entering; hit1.type м leaving};
hits м LIST[hit0, hit1];
found м TRUE;
}
ELSE IF ABS[midValue] < MIN[ABS[i0.value], ABS[i1.value]] THEN {
newDepth: NAT м depth+1;
midI: Intersection м [,, 0.5*(i0.t+i1.t), midPoint, midValue];
found м Test[i0, midI, newDepth] OR Test[midI, i1, newDepth];
};
}
};
[] м Test[i0, i1, 0];
};
};

RayIntersections: PUBLIC PROC [
ray: Ray,
octree: Octree,
valueProc: ValueProc,
threshold: REAL м 1.0,
clientData: REF ANY м NIL]
RETURNS [hits: RayHitList]
~ {
list: IntersectionList м G3dRayCube.IntersectRayWithOctree[ray, octree];
IF list # NIL THEN {
ReverseList: PROC [in: RayHitList] RETURNS [out: RayHitList] ~ {
FOR l: RayHitList м in, l.rest WHILE l # NIL DO out м CONS[l.first, out]; ENDLOOP;
};
i0: Intersection м list.first;
i0.value м valueProc[i0.point, clientData];
FOR l: IntersectionList м list.rest, l.rest WHILE l # NIL DO
i1: Intersection м l.first;
IF i1.t # i0.t THEN {
v: REAL м i1.value м valueProc[i1.point, clientData];
gets:RayHitList мGetRayHits[i0, i1, valueProc, threshold, clientData, .0001*i0.cube.size];
IF gets # NIL THEN {
IF gets.rest # NIL THEN hits м CONS[gets.rest.first, hits];
hits м CONS[gets.first, hits];
};
i0 м i1;
};
ENDLOOP;
hits м ReverseList[hits];
};
};

RayIntersection: PUBLIC PROC [
ray: Ray,
octree: Octree,
valueProc: ValueProc,
threshold: REAL м 1.0,
clientData: REF ANY м NIL]
RETURNS [hit: RayHit]
~ {
list: IntersectionList м G3dRayCube.IntersectRayWithOctree[ray, octree];
IF list # NIL THEN {
i0: Intersection м list.first;
i0.value м valueProc[i0.point, clientData];
FOR l: IntersectionList м list.rest, l.rest WHILE l # NIL DO
i1: Intersection м l.first;
IF i1.t # i0.t THEN {
v: REAL м i1.value м valueProc[i1.point, clientData];
hits:RayHitList мGetRayHits[i0, i1, valueProc, threshold, clientData, .0001*i0.cube.size];
IF hits # NIL THEN RETURN[hits.first];
i0 м i1;
};
ENDLOOP;
};
};

RayAtSurface: PUBLIC PROC [
ray: Ray,
octree: Octree,
valueProc: ValueProc,
threshold: REAL м 1.0,
normalProc: NormalProc м NIL,
clientData: REF ANY м NIL]
RETURNS [s: SurfacePoint]
~ {
hit: RayHit м RayIntersection[ray, octree, valueProc, threshold, clientData];
IF hit.type # empty THEN {
s.point м hit.point;
s.value м hit.value;
s.normal м IF normalProc # NIL
THEN normalProc[s.point, hit.value, clientData]
ELSE ImplicitPoints.GetPointNormal[
hit.point, valueProc, hit.value+threshold, 0.005, clientData];
};
};

RayThroughSurface: PUBLIC PROC [
ray: Ray,
octree: Octree,
valueProc: ValueProc,
threshold: REAL м 1.0,
clientData: REF ANY м NIL]
RETURNS [thickness: REAL м 0.0, firstHit: RayHit]
~ {
hits: RayHitList м RayIntersections[ray, octree, valueProc, threshold, clientData];
IF hits # NIL THEN {
h0: RayHit м firstHit м hits.first;
FOR l: RayHitList м hits.rest, l.rest WHILE l # NIL DO
h1: RayHit м l.first;
IF h0.type = entering AND h1.type = leaving THEN thickness м thickness+h1.t-h0.t;
h0 м h1;
IF l.rest = NIL AND h1.type = entering THEN {
i0: Intersection м [entering, none, l.first.t, l.first.point, l.first.value];
i1: Intersection м [leaving, none, l.first.t, l.first.point, l.first.value];
FOR n: NAT IN [0..10) DO
i1.t м i1.t+octree.terminalRadius;
i1.point м G3dVector.ScaleRay[[i1.point, ray.axis], octree.terminalRadius];
IF (i1.value м valueProc[i1.point, clientData]) < 0.0 THEN {
hit: RayHit м Converge[
i0, i1, valueProc, threshold, clientData, .0001*octree.terminalRadius, 0];
thickness м thickness+i0.t-hit.t;
RETURN;
};
ENDLOOP;
thickness м 1.0;
};
ENDLOOP;
};
};

InShadow: PUBLIC PROC [
octree: Octree,
surfacePoint, lightDirection: Triple,
valueProc: ValueProc,
threshold: REAL м 1.0,
clientData: REF ANY м NIL]
RETURNS [BOOL]
~ {
nudged: Triple м G3dVector.ScaleRay[[surfacePoint, lightDirection], -0.0001];
l: IntersectionList м G3dRayCube.IntersectRayWithOctree[[nudged, lightDirection], octree];
IF l = NIL
THEN RETURN[FALSE]
ELSE {
i0: Intersection м l.first;
i0.value м valueProc[i0.point, clientData];
FOR ll: IntersectionList м l.rest, ll.rest WHILE ll # NIL DO
i1: Intersection м ll.first;
IF i1.t # i0.t THEN {
i1.value м valueProc[i1.point, clientData];
IF AnyHit[i0, i1, valueProc, threshold, clientData] THEN RETURN[TRUE];
i0 м i1;
};
ENDLOOP;
RETURN[FALSE];
};
};

AnyHit: PUBLIC PROC [
i0, i1: Intersection,
valueProc: ValueProc,
threshold: REAL м 1.0,
clientData: REF ANY м NIL]
RETURNS [BOOL]
~ {
Test: PROC [i0, i1: Intersection, depth: NAT] RETURNS [found: BOOL м FALSE] ~ {
IF depth < recurseMax THEN {
midPoint: Triple м G3dVector.Midpoint[i0.point, i1.point];
midValue: REAL м valueProc[midPoint, clientData];
IF (midValue > threshold) # (i0.value > threshold)
THEN RETURN[TRUE]
ELSE IF ABS[midValue] < MIN[ABS[i0.value], ABS[i1.value]] THEN {
newDepth: NAT м depth+1;
midI: Intersection м [,, 0.5*(i0.t+i1.t), midPoint, midValue];
RETURN[Test[i0, midI, newDepth] OR Test[midI, i1, newDepth]];
};
};
};
RETURN[IF (i0.value > threshold) # (i1.value > threshold) THEN TRUE ELSE Test[i0, i1, 0]];
};

END.
  F  
ImplicitRayTraceImpl.mesa
Copyright ╙ 1985, 1990 by Xerox Corporation.  All rights reserved.
Bloomenthal, August 11, 1992 4:07 pm PDT
Types
Ray Tracing Implicit Functions
ray.axis м G3dVector.Normalize[ray.axis];	-- so 2t is in distance units
Shouldn't the nudge amount be positive?
Reject any hit that has .t < 1e-4?
 Э╩
(  ХNewlineDelimiter
Щ ЩJЪЬBЩBJЩ(JШ JЪ╧k	ЬqШzJШ ЧЪ╨blЬЭЬЭШ#JШ JЪЭЬ&Ш-JЪЭЬШJШ ЧJЪЬЭШheadЪ╧lЩJЪЬЭЬШJЪЬЭЬШ!JЪЬЭЬШJЪЬЭЬШ-JЪЬЭЬШ4JЪЬЭЬШ"JЪЭЬЭЬЭЬШJЪЬЭЬШ,JЪЬЭЬШ%JЪЬЭЬШ*JЪЬЭЬШ)JЪЬЭЬШ0JЪЬЭЬ!Ш4JЪЬЭЬШ+ЧЪЯЩcodeЪ
╧nЬЭЬЭЬ
ЭЬЭЬШ*LШ ЧЪЬЭЬШLШ ЧЪаЬЭЬШJШJШJЪЬЭЬШJЪЬЭЬЭЬШJЪЬ	ЭЬШJЪЬЭЬШЪЭЬШJШЧЪаЬЭЬ ЭЬШ3JШ;JЪЬ
ЭЬ#Ш1JЪЬЭЬШЪЭЬ9ЭЬШQЪЭЬШЪЭЬШJЪЭЬ╧bЬ,Ш6JЪЭЬбЬ.Ш9ЧJШЧJЪЭЬ"Ш&ЧJШЧJШJШJШ ЧЪа	ЬЭЬЭЬШJШJШJЪЬЭЬШJЪЬЭЬЭЬЭЬШJЪЬ	ЭЬШJЪЭЬШJШЪЭЬ0ЭЬ╨biШCЪЭЬШЪЭЬШJШEJЪЬ╧c"Ш7JШЧЪЭЬШJШEJЪЬг"Ш8JШЧЧJШЧJШJШ ЧЪа
ЬЭЬЭЬШJШJШJЪЬЭЬШJЪЬЭЬЭЬЭЬШJЪЬ	ЭЬШJЪЭЬШJШЪЭЬ$Ш&JЪЭЬЭЬЭЬ?ШOЪЭЬШЪаЬЭЬЭЬЭЬ	ЭЬЭЬШOЪЭЬЭЬШJШ:JЪЬ
ЭЬ#Ш1ЪЭЬ(вШ0ЪЭЬШJЪЬЭЬШJШ>JЪЬ╧sЬдЬ
дЬ
дЬдЬдЬШOJЪЬдЬдЬдЬ
дЬ
дЬдЬдЬШOЪЭЬШJЪЭЬ,Ш0JЪЭЬ.Ш2ЧJЪЬЭЬШJЪЬЭЬШJШЧЪЭЬЭЬЭЬЭЬЭЬЭЬЭЬШ@JЪЬ
ЭЬШJШ>JЪЬбЬЭЬбЬШ=JШЧЧJШЧJШЧJШJШЧЧJШJШ ЧЪаЬЭЬЭЬШJШ	JШJШJЪЬЭЬШJЪЬЭЬЭЬЭЬШJЪЭЬШJШJШHЪЭЬЭЬШЪаЬЭЬЭЬШ@JЪЭЬЭЬЭЬЭЬЭЬЭЬШRJШЧJШJШ+ЪЭЬ)ЭЬЭЬЭШ<JШЪЭЬЭЬШJЪЬЭЬ.Ш5JЪЬдЬдЬдЬ
дЬ
дЬдЬШZЪЭЬЭЬЭЬШJЪЭЬЭЬЭЬЭЬШ;JЪЬЭЬШJШЧJШJШЧJЪЭЬШЧJШJШЧJШJШ ЧЪаЬЭЬЭЬШJШ	JШJШJЪЬЭЬШJЪЬЭЬЭЬЭЬШJЪЭЬШJШJШHЪЭЬЭЬШJШJШ+ЪЭЬ)ЭЬЭЬЭШ<JШЪЭЬЭЬШJЪЬЭЬ.Ш5JЪЬдЬдЬдЬ
дЬ
дЬдЬШZJЪЭЬЭЬЭЬЭЬШ&JШJШЧJЪЭЬШЧJШЧJШJШ ЧЪаЬЭЬЭЬШJШ	JШJШJЪЬЭЬШJЪЬЭЬШJЪЬЭЬЭЬЭЬШJЪЭЬШJШJШMЪЭЬЭЬШJШJШЪЬЭЬЭШJЪЭЬ+Ш/ЪЭЬШ#JЪЬ>Ш>ЧЧJШЧJШJШ ЧЪаЬЭЬЭЬШ JШ	JШJШJЪЬЭЬШJЪЬЭЬЭЬЭЬШJЪЭЬЭЬШ1JШJЪЬ*г╨cmгЩGJШSЪЭЬЭЬЭЬШJШ#ЪЭЬ#ЭЬЭЬЭШ6JШJЪЭЬЭЬЭЬ!ШQJШЪЭЬ
ЭЬЭЬЭЬШ-JШMJШLЪЭЬЭЬЭЬ	ЭШJШ"JШKЪЭЬ4ЭЬШ<ШJШJЧJШ!JЪЭЬШJШЧJЪЭЬШЧJШJШЧJЪЭЬШЧJШЧJШJШ ЧЪаЬЭЬШJШJШ%JШJЪЬЭЬШJЪЬЭЬЭЬЭЬШJЪЭЬЭЬШJШJЩ'JШMJШZЪЭЬЭШ
JЪЭЬЭЬЭЬШЪЭЬШJШJШ+ЪЭЬ(ЭЬЭЬЭШ<JШЪЭЬЭЬШJШ+JЩ"JЪЭЬ2ЭЬЭЬЭЬШFJШJШЧJЪЭЬШЧJЪЭЬЭЬШJШЧЧJШJШ ЧЪаЬЭЬЭЬШJЪЬШJЪЬШJЪЬЭЬШJЪЬЭЬЭЬЭЬШJЪЭЬЭЬШJШЪаЬЭЬЭЬЭЬ	ЭЬЭЬШOЪЭЬЭЬШJШ:JЪЬ
ЭЬ#Ш1ЪЭЬ0Ш2JЪЭЬЭЬЭЬШЪЭЬЭЬЭЬЭЬЭЬЭЬЭЬШ@JЪЬ
ЭЬШJШ>JЪЭЬбЬЭЬбЬШ=JШЧЧJШЧJШЧJЪ
ЭЬЭЬ1ЭЬЭЬЭЬШZJШЧЧJШ JЪЭЬШЧ ЕЧ    ш  *V  