Method for forming a computer model from an intersection of a cutting surface with a bounded volume

Claim 1

A method for forming a computer model of a modified bounded volume representing a portion of a bounded volume on a cutting surface and to a first side of the cutting surface, wherein the bounded volume is comprised of a plurality of faces, edges, and vertices, comprising the steps of: (a) calculating a first signed distance between (1) a first vertex on a first edge of a first face of the bounded volume and (2) the cutting surface, wherein the first signed distance is positive if the first vertex does not reside on the cutting surface and does not reside on the first side of the cutting surface, wherein the first signed distance is negative if the first vertex resides on the first side of the cutting surface, and wherein the first signed distance is zero if the first vertex resides on the cutting surface; (b) calculating a second signed distance between (1) a second vertex on the first edge of the first face of the bounded volume and (2) the cutting surface, wherein the second signed distance is positive if the second vertex does not reside on the cutting surface and does not reside on the first side of the cutting surface, wherein the second signed distance is negative if the second vertex resides on the first side of the cutting surface, and wherein the second signed distance is zero if the second vertex resides on the cutting surface; (c) if both the first signed distance and the second signed distance are positive, then modifying the first face by deleting the first edge from the first face; (d) if both the first signed distance and the second signed distance are negative, then retaining the first edge on the first face; (e) if both the first signed distance and the second signed distance are zero, then retaining the first edge on the first face; (f) if the first signed distance is of a different sign that the second signed distance, then modifying the first face by modifying the first edge of the first face by interpolation; (g) if one and only one of the first and second signed distances is zero, then: (i) modifying the first face by deleting the first edge from the first face if the first signed distance is zero and the second signed distance is positive: (ii) modifying the first face by retaining the first edge on the first face if the first signed distance is zero and the second signed distance is negative: (iii) modifying the first face by deleting the first edge from the first face if the second signed distance is zero and the first signed distance is positive: (iv) modifying the first face by retaining the first edge on the first face if the second signed distance is zero and the first signed distance is negative: (h) repeating steps (a) through (g) for each of the remaining edges of the first face, wherein each next edge of the remaining edges becomes the first edge upon each repetition of steps (a) through (g); (i) if the first face has been modified and is missing an edge, then: (1) generating a first cut-face edge for the first face; (2) storing the first cut-face edge; and (3) modifying the first face by adding the first cut-face edge to the first face; (j) if the first face has been modified, then storing the first face as modified; (k) if the first face has not been modified, then storing the unmodified first face; (l) repeating steps (a) through (k) for each of the remaining faces of the bounded volume, wherein upon each repetition of steps (a) through (k), (1) each next face of the remaining faces becomes the first face and (2) each next cut-face edge becomes the first cut-face edge; (m) forming a cut face from the stored cut-face edges; (n) adding the cut face to the stored faces of the bounded volume to form the modified bounded volume.

Claim 2

A method for forming a computer model of a modified bounded volume representing a portion of a bounded volume on a cutting surface and to a first side of the cutting surface, wherein the bounded volume is comprised of a plurality of faces, edges, and vertices, comprising the steps of: (a) calculating a first signed distance between (1) a first vertex on a first edge of a first face of the bounded volume and (2) the cutting surface, wherein the first signed distance is positive if the first vertex does not reside on the cutting surface and does not reside on the first side of the cutting surface, wherein the first signed distance is negative if the first vertex resides on the first side of the cutting surface, and wherein the first signed distance is zero if the first vertex resides on the cutting surface; (b) calculating a second signed distance between (1) a second vertex on the first edge of the first face of the bounded volume and (2) the cutting surface, wherein the second signed distance is positive if the second vertex does not reside on the cutting surface and does not reside on the first side of the cutting surface, wherein the second signed distance is negative if the second vertex resides on the first side of the cutting surface, and wherein the second signed distance is zero if the second vertex resides on the cutting surface; (c) if both the first signed distance and the second signed distance are positive, then modifying the first face by deleting the first edge from the first face; (d) if both the first signed distance and the second signed distance are negative, then retaining the first edge on the first face; (e) if both the first signed distance and the second signed distance are zero, then retaining the first edge on the first face; (f) if the first signed distance is of a different sign that the second signed distance, then modifying the first face by modifying the first edge of the first face by interpolation; (g) if one and only one of the first and second signed distances is zero, then: (i) modifying the first face by deleting the first edge from the first face if the first signed distance is zero and the second signed distance is positive: (ii) modifying the first face by retaining the first edge on the first face if the first signed distance is zero and the second signed distance is negative: (iii) modifying the first face by deleting the first edge from the first face if the second signed distance is zero and the first signed distance is positive: (iv) modifying the first face by retaining the first edge on the first face if the second signed distance is zero and the first signed distance is negative: (h) repeating steps (a) through (g) for each of the remaining edges of the first face, wherein each next edge of the remaining edges becomes the first edge upon each repetition of steps (a) through (g); (i) if the first face has been modified and is missing an edge, then: (1) generating a first cut-face edge for the first face; (2) storing the first cut-face edge; and (3) modifying the first face by adding the first cut-face edge to the first face; (j) if the first face has been modified, then storing the first face as modified; (k) if the first face has not been modified, then storing the unmodified first face; (l) repeating steps (a) through (k) for each of the remaining faces of the bounded volume, wherein upon each repetition of steps (a) through (k), (1) each next face of the remaining faces becomes the first face and (2) each next cut-face edge becomes the first cut-face edge; (m) forming a cut face from the stored cut-face edges; (n) adding the cut face to the stored faces of the bounded volume to form the modified bounded volume.

