Game Development Reference
In-Depth Information
edges = []
// list of all edges
lines = []
// initially empty list of infinite lines
edgeToLineMap = {}
// maps from edges to lines the fall on
for edge in edges:
edgeDirection = edge.start - edge.end
if edgeDirection.length < epsilon:
continue
// skip degenerate edge
for line in lines:
d[0] = line.planeA.distanceToPoint(edge.start)
d[1] = line.planeB.distanceToPoint(edge.start);
d[2] = line.planeA.distanceToPoint(edge.end);
d[3] = line.planeB.distanceToPoint(edge.end);
for distance in d:
if abs(distance) > pointOnLineTolerance:
next line
// point does not lie on this line
line.insertPoints(edge.start, edge.end)
// insert edge points into ordered list on the line
for p in (edge.start, edge.end):
delta = p line.origin
t = dotProduct(delta, line.direction)
for pointOnLine in line.points:
if pointOnLine == p:
break
if pointOnLine.t < t:
line.points.insertBefore(pointOnLine, p)
else:
line.points.append(p)
edgeToLineMap[edge] = line
return
// otherwise create a new line based on this edge
newLine = lines.add()
newLine.origin = edge.start
newLine.direction = normalize(edgeDirection)
normalA, normalB = makePlanesPerpendicularToDirection(
edge.start, newLine.direction)
newLine.planeA = Plane(edge.start, normalA)
newLine.planeB = Plane(edge.start, normalB)
newLine.insertPoints(edge.start, edge.end)
edgeToLineMap[edge] = newline
Listing 8.2.
Inserting edge points into a list of infinite lines.
mined by traversing the ordered list of points on the edge's corresponding line entry
in the table. If this is the case, the original edge has to be split and the polygon
retriangulated.
8.3.2 Retriangulation
The output of the first stage of the CSG algorithm will contain many convex polygon
fragments resulting from plane splits, many more than a skilled modeler would use
