Subdivision Surfaces

ΟρισμόςDefinition

Μια επιφάνεια υποδιαίρεσης δεν ορίζεται από εξίσωση. Ορίζεται από ένα αδρό πλέγμα και έναν κανόνα: κάθε πέρασμα του κανόνα σπάει τις έδρες σε μικρότερες και μετακινεί όλες τις κορυφές σε σταθμισμένους μέσους όρους των γειτόνων τους. Επανάλαβέ το και η ακολουθία των πλεγμάτων συγκλίνει. Η επιφάνεια είναι το όριο της — όχι κάποιο από τα βήματά της. A subdivision surface is not defined by an equation. It is defined by a coarse mesh and a rule: each pass of the rule splits the faces into smaller ones and moves every vertex to a weighted average of its neighbours. Repeat, and the sequence of meshes converges. The surface is its limit — not any one of its steps.

Αυτή η μία μετατόπιση — από την εξίσωση στον κανόνα — είναι όλη η διαφορά. Μια παραμετρική επιφάνεια χρειάζεται κανονικό πλέγμα παραμέτρων: γραμμές και στήλες, τέσσερις γείτονες παντού. Ένας κανόνας δεν χρειάζεται τίποτα τέτοιο, γιατί δεν κοιτάζει συντεταγμένες παραμέτρου· κοιτάζει γείτονες. Γι’ αυτό δέχεται πλέγμα οποιασδήποτε τοπολογίας και βγάζει μία και μόνη λεία επιφάνεια, χωρίς ραφές να ταιριάξουν και χωρίς μπαλώματα να συνδεθούν. That single shift — from equation to rule — is the whole difference. A parametric surface needs a regular parameter grid: rows and columns, four neighbours everywhere. A rule needs none of that, because it never looks at parameter coordinates; it looks at neighbours. Which is why it accepts a mesh of arbitrary topology and returns one single smooth surface, with no seams to match and no patches to stitch.

Catmull–ClarkCatmull–Clark

1978

Έδρες ανά επίπεδοFaces per level

×4

Κανονικός βαθμός σε τετράπλευραRegular valence on quads

4

ΣυνέχειαContinuity

C² / C¹

Η τελευταία στήλη κρύβει τον μοναδικό συμβιβασμό ολόκληρης της μεθόδου. Παντού όπου το πλέγμα είναι κανονικό, η οριακή επιφάνεια είναι κυβικό B-spline — C², bit για bit το ίδιο πράγμα. Στις μη κανονικές κορυφές, εκεί δηλαδή που κανένα B-spline δεν μπορούσε να πάει, πέφτει σε C¹. Πληρώνεις μία παράγωγο σε πεπερασμένα, απομονωμένα σημεία και παίρνεις πίσω την ελευθερία της τοπολογίας. That last figure hides the one compromise in the whole method. Wherever the mesh is regular, the limit surface is a cubic B-spline — C², bit for bit the same object. At extraordinary vertices, exactly where no B-spline could go, it drops to C¹. You pay one derivative at finitely many isolated points and get the freedom of topology in return.

ΠεριγραφήDescription

Ίδια είσοδος, δύο κανόνες, δύο εντελώς διαφορετικά πλέγματα. Ο Catmull–Clark δέχεται τρίγωνα αλλά δεν τα κρατάει: κάθε n-γωνο γίνεται n τετράπλευρα, οπότε μετά το πρώτο κιόλας πέρασμα δεν έχει μείνει ούτε ένα τρίγωνο. Ο Loop τα κρατάει — κάθε τρίγωνο γίνεται τέσσερα, για πάντα. Same input, two rules, two entirely different meshes. Catmull–Clark accepts triangles but does not keep them: every n-gon becomes n quads, so after the very first pass not a single triangle is left. Loop keeps them — every triangle becomes four, forever.

• Δύο «κανονικά»Two “regulars”Ο μετρητής των μη κανονικών δεν συγκρίνεται με το μάτι: κανονική είναι η κορυφή βαθμού 4 στα τετράπλευρα και βαθμού 6 στα τρίγωνα. Είναι δύο διαφορετικοί ορισμοί, και η valenceCensus() τους παίρνει ως όρισμα αντί να υποθέτει.The extraordinary counter is not comparable by eye: regular means valence 4 on quads and valence 6 on triangles. Two different definitions, and valenceCensus() takes which one as an argument instead of assuming.
• 6 απέναντι σε 16 versus 1Και οι δύο ξεκινούν από μία μη κανονική κορυφή στο L0 — το κέντρο, βαθμού 5. Στο L1 ο Loop έχει ακόμη μία· ο Catmull–Clark έχει έξι. Τις έφτιαξε ο ίδιος: το σημείο έδρας κάθε τριγώνου γίνεται κορυφή βαθμού 3, δηλαδή μη κανονική σε τετραπλευρικό πλέγμα. Ταΐζοντας τρίγωνα σε κανόνα τετραπλεύρων πληρώνεις πέντε καινούριες ιδιομορφίες.Both start from one extraordinary vertex at L0 — the centre, valence 5. At L1 Loop still has one; Catmull–Clark has six. It made them itself: each triangle’s face point becomes a valence-3 vertex, which is extraordinary on a quad mesh. Feed triangles to a quad rule and you pay five new singularities.
• Και όμως το θεώρημα ισχύειAnd the theorem still holdsΑνέβα L2, L3, L∞: το 6 δεν κουνιέται. Γι’ αυτό η διατύπωση είναι «μετά την πρώτη υποδιαίρεση ο αριθμός παγώνει» — το πρώτο πέρασμα είναι που κανονικοποιεί την τοπολογία, και μόνο αυτό.Step to L2, L3, L∞: the 6 does not move. This is why the statement is “after the first subdivision the number freezes” — the first pass is the one that normalises the topology, and only it.
• Το β του LoopLoop’s βΤο βάρος β = (1/n)·(5/8 − (3/8 + ¼·cos(2π/n))²) δεν είναι ρυθμισμένο με το μάτι: είναι η τιμή που κρατάει την επιφάνεια C² στην κανονική κορυφή. Ο κανόνας γράφτηκε από τη λειότητα προς τα πίσω, όχι το αντίστροφο.The weight β = (1/n)·(5/8 − (3/8 + ¼·cos(2π/n))²) is not eyeballed: it is the value that keeps the surface C² at a regular vertex. The rule was written backwards from the smoothness, not the other way round.
• Ποιο να διαλέξειςWhich to pickΟ Loop, αν το μοντέλο σου είναι ήδη τριγωνικό (σάρωση, γλυπτική). Ο Catmull–Clark, αν είναι σχεδιασμένο (τετράπλευρα, βιομηχανική γεωμετρία) — και γι’ αυτό είναι το de facto πρότυπο στα CAD και στα στούντιο.Loop, if your model is already triangular (scans, sculpting). Catmull–Clark, if it was authored (quads, industrial geometry) — which is why it is the de facto standard in CAD and in studios.

Και οι δύο κανόνες απαντούν στο ίδιο ερώτημα: πώς σπάει το πλέγμα. Μένει το δεύτερο, που σχεδόν όλοι το προσπερνούν — πού καταλήγει μια κορυφή. Η απάντηση δεν είναι «εκεί που είναι». Η οριακή επιφάνεια δεν περνά από τις κορυφές του πλέγματος ελέγχου, και αυτό δεν είναι ατέλεια της υλοποίησης: είναι ο ορισμός. Both rules answer the same question: how the mesh splits. What is left is the second one, which almost everybody skips — where a vertex ends up. The answer is not “where it already is”. The limit surface does not pass through the vertices of the control mesh, and that is not an artefact of the implementation: it is the definition.

Κάθε κόκκινο τετράγωνο ενώνεται με ένα μπλε σημείο: εκεί καταλήγει. Το σημείο αυτό δεν χρειάζεται επανάληψη — βγαίνει με μία γραμμή αριθμητικής, από τους δύο γείτονες της κορυφής: Every red square is joined to a blue dot: that is where it ends up. The dot needs no iteration — it comes out of one line of arithmetic, from the vertex’s two neighbours:

P_∞ = (P₋₁ + 4P + P₊₁) / 6

Τα βάρη 1, 4, 1 δεν είναι ρύθμιση: είναι οι τιμές της κυβικής B-spline βάσης πάνω στον κόμβο. Η ίδια σχέση ισχύει και στην επιφάνεια, με τους γείτονες όλου του δακτυλίου αντί για δύο. Ο κανόνας δεν είναι επομένως δύο πράγματα — ο κανόνας που τρέχει και ο τύπος που τερματίζει — είναι το ίδιο πράγμα, γραμμένο μία φορά ως επανάληψη και μία φορά ως όριο. The weights 1, 4, 1 are not a tuning choice: they are the values of the cubic B-spline basis at the knot. The same relation holds on the surface, with the whole ring of neighbours instead of two. So the rule is not two things — the rule that runs and the formula that stops — it is one thing, written once as an iteration and once as a limit.