Claim 6

The method of claim for 1 for forming a computer model of a modified bounded volume, wherein the modification of the first edge of the first face by interpolation is governed by the equation v=a 1 v 1 +a 2 v 2 , wherein e 1 equals (v 1 v) if d 1 is less than zero and d 2 is greater than or equal to zero, wherein e 1 equals (v, v 2 ) if d 2 is less than zero and d 1 is greater than or equal to zero, wherein e 1 is the modified first edge, wherein d 1 is the first signed distance, wherein d 2 is the second signed distance, wherein v 1 is the first vertex of first edge of the first face of the bounded volume, wherein v 2 is the second vertex of the first edge of the first face of the bounded volume, wherein is a modified vertex, wherein a 1 , equals |d 2 |/(|d 1 |+|d 2 |), wherein a 2 equals |d 1 |/(|d 1 )+|d 2 |), wherein |d 1 | is the absolute value of the first signed distance, and wherein |d 2 | is the absolute value of the second signed distance.

Claim 15

A method for forming a computer model of a cut face representing an intersection of a cutting surface with a bounded volume comprised of a plurality of faces, edges, and vertices, comprising the steps of: (a) generating an edge visibility list for each of the edges of the bounded volume, wherein an edge is visible to another edge if the two edges share a common face; (b) calculating a first signed distance between (1) a first vertex on a first edge of the bounded volume and (2) the cutting surface, wherein the first signed distance is positive if the first vertex does not reside on the cutting surface and does not reside on a first side of the cutting surface, wherein the first signed distance is negative if the first vertex resides on the first side of the cutting surface, and wherein the first signed distance is zero if 1he first vertex resides on the cutting surface; (c) calculating a second signed distance between (1) a second vertex on the first edge of the bounded volume and (2) the cutting surface, wherein the second signed distance is positive if the second vertex does not reside on the cutting surface and does not reside on the first side of the cutting surface, wherein the second signed distance is negative if the second vertex resides on the first side of the cutting surface, and wherein the second signed distance is zero if the second vertex resides on the cutting surface; (d) if the first signed distance is of a different sign than the second signed distance, then: (1) modifying one of the first and second vertices of the first edge by interpolation; (2) storing the modified vertex of the first edge of the bounded volume, and (3) setting an edge-cut flag to indicate that the first edge of the bounded volume has been cut by the cutting surface; (e) repeating steps (b) through (d) for each of the remaining edges of the bounded volume, wherein each next edge of the remaining edges of the bounded volume becomes the first edge upon each repetition of steps (b) through (d); (f) if any of the edges of the bounded volume have been cut, then: (1) stepping sequentially through the edge visibility list from the beginning of the edge visibility list for one of the cut edges until reaching an entry for a cut edge in the edge visibility list, as indicated by the edge-cut flag for the cut edge reached in the edge visibility list; (2) storing the modified vertex of the cut edge reached in the edge visibility list; (3) repeating steps (1) and (2) immediately above for each of the remaining cut edges of the bounded volume, wherein the cut edge reached in the edge visibility list becomes the one of the cut edges upon each repetition of steps (1) and (2); and (4) forming the cut face from the stored modified vertices of the cut edges of the bounded volume.

