Catmull–Clark subdivision surface: Difference between revisions

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.

 

 

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;

}

return nm;

=={{header|Go}}==

{{trans|Python}}

 

See the original version for full comments.

 

import (

fmt.Printf("%2d\n", f)

}

 

{{out}}

[ 4 23 13 20]

</pre>

=={{header|Haskell}}==

{-# LANGUAGE ScopedTypeVariables #-}

 

 

main :: IO ()

{{out}}

<pre>Vertices:

(22,[24,15,5,8])

(23,[22,8,5,7])</pre>

=={{header|J}}==

 

 

havePoints=: e."1/~ i.@#

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

│ │ 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.

 

println("Press Enter to continue", readline())

=={{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]]]

 

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.

 

 

 

edges = DeleteDuplicates[Flatten[Partition[#,2,1,-1]&/@faces,1],Sort[#1]==Sort[#2]&];

avgFacePoints=Mean[Points[[#]]] &/@ faces;

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]])]

[[File:CAM noholes 1.png]]

 

For a surface with holes the resulting iterative subdivision will be:

Function[iteration, Graphics3D[

(Polygon[iteration[[1]][[#]]] & /@ iteration[[2]])

[[File:CAM holes 1.png]]

 

This code was written in Mathematica 8.

=={{header|Nim}}==

{{trans|Go}}

{{trans|Python}}

import tables

 

s.add(fmt"{n:2d}")

s.add(']')

 

{{out}}

[ 2, 20, 13, 17]

[ 4, 23, 13, 20]</pre>

=={{header|OCaml}}==

{{incorrect|OCaml|wrong output data}}

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) =

(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 }

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;

with output:

<pre>surface {

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}}

<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: #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>

{{out}}

<pre>

{ 4,23,13,20}}

</pre>

=={{header|Python}}==

"""

 

graph_output(output_points, output_faces)

=={{header|Rust}}==

{{trans|Python}}

pub struct Vector3 {pub x: f64, pub y: f64, pub z: f64, pub w: f64}

 

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);

}

}

=={{header|Tcl}}==

This code handles both holes and arbitrary polygons in the input data.

 

# Use math functions and operators as commands (Lisp-like).

 

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-math}}

{{libheader|Wren-fmt}}

 

var Point = Tuple.create("Point", ["x", "y", "z"])

for (f in outputFaces) {

Fmt.aprint(f, 2, 0, "[]")

 

{{out}}

[ 4 23 13 20]

</pre>