ImplicitRayTraceImpl.mesa
Copyright Ó 1985, 1990 by Xerox Corporation. All rights reserved.
Bloomenthal, August 11, 1992 4:07 pm PDT
DIRECTORY G3dBasic, G3dOctree, G3dVector, ImplicitDefs, ImplicitPoints, ImplicitRayTrace, Rope, ViewerClasses, G3dRayCube;
ImplicitRayTraceImpl: CEDAR PROGRAM
IMPORTS G3dRayCube, G3dVector, ImplicitPoints
EXPORTS ImplicitRayTrace
~ BEGIN
Types
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;
Ray Tracing Implicit Functions
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]
~ {
ray.axis ¬ G3dVector.Normalize[ray.axis]; -- so t is in distance units
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]
~ {
Shouldn't the nudge amount be positive?
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];
Reject any hit that has .t < 1e-4?
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.