Package gov.nih.mipav.view.renderer.J3D.surfaceview

Class Geodesic

java.lang.Object

gov.nih.mipav.view.renderer.J3D.surfaceview.Geodesic

All Implemented Interfaces:

KeyListener, MouseListener, MouseMotionListener, EventListener

public class Geodesic
extends Object
implements MouseListener, MouseMotionListener, KeyListener

Introduction: The goal of this task is to add the ability for the user to draw a region of interest on a triangle mesh surface, by allowing the user to select points on the mesh surface and calculating the connecting polyline on the surface between the points. Pairs of consecutive points are connected by a geodesics path. The geodesic path is the shortest surface path between the points. For a triangle mesh, the final boundary curve for the region of interest is a polyline. To compute the polyline curve I start with Dijkstra's Single-Source Shortest Path graph algorithm to find the shortest path along triangle edges between the pair of points on the mesh. In the algorithm, the triangle vertices and edges are the nodes and edges of the graph, and the Euclidean distance between vertices connected by an edge serves as the edge weight. The result of Dijkstra's algorithm is a path that follows the edges in the mesh and may be jagged. I then iterate over the points on the polyline curve and the edges of the triangle mesh the curve crosses, to compute new points on the curve that lie on the triangle edges but not necessarily on the triangle vertices. This produces a smoother curve. Implementation: Drawing the user-selected region of interest on a surface is implemented through the Geodesic class in Geodesic.java. The Geodesic class may be used in two different ways. It may be used as a MouseListener that implements picking points on the surface of the mesh with the mouse and drawing the region of interest directly on the mesh. Or it may be used just to calculate the geodesic curve between two points on the triangle mesh. When the Geodesic class is used just to calculate the geodesic curve between two points on the triangle mesh, the points on the mesh must be specified prior to calculation. The points may be determined through a different picking implementation, or may be determined some other way. The interface to the Geodesic class allows the programmer to set the end points directly and to read the resulting geodesic curve. Calculating the Geodesic Curve The first step in calculating the geodesic curve on the triangle mesh, whether the Geodesic class implements MouseListener or not, is to initialize the local copy of the triangle mesh and the Single-Source Shortest Path Algorithm data structures based on the locations of the two endpoints of the path. The two endpoints of the path are specified in local mesh coordinates. They are not restricted to vertices in the triangle mesh, but may fall inside a triangle. When the endpoints fall inside a triangle, the triangle is divided into three new triangles, by connecting the new vertex to each of the three triangle vertices. This modification only affects the local copy of the triangle mesh. In Dijkstra's Single-Source Shortest Path Algorithm, each vertex and edge in the mesh has a weight; vertex weights represent the distance from the source vertex to that vertex, edge weights represent the distance between the two vertices the edge connects. In this implementation of Dijkstra's algorithm the edge weight is the Euclidean distance between the two vertices. Optimization: At the start of the algorithm each vertex is initialized to Float.MAX_VALUE, to represent the distance from the start node to that node has not yet been determined. Because the nodes and edges fall on a triangle mesh, where distances are based on actual distances in 3-dimensions, we can use an optimization to the standard Dijkstra's algorithm. This optimization uses an additional weight factor, which is the straight-line distance from the vertex to the end vertex. This is calculated for each vertex in the triangle mesh. Dijkstra's algorithm is a Greedy Algorithm. As it proceeds, points are examined, "relaxed", and potentially added to the final path based on the distance from the start vertex - the vertex not yet on the shortest path with the lowest weight is examined first. In the optimized version, the vertex with the lowest weight plus the lowest straight-line distance to the end point is examined, or "relaxed" first. This causes the area of vertices that Dijkstra's algorithm searches to be weighted in the direction of the end vertex. A non-optimized search pattern is symmetrical, and spreads out in a spherical pattern around the start vertex. The optimized search pattern appears conical, and points in the direction of the end vertex. Dijkstra's algorithm returns a list of points on the triangle mesh that connect the start and end vertices. The path travels along edges in the mesh and so may appear jagged. The final step in the Geodesic class algorithm is to smooth the polyline by moving points that fall on triangle vertices along the triangle edges. The final polyline contains points that are on triangle mesh edges, but are not constrained to the triangle vertices. The smoothing process is iterative. Given two points in the polyline that are connected by a path that goes through one triangle vertex, the intermediate vertex is moved across the edges that extend from it, until a new position is found that minimizes the distance between the two points. If more than one edge is crossed, then a new vertex for each new edge crossed is added to the polyline. The smoothing proceeds for each pair of points on the polyline. Added 7/31/05: LiveWire mode. LiveWire mode enables the user to interactively watch the Dijkstra's path being drawn between the last point placed on the curve to the current mouse location. LiveWire mode does not compute the smoothed geodesic interactively, but instead, waits for the user to place points on Dijkstra's curve and then finish the curve -- by pressing either the "Finish Open" or "Finish Closed" buttons in the interface. Once the curve is finished, then the smoothed geodesic is calculated and the triangle mesh is re-triangulated along the curve. Added: Cutting the mesh along the Geodesic.

Author:

Alexandra Bokinsky, Ph.D. Under contract from Magic Software.

See Also:

• ViewJFrameVolumeView

Field Summary

Fields

Modifier and Type	Field	Description
private boolean[]	m_abRemoveTris	DOCUMENT ME!
private int[]	m_aiEndIndex	DOCUMENT ME!
private int[]	m_aiFirstIndex	DOCUMENT ME!
private int[]	m_aiIndex	vertices array.
private int[]	m_aiIndexShift	DOCUMENT ME!
private int[]	m_aiPreviousStartIndex	DOCUMENT ME!
private int[]	m_aiStartIndex	The index values in the Vertex array for the triangle that the Start, First, and End points fall in, if they are inside a triangle and not on a triangle vertex:.
private javax.vecmath.Color4f[]	m_akColors	triangle color array.
private javax.vecmath.Point3f[]	m_akCoordinates	triangle index coordinate array.
private LinkedList[]	m_akEdgeList	Data members used in Dijkstra's search.
private javax.vecmath.Vector3f[]	m_akNormals	triangle normal array.
private javax.vecmath.TexCoord3f[]	m_akTexCoords	triangle texture coordinate array.
private boolean	m_bDisplayDijkstra	toggle for displaying Dijkstra's path as well as the smoothed path:.
private boolean	m_bEnabled	Turned on when picking with the mouse is enabled:.
private boolean	m_bEndpointChanged	Flag to indicates end ponit changes.
private boolean	m_bFinished	Closing the Geodesic path:.
private boolean	m_bFirstWire	DOCUMENT ME!
private boolean	m_bGroupAdded	Flag for clearing the Geodesic curves, if it is false, no curves have been added to the GeodesicGroup.
private boolean	m_bLastWire	DOCUMENT ME!
private boolean	m_bLivewire	Live wire or point and click mode:.
private boolean	m_bMouseMotion	DOCUMENT ME!
private boolean	m_bMousePressed	Mouse events.
private boolean	m_bMouseReleased	DOCUMENT ME!
private boolean	m_bOpen	Close path or not.
private boolean[]	m_bRelaxed	DOCUMENT ME!
private float	m_fDijkstraPathLength	Path length statistics for each type of path:.
private float	m_fEpsilon	Error correction Epsilon.
private float	m_fRadius	Radius of the sphere displayed to mark the points on the Geodesic.
private float[]	m_fRemainingWeight	Weights, relaxed flags, and previous vertex index for Dijkstra's search:.
private float	m_fSmoothedPathLength	DOCUMENT ME!
private float[]	m_fWeight	DOCUMENT ME!
private int	m_iDijkstraCount	DOCUMENT ME!
private int	m_iEnd	DOCUMENT ME!
private int	m_iFirst	DOCUMENT ME!
private int	m_iIndexCount	index count.
private int	m_iLineClosed	DOCUMENT ME!
private int	m_iNumGeodesicVertices	DOCUMENT ME!
private int	m_iNumNewMeshes	Number of meshes.
private int	m_iNumPicked	Keeps track of the of picking, so that when a pair of points has been picked the Geodesic is calculated:.
private int	m_iNumTriangles	Number of triangles in the mesh, after the new triangles are added:.
private int	m_iNumWorking	number of vertices in the path.
private int[]	m_iPrevious	DOCUMENT ME!
private int	m_iStart	The start, first, and end index values for the pair of points:.
private int	m_iVertexCount	Local copies of the Vertex and Index arrays: a local copy is kept so that when the start or end points fall inside a triangle, a new vertex is added to the vertex array, and three new triangles are added to the triangle index array, new normals are added to the Normal array:.
private int	m_iWhich	DOCUMENT ME!
private LinkedList	m_kBorder	Data memebr for Dijkstra's search.
private javax.media.j3d.BranchGroup	m_kDijkstraGeodesicGroup	DOCUMENT ME!
private javax.vecmath.Point3f	m_kEndPoint	DOCUMENT ME!
private ModelTriangleMesh	m_kEndSurface	DOCUMENT ME!
private javax.media.j3d.BranchGroup	m_kEuclidianGeodesicGroup	DOCUMENT ME!
private ModelTriangleMesh	m_kFinished	DOCUMENT ME!
private javax.vecmath.Point3f	m_kFirstPoint	First point, for closing the Geodesic curve:.
private LinkedList	m_kGeodesic_Finished	For finished paths, either open or closed:.
private LinkedList	m_kGeodesic_Working	LinkedLists to contain the working paths in progress, and all finished paths, open and closed for the smoothed geodesics and dijkstra's geodesics.
private LinkedList	m_kGeodesic_Working_Left	DOCUMENT ME!
private LinkedList	m_kGeodesic_Working_Right	DOCUMENT ME!
private javax.media.j3d.Group	m_kGeodesicGroup	Group for drawing the Geodesic on the triangle mesh, assumes that the Group is created in the same branch tree as the triangle mesh surface, so when the mesh is transformed (rotated,scaled,translated) the polyline drawn and stored in the Group m_kSmoothedGeodesicGroup will be transformed in the same way:.
private javax.vecmath.Point3f[]	m_kGeodesicVertices	The final list of points in the Geodesic curve.
private ModelTriangleMesh	m_kLastCut	DOCUMENT ME!
private ModelTriangleMesh	m_kLastFinished	DOCUMENT ME!
private ModelTriangleMesh	m_kModified	DOCUMENT ME!
private MouseEvent	m_kMouseEvent	DOCUMENT ME!
private LinkedList	m_kNewColors	New Colors link list.
private LinkedList	m_kNewNormals	New normal link list.
private LinkedList	m_kNewTexCoords	New texCoords link list.
private LinkedList	m_kNewTriangles	new triangle link list.
private LinkedList	m_kNewVerts	New vertices link list.
private ModelTriangleMesh	m_kOriginal	Data members for the Geodesic Class: Triangle mesh:.
(package private) JPanelGeodesic	m_kPanel	Reference to the JPanelGeodesic:.
private JProgressBar	m_kPBar	Volume renderer progress bar:.
private com.sun.j3d.utils.picking.PickCanvas	m_kPickCanvas	PickCanvas, created by the class that creates the triangle mesh and the geodesic group:.
private javax.vecmath.Color3f[]	m_kPickColors	Color of the first and sucessive points on the Geodesic curve:.
private javax.vecmath.Point3f	m_kPreviousStartPoint	DOCUMENT ME!
private LinkedList	m_kRemoveTriangles	Removed triangle link list.
private javax.media.j3d.BranchGroup	m_kSmoothedGeodesicGroup	Root group for different path.
private LinkedList	m_kStartEndList	link list to hold the path.
private javax.vecmath.Point3f	m_kStartPoint	Start and End points -- pair of points for which a Geodesic is calculated, must be in TriangleMesh coordinates:.
private ModelTriangleMesh	m_kStartSurface	DOCUMENT ME!
private ModelTriangleMesh	m_kSurface	DOCUMENT ME!
private ModelTriangleMesh	m_kSurfaceBackup	DOCUMENT ME!
private javax.media.j3d.Switch	m_kSwitchDisplay	DOCUMENT ME!

Constructor Summary

Constructors

Constructor	Description
Geodesic()	Instantiation without initializing the progress bar, pickCanvas, GeodesicGroup, triangle mesh or sphere radius, each of those can be set through individual member access functions:.
Geodesic(com.sun.j3d.utils.picking.PickCanvas kPickCanvas, javax.media.j3d.Group kGeodesicGroup, ModelTriangleMesh kMesh, float fRadius)	Instantiaion of the Geodesic object, with the objects necessary for the Geodesic to serve as a MouseListener that performs picking and with the Group kGeodesicGroup so that the Geodesic curve can be drawn directly on the ModelTriangleMesh.

Method Summary

Modifier and Type	Method	Description
private void	addEdge(int iEdgeIndex, int iNewEdge)	Add the edge to the EdgeList, check to make sure that edge has not already been added.
private int	checkOnEdge(ModelTriangleMesh kMesh, javax.vecmath.Point3f kPoint, int[] aiTriIndex, javax.vecmath.Vector3f kNormal, javax.vecmath.TexCoord3f kTexCoord, javax.vecmath.Color4f kColor)	Given a point which is known to be inside a triangle, and that triangle, this function determines which edge, if any, that point falls on.
private void	cleanUp()	cleanUp deletes the data stuctures used for the Dijkstra's search, but does not delete the array of points on the Geodesic curve.
void	clear(boolean bAll)	Clear all geodesics curves drawn on the surface.
private void	clearAllStartEnd()	clears the all the points added in livewire mode when clear all is called from the user interface.
void	clearCut(boolean bAll)	Clear the current geodesics curve drawn on the surface.
private void	clearLastStartEnd()	clears the last points added in livewire mode when clear last point is called from the user interface.
boolean	computeGeodesic(float fPercentage, boolean bSmoothed)	Compute the Geodesic curve.
private boolean	contains(LinkedList kTriList, javax.vecmath.Point3i kNewTri)	Contains determines if the linked list kTriList contains the input triangle, which is specified by three vertex indices.
private boolean	createEdgeLists(ModelTriangleMesh kMesh)	Create the edges list from the given surface triangle mesh.
private ModelTriangleMesh	createNewMesh(ModelTriangleMesh kMesh, int iVertexCount, int iOldVertexCount)	creates a new mesh after triangulation or when a mesh is cut along the geodesic.
boolean	createPath(int iStart, int iEnd)	createPath starts with the results of Dijkstra's minimum path algorithm.
void	cut()	Cut the m_kModified mesh.
void	dispose()	Deletes all member variables, clean memory.
private float	distance(javax.vecmath.Point3f kPoint1, javax.vecmath.Point3f kPoint2)	Calculate the Euclidean distance between two points.
void	drawDijkstraEuclidianPath(int iStart, int iEnd)	drawPath draws the Dijkstra path and Euclidian paths and adds them to the corresponding m_kDijkstraGeodesicGroup and m_kEuclidianGeodesicGroups.
private void	drawDijkstraEuclidianPoint(javax.vecmath.Point3f kStart, javax.vecmath.Color3f kColor)	Draw the user-selected point as a sphere on the triangle mesh, the sphere is added to all three drawing groups: m_kSmoothedGeodesicGroup, m_kDijkstraGeodesicGroup, and m_kEuclidianGeodesicGroup.
void	drawGeodesicPath(int iStart, int iEnd)	drawPath draws the Geodesic path as a LineArray and adds it to the children of the m_kSmoothedGeodesicGroup object, it also draws the Dijkstra path and Euclidian paths and adds them to the corresponding m_kDijkstraGeodesicGroup and m_kEuclidianGeodesicGroups.
private void	drawGeodesicPoint(javax.vecmath.Point3f kStart, javax.vecmath.Color3f kColor)	Draw the user-selected point as a sphere on the triangle mesh, the sphere is added to all three drawing groups: m_kSmoothedGeodesicGroup, m_kDijkstraGeodesicGroup, and m_kEuclidianGeodesicGroup.
void	drawPath(int iStart, int iEnd)	drawPath draws the Geodesic path as a LineArray and adds it to the children of the m_kSmoothedGeodesicGroup object, it also draws the Dijkstra path and Euclidian paths and adds them to the corresponding m_kDijkstraGeodesicGroup and m_kEuclidianGeodesicGroups.
private void	drawPoint(javax.vecmath.Point3f kStart, javax.vecmath.Color3f kColor)	Draw the user-selected point as a sphere on the triangle mesh, the sphere is added to all three drawing groups: m_kSmoothedGeodesicGroup, m_kDijkstraGeodesicGroup, and m_kEuclidianGeodesicGroup.
private int	extractNewMesh(LinkedList kLoop)	Used in cutting closed paths and creating new meshes to export to the scene graph.
private void	findEdges(int iIndex, boolean[] bFound)	Go through the edge list find the the edge specified.
private float	findMin(javax.vecmath.Point3f kStart, int iMiddle, int iSide, javax.vecmath.Point3f kEnd, javax.vecmath.Point4f kNewPoint4)	findMin finds the point (newpoint) along the edge that connects the points Side-Middle that minimizes the distance Start-newpoint-End.
private int	findNewMeshes(ModelTriangleMesh kSourceMesh, LinkedList kGeodesic_Closed_Loops)	Used in cutting closed paths and creating new meshes to export to the scene graph.
private int	findSmallest()	The findSmallest function searches through the list of vertices that are not yet relaxed but that have been visited by the Dijkstra Search, so that the weight factor is not Float.MAX_VALUE, but also is not the minimum value for that node.
private int	findTriPoints(int iNode1, int iNode2, LinkedList kEndPoints)	Find the next side triangle index.
void	finish(boolean bOpen)	Closes the geodesic curve.
private void	finishWorkingLists(boolean bOpen)	Adds the working paths to the finished path lists, combining the segments in the working paths into one path.
private javax.vecmath.Color4f	getColor(ModelTriangleMesh kMesh, int[] aiIndex)	Calculates and returns the start point color for a new starting point inside an existing triangle.
private javax.vecmath.Color4f	getColor(ModelTriangleMesh kMesh, int iIndex1, int iIndex2)	Get the the triangle color from the given triangle index.
boolean	getEnable()	Access on when picking with the mouse is enabled.
private javax.vecmath.Vector3f	getNormal(ModelTriangleMesh kMesh, int[] aiIndex)	Calculates and returns the start point normal for a new starting point inside an existing triangle.
private javax.vecmath.Vector3f	getNormal(ModelTriangleMesh kMesh, int iIndex1, int iIndex2)	Get the the triangle normal from the given triangle index.
int	getNumPathPoints()	Returns the number of points in the geodesic curve.
private int	getPathIndex(LinkedList kPath, int iVertexCount, int iIndex, boolean bOpen)	getPathIndex returns what the new vertex index should be.
void	getPathPoint(int iPoint, javax.vecmath.Point3f kPoint)	Access to the ith point on the Geodesic curve.
void	getPathPoints(javax.vecmath.Point3f[] akPoints)	Access to the all the points on the Geodesic curve.
private void	getStartEnd(int iWhich)	In livewire mode the endpoints of each path segment along Dijkstra's curve -- between each of the user-selected points -- are stored so that the smoothed geodesic may be calculated and displayed later.
private javax.vecmath.TexCoord3f	getTexCoord(ModelTriangleMesh kMesh, int[] aiIndex)	Calculates and returns the start point texture coordinate for a new starting point inside an existing triangle.
private javax.vecmath.TexCoord3f	getTexCoord(ModelTriangleMesh kMesh, int iIndex1, int iIndex2)	Get the the triangle texture coordinate from the given triangle index.
private void	initColors()	Initializes the colors for the first point on the curve, and the successive points.
private void	initializeGeodesic(float fPercentage)	initializeGeodesic copies the triangle mesh and initializes the data structures for Dijkstra's Single-Source shortest path algorithm.
void	keyPressed(KeyEvent kEvent)	Invoked when a key has been pressed.
void	keyReleased(KeyEvent kEvent)	Invoked when a key has been released.
void	keyTyped(KeyEvent kEvent)	Invoked when a key has been typed.
void	mouseClicked(MouseEvent kMouseEvent)	One of the overrides necessary to be a MouseListener.
void	mouseDragged(MouseEvent kMouseEvent)	mouseDragged.
void	mouseEntered(MouseEvent kMouseEvent)	One of the overrides necessary to be a MouseListener.
void	mouseExited(MouseEvent kMouseEvent)	One of the overrides necessary to be a MouseListener.
void	mouseMoved(MouseEvent kMouseEvent)	mouseMoved.
void	mousePressed(MouseEvent kMouseEvent)	One of the overrides necessary to be a MouseListener.
void	mouseReleased(MouseEvent kMouseEvent)	One of the overrides necessary to be a MouseListener.
private boolean	onRight(ModelTriangleMesh kMesh, int iPrevIndex, int iIndex, int iSideIndex)	onRight determines if a given point on a triangle, kSide, is to the right of or to the left of the vector specified by the vertices kPrev - kPoint.
private void	outputDeletedAsNew()	creating new meshes to export to the scene graph.
private void	relaxEdges(int iNode)	This function determines the shortest path from the start vertex through the input vertex to the vertices that neighbor the input vertex.
private void	resetDrawGeodesic()	Remove all the geodesic lines and reset to draw the new geodesic lines.
private void	saveStartEnd()	In livewire mode the endpoints of each path segment along Dijkstra's curve -- between each of the user-selected points -- are stored so that the smoothed geodesic may be calculated and displayed later.
void	setEnable(boolean bEnable)	Enables picking with the mouse and drawing the curve on the mesh.
void	setEndIndex(int iIndex)	Set the index of the vertex in the triangle mesh where the Geodesic curve is to end.
void	setEndIndices(int[] iIndices)	Sets the indices of the triangle that the end point is located in.
void	setEndPoint(javax.vecmath.Point3f kPoint)	Sets the end point of the geodesic curve on the mesh.
private void	setEndSurface(ModelTriangleMesh kMesh)	The start and end surfaces ensure that the points on the geodesic curve all fall on one mesh, and that the algorithm isn't trying to find a path between two unconnected meshes.
private void	setEpsilon()	Determines an appropriate epsilon, based on the size of the triangles in the mesh.
void	setGeodesicGroup(javax.media.j3d.Group kGeodesicGroup)	Access function to set the Group object m_kGeodesicGroup.
void	setPanel(JPanelGeodesic kPanel)	Access to the JPanelGeodesic interface object.
void	setPickCanvas(com.sun.j3d.utils.picking.PickCanvas kPickCanvas)	Access function to set the pickCanvas.
void	setPreviousStartIndices(int[] iIndices)	Sets the indices of the triangle that the previous start point is located in.
private void	setPreviousStartPoint(javax.vecmath.Point3f kPoint)	Sets the previous start point of the geodesic curve on the mesh.
void	setRadius(float fRadius)	Set the radius of the spheres used to mark the start and end points on the geodesic curve.
void	setStartIndex(int iIndex)	Set the index of the vertex in the triangle mesh where the Geodesic curve is to start.
void	setStartIndices(int[] iIndices, boolean bFirst)	Sets the indices of the triangle that the start point is located in.
void	setStartPoint(javax.vecmath.Point3f kPoint, boolean bFirst)	Sets the start point of the geodesic curve on the mesh.
private void	setStartSurface(ModelTriangleMesh kMesh)	The start and end surfaces ensure that the points on the geodesic curve all fall on one mesh, and that the algorithm isn't trying to find a path between two unconnected meshes.
private void	setSurface(ModelTriangleMesh kMesh)	Access function to set the triangle mesh that the geodesic curve is calculated on.
private int	smoothPath(int iNode, LinkedList kLeft, LinkedList kMiddle, LinkedList kRight, LinkedList kLeftTemp, LinkedList kRightTemp, LinkedList kNewVertTemp)	Smooth the path.
private void	sortTriIndex(javax.vecmath.Point3i aiAddTri, javax.vecmath.Point3f[] akVertices, javax.vecmath.Vector3f[] akNormals)	Used when new triangles are added to the mesh, either when the mesh is triangulated along the smoothed geodesic curve, or when the mesh is cut. sortTriIndex sorts the triangle indices so that the triangle is always front-facing and that the normals are correct for rendering
void	toggleDisplay(int iWhich)	Called by the JPanelGeodesic interface to switch between displaying the Smoothed Geodesic, Dijkstra's path, or the Euclidian path.
void	toggleLivewire()	Toggle between livewire mode and point invalid input: '&' click mode.
private int	triangleEdge(int i0, int i1, int i2, int iP0, int iP1)	if the two of the first three triangle indices equal the second two indices, then the third index is returned.
private boolean	triangleEquals(int i0, int i1, int i2, int iP0, int iP1, int iP2)	Returns true if the first three triangle indices equal the second three indices.
private boolean	triangleExists(javax.vecmath.Point3i kTri)	Check to see if the triangle specified in the triangle list.
private int	triangulate(ModelTriangleMesh kMesh, LinkedList kPath, LinkedList kLeftPath, LinkedList kRightPath, int iVertexCount)	triangulates the mesh along a single geodesic.
private void	triangulateMeshPath()	re-triangulates the mesh along the Smoothed Geodesic.
private int	unZip(ModelTriangleMesh kMesh, LinkedList kPath, int iVertexCount, boolean bOpen, LinkedList kNewPath)	unZip cuts along the smoothed geodesic path by creating new vertices for each point on the path, and updating the triangles that are connected to the path and that fall on the right of the path to contain the new path vertices.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

