Page 1 of 1

Doo-Sabin Subdivision surfaces.

Posted: Thu Nov 25, 2004 9:02 am
by NateTG
Hey, I'm new to coding in blender (and fairly new at coding in general), so I decided to take on a little project to get myself aquianted with the code. I decided to try to implement Doo-Sabin subdivision surfaces. I have made some significant progress, but I am running into trouble on a few issues.

Although I can create 3 vertex faces with hypermesh_add_face, hypermesh_to_displistmesh seems to have a problem with them (I get an access violation here:

Code: Select all

static DispListMesh *hypermesh_to_displistmesh(HyperMesh *hme, short flag) {
.
.
mf->v1= (int) f->verts[0]->nmv;
mf->v2= (int) f->verts[1]->nmv;
mf->v3= (int) f->verts[2]->nmv;
mf->v4= (int) f->verts[3]->nmv;/*<--right here*/
Also, hypermesh_to_displistmesh seems to require that all hyperfaces point to an original editface (hyperface->orig) however, with Doo-Sabin, there are faces that are not directly descended from original faces. I got around this by pointing to the closest face, but I am not sure what the side effects of that are.

Finally, I am wondering if there is any order to the verts array in HyperFace. Am I guaranteed that vert 0 will not share an edge with vert 2? ie:

Code: Select all

0-----1
|     |
|     |
3-----2
Any insights would be most valuable.
thanks
\n

Posted: Thu Nov 25, 2004 10:04 am
by bjornmose
Looks like subdividing always calls
hypermesh_add_face(blah, blah, 4,blah);
to make sure all 4 pointers are valid.

geee what a hack.

/BM

Posted: Thu Nov 25, 2004 10:22 am
by NateTG
yes, that is the problem. catmull clark always generate 4 sided polys. Doo-Sabin doesn't.

I was hesitant to change too much existing code, but i solved the problem like this, in hypermesh_to_displistmesh:

mf->v1= (int) f->verts[0]->nmv;
mf->v2= (int) f->verts[1]->nmv;
mf->v3= (int) f->verts[2]->nmv;
if (f->nverts==4) mf->v4= (int) f->verts[3]->nmv;
else mf->v4=NULL;
.
and...
if (f->edges[0]->flag) mf->edcode|= ME_V4V1;
if (f->edges[1]->flag) mf->edcode|= ME_V1V2;
if (f->edges[2]->flag) mf->edcode|= ME_V2V3;
if (f->nverts==4 && f->edges[3]->flag) mf->edcode|= ME_V3V4;

again, since I am unfamiliar with the blender code, I don't know what side-effects this might cause. Now I am almost done! Although, I have no idea how uvcoords would translate over in Doo-Sabin... :x

Posted: Sun Nov 28, 2004 5:20 am
by NateTG
:evil: alright.. I'm ready to give up. I cannot figure out a way to solve extraordinary points. Wihtout n-gons in blender, Doo-Sabin is impossible. On top of that, it would be implausible to translate UV coordinates onto the subdivided surface I think. Although its a shame to give up. I was pretty happy with the results I was achieving...

Its was a good learning experience anyway.
\n

Posted: Sun Nov 28, 2004 3:35 pm
by theeth
The UV interpolation problem must be why Doo-Sabin is used less often than Catmull-Clark (AFAIK).

Having a second subsurf algorithm could have been useful.

Martin

Posted: Sun Nov 28, 2004 10:18 pm
by ideasman
why not impliment it without UV's to start with?

I think its best to add these things early and you can fix and add allong-
Hell- The exact knife tool dosent support UV's (assumes midpoint and messes up your whole UV map.)

Posted: Sun Nov 28, 2004 10:54 pm
by NateTG
Yeah, that was what I was intending to do in the first place. But my main problem is not the UVs it is extraordinary points with valence higher than 4. These points require n-gons, since Doo-Sabin is a vertex refinement scheme.

Other than extraordinary verts, it works fine. So as long as you have a mesh in which no vert has more than 4 edges, it looks great.

In my reading, I have found that this is one of the reasons Doo-Sabin and other vertex refinement/corner-cutting shemes have not come to common use.

I am thinking of working out a hybrid scheme though....
Also, I would like to implement the loop scheme, but that requires tris only in the mesh.

\n

Posted: Sun Nov 28, 2004 10:59 pm
by NateTG
oh also, I'm getting a lot of errors with blender's memory manager stuff... Is there anywhere I can read up on how this all works?

Posted: Mon Nov 29, 2004 1:12 am
by theeth
Compiling errors or runtime prints in the console? Runtime prints are usually caused by memory leaks.

Martin

Posted: Mon Nov 29, 2004 5:01 am
by NateTG
runtime errors. ya i figured it was memory leaks. but I'm not sure what could cause it. I am only using hypermesh_add_vert, edge and face... and it looks like they handle all the memory stuff... :?

and if anyone could answer this question:
am I guaranteed that verts[0] and verts[2] of a hyperFace will not share an edge?

thanks
\n

Posted: Wed Dec 01, 2004 11:51 pm
by Youssef|3d
well, if you have a quad, verts[0] and verts[2] are not able to share a edge, because you won't get a quad. A triangle is differnt. One of its three edges lies between those two verts.

The reason is that a face structure always contains a single face. If a edge would run through a face, it would have to be split up into two face structures, each of them containing exactly one triangle.

Posted: Thu Dec 02, 2004 1:54 am
by NateTG
I realize the logic behind it ;) I just didnt know if blender I was guaranteed that Blender wouldn't index the verticies 0,2,1,3 for example. Being new to coding blender, I have very little knowledge of how its data structure works. I was just double checking. Thanks though. :D

Posted: Wed May 11, 2005 9:39 pm
by Anthony
Nate, what's the status on this project? I'd really like to have a doo-sabin option. In fact, I've coded my own algorithm in python, but it's way too slow.

See this elysiun post to download.

Posted: Wed May 11, 2005 11:11 pm
by NateTG
Anthony, the project is currently on hold indefinitely. It worked alright (although my algorithm is horribly inefficient), except for extraordinary verticies, where ngons are required (I wasn't too eager to triangulate them, especially since blender's subdivision surfaces are recursive). And i had some crashes because of memory, which I couldn't figure out.

I'll take a look at your code. Maybe if I had a smart fellow to work with, I could be persuaded to take it up again.

\n