# Catmull-Clark brainstorming

#### BentFX

##### New Member
OK, heres the deal...
Let's recreate the wheel and recreate it better!

I'm working on a project where I'm dealing with catmull-clark subdivision of polygons... in C++. I'm looking for an ingenious algorithm to keep track of points and faces for subdivided 3D faces. To subdivide each face, a point is plotted at the center of the face and edges are created to the midpoint of each edge of the face. And it must take into account that the algorithm is recursive(ie. subdivided faces can be subdivided again on recursive passes)

Talk to me about the patterns you see in the attached image...

It is really a lot more involved than what I've said, but truly, talk to me, and we'll work out the deeper considerations as we go.

It is a simple routine... place a point in the center of the face and split new edges to each face-edge...

Anyone... Come on... help me out with this!

Thanks,

Skip

#### Attachments

• cat-clarke.png
127.6 KB · Views: 480

#### BentFX

##### New Member
It is a difficult problem, but it is simple... each face(after the first pass) is broken into four faces.

This is for an opensource project(click around in my sig if you need more input)
Edit:
These are some rules I've already figured out...
on first subdivision pass...
vertices = FaceCount + EdgeCount (each face is broken in the center, and each edge is broken at its midpoint)
faces = edge count of existing faces(it's true, think about it)

Anyone want to help me.... really... I need help!

Last edited:

#### BentFX

##### New Member
I got it, but really Thanks for all the input I realize now that it isn't really the kind of problem thats normally discussed here... But here is the solution if anyones interested... In a couple days I'll follow up with a C++ snippet.

keeping googlers happy... Catmull Clark subdivision polygon mesh programming algorithm source code how-to
[/edit]

#### Attachments

• split.png
115 KB · Views: 1,172
Last edited:

#### taekwondokid42

##### New Member
Yeah, most of the people here do not work with "programming" languages. PHP is usually as deep as we go.

I wish I could help but I can't even say "hello world" in C++ (although I'd imagine it's very similar to other languages)

#### TechAsh

##### Retired
taekwondokid42 said:
I wish I could help but I can't even say "hello world" in C++ (although I'd imagine it's very similar to other languages)

Code:
``````#include <iostream>

int main()
{
std::cout << "Hello, world!\n";
}``````

There you go, how to say "Hello World" in C++

Note: I do not know any more C++ than that, so please don't ask me to help coding anything as I won't be able to help.

#### BentFX

##### New Member
Well as things sunk in a bit, I realized that the steps I outlined for subdividing a face aren't the holy grail I need to find. I still need to structure the face data such that I can access the vertices in a coherent way, without re-subdividing the entire mesh.

Since this is the basis for the program I'm working on, I'm moving this thread to my own forum... Please surf to it and follow the progress, if it is of interest to you... new thread

#### BentFX

##### New Member
HAHAHAHA!!!! I GOT IT!!!!

Patches! yup, I said PATCHES!

The struggle was to find a pattern that would fit a quad and also relate to an n-gon. We are already using a halfedge data structure where edges point clockwise around each face. The patch concept makes each halfedge also responsible for a sub-quad. The halfedge data structure already manages pointers to next previous and opposite halfedge. Since we already manage pointers to the neighbor halfedges, this is merely an extension whereby we can keep track of shared points with the neighboring patches... This is the atomic structure by which any base mesh can be defined/displayed/subdivided/etc.

If you don't see it, OK, it doesn't matter... It's gonna Work!

#### Attachments

• patches.gif
24.5 KB · Views: 215
Last edited:

#### BentFX

##### New Member
Okay, we've already determined that this programming bit goes beyond the scope of the SD&D forums, yet I think this post is necessary to place the previous posts into proper context. If you've read the thread and are still wondering what the heck I'm talking about this image should do a lot to explain it. It's polygon mesh subdivision/smoothing. In the image is my little chopper model, showing both the base mesh, and with one smoothing pass...

(moderators: due to the off topic nature, I am now linking to images rather than attaching.)

#### cowctcat

##### New Member
well just use my awesome solution guaranteed to work every once in a while:
Throw some random code together and hope it works!

lol
my knowledge of c++ goes to about the point where i can write "helo world" to a text file thats it.

#### BentFX

##### New Member
Hi kllctcat,

Thanks for the suggestion. I have ADD(attention deficit disorder), and truly, even my own code, seems like random nonsense much of the time.

I can usually think up a solid solution to a problem, but when it comes to coding it, I spend most of my time trying to figure out what I was just doing. The one decent upside is, I'm learning to write well commented code.

Skip
Edit:
Here's the chopper model with two subd passes...

I only plan to support three subd passes, but programming the third pass will wait, while I work out how to handle some special case stuff that this model doesn't have. Such as holes in the mesh, and creased edges. I also need to add vertex normals which will smooth out the blocky shading.

(Yeah, at this point I'm just showing off )

 Vertex normals was easy. I already had them allocated in the data structure. I just needed to calculate the normals, and figure for them in the drawing loop...

Last edited: