Jump to content

Catmull–Clark subdivision surface: Difference between revisions

Catmull–Clark subdivision surface (view source)

Revision as of 15:14, 18 January 2010

826 bytes added ,  14 years ago
Expand the description of the task a bit
m (→‎{{header|Tcl}}: link to output)
(Expand the description of the task a bit)
Line 1:
{{task|3D}}
 
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.
 
The process works as follow:
 
The process for computing the new locations of the points works as follows when the surface is free of holes:
# for each face, a ''face point'' is created which is the average of all the points of the face.
# 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.
# for each vertex point, its coordinates are updated from (<tt>new_coords</tt>):
## the old coordinates (<tt>old_coords</tt>),
## the average of the face points of the faces the point belongs to (<tt>avg_face_points</tt>),
## the average of the centers of edges the point belongs to (<tt>avg_mid_edges</tt>),
## how many faces a point belongs to (<tt>n</tt>), then use this formula:
m<sub>1</sub> = (n - 3) / n
 
m1m<sub>2</sub> = (n - 3)1 / n
m2m<sub>3</sub> = 12 / n
m3new_coords = 2 (m<sub>1</sub> * nold_coords)
new_coords = + (m1m<sub>2</sub> * old_vertexavg_face_points)
+ (m2m<sub>3</sub> * avg_face_pointsavg_mid_edges)
+ (m3 * avg_mid_edges)
 
Then each face is replaced by new faces made with the new points,
* for a triangle face (a,b,c):
(a, edge_point_abedge_point<sub>ab</sub>, face_point<sub>abc</sub>, edge_point_caedge_point<sub>ca</sub>)
(b, edge_point_bcedge_point<sub>bc</sub>, face_point<sub>abc</sub>, edge_point_abedge_point<sub>ab</sub>)
(c, edge_point_caedge_point<sub>ca</sub>, face_point<sub>abc</sub>, edge_point_bcedge_point<sub>bc</sub>)
* for a quad face (a,b,c,d):
(a, edge_point_abedge_point<sub>ab</sub>, face_point<sub>abcd</sub>, edge_point_daedge_point<sub>da</sub>)
(b, edge_point_bcedge_point<sub>bc</sub>, face_point<sub>abcd</sub>, edge_point_abedge_point<sub>ab</sub>)
(c, edge_point_cdedge_point<sub>cd</sub>, face_point<sub>abcd</sub>, edge_point_bcedge_point<sub>bc</sub>)
(d, edge_point_daedge_point<sub>da</sub>, face_point<sub>abcd</sub>, edge_point_cdedge_point<sub>cd</sub>)
 
This process is relevant when there are no holes in the surface.
 
When there is a hole, we can detect it as followfollows:
* an edge is the border of a hole if it belongs to only one face,
* a point is on the border of a hole if n1<tt>n<sub>faces</sub> != n2n<sub>edges</sub></tt> with n1<tt>n<sub>faces</sub></tt> the number of faces the point belongs to, and n2<tt>n<sub>edges</sub></tt> the number of edges a point belongs to.
 
On the border of a hole the subdivision occurs as followfollows:
# for the edges that are on the border of a hole, the edge point is just the middle of the edge.
# for the vertex points that are on the border of a hole, the new coordinates are calculated as followfollows:
## in all the edges the point belongs to, only take in account the middles of the edges that are on the border of the hole then calculate the average between these points and the old coordinates.
## calculate the average between these points (on the hole boundary) and the old coordinates (also on the hole boundary).
 
For edges and vertices not next to a hole, the standard algorithm from above is used.
 
=={{header|Mathematica}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/136005"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information