Catmull–Clark subdivision surface: Difference between revisions
New post.
m (→{{header|Wren}}: Minor tidy) |
(New post.) |
||
Line 913:
│ │ 0.555556 0.555556 0.555556│
└──────────┴─────────────────────────────┘</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public final class SurfaceSubdivision {
public static void main(String[] args) {
List<Point> points = List.of( new Point(-1.0, 1.0, 1.0),
new Point(-1.0, -1.0, 1.0),
new Point( 1.0, -1.0, 1.0),
new Point( 1.0, 1.0, 1.0),
new Point( 1.0, -1.0, -1.0),
new Point( 1.0, 1.0, -1.0),
new Point(-1.0, -1.0, -1.0),
new Point(-1.0, 1.0, -1.0) );
List<List<Integer>> faces = List.of( List.of( 0, 1, 2, 3 ),
List.of( 3, 2, 4, 5 ),
List.of( 5, 4, 6, 7 ),
List.of( 7, 0, 3, 5 ),
List.of( 7, 6, 1, 0 ),
List.of( 6, 1, 2, 4 ) );
ListPair result = new ListPair(points, faces);
final int iterations = 1;
for ( int i = 0; i < iterations; i++ ) {
result = catmullClarkSurfaceSubdivision(result.points, result.faces);
}
for ( Point point : result.points ) {
System.out.println(point);
}
System.out.println();
for ( List<Integer> face : result.faces ) {
System.out.println(face);
}
}
private static ListPair catmullClarkSurfaceSubdivision(List<Point> points, List<List<Integer>> faces) {
List<Point> facePoints = facePoints(points, faces);
List<Edge> edges = edges(points, faces);
List<Point> edgePoints = edgePoints(points, facePoints, edges);
List<Point> averageFacePoints = averageFacePoints(points, faces, facePoints);
List<Point> averageEdgeCentres = averageEdgeCentres(points, edges);
List<Integer> facesCount = facesCount(points, faces);
List<Point> newPoints = newPoints(points, facesCount, averageFacePoints, averageEdgeCentres);
List<Integer> facePointIndexes = new ArrayList<Integer>();
int facePointIndex = newPoints.size();
for ( Point facePoint : facePoints ) {
newPoints.add(facePoint);
facePointIndexes.addLast(facePointIndex);
facePointIndex += 1;
}
Map<Long, Integer> edgePointIndexes = new HashMap<Long, Integer>();
for ( int edgeIndex = 0; edgeIndex < edges.size(); edgeIndex++ ) {
final int pointOne = edges.get(edgeIndex).pointOne;
final int pointTwo = edges.get(edgeIndex).pointTwo;
Point edgePoint = edgePoints.get(edgeIndex);
newPoints.add(edgePoint);
edgePointIndexes.put(szudzikHash( new IndexPair(pointOne, pointTwo) ), facePointIndex);
facePointIndex += 1;
}
List<List<Integer>> newFaces = new ArrayList<List<Integer>>();
for ( List<Integer> face : faces ) { // The face can contain any number of points
if ( face.size() >= 3 ) { // A face with 2 or less points does not contribute to the surface
final int fullFace = facePointIndexes.get(faces.indexOf(face));
IndexPair pair = order( new IndexPair(face.getLast(), face.getFirst()) );
int edgePoint = edgePointIndexes.get(szudzikHash(pair));
for ( int i = 0; i < face.size(); i++ ) {
IndexPair previousPair = order( new IndexPair(face.get(i), face.get(( i + 1 ) % face.size())) );
final int previousEdgePoint = edgePointIndexes.get(szudzikHash(previousPair));
newFaces.addLast(List.of( face.get(i), previousEdgePoint, fullFace, edgePoint ));
edgePoint = previousEdgePoint;
}
}
}
return new ListPair(newPoints, newFaces);
}
// Return the new points created by the current iteration of the Catmull-Clark surface subdivision algorithm.
private static List<Point> newPoints(List<Point> points, List<Integer> facesCount,
List<Point> averageFacePoints, List<Point> averageEdgeCentres) {
List<Point> newPoints = new ArrayList<Point>();
for ( int pointIndex = 0; pointIndex < points.size(); pointIndex++ ) {
final int faceCount = facesCount.get(pointIndex);
final double multipleOne = (double) ( faceCount - 3 ) / faceCount;
final double multipleTwo = 1.0 / faceCount;
final double multipleThree = 2.0 / faceCount;
Point currentPoint = points.get(pointIndex);
Point pointOne = currentPoint.scalarMultiply(multipleOne);
Point averageFacePoint = averageFacePoints.get(pointIndex);
Point pointTwo = averageFacePoint.scalarMultiply(multipleTwo);
Point averageEdgeCentre = averageEdgeCentres.get(pointIndex);
Point pointThree = averageEdgeCentre.scalarMultiply(multipleThree);
Point pointFour = pointOne.add(pointTwo);
newPoints.addLast(pointFour.add(pointThree));
}
return newPoints;
}
// Return a list containing a value for each point, which is the number of faces containing that point.
private static List<Integer> facesCount(List<Point> points, List<List<Integer>> faces) {
List<Integer> pointsFaces = Stream.generate( () -> 0 ).limit(points.size()).collect(Collectors.toList());
for ( List<Integer> face : faces ) {
for ( int pointIndex : face ) {
pointsFaces.set(pointIndex, pointsFaces.get(pointIndex) + 1);
}
}
return pointsFaces;
}
// Return a list containing a value for each point,
// which is the average of the centres of the edges containing that point.
private static List<Point> averageEdgeCentres(List<Point> points, List<Edge> edges) {
List<PointWithEdgeCount> pointExtras = Stream.generate( () -> new PointWithEdgeCount(Point.ZERO, 0) )
.limit(points.size()).collect(Collectors.toList());
for ( Edge edge : edges ) {
Point centrePoint = edge.centrePoint;
for ( int pointIndex : List.of( edge.pointOne, edge.pointTwo ) ) {
Point point = pointExtras.get(pointIndex).point;
pointExtras.get(pointIndex).point = point.add(centrePoint);
pointExtras.get(pointIndex).edgeCount += 1;
}
}
List<Point> averageEdgeCentres = new ArrayList<Point>();
for ( PointWithEdgeCount pointExtra : pointExtras ) {
averageEdgeCentres.addLast(pointExtra.point.scalarDivide(pointExtra.edgeCount));
};
return averageEdgeCentres;
}
// Return a list containing a value for each point,
// which is the average of the face points for the faces containing that point.
private static List<Point> averageFacePoints(List<Point> points, List<List<Integer>> faces,
List<Point> facePoints) {
List<PointWithEdgeCount> pointExtras = Stream.generate( () -> new PointWithEdgeCount(Point.ZERO, 0) )
.limit(points.size()).collect(Collectors.toList());
for ( List<Integer> face : faces ) {
Point facePoint = facePoints.get(faces.indexOf(face));
for ( int pointIndex : face ) {
Point pointExtra = pointExtras.get(pointIndex).point;
pointExtras.get(pointIndex).point = pointExtra.add(facePoint);
pointExtras.get(pointIndex).edgeCount += 1;
}
}
List<Point> averageFacePoints = new ArrayList<Point>();
for ( PointWithEdgeCount pointExtra : pointExtras ) {
averageFacePoints.addLast(pointExtra.point.scalarDivide(pointExtra.edgeCount));
}
return averageFacePoints;
}
// Return a list of edge points, where an edge point is the average of the centre of an edge
// and the centre of the line segment joining the face points of its two adjacent faces.
private static List<Point> edgePoints(List<Point> points, List<Point> facePoints, List<Edge> edges) {
List<Point> edgePoints = new ArrayList<Point>();
for ( Edge edge : edges ) {
Point edgeCentre = edge.centrePoint;
Point facePoint1 = facePoints.get(edge.faceOne);
Point facePoint2 = ( edge.faceTwo == FACE_NOT_SET ) ? facePoint1 : facePoints.get(edge.faceTwo);
Point centreFacePoint = facePoint1.centrePoint(facePoint2);
edgePoints.addLast(edgeCentre.centrePoint(centreFacePoint));
}
return edgePoints;
}
// Return a list of edges.
private static List<Edge> edges(List<Point> points, List<List<Integer>> faces) {
List<Edge> partialEdges = new ArrayList<Edge>();
for ( List<Integer> face : faces ) {
for ( int pointIndex = 0; pointIndex < face.size(); pointIndex++ ) {
final int pointIndexOne = face.get(pointIndex);
final int pointIndexTwo = face.get((pointIndex + 1) % face.size());
IndexPair pair = order( new IndexPair(pointIndexOne, pointIndexTwo) );
partialEdges.addLast( new Edge(pair.first, pair.second, faces.indexOf(face), 0, Point.ZERO) );
}
}
Collections.sort(partialEdges);
List<Edge> mergedEdges = new ArrayList<Edge>();
int edgeIndex = 0;
while ( edgeIndex < partialEdges.size() ) {
Edge edgeOne = partialEdges.get(edgeIndex);
if ( edgeIndex < partialEdges.size() - 1 ) {
Edge edgeTwo = partialEdges.get(edgeIndex + 1);
if ( edgeOne.pointOne == edgeTwo.pointOne && edgeOne.pointTwo == edgeTwo.pointTwo ) {
mergedEdges.addLast( new Edge(
edgeOne.pointOne, edgeOne.pointTwo, edgeOne.faceOne, edgeTwo.faceOne, Point.ZERO) );
edgeIndex += 2;
} else {
mergedEdges.addLast( new Edge(
edgeOne.pointOne, edgeOne.pointTwo, edgeOne.faceOne, FACE_NOT_SET, Point.ZERO) );
edgeIndex += 1;
}
} else {
mergedEdges.add( new Edge(
edgeOne.pointOne, edgeOne.pointTwo, edgeOne.faceOne, FACE_NOT_SET, Point.ZERO) );
edgeIndex += 1;
}
}
List<Edge> edges = new ArrayList<Edge>();
for ( Edge mergedEdge : mergedEdges ) {
Point pointOne = points.get(mergedEdge.pointOne);
Point pointTwo = points.get(mergedEdge.pointTwo);
Point centrePoint = pointOne.centrePoint(pointTwo);
edges.addLast( new Edge(
mergedEdge.pointOne, mergedEdge.pointTwo, mergedEdge.faceOne, mergedEdge.faceTwo, centrePoint) );
}
return edges;
}
// Return a list of face points, where a face point is the average of all the points of a face.
private static List<Point> facePoints(List<Point> points, List<List<Integer>> faces) {
List<Point> facePoints = new ArrayList<Point>();
for ( List<Integer> face : faces ) {
Point facePoint = Point.ZERO;
for ( int pointIndex : face ) {
Point point = points.get(pointIndex);
facePoint = facePoint.add(point);
}
facePoints.addLast(facePoint.scalarDivide(face.size()));
}
return facePoints;
}
// Return an IndexPair with its values sorted into ascending order.
private static IndexPair order(IndexPair pair) {
if ( pair.first < pair.second ) {
return pair;
}
return new IndexPair(pair.second, pair.first);
}
// Return a hashed value of the two numbers in the given IndexPair.
private static long szudzikHash(IndexPair pair) {
return ( pair.first >= pair.second ) ?
( pair.first * pair.first ) + pair.first + pair.second : ( pair.second * pair.second ) + pair.first;
}
// A three dimensional point.
private static class Point {
public Point(double aX, double aY, double aZ) {
x = aX; y = aY; z = aZ;
}
public Point add(Point other) {
return new Point(x + other.x, y + other.y, z + other.z);
}
public Point scalarMultiply(double factor) {
return new Point(x * factor, y * factor, z * factor);
}
public Point scalarDivide(double factor) {
return scalarMultiply(1.0 / factor);
}
public Point centrePoint(Point other) {
return add(other).scalarDivide(2.0);
}
public String toString() {
return "(" + format(x) + ", " + format(y) + ", " + format(z) + ")";
}
public static Point ZERO = new Point(0.0, 0.0, 0.0);
private String format(double value) {
return ( value >= 0 ) ? String.format(" %.5f", value) : String.format("%.5f", value);
}
private double x, y, z;
}
// An edge consists of two end points, together with it's one or two adjacent faces
// and the centre point of that edge.
private static class Edge implements Comparable<Edge> {
public Edge(int aPointOne, int aPointTwo, int aFaceOne, int aFaceTwo, Point aCentrePoint) {
pointOne = aPointOne; pointTwo = aPointTwo; faceOne = aFaceOne; faceTwo = aFaceTwo;
centrePoint = aCentrePoint;
}
@Override
public int compareTo(Edge other) {
if ( pointOne == other.pointOne ) {
if ( pointTwo == other.pointTwo ) {
return Integer.compare(faceOne, other.faceOne);
}
return Integer.compare(pointTwo, other.pointTwo);
}
return Integer.compare(pointOne, other.pointOne);
}
private int pointOne, pointTwo, faceOne, faceTwo;
private Point centrePoint;
}
// A point together with the number of edges containing that point.
private static class PointWithEdgeCount {
public PointWithEdgeCount(Point aPoint, int aEdgeCount) {
point = aPoint; edgeCount = aEdgeCount;
}
private Point point;
private int edgeCount;
}
private static record IndexPair(int first, int second) {}
private static record ListPair(List<Point> points, List<List<Integer>> faces) {}
private static final int FACE_NOT_SET = -1;
}
</syntaxhighlight>
{{ out }}
<pre>
(-0.55556, 0.55556, 0.55556)
(-0.55556, -0.55556, 0.55556)
( 0.55556, -0.55556, 0.55556)
( 0.55556, 0.55556, 0.55556)
( 0.55556, -0.55556, -0.55556)
( 0.55556, 0.55556, -0.55556)
(-0.55556, -0.55556, -0.55556)
(-0.55556, 0.55556, -0.55556)
( 0.00000, 0.00000, 1.00000)
( 1.00000, 0.00000, 0.00000)
( 0.00000, 0.00000, -1.00000)
( 0.00000, 1.00000, 0.00000)
(-1.00000, 0.00000, 0.00000)
( 0.00000, -1.00000, 0.00000)
(-0.75000, 0.00000, 0.75000)
( 0.00000, 0.75000, 0.75000)
(-0.75000, 0.75000, 0.00000)
( 0.00000, -0.75000, 0.75000)
(-0.75000, -0.75000, 0.00000)
( 0.75000, 0.00000, 0.75000)
( 0.75000, -0.75000, 0.00000)
( 0.75000, 0.75000, 0.00000)
( 0.75000, 0.00000, -0.75000)
( 0.00000, -0.75000, -0.75000)
( 0.00000, 0.75000, -0.75000)
(-0.75000, 0.00000, -0.75000)
[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|Julia}}==
<syntaxhighlight lang="julia">using Makie, Statistics
| |||