Sign in to follow this  
teutoburger

Does Catmull Clark Subdivision work for Meshes consisting of only triangles?

Recommended Posts

That's my question, does Catmull Clark Subdivision work for Meshes consisting of only triangles or is it basically designed for quad-faced meshes?

 

All the sources I found, somehow gave me the impression it works for Meshes made up of quad faces. Does it also work for Meshes with triangular faces?

Additional question, if it doesn't work, it there any subdivision scheme that works for such meshes?

 

Share this post


Link to post
Share on other sites

so, if I understand you correctly, given a triangle mesh, basically the usual/recommended way to use subdivision would be to:

 

-do a mesh operation, so that the triangle mesh is converted to a quad-faced mesh

-do subdivision on the quad-face mesh

-triangulate the quad-face mesh ?

 

edit: I'm trying to build tools, that allow me to create models, for populating my game world. I'd like them all to run from the same code base. So one of these tools should be a subdivision tool.

 

With that in mind, actually a better high level strategy, is to construct a quad-faced mesh from code, use that as input for catmull clark subdivision, and finally triangulate the output, use that as in-game mesh.

Edited by teutoburger

Share this post


Link to post
Share on other sites

Catmull-Clark works on any convex polygon (including triangles), but it is better suited to quads and produces all quads after just one iteration.

For triangular meshes usually Loop subdivision can be better and it produces a triangular mesh. There is also the old ATI/AMD gpu friendly PN triangles subdivision.

 

PS: some references!

http://graphics.stanford.edu/courses/cs468-10-fall/LectureSlides/10_Subdivision.pdf

https://www.cise.ufl.edu/research/SurfLab/papers/00ati.pdf

Edited by Jihodg

Share this post


Link to post
Share on other sites

From the artists point of view: Catmull Clark is a great subdivison method, but it totally requires quad meshes.

The artist will avoid triangles almost always and tries to use 5-sided polygons instead when necessary.

So use it only if you are willing to model with quads.

 

If you already have a lot if triangle models, conversion to quadmesh is hard to do for both humans or algorithms (eventually it's necessary to remesh the model).

Try Loop subdivision first for triangle meshes.

 

Some software uses Loop for triangles and Catmull Clark for anything else (e.g. XSI) - that's good but still the artist needs to work for a known subidivsion method upfront.

Modeling first and choosing kind of subidivsion later is a bad idea.

Share this post


Link to post
Share on other sites

Thanks for the links, it's hard to find the good papers and lectures..

I got it working. After some ridiculous drafting..

The catmull clark delivered quad faces, as you say. I had to triangulate them and then check their orientation. 

If the normal pointed inwards, the triangle had to be index-ordered, so that they were oriented such that the normal pointed outwards. Also my whole procedure is probably not very efficient. But it works. Thanks for the tips.

Here's the unit cube, after one subdivision pass.

 

[attachment=34158:catmull-clark.png]

Share this post


Link to post
Share on other sites

It can be done, the problem is that dividing a triangle produces incorrect result up to 50% of the time.

It's the same problem when using a auto program to divide your quad mesh into triangles, it just uses a formula it has no way of knowing if the model looks correct.

 

Here is a quick example using Blender to explain.

ux250Tx.png

 

 

 

if it doesn't work, it there any subdivision scheme that works for such meshes?

I have once seen it done with tessellation of a triangle mesh. How it works I have no idea maybe some kind of smoothing based on the normal?

 

I am not sure about what was done in order to have the image at the bottom-right. It does not look to be a subdivision since the number of faces look to be approximately the same.

Share this post


Link to post
Share on other sites

I am not sure about what was done in order to have the image at the bottom-right. It does not look to be a subdivision since the number of faces look to be approximately the same.

left side shows good result from quad mesh, right side shows bad result from trimesh.

It's a good image to show the problem. Maybe you assumed right side means result from left side but that's not the case.

 

Catmull-Clark works on any convex polygon (including triangles)

That's slightly wrong - polys don't need to be convex (and also not planar).

Share this post


Link to post
Share on other sites
I got it working. After some ridiculous drafting.. The catmull clark delivered quad faces, as you say. I had to triangulate them and then check their orientation.  If the normal pointed inwards, the triangle had to be index-ordered, so that they were oriented such that the normal pointed outwards. Also my whole procedure is probably not very efficient. But it works. Thanks for the tips.

Looking good, very well done.

 

I would love to see how it responds to a normal model, if possible could you get one of the free models on the internet and show us the results? 

I think the unpredictable way artist work would cause some unexpected results, although it looks really good so there is no way of telling without testing. 

 

 

 

so, if I understand you correctly, given a triangle mesh, basically the usual/recommended way to use subdivision would be to:   -do a mesh operation, so that the triangle mesh is converted to a quad-faced mesh -do subdivision on the quad-face mesh -triangulate the quad-face mesh ?

Converting to triangles, back to quads and then back to triangles will cause some unexpected results. It has the same problem as dividing, the code follows a solid rule and won't be able to work with strange results that artist could produce.

 

Of course if you knew what problems do happen you could set rules to allow for creation for assets that would work perfectly with your code.

 

 

 

I am not sure about what was done in order to have the image at the bottom-right. It does not look to be a subdivision since the number of faces look to be approximately the same.

It's normal in subdivision for faces to look the same, same leagnth faces makes it easy to work with and the results predictable.

H1zmLbF.png

Here is the mesh divided. First no division, then basic division followed by simple division and last is Catmull Clark.

Maybe it looked strange because I first used a simple division on the cube to resemble a more likely mesh, I also used two passes?

Edited by Scouting Ninja

Share this post


Link to post
Share on other sites

Maybe you assumed right side means result from left side but that's not the case.

 

That's effectively what I did. Thanks for the precision. It makes more sense now.


Maybe it looked strange because I first used a simple division on the cube to resemble a more likely mesh, I also used two passes?

 

Look weird to me because I assumed things bad :)

