基本space雕刻算法

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

我是这样看的：

所以你从已知和 FOV 和焦距的相机获得了图像。

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

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

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

不确定在没有输入图像的情况下要如何执行此操作。为此，您需要决定从哪个 side/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]

我终于到了可以编译示例测试输入数据的地步，甚至可以开始（因为您根本无法共享有效数据）：

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

[进度更新2]

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

如您所见，仅投射有效光线（那些在图像上可见的光线），因此点云上的某些点不会投射光线（奇异的浅绿色点））。所以现在只缺少 ray/triangle 交集和从列表中删除的四面体...

基本space雕刻算法

Basic space carving algorithm

algorithm

graphics

3d

computer-vision

3d-reconstruction