m_kPanel

JPanelGeodesic m_kPanel

Reference to the JPanelGeodesic:.

m_abRemoveTris

private boolean[] m_abRemoveTris

DOCUMENT ME!

m_aiEndIndex

private int[] m_aiEndIndex

DOCUMENT ME!

m_aiFirstIndex

private int[] m_aiFirstIndex

DOCUMENT ME!

m_aiIndex

private int[] m_aiIndex

vertices array.

m_aiIndexShift

private int[] m_aiIndexShift

DOCUMENT ME!

m_aiPreviousStartIndex

private int[] m_aiPreviousStartIndex

DOCUMENT ME!

m_aiStartIndex

private int[] m_aiStartIndex

The index values in the Vertex array for the triangle that the Start, First, and End points fall in, if they are inside a triangle and not on a triangle vertex:.

m_akCoordinates

private javax.vecmath.Point3f[] m_akCoordinates

triangle index coordinate array.

m_akEdgeList

private LinkedList[] m_akEdgeList

Data members used in Dijkstra's search. The Edgelist is a list for each vertex of all the vertices that it is connected to by one edge. The vertices are stored in the Edgelist as the vertex index.

m_akNormals

private javax.vecmath.Vector3f[] m_akNormals

triangle normal array.

m_akTexCoords

private javax.vecmath.TexCoord3f[] m_akTexCoords

triangle texture coordinate array.

m_akColors

private javax.vecmath.Color4f[] m_akColors

triangle color array.

m_bDisplayDijkstra

private boolean m_bDisplayDijkstra

toggle for displaying Dijkstra's path as well as the smoothed path:.

m_bEnabled

private boolean m_bEnabled

Turned on when picking with the mouse is enabled:.

m_bEndpointChanged

private boolean m_bEndpointChanged

Flag to indicates end ponit changes.

m_bFinished

private boolean m_bFinished

Closing the Geodesic path:.

m_bFirstWire

private boolean m_bFirstWire

DOCUMENT ME!

m_bGroupAdded

private boolean m_bGroupAdded

Flag for clearing the Geodesic curves, if it is false, no curves have been added to the GeodesicGroup.

m_bLastWire

private boolean m_bLastWire

DOCUMENT ME!

m_bLivewire

private boolean m_bLivewire

Live wire or point and click mode:.

m_bMouseMotion

private boolean m_bMouseMotion

DOCUMENT ME!

m_bMousePressed

private boolean m_bMousePressed

Mouse events. Setting mousePressed and mouseReleased explicitly when the mouse events are received has deals with getting multiply mouse event notifications for the same mouse press.

m_bMouseReleased

private boolean m_bMouseReleased

DOCUMENT ME!

m_bOpen

private boolean m_bOpen

Close path or not.

m_bRelaxed

private boolean[] m_bRelaxed

DOCUMENT ME!

m_fDijkstraPathLength

private float m_fDijkstraPathLength

Path length statistics for each type of path:.

m_fEpsilon

private float m_fEpsilon

Error correction Epsilon.

m_fRadius

private float m_fRadius

Radius of the sphere displayed to mark the points on the Geodesic. This can be set directly by the class using the Geodesic object.

m_fRemainingWeight

private float[] m_fRemainingWeight

Weights, relaxed flags, and previous vertex index for Dijkstra's search:.

m_fSmoothedPathLength

private float m_fSmoothedPathLength

DOCUMENT ME!

m_fWeight

private float[] m_fWeight

DOCUMENT ME!

m_iDijkstraCount

private int m_iDijkstraCount

DOCUMENT ME!

m_iEnd

private int m_iEnd

DOCUMENT ME!

m_iFirst

private int m_iFirst

DOCUMENT ME!

m_iIndexCount

private int m_iIndexCount

index count.

m_iLineClosed

private int m_iLineClosed

DOCUMENT ME!

m_iNumGeodesicVertices

private int m_iNumGeodesicVertices

DOCUMENT ME!

m_iNumNewMeshes

private int m_iNumNewMeshes

Number of meshes.

m_iNumPicked

private int m_iNumPicked

Keeps track of the of picking, so that when a pair of points has been picked the Geodesic is calculated:.

m_iNumTriangles

private int m_iNumTriangles

Number of triangles in the mesh, after the new triangles are added:.

m_iNumWorking

private int m_iNumWorking

number of vertices in the path.

m_iPrevious

private int[] m_iPrevious

DOCUMENT ME!

m_iStart

private int m_iStart

The start, first, and end index values for the pair of points:.

m_iVertexCount

private int m_iVertexCount

Local copies of the Vertex and Index arrays: a local copy is kept so that when the start or end points fall inside a triangle, a new vertex is added to the vertex array, and three new triangles are added to the triangle index array, new normals are added to the Normal array:.

m_iWhich

private int m_iWhich

DOCUMENT ME!

m_kBorder

private LinkedList m_kBorder

Data memebr for Dijkstra's search. The m_kBorder list stores all the vertices that have been visited by Dijkstra's search, but that have not yet been relaxed. It is used to speed up the search for the non-relaxed vertex with the smallest path distance

m_kDijkstraGeodesicGroup

private javax.media.j3d.BranchGroup m_kDijkstraGeodesicGroup

DOCUMENT ME!

m_kEndPoint

private javax.vecmath.Point3f m_kEndPoint

DOCUMENT ME!

m_kEndSurface

private ModelTriangleMesh m_kEndSurface

DOCUMENT ME!

m_kEuclidianGeodesicGroup

