Jump to content
  • Advertisement
Sign in to follow this  
billconan

need backup of subdivision

This topic is 4809 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hi guys, i'm writing a 3d tool myself. but now i'm stuck by the catmull clark subdivision. i'v got a chinese version book named <realtime redering> which mentions this subdivision method. but the book is poor published, the diagram to explain the subdivision algorithm does not contain the necessary legend, so i still don't get it. and i've googled a lot, just can't find much information. i know the subdivision can be divided into 2 steps. first, linear subdivide the mesh and then renew the positions of vertices by calculating some average. it's not complicated to linear subdivide a mesh, and the real problem is how to get the new vertices positions? i can't find the right expression for doing this (averaging). for example, look at the subdivision process in silo ( http://www.nevercenter.com ) a mesh like this: will be like this after subdivision: add the subdivision level: here is a problem, from the top view, you see, it is easy to understand the new position for the point A, because it might be calculated by averaging the old A and the centroid of the mesh. but how about the B? it did not move after the subdivision, why? it should be averaged with the centroids of meshes to which it adjacent. no matter what the subdivision level is, the B just didn't move. so, what is the difference between B and A. B has two adjacent meshes while A gets only one. does that mean the position of those points with more than 1 adjacent mesh won't be renewed? NOPE! another example is like this: the B got 3 meshes adjacent to it, and after the subdivision process, it moved. so, does that mean, a vertex with 2 adjacent meshes won't be renewed? still, NOPE! for example: so what is the expression for the averaging part behind the catmull clark subdivision algorithm? i can explain my problem in a more simple way: how to subdivide this: after the right process, it should be like this: and, how to subdivide this, and why B and C don't shrink in (move)? what is the expression? thank you. and really sorry for my poor english, hope you can understand it.

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
Your last image is a good test case.

If you consider the corner area where A is, you will notice that the newly created vertex on the top edge is precisely between the original A and B. The newly created vertex along the side of the upper corner is precisely between the original A and that original vertex halfway down the side.

It is only after these new vertices are created, that the new positions of the old vertices are computed. And they are computed considering ONLY THE BOUNDARY EDGES. The line running from B down through the figure is NOT an edge as its shared by multiple polgons.

In the case of A, A is connected via edges to two newly created vertices. The new position of A is the average of A and those two vertices.

In the case of B, B is connected to two newly created vertices as well (although you cant see them) and B is the average of itself and those vertices (which in this case means B doesnt move)

In general, smooth subdivision surfaces come in two classes. Those where the new surface extends through all the original control points, and those where that is not the case. The subdivision in question is the later, not the former.

In all subdivision schemes, there is a special case for BOUNDARY vertices and edges (as well as what are called 'extraordinary vertices'). Like the ones that entirely surround your figure but not the ones that run through the middle. How the boundary cases are handled cannot be easily defined. There is no general 'all purpose' method. Sometimes you want those boundary edges to be smoothed and sometimes you do not.

In this case, definate boundary smoothing is happening and the subdivision scheme does not create a surface that runs through all the original control points.

I do not know if the software you are using can be configured differently.

- Rockoon (Joseph Koss)

Share this post


Link to post
Share on other sites
hi there pal, thank you for replying, but what do you mean by THE BOUNDARY EDGES?

you mentioned that the B connects to two new vertices, but in my humble opinion, B should connects to 3 new vertices as in the image(after the linear subdivision), it should move after the average.



and you said that edge points should be handled differently, so in my case, how to know B is in the edge and A is not? i just can't simply judge this by the number of adjacent meshes.

thank you.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by billconan
hi there pal, thank you for replying, but what do you mean by THE BOUNDARY EDGES?


I mean that there is only one polygon that uses the edge. That makes it a boundary edge.

For example:



A--B--C
| | |
D--E--F



The edge BE is shared by the polygons ABDE and BCEF. It is not part of the boundary of the object but rather just a regular old polygon edge. We arent interested in smoothing polygons. We are interrested in smoothing objects.

Quote:
Original post by billconan
you mentioned that the B connects to two new vertices, but in my humble opinion, B should connects to 3 new vertices as in the image(after the linear subdivision), it should move after the average.


Forcing your opinion of the problem onto the problem domain isnt going to help you. Consider the problem, not your opinion of it. Pretty much "free your mind."

AFAIK, all subdivision algorithms consider how many polygons share an edge and act differently depending on this consideration. If the vertex in question is connected to a boundary edge, then it is treated as a boundary vertex. If it is not connected to a boundary edge, then it is treated as a general vertex and the general subdivision smoothing is applied.

You should probably do some research into the Loop Subdivision algorithm. Loop (who works for Microsoft now?) wrote a nice paper on it at one point. This algorithm is ideal for Direct3D graphics as it works with triangles, not arbitrary polygons. Triangles are the workhorse of DirectX mesh objects. Also, the Mesh object has the built-in ability to generate adjacency information which can be used to determine what edges and vertices are on the boundary of the object.

- Rockoon (Joseph Koss)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!