How to get OutLine of Polygon object

chuanzhen

Hi,
How to get the Outlines of polygon objects, just like in the image.

Thanks for any help!

ferdinand

Thank you for reaching out to us. Both in the Python and C++ Cinema 4D API there is no function to extract the outline of an object. Your question is therefore an algorithm question and out of scope of support. I have moved your topic to our General Talk forum.

About your Question

When I use the word polygon(al) in the section below, I am referring to the mathematical concept. When a polygon in the sense of a mesh element is meant, I will use the words quad(rangle) and tri(angle).

This is very much an algorithm question, and I am limited in how much help I can provide. The topic also ranges from medium to high complexity, depending on what you want to do exactly.

First, I am assuming that you want to find the polygonal outline of your object, based on some tri/quad mesh data. If you want to operate on an RGBA or alpha pass in a rendering, you might want to investigate things like the Sobel kernel and how to construct polygons on it.

Finding the polygonal outline of a (discrete) mesh can be split into three steps:

Project the points of the mesh into a plane, usually the camera plane. There are some helper functions in BaseView which can help you with this, but you can also just do it on your own.
Remove all polygons facing in the opposite direction than the projection plane normal. Doing this is not absolutely necessary but makes the third step less complicated. You could also remove the polygons facing away from the camera before the first step, but doing it after the projection is easier because they then either face you directly or not.
The third step is the hardest, as you must build the complex polygon, the outline, out of your projected tris and quads. First, you should convert the whole mesh into tris, and then you must run a Boolean union of polygons algorithm on them; the Vatti clipping algorithm is very popular. In practice you then iteratively join all tris into your output outline polygon P which starts out as the empty set.
- In Cinema 4D you could side-step this last point by not implementing the recursive Boolean union yourself, but by using the Spline Mask object. Just construct splines for all your tris and quads (here you would want to avoid converting quads into tris) and add them to the Spline Mask object as input objects. Then evaluate the cache of the Spline mask and you have your outline. The Spline Mask can only evaluate discrete objects though, it cannot join segments within a spline (at least I could not make that work when I tried). So, for an object with one thousand polygons, you would have to construct one thousand splines. This approach is therefore extremely limited when it comes to performance and scalability.
- If want to do anything akin to what for example our Sketch and Toon or some games do, i.e., generate in real time the outline over animated geometry, you will have to do that in C++ (Python will not even remotely be performant enough) and also implement the recursive Boolean union of polygons yourself.

We cannot give any further advice on the algorithmic portion of this subject.

Cheers,
Ferdinand

chuanzhen

@ferdinand Thanks for your detailed reply, it is helpful!

fwilleke80

Another idea: You could also use some primitive way to render an object mask (e.g. white object on black background), and then run an edge recognition kernel on the resulting image.

chuanzhen

@fwilleke80 Thanks

Paul Everett

Think edges. an edge has 2 polygons.

for each polygon, check the face normal direction against camera z vector. (dot product of normal and cam z)

run through all edges.

if the 2 polys of any edge, face in different directions, that's an outer edge candidate.
Build a list of outer edge candidates, sort it, and connect the dots.

more or less what Ferdinand wrote, but its simpler if you just think of it as edges.

best
Paul

baca

@Paul-Everett not really

In fact, if it's not convex-hull geometry, some edge might be fully or partially covered by some polygon(s) laying in front if this edge.

ferdinand

Hi,

Paul is describing there what usually runs under the label of a "folds" computation which will contain line segments humans would consider "inside" a shape but sensible nonetheless. This can be cheaper than what I described under outline. But it won't always give you the correct outline, my approach is slow but will always yield a correct 2D outline including holes.

When one can use vertex shaders, an even cheaper form of Paul's approach is just flipping the normals of a copy of a to be "fold-outlined" mesh and then move each polygon -n units (the outline thickness) along its normal (and turn on backface culling for that mesh). Games often do it that way but the results can get a bit janky.

There are many ways to do this which is why we tend to stay away from algorithmic questions

Cheers,
Ferdinand

Paul Everett

you can test for all cases, that's why I call those edges "candidates".

The devil is always in the details.

There are many ways to skin this cat.

best
Paul