private javax.media.j3d.BranchGroup m_kEuclidianGeodesicGroup

DOCUMENT ME!

m_kFinished

private ModelTriangleMesh m_kFinished

DOCUMENT ME!

m_kFirstPoint

private javax.vecmath.Point3f m_kFirstPoint

First point, for closing the Geodesic curve:.

m_kGeodesic_Finished

private LinkedList m_kGeodesic_Finished

For finished paths, either open or closed:.

m_kGeodesic_Working

private LinkedList m_kGeodesic_Working

LinkedLists to contain the working paths in progress, and all finished paths, open and closed for the smoothed geodesics and dijkstra's geodesics. These are used in the cutting operations: For paths that are not finished, points may still be added to these paths:

m_kGeodesic_Working_Left

private LinkedList m_kGeodesic_Working_Left

DOCUMENT ME!

m_kGeodesic_Working_Right

private LinkedList m_kGeodesic_Working_Right

DOCUMENT ME!

m_kGeodesicGroup

private javax.media.j3d.Group m_kGeodesicGroup

Group for drawing the Geodesic on the triangle mesh, assumes that the Group is created in the same branch tree as the triangle mesh surface, so when the mesh is transformed (rotated,scaled,translated) the polyline drawn and stored in the Group m_kSmoothedGeodesicGroup will be transformed in the same way:.

m_kGeodesicVertices

private javax.vecmath.Point3f[] m_kGeodesicVertices

The final list of points in the Geodesic curve. All points are constrained to lie on the triangle mesh,

m_kLastCut

private ModelTriangleMesh m_kLastCut

DOCUMENT ME!

m_kLastFinished

private ModelTriangleMesh m_kLastFinished

DOCUMENT ME!

m_kModified

private ModelTriangleMesh m_kModified

DOCUMENT ME!

m_kMouseEvent

private MouseEvent m_kMouseEvent

DOCUMENT ME!

m_kNewNormals

private LinkedList m_kNewNormals

New normal link list.

m_kNewTexCoords

private LinkedList m_kNewTexCoords

New texCoords link list.

m_kNewColors

private LinkedList m_kNewColors

New Colors link list.

m_kNewTriangles

private LinkedList m_kNewTriangles

new triangle link list.

m_kNewVerts

private LinkedList m_kNewVerts

New vertices link list.

m_kOriginal

private ModelTriangleMesh m_kOriginal

Data members for the Geodesic Class: Triangle mesh:.

m_kPBar

private JProgressBar m_kPBar

Volume renderer progress bar:.

m_kPickCanvas

private com.sun.j3d.utils.picking.PickCanvas m_kPickCanvas

PickCanvas, created by the class that creates the triangle mesh and the geodesic group:.

m_kPickColors

private javax.vecmath.Color3f[] m_kPickColors

Color of the first and sucessive points on the Geodesic curve:.

m_kPreviousStartPoint

private javax.vecmath.Point3f m_kPreviousStartPoint

DOCUMENT ME!

m_kRemoveTriangles

private LinkedList m_kRemoveTriangles

Removed triangle link list.

m_kSmoothedGeodesicGroup

private javax.media.j3d.BranchGroup m_kSmoothedGeodesicGroup

Root group for different path.

m_kStartEndList

private LinkedList m_kStartEndList

link list to hold the path.

m_kStartPoint

private javax.vecmath.Point3f m_kStartPoint

Start and End points -- pair of points for which a Geodesic is calculated, must be in TriangleMesh coordinates:.

m_kStartSurface

private ModelTriangleMesh m_kStartSurface

DOCUMENT ME!

m_kSurface

private ModelTriangleMesh m_kSurface

DOCUMENT ME!

m_kSurfaceBackup

private ModelTriangleMesh m_kSurfaceBackup

DOCUMENT ME!

m_kSwitchDisplay

private javax.media.j3d.Switch m_kSwitchDisplay

DOCUMENT ME!

Constructor Details

Geodesic

public Geodesic()

Instantiation without initializing the progress bar, pickCanvas, GeodesicGroup, triangle mesh or sphere radius, each of those can be set through individual member access functions:.

Geodesic

public Geodesic(com.sun.j3d.utils.picking.PickCanvas kPickCanvas,
 javax.media.j3d.Group kGeodesicGroup,
 ModelTriangleMesh kMesh,
 float fRadius)

Instantiaion of the Geodesic object, with the objects necessary for the Geodesic to serve as a MouseListener that performs picking and with the Group kGeodesicGroup so that the Geodesic curve can be drawn directly on the ModelTriangleMesh.

Parameters:

kPickCanvas - PickCanvas

kGeodesicGroup - Group

kMesh - ModelTriangleMesh surface

fRadius - float marker sphere radius

Method Details

clear

public void clear(boolean bAll)

Clear all geodesics curves drawn on the surface.

Parameters:

bAll - bAll, when true clears all the geodesic curves, when false, clears the last point drawn:

clearCut

public void clearCut(boolean bAll)

Clear the current geodesics curve drawn on the surface.

Parameters:

bAll - bAll, when true clears all the geodesic curves, when false, clears the last point drawn:

computeGeodesic

public boolean computeGeodesic(float fPercentage,
 boolean bSmoothed)

Compute the Geodesic curve. The triangle mesh, start, and end points, start and end indices must be defined before this function is called.

Parameters:

fPercentage - float, the optimization parameter for Dijkstra's shortest-path search. Values between 0-100, (increasing optimization).

bSmoothed - flag to smooths and stores the shortest path.

Returns:

DOCUMENT ME!

createPath

public boolean createPath(int iStart,
 int iEnd)

createPath starts with the results of Dijkstra's minimum path algorithm. It smooths the path, and stores the resulting points in the m_kGeodesicPath data member.

Parameters:

iStart - int given geodesic line starting point

iEnd - int given geodesic line ending point

Returns:

boolean success or not

cut

public void cut()

Cut the m_kModified mesh.

dispose

public void dispose()

Deletes all member variables, clean memory.

drawDijkstraEuclidianPath

public void drawDijkstraEuclidianPath(int iStart,
 int iEnd)

drawPath draws the Dijkstra path and Euclidian paths and adds them to the corresponding m_kDijkstraGeodesicGroup and m_kEuclidianGeodesicGroups.

Parameters:

iStart - int Dijkstra path starting point

iEnd - int Dijkstra path ending point

drawGeodesicPath

public void drawGeodesicPath(int iStart,
 int iEnd)

drawPath draws the Geodesic path as a LineArray and adds it to the children of the m_kSmoothedGeodesicGroup object, it also draws the Dijkstra path and Euclidian paths and adds them to the corresponding m_kDijkstraGeodesicGroup and m_kEuclidianGeodesicGroups.

Parameters:

iStart - int Geodesic path starting point

iEnd - int Geodesic path ending point

drawPath

public void drawPath(int iStart,
 int iEnd)

drawPath draws the Geodesic path as a LineArray and adds it to the children of the m_kSmoothedGeodesicGroup object, it also draws the Dijkstra path and Euclidian paths and adds them to the corresponding m_kDijkstraGeodesicGroup and m_kEuclidianGeodesicGroups.

Parameters:

iStart - int Geodesic path starting point

iEnd - int Geodesic path ending point

finish

public void finish(boolean bOpen)

Closes the geodesic curve.

Parameters:

bOpen - bOpen: when true leaves the geodesic open, when false closes the geodesic by connecting to the first point on the polyline sequence.

getEnable

public boolean getEnable()

Access on when picking with the mouse is enabled.

Returns:

boolean picking is enabled or not.

getNumPathPoints

public int getNumPathPoints()

Returns the number of points in the geodesic curve.

Returns:

int, the number of points on the Geodesic.

getPathPoint

public void getPathPoint(int iPoint,
 javax.vecmath.Point3f kPoint)

Access to the ith point on the Geodesic curve. All points on the geodesic curve lie on the triangle mesh.

