algorithm - 基本空间雕刻算法

Question

我有如下图所示的问题。我有点云和由四面体算法生成的网格。我将如何使用该算法雕刻网格？地标是点云吗？

算法伪代码:

for every 3D feature point
 convert it 2D projected coordinates

for every 2D feature point
cast a ray toward the polygons of the mesh 
get intersection point
if zintersection < z of 3D feature point
for ( every triangle vertices )
cull that triangle.

这是 Guru Spektre 提到的算法的后续实现 :)

更新算法代码:

 int i;
        for (i = 0; i < out.numberofpoints; i++)
        {
            Ogre::Vector3 ray_pos = pos; // camera position);
            Ogre::Vector3 ray_dir = (Ogre::Vector3 (out.pointlist[(i*3)], out.pointlist[(3*i)+1], out.pointlist[(3*i)+2]) - pos).normalisedCopy();  // vertex - camea pos ;

            Ogre::Ray ray;
            ray.setOrigin(Ogre::Vector3( ray_pos.x, ray_pos.y, ray_pos.z));
            ray.setDirection(Ogre::Vector3(ray_dir.x, ray_dir.y, ray_dir.z));
            Ogre::Vector3 result;
            unsigned int u1;
            unsigned int u2;
            unsigned int u3;
            bool rayCastResult = RaycastFromPoint(ray.getOrigin(), ray.getDirection(), result, u1, u2, u3);

            if ( rayCastResult )
            {
                Ogre::Vector3 targetVertex(out.pointlist[(i*3)], out.pointlist[(3*i)+1], out.pointlist[(3*i)+2]);
                float distanceTargetFocus = targetVertex.squaredDistance(pos);
                float distanceIntersectionFocus = result.squaredDistance(pos);
                if(abs(distanceTargetFocus) >= abs(distanceIntersectionFocus))
                {
                    if ( u1 != -1 && u2 != -1 && u3 != -1)
                    {
                        std::cout << "Remove index "<< "u1 ==> " <<u1 << "u2 ==>"<<u2<<"u3 ==> "<<u3<< std::endl;
                        updatedIndices.erase(updatedIndices.begin()+ u1);
                        updatedIndices.erase(updatedIndices.begin()+ u2);
                        updatedIndices.erase(updatedIndices.begin()+ u3);

                    }
                }
            }

            }


            if ( updatedIndices.size() <= out.numberoftrifaces)
            {
                std::cout << "current face list===> "<< out.numberoftrifaces << std::endl;

                std::cout << "deleted face list===> "<< updatedIndices.size() << std::endl;
                manual->begin("Pointcloud", Ogre::RenderOperation::OT_TRIANGLE_LIST);

                for (int n = 0; n < out.numberofpoints; n++)
                {
                    Ogre::Vector3 vertexTransformed = Ogre::Vector3( out.pointlist[3*n+0], out.pointlist[3*n+1], out.pointlist[3*n+2]) - mReferencePoint;
                    vertexTransformed *=1000.0 ;
                    vertexTransformed = mDeltaYaw * vertexTransformed;

                    manual->position(vertexTransformed);

                }

                for (int n = 0 ; n < updatedIndices.size(); n++)
                {
                     int n0 = updatedIndices[n+0];
                     int n1 = updatedIndices[n+1];
                     int n2 = updatedIndices[n+2];

                    if ( n0 < 0 || n1 <0 || n2 <0 )
                    {
                        std::cout<<"negative indices"<<std::endl;
                        break;
                    }
                    manual->triangle(n0, n1, n2);

                }

                manual->end();

跟进算法:

我现在有两个版本，一个是三角版，一个是雕刻版。

它不是表面网格。 这是两个文件 http://www.mediafire.com/file/cczw49ja257mnzr/ahmed_non_triangulated.obj http://www.mediafire.com/file/cczw49ja257mnzr/ahmed_triangulated.obj

Answer 1

我是这样看的:

所以你从已知 matrix 的相机中得到了图像以及 FOV 和焦距。

由此您可以知道焦点的确切位置以及图像投影到相机芯片的位置(Z_near 平面)。所以任何一个顶点，它对应的像素点和焦点都在同一条直线上。

因此对于从焦点到点云的每个可见顶点的每个 View cas 射线。并在击中包含目标顶点的面之前测试网格的任何面是否击中。如果是，请将其移除，因为它会阻挡可见性。

Landmark 在此上下文中只是对应于点云中的vertex 的特征点。它可以是任何可检测的(强度、颜色、图案的变化)，通常 SIFT/SURF 用于此。您应该已经找到它们，因为这是点云生成的输入。如果不是，您可以查看每个顶点对应的像素并测试背景颜色。

不确定在没有输入图像的情况下如何执行此操作。为此，您需要决定从哪个侧面/ View 可以看到哪个顶点。可能以某种方式形成附近的顶点(例如使用顶点密度点或与平面的对应......)或者算法以某种方式改变以在网格内找到未使用的顶点。

要转换光线，请执行以下操作:

ray_pos=tm_eye*vec4(imgx/aspect,imgy,0.0,1.0);
ray_dir=ray_pos-tm_eye*vec4(0.0,0.0,-focal_length,1.0);

哪里tm_eye是相机直接变换矩阵，imgx,imgy是归一化为 <-1,+1> 的图像中的二维像素位置其中 (0,0)是图像的中间。 focal_length决定相机的FOV，宽高比是图像分辨率的比值image_ys/image_xs

射线三角形相交方程可以在这里找到:

• Reflection and refraction impossible without recursive ray tracing?

如果我提取它:

vec3 v0,v1,v2; // input triangle vertexes
vec3 e1,e2,n,p,q,r;
float t,u,v,det,idet;
//compute ray triangle intersection
e1=v1-v0;
e2=v2-v0;
// Calculate planes normal vector
p=cross(ray[i0].dir,e2);
det=dot(e1,p);
// Ray is parallel to plane
if (abs(det)<1e-8) no intersection;
idet=1.0/det;
r=ray[i0].pos-v0;
u=dot(r,p)*idet;
if ((u<0.0)||(u>1.0)) no intersection;
q=cross(r,e1);
v=dot(ray[i0].dir,q)*idet;
if ((v<0.0)||(u+v>1.0)) no intersection;
t=dot(e2,q)*idet;
if ((t>_zero)&&((t<=tt))  // tt is distance to target vertex
    {
    // intersection
    }              

跟进:

在标准化图像之间移动 (imgx,imgy)和原始图像 (rawx,rawy)尺寸图像的坐标 (imgxs,imgys)其中 (0,0)是左上角，(imgxs-1,imgys-1)是你需要的右下角:

imgx = (2.0*rawx / (imgxs-1)) - 1.0
imgy = 1.0 - (2.0*rawy / (imgys-1))

rawx = (imgx + 1.0)*(imgxs-1)/2.0
rawy = (1.0 - imgy)*(imgys-1)/2.0

[进度更新 1]

我终于到了可以编译示例测试输入数据的地步，以便开始(因为您根本无法共享有效数据):

我用硬编码的表格网格(灰色)和点云(浅绿色)和简单的相机控制创建了一个小应用程序。我可以在哪里保存任意数量的 View (屏幕截图 + 相机直接矩阵)。当加载回来时，它与网格本身对齐(黄色光线穿过图像中的水点，也穿过桌面网格)。蓝线是从相机焦点转换到它的角落。这将模拟您获得的输入。应用程序的第二部分将仅使用这些图像和点云矩阵(不再有网格表面)四边形化它(已经完成)现在只需通过每个 View 中的每个地标转换光线(浅绿色点)并删除目标顶点之前的所有四边形在 pointcloud 中被击中(这东西甚至还没有开始但可能在周末)...最后只存储表面三角形(很容易只使用所有只使用过一次的三角形也已经完成除了保存部分但是从这很容易......)。

[进度更新2]

我添加了地标检测和点云匹配

如您所见，仅转换有效光线(那些在图像上可见的光线)，因此点云上的某些点不会转换光线(奇异的浅绿色点))。所以现在只缺少从列表中删除的射线/三角形交点和四面体......