Package org.jmol.util
Class MeshCapper
java.lang.Object
org.jmol.util.MeshCapper
A class to properly cap a convoluted, closed slice of an isosurface
inspired by: Computational Geometry: Algorithms and Applications Mark de
Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf
Springer-Verlag, Berlin Heidelberg 1997 Chapter 3. Polygon Triangulation
Thanks given to Olaf Hall-Holt for pointing me to this reference.
Extensively modified:
- quaternion transform from 3D plane to XY plane for best precision
- using directional edges -- no angle measurements necessary
- continuous splitting off of triangles
- independent dynamic monotonic regions created and processed as one stream
- no need for vertex typing
- no push/pop stacks
INPUT: stream of [a b] ordered-vertex edges such that triangle a-b-c is
interior if (ab.cross.ac).dot.planeNormal > 0 (right-hand rule;
counter-clockwise edge flow)
Bob Hanson - Jan 11, 2015
- Author:
- Bob Hanson, hansonr@stolaf.edu
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate class
A class to provide linked vertices for MeshCapperclass
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate static final int
private Map<Integer,
MeshCapper.CapVertex> initialization onlyprivate static final int
private boolean
for debuggingprivate static final int
private javajs.util.Lst<MeshCapper.CapVertex[]>
dynamic region processing.private javajs.util.Lst<int[]>
(package private) javajs.util.M3
(package private) javajs.util.M3
private int
private int
informational onlyprivate int
informational onlyprivate MeshSlicer
source of edges; consumer of trianglesprivate javajs.util.Lst<MeshCapper.CapVertex>
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) void
addEdge
(int ipt1, int ipt2, int thisSet) Input method from MeshSlicer.private MeshCapper.CapVertex
addPoint
(int thisSet, int i) The MeshSlicer class manages all introduction of vertices; we must pass on to it the subset of vertices from the original Jmol isosurface being capped.private void
addTriangle
(MeshCapper.CapVertex v0, MeshCapper.CapVertex v1, MeshCapper.CapVertex v2, String note) Add the triangle and remove v1 from the chain.private boolean
Check for CCW winding.(package private) void
clear()
private static void
(package private) void
createCap
(javajs.util.V3 norm) Entry point when finished generating edges.private void
drawTriangle
(int index, MeshCapper.CapVertex v0, MeshCapper.CapVertex v1, MeshCapper.CapVertex v2, String color) for debuggingprivate MeshCapper.CapVertex
findNearestVertex
(javajs.util.Lst<MeshCapper.CapVertex> v1s, MeshCapper.CapVertex v0) Find the nearest vertex to v0 in the list v1s.private void
Generate yxNext links based on scanning Y large to small and if Y1==Y2, then X small to largeprivate javajs.util.T3
for debuggingprivate MeshCapper.CapVertex
Find the lowest ascender or descender above scan line bounding the region for this point.private boolean
isEdge
(int i, int j) private void
Add a new region to the list of regions.private void
outputTriangle
(int ipt1, int ipt2, int ipt3) Export triangle to MeshSlicerprivate MeshCapper.CapVertex
Handle the point; mark as processed.private void
processMonotonic
(MeshCapper.CapVertex v, boolean isDescending) Process a standard monotonic region, cleaving off as many triangles as possible.private MeshCapper.CapVertex
Process what M3O refer to as a "split" vertex, which we handle differently here, cloning the "helper" point and the "split" point, creating a new region if necessary, and then swapping pointers.set
(MeshSlicer slicer) int[][]
triangulateFaces
(int[][] faces, javajs.util.P3[] vertices, int[][] faceTriangles) generic entry for a set of facesint[][]
triangulatePolygon
(javajs.util.P3[] points, int nPoints) generic entry for a polygon
-
Field Details
-
slicer
source of edges; consumer of triangles -
dumping
private boolean dumpingfor debugging -
capMap
initialization only -
vertices
-
lstRegions
dynamic region processing. These are just [DESCENDER, ASCENDER, LAST] for each region -
DESCENDER
private static final int DESCENDER- See Also:
-
ASCENDER
private static final int ASCENDER- See Also:
-
LAST
private static final int LAST- See Also:
-
nTriangles
private int nTrianglesinformational only -
nRegions
private int nRegionsinformational only -
lstTriangles
private javajs.util.Lst<int[]> lstTriangles -
nPoints
private int nPoints -
m3
javajs.util.M3 m3 -
m3inv
javajs.util.M3 m3inv
-
-
Constructor Details
-
MeshCapper
public MeshCapper()
-
-
Method Details
-
set
- Parameters:
slicer
-- Returns:
- this
-
clear
void clear() -
triangulateFaces
public int[][] triangulateFaces(int[][] faces, javajs.util.P3[] vertices, int[][] faceTriangles) generic entry for a set of faces- Parameters:
faces
- array of pointers into pointsvertices
-faceTriangles
- optional return list by face- Returns:
- array of triangles [a b c mask]
-
triangulatePolygon
public int[][] triangulatePolygon(javajs.util.P3[] points, int nPoints) generic entry for a polygon- Parameters:
points
-nPoints
- number of points or -1- Returns:
- int[][i j k mask]
-
addEdge
void addEdge(int ipt1, int ipt2, int thisSet) Input method from MeshSlicer. Pointers are into MeshSlicer.m.vs[]- Parameters:
ipt1
-ipt2
-thisSet
-
-
addPoint
The MeshSlicer class manages all introduction of vertices; we must pass on to it the subset of vertices from the original Jmol isosurface being capped.- Parameters:
thisSet
-i
-- Returns:
- a CapVertex pointing to this new point in the isosurface or one we already have
-
getInputPoint
for debugging- Parameters:
v
-- Returns:
- external point or test point
-
outputTriangle
private void outputTriangle(int ipt1, int ipt2, int ipt3) Export triangle to MeshSlicer- Parameters:
ipt1
-ipt2
-ipt3
-
-
isEdge
private boolean isEdge(int i, int j) -
createCap
void createCap(javajs.util.V3 norm) Entry point when finished generating edges.- Parameters:
norm
-
-
fixEndsAndSortVertices
Generate yxNext links based on scanning Y large to small and if Y1==Y2, then X small to large- Parameters:
vs
-
-
findNearestVertex
private MeshCapper.CapVertex findNearestVertex(javajs.util.Lst<MeshCapper.CapVertex> v1s, MeshCapper.CapVertex v0) Find the nearest vertex to v0 in the list v1s.- Parameters:
v1s
-v0
-- Returns:
- nearest vertex or null if we can't match
-
process
Handle the point; mark as processed.- Parameters:
v
-- Returns:
- next point to process
-
clearV
-
processMonotonic
Process a standard monotonic region, cleaving off as many triangles as possible.- Parameters:
v
-isDescending
-
-
processSplit
Process what M3O refer to as a "split" vertex, which we handle differently here, cloning the "helper" point and the "split" point, creating a new region if necessary, and then swapping pointers.- Parameters:
v
-last
- "helper" or left edge- Returns:
- new point clone of this
-
newRegion
Add a new region to the list of regions.- Parameters:
v
-
-
getLastPoint
Find the lowest ascender or descender above scan line bounding the region for this point. In the case of a region that consists of a single edge with descender above ascender, this will return the ascender. In the case where there are two independent regions, it is possible for the lowest to be missed, but to no import. [This is MOST confusing in the M3O book.]- Parameters:
v
-- Returns:
- pt
-
checkWinding
private boolean checkWinding(MeshCapper.CapVertex v0, MeshCapper.CapVertex v1, MeshCapper.CapVertex v2) Check for CCW winding.- Parameters:
v0
-v1
-v2
-- Returns:
- true if properly wound -- (v1-v0).cross.(v2-v0).dot.norm > 0
-
addTriangle
private void addTriangle(MeshCapper.CapVertex v0, MeshCapper.CapVertex v1, MeshCapper.CapVertex v2, String note) Add the triangle and remove v1 from the chain.- Parameters:
v0
-v1
-v2
-note
-
-
drawTriangle
private void drawTriangle(int index, MeshCapper.CapVertex v0, MeshCapper.CapVertex v1, MeshCapper.CapVertex v2, String color) for debugging- Parameters:
index
-v0
-v1
-v2
-color
-
-