Parameters:

iPoint - ith point index

kPoint - Point3f point's coordinate

getPathPoints

public void getPathPoints(javax.vecmath.Point3f[] akPoints)

Access to the all the points on the Geodesic curve. All points on the geodesic curve lie on the triangle mesh.

Parameters:

akPoints - Point3f[] points coordinates array

keyPressed

public void keyPressed(KeyEvent kEvent)

Invoked when a key has been pressed.

Specified by:

keyPressed in interface KeyListener

Parameters:

kEvent - KeyEvent

keyReleased

public void keyReleased(KeyEvent kEvent)

Invoked when a key has been released.

Specified by:

keyReleased in interface KeyListener

Parameters:

kEvent - KeyEvent

keyTyped

public void keyTyped(KeyEvent kEvent)

Invoked when a key has been typed.

Specified by:

keyTyped in interface KeyListener

Parameters:

kEvent - KeyEvent

mouseClicked

public void mouseClicked(MouseEvent kMouseEvent)

One of the overrides necessary to be a MouseListener. This function is invoked when a button has been pressed and released.

Specified by:

mouseClicked in interface MouseListener

Parameters:

kMouseEvent - the mouse event generated by a mouse clicked

mouseDragged

public void mouseDragged(MouseEvent kMouseEvent)

mouseDragged.

Specified by:

mouseDragged in interface MouseMotionListener

Parameters:

kMouseEvent - MouseEvent

mouseEntered

public void mouseEntered(MouseEvent kMouseEvent)

One of the overrides necessary to be a MouseListener. Invoked when the mouse enters a component.

Specified by:

mouseEntered in interface MouseListener

Parameters:

kMouseEvent - the mouse event generated by a mouse entered

mouseExited

public void mouseExited(MouseEvent kMouseEvent)

One of the overrides necessary to be a MouseListener. Invoked when the mouse leaves a component.

Specified by:

mouseExited in interface MouseListener

Parameters:

kMouseEvent - the mouse event generated by a mouse exit

mouseMoved

public void mouseMoved(MouseEvent kMouseEvent)

mouseMoved. In livewire mode the mouseMoved function updates the endpoints of the Dijkstra's geodesic and computes Dijkstra's path between the last point added and the mouse position. Only Dijkstra's and the Euclidian paths are updated, the smoothed geodesic is not calculated or displayed:

Specified by:

mouseMoved in interface MouseMotionListener

Parameters:

kMouseEvent - MouseEvent

mousePressed

public void mousePressed(MouseEvent kMouseEvent)

One of the overrides necessary to be a MouseListener. Invoked when a mouse button is pressed.

Specified by:

mousePressed in interface MouseListener

Parameters:

kMouseEvent - the mouse event generated by a mouse press

mouseReleased

public void mouseReleased(MouseEvent kMouseEvent)

One of the overrides necessary to be a MouseListener. Invoked when a mouse button is released.

Specified by:

mouseReleased in interface MouseListener

Parameters:

kMouseEvent - the mouse event generated by a mouse release

setEnable

public void setEnable(boolean bEnable)

Enables picking with the mouse and drawing the curve on the mesh.

Parameters:

bEnable - set the mouse picking enabled or not.

setEndIndex

public void setEndIndex(int iIndex)

Set the index of the vertex in the triangle mesh where the Geodesic curve is to end. The index must be less than or equal to the number of vertices in the triangle mesh.

Parameters:

iIndex - int the index of the vertex in the triangle mesh where the Geodesic curve is to end.

setEndIndices

public void setEndIndices(int[] iIndices)

Sets the indices of the triangle that the end point is located in. This is used when the end point falls on the inside of a triangle in the mesh, the indices parameter defines which triangle the end point falls in.

Parameters:

iIndices - int[3] array of vertex indices defining the end triangle.

setEndPoint

public void setEndPoint(javax.vecmath.Point3f kPoint)

Sets the end point of the geodesic curve on the mesh. The point coordinates must be in local mesh coordinates.

Parameters:

kPoint - the point on the triangle mesh where the geodesic curve is to end, in mesh coordinates.

setGeodesicGroup

public void setGeodesicGroup(javax.media.j3d.Group kGeodesicGroup)

Access function to set the Group object m_kGeodesicGroup. This is necessary for the Geodesic object to draw the geodesic curve on the mesh. The curve may be drawn in one of three ways: (1) the straight-line Euclidian curve, which is not constrained to lie on the mesh surface, or (2) Dijkstra's path, which falls along the original mesh triangle edges, or (3) the Smoothed Geodesic, which is constrained to lie on the mesh surface, but which may cross triangle edges. All three display modes are represented by a different BranchGroup.

Parameters:

kGeodesicGroup - Geodesic image scene graph node.

setPanel

public void setPanel(JPanelGeodesic kPanel)

Access to the JPanelGeodesic interface object.

Parameters:

kPanel - JPanelGeodesic geodesic panel

setPickCanvas

public void setPickCanvas(com.sun.j3d.utils.picking.PickCanvas kPickCanvas)

Access function to set the pickCanvas. This is necessary for the Geodesic class to do picking with the mouse.

Parameters:

kPickCanvas - PickCanvas

setPreviousStartIndices

public void setPreviousStartIndices(int[] iIndices)

Sets the indices of the triangle that the previous start point is located in. This is used when the start point falls on the inside of a triangle in the mesh, the indices parameter defines which triangle the start point falls in.

Parameters:

iIndices - index coordinate

setRadius

public void setRadius(float fRadius)

Set the radius of the spheres used to mark the start and end points on the geodesic curve.

Parameters:

fRadius - the size of the marker sphere to be drawn on the mesh

setStartIndex

public void setStartIndex(int iIndex)

Set the index of the vertex in the triangle mesh where the Geodesic curve is to start. The index must be less than or equal to the number of vertices in the triangle mesh.

Parameters:

iIndex - int the index of the vertex in the triangle mesh where the Geodesic curve is to start.

setStartIndices

public void setStartIndices(int[] iIndices,
 boolean bFirst)

Sets the indices of the triangle that the start point is located in. This is used when the start point falls on the inside of a triangle in the mesh, the indices parameter defines which triangle the start point falls in.

Parameters:

iIndices - int[3] array of vertex indices defining the start triangle.

bFirst - flag indicate the first indices defining the start triangle.

setStartPoint

public void setStartPoint(javax.vecmath.Point3f kPoint,
 boolean bFirst)

Sets the start point of the geodesic curve on the mesh. The point coordinates must be in local mesh coordinates.

Parameters:

kPoint - the point on the triangle mesh where the geodesic curve is to start, in mesh coordinates.

bFirst - flag indicate the first indices defining the start triangle.

toggleDisplay

public void toggleDisplay(int iWhich)

Called by the JPanelGeodesic interface to switch between displaying the Smoothed Geodesic, Dijkstra's path, or the Euclidian path.

Parameters:

iWhich - display group index

toggleLivewire

public void toggleLivewire()

Toggle between livewire mode and point invalid input: '&' click mode.

addEdge

private void addEdge(int iEdgeIndex,
 int iNewEdge)

Add the edge to the EdgeList, check to make sure that edge has not already been added.

Parameters:

iEdgeIndex - edge index

iNewEdge - int added edge index

checkOnEdge

private int checkOnEdge(ModelTriangleMesh kMesh,
 javax.vecmath.Point3f kPoint,
 int[] aiTriIndex,
 javax.vecmath.Vector3f kNormal,
 javax.vecmath.TexCoord3f kTexCoord,
 javax.vecmath.Color4f kColor)

Given a point which is known to be inside a triangle, and that triangle, this function determines which edge, if any, that point falls on.

Parameters:

kMesh - ModelTriangleMesh surface

kPoint - Point3f

aiTriIndex - int[]

kNormal - Vector3f

Returns:

int

cleanUp

