Rosetta Code

Catmull–Clark subdivision surface: Difference between revisions

← Older edit
Content deleted Content added
PSNOW123 (talk | contribs)
927 edits
New post.
PSNOW123 (talk | contribs)
927 edits
New post.
 
(2 intermediate revisions by the same user not shown)
Line 140:
return nm;
}</syntaxhighlight>
 
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <algorithm>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <vector>
 
// A point of the current Catmull-Clark surface.
class Point {
public:
Point() : x(0.0), y(0.0), z(0.0) { }
Point(const double& aX, const double& aY, const double& aZ) : x(aX), y(aY), z(aZ) { }
 
Point add(const Point& other) const {
return Point(x + other.x, y + other.y, z + other.z);
}
 
Point multiply(const double& factor) const {
return Point(x * factor, y * factor, z * factor);
}
 
Point divide(const double& factor) const {
return multiply(1.0 / factor);
}
 
bool operator<(const Point& other) const {
return ( x < other.x ) || ( ( x == other.x && y < other.y ) )
|| ( x == other.x && y == other.y && z < other.z );
}
 
bool operator==(const Point& other) const {
return x == other.x && y == other.y && z == other.z;
}
 
Point& operator=(const Point& other) {
if ( *this != other ) {
x = other.x; y = other.y; z = other.z;
}
return *this;
}
 
std::string to_string() const {
return "(" + format(x) + ", " + format(y) + ", " + format(z) + ")";
}
 
private:
std::string format(const double& value) const {
std::stringstream stream;
stream << std::fixed << std::setprecision(3) << value;
return ( value >= 0 ) ? " " + stream.str() : stream.str();
}
 
double x, y, z;
};
 
// Return the centroid point of the given vector of points.
Point centroid(const std::vector<Point>& points) {
Point sum;
for ( const Point& point : points ) {
sum = sum.add(point);
}
return sum.divide(points.size());
}
 
// An edge of the current Catmull-Clark surface.
class Edge {
public:
Edge(Point aBegin, Point aEnd) {
if ( aEnd < aBegin ) {
std::swap(aBegin, aEnd);
}
begin = aBegin; end = aEnd;
 
mid_edge = centroid({ begin, end });
hole_edge = false;
}
 
bool contains(const Point& point) const {
return point == begin || point == end;
}
 
bool operator<(const Edge other) const {
return ( begin < other.begin ) || ( begin == other.begin && end < other.end );
}
 
bool operator==(const Edge& other) const {
return contains(other.begin) && contains(other.end);
}
 
bool hole_edge;
Point begin, end, mid_edge, edge_point;
};
 
// A face of the current Catmull-Clark surface.
class Face {
public:
Face(std::vector<Point> aVertices) {
vertices = aVertices;
face_point = centroid(vertices);
 
for ( uint64_t i = 0; i < vertices.size() - 1; ++i ) {
edges.emplace_back(Edge(vertices[i], vertices[i + 1]));
}
edges.emplace_back(Edge(vertices.back(), vertices.front()));
}
 
bool contains(const Point& vertex) const {
return std::find(vertices.begin(), vertices.end(), vertex) != vertices.end();
}
 
bool contains(Edge edge) const {
return contains(edge.begin) && contains(edge.end);
}
 
std::string toString() const {
std::string result = "Face: ";
for ( uint64_t i = 0; i < vertices.size() - 1; ++i ) {
result += vertices[i].to_string() + ", ";
}
return result + vertices.back().to_string();
}
 
std::vector<Point> vertices;
std::vector<Edge> edges;
Point face_point;
};
 
// Return a map containing, for each vertex,
// the new vertex created by the current iteration of the Catmull-Clark surface subdivision algorithm.
std::map<Point, Point> next_vertices(const std::vector<Edge>& edges, const std::vector<Face>& faces) {
std::map<Point, Point> next_vertices = { };
std::set<Point> vertices = { };
for ( const Face& face : faces ) {
for ( const Point& vertex : face.vertices ) {
vertices.emplace(vertex);
}
}
 
for ( const Point& vertex : vertices ) {
std::vector<Face> faces_for_vertex = { };
for ( const Face& face : faces ) {
if ( face.contains(vertex) ) {
faces_for_vertex.emplace_back(face);
}
}
 
std::set<Edge> edges_for_vertex = { };
for ( const Edge& edge : edges ) {
if ( edge.contains(vertex) ) {
edges_for_vertex.emplace(edge);
}
}
 
if ( faces_for_vertex.size() != edges_for_vertex.size() ) {
std::vector<Point> mid_edge_of_hole_edges = { };
for ( const Edge& edge : edges_for_vertex ) {
if ( edge.hole_edge ) {
mid_edge_of_hole_edges.emplace_back(edge.mid_edge);
}
}
mid_edge_of_hole_edges.emplace_back(vertex);
next_vertices[vertex] = centroid(mid_edge_of_hole_edges);
} else {
const uint64_t face_count = faces_for_vertex.size();
const double multiple_1 = static_cast<double>(( face_count - 3 ) / face_count);
const double multiple_2 = 1.0 / face_count;
const double multiple_3 = 2.0 / face_count;
 
Point next_vertex_1 = vertex.multiply(multiple_1);
std::vector<Point> face_points = { };
for ( const Face& face : faces_for_vertex ) {
face_points.emplace_back(face.face_point);
}
Point next_vertex_2 = centroid(face_points).multiply(multiple_2);
std::vector<Point> mid_edges = { };
for ( const Edge& edge : edges_for_vertex ) {
mid_edges.emplace_back(edge.mid_edge);
}
Point next_vertex_3 = centroid(mid_edges).multiply(multiple_3);
Point next_vertex_4 = next_vertex_1.add(next_vertex_2);
 
next_vertices[vertex] = next_vertex_4.add(next_vertex_3);
}
}
return next_vertices;
}
 
// The Catmull-Clarke surface subdivision algorithm.
std::vector<Face> catmull_clark_surface_subdivision(std::vector<Face>& faces) {
// Determine, for each edge, whether or not it is an edge of a hole, and set its edge point accordingly.
for ( Face& face : faces ) {
for ( Edge& edge : face.edges ) {
std::vector<Point> face_points_for_edge = { };
for ( const Face& search_face : faces ) {
if ( search_face.contains(edge) ) {
face_points_for_edge.emplace_back(search_face.face_point);
}
}
 
if ( face_points_for_edge.size() == 2 ) {
edge.hole_edge = false;
edge.edge_point = centroid({ edge.mid_edge, centroid(face_points_for_edge) });
} else {
edge.hole_edge = true;
edge.edge_point = edge.mid_edge;
}
}
}
 
std::vector<Edge> edges = { };
for ( const Face& face : faces ) {
for ( const Edge& edge : face.edges ) {
edges.emplace_back(edge);
}
}
std::map<Point, Point> next_vertex_map = next_vertices(edges, faces);
 
std::vector<Face> next_faces = { };
for ( Face face : faces ) { // The face may contain any number of points
if ( face.vertices.size() >= 3 ) { // A face with 2 or fewer points does not contribute to the surface
Point face_point = face.face_point;
for ( uint64_t i = 0; i < face.vertices.size(); ++i ) {
next_faces.emplace_back(Face({
next_vertex_map[face.vertices[i]],
face.edges[i].edge_point,
face_point,
face.edges[( i - 1 + face.vertices.size() ) % face.vertices.size()].edge_point}));
}
}
}
return next_faces;
}
 
// Display the current Catmull-Clark surface on the console.
void displaySurface(const std::vector<Face> faces) {
std::cout << "Surface {" << std::endl;
for ( const Face& face : faces ) {
std::cout << face.toString() << std::endl;
}
std::cout << "}" << std::endl << std::endl;
}
 