Claim 16

A method for forming a computer model of a cut face representing an intersection of a cutting surface with a bounded volume comprised of a plurality of faces, edges, and vertices, comprising the steps of: (a) generating an edge visibility list for each of the edges of the bounded volume, wherein an edge is visible to another edge if the two edges share a common face; (b) calculating a first signed distance between (1) a first vertex on a first edge of the bounded volume and (2) the cutting surface, wherein the first signed distance is positive if the first vertex does not reside on the cutting surface and does not reside on a first side of the cutting surface, wherein the first signed distance is negative if the first vertex resides on the first side of the cutting surface, and wherein the first signed distance is zero if 1he first vertex resides on the cutting surface; (c) calculating a second signed distance between (1) a second vertex on the first edge of the bounded volume and (2) the cutting surface, wherein the second signed distance is positive if the second vertex does not reside on the cutting surface and does not reside on the first side of the cutting surface, wherein the second signed distance is negative if the second vertex resides on the first side of the cutting surface, and wherein the second signed distance is zero if the second vertex resides on the cutting surface; (d) if the first signed distance is of a different sign than the second signed distance, then: (1) modifying one of the first and second vertices of the first edge by interpolation; (2) storing the modified vertex of the first edge of the bounded volume, and (3) setting an edge-cut flag to indicate that the first edge of the bounded volume has been cut by the cutting surface; (e) repeating steps (b) through (d) for each of the remaining edges of the bounded volume, wherein each next edge of the remaining edges of the bounded volume becomes the first edge upon each repetition of steps (b) through (d); (f) if any of the edges of the bounded volume have been cut, then: (1) stepping sequentially through the edge visibility list from the beginning of the edge visibility list for one of the cut edges until reaching an entry for a cut edge in the edge visibility list, as indicated by the edge-cut flag for the cut edge reached in the edge visibility list; (2) storing the modified vertex of the cut edge reached in the edge visibility list; (3) repeating steps (1) and (2) immediately above for each of the remaining cut edges of the bounded volume, wherein the cut edge reached in the edge visibility list becomes the one of the cut edges upon each repetition of steps (1) and (2); and (4) forming the cut face from the stored modified vertices of the cut edges of the bounded volume.

Claim 28

A method of forming a computer model of a modified bounded volume representing an intersection of a half-space with a bounded volume, wherein the half-space is comprised of points on a cutting surface and to one side of a cutting surface, comprising the steps of: (a) decomposing the bounded volume into a plurality of cells, wherein each cell comprises a polyhedron; (b) calculating a first signed distance between (1) a first vertex on a first edge of a first face of the a first cell of the plurality of cells and (2) the cutting surface, wherein the first signed distance is positive if the first vertex resides outside the half-space, wherein the first signed distance is negative if the first vertex resides inside the half-space, and wherein the first signed distance is zero if the first vertex resides on the cutting surface; (c) calculating a second signed distance between (1) a second vertex on the first edge of the first face of the first cell and (2) the cutting surface, wherein the second signed distance is positive if the second vertex resides outside the half-space, wherein the second signed distance is negative if the second vertex resides inside the half-space, and wherein the second signed distance is zero if the second vertex resides on the cutting surface; (d) if both the first signed distance and the second signed distance are positive, then modifying the first face by deleting the first edge from the first face; (e) if both the first signed distance and the second signed distance are negative, then retaining the first edge on the first face; (f) if both the first signed distance and the second signed distance are zero, then retaining the first edge on the first face; (g) if the first signed distance is of a different sign than the second signed distance, then modifying the first face by modifying the first edge of the first face by interpolation; (h) if one and only one of the first and second signed distances is zero, then: (i) modifying the first face by deleting the first edge from the first face if the first signed distance is zero and the second signed distance is positive; (ii) modifying the first face by retaining the first edge on the first face if the first signed distance is zero and the second signed distance is negative; (iii) modifying the first face by deleting the first edge from the first face if the second signed distance is zero and the first signed distance is positive; (iv) modifying the first face by retaining the first edge on the first face if the second signed distance is zero and the first signed distance is negative; (i) repeating steps (b) through (h) for each of the remaining edges of the first face, wherein each next edge of the remaining edges becomes the first edge upon each repetition of steps (b) through (h); (j) if the first face has been modified and is missing an edge, then: (1) generating a first cut-face edge for the first face; (2) storing the first cut-face edge; and (3) modifying the first face by adding the first cut-face edge to the first face; (k) if the first face has been modified, then storing the first face as modified; (l) if the first face has not been modified, then storing the unmodified first face; (m) repeating steps (b) through (l) for each of the remaining faces of the first cell, wherein upon each repetition of steps (b) through (l), (1) each next face of the remaining faces becomes the first face and (2) each next cut-face edge becomes the first cut-face edge; (n) forming a cut face from the stored cut-face edges; (o) adding the cut face to the stored faces of the first cell to form a modified first cell, wherein the modified first cell represents the intersection of the half-space with the first cell; and (p) repeating steps (b) through (o) for each of the remaining cells of the bounded volume, wherein upon each repetition of steps (b) through (o), each next cell of the remaining cells becomes the first cell.