Share this post


Link to post
Share on other sites
, if possible could you get one of the free models on the internet and show us the results? 

 

I can try. I've been meaning to add an .obj reader routine anyway. But I can tell you already it won't work for non-convex meshes.

What my current code does, is only this:

-take the average a of all mesh vertices

-for each face:

get the normal n of the face

get the center c of the face 

v := c-a

get angle between v and n

use the value of angle to decide wether the face is oriented the right way.

(if value smaller 0 or greater 0)

if needed, change the ordering of the face indices

 

So this works only if you can assume that all faces are around the mesh center and should be facing outward..

 

so.... there is room for improvement..

Edited by teutoburger

Share this post


Link to post
Share on other sites

I can try. I've been meaning to add an .obj reader routine anyway. But I can tell you already it won't work for non-convex meshes.

Even so if you could get it to work on 70% of a mesh it could be considered production ready, it won't be the best out there but it will be a very good start.

 

-for each face: get the normal n of the face get the center c of the face  v := c-a get angle between v and n use the value of angle to decide wether the face is oriented the right way. (if value smaller 0 or greater 0) if needed, change the ordering of the face indices

Could you maybe allow the artist to control the subdivision by using vertex paint?

 

So when the vertex is white the face is considered convex and a black vertex is considered to be concave. Now you can check if it's concave or convex and adjust your formula, it will also allow the artist to have a weight option on deciding how convex or concave a mesh is.

Share this post


Link to post
Share on other sites

Even so if you could get it to work on 70% of a mesh it could be considered production ready, it won't be the best out there but it will be a very good start.

 

Okay I added a minimal Obj reader to my code base. This is starting to get off topic, sorry about that... 

But my code assumes that the mesh is not very large in file size (KB rather than MB) and it assumes that the Mesh is closed ( no holes, there should be an inside and an outside). It can be concave or convex, both works. And it can contain any number sub-meshes, as long as they are closed respectively. If you have any test meshes, I'd be happy to test a few.

Or point me to a site that has such meshes (closed meshes..).

 

The ones I keep finding are all too large file size or have holes. Maybe I should be looking for models that are specifically made for games, they are probably smaller file size(?)

 

My subdivision also assumes closed meshes.

 

The vertex painting... hmmm.. have to think about that.

Share this post


Link to post
Share on other sites

I found a model. But discovered some bugs in my code, they have to be fixed first anyway so no urgency anyway. Have to fix stuff first.

 

Edit: Fixed. Actually the model I tested on, had holes. So it not working with the subdivision, was expected behaviour.

Edited by teutoburger

Share this post


Link to post
Share on other sites

Finally found some free time to make the model:

.Blend file https://drive.google.com/file/d/0B3hHgiNtHATdM1ZLRGRrM1MxcE0/view?usp=sharing

.Fbx file https://drive.google.com/open?id=0B3hHgiNtHATdRXJHN2hldk1aTVk

rCNlXw1.png

The top shows the model with no division, middle shows the topology and last is how it should look when divided.

It is a manifold mesh as you asked.

 

You will note that the mesh is +/-15 000 triangles, although in a game it will be about a 1/3 (+/- 6 000 triangles) of that as I used reinforce loops instead of marking the edges.

To use marked edges you need a custom importer for it and you need to support custom normal importing. Because I didn't know if you have this in your engine I used loops, because they are part of the mesh they will always work.

 

R8RfVnB.png

The first object has no support, the second uses reinforce loops and last uses marked edges that would be used in games normally. You will see that the marked edges produce a very sharp look, this is often favored in games because of how small models appear on screen while playing.

 

 

It was interesting to make this model because I wanted to place in things that I knew can cause problems when divided, you will see there is triangles and such, the Catmull Clark Subdivision does work with them, it will be interesting to see if your code does.

 

I don't want you to feel like there is a obligation for you to complete the code or to perfect it, I am just interested in these kind of work as a 3D artist. If you ever do complete it please allow us to see the results. :)

Edited by Scouting Ninja

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this