int main() {
std::vector<Face> faces = {
Face({ Point(-1.0, 1.0, 1.0), Point(-1.0, -1.0, 1.0), Point( 1.0, -1.0, 1.0), Point( 1.0, 1.0, 1.0) }),
Face({ Point( 1.0, 1.0, 1.0), Point( 1.0, -1.0, 1.0), Point( 1.0, -1.0, -1.0), Point( 1.0, 1.0, -1.0) }),
Face({ Point( 1.0, 1.0, -1.0), Point( 1.0, -1.0, -1.0), Point(-1.0, -1.0, -1.0), Point(-1.0, 1.0, -1.0) }),
Face({ Point(-1.0, 1.0, -1.0), Point(-1.0, 1.0, 1.0), Point( 1.0, 1.0, 1.0), Point( 1.0, 1.0, -1.0) }),
Face({ Point(-1.0, 1.0, -1.0), Point(-1.0, -1.0, -1.0), Point(-1.0, -1.0, 1.0), Point(-1.0, 1.0, 1.0) }),
Face({ Point(-1.0, -1.0, -1.0), Point(-1.0, -1.0, 1.0), Point( 1.0, -1.0, 1.0), Point( 1.0, -1.0, -1.0) })};
 
displaySurface(faces);
const uint32_t iterations = 1;
for ( uint32_t i = 0; i < iterations; ++i ) {
faces = catmull_clark_surface_subdivision(faces);
}
displaySurface(faces);
}
</syntaxhighlight>
{{ out }}
<pre>
Surface {
Face: (-1.000, 1.000, 1.000), (-1.000, -1.000, 1.000), ( 1.000, -1.000, 1.000), ( 1.000, 1.000, 1.000)
Face: ( 1.000, 1.000, 1.000), ( 1.000, -1.000, 1.000), ( 1.000, -1.000, -1.000), ( 1.000, 1.000, -1.000)
Face: ( 1.000, 1.000, -1.000), ( 1.000, -1.000, -1.000), (-1.000, -1.000, -1.000), (-1.000, 1.000, -1.000)
Face: (-1.000, 1.000, -1.000), (-1.000, 1.000, 1.000), ( 1.000, 1.000, 1.000), ( 1.000, 1.000, -1.000)
Face: (-1.000, 1.000, -1.000), (-1.000, -1.000, -1.000), (-1.000, -1.000, 1.000), (-1.000, 1.000, 1.000)
Face: (-1.000, -1.000, -1.000), (-1.000, -1.000, 1.000), ( 1.000, -1.000, 1.000), ( 1.000, -1.000, -1.000)
}
 
