PDA

View Full Version : Non-smooth subdivision algorithms

matthew.tipton
01-09-2016, 06:04 AM
I've learned that there are different smooth subdivision algorithms like `Catmull–Clark`, but what about NON-smooth one?

For e.g. in Blender 3D editor there are two subdivide actions smooth and non-smooth. I want to implement similar in my OpenGL program.
As I have viewed other frameworks where the non-smooth algorithm exists, it's like some kind of linear simple function, but I want to use well-known practice.
So, do exist some well-known algorithms for the non-smooth subdivision with a good asymptote? Because, Google shows only results for the smooth algos exactly.

GClements
01-09-2016, 07:21 AM
Non-smooth subdivision normally means that you treat a set of faces as being just that: faces of some polyhedron. Subdividing gives exactly the same polyhedron, just with more vertices and faces.

Smooth subdivision treats the faces as being an approximation to a smooth surface. Subdivision creates a better approximation to the surface.

Smooth subdivision is more complex because you typically want each level of subdivision to be self-contained (i.e. the subdivided geometry replaces the original geometry) while the limit of a sequence of repeated subdivisions is determined by the original geometry.

Non-smooth subdivision is simple enough that there isn't really much that needs to be written about it. It's basically a solved problem, there aren't going to be any new "algorithms" developed. It's just a matter of choosing where to subdivide, at which point the resulting vertices are known.

matthew.tipton
01-09-2016, 09:45 AM
Non-smooth subdivision normally means that you treat a set of faces as being just that: faces of some polyhedron. Subdividing gives exactly the same polyhedron, just with more vertices and faces.

Smooth subdivision treats the faces as being an approximation to a smooth surface. Subdivision creates a better approximation to the surface.

Smooth subdivision is more complex because you typically want each level of subdivision to be self-contained (i.e. the subdivided geometry replaces the original geometry) while the limit of a sequence of repeated subdivisions is determined by the original geometry.

Non-smooth subdivision is simple enough that there isn't really much that needs to be written about it. It's basically a solved problem, there aren't going to be any new "algorithms" developed. It's just a matter of choosing where to subdivide, at which point the resulting vertices are known.

Ok, dude. But let's compare thiz sutff with the sorting algo.

Are they more complex? As for me - no.
The sorting algos are different: bubble sort (any lamer know it), quick sort, gnome sort etc...

As I suppose, the sorting algo is MILES EASIER (but there various cont of sorting algos) than any non-smooth subdivision algo (but of course, it may be only my opinion).

So, if it's too easy, can you provide here, please a simple algo, just for a cube, please?
I will be very thankful for it and I think any who will google the similar topic will be thankful too.

GClements
01-09-2016, 03:43 PM
To subdivide geometry (without any kind of smoothing), you generate new vertices by linearly interpolating each edge. The simplest case is subdividing by a factor of two, i.e. each new vertex is just the midpoint (average) of two other vertices. To divide an edge into N equal parts, the new vertices are (i*v1 + (N-i)*v2)/N for 0<i<N (i.e. i between 1 and N-1 inclusive). When N=2, this is just (v1 + v2)/2.

For a triangle, you find the midpoint of each edge. Now you have 6 vertices which are connected like so to form 4 triangles.

o
|\
| \
| \
o---o
|\ |\
| \ | \
| \| \
o---o---o

To subdivide a quadrilateral (4 vertices and 4 edges) into smaller quadrilaterals, you find the midpoint of each edge, plus a centroid which is the average of the 4 initial vertices. This gives you 9 vertices (3x3) which you use to create the smaller quadrilaterals.

o---o---o
| | |
| | |
o---o---o
| | |
| | |
o---o---o

Or you could split it into two triangles then use the above scheme, or treat it as a polygon using the following scheme.

For a polygon with 4 or more sides, you'd typically start by finding the centroid (the average of all of the vertices) and tessellating the polygon into triangles:

o-----o
/ \ / \
/ \ / \
o-----o-----o
\ / \ /
\ / \ /
o-----o

Thereafter, you'd use the triangle scheme above.

When you're dealing with meshes made from connected polygons (i.e. which share edges), you'd typically want the smaller polygons to also share edges. Probably the simplest way to achieve this is to use an associative array (dictionary, hash table, ...) whose key is a pair of vertex indices and whose value is the index of the new vertex formed from subdividing the edge between the first two vertices. So before subdividing an edge, you check if it's already been done, and if it has you use the existing vertex rather than creating a new one.