投影3D网格的2D轮廓算法

Given: A 3D mesh defined with a set of vertices and triangles building up the mesh with these points.

给定:使用一组顶点和三角形定义的3D网格构建具有这些点的网格。

Problem: Find the 2d outline of the projected arbitrarily rotated mesh on an arbitrary plane.

问题:在任意平面上找到投影任意旋转网格的2d轮廓。

The projection is easy. The challenge lies in finding the "hull" of the projected triangle edges in the plane. I need some help with input/pointers on researching this algorithm. For simplicity, we can assume the 3D edges are projected straight down onto the xy plane.

投影很容易。挑战在于找到平面中投影三角形边缘的“船体”。我需要一些关于研究这种算法的输入/指针的帮助。为简单起见,我们可以假设3D边缘直接向下投影到xy平面上。

6 个解决方案

#1

Start with the rightmost point (the point with the biggest x coordinate)

从最右边的点开始(具有最大x坐标的点)

Get all edges from this point

从这一点获取所有优势

Follow the edge with the smallest angle to the positive x-axis, and also add it to the solution set

沿着与正x轴最小角度的边缘,并将其添加到解集

From the point reached, follow and add the edge with the smallest angle to the edge you came from

从达到的点开始,跟随并添加具有最小角度的边缘到您来自的边缘

Repeat until you reach the original point

重复,直到达到原始点

#2

I only see answers for convex solutions, so here is mine for non-convex. (It was a little confusing what was the intention.)

我只看到凸解的答案,所以这里是非凸的。 (这意味着什么有点混乱。)

Take all edges from your 2D-triangles and group them. If two edges share both endpoints, they are in the same group. All groups, with only one edge, is then a part of the shell.

从2D三角形中取出所有边并将它们分组。如果两条边共享两个端点,则它们位于同一组中。所有只有一条边的组都是shell的一部分。

Finally you can combine the shell-edges to one ring, by joining them together.

最后,您可以将外壳边缘组合到一个环上,将它们连接在一起。

#3

The alpha shapes technique mentioned in this question handles a general set of points where the vertex connections are not known:

此问题中提到的alpha形状技术处理顶点连接未知的一般点集:

Is there an efficient algorithm to generate a 2D concave hull?

是否有一种有效的算法来生成2D凹壳?

However, since you already know "face" information which can be preserved through the projection, it is probably not the best approach.

但是,由于您已经知道可以通过投影保留的“面部”信息,因此可能不是最好的方法。

A brute force algorithm might feasible, especially if spatial sorting structures where used. eg for each facet:

蛮力算法可能是可行的,尤其是在使用空间排序结构的情况下。例如,对于每个方面:

Project facet on to the plane

项目方面在飞机上

Check if projected facet is completely enclosed by existing geometry, if yes: done (no need to expand projected silhouette)

检查投影面是否完全被现有几何体包围,如果是:完成(无需扩展投影轮廓)

If points fall outside the existing geometry, do triangle-triangle intersections to determine which portions fall outside, build an arbitrary n-gon (possibly concave) to fill the missing space, then chop the n-gon in to triangles

如果点落在现有几何体之外,请执行三角形 - 三角形交叉点以确定哪些部分落在外面,构建任意n-gon(可能是凹形)以填充缺失的空间,然后将n-gon切入三角形

Another idea, depending on the fidelity you require, is just shoot a bunch of rays normal from your projection plane to your original geometry. Create a 2d hit/miss and use that to determine your extents.

另一个想法,取决于你需要的保真度,只是从你的投影平面到原始几何体射出一束正常光线。创建一个2d命中/未命中并使用它来确定您的范围。

#4

The 2D outline of the mesh projection is a subset of the projection of its edges.

网格投影的2D轮廓是其边缘投影的子集。

Using this observation, one can determine the 2D outline using the following method:

使用此观察,可以使用以下方法确定2D轮廓:

the projection of every edge belonging to only one face is part of the 2D outline,

仅属于一个面的每个边的投影是2D轮廓的一部分,

for other edges, determine the normal vector of its adjacent faces

对于其他边缘,确定其相邻面的法向量

calculate the dot products of those normals with the normal of the plane of projection

用投影平面的法线计算那些法线的点积

the projection of this edge belongs to the 2D outline if all the signs of the dot products not the same (which means, one face is pointing towards the projection plane while at least one other doesn't, which identifies the edge as part of the outline).

如果点积的所有符号不相同(这意味着,一个面指向投影平面,而至少另一个面不指向投影平面,则该边缘的投影属于2D轮廓,其将边缘识别为大纲)。

Note that this method will report all the edges that are orthogonal to the projection plane, even those which are not visible from the projection plane's point of view. For example, with a torus, it will find the interior and the exterior outlines, even when the torus is rotated in such a way that its interior hole isn't visible from the projection plane's point of view. To sort out which edges are visible, you will need some sort of visibility test. If the intended use is for user display, you can use a depth buffer computed with an orthogonal projection matrix to render the geometry from the projection plane's point-of-view and do some z-testing to determine which edges are visible from the plane. If you need precision, you will need to perform ray/triangle intersection to determine visibility.

请注意,此方法将报告与投影平面正交的所有边,即使是从投影平面的视点不可见的边。例如,对于圆环,它将找到内部轮廓和外部轮廓,即使圆环以这样的方式旋转,使得其内部孔从投影平面的视点不可见。要弄清楚哪些边可见,您需要进行某种可见性测试。如果预期用途是用于用户显示,则可以使用使用正交投影矩阵计算的深度缓冲来从投影平面的视点渲染几何体,并进行一些z测试以确定哪些边缘在平面上可见。如果需要精度,则需要执行光线/三角形交叉以确定可见性。

#5

Just to add: A very intuitive way to find edges in a projection is back face culling! Any edge between a culled and non-culled face should be an outline. If you want to hide interior edges, just use the z-buffer. Back face culling is simply the post projection vertex order and very cheap to compute.

添加:在投影中找到边缘的一种非常直观的方法是背面剔除!剔除面和非剔除面之间的任何边缘都应该是轮廓。如果要隐藏内部边缘,只需使用z缓冲区。背面剔除只是后投影顶点顺序,计算起来非常便宜。

#6

Is it simply a matter of projecting the xyz points into x'Y' points on the arbitrary plane and then just doing a convex hull in those coordinates?

是否只是将xyz点投影到任意平面上的x'Y'点然后在这些坐标中做一个凸包?

#1

Start with the rightmost point (the point with the biggest x coordinate)