Claim 29

A method of forming a computer model of a modified bounded volume representing an intersection of a half-space with a bounded volume, wherein the half-space is comprised of points on a cutting surface and to one side of a cutting surface, comprising the steps of: (a) decomposing the bounded volume into a plurality of cells, wherein each cell comprises a polyhedron; (b) calculating a first signed distance between (1) a first vertex on a first edge of a first face of the a first cell of the plurality of cells and (2) the cutting surface, wherein the first signed distance is positive if the first vertex resides outside the half-space, wherein the first signed distance is negative if the first vertex resides inside the half-space, and wherein the first signed distance is zero if the first vertex resides on the cutting surface; (c) calculating a second signed distance between (1) a second vertex on the first edge of the first face of the first cell and (2) the cutting surface, wherein the second signed distance is positive if the second vertex resides outside the half-space, wherein the second signed distance is negative if the second vertex resides inside the half-space, and wherein the second signed distance is zero if the second vertex resides on the cutting surface; (d) if both the first signed distance and the second signed distance are positive, then modifying the first face by deleting the first edge from the first face; (e) if both the first signed distance and the second signed distance are negative, then retaining the first edge on the first face; (f) if both the first signed distance and the second signed distance are zero, then retaining the first edge on the first face; (g) if the first signed distance is of a different sign than the second signed distance, then modifying the first face by modifying the first edge of the first face by interpolation; (h) if one and only one of the first and second signed distances is zero, then: (i) modifying the first face by deleting the first edge from the first face if the first signed distance is zero and the second signed distance is positive; (ii) modifying the first face by retaining the first edge on the first face if the first signed distance is zero and the second signed distance is negative; (iii) modifying the first face by deleting the first edge from the first face if the second signed distance is zero and the first signed distance is positive; (iv) modifying the first face by retaining the first edge on the first face if the second signed distance is zero and the first signed distance is negative; (i) repeating steps (b) through (h) for each of the remaining edges of the first face, wherein each next edge of the remaining edges becomes the first edge upon each repetition of steps (b) through (h); (j) if the first face has been modified and is missing an edge, then: (1) generating a first cut-face edge for the first face; (2) storing the first cut-face edge; and (3) modifying the first face by adding the first cut-face edge to the first face; (k) if the first face has been modified, then storing the first face as modified; (l) if the first face has not been modified, then storing the unmodified first face; (m) repeating steps (b) through (l) for each of the remaining faces of the first cell, wherein upon each repetition of steps (b) through (l), (1) each next face of the remaining faces becomes the first face and (2) each next cut-face edge becomes the first cut-face edge; (n) forming a cut face from the stored cut-face edges; (o) adding the cut face to the stored faces of the first cell to form a modified first cell, wherein the modified first cell represents the intersection of the half-space with the first cell; and (p) repeating steps (b) through (o) for each of the remaining cells of the bounded volume, wherein upon each repetition of steps (b) through (o), each next cell of the remaining cells becomes the first cell.

Claim 31