private void cleanUp()

cleanUp deletes the data stuctures used for the Dijkstra's search, but does not delete the array of points on the Geodesic curve.

clearAllStartEnd

private void clearAllStartEnd()

clears the all the points added in livewire mode when clear all is called from the user interface.

clearLastStartEnd

private void clearLastStartEnd()

clears the last points added in livewire mode when clear last point is called from the user interface.

contains

private boolean contains(LinkedList kTriList,
 javax.vecmath.Point3i kNewTri)

Contains determines if the linked list kTriList contains the input triangle, which is specified by three vertex indices. The LinkedList member function contains is not used because the indices may be in a different order, and the function must return true if any of the triangles in the list match the input triangle regardless of the order the vertices are specified

Parameters:

kTriList - Link List

kNewTri - Point3i input triangle vertex indices

Returns:

boolean contains the triangle or not.

createEdgeLists

private boolean createEdgeLists(ModelTriangleMesh kMesh)

Create the edges list from the given surface triangle mesh.

Parameters:

kMesh - ModelTriangleMesh surface

Returns:

boolean success or not

createNewMesh

private ModelTriangleMesh createNewMesh(ModelTriangleMesh kMesh,
 int iVertexCount,
 int iOldVertexCount)

creates a new mesh after triangulation or when a mesh is cut along the geodesic.

Parameters:

kMesh - ModelTriangleMesh surface

iVertexCount - int new vertex count

iOldVertexCount - int old vertex cunt

Returns:

ModelTriangleMesh surface

distance

private float distance(javax.vecmath.Point3f kPoint1,
 javax.vecmath.Point3f kPoint2)

Calculate the Euclidean distance between two points.

Parameters:

kPoint1 - Point3f starting point

kPoint2 - Point3f ending point

Returns:

float distance

drawDijkstraEuclidianPoint

private void drawDijkstraEuclidianPoint(javax.vecmath.Point3f kStart,
 javax.vecmath.Color3f kColor)

Draw the user-selected point as a sphere on the triangle mesh, the sphere is added to all three drawing groups: m_kSmoothedGeodesicGroup, m_kDijkstraGeodesicGroup, and m_kEuclidianGeodesicGroup.

Parameters:

kStart - Point3f starting point

kColor - Color3f ending point

drawGeodesicPoint

private void drawGeodesicPoint(javax.vecmath.Point3f kStart,
 javax.vecmath.Color3f kColor)

Draw the user-selected point as a sphere on the triangle mesh, the sphere is added to all three drawing groups: m_kSmoothedGeodesicGroup, m_kDijkstraGeodesicGroup, and m_kEuclidianGeodesicGroup.

Parameters:

kStart - Point3f starting point

kColor - Color3f ending point

drawPoint

private void drawPoint(javax.vecmath.Point3f kStart,
 javax.vecmath.Color3f kColor)

Draw the user-selected point as a sphere on the triangle mesh, the sphere is added to all three drawing groups: m_kSmoothedGeodesicGroup, m_kDijkstraGeodesicGroup, and m_kEuclidianGeodesicGroup.

Parameters:

kStart - Point3f point coordinate

kColor - Color3f point color

extractNewMesh

private int extractNewMesh(LinkedList kLoop)

Used in cutting closed paths and creating new meshes to export to the scene graph.

Parameters:

kLoop - LinkedList surface mesh link list

Returns:

int number of deleted vertices

findEdges

private void findEdges(int iIndex,
 boolean[] bFound)

Go through the edge list find the the edge specified.

Parameters:

iIndex - int edge index

bFound - boolean[] edge being found

findMin

private float findMin(javax.vecmath.Point3f kStart,
 int iMiddle,
 int iSide,
 javax.vecmath.Point3f kEnd,
 javax.vecmath.Point4f kNewPoint4)

findMin finds the point (newpoint) along the edge that connects the points Side-Middle that minimizes the distance Start-newpoint-End.

Parameters:

kStart - Point3f starting point

iMiddle - int middle point

iSide - int side point index

kEnd - Point3f end index

kNewPoint4 - Point4f new point

Returns:

float find min point index

findNewMeshes

private int findNewMeshes(ModelTriangleMesh kSourceMesh,
 LinkedList kGeodesic_Closed_Loops)

Used in cutting closed paths and creating new meshes to export to the scene graph.

Parameters:

kSourceMesh - ModelTriangleMesh surface mesh

kGeodesic_Closed_Loops - LinkedList closed path

Returns:

int

findSmallest

private int findSmallest()

The findSmallest function searches through the list of vertices that are not yet relaxed but that have been visited by the Dijkstra Search, so that the weight factor is not Float.MAX_VALUE, but also is not the minimum value for that node. In Dijkstra's search the vertex with the smallest weight is relaxed first, a greedy algorithm that chooses the locally closest vertex to add to the path. The final weight for the vertex is determined when it is relaxed.

This function uses the data member m_kBorder -- the linked list of vertices that have been visited by Dijkstra's search, but which have not yet been relaxed.

Returns:

int index of the vertex with the smallest weight

findTriPoints

private int findTriPoints(int iNode1,
 int iNode2,
 LinkedList kEndPoints)

Find the next side triangle index.

Parameters:

iNode1 - int node 1 along the side

iNode2 - int node 2 along the side

kEndPoints - end point Link List

Returns:

int next side triangle index

finishWorkingLists

private void finishWorkingLists(boolean bOpen)

Adds the working paths to the finished path lists, combining the segments in the working paths into one path.

Parameters:

bOpen - boolean close path or not

getNormal

private javax.vecmath.Vector3f getNormal(ModelTriangleMesh kMesh,
 int[] aiIndex)

Calculates and returns the start point normal for a new starting point inside an existing triangle. The new normal is the average of the normals at each point in the triangle the starting point is inside

Parameters:

kMesh - ModelTriangleMesh surface mesh

aiIndex - int[] 3 triangle points

Returns:

Vector3f Average normal of the triangle.

getTexCoord

private javax.vecmath.TexCoord3f getTexCoord(ModelTriangleMesh kMesh,
 int[] aiIndex)

Calculates and returns the start point texture coordinate for a new starting point inside an existing triangle. The new texture coordinate is the average of the texture coordinates at each point in the triangle the starting point is inside

Parameters:

kMesh - ModelTriangleMesh surface mesh

aiIndex - int[] 3 triangle points

Returns:

Texture3f Average texture coordinate of the triangle.

getColor

private javax.vecmath.Color4f getColor(ModelTriangleMesh kMesh,
 int[] aiIndex)

Calculates and returns the start point color for a new starting point inside an existing triangle. The new color is the average of the colors at each point in the triangle the starting point is inside

Parameters:

kMesh - ModelTriangleMesh surface mesh

aiIndex - int[] 3 triangle points

Returns:

Color4f Average color of the triangle.

getNormal

private javax.vecmath.Vector3f getNormal(ModelTriangleMesh kMesh,
 int iIndex1,
 int iIndex2)

Get the the triangle normal from the given triangle index.

Parameters:

kMesh - ModelTriangleMesh surface mesh

iIndex1 - int triangle point index 1

iIndex2 - int triangle point index 2

Returns:

Vector3f normal of the triangle

getTexCoord

private javax.vecmath.TexCoord3f getTexCoord(ModelTriangleMesh kMesh,
 int iIndex1,
 int iIndex2)

Get the the triangle texture coordinate from the given triangle index.

Parameters:

kMesh - ModelTriangleMesh surface mesh

iIndex1 - int triangle point index 1

iIndex2 - int triangle point index 2

Returns:

interpolated texture coordinate the triangle

getColor

private javax.vecmath.Color4f getColor(ModelTriangleMesh kMesh,
 int iIndex1,
 int iIndex2)

Get the the triangle color from the given triangle index.

Parameters:

kMesh - ModelTriangleMesh surface mesh