Surface {
Face: (-0.556, 0.556, 0.556), (-0.750, 0.000, 0.750), ( 0.000, 0.000, 1.000), ( 0.000, 0.750, 0.750)
Face: (-0.556, -0.556, 0.556), ( 0.000, -0.750, 0.750), ( 0.000, 0.000, 1.000), (-0.750, 0.000, 0.750)
Face: ( 0.556, -0.556, 0.556), ( 0.750, 0.000, 0.750), ( 0.000, 0.000, 1.000), ( 0.000, -0.750, 0.750)
Face: ( 0.556, 0.556, 0.556), ( 0.000, 0.750, 0.750), ( 0.000, 0.000, 1.000), ( 0.750, 0.000, 0.750)
Face: ( 0.556, 0.556, 0.556), ( 0.750, 0.000, 0.750), ( 1.000, 0.000, 0.000), ( 0.750, 0.750, 0.000)
Face: ( 0.556, -0.556, 0.556), ( 0.750, -0.750, 0.000), ( 1.000, 0.000, 0.000), ( 0.750, 0.000, 0.750)
Face: ( 0.556, -0.556, -0.556), ( 0.750, 0.000, -0.750), ( 1.000, 0.000, 0.000), ( 0.750, -0.750, 0.000)
Face: ( 0.556, 0.556, -0.556), ( 0.750, 0.750, 0.000), ( 1.000, 0.000, 0.000), ( 0.750, 0.000, -0.750)
Face: ( 0.556, 0.556, -0.556), ( 0.750, 0.000, -0.750), ( 0.000, 0.000, -1.000), ( 0.000, 0.750, -0.750)
Face: ( 0.556, -0.556, -0.556), ( 0.000, -0.750, -0.750), ( 0.000, 0.000, -1.000), ( 0.750, 0.000, -0.750)
Face: (-0.556, -0.556, -0.556), (-0.750, 0.000, -0.750), ( 0.000, 0.000, -1.000), ( 0.000, -0.750, -0.750)
Face: (-0.556, 0.556, -0.556), ( 0.000, 0.750, -0.750), ( 0.000, 0.000, -1.000), (-0.750, 0.000, -0.750)
Face: (-0.556, 0.556, -0.556), (-0.750, 0.750, 0.000), ( 0.000, 1.000, 0.000), ( 0.000, 0.750, -0.750)
Face: (-0.556, 0.556, 0.556), ( 0.000, 0.750, 0.750), ( 0.000, 1.000, 0.000), (-0.750, 0.750, 0.000)
Face: ( 0.556, 0.556, 0.556), ( 0.750, 0.750, 0.000), ( 0.000, 1.000, 0.000), ( 0.000, 0.750, 0.750)
Face: ( 0.556, 0.556, -0.556), ( 0.000, 0.750, -0.750), ( 0.000, 1.000, 0.000), ( 0.750, 0.750, 0.000)
Face: (-0.556, 0.556, -0.556), (-0.750, 0.000, -0.750), (-1.000, 0.000, 0.000), (-0.750, 0.750, 0.000)
Face: (-0.556, -0.556, -0.556), (-0.750, -0.750, 0.000), (-1.000, 0.000, 0.000), (-0.750, 0.000, -0.750)
Face: (-0.556, -0.556, 0.556), (-0.750, 0.000, 0.750), (-1.000, 0.000, 0.000), (-0.750, -0.750, 0.000)
Face: (-0.556, 0.556, 0.556), (-0.750, 0.750, 0.000), (-1.000, 0.000, 0.000), (-0.750, 0.000, 0.750)
Face: (-0.556, -0.556, -0.556), (-0.750, -0.750, 0.000), ( 0.000, -1.000, 0.000), ( 0.000, -0.750, -0.750)
Face: (-0.556, -0.556, 0.556), ( 0.000, -0.750, 0.750), ( 0.000, -1.000, 0.000), (-0.750, -0.750, 0.000)
Face: ( 0.556, -0.556, 0.556), ( 0.750, -0.750, 0.000), ( 0.000, -1.000, 0.000), ( 0.000, -0.750, 0.750)
Face: ( 0.556, -0.556, -0.556), ( 0.000, -0.750, -0.750), ( 0.000, -1.000, 0.000), ( 0.750, -0.750, 0.000)
}
</pre>
 
=={{header|Go}}==
{{trans|Python}}
Line 917 ⟶ 1,221:
<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.Objects;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.Stream;
 
public final class SurfaceSubdivisionCatmullClarkSurfaceSubdivision {
 
public static void main(String[] args) {
List<PointFace> pointsfaces = List.of( new Face(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 Face(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 Face(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 Face(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 Face(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 Face(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) )) );
displaySurface(faces);
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 faces = catmullClarkSurfaceSubdivision(result.points, result.faces);
}
displaySurface(faces);
}
for ( Point point : result.points ) {
System.out.println(point);
// The Catmull-Clarke surface subdivision algorithm.
}
private static List<Face> catmullClarkSurfaceSubdivision(List<Face> faces) {
System.out.println();
// Determine, for each edge, whether or not it is an edge of a hole, and set its edge point accordingly.
List<Edge> edges = faces.stream().map( face -> face.edges.stream() ).flatMap(Function.identity()).toList();
for ( List<Integer> face : result.faces ) {
for ( Edge edge : edges ) {
System.out.println(face);
List<Point> facePointsForEdge =
faces.stream().filter( face -> face.contains(edge) ).map( face -> face.facePoint ).toList();
if ( facePointsForEdge.size() == 2 ) {
edge.holeEdge = false;
edge.edgePoint = centroid(List.of( edge.midEdge, centroid(facePointsForEdge) ));
} else {
edge.holeEdge = true;
edge.edgePoint = edge.midEdge;
}
}
}
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);
Map<Point, Point> nextVertices = nextVertices(edges, faces);
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;
}
}
}
List<Face> nextFaces = new ArrayList<Face>();
return new ListPair(newPoints, newFaces);
for ( Face face : faces ) { // The face may contain any number of points
if ( face.vertices.size() >= 3 ) { // A face with 2 or fewer points does not contribute to the surface
Point facePoint = face.facePoint;
for ( int i = 0; i < face.vertices.size(); i++ ) {
nextFaces.addLast( new Face(List.of(
nextVertices.get(face.vertices.get(i)),
face.edges.get(i).edgePoint,
facePoint,
face.edges.get(Math.floorMod(i - 1, face.vertices.size())).edgePoint )) );
}
}
}
return nextFaces;
}
// Return a map containing, for each vertex,
// Return the new points created by the current iteration of the Catmull-Clark surface subdivision algorithm.
// the new vertex created by the current iteration of the Catmull-Clark surface subdivision algorithm.
private static List<Point> newPoints(List<Point> points, List<Integer> facesCount,
private Liststatic Map<Point, Point> averageFacePointsnextVertices(List<Edge> edges, List<PointFace> averageEdgeCentresfaces) {
List Map<Point, Point> newPointsnextVertices = new ArrayListHashMap<Point, Point>();
List<Point> vertices =
for ( int pointIndex = 0; pointIndex < points.size(); pointIndex++ ) {
faces.stream().map( face -> face.vertices.stream() ).flatMap(Function.identity()).distinct().toList();
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;
}
}
for ( Point vertex : vertices ) {
List<Point> averageFacePoints = new ArrayList<Point>();
List<Face> facesForVertex = faces.stream().filter( face -> face.contains(vertex) ).toList();
for ( PointWithEdgeCount pointExtra : pointExtras ) {
List<Edge> edgesForVertex = edges.stream().filter( edge -> edge.contains(vertex) ).distinct().toList();
averageFacePoints.addLast(pointExtra.point.scalarDivide(pointExtra.edgeCount));
}
if ( facesForVertex.size() != edgesForVertex.size() ) {
 
List<Point> midEdgeOfHoleEdges = edgesForVertex.stream().filter( edge -> edge.holeEdge )
return averageFacePoints;
.map( edge -> edge.midEdge ).collect(Collectors.toList());
}
midEdgeOfHoleEdges.add(vertex);
nextVertices.put(vertex, centroid(midEdgeOfHoleEdges));
// Return a list of edge points, where an edge point is the average of the centre of an edge
} else {
// and the centre of the line segment joining the face points of its two adjacent faces.
final int faceCount = facesForVertex.size();
private static List<Point> edgePoints(List<Point> points, List<Point> facePoints, List<Edge> edges) {
final double multipleOne = (double) ( faceCount - 3 ) / faceCount;
List<Point> edgePoints = new ArrayList<Point>();
final double multipleTwo = 1.0 / faceCount;
for ( Edge edge : edges ) {
Pointfinal edgeCentredouble multipleThree = edge2.centrePoint0 / faceCount;
Point facePoint1 = facePoints.get(edge.faceOne);
Point nextVertexOne = vertex.multiply(multipleOne);
Point facePoint2 = ( edge.faceTwo == FACE_NOT_SET ) ? facePoint1 : facePoints.get(edge.faceTwo);
List<Point> facePoints = facesForVertex.stream().map( face -> face.facePoint ).toList();
Point centreFacePoint = facePoint1.centrePoint(facePoint2);
Point nextVertexTwo = centroid(facePoints).multiply(multipleTwo);
edgePoints.addLast(edgeCentre.centrePoint(centreFacePoint));
List<Point> midEdges = edgesForVertex.stream().map( edge -> edge.midEdge ).toList();
}
Point nextVertexThree = centroid(midEdges).multiply(multipleThree);
 
Point nextVertexFour = nextVertexOne.add(nextVertexTwo);
return edgePoints;
}
nextVertices.put(vertex, nextVertexFour.add(nextVertexThree));
}
// Return a list of edges.
}
private static List<Edge> edges(List<Point> points, List<List<Integer>> faces) {
return nextVertices;
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 anthe IndexPaircentroid withpoint itsof valuesthe sortedgiven intolist ascendingof orderpoints.
private static IndexPairPoint ordercentroid(IndexPairList<Point> pairpoints) {
return points.stream().reduce(Point.ZERO, (left, right) -> left.add(right) ).divide(points.size());
if ( pair.first < pair.second ) {
return pair;
}
return new IndexPair(pair.second, pair.first);
}
// Display the current Catmull-Clark surface on the console.
// Return a hashed value of the two numbers in the given IndexPair.
private static longvoid szudzikHashdisplaySurface(IndexPairList<Face> pairfaces) {
System.out.println("Surface {");
return ( pair.first >= pair.second ) ?
faces.stream().forEach(System.out::println);
( pair.first * pair.first ) + pair.first + pair.second : ( pair.second * pair.second ) + pair.first;
System.out.println("}" + System.lineSeparator());
}
// A point of the current Catmull-Clark surface.
// A three dimensional point.
private static final class Point implements Comparable<Point> {
public Point(double aX, double aY, double aZ) {
x = aX; y = aY; z = aZ;
}
@Override
public int compareTo(Point other) {
if ( x == other.x ) {
if ( y == other.y ) {
return Double.compare(z, other.z);
}
return Double.compare(y, other.y);
}
return Double.compare(x, other.x);
}
@Override
public boolean equals(Object other) {
return switch ( other ) {
case Point point -> x == point.x && y == point.y && z == point.z;
default -> false;
};
}
@Override
public int hashCode() {
return Objects.hash(x, y, z);
}
Line 1,190 ⟶ 1,385:
}
public Point scalarMultiplymultiply(double factor) {
return new Point(x * factor, y * factor, z * factor);
}
public Point scalarDividedivide(double factor) {
return scalarMultiplymultiply(1.0 / factor);
}
public Point centrePoint(Point other) {
return add(other).scalarDivide(2.0);
}
Line 1,209 ⟶ 1,400:
private String format(double value) {
return ( value >= 0 ) ? String.format(" %.5f3f", value) : String.format("%.5f3f", value);
}
private final double x, y, z;
}
// An edge of the current Catmull-Clark surface.
// An edge consists of two end points, together with it's one or two adjacent faces
private static final class Edge {
// and the centre point of that edge.
private static class Edge implements Comparable<Edge> {
public Edge(int aPointOne, int aPointTwo, int aFaceOne, intPoint aFaceTwoaBegin, Point aCentrePointaEnd) {
if ( aBegin.compareTo(aEnd) <= 0 ) {
pointOne = aPointOne; pointTwo = aPointTwo; faceOne = aFaceOne; faceTwo = aFaceTwo;
begin = aBegin; end = aEnd;
centrePoint = aCentrePoint;
} else {
begin = aEnd; end = aBegin;
}
midEdge = centroid(List.of( begin, end ));
}
 
@Override
public boolean equals(Object other) {
return switch ( other ) {
case Edge edge -> begin.equals(edge.begin) && end.equals(edge.end);
default -> false;
};
}
@Override
public int compareTohashCode(Edge other) {
return Objects.hash(begin, end);
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;
public boolean contains(Point point) {
}
return point.equals(begin) || point.equals(end);
}
public boolean holeEdge;
public Point edgePoint;
public final Point begin, end, midEdge;
}
// A face of the current Catmull-Clark surface.
// A point together with the number of edges containing that point.
private static final class PointWithEdgeCountFace {
public PointWithEdgeCountFace(List<Point> aPoint, int aEdgeCountaVertices) {
vertices = new ArrayList<Point>(aVertices);
point = aPoint; edgeCount = aEdgeCount;
facePoint = centroid(vertices);
edges = new ArrayList<Edge>();
for ( int i = 0; i < vertices.size() - 1; i++ ) {
edges.addLast( new Edge(vertices.get(i), vertices.get(i + 1)) );
}
edges.addLast( new Edge(vertices.getLast(), vertices.getFirst()) );;
}
public boolean contains(Point vertex) {
return vertices.contains(vertex);
}
public boolean contains(Edge edge) {
private Point point;
return contains(edge.begin) && contains(edge.end);
private int edgeCount;
}
public String toString() {
}
return "Face: " + vertices.stream().map( point -> point.toString() ).collect(Collectors.joining("; "));
}
private static record IndexPair(int first, int second) {}
private static record ListPair(List<Point> points, List<List<Integer>> faces) {}
public final List<Point> vertices;
public final Point facePoint;
private static final int FACE_NOT_SET = -1;
public final List<Edge> edges;
}
 
}
Line 1,264 ⟶ 1,480:
{{ out }}
<pre>
Surface {
(-0.55556, 0.55556, 0.55556)
Face: (-1.000, 1.000, 1.000); (-1.000, -1.000, 1.000); ( 1.000, -1.000, 1.000); ( 1.000, 1.000, 1.000)
(-0.55556, -0.55556, 0.55556)
Face: ( 1.000, 1.000, 1.000); ( 1.000, -1.000, 1.000); ( 1.000, -1.000, -1.000); ( 1.000, 1.000, -1.000)
( 0.55556, -0.55556, 0.55556)
Face: ( 1.000, 1.000, -1.000); ( 1.000, -1.000, -1.000); (-1.000, -1.000, -1.000); (-1.000, 1.000, -1.000)
( 0.55556, 0.55556, 0.55556)
Face: (-1.000, 1.000, -1.000); (-1.000, 1.000, 1.000); ( 1.000, 1.000, 1.000); ( 1.000, 1.000, -1.000)
( 0.55556, -0.55556, -0.55556)
Face: (-1.000, 1.000, -1.000); (-1.000, -1.000, -1.000); (-1.000, -1.000, 1.000); (-1.000, 1.000, 1.000)
( 0.55556, 0.55556, -0.55556)
Face: (-1.000, -1.000, -1.000); (-1.000, -1.000, 1.000); ( 1.000, -1.000, 1.000); ( 1.000, -1.000, -1.000)
(-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)
 
Surface {
[0, 14, 8, 15]
Face: (-0.556, 0.556, 0.556); (-0.750, 0.000, 0.750); ( 0.000, 0.000, 1.000); ( 0.000, 0.750, 0.750)
[1, 17, 8, 14]
Face: (-0.556, -0.556, 0.556); ( 0.000, -0.750, 0.750); ( 0.000, 0.000, 1.000); (-0.750, 0.000, 0.750)
[2, 19, 8, 17]
Face: ( 0.556, -0.556, 0.556); ( 0.750, 0.000, 0.750); ( 0.000, 0.000, 1.000); ( 0.000, -0.750, 0.750)
[3, 15, 8, 19]
Face: ( 0.556, 0.556, 0.556); ( 0.000, 0.750, 0.750); ( 0.000, 0.000, 1.000); ( 0.750, 0.000, 0.750)
[3, 19, 9, 21]
Face: ( 0.556, 0.556, 0.556); ( 0.750, 0.000, 0.750); ( 1.000, 0.000, 0.000); ( 0.750, 0.750, 0.000)
[2, 20, 9, 19]
Face: ( 0.556, -0.556, 0.556); ( 0.750, -0.750, 0.000); ( 1.000, 0.000, 0.000); ( 0.750, 0.000, 0.750)
[4, 22, 9, 20]
Face: ( 0.556, -0.556, -0.556); ( 0.750, 0.000, -0.750); ( 1.000, 0.000, 0.000); ( 0.750, -0.750, 0.000)
[5, 21, 9, 22]
Face: ( 0.556, 0.556, -0.556); ( 0.750, 0.750, 0.000); ( 1.000, 0.000, 0.000); ( 0.750, 0.000, -0.750)
[5, 22, 10, 24]
Face: ( 0.556, 0.556, -0.556); ( 0.750, 0.000, -0.750); ( 0.000, 0.000, -1.000); ( 0.000, 0.750, -0.750)
[4, 23, 10, 22]
Face: ( 0.556, -0.556, -0.556); ( 0.000, -0.750, -0.750); ( 0.000, 0.000, -1.000); ( 0.750, 0.000, -0.750)
[6, 25, 10, 23]
Face: (-0.556, -0.556, -0.556); (-0.750, 0.000, -0.750); ( 0.000, 0.000, -1.000); ( 0.000, -0.750, -0.750)
[7, 24, 10, 25]
Face: (-0.556, 0.556, -0.556); ( 0.000, 0.750, -0.750); ( 0.000, 0.000, -1.000); (-0.750, 0.000, -0.750)
[7, 16, 11, 24]
Face: (-0.556, 0.556, -0.556); (-0.750, 0.750, 0.000); ( 0.000, 1.000, 0.000); ( 0.000, 0.750, -0.750)
[0, 15, 11, 16]
Face: (-0.556, 0.556, 0.556); ( 0.000, 0.750, 0.750); ( 0.000, 1.000, 0.000); (-0.750, 0.750, 0.000)
[3, 21, 11, 15]
Face: ( 0.556, 0.556, 0.556); ( 0.750, 0.750, 0.000); ( 0.000, 1.000, 0.000); ( 0.000, 0.750, 0.750)
[5, 24, 11, 21]
Face: ( 0.556, 0.556, -0.556); ( 0.000, 0.750, -0.750); ( 0.000, 1.000, 0.000); ( 0.750, 0.750, 0.000)
[7, 25, 12, 16]
Face: (-0.556, 0.556, -0.556); (-0.750, 0.000, -0.750); (-1.000, 0.000, 0.000); (-0.750, 0.750, 0.000)
[6, 18, 12, 25]
Face: (-0.556, -0.556, -0.556); (-0.750, -0.750, 0.000); (-1.000, 0.000, 0.000); (-0.750, 0.000, -0.750)
[1, 14, 12, 18]
Face: (-0.556, -0.556, 0.556); (-0.750, 0.000, 0.750); (-1.000, 0.000, 0.000); (-0.750, -0.750, 0.000)
[0, 16, 12, 14]
Face: (-0.556, 0.556, 0.556); (-0.750, 0.750, 0.000); (-1.000, 0.000, 0.000); (-0.750, 0.000, 0.750)
[6, 18, 13, 23]
Face: (-0.556, -0.556, -0.556); (-0.750, -0.750, 0.000); ( 0.000, -1.000, 0.000); ( 0.000, -0.750, -0.750)
[1, 17, 13, 18]
Face: (-0.556, -0.556, 0.556); ( 0.000, -0.750, 0.750); ( 0.000, -1.000, 0.000); (-0.750, -0.750, 0.000)
[2, 20, 13, 17]
Face: ( 0.556, -0.556, 0.556); ( 0.750, -0.750, 0.000); ( 0.000, -1.000, 0.000); ( 0.000, -0.750, 0.750)
[4, 23, 13, 20]
Face: ( 0.556, -0.556, -0.556); ( 0.000, -0.750, -0.750); ( 0.000, -1.000, 0.000); ( 0.750, -0.750, 0.000)
}
</pre>
 
Retrieved from "https://rosettacode.org/wiki/Catmull–Clark_subdivision_surface"