A method for forming a computer model of a cut face representing an intersection of a cutting surface with a bounded volume comprised of a plurality of faces, edges, and vertices, comprising the steps of: (a) decomposing the bounded volume into a plurality of cells, wherein each cell comprises a polyhedron; (b) generating an edge visibility list for each of the edges of the plurality of cells, wherein an edge is visible to another edge if the two edges share a common face; (c) calculating a first signed distance between (1) a first vertex on a first edge of a first cell of the plurality of cells and (2) the cutting surface, wherein the first signed distance is positive if the first vertex resides off the cutting surface at a first side of the cutting surface, wherein the first signed distance is negative if the first vertex resides off the cutting surface at a second side of the cutting surface, wherein the second side is opposite to the first side, and wherein the first signed distance is zero if the first vertex resides on the cutting surface; (d) calculating a second signed distance between (1) a second vertex on the first edge of the first cell and (2) the cutting surface, wherein the second signed distance is positive if the second vertex resides off the cutting surface at the first side of the cutting surface, wherein the second signed distance is negative if the second vertex resides off the cutting surface at the second side of the cutting surface, and wherein the second signed distance is zero if the second vertex resides on the cutting surface; (e) if the first signed distance is of a different sign than the second signed distance, then: (1) modifying one of the first and second vertices of the first edge by interpolation; (2) storing the modified vertex of the first edge of the solid, and (3) setting an edge-cut flag to indicate that the first edge of the first cell has been cut by the cutting surface; (f) repeating steps (c) through (e) for each of the remaining edges of the first cell, wherein each next edge of the remaining edges of the solid becomes the first edge upon each repetition of steps (b) through (d); (g) if any of the edges of the first cell have been cut, then: (1) stepping sequentially through the edge visibility list from the beginning of the edge visibility list for one of the cut edges until reaching an entry for a cut edge in the edge visibility list, as indicated by the edge-cut flag for the cut edge reached in the edge visibility list; (2) storing the modified vertex of the cut edge reached in the edge visibility list; (3) repeating steps (1) and (2) immediately above for each of the remaining cut edges of the first cell, wherein the cut edge reached in the edge visibility list becomes the one of the cut edges upon each repetition of steps (1) and (2); and (4) forming a cut face for the first cell from the stored modified vertices of the cut edges of the first cell; (h) repeating steps (c) through (g) for each of the remaining cells of the bounded volume, wherein upon each repetition of steps (c) through (g), each next cell of the remaining cells becomes the first cell.

Claim 32

A method for forming a computer model of a cut face representing an intersection of a cutting surface with a bounded volume comprised of a plurality of faces, edges, and vertices, comprising the steps of: (a) decomposing the bounded volume into a plurality of cells, wherein each cell comprises a polyhedron; (b) generating an edge visibility list for each of the edges of the plurality of cells, wherein an edge is visible to another edge if the two edges share a common face; (c) calculating a first signed distance between (1) a first vertex on a first edge of a first cell of the plurality of cells and (2) the cutting surface, wherein the first signed distance is positive if the first vertex resides off the cutting surface at a first side of the cutting surface, wherein the first signed distance is negative if the first vertex resides off the cutting surface at a second side of the cutting surface, wherein the second side is opposite to the first side, and wherein the first signed distance is zero if the first vertex resides on the cutting surface; (d) calculating a second signed distance between (1) a second vertex on the first edge of the first cell and (2) the cutting surface, wherein the second signed distance is positive if the second vertex resides off the cutting surface at the first side of the cutting surface, wherein the second signed distance is negative if the second vertex resides off the cutting surface at the second side of the cutting surface, and wherein the second signed distance is zero if the second vertex resides on the cutting surface; (e) if the first signed distance is of a different sign than the second signed distance, then: (1) modifying one of the first and second vertices of the first edge by interpolation; (2) storing the modified vertex of the first edge of the solid, and (3) setting an edge-cut flag to indicate that the first edge of the first cell has been cut by the cutting surface; (f) repeating steps (c) through (e) for each of the remaining edges of the first cell, wherein each next edge of the remaining edges of the solid becomes the first edge upon each repetition of steps (b) through (d); (g) if any of the edges of the first cell have been cut, then: (1) stepping sequentially through the edge visibility list from the beginning of the edge visibility list for one of the cut edges until reaching an entry for a cut edge in the edge visibility list, as indicated by the edge-cut flag for the cut edge reached in the edge visibility list; (2) storing the modified vertex of the cut edge reached in the edge visibility list; (3) repeating steps (1) and (2) immediately above for each of the remaining cut edges of the first cell, wherein the cut edge reached in the edge visibility list becomes the one of the cut edges upon each repetition of steps (1) and (2); and (4) forming a cut face for the first cell from the stored modified vertices of the cut edges of the first cell; (h) repeating steps (c) through (g) for each of the remaining cells of the bounded volume, wherein upon each repetition of steps (c) through (g), each next cell of the remaining cells becomes the first cell.