iIndex1 - int triangle point index 1

iIndex2 - int triangle point index 2

Returns:

interpolated color the triangle

getPathIndex

private int getPathIndex(LinkedList kPath,
 int iVertexCount,
 int iIndex,
 boolean bOpen)

getPathIndex returns what the new vertex index should be. If the input index, iIndex, does fall on the cut path, kPath, then that point on the path is going to be duplicated to disconnect the triangles on either side of the cut path. Therefore the input index needs to be translated into a new vertex index, based on the current iVertexCount, the point's position along the path, and wehter or not the path is open or closed.

Parameters:

kPath - LinkedList path link list

iVertexCount - int vertex count

iIndex - int path index

bOpen - boolean close path or not

Returns:

int the new vertex index

getStartEnd

private void getStartEnd(int iWhich)

In livewire mode the endpoints of each path segment along Dijkstra's curve -- between each of the user-selected points -- are stored so that the smoothed geodesic may be calculated and displayed later. This function retrieves the stored values when the livewire path is finished

Parameters:

iWhich - int path index

initColors

private void initColors()

Initializes the colors for the first point on the curve, and the successive points.

initializeGeodesic

private void initializeGeodesic(float fPercentage)

initializeGeodesic copies the triangle mesh and initializes the data structures for Dijkstra's Single-Source shortest path algorithm.

If the start and end vertices do not fall on a triangle vertex, then the triangle they fall inside split into three new triangles, by connecting the new vertex to each of the triangle vertices.

Parameters:

fPercentage - float the optimization parameter for Dijkstra's shortest-path search

onRight

private boolean onRight(ModelTriangleMesh kMesh,
 int iPrevIndex,
 int iIndex,
 int iSideIndex)

onRight determines if a given point on a triangle, kSide, is to the right of or to the left of the vector specified by the vertices kPrev - kPoint.

Parameters:

kMesh - ModelTriangleMesh surface mesh

iPrevIndex - int previous vertice

iIndex - int specified vertice index

iSideIndex - int side vertice index

Returns:

boolean a point on the right or triangle or not.

outputDeletedAsNew

private void outputDeletedAsNew()

creating new meshes to export to the scene graph.

relaxEdges

private void relaxEdges(int iNode)

This function determines the shortest path from the start vertex through the input vertex to the vertices that neighbor the input vertex.

The function relaxEdges looks at all the vertices connected by triangle edges to the input vertex and calculated the weight factors for each of those vertices, adding those vertices that are not yet "relaxed" to the list of vertices on the border.

Once the weight factors for each of the vertices connected to the input vertex are set, the input vertex is labeled "relaxed" and removed from the list of vertices on the border.

Parameters:

iNode - int input vertex index

resetDrawGeodesic

private void resetDrawGeodesic()

Remove all the geodesic lines and reset to draw the new geodesic lines.

saveStartEnd

private void saveStartEnd()

In livewire mode the endpoints of each path segment along Dijkstra's curve -- between each of the user-selected points -- are stored so that the smoothed geodesic may be calculated and displayed later.

setEndSurface

private void setEndSurface(ModelTriangleMesh kMesh)

The start and end surfaces ensure that the points on the geodesic curve all fall on one mesh, and that the algorithm isn't trying to find a path between two unconnected meshes.

Parameters:

kMesh - ModelTriangleMesh surface mesh

setEpsilon

private void setEpsilon()

Determines an appropriate epsilon, based on the size of the triangles in the mesh. The epsilon is used to determine if points are "close enough" to the triangle vertices or edges.

setPreviousStartPoint

private void setPreviousStartPoint(javax.vecmath.Point3f kPoint)

Sets the previous start point of the geodesic curve on the mesh. Used when the last point is deleted, the start point reverts to the previous start point. The point coordinates must be in local mesh coordinates.

Parameters:

kPoint - the point on the triangle mesh where the geodesic curve is to start, in mesh coordinates.

setStartSurface

private void setStartSurface(ModelTriangleMesh kMesh)

The start and end surfaces ensure that the points on the geodesic curve all fall on one mesh, and that the algorithm isn't trying to find a path between two unconnected meshes.

Parameters:

kMesh - surface mesh

setSurface

private void setSurface(ModelTriangleMesh kMesh)

Access function to set the triangle mesh that the geodesic curve is calculated on.

Parameters:

kMesh - DOCUMENT ME!

smoothPath

private int smoothPath(int iNode,
 LinkedList kLeft,
 LinkedList kMiddle,
 LinkedList kRight,
 LinkedList kLeftTemp,
 LinkedList kRightTemp,
 LinkedList kNewVertTemp)

Smooth the path.

Parameters:

iNode - int vertex index

kLeft - LinkedList left point

kMiddle - LinkedList middle point

kRight - LinkedList right point

kLeftTemp - LinkedList left point temporary

kRightTemp - LinkedList right point temporary

kNewVertTemp - LinkedList new point temporary

Returns:

int success or not

sortTriIndex

private void sortTriIndex(javax.vecmath.Point3i aiAddTri,
 javax.vecmath.Point3f[] akVertices,
 javax.vecmath.Vector3f[] akNormals)

Used when new triangles are added to the mesh, either when the mesh is triangulated along the smoothed geodesic curve, or when the mesh is cut. sortTriIndex sorts the triangle indices so that the triangle is always front-facing and that the normals are correct for rendering

Parameters:

aiAddTri - Point3i added triangle vertices

akVertices - Point3f[] triangle vertices arrray

akNormals - Vector3f[] triangle vertices normal array

triangleEdge

private int triangleEdge(int i0,
 int i1,
 int i2,
 int iP0,
 int iP1)

if the two of the first three triangle indices equal the second two indices, then the third index is returned.

Parameters:

i0 - int first triangle indice 1

i1 - int first triangle indice 2

i2 - int first triangle indice 3

iP0 - int second triangle indice 1

iP1 - int second triangle indice 2

Returns:

int third index

triangleEquals

private boolean triangleEquals(int i0,
 int i1,
 int i2,
 int iP0,
 int iP1,
 int iP2)

Returns true if the first three triangle indices equal the second three indices.

Parameters:

i0 - int first triangle indice 1

i1 - int first triangle indice 2

i2 - int first triangle indice 3

iP0 - int second triangle indice 1

iP1 - int second triangle indice 2

iP2 - DOCUMENT ME!

Returns:

boolean true equal, false not

triangleExists

private boolean triangleExists(javax.vecmath.Point3i kTri)

Check to see if the triangle specified in the triangle list.

Parameters:

kTri - Point3i triangle specified

Returns:

boolean true in the list, false not in the list

triangulate

private int triangulate(ModelTriangleMesh kMesh,
 LinkedList kPath,
 LinkedList kLeftPath,
 LinkedList kRightPath,
 int iVertexCount)

triangulates the mesh along a single geodesic.

Parameters:

kMesh - ModelTriangleMesh surface mesh

kPath - LinkedList path link list

kLeftPath - LinkedList left path link list

kRightPath - LinkedList right path link list

iVertexCount - int vertex count

Returns:

int number of vertices

triangulateMeshPath

private void triangulateMeshPath()

re-triangulates the mesh along the Smoothed Geodesic.

unZip

private int unZip(ModelTriangleMesh kMesh,
 LinkedList kPath,
 int iVertexCount,
 boolean bOpen,
 LinkedList kNewPath)

unZip cuts along the smoothed geodesic path by creating new vertices for each point on the path, and updating the triangles that are connected to the path and that fall on the right of the path to contain the new path vertices. This cuts the mesh by disconnecting the triangles that are on the left and right sides of the geodesic path.

Parameters:

kMesh - ModelTriangleMesh surface mesh

kPath - LinkedList path link list

iVertexCount - int vertex count

bOpen - boolean closed path or not

kNewPath - LinkedList new path link list

Returns:

int new number of vertices