Πάτα τώρα Παρεμβολή. Τα σημεία που σέρνεις μένουν εκεί που τα άφησες και ο μετρητής γράφει 7 / 7: η καμπύλη περνά πλέον από όλα. Δεν άλλαξε ο κανόνας — λύθηκε το αντίστροφο πρόβλημα, δηλαδή ποιο κλουβί έχει αυτά τα σημεία ως οριακά. Και το κλουβί που προκύπτει έχει βγει έξω από τα σημεία, για να τα φτάσει η καμπύλη τραβώντας προς τα μέσα. Now press Interpolation. The points you drag stay exactly where you left them and the counter reads 7 / 7: the curve now passes through all of them. The rule did not change — what got solved is the inverse problem, namely which cage has these points as its limit. And the resulting cage has moved outside the points, so that the inward pull lands the curve on them.

• Το L∞ δεν είναι το άπειροL∞ is not infinityΟ τρίτος μετρητής συγκρίνει τον τύπο με οκτώ πραγματικά περάσματα του κανόνα. Το κενό δεν είναι μηδέν: είναι της τάξης του 10⁻⁶ και διαιρείται με 4 σε κάθε επίπεδο — μετρημένο, όχι εκτιμώμενο. Η επανάληψη τείνει στο όριο χωρίς ποτέ να το πιάσει, και γι’ αυτό οι μηχανές απόδοσης «σπρώχνουν στο όριο» με τον τύπο αντί να υποδιαιρούν ένα επίπεδο ακόμη.The third counter compares the formula with eight real passes of the rule. The gap is not zero: it is of order 10⁻⁶ and is divided by 4 at every level — measured, not estimated. The iteration tends to the limit without ever reaching it, which is why renderers “push to limit” with the formula instead of subdividing one more level.
• Το τίμημα της παρεμβολήςWhat interpolation costsΤο σύστημα Q₋₁ + 4Q + Q₊₁ = 6P είναι καθολικό: κουνώντας ένα μόνο σημείο ξαναγράφονται όλες οι κορυφές του κλουβιού. Η επιρροή σβήνει με παράγοντα 2 + √3 ≈ 3.73 ανά βήμα, αλλά δεν μηδενίζεται ποτέ — ακριβώς το αντίθετο από τον τοπικό φορέα που κάνει τη σχεδίαση να συγκλίνει. Η προσέγγιση δεν είναι ο φτωχός συγγενής της παρεμβολής· είναι η επιλογή που κρατάει τον έλεγχο τοπικό.The system Q₋₁ + 4Q + Q₊₁ = 6P is global: moving a single point rewrites every vertex of the cage. The influence decays by a factor of 2 + √3 ≈ 3.73 per step, but never reaches zero — the exact opposite of the local support that makes design converge. Approximation is not interpolation’s poor relation; it is the choice that keeps control local.
• Γιατί το κλουβί είναι φράγμαWhy the cage is a boundΕπειδή τα βάρη είναι θετικά και αθροίζουν στη μονάδα, κάθε σημείο της επιφάνειας είναι σταθμισμένος μέσος όρος κορυφών: η επιφάνεια μένει μέσα στο κυρτό περίβλημα του πλέγματος και δεν κυματίζει περισσότερο από αυτό. Στην παρεμβολή αυτή η εγγύηση φεύγει — το κλουβί βγήκε ήδη έξω από τα σημεία σου.Because the weights are positive and sum to one, every point of the surface is a weighted average of vertices: the surface stays inside the convex hull of the mesh and never oscillates more than it does. Interpolation gives that guarantee away — the cage has already moved outside your points.

Μένει το ερώτημα που δεν απαντά κανένα από τα δύο διαγράμματα: τι δεν μπορεί να κάνει η υποδιαίρεση. Δεν μπορεί να δώσει ακριβή κύκλο, ακριβή κύλινδρο, ακριβή σφαίρα. Η οριακή επιφάνεια είναι κατά τμήματα πολυωνυμική, και καμία πολυωνυμική καμπύλη δεν είναι κύκλος. Την ακρίβεια αυτή τη δίνει η άλλη μεγάλη αναπαράσταση, τα NURBS — και είναι ο λόγος που στη μηχανολογική φάση συνυπάρχουν οι δύο αντί να αντικαθιστά η μία την άλλη. What is left is the question neither diagram answers: what subdivision cannot do. It cannot give you an exact circle, an exact cylinder, an exact sphere. The limit surface is piecewise polynomial, and no polynomial curve is a circle. That precision comes from the other great representation, NURBS — and it is why the two coexist in the engineering phase rather than one replacing the other.

Δείτε τον κανόνα να τρέχειWatch the rule run

ΠαραδείγματαExamples

Όχι κλάδοι — αυτούς τους απαριθμεί η γενική σελίδα. Εδώ είναι τρεις αποφάσεις που παίρνει κανείς μπροστά σε συγκεκριμένο πλέγμα, και ο λόγος που τις παίρνει έτσι. Not industries — the overview page lists those. Here are three decisions taken in front of an actual mesh, and the reason they go the way they do.