ImplicitPolygonsImpl.mesa
Copyright Ó 1985, 1990 by Xerox Corporation. All rights reserved.
Bloomenthal, February 27, 1993 4:08 pm PST
DIRECTORY G2dBasic, G3dBasic, G3dOctree, G3dPolygon, G3dMatrix, G3dVector, ImplicitDefs, ImplicitPoints, ImplicitPolygons, ImplicitSurface, MessageWindow, IO, Real, Rope, RuntimeError;
ImplicitPolygonsImpl:
CEDAR
PROGRAM
IMPORTS G2dBasic, G3dBasic, G3dOctree, G3dPolygon, G3dMatrix, G3dVector, ImplicitPoints, ImplicitSurface, IO, MessageWindow, Real, Rope, RuntimeError
EXPORTS ImplicitPolygons
~
BEGIN
Triple: TYPE ~ G3dBasic.Triple;
NatSequence: TYPE ~ G3dBasic.NatSequence;
NatSequenceRep: TYPE ~ G3dBasic.NatSequenceRep;
SurfaceSequence: TYPE ~ G3dBasic.SurfaceSequence;
SurfaceSequenceRep: TYPE ~ G3dBasic.SurfaceSequenceRep;
TripleSequence: TYPE ~ G3dBasic.TripleSequence;
TripleSequenceRep: TYPE ~ G3dBasic.TripleSequenceRep;
Matrix: TYPE ~ G3dMatrix.Matrix;
Viewport: TYPE ~ G3dMatrix.Viewport;
Corner: TYPE ~ G3dOctree.Corner;
Corners: TYPE ~ G3dOctree.Corners;
Cross: TYPE ~ G3dOctree.Cross;
CrossedEdge: TYPE ~ G3dOctree.CrossedEdge;
CrossedEdges: TYPE ~ G3dOctree.CrossedEdges;
CrossPolygonProc: TYPE ~ G3dOctree.CrossPolygonProc;
CrossSequence: TYPE ~ G3dOctree.CrossSequence;
CrossSequenceRep: TYPE ~ G3dOctree.CrossSequenceRep;
Cube: TYPE ~ G3dOctree.Cube;
CubeProc: TYPE ~ G3dOctree.CubeProc;
Direction: TYPE ~ G3dOctree.Direction;
Edge: TYPE ~ G3dOctree.Edge;
Face: TYPE ~ G3dOctree.Face;
Octant: TYPE ~ G3dOctree.Octant;
ThreeEdges: TYPE ~ G3dOctree.ThreeEdges;
TwoOctants: TYPE ~ G3dOctree.TwoOctants;
PolygonProc: TYPE ~ G3dPolygon.PolygonProc;
PolygonOkProc: TYPE ~ ImplicitDefs.PolygonOkProc;
Surface: TYPE ~ ImplicitDefs.Surface;
ValueProc: TYPE ~ ImplicitDefs.ValueProc;
maxNTriples: CARDINAL ~ ImplicitDefs.maxNTriples;
maxNNats: CARDINAL ~ ImplicitDefs.maxNNats;
Polygonization
BoundsFault:
ERROR ~ RuntimeError.BoundsFault;
CrossPolygonizeCube:
PUBLIC
PROC [
cube: Cube,
crossPolygonProc: CrossPolygonProc,
scratchCrossSequence: CrossSequence ¬ NIL,
recurseTrackFace: BOOL ¬ TRUE]
RETURNS [result: ATOM ¬ $Normal]
~ {
Presumes a restricted octree.
Apply crossPolygonProc to each of the polygons in cube.
Result is $Normal, $RecurseTracked or $RecurseFailed.
IF ImplicitPoints.IsCrossed[cube]
AND
NOT ImplicitPoints.IsOutOfRange[cube]
THEN {
AddCrossToPolygon:
PROC [crossedEdge: CrossedEdge] ~ {
Find the surface point associated with this edge:
cross: Cross ¬ ImplicitPoints.CrossFromCrossedEdge[crossedEdge];
IF NOT cross.ok THEN nBadVertices ¬ nBadVertices+1;
And add it to the polygon:
IF scratchCrossSequence.length = scratchCrossSequence.maxLength
THEN {
old: CrossSequence ¬ scratchCrossSequence;
scratchCrossSequence ¬ NEW[CrossSequenceRep[2*scratchCrossSequence.length]];
FOR i: INT IN [0..old.length) DO scratchCrossSequence[i] ¬ old[i]; ENDLOOP;
scratchCrossSequence.length ¬ old.length;
};
scratchCrossSequence[scratchCrossSequence.length] ¬ cross;
scratchCrossSequence.length ¬ scratchCrossSequence.length+1;
};
RecursiveTrackFace:
PROC [cube: Cube, face: Face, edge: Edge]
RETURNS [Edge] ~ {
Polygonize the terminal cubes using a modified polygonization algorithm.
When proceeding around a face, if the face neighbor is not terminal, then proceed
(recursively if necessary) around the next level's face, as shown below, until the next
vertex, located on an edge belonging to the parent's face, is found.
[Artwork node; type 'Artwork on' to command tool]
Face tracking method
dFace: Direction ~ G3dOctree.DirectionFromFace[face];
dFaceOpp: Direction ~ G3dOctree.OppositeDirection[dFace];
corners: Corners ~ cube.corners;
octs: TwoOctants ~ G3dOctree.EdgeOctants[edge];
mid: Corner ~ cube.kids[octs.o0].corners[octs.o1];
octant: Octant ¬
IF mid.inside = corners[octs.o0].inside
THEN octs.o1
ELSE
IF mid.inside = corners[octs.o1].inside
THEN octs.o0
ELSE IF mid.inside THEN octs.o1 ELSE octs.o0; -- edge anomaly
DO
kid: Cube ¬ cube.kids[octant];
edges: ThreeEdges ~ G3dOctree.EdgesFromOctant[octant];
Find all the edges of kid that are crossed by the surface:
crossedEdges: CrossedEdges ~ ImplicitPoints.CubeCrossedEdges[kid];
IF
NOT kid.terminal
THEN edge ¬ RecursiveTrackFace[kid, face, edge]
ELSE {
start: Edge ¬ edge;
DO
edge ¬ G3dOctree.NextCCWEdge[edge, face]; -- CCW tracking!
IF edge = start THEN ERROR;
IF crossedEdges[edge].cIn # NIL THEN EXIT;
ENDLOOP;
AddCrossToPolygon[crossedEdges[edge]];
};
IF edge = edges.e0
OR edge = edges.e1
OR edge = edges.e2
THEN RETURN[edge]
ELSE {
prepare to track around edge neighbor:
dEdge: Direction ¬ G3dOctree.DirectionFromEdge[edge];
dOctant: Direction ¬ G3dOctree.DirectionFromOctant[octant];
d: Direction ¬ G3dOctree.AddDirection[dEdge, dFaceOpp];
dOctant ¬ G3dOctree.AddDirection[dOctant, d];
dOctant ¬ G3dOctree.AddDirection[dOctant, d];
octant ¬ G3dOctree.OctantFromDirection[dOctant];
edge ¬ G3dOctree.OppositeEdge[edge, face];
}
ENDLOOP;
};
NextCrossedEdge:
PROC [edge: Edge]
RETURNS [Edge] ~ {
Go CW around face until an edge with a surface vertex.
face: Face ~ G3dOctree.FaceFromEdgeOctant[edge, crossedEdges[edge].oOut];
neighbor: Cube ~ G3dOctree.FaceNeighbor[cube, face];
IF recurseTrackFace
AND neighbor #
NIL
AND
NOT neighbor.terminal
THEN {
We have a subdivision mismatch:
oppFace: Face ~ G3dOctree.OppositeFace[face];
invEdge: Edge ~ G3dOctree.InverseEdge[edge, face];
IF result = $Normal THEN result ¬ $RecurseTracked;
edge ¬ G3dOctree.InverseEdge[
RecursiveTrackFace[neighbor, oppFace, invEdge], oppFace];
}
ELSE {
start: Edge ¬ edge;
DO
edge ¬ G3dOctree.NextCWEdge[edge, face];
IF crossedEdges[edge].cIn # NIL THEN EXIT;
IF edge = start THEN ERROR RecurseError;
ENDLOOP;
AddCrossToPolygon[crossedEdges[edge]];
};
RETURN[edge];
};
Inner:
PROC
RETURNS [
BOOL] ~ {
done: ARRAY Edge OF BOOL ¬ ALL[FALSE];
nBadVertices ¬ 0;
FOR edge: Edge
IN Edge
DO
IF crossedEdges[edge].cIn #
NIL
AND
NOT done[edge]
THEN {
e, start: Edge ¬ edge;
scratchCrossSequence.length ¬ 0;
DO
e ¬ NextCrossedEdge[e ! RecurseError => GOTO recurseError];
done[e] ¬ TRUE;
IF e = start THEN EXIT;
ENDLOOP;
IF nBadVertices = scratchCrossSequence.length THEN RETURN[TRUE];
Create the actual polygon by calling the client-supplied procedure,
crossPolygonProc, with the polygon number and a sequence of vertex ids:
IF NOT crossPolygonProc[nPolygon, scratchCrossSequence] THEN RETURN[TRUE];
nPolygon ¬ nPolygon+1;
};
ENDLOOP;
RETURN[TRUE];
EXITS
recurseError => RETURN[FALSE];
};
RecurseError: ERROR = CODE;
nBadVertices, nPolygon: INT ¬ 0;
Find edges of cube crossed by the surface:
crossedEdges: CrossedEdges ~ ImplicitPoints.CubeCrossedEdges[cube];
IF scratchCrossSequence =
NIL
OR scratchCrossSequence.maxLength < 100
THEN scratchCrossSequence ¬ NEW[CrossSequenceRep[100]];
IF
NOT Inner[]
THEN {
recurseTrackFace ¬ FALSE;
result ¬ $RecurseFailed;
[] ¬ Inner[];
};
};
};
PolygonizeCube:
PUBLIC
PROC [
cube: Cube,
polygonProc: PolygonProc,
scratchPolygon: NatSequence ¬ NIL,
recurseTrackFace: BOOL ¬ TRUE]
RETURNS [result: ATOM ¬ $Normal]
~ {
crossPolygonProc: CrossPolygonProc ~ {
FOR n:
INT
IN [0..polygon.length)
DO
scratchPolygon[n] ¬ polygon[n].id;
ENDLOOP;
scratchPolygon.length ¬ polygon.length;
[] ¬ polygonProc[nPolygon, scratchPolygon];
};
crossSequence: CrossSequence ¬ G3dOctree.ObtainCrossSequence[];
IF scratchPolygon =
NIL
OR scratchPolygon.maxLength < 100
THEN scratchPolygon ¬ NEW[NatSequenceRep[100]];
result ¬ CrossPolygonizeCube[cube, crossPolygonProc, crossSequence, recurseTrackFace];
G3dOctree.ReleaseCrossSequence[crossSequence];
};
SetSurfacePolygons:
PUBLIC
PROC [
surface: Surface,
root: Cube,
triangulate: BOOL ¬ FALSE,
valueProc: ValueProc ¬ NIL,
threshold: REAL ¬ 0.0,
cubeProc: CubeProc ¬ NIL,
polygonOkProc: PolygonOkProc ¬ NIL,
clientData: REF ANY ¬ NIL]
RETURNS [message: ROPE]
~ {
TriangulateAbort: ERROR = CODE;
TerminalCubeProc: CubeProc ~ {
Finesse: PROC [length0: INT, poly1: NatSequence] ~ {
tripoints: G3dBasic.TripointSequence;
nPoints: INT ~ length0+poly1.length;
map: NatSequence ¬ NEW[NatSequenceRep[nPoints]];
points: TripleSequence ¬ NEW[TripleSequenceRep[nPoints]];
indices0: NatSequence ¬ NEW[NatSequenceRep[length0]];
indices1: NatSequence ¬ NEW[NatSequenceRep[poly1.length]];
poly0: NatSequence ¬ NEW[NatSequenceRep[length0]];
FOR n: INT IN [0..poly0.length ¬ length0) DO
poly0[n] ¬ polys[polys.length-length0+n];
ENDLOOP;
polys.length ¬ polys.length-length0-1;
surface.nPolygons ¬ surface.nPolygons-1;
points.length ¬ nPoints;
FOR n: INT IN [0..indices0.length ¬ poly0.length) DO
points[indices0[n] ¬ n] ¬ surface.vertices[map[n] ¬ poly0[n]].point;
ENDLOOP;
FOR n: INT IN [0..indices1.length ¬ poly1.length) DO
m: INT ~ n+poly0.length;
points[indices1[n] ¬ m] ¬ surface.vertices[map[m] ¬ poly1[n]].point;
ENDLOOP;
tripoints ¬ G3dPolygon.Triangulate2Polygons[indices0, indices1, points];
scratchPolygon.length ¬ 3;
FOR n: INT IN [0..tripoints.length) DO
scratchPolygon[0] ¬ map[tripoints[n].i2];
scratchPolygon[1] ¬ map[tripoints[n].i1];
scratchPolygon[2] ¬ map[tripoints[n].i0];
AddPolygonToSurface[scratchPolygon];
ENDLOOP;
};
AddPolygonToSurface:
PROC [polygon: NatSequence] ~ {
CheckLength:
PROC [n:
INT] ~ {
IF
CARD[polys.length+n+1] >= polys.maxLength
THEN
polys ¬ G2dBasic.LengthenNatSequence[polys !
RuntimeError.BoundsFault, Real.RealException => {
AddPolysToEndOfSurfaceList[polys]; -- first, store full sequence
polys ¬ NEW[NatSequenceRep[1000]]; -- now, start new sequence
CONTINUE;
}];
};
AddPolygon:
PROC [polygon: NatSequence] ~ {
surface.nPolygons ¬ surface.nPolygons+1;
CheckLength[polygon.length];
polys ¬ G2dBasic.AddToNatSequence[polys, polygon.length];
FOR n:
INT
IN [0..polygon.length)
DO
polys ¬ G2dBasic.AddToNatSequence[polys, polygon[n]];
ENDLOOP;
};
AddTriangle:
PROC [i1, i2, i3:
INT] ~ {
surface.nPolygons ¬ surface.nPolygons+1;
CheckLength[3];
polys ¬ G2dBasic.AddToNatSequence[polys, 3];
polys ¬ G2dBasic.AddToNatSequence[polys, i1];
polys ¬ G2dBasic.AddToNatSequence[polys, i2];
polys ¬ G2dBasic.AddToNatSequence[polys, i3];
};
IF polygon.length > 3
AND triangulate
AND valueProc #
NIL
THEN {
v1: REAL;
center, vector, point: Triple ¬ [];
FOR i:
INT
IN [0..polygon.length)
DO
center ¬ G3dVector.Add[center, surface.vertices[polygon[i]].point];
ENDLOOP;
point ¬ center ¬ G3dVector.Div[center, REAL[polygon.length]];
v1 ¬ valueProc[center, clientData];
vector ¬ ImplicitPoints.GetPointNormal[center, valueProc, v1, delta, clientData];
vector ¬ G3dVector.Mul[vector, delta];
IF (v1 ¬ valueProc[center, clientData]) < 0 THEN vector ¬ G3dVector.Negate[vector];
FOR i:
INT
IN [0..100)
DO
v2: REAL ¬ valueProc[point ¬ G3dVector.Add[point, vector], clientData];
IF (v2 > 0.0) # (v1 > 0.0)
THEN {
p: Triple ¬ ImplicitSurface.SegmentConverge[center, point, v1, v2, valueProc, threshold, clientData].point;
n: Triple ¬ ImplicitPoints.GetPointNormal[
p, valueProc, valueProc[p, clientData], delta, clientData];
vid: INT ¬ ImplicitPoints.AddSurfaceVertex[p, n, surface];
FOR j:
INT
IN [0..polygon.length)
DO
AddTriangle[vid, polygon[j], polygon[(j+1) MOD polygon.length]];
ENDLOOP;
EXIT;
};
REPEAT
FINISHED => {
MessageWindow.Append["can't triangulate "];
AddPolygon[polygon];
};
ENDLOOP;
}
ELSE AddPolygon[polygon];
};
StorePolygon: PolygonProc ~ {
IF polygonOkProc #
NIL
THEN {
scratchPoints.length ¬ scratchPolygon.length;
FOR i:
INT
IN [0..scratchPolygon.length)
DO
scratchPoints[i] ¬ surface.vertices[scratchPolygon[i]].point;
ENDLOOP;
IF NOT polygonOkProc[scratchPoints, clientData] THEN RETURN;
};
SELECT nPolygon
FROM
0 => {
length0 ¬ polygon.length;
AddPolygonToSurface[polygon];
cube.refAny ¬ polygon;
IF cubeProc # NIL AND NOT cubeProc[cube] THEN ERROR TriangulateAbort;
};
1 => Finesse[length0, polygon];
ENDCASE;
};
length0: INT;
delta: REAL ¬ IF triangulate AND valueProc # NIL THEN 0.01*cube.size ELSE 0.0;
SELECT PolygonizeCube[cube, StorePolygon, scratchPolygon]
FROM
$RecurseTracked => nRecursiveTrackFaces ¬ nRecursiveTrackFaces+1;
$RecurseFailed => nRecurseFailures ¬ nRecurseFailures+1;
ENDCASE;
};
AddPolysToEndOfSurfaceList:
PROC [polys: NatSequence] ~ {
IF surface.polygons =
NIL
THEN surface.polygons ¬ LIST[polys]
ELSE FOR l:
LIST
OF NatSequence ¬ surface.polygons, l.rest
DO
IF l.rest = NIL THEN {l.rest ¬ LIST[polys]; EXIT};
ENDLOOP;
};
nRecursiveTrackFaces, nRecurseFailures: INT ¬ 0;
scratchPolygon: NatSequence ¬ NEW[NatSequenceRep[24]];
scratchPoints: TripleSequence ¬ NEW[TripleSequenceRep[24]];
polys: NatSequence ¬ NEW[NatSequenceRep[MIN[maxNNats, MAX[1, surface.vertices.length]]]];
G3dOctree.ApplyToTerminal[root, TerminalCubeProc !
TriangulateAbort => {message ¬ Rope.Concat[message, " *aborted, "]; CONTINUE};
BoundsFault => {message ¬ Rope.Cat[message, " *polygons limited, "]; CONTINUE}
];
AddPolysToEndOfSurfaceList[polys];
message ¬ IO.PutFR["%g%g polygons", IO.rope[message], IO.int[surface.nPolygons]];
message ¬ IO.PutFR["%g (%g changes", IO.rope[message], IO.int[nRecursiveTrackFaces]];
message ¬ IO.PutFR["%g, %g failed)", IO.rope[message], IO.int[nRecurseFailures]];
};
Miscellany
ApplyToSurfacePolygons:
PUBLIC PROC [surface: Surface, polygonProc: PolygonProc] ~ {
IF surface #
NIL
AND surface.polygons #
NIL
THEN {
nPolygon: INT ¬ 0;
polygon: NatSequence ¬ NEW[NatSequenceRep[100]];
FOR l:
LIST
OF NatSequence ¬ surface.polygons, l.rest
WHILE l #
NIL
DO
index: CARDINAL ¬ 0;
polygons: NatSequence ~ l.first;
WHILE index < polygons.length
DO
polygon.length ¬ polygons[index];
index ¬ index+1;
FOR n:
INT
IN [0..polygon.length)
DO
polygon[n] ¬ polygons[index];
index ¬ index+1;
ENDLOOP;
IF NOT polygonProc[nPolygon, polygon] THEN RETURN;
nPolygon ¬ nPolygon+1;
ENDLOOP;
ENDLOOP;
};
};
ApplyToFrontFacingPolygons:
PUBLIC PROC [
surface: Surface,
view: Matrix,
viewport: Viewport,
polygonProc: PolygonProc]
~ {
abort: ERROR = CODE;
Inner: PolygonProc ~ {
Reverse the sense of the FrontFacing tests since implicit polygons are backwards:
do:
BOOL ¬
SELECT
TRUE
FROM
nPolygon >= surface.faceNormals.length => TRUE,
persp =>
NOT G3dVector.FrontFacingWithPerspective[
surface.faceNormals[nPolygon], surface.faceCenters[nPolygon], inverse],
ENDCASE =>
NOT G3dVector.FrontFacingNoPerspective[surface.faceNormals[nPolygon], view];
IF do AND NOT polygonProc[nPolygon, polygon] THEN ERROR abort;
};
inverse: Matrix;
persp: BOOL ¬ G3dMatrix.HasPerspective[view];
IF persp THEN inverse ¬ G3dMatrix.Invert[view, G3dMatrix.ObtainMatrix[]];
IF ImplicitSurface.VerticesOK[surface, view, viewport]
AND
ImplicitSurface.FaceNormalsCentersOK[surface]
THEN ApplyToSurfacePolygons[surface, Inner ! abort => CONTINUE];
G3dMatrix.ReleaseMatrix[inverse];
};
SetFaceNormalsCenters:
PUBLIC
PROC [surface: Surface, setNormals, setCenters:
BOOL ¬
TRUE]
~ {
IF surface #
NIL
AND surface.polygons #
NIL
AND (setNormals
OR setCenters)
THEN {
points: TripleSequence ~ NEW[TripleSequenceRep[24]];
normals: TripleSequence ¬ surface.faceNormals;
centers: TripleSequence ¬ surface.faceCenters;
polygonProc: PolygonProc ~ {
points.length ¬ polygon.length;
FOR n:
INT
IN [0..points.length)
DO
points[n] ¬ surface.vertices[polygon[n]].point;
ENDLOOP;
IF setNormals
THEN
normals ¬ G3dBasic.AddToTripleSequence[normals, G3dPolygon.PolygonNormal[points]];
IF setCenters
THEN
centers ¬ G3dBasic.AddToTripleSequence[centers, G3dPolygon.PolygonCenter[points]];
};
IF setNormals
AND (normals =
NIL
OR normals.maxLength < surface.nPolygons)
THEN normals ¬ NEW[TripleSequenceRep[MIN[maxNTriples, surface.nPolygons]]];
IF setCenters
AND (centers =
NIL
OR centers.maxLength < surface.nPolygons)
THEN centers ¬ NEW[TripleSequenceRep[MIN[maxNTriples, surface.nPolygons]]];
ApplyToSurfacePolygons[surface, polygonProc ! BoundsFault => CONTINUE];
surface.faceNormals ¬ normals;
surface.faceCenters ¬ centers;
};
};
DecodePolygons:
PUBLIC
PROC [surface: Surface]
RETURNS [polygons: SurfaceSequence] ~ {
IF surface #
NIL
AND surface.polygons #
NIL
THEN {
Decoder: PolygonProc ~ {
poly: NatSequence ¬ NEW[NatSequenceRep[polygon.length]];
polygons[nPolygon] ¬ [NIL, poly];
poly.length ¬ polygon.length;
FOR n:
INT
IN [0..polygon.length)
DO
poly[n] ¬ polygon[n];
ENDLOOP;
nPolygon ¬ nPolygon+1;
};
nPolygon: INT ¬ 0;
polygons ¬ NEW[SurfaceSequenceRep[surface.nPolygons]];
polygons.length ¬ surface.nPolygons;
ApplyToSurfacePolygons[surface, Decoder];
};
};
..
maxTripoints: CARDINAL = (LAST[CARDINAL]-4-SIZE[TripointSequenceRep[0]])/SIZE[Tripoint];
nTripoints: CARDINAL ¬ MIN[maxTripoints, MAX[1, 2*nPoints-4]];
FOR n:
INT
IN [1..poly.length-2]
DO
surface.tripoints ¬ AddTripoint[surface.tripoints, [poly[n+1], poly[n], poly[0]]];
ENDLOOP;
SetFaceNormals:
PUBLIC
PROC [surface: Surface] ~ {
IF surface #
NIL
AND surface.tripoints #
NIL
AND surface.vertices #
NIL
THEN {
num: INT ¬ surface.tripoints.length;
surface.faceNx ¬ NEW[RealSequenceRep[num]];
surface.faceNy ¬ NEW[RealSequenceRep[num]];
surface.faceNz ¬ NEW[RealSequenceRep[num]];
surface.faceNx.length ¬ surface.faceNy.length ¬ surface.faceNz.length ¬ num;
FOR n:
INT
IN [0..num)
DO
p0: Triple ~ surface.vertices[surface.tripoints[n].i0].point;
p1: Triple ~ surface.vertices[surface.tripoints[n].i1].point;
p2: Triple ~ surface.vertices[surface.tripoints[n].i2].point;
v: Triple ~ G3dPolygon.TriangleNormal[p0, p1, p2];
surface.faceNx[n] ¬ v.x;
surface.faceNy[n] ¬ v.y;
surface.faceNz[n] ¬ v.z;
ENDLOOP;
};
};
AddTripoint:
PUBLIC
PROC [tripoints: TripointSequence, tripoint: Tripoint]
RETURNS [TripointSequence]
~ {
IF tripoints.length >= tripoints.maxLength
THEN tripoints ¬ G3dBasic.LengthenTripointSequence[tripoints];
tripoints[tripoints.length] ¬ tripoint;
tripoints.length ¬ tripoints.length+1;
RETURN[tripoints];
};
NTripoints:
PUBLIC
PROC [surface: Surface]
RETURNS [
INTEGER] ~ {
RETURN[IF surface = NIL OR surface.tripoints = NIL THEN 0 ELSE surface.tripoints.length];
};
The following was an attempt in Triangulate[] to take the original polygon derived from the
cube's edge crossedEdges, approximate a central point, and form sub-triangles like pie slices. It
didn't work, probably because of problems in Jiggle[].
wheels: WheelSequence ¬ NEW[WheelSequenceRep[triangles.maxLength]];
polyPts: TripleSequence ¬ NEW[TripleSequenceRep[12]];
radius: REAL ~ 0.5*G3dOctree.Size[cube];
SELECT poly.length FROM
3 => AddTripoint[poly[0], poly[1], poly[2] ! BoundsFault => GOTO TriangleLimit];
> 3 => {
target: Target ¬ Jiggle[];
IF target.ok
THEN SpokePoly[NewPt[target.pt], poly ! BoundsFault => GOTO TriangleLimit]
ELSE SweepPoly[poly ! BoundsFault => GOTO TriangleLimit];
};
ENDCASE;
Jiggle: PROC RETURNS [target: Target] ~ {
FOR n: INT IN [0..poly.length) DO polyPts[n] ¬ points[poly[n]]; ENDLOOP;
polyPts.length ¬ poly.length;
{
v: Triple ~ Vector3d.Normalize[G3dPolygon.PolygonNormal[polyPts]];
a: Triple ~ PolygonCenter[polyPts];
aPot: REAL ~ valueProc[a];
b: Triple ¬ Vector3d.Ray[[a, v], 0.1*radius];
bPot: REAL ¬ valueProc[b];
IF (aPot > 0.0) = (bPot > 0.0)
THEN bPot ¬ valueProc[b ¬ Vector3d.Ray[[a, v], -0.1*radius]];
IF (aPot > 0.0) = (bPot > 0.0)
THEN target.ok ¬ FALSE
ELSE {
target ¬ Converge[a, b, aPot, bPot];
target.ok ¬ ImplicitSurface.PointInCube[target.pt, cube];
target.ok ¬ FALSE;
};
}
};
SpokePoly: PROC [id: INT, poly: REF NatSequence] ~ {
FOR n: INT IN [0..poly.length-1) DO AddTripoint[id, poly[n], poly[n+1]]; ENDLOOP;
AddTripoint[id, poly[poly.length-1], poly[0]];
wheels[wheels.length].id ¬ id;
FOR n: INT IN [0..poly.length) DO wheels[wheels.length].poly[n] ¬ poly[n]; ENDLOOP;
wheels.length ¬ wheels.length+1;
};
SweepPoly: PROC[poly: REF NatSequence] ~ {
FOR n: INT IN [2..poly.length) DO AddTripoint[poly[0], poly[n-1], poly[n]]; ENDLOOP;
};
PolygonCenter: PROC [points: TripleSequence] RETURNS [center: Triple ¬ origin] ~ {
IF points.length = 0 THEN RETURN;
FOR i: INT IN [0..points.length) DO center ¬ Vector3d.Add[center, points[i]]; ENDLOOP;
center ¬ Vector3d.Div[center, points.length];
};
In Triangulate[], to divide up polygon according to longest side:
(this didn't make much improvement, so the working code is kept simpler.)
FOR edge: Edge
IN Edge
DO
IF crossedEdges[edge].cIn #
NIL
AND
NOT done[edge]
THEN {
lengths: ARRAY [0..12) OF REAL;
e, start: Edge ¬ edge;
poly.length ¬ 0;
DO
e ¬ NextCWEdgeCrossed[e];
poly[poly.length] ¬ GetVertexId[crossedEdges[e] ! BoundsFault => GOTO PointsLimit];
poly.length ¬ poly.length+1;
done[e] ¬ TRUE;
IF e = start THEN EXIT;
ENDLOOP;
FOR n: INT IN [0..poly.length) DO
lengths[n] ¬ Vector3d.Square[
Vector3d.Sub[points[poly[n]], points[poly[(n+1) MOD poly.length]]]];
ENDLOOP;
WHILE poly.length > 3 DO
Tri: PROC [n0, n1, n2: INT] ~ {
NewTriangle[poly[n0], poly[n1], poly[n2]];
FOR n: INT IN [n1..poly.length-1) DO poly[n] ¬ poly[n+1]; ENDLOOP;
FOR n: INT IN [n1..poly.length-1) DO lengths[n] ¬ lengths[n+1]; ENDLOOP;
poly.length ¬ poly.length-1;
};
max: REAL ¬ 0.0;
n0, n1, n2, n3: INT;
FOR n: INT IN [0..poly.length) DO
IF lengths[n] > max THEN {n1 ¬ n; max ¬ lengths[n]};
ENDLOOP;
n0 ¬ IF n1 = 0 THEN poly.length-1 ELSE n1-1;
n2 ¬ (n1+1) MOD poly.length;
n3 ¬ (n2+1) MOD poly.length;
IF lengths[n0] > lengths[n2]
THEN Tri[n0, n1, n2 ! BoundsFault => GOTO TriangleLimit]
ELSE Tri[n1, n2, n3 ! BoundsFault => GOTO TriangleLimit];
ENDLOOP;
NewTriangle[poly[0], poly[1], poly[2] ! BoundsFault => GOTO TriangleLimit];
FOR n:
INT
IN [0..poly.length-2]
DO
NewTriangle[poly[0], poly[n], poly[n+1] ! BoundsFault => GOTO TriangleLimit];
ENDLOOP;
};
REPEAT
PointsLimit => NULL;
TriangleLimit => trianglesLimited ¬ TRUE;
ENDLOOP;