Catmull–Clark subdivision surface: Difference between revisions
Catmull–Clark subdivision surface (view source)
Revision as of 12:15, 12 November 2023
, 6 months ago→{{header|Wren}}: Minor tidy
(julia example) |
m (→{{header|Wren}}: Minor tidy) |
||
| (15 intermediate revisions by 7 users not shown) | |||
Line 1:
[[Category:Geometry]]
{{task|3D}}{{requires|Graphics}}
Implement the Catmull-Clark surface subdivision ([[wp:Catmull–Clark_subdivision_surface|description on Wikipedia]]), which is an algorithm that maps from a surface (described as a set of points and a set of polygons with vertices at those points) to another more refined surface. The resulting surface will always consist of a mesh of quadrilaterals.
Line 42 ⟶ 44:
For edges and vertices not next to a hole, the standard algorithm from above is used.
=={{header|C}}==
[[file:catmull-C.png|center]]
Only the subdivision part. The [[Catmull–Clark_subdivision_surface/C|full source]] is way too long to be shown here. Lots of macros, you'll have to see the full code to know what's what.
<
{
int i;
Line 138 ⟶ 139:
}
return nm;
}</
=={{header|Go}}==
{{trans|Python}}
<br>
This just prints the new points and faces after 1 iteration of the Catmull-Clark algorithm, agreeing with what the Python results would have been had they been printed rather than plotted.
See the original version for full comments.
<syntaxhighlight lang="go">package main
import (
"fmt"
"sort"
)
type (
Point [3]float64
Face []int
Edge struct {
pn1 int // point number 1
pn2 int // point number 2
fn1 int // face number 1
fn2 int // face number 2
cp Point // center point
}
PointEx struct {
p Point
n int
}
)
func sumPoint(p1, p2 Point) Point {
sp := Point{}
for i := 0; i < 3; i++ {
sp[i] = p1[i] + p2[i]
}
return sp
}
func mulPoint(p Point, m float64) Point {
mp := Point{}
for i := 0; i < 3; i++ {
mp[i] = p[i] * m
}
return mp
}
func divPoint(p Point, d float64) Point {
return mulPoint(p, 1.0/d)
}
func centerPoint(p1, p2 Point) Point {
return divPoint(sumPoint(p1, p2), 2)
}
func getFacePoints(inputPoints []Point, inputFaces []Face) []Point {
facePoints := make([]Point, len(inputFaces))
for i, currFace := range inputFaces {
facePoint := Point{}
for _, cpi := range currFace {
currPoint := inputPoints[cpi]
facePoint = sumPoint(facePoint, currPoint)
}
facePoint = divPoint(facePoint, float64(len(currFace)))
facePoints[i] = facePoint
}
return facePoints
}
func getEdgesFaces(inputPoints []Point, inputFaces []Face) []Edge {
var edges [][3]int
for faceNum, face := range inputFaces {
numPoints := len(face)
for pointIndex := 0; pointIndex < numPoints; pointIndex++ {
pointNum1 := face[pointIndex]
var pointNum2 int
if pointIndex < numPoints-1 {
pointNum2 = face[pointIndex+1]
} else {
pointNum2 = face[0]
}
if pointNum1 > pointNum2 {
pointNum1, pointNum2 = pointNum2, pointNum1
}
edges = append(edges, [3]int{pointNum1, pointNum2, faceNum})
}
}
sort.Slice(edges, func(i, j int) bool {
if edges[i][0] == edges[j][0] {
if edges[i][1] == edges[j][1] {
return edges[i][2] < edges[j][2]
}
return edges[i][1] < edges[j][1]
}
return edges[i][0] < edges[j][0]
})
numEdges := len(edges)
eIndex := 0
var mergedEdges [][4]int
for eIndex < numEdges {
e1 := edges[eIndex]
if eIndex < numEdges-1 {
e2 := edges[eIndex+1]
if e1[0] == e2[0] && e1[1] == e2[1] {
mergedEdges = append(mergedEdges, [4]int{e1[0], e1[1], e1[2], e2[2]})
eIndex += 2
} else {
mergedEdges = append(mergedEdges, [4]int{e1[0], e1[1], e1[2], -1})
eIndex++
}
} else {
mergedEdges = append(mergedEdges, [4]int{e1[0], e1[1], e1[2], -1})
eIndex++
}
}
var edgesCenters []Edge
for _, me := range mergedEdges {
p1 := inputPoints[me[0]]
p2 := inputPoints[me[1]]
cp := centerPoint(p1, p2)
edgesCenters = append(edgesCenters, Edge{me[0], me[1], me[2], me[3], cp})
}
return edgesCenters
}
func getEdgePoints(inputPoints []Point, edgesFaces []Edge, facePoints []Point) []Point {
edgePoints := make([]Point, len(edgesFaces))
for i, edge := range edgesFaces {
cp := edge.cp
fp1 := facePoints[edge.fn1]
var fp2 Point
if edge.fn2 == -1 {
fp2 = fp1
} else {
fp2 = facePoints[edge.fn2]
}
cfp := centerPoint(fp1, fp2)
edgePoints[i] = centerPoint(cp, cfp)
}
return edgePoints
}
func getAvgFacePoints(inputPoints []Point, inputFaces []Face, facePoints []Point) []Point {
numPoints := len(inputPoints)
tempPoints := make([]PointEx, numPoints)
for faceNum := range inputFaces {
fp := facePoints[faceNum]
for _, pointNum := range inputFaces[faceNum] {
tp := tempPoints[pointNum].p
tempPoints[pointNum].p = sumPoint(tp, fp)
tempPoints[pointNum].n++
}
}
avgFacePoints := make([]Point, numPoints)
for i, tp := range tempPoints {
avgFacePoints[i] = divPoint(tp.p, float64(tp.n))
}
return avgFacePoints
}
func getAvgMidEdges(inputPoints []Point, edgesFaces []Edge) []Point {
numPoints := len(inputPoints)
tempPoints := make([]PointEx, numPoints)
for _, edge := range edgesFaces {
cp := edge.cp
for _, pointNum := range []int{edge.pn1, edge.pn2} {
tp := tempPoints[pointNum].p
tempPoints[pointNum].p = sumPoint(tp, cp)
tempPoints[pointNum].n++
}
}
avgMidEdges := make([]Point, len(tempPoints))
for i, tp := range tempPoints {
avgMidEdges[i] = divPoint(tp.p, float64(tp.n))
}
return avgMidEdges
}
func getPointsFaces(inputPoints []Point, inputFaces []Face) []int {
numPoints := len(inputPoints)
pointsFaces := make([]int, numPoints)
for faceNum := range inputFaces {
for _, pointNum := range inputFaces[faceNum] {
pointsFaces[pointNum]++
}
}
return pointsFaces
}
func getNewPoints(inputPoints []Point, pointsFaces []int, avgFacePoints, avgMidEdges []Point) []Point {
newPoints := make([]Point, len(inputPoints))
for pointNum := range inputPoints {
n := float64(pointsFaces[pointNum])
m1, m2, m3 := (n-3)/n, 1.0/n, 2.0/n
oldCoords := inputPoints[pointNum]
p1 := mulPoint(oldCoords, m1)
afp := avgFacePoints[pointNum]
p2 := mulPoint(afp, m2)
ame := avgMidEdges[pointNum]
p3 := mulPoint(ame, m3)
p4 := sumPoint(p1, p2)
newPoints[pointNum] = sumPoint(p4, p3)
}
return newPoints
}
func switchNums(pointNums [2]int) [2]int {
if pointNums[0] < pointNums[1] {
return pointNums
}
return [2]int{pointNums[1], pointNums[0]}
}
func cmcSubdiv(inputPoints []Point, inputFaces []Face) ([]Point, []Face) {
facePoints := getFacePoints(inputPoints, inputFaces)
edgesFaces := getEdgesFaces(inputPoints, inputFaces)
edgePoints := getEdgePoints(inputPoints, edgesFaces, facePoints)
avgFacePoints := getAvgFacePoints(inputPoints, inputFaces, facePoints)
avgMidEdges := getAvgMidEdges(inputPoints, edgesFaces)
pointsFaces := getPointsFaces(inputPoints, inputFaces)
newPoints := getNewPoints(inputPoints, pointsFaces, avgFacePoints, avgMidEdges)
var facePointNums []int
nextPointNum := len(newPoints)
for _, facePoint := range facePoints {
newPoints = append(newPoints, facePoint)
facePointNums = append(facePointNums, nextPointNum)
nextPointNum++
}
edgePointNums := make(map[[2]int]int)
for edgeNum := range edgesFaces {
pointNum1 := edgesFaces[edgeNum].pn1
pointNum2 := edgesFaces[edgeNum].pn2
edgePoint := edgePoints[edgeNum]
newPoints = append(newPoints, edgePoint)
edgePointNums[[2]int{pointNum1, pointNum2}] = nextPointNum
nextPointNum++
}
var newFaces []Face
for oldFaceNum, oldFace := range inputFaces {
if len(oldFace) == 4 {
a, b, c, d := oldFace[0], oldFace[1], oldFace[2], oldFace[3]
facePointAbcd := facePointNums[oldFaceNum]
edgePointAb := edgePointNums[switchNums([2]int{a, b})]
edgePointDa := edgePointNums[switchNums([2]int{d, a})]
edgePointBc := edgePointNums[switchNums([2]int{b, c})]
edgePointCd := edgePointNums[switchNums([2]int{c, d})]
newFaces = append(newFaces, Face{a, edgePointAb, facePointAbcd, edgePointDa})
newFaces = append(newFaces, Face{b, edgePointBc, facePointAbcd, edgePointAb})
newFaces = append(newFaces, Face{c, edgePointCd, facePointAbcd, edgePointBc})
newFaces = append(newFaces, Face{d, edgePointDa, facePointAbcd, edgePointCd})
}
}
return newPoints, newFaces
}
func main() {
inputPoints := []Point{
{-1.0, 1.0, 1.0},
{-1.0, -1.0, 1.0},
{1.0, -1.0, 1.0},
{1.0, 1.0, 1.0},
{1.0, -1.0, -1.0},
{1.0, 1.0, -1.0},
{-1.0, -1.0, -1.0},
{-1.0, 1.0, -1.0},
}
inputFaces := []Face{
{0, 1, 2, 3},
{3, 2, 4, 5},
{5, 4, 6, 7},
{7, 0, 3, 5},
{7, 6, 1, 0},
{6, 1, 2, 4},
}
outputPoints := make([]Point, len(inputPoints))
outputFaces := make([]Face, len(inputFaces))
copy(outputPoints, inputPoints)
copy(outputFaces, inputFaces)
iterations := 1
for i := 0; i < iterations; i++ {
outputPoints, outputFaces = cmcSubdiv(outputPoints, outputFaces)
}
for _, p := range outputPoints {
fmt.Printf("% .4f\n", p)
}
fmt.Println()
for _, f := range outputFaces {
fmt.Printf("%2d\n", f)
}
}</syntaxhighlight>
{{out}}
<pre>
[-0.5556 0.5556 0.5556]
[-0.5556 -0.5556 0.5556]
[ 0.5556 -0.5556 0.5556]
[ 0.5556 0.5556 0.5556]
[ 0.5556 -0.5556 -0.5556]
[ 0.5556 0.5556 -0.5556]
[-0.5556 -0.5556 -0.5556]
[-0.5556 0.5556 -0.5556]
[ 0.0000 0.0000 1.0000]
[ 1.0000 0.0000 0.0000]
[ 0.0000 0.0000 -1.0000]
[ 0.0000 1.0000 0.0000]
[-1.0000 0.0000 0.0000]
[ 0.0000 -1.0000 0.0000]
[-0.7500 0.0000 0.7500]
[ 0.0000 0.7500 0.7500]
[-0.7500 0.7500 0.0000]
[ 0.0000 -0.7500 0.7500]
[-0.7500 -0.7500 0.0000]
[ 0.7500 0.0000 0.7500]
[ 0.7500 -0.7500 0.0000]
[ 0.7500 0.7500 0.0000]
[ 0.7500 0.0000 -0.7500]
[ 0.0000 -0.7500 -0.7500]
[ 0.0000 0.7500 -0.7500]
[-0.7500 0.0000 -0.7500]
[ 0 14 8 15]
[ 1 17 8 14]
[ 2 19 8 17]
[ 3 15 8 19]
[ 3 19 9 21]
[ 2 20 9 19]
[ 4 22 9 20]
[ 5 21 9 22]
[ 5 22 10 24]
[ 4 23 10 22]
[ 6 25 10 23]
[ 7 24 10 25]
[ 7 16 11 24]
[ 0 15 11 16]
[ 3 21 11 15]
[ 5 24 11 21]
[ 7 25 12 16]
[ 6 18 12 25]
[ 1 14 12 18]
[ 0 16 12 14]
[ 6 18 13 23]
[ 1 17 13 18]
[ 2 20 13 17]
[ 4 23 13 20]
</pre>
=={{header|Haskell}}==
<
{-# LANGUAGE ScopedTypeVariables #-}
Line 451 ⟶ 798:
main :: IO ()
main = putStr . pShowSimpleMesh $ subdivide testCube</
{{out}}
<pre>Vertices:
Line 505 ⟶ 852:
(22,[24,15,5,8])
(23,[22,8,5,7])</pre>
=={{header|J}}==
<
havePoints=: e."1/~ i.@#
Line 530 ⟶ 876:
msh=. (,c0+mesh),.(,e0+edges i. meshEdges),.((#i.)~/$mesh),.,e0+_1|."1 edges i. meshEdges
msh;pts
)</
Example use:
<
points=: _1+2*#:i.8
mesh=: 1 A."1 I.(,1-|.)8&$@#&0 1">4 2 1
Line 566 ⟶ 912:
│ │ 0.555556 0.555556 _0.555556│
│ │ 0.555556 0.555556 0.555556│
└──────────┴─────────────────────────────┘</
=={{header|Julia}}==
<
# Point3f0 is a 3-tuple of 32-bit floats for 3-dimensional space, and all Points are 3D.
Line 714 ⟶ 1,059:
println("Press Enter to continue", readline())
</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
This implementation supports tris, quads, and higher polys, as well as surfaces with holes.
The function relies on three externally defined general functionality functions:
<
subSetQ[large_,small_List] := And@@(MemberQ[large,#]&/@small)
containing[groupList_,item_]:= Flatten[Position[groupList,group_/;subSetQ[group,item]]]
ReplaceFace[face_]:=Transpose[Prepend[Transpose[{#[[1]],face,#[[2]]}&/@Transpose[Partition[face,2,1,1]//{#,RotateRight[#]}&]],face]]</
subSetQ[small,large] is a boolean test for whether small is a subset of large. Note this is not a general purpose implimentation and only serves this purpose under the constrictions of the following program.
Line 735 ⟶ 1,079:
<
edges = DeleteDuplicates[Flatten[Partition[#,2,1,-1]&/@faces,1],Sort[#1]==Sort[#2]&];
avgFacePoints=Mean[Points[[#]]] &/@ faces;
Line 762 ⟶ 1,106:
newFaces = Flatten[Map[newIndex[#,{Points,edges,faces}]&,ReplaceFace/@faces,{-2}],1];
{newPoints,newFaces}
]</
The implimentation can be tested with polygons with and without holes by using the polydata
<
Function[iteration,
Graphics3D[(Polygon[iteration[[1]][[#]]]&/@iteration[[2]])]
]/@NestList[CatMullClark,{points,faces},3]//GraphicsRow</
[[File:CAM noholes 1.png]]
For a surface with holes the resulting iterative subdivision will be:
<
Function[iteration, Graphics3D[
(Polygon[iteration[[1]][[#]]] & /@ iteration[[2]])
]] /@ NestList[CatMullClark, {points, faces}, 3] // GraphicsRow</
[[File:CAM holes 1.png]]
This code was written in Mathematica 8.
=={{header|Nim}}==
{{trans|Go}}
{{trans|Python}}
<syntaxhighlight lang="nim">import algorithm
import tables
const None = -1 # Index number used to indicate no data.
type
Point = array[3, float]
Face = seq[int]
Edge = object
pn1: int # Point number 1.
pn2: int # Point number 2.
fn1: int # Face number 1.
fn2: int # Face number 2.
cp: Point # Center point.
PointEx = object
p: Point
n: int
PointNums = tuple[pn1, pn2: int]
####################################################################################################
# Point operations.
func `+`(p1, p2: Point): Point =
## Adds points p1 and p2.
for i in 0..Point.high:
result[i] = p1[i] + p2[i]
#---------------------------------------------------------------------------------------------------
func `*`(p: Point; m: float): Point =
## Multiply point p by m.
for i in 0..Point.high:
result[i] = p[i] * m
#---------------------------------------------------------------------------------------------------
func `/`(p: Point; d: float): Point =
## Divide point p by d.
for i in 0..Point.high:
result[i] = p[i] / d
#---------------------------------------------------------------------------------------------------
func centerPoint(p1, p2: Point): Point =
## Return a point in the center of the segment ended by points p1 and p2.
for i in 0..Point.high:
result[i] = (p1[i] + p2[i]) / 2
####################################################################################################
func getFacePoints(inputPoints: seq[Point]; inputFaces: seq[Face]): seq[Point] =
## For each face, a face point is created which is the average of all the points of the face.
result.setLen(inputFaces.len)
for i, currFace in inputFaces:
var facePoint: Point
for currPointIndex in currFace:
# Add currPoint to facePoint. Will divide later.
facePoint = facePoint + inputPoints[currPointIndex]
result[i] = facePoint / currFace.len.toFloat
#---------------------------------------------------------------------------------------------------
func getEdgesFaces(inputPoints: seq[Point]; inputFaces: seq[Face]): seq[Edge] =
## Get list of edges and the one or two adjacent faces in a list.
## Also get center point of edge.
# Get edges for each face.
var edges: seq[array[3, int]]
for faceNum, face in inputFaces:
# Loop over index into face.
for pointIndex in 0..face.high:
# If not last point then edge is current point and next point
# and for last point, edge is current point and first point.
var pointNum1 = face[pointIndex]
var pointNum2 = if pointIndex < face.high: face[pointIndex + 1] else: face[0]
# Order points in edge by lowest point number.
if pointNum1 > pointNum2:
swap pointNum1, pointNum2
edges &= [pointNum1, pointNum2, faceNum]
# Sort edges by pointNum1, pointNum2, faceNum.
edges.sort(proc(a1, a2: array[3, int]): int =
result = cmp(a1[0], a2[0])
if result == 0:
result = cmp(a1[1], a2[1])
if result == 0:
result = cmp(a1[2], a2[2]))
# Merge edges with 2 adjacent faces:
# [pointNum1, pointNum2, faceNum1, faceNum2] or
# [pointNum1, pointNum2, faceNum1, None]
var eIndex = 0
var mergedEdges: seq[array[4, int]]
while eIndex < edges.len:
let e1 = edges[eIndex]
# Check if not last edge.
if eIndex < edges.high:
let e2 = edges[eIndex + 1]
if e1[0] == e2[0] and e1[1] == e2[1]:
mergedEdges &= [e1[0], e1[1], e1[2], e2[2]]
inc eIndex, 2
else:
mergedEdges &= [e1[0], e1[1], e1[2], None]
inc eIndex
else:
mergedEdges &= [e1[0], e1[1], e1[2], None]
inc eIndex
# Add edge centers.
for me in mergedEdges:
let p1 = inputPoints[me[0]]
let p2 = inputPoints[me[1]]
let cp = centerPoint(p1, p2)
result.add(Edge(pn1: me[0], pn2: me[1], fn1: me[2], fn2: me[3], cp: cp))
#---------------------------------------------------------------------------------------------------
func getEdgePoints(inputPoints: seq[Point];
edgesFaces: seq[Edge];
facePoints: seq[Point]): seq[Point] =
## For each edge, an edge point is created which is the average between the center of the
## edge and the center of the segment made with the face points of the two adjacent faces.
result.setLen(edgesFaces.len)
for i, edge in edgesFaces:
# Get center of two facepoints.
let fp1 = facePoints[edge.fn1]
# If not two faces, just use one facepoint (should not happen for solid like a cube).
let fp2 = if edge.fn2 == None: fp1 else: facePoints[edge.fn2]
let cfp = centerPoint(fp1, fp2)
# Get average between center of edge and center of facePoints.
result[i] = centerPoint(edge.cp, cfp)
#---------------------------------------------------------------------------------------------------
func getAvgFacePoints(inputPoints: seq[Point];
inputFaces: seq[Face];
facePoints: seq[Point]): seq[Point] =
## For each point calculate the average of the face points of the faces the
## point belongs to (avgFacePoints), create a list of lists of two numbers
## [facePointSum, numPoints] by going through the points in all the faces then
## create the avgFacePoints list of point by dividing pointSum(x, y, z) by numPoints
var tempPoints = newSeq[PointEx](inputPoints.len)
# Loop through faces, updating tempPoints.
for faceNum, pointNums in inputFaces:
let fp = facePoints[faceNum]
for pointNum in pointNums:
let tp = tempPoints[pointNum].p
tempPoints[pointNum].p = tp + fp
inc tempPoints[pointNum].n
# Divide to build the result.
result.setLen(inputPoints.len)
for i, tp in tempPoints:
result[i] = tp.p / tp.n.toFloat
#---------------------------------------------------------------------------------------------------
func getAvgMidEdges(inputPoints: seq[Point]; edgesFaces: seq[Edge]): seq[Point] =
## Return the average of the centers of edges the point belongs to (avgMidEdges).
## Create list with entry for each point. Each entry has two elements. One is a point
## that is the sum of the centers of the edges and the other is the number of edges.
## After going through all edges divide by number of edges.
var tempPoints = newSeq[PointEx](inputPoints.len)
# Go through edgesFaces using center updating each point.
for edge in edgesFaces:
for pointNum in [edge.pn1, edge.pn2]:
let tp = tempPoints[pointNum].p
tempPoints[pointNum].p = tp + edge.cp
inc tempPoints[pointNum].n
# Divide out number of points to get average.
result.setLen(inputPoints.len)
for i, tp in tempPoints:
result[i] = tp.p / tp.n.toFloat
#---------------------------------------------------------------------------------------------------
func getPointsFaces(inputPoints: seq[Point]; inputFaces: seq[Face]): seq[int] =
# Return the number of faces for each point.
result.setLen(inputPoints.len)
# Loop through faces updating the result.
for pointNums in inputFaces:
for pointNum in pointNums:
inc result[pointNum]
#---------------------------------------------------------------------------------------------------
func getNewPoints(inputPoints: seq[Point]; pointsFaces: seq[int];
avgFacePoints, avgMidEdges: seq[Point]): seq[Point] =
## m1 = (n - 3.0) / n
## m2 = 1.0 / n
## m3 = 2.0 / n
## newCoords = (m1 * oldCoords) + (m2 * avgFacePoints) + (m3 * avgMidEdges)
result.setLen(inputPoints.len)
for pointNum, oldCoords in inputPoints:
let n = pointsFaces[pointNum].toFloat
let (m1, m2, m3) = ((n - 3) / n, 1 / n, 2 / n)
let p1 = oldCoords * m1
let afp = avgFacePoints[pointNum]
let p2 = afp * m2
let ame = avgMidEdges[pointNum]
let p3 = ame * m3
let p4 = p1 + p2
result[pointNum] = p4 + p3
#---------------------------------------------------------------------------------------------------
func switchNums(pointNums: PointNums): PointNums =
## Return tuple of point numbers sorted least to most.
if pointNums.pn1 < pointNums.pn2: pointNums
else: (pointNums.pn2, pointNums.pn1)
#---------------------------------------------------------------------------------------------------
func cmcSubdiv(inputPoints: seq[Point];
inputFaces: seq[Face]): tuple[p: seq[Point], f: seq[Face]] =
## For each face, a face point is created which is the average of all the points of the face.
## Each entry in the returned list is a point (x, y, z).
let facePoints = getFacePoints(inputPoints, inputFaces)
let edgesFaces = getEdgesFaces(inputPoints, inputFaces)
let edgePoints = getEdgePoints(inputPoints, edgesFaces, facePoints)
let avgFacePoints = getAvgFacePoints(inputPoints, inputFaces, facePoints)
let avgMidEdges = getAvgMidEdges(inputPoints, edgesFaces)
let pointsFaces = getPointsFaces(inputPoints, inputFaces)
var newPoints = getNewPoints(inputPoints, pointsFaces, avgFacePoints, avgMidEdges)
#[Then each face is replaced by new faces made with the new points,
for a triangle face (a,b,c):
(a, edgePoint ab, facePoint abc, edgePoint ca)
(b, edgePoint bc, facePoint abc, edgePoint ab)
(c, edgePoint ca, facePoint abc, edgePoint bc)
for a quad face (a,b,c,d):
(a, edgePoint ab, facePoint abcd, edgePoint da)
(b, edgePoint bc, facePoint abcd, edgePoint ab)
(c, edgePoint cd, facePoint abcd, edgePoint bc)
(d, edgePoint da, facePoint abcd, edgePoint cd)
facePoints is a list indexed by face number so that is easy to get.
edgePoints is a list indexed by the edge number which is an index into edgesFaces.
Need to add facePoints and edgePoints to newPoints and get index into each.
Then create two new structures:
facePointNums: list indexes by faceNum whose value is the index into newPoints.
edgePointNums: dictionary with key (pointNum1, pointNum2) and value is index into newPoints.
]#
# Add face points to newPoints.
var facePointNums: seq[int]
var nextPointNum = newPoints.len # PointNum after next append to newPoints.
for facePoint in facePoints:
newPoints.add(facePoint)
facePointNums.add(nextPointNum)
inc nextPointNum
# Add edge points to newPoints.
var edgePointNums: Table[tuple[pn1, pn2: int], int]
for edgeNum, edgesFace in edgesFaces:
let pointNum1 = edgesFace.pn1
let pointNum2 = edgesFace.pn2
newPoints.add(edgePoints[edgeNum])
edgePointNums[(pointNum1, pointNum2)] = nextPointNum
inc nextPointNum
# newPoints now has the points to output. Need new faces.
#[Just doing this case for now:
for a quad face (a,b,c,d):
(a, edgePoint ab, facePoint abcd, edgePoint da)
(b, edgePoint bc, facePoint abcd, edgePoint ab)
(c, edgePoint cd, facePoint abcd, edgePoint bc)
(d, edgePoint da, facePoint abcd, edgePoint cd)
newFaces will be a list of lists where the elements are like this:
[pointNum1, pointNum2, pointNum3, pointNum4]
]#
var newFaces: seq[Face]
for oldFaceNum, oldFace in inputFaces:
# 4 points face.
if oldFace.len == 4:
let (a, b, c, d) = (oldFace[0], oldface[1], oldface[2], oldface[3])
let facePointAbcd = facePointNums[oldFaceNum]
let edgePointAb = edgePointNums[switchNums((a, b))]
let edgePointDa = edgePointNums[switchNums((d, a))]
let edgePointBc = edgePointNums[switchNums((b, c))]
let edgePointCd = edgePointNums[switchNums((c, d))]
newFaces &= @[a, edgePointAb, facePointAbcd, edgePointDa]
newFaces &= @[b, edgePointBc, facePointAbcd, edgePointAb]
newFaces &= @[c, edgePointCd, facePointAbcd, edgePointBc]
newFaces &= @[d, edgePointDa, facePointAbcd, edgePointCd]
result = (newPoints, newFaces)
#———————————————————————————————————————————————————————————————————————————————————————————————————
when isMainModule:
import strformat, strutils
let inputPoints = @[[-1.0, 1.0, 1.0],
[-1.0, -1.0, 1.0],
[1.0, -1.0, 1.0],
[1.0, 1.0, 1.0],
[1.0, -1.0, -1.0],
[1.0, 1.0, -1.0],
[-1.0, -1.0, -1.0],
[-1.0, 1.0, -1.0]]
let inputFaces = @[@[0, 1, 2, 3],
@[3, 2, 4, 5],
@[5, 4, 6, 7],
@[7, 0, 3, 5],
@[7, 6, 1, 0],
@[6, 1, 2, 4]]
var outputPoints = inputPoints
var outputFaces = inputFaces
const Iterations = 1
for i in 1..Iterations:
(outputPoints, outputFaces) = cmcSubdiv(outputPoints, outputFaces)
for p in outputPoints:
echo fmt"[{p[0]: .4f}, {p[1]: .4f}, {p[2]: .4f}]"
echo ""
for nums in outputFaces:
var s = "["
for n in nums:
s.addSep(", ", 1)
s.add(fmt"{n:2d}")
s.add(']')
echo s</syntaxhighlight>
{{out}}
The output is the same as that of Go.
<pre>[-0.5556, 0.5556, 0.5556]
[-0.5556, -0.5556, 0.5556]
[ 0.5556, -0.5556, 0.5556]
[ 0.5556, 0.5556, 0.5556]
[ 0.5556, -0.5556, -0.5556]
[ 0.5556, 0.5556, -0.5556]
[-0.5556, -0.5556, -0.5556]
[-0.5556, 0.5556, -0.5556]
[ 0.0000, 0.0000, 1.0000]
[ 1.0000, 0.0000, 0.0000]
[ 0.0000, 0.0000, -1.0000]
[ 0.0000, 1.0000, 0.0000]
[-1.0000, 0.0000, 0.0000]
[ 0.0000, -1.0000, 0.0000]
[-0.7500, 0.0000, 0.7500]
[ 0.0000, 0.7500, 0.7500]
[-0.7500, 0.7500, 0.0000]
[ 0.0000, -0.7500, 0.7500]
[-0.7500, -0.7500, 0.0000]
[ 0.7500, 0.0000, 0.7500]
[ 0.7500, -0.7500, 0.0000]
[ 0.7500, 0.7500, 0.0000]
[ 0.7500, 0.0000, -0.7500]
[ 0.0000, -0.7500, -0.7500]
[ 0.0000, 0.7500, -0.7500]
[-0.7500, 0.0000, -0.7500]
[ 0, 14, 8, 15]
[ 1, 17, 8, 14]
[ 2, 19, 8, 17]
[ 3, 15, 8, 19]
[ 3, 19, 9, 21]
[ 2, 20, 9, 19]
[ 4, 22, 9, 20]
[ 5, 21, 9, 22]
[ 5, 22, 10, 24]
[ 4, 23, 10, 22]
[ 6, 25, 10, 23]
[ 7, 24, 10, 25]
[ 7, 16, 11, 24]
[ 0, 15, 11, 16]
[ 3, 21, 11, 15]
[ 5, 24, 11, 21]
[ 7, 25, 12, 16]
[ 6, 18, 12, 25]
[ 1, 14, 12, 18]
[ 0, 16, 12, 14]
[ 6, 18, 13, 23]
[ 1, 17, 13, 18]
[ 2, 20, 13, 17]
[ 4, 23, 13, 20]</pre>
=={{header|OCaml}}==
{{incorrect|OCaml|wrong output data}}
Line 790 ⟶ 1,546:
In the [[Catmull–Clark subdivision surface/OCaml|sub-page]] there is also a program in OCaml+OpenGL which displays a cube subdivided 2 times with this algorithm.
<
let add3 (x1, y1, z1) (x2, y2, z2) (x3, y3, z3) =
Line 925 ⟶ 1,681:
(Dynar.to_array da_points,
Dynar.to_array new_faces)
;;</
=== Another implementation ===
Another implementation which should work with holes, but has only been tested on a cube
{{works with|OCaml|4.02+}}
<
let zero = { x = 0.0; y = 0.0; z = 0.0 }
let add a b = { x = a.x+.b.x; y = a.y+.b.y; z = a.z+.b.z }
Line 1,002 ⟶ 1,758:
Face [c 0 0 0; c 0 1 0; c 1 1 0; c 1 0 0]; Face [c 0 0 1; c 0 1 1; c 1 1 1; c 1 0 1] ] in
show_faces cube;
show_faces (catmull_clark cube)</
with output:
<pre>surface {
Line 1,038 ⟶ 1,794:
Face: (0.7500, 0.0000, 0.7500) (0.5556, -0.5556, 0.5556) (0.0000, -0.7500, 0.7500) (0.0000, 0.0000, 1.0000)
}</pre>
=={{header|Phix}}==
{{trans|Go}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Catmull_Clark_subdivision_surface.exw</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">newPoint</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">newPointEx</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">newPoint</span><span style="color: #0000FF;">(),</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">centerPoint</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">sq_div</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p2</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">getFacePoints</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">facePoints</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">currFace</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">[</span><span style="color: #000000;">f</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">facePoint</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">currFace</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">currFace</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">facePoint</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">facePoint</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">currFace</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">facePoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">f</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_div</span><span style="color: #0000FF;">(</span><span style="color: #000000;">facePoint</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">currFace</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">facePoints</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">getEdgesFaces</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">edges</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">faceNum</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">face</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">[</span><span style="color: #000000;">faceNum</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">numPoints</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">face</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">pointIndex</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">numPoints</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">pointNum1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">face</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pointIndex</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">pointNum2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">face</span><span style="color: #0000FF;">[</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pointIndex</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">numPoints</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #000000;">pointIndex</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">:</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pointNum1</span> <span style="color: #0000FF;">></span> <span style="color: #000000;">pointNum2</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">pointNum1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pointNum2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">pointNum2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pointNum1</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">edges</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edges</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">pointNum1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pointNum2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">faceNum</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">edges</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edges</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">numEdges</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edges</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">eIndex</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">mergedEdges</span> <span style="color: #0000FF;">={}</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">eIndex</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">numEdges</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">e1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">eIndex</span><span style="color: #0000FF;">])</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">e4</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">eIndex</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">numEdges</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">e1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">edges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">eIndex</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">e4</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">eIndex</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">3</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">eIndex</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">e1</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">e4</span>
<span style="color: #000000;">mergedEdges</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mergedEdges</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">e1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">eIndex</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">edgesCenters</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mergedEdges</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">me</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mergedEdges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]),</span>
<span style="color: #000000;">cp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">centerPoint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">me</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]],</span>
<span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">me</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]])</span>
<span style="color: #000000;">me</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">me</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cp</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">edgesCenters</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edgesCenters</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">me</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">edgesCenters</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">getEdgePoints</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">edgesFaces</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">facePoints</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">edgePoints</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edgesFaces</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edgesFaces</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">edge</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">edgesFaces</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">cp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">edge</span><span style="color: #0000FF;">[</span><span style="color: #000000;">5</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">fp1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">facePoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">edge</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">]],</span>
<span style="color: #000000;">fp2</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edge</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4</span><span style="color: #0000FF;">]=-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #000000;">fp1</span><span style="color: #0000FF;">:</span><span style="color: #000000;">facePoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">edge</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4</span><span style="color: #0000FF;">]]),</span>
<span style="color: #000000;">cfp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">centerPoint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fp1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fp2</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">edgePoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">centerPoint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cfp</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">edgePoints</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">getAvgFacePoints</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">facePoints</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">numPoints</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tempPoints</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newPointEx</span><span style="color: #0000FF;">(),</span><span style="color: #000000;">numPoints</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">faceNum</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">fp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">facePoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">faceNum</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">[</span><span style="color: #000000;">faceNum</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">pointNum</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">[</span><span style="color: #000000;">faceNum</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tempPoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pointNum</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">tempPoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pointNum</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fp</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">tempPoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pointNum</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">avgFacePoints</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">numPoints</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tempPoints</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tempPoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">avgFacePoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_div</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tp</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">tp</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">avgFacePoints</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">getAvgMidEdges</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">edgesFaces</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">numPoints</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tempPoints</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newPointEx</span><span style="color: #0000FF;">(),</span> <span style="color: #000000;">numPoints</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edgesFaces</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">edge</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">edgesFaces</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">cp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">edge</span><span style="color: #0000FF;">[</span><span style="color: #000000;">5</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">edx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">pointNum</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">edge</span><span style="color: #0000FF;">[</span><span style="color: #000000;">edx</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tempPoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pointNum</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">tempPoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pointNum</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cp</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">tempPoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pointNum</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">avgMidEdges</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tempPoints</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tempPoints</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tempPoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">avgMidEdges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_div</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tp</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">tp</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">avgMidEdges</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">getPointsFaces</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">numPoints</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">pointsFaces</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">numPoints</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">faceNum</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">[</span><span style="color: #000000;">faceNum</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">pointNum</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">[</span><span style="color: #000000;">faceNum</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">pointsFaces</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pointNum</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">pointsFaces</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">getNewPoints</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pointsFaces</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">avgFacePoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">avgMidEdges</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">newPoints</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">pointNum</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pointsFaces</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pointNum</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pointNum</span><span style="color: #0000FF;">],</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">p2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">avgFacePoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pointNum</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">/</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">p3</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">avgMidEdges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pointNum</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">/</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">newPoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pointNum</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p2</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">p3</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">newPoints</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">switchNums</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">pointNums</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pointNums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">pointNums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">pointNums</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">pointNums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">pointNums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">cmcSubdiv</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">facePoints</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">getFacePoints</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">edgesFaces</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">getEdgesFaces</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">edgePoints</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">getEdgePoints</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">edgesFaces</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">facePoints</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">avgFacePoints</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">getAvgFacePoints</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">facePoints</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">avgMidEdges</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">getAvgMidEdges</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">edgesFaces</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">pointsFaces</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">getPointsFaces</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">newPoints</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">getNewPoints</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pointsFaces</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">avgFacePoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">avgMidEdges</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">facePointNums</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nextPointNum</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newPoints</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">facePoints</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">facePoint</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">facePoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">newPoints</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">facePoint</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">facePointNums</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">facePointNums</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nextPointNum</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">nextPointNum</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">edgePointNums</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">edgeNum</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edgesFaces</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">pointNum1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pointNum2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">edgesFaces</span><span style="color: #0000FF;">[</span><span style="color: #000000;">edgeNum</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">edgePoint</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">edgePoints</span><span style="color: #0000FF;">[</span><span style="color: #000000;">edgeNum</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">newPoints</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">edgePoint</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">({</span><span style="color: #000000;">pointNum1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pointNum2</span><span style="color: #0000FF;">},</span><span style="color: #000000;">nextPointNum</span><span style="color: #0000FF;">,</span><span style="color: #000000;">edgePointNums</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">nextPointNum</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">newFaces</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">oldFaceNum</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">oldFace</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">[</span><span style="color: #000000;">oldFaceNum</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">oldFace</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">4</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">oldFace</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">facePointAbcd</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">facePointNums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">oldFaceNum</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">edgePointAb</span> <span style="color: #0000FF;">:=</span> <span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">switchNums</span><span style="color: #0000FF;">({</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">}),</span><span style="color: #000000;">edgePointNums</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">edgePointDa</span> <span style="color: #0000FF;">:=</span> <span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">switchNums</span><span style="color: #0000FF;">({</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">}),</span><span style="color: #000000;">edgePointNums</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">edgePointBc</span> <span style="color: #0000FF;">:=</span> <span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">switchNums</span><span style="color: #0000FF;">({</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">}),</span><span style="color: #000000;">edgePointNums</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">edgePointCd</span> <span style="color: #0000FF;">:=</span> <span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">switchNums</span><span style="color: #0000FF;">({</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">}),</span><span style="color: #000000;">edgePointNums</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">newFaces</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newFaces</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">edgePointAb</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">facePointAbcd</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">edgePointDa</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">newFaces</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newFaces</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">edgePointBc</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">facePointAbcd</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">edgePointAb</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">newFaces</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newFaces</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">edgePointCd</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">facePointAbcd</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">edgePointBc</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">newFaces</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newFaces</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">edgePointDa</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">facePointAbcd</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">edgePointCd</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">newPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">newFaces</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">inputPoints</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span>
<span style="color: #000000;">inputFaces</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">}}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">outputPoints</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inputPoints</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">outputFaces</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inputFaces</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">iterations</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">iterations</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">outputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">outputFaces</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cmcSubdiv</span><span style="color: #0000FF;">(</span><span style="color: #000000;">outputPoints</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">outputFaces</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">ppOpt</span><span style="color: #0000FF;">({</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_FltFmt</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%7.4f"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_IntFmt</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%7.4f"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">})</span>
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">outputPoints</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">outputFaces</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),{</span><span style="color: #004600;">pp_IntFmt</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%2d"</span><span style="color: #0000FF;">})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{{-0.5556, 0.5556, 0.5556},
{-0.5556,-0.5556, 0.5556},
{ 0.5556,-0.5556, 0.5556},
{ 0.5556, 0.5556, 0.5556},
{ 0.5556,-0.5556,-0.5556},
{ 0.5556, 0.5556,-0.5556},
{-0.5556,-0.5556,-0.5556},
{-0.5556, 0.5556,-0.5556},
{ 0.0000, 0.0000, 1.0000},
{ 1.0000, 0.0000, 0.0000},
{ 0.0000, 0.0000,-1.0000},
{ 0.0000, 1.0000, 0.0000},
{-1.0000, 0.0000, 0.0000},
{ 0.0000,-1.0000, 0.0000},
{-0.7500, 0.0000, 0.7500},
{ 0.0000, 0.7500, 0.7500},
{-0.7500, 0.7500, 0.0000},
{ 0.0000,-0.7500, 0.7500},
{-0.7500,-0.7500, 0.0000},
{ 0.7500, 0.0000, 0.7500},
{ 0.7500,-0.7500, 0.0000},
{ 0.7500, 0.7500, 0.0000},
{ 0.7500, 0.0000,-0.7500},
{ 0.0000,-0.7500,-0.7500},
{ 0.0000, 0.7500,-0.7500},
{-0.7500, 0.0000,-0.7500}}
{{ 0,14, 8,15},
{ 1,17, 8,14},
{ 2,19, 8,17},
{ 3,15, 8,19},
{ 3,19, 9,21},
{ 2,20, 9,19},
{ 4,22, 9,20},
{ 5,21, 9,22},
{ 5,22,10,24},
{ 4,23,10,22},
{ 6,25,10,23},
{ 7,24,10,25},
{ 7,16,11,24},
{ 0,15,11,16},
{ 3,21,11,15},
{ 5,24,11,21},
{ 7,25,12,16},
{ 6,18,12,25},
{ 1,14,12,18},
{ 0,16,12,14},
{ 6,18,13,23},
{ 1,17,13,18},
{ 2,20,13,17},
{ 4,23,13,20}}
</pre>
=={{header|Python}}==
<
"""
Line 1,354 ⟶ 2,382:
"""
m1 = (n - 3.0) / n
m2 = 1.0 / n
m3 = 2.0 / n
new_coords = (m1 * old_coords)
+ (m2 * avg_face_points)
Line 1,367 ⟶ 2,395:
for pointnum in range(len(input_points)):
n = points_faces[pointnum]
m1 = (n - 3.0) / n
m2 = 1.0 / n
m3 = 2.0 / n
old_coords = input_points[pointnum]
p1 = mul_point(old_coords, m1)
Line 1,597 ⟶ 2,625:
graph_output(output_points, output_faces)
</syntaxhighlight>
=={{header|Rust}}==
{{trans|Python}}
<syntaxhighlight lang="rust">
pub struct Vector3 {pub x: f64, pub y: f64, pub z: f64, pub w: f64}
pub struct Triangle {pub r: [usize; 3], pub(crate) col: [f32; 4], pub(crate) p: [Vector3; 3], n: Vector3, pub t: [Vector2; 3]}
pub struct Mesh{pub v: Vec<Vector3>, pub f: Vec<Triangle>}
impl Triangle{
pub fn new() -> Triangle {return Triangle {r: [0, 0, 0], col: [0.0; 4], p: [Vector3::new(0.0, 0.0, 0.0), Vector3::new(0.0, 0.0, 0.0), Vector3::new(0.0, 0.0, 0.0)], n: Vector3::new(0.0, 0.0, 0.0), t: [Vector2::new(0.0, 0.0), Vector2::new(0.0, 0.0), Vector2::new(0.0, 0.0)]}}
pub fn copy(&self) -> Triangle {return Triangle {r: self.r.clone(), col: self.col, p: [self.p[0].copy(), self.p[1].copy(), self.p[2].copy()], n: self.n.copy(), t: [self.t[0].copy(), self.t[1].copy(), self.t[2].copy()]}}
}
impl Vector3 {
pub fn new(x: f64, y: f64, z: f64) -> Vector3 {return Vector3 {x, y, z, w: 1.0}}
pub fn normalize(&mut self) {
let l = (self.x * self.x + self.y * self.y + self.z * self.z).sqrt();
self.x /= l;
self.y /= l;
self.z /= l;
}
pub fn dot_product(v1: &Vector3, v2: &Vector3) -> f64 {return v1.x * v2.x + v1.y * v2.y + v1.z * v2.z}
pub fn cross_product(v1: &Vector3, v2: &Vector3) -> Vector3 {return Vector3::new(v1.y * v2.z - v1.z * v2.y, v1.z * v2.x - v1.x * v2.z, v1.x * v2.y - v1.y * v2.x)}
pub fn intersect_plane(plane_n: &Vector3, plane_p: &Vector3, line_start: &Vector3, line_end: &Vector3, mut t: f64) -> Vector3 {
let mut p_n = plane_n.copy();
p_n.normalize();
let plane_d = -Vector3::dot_product(&p_n, plane_p);
let ad = Vector3::dot_product(line_start, &p_n);
let bd = Vector3::dot_product(line_end, &p_n);
t = (-plane_d - ad) / (bd - ad);
let line = line_end.copy() - line_start;
let line_i = line * t;
return line_start.copy() + &line_i;
}
pub fn copy(&self) -> Vector3 {return Vector3 {x: self.x, y: self.y, z: self.z, w: self.w}}
}
impl Mesh {
pub fn get_face_points(&self) -> Vec<Vector3> {
let mut face_points: Vec<Vector3> = Vec::new();
for curr_face in &self.f {
let mut face_point = Vector3::new(0.0, 0.0, 0.0);
for curr_point_index in curr_face.r {
let curr_point = &self.v[curr_point_index];
face_point += &curr_point
}
face_point /= curr_face.r.len() as f64;
face_points.push(face_point.copy());
}
return face_points;
}
pub fn get_edges_faces(&self) -> Vec<[f64; 7]> {
let mut edges: Vec<[usize; 3]> = Vec::new();
for face_num in 0..self.f.len() {
let face: Triangle = self.f[face_num].copy();
let num_points = face.p.len();
for point_index in 0..num_points {
let mut point_num_1 = 0;
let mut point_num_2 = 0;
if point_index < num_points - 1 {
point_num_1 = face.r[point_index];
point_num_2 = face.r[point_index + 1];
} else {
point_num_1 = face.r[point_index];
point_num_2 = face.r[0];
}
if point_num_1 > point_num_2 {
let temp = point_num_1;
point_num_1 = point_num_2;
point_num_2 = temp;
}
edges.push([point_num_1, point_num_2, face_num]);
}
}
edges.sort();
let num_edges = edges.len();
let mut index = 0;
let mut merged_edges: Vec<[f64; 4]> = Vec::new();
while index < num_edges {
let e1 = edges[index];
if index < num_edges - 1 {
let e2 = edges[index + 1];
if e1[0] == e2[0] && e1[1] == e2[1] {
merged_edges.push([e1[0] as f64, e1[1] as f64, e1[2] as f64, e2[2] as f64]);
index += 2;
} else {
merged_edges.push([e1[0] as f64, e1[1] as f64, e1[2] as f64, -1.0]);
index += 1;
}
} else {
merged_edges.push([e1[0] as f64, e1[1] as f64, e1[2] as f64, -1.0]);
index += 1
}
}
let mut edges_centers = Vec::new();
for me in merged_edges {
let p1 = self.v[me[0] as usize].copy();
let p2 = self.v[me[1] as usize].copy();
let cp: Vector3 = Mesh::center_point(&p1, &p2);
edges_centers.push([me[0] as f64, me[1] as f64, me[2] as f64, me[3] as f64, cp.x, cp.y, cp.z]);
}
return edges_centers;
}
pub fn get_edge_points(&self, edges_faces: &Vec<[f64; 7]>, face_points: &Vec<Vector3>) -> Vec<Vector3> {
let mut edge_points = Vec::new();
for edge in edges_faces {
let cp = Vector3::new(edge[4], edge[5], edge[6]);
let fp1: Vector3 = face_points[edge[2] as usize].copy();
let mut fp2: Vector3 = fp1.copy();
if edge[3] != -1.0 { fp2 = face_points[edge[3] as usize].copy() };
let cfp = Mesh::center_point(&fp1, &fp2);
let edge_point = Mesh::center_point(&cp, &cfp);
edge_points.push(edge_point);
}
return edge_points
}
pub fn get_avg_face_points(&self, face_points: &Vec<Vector3>) -> Vec<Vector3> {
let num_points = self.v.len();
let mut temp_points = Vec::new();
let mut div: Vec<i32> = Vec::new();
for _ in 0..num_points {
temp_points.push(Vector3::new(0.0, 0.0, 0.0));
div.push(0)
};
for face_num in 0..self.f.len() {
let mut fp = face_points[face_num].copy();
for point_num in self.f[face_num].r {
let tp = temp_points[point_num].copy();
temp_points[point_num] = tp + &fp;
div[point_num] += 1;
}
}
let mut avg_face_points: Vec<Vector3> = Vec::new();
for i in 0..temp_points.len() {
let tp: Vector3 = temp_points[i].copy();
let t = tp / (div[i] as f64);
avg_face_points.push(t.copy());
}
return avg_face_points;
}
pub fn get_avg_mid_edges(&self, edges_faces: &Vec<[f64; 7]>) -> Vec<Vector3> {
let num_points = self.v.len();
let mut temp_points = Vec::new();
let mut div: Vec<i32> = Vec::new();
for point_num in 0..num_points{ temp_points.push(Vector3::new(0.0, 0.0, 0.0)); div.push(0)}
for edge in edges_faces {
let cp = Vector3::new(edge[4], edge[5], edge[6]);
for point_num in [edge[0] as usize, edge[1] as usize] {
let tp = temp_points[point_num].copy();
temp_points[point_num] = tp + &cp;
div[point_num] += 1
}
}
let mut avg_mid_edges: Vec<Vector3> = Vec::new();
for i in 0..temp_points.len(){
let ame: Vector3 = temp_points[i].copy() / (div[i] as f64);
avg_mid_edges.push(ame)}
return avg_mid_edges
}
pub fn get_points_faces(&self) -> Vec<i32> {
let num_points = self.v.len();
let mut points_faces: Vec<i32> = Vec::new();
for point_num in 0..num_points{points_faces.push(0)}
for face_num in 0..self.f.len() {
for point_num in self.f[face_num].r {
points_faces[point_num] += 1;
}
}
return points_faces
}
pub fn get_new_points(&self, points_faces: &Vec<i32>, avg_face_points: &Vec<Vector3>, avg_mid_edges: &Vec<Vector3>) -> Vec<Vector3> {
let mut new_points: Vec<Vector3> = Vec::new();
for point_num in 0..self.v.len() {
let n = points_faces[point_num] as f64;
let m1 = (n - 3.0) / n;
let m2 = 1.0 / n;
let m3 = 2.0 / n;
let old_coords = self.v[point_num].copy();
let p1 = old_coords * m1;
let afp = avg_face_points[point_num].copy();
let p2 = afp * m2;
let ame = avg_mid_edges[point_num].copy();
let p3 = ame * m3;
let p4 = p1 + &p2;
let new_coords = p4 + &p3;
new_points.push(new_coords);
}
return new_points;
}
pub fn switch_nums(point_nums: [f64; 2]) -> [f64; 2] {
return if point_nums[0] < point_nums[1] { point_nums } else {[point_nums[1], point_nums[0]]}
}
pub fn get_key(points: [f64; 2]) -> String {
return points[0].to_string() + ";" + &*points[1].to_string();
}
pub fn subdivide(&mut self) {
let face_points = self.get_face_points();
let edges_faces = self.get_edges_faces();
let edge_points = self.get_edge_points(&edges_faces, &face_points);
let avg_face_points = self.get_avg_face_points(&face_points);
let avg_mid_edges = self.get_avg_mid_edges(&edges_faces);
let points_faces = self.get_points_faces();
let mut new_points = self.get_new_points(&points_faces, &avg_face_points, &avg_mid_edges);
let mut face_point_nums = Vec::new();
let mut next_point_num = new_points.len();
for face_point in face_points {
new_points.push(face_point);
face_point_nums.push(next_point_num);
next_point_num += 1;
}
let mut edge_point_nums: HashMap<String, usize> = HashMap::new();
for edge_num in 0..edges_faces.len() {
let point_num_1 = edges_faces[edge_num][0];
let point_num_2 = edges_faces[edge_num][1];
let edge_point = edge_points[edge_num].copy();
new_points.push(edge_point);
edge_point_nums.insert(Mesh::get_key([point_num_1, point_num_2]), next_point_num);
next_point_num += 1;
}
let mut new_faces = Vec::new();
for old_face_num in 0..self.f.len() {
let old_face = self.f[old_face_num].copy();
let a = old_face.r[0] as f64;
let b = old_face.r[1] as f64;
let c = old_face.r[2] as f64;
let face_point_abc = face_point_nums[old_face_num];
let edge_point_ab = *edge_point_nums.get(&*Mesh::get_key(Mesh::switch_nums([a, b]))).unwrap();
let edge_point_bc = *edge_point_nums.get(&*Mesh::get_key(Mesh::switch_nums([b, c]))).unwrap();
let edge_point_ca = *edge_point_nums.get(&*Mesh::get_key(Mesh::switch_nums([c, a]))).unwrap();
new_faces.push([a, edge_point_ab as f64, face_point_abc as f64, edge_point_ca as f64]);
new_faces.push([b, edge_point_bc as f64, face_point_abc as f64, edge_point_ab as f64]);
new_faces.push([c, edge_point_ca as f64, face_point_abc as f64, edge_point_bc as f64]);
}
self.f = Vec::new();
for face_num in 0..new_faces.len() {
let curr_face = new_faces[face_num];
let mut t1: Triangle = Triangle::new();
let mut t2: Triangle = Triangle::new();
t1.p[0] = Vector3::new(new_points[curr_face[0] as usize].x, new_points[curr_face[0] as usize].y, new_points[curr_face[0] as usize].z);
t1.p[1] = Vector3::new(new_points[curr_face[1] as usize].x, new_points[curr_face[1] as usize].y, new_points[curr_face[1] as usize].z);
t1.p[2] = Vector3::new(new_points[curr_face[2] as usize].x, new_points[curr_face[2] as usize].y, new_points[curr_face[2] as usize].z);
t2.p[0] = Vector3::new(new_points[curr_face[2] as usize].x, new_points[curr_face[2] as usize].y, new_points[curr_face[2] as usize].z);
t2.p[1] = Vector3::new(new_points[curr_face[3] as usize].x, new_points[curr_face[3] as usize].y, new_points[curr_face[3] as usize].z);
t2.p[2] = Vector3::new(new_points[curr_face[0] as usize].x, new_points[curr_face[0] as usize].y, new_points[curr_face[0] as usize].z);
t1.r = [curr_face[0] as usize, curr_face[1] as usize, curr_face[2] as usize];
t2.r = [curr_face[2] as usize, curr_face[3] as usize, curr_face[0] as usize];
self.f.push(t1);
self.f.push(t2);
}
self.v = new_points;
}
}
</syntaxhighlight>
=={{header|Tcl}}==
This code handles both holes and arbitrary polygons in the input data.
<
# Use math functions and operators as commands (Lisp-like).
Line 1,722 ⟶ 3,036:
list [concat $newPoints $facepoints $edgepoints] $newFaces
}</
The [[/Tcl Test Code|test code]] for this solution is available as well. The example there produces the following partial toroid output image:
<center>[[File:Tcl-Catmull.png]]</center>
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-dynamic}}
{{libheader|Wren-sort}}
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./dynamic" for Tuple, Struct
import "./sort" for Sort
import "./math" for Int
import "./fmt" for Fmt
var Point = Tuple.create("Point", ["x", "y", "z"])
var fields = [
"pn1", // point number 1
"pn2", // point number 2
"fn1", // face number 1
"fn2", // face number 2
"cp" // center point
]
var Edge = Tuple.create("Edge", fields)
var PointEx = Struct.create("PointEx", ["p", "n"])
var sumPoint = Fn.new { |p1, p2| Point.new(p1.x + p2.x, p1.y + p2.y, p1.z + p2.z) }
var mulPoint = Fn.new { |p, m| Point.new(p.x * m, p.y * m, p.z * m) }
var divPoint = Fn.new { |p, d| mulPoint.call(p, 1/d) }
var centerPoint = Fn.new { |p1, p2| divPoint.call(sumPoint.call(p1, p2), 2) }
var getFacePoints = Fn.new { |inputPoints, inputFaces|
var facePoints = List.filled(inputFaces.count, null)
var i = 0
for (currFace in inputFaces) {
var facePoint = Point.new(0, 0, 0)
for (cpi in currFace) {
var currPoint = inputPoints[cpi]
facePoint = sumPoint.call(facePoint, currPoint)
}
facePoints[i] = divPoint.call(facePoint, currFace.count)
i = i + 1
}
return facePoints
}
var getEdgesFaces = Fn.new { |inputPoints, inputFaces|
var edges = []
var faceNum = 0
for (face in inputFaces) {
var numPoints = face.count
for (pointIndex in 0...numPoints) {
var pointNum1 = face[pointIndex]
var pointNum2 = (pointIndex < numPoints-1) ? face[pointIndex+1] : face[0]
if (pointNum1 > pointNum2) {
var t = pointNum1
pointNum1 = pointNum2
pointNum2 = t
}
edges.add([pointNum1, pointNum2, faceNum])
}
faceNum = faceNum + 1
}
var cmp = Fn.new { |e1, e2|
if (e1[0] == e2[0]) {
if (e1[1] == e2[1]) return (e1[2] - e2[2]).sign
return (e1[1] - e2[1]).sign
}
return (e1[0] - e2[0]).sign
}
var numEdges = edges.count
Sort.quick(edges, 0, numEdges-1, cmp)
var eIndex = 0
var mergedEdges = []
while (eIndex < numEdges) {
var e1 = edges[eIndex]
if (eIndex < numEdges-1) {
var e2 = edges[eIndex+1]
if (e1[0] == e2[0] && e1[1] == e2[1]) {
mergedEdges.add([e1[0], e1[1], e1[2], e2[2]])
eIndex = eIndex + 2
} else {
mergedEdges.add([e1[0], e1[1], e1[2], -1])
eIndex = eIndex + 1
}
} else {
mergedEdges.add([e1[0], e1[1], e1[2], -1])
eIndex = eIndex + 1
}
}
var edgesCenters = []
for (me in mergedEdges) {
var p1 = inputPoints[me[0]]
var p2 = inputPoints[me[1]]
var cp = centerPoint.call(p1, p2)
edgesCenters.add(Edge.new(me[0], me[1], me[2], me[3], cp))
}
return edgesCenters
}
var getEdgePoints = Fn.new { |inputPoints, edgesFaces, facePoints|
var edgePoints = List.filled(edgesFaces.count, null)
var i = 0
for (edge in edgesFaces) {
var cp = edge.cp
var fp1 = facePoints[edge.fn1]
var fp2 = (edge.fn2 == -1) ? fp1 : facePoints[edge.fn2]
var cfp = centerPoint.call(fp1, fp2)
edgePoints[i] = centerPoint.call(cp, cfp)
i = i + 1
}
return edgePoints
}
var getAvgFacePoints = Fn.new { |inputPoints, inputFaces, facePoints|
var numPoints = inputPoints.count
var tempPoints = List.filled(numPoints, null)
for (i in 0...numPoints) tempPoints[i] = PointEx.new(Point.new(0, 0, 0), 0)
for (faceNum in 0...inputFaces.count) {
var fp = facePoints[faceNum]
for (pointNum in inputFaces[faceNum]) {
var tp = tempPoints[pointNum].p
tempPoints[pointNum].p = sumPoint.call(tp, fp)
tempPoints[pointNum].n = tempPoints[pointNum].n + 1
}
}
var avgFacePoints = List.filled(numPoints, null)
var i = 0
for (tp in tempPoints) {
avgFacePoints[i] = divPoint.call(tp.p, tp.n)
i = i + 1
}
return avgFacePoints
}
var getAvgMidEdges = Fn.new { |inputPoints, edgesFaces|
var numPoints = inputPoints.count
var tempPoints = List.filled(numPoints, null)
for (i in 0...numPoints) tempPoints[i] = PointEx.new(Point.new(0, 0, 0), 0)
for (edge in edgesFaces) {
var cp = edge.cp
for (pointNum in [edge.pn1, edge.pn2]) {
var tp = tempPoints[pointNum].p
tempPoints[pointNum].p = sumPoint.call(tp, cp)
tempPoints[pointNum].n = tempPoints[pointNum].n + 1
}
}
var avgMidEdges = List.filled(tempPoints.count, null)
var i = 0
for (tp in tempPoints) {
avgMidEdges[i] = divPoint.call(tp.p, tp.n)
i = i + 1
}
return avgMidEdges
}
var getPointsFaces = Fn.new { |inputPoints, inputFaces|
var numPoints = inputPoints.count
var pointsFaces = List.filled(numPoints, 0)
for (faceNum in 0...inputFaces.count) {
for (pointNum in inputFaces[faceNum]) {
pointsFaces[pointNum] = pointsFaces[pointNum] + 1
}
}
return pointsFaces
}
var getNewPoints = Fn.new { |inputPoints, pointsFaces, avgFacePoints, avgMidEdges|
var newPoints = List.filled(inputPoints.count, null)
for (pointNum in 0...inputPoints.count) {
var n = pointsFaces[pointNum]
var m1 = (n-3) / n
var m2 = 1 / n
var m3 = 2 / n
var oldCoords = inputPoints[pointNum]
var p1 = mulPoint.call(oldCoords, m1)
var afp = avgFacePoints[pointNum]
var p2 = mulPoint.call(afp, m2)
var ame = avgMidEdges[pointNum]
var p3 = mulPoint.call(ame, m3)
var p4 = sumPoint.call(p1, p2)
newPoints[pointNum] = sumPoint.call(p4, p3)
}
return newPoints
}
var switchNums = Fn.new { |pointNums|
if (pointNums[0] < pointNums[1]) return pointNums
return [pointNums[1], pointNums[0]]
}
var cmcSubdiv = Fn.new { |inputPoints, inputFaces|
var facePoints = getFacePoints.call(inputPoints, inputFaces)
var edgesFaces = getEdgesFaces.call(inputPoints, inputFaces)
var edgePoints = getEdgePoints.call(inputPoints, edgesFaces, facePoints)
var avgFacePoints = getAvgFacePoints.call(inputPoints, inputFaces, facePoints)
var avgMidEdges = getAvgMidEdges.call(inputPoints, edgesFaces)
var pointsFaces = getPointsFaces.call(inputPoints, inputFaces)
var newPoints = getNewPoints.call(inputPoints, pointsFaces, avgFacePoints, avgMidEdges)
var facePointNums = []
var nextPointNum = newPoints.count
for (facePoint in facePoints) {
newPoints.add(facePoint)
facePointNums.add(nextPointNum)
nextPointNum = nextPointNum + 1
}
var edgePointNums = {}
for (edgeNum in 0...edgesFaces.count) {
var pointNum1 = edgesFaces[edgeNum].pn1
var pointNum2 = edgesFaces[edgeNum].pn2
var edgePoint = edgePoints[edgeNum]
newPoints.add(edgePoint)
edgePointNums[Int.cantorPair(pointNum1, pointNum2)] = nextPointNum
nextPointNum = nextPointNum + 1
}
var newFaces = []
var oldFaceNum = 0
for (oldFace in inputFaces) {
if (oldFace.count == 4) {
var a = oldFace[0]
var b = oldFace[1]
var c = oldFace[2]
var d = oldFace[3]
var facePointAbcd = facePointNums[oldFaceNum]
var p = switchNums.call([a, b])
var edgePointAb = edgePointNums[Int.cantorPair(p[0], p[1])]
p = switchNums.call([d, a])
var edgePointDa = edgePointNums[Int.cantorPair(p[0], p[1])]
p = switchNums.call([b, c])
var edgePointBc = edgePointNums[Int.cantorPair(p[0], p[1])]
p = switchNums.call([c, d])
var edgePointCd = edgePointNums[Int.cantorPair(p[0], p[1])]
newFaces.add([a, edgePointAb, facePointAbcd, edgePointDa])
newFaces.add([b, edgePointBc, facePointAbcd, edgePointAb])
newFaces.add([c, edgePointCd, facePointAbcd, edgePointBc])
newFaces.add([d, edgePointDa, facePointAbcd, edgePointCd])
}
oldFaceNum = oldFaceNum + 1
}
return [newPoints, newFaces]
}
var inputPoints = [
Point.new(-1, 1, 1),
Point.new(-1, -1, 1),
Point.new( 1, -1, 1),
Point.new( 1, 1, 1),
Point.new( 1, -1, -1),
Point.new( 1, 1, -1),
Point.new(-1, -1, -1),
Point.new(-1, 1, -1)
]
var inputFaces = [
[0, 1, 2, 3],
[3, 2, 4, 5],
[5, 4, 6, 7],
[7, 0, 3, 5],
[7, 6, 1, 0],
[6, 1, 2, 4]
]
var outputPoints = inputPoints.toList
var outputFaces = inputFaces.toList
var iterations = 1
for (i in 0...iterations) {
var res = cmcSubdiv.call(outputPoints, outputFaces)
outputPoints = res[0]
outputFaces = res[1]
}
for (p in outputPoints) {
Fmt.aprint([p.x, p.y, p.z], 7, 4, "[]")
}
System.print()
for (f in outputFaces) {
Fmt.aprint(f, 2, 0, "[]")
}</syntaxhighlight>
{{out}}
<pre>
[-0.5556 0.5556 0.5556]
[-0.5556 -0.5556 0.5556]
[ 0.5556 -0.5556 0.5556]
[ 0.5556 0.5556 0.5556]
[ 0.5556 -0.5556 -0.5556]
[ 0.5556 0.5556 -0.5556]
[-0.5556 -0.5556 -0.5556]
[-0.5556 0.5556 -0.5556]
[ 0.0000 0.0000 1.0000]
[ 1.0000 0.0000 0.0000]
[ 0.0000 0.0000 -1.0000]
[ 0.0000 1.0000 0.0000]
[-1.0000 0.0000 0.0000]
[ 0.0000 -1.0000 0.0000]
[-0.7500 0.0000 0.7500]
[ 0.0000 0.7500 0.7500]
[-0.7500 0.7500 0.0000]
[ 0.0000 -0.7500 0.7500]
[-0.7500 -0.7500 0.0000]
[ 0.7500 0.0000 0.7500]
[ 0.7500 -0.7500 0.0000]
[ 0.7500 0.7500 0.0000]
[ 0.7500 0.0000 -0.7500]
[ 0.0000 -0.7500 -0.7500]
[ 0.0000 0.7500 -0.7500]
[-0.7500 0.0000 -0.7500]
[ 0 14 8 15]
[ 1 17 8 14]
[ 2 19 8 17]
[ 3 15 8 19]
[ 3 19 9 21]
[ 2 20 9 19]
[ 4 22 9 20]
[ 5 21 9 22]
[ 5 22 10 24]
[ 4 23 10 22]
[ 6 25 10 23]
[ 7 24 10 25]
[ 7 16 11 24]
[ 0 15 11 16]
[ 3 21 11 15]
[ 5 24 11 21]
[ 7 25 12 16]
[ 6 18 12 25]
[ 1 14 12 18]
[ 0 16 12 14]
[ 6 18 13 23]
[ 1 17 13 18]
[ 2 20 13 17]
[ 4 23 13 20]
</pre>
| |||