🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Back to General and Gameplay Programming

Ray to Octree Intersection for boolean geometry

AhmedSaleh · 2021-02-24T07:37:10

Hi, I'm trying to do boolean geometry that I have two meshes and would like to compute the intersection between them. So I construct an octree from mesh A, and I check the vertices from mesh B against the octants, if there is an intersection, check the octant triangles for intersection, then I add the triangles, construct a mesh. auto intersected_octant_faces = mn::buf_new<musa::Triangle>(); std::stack < cg::Octant *> stack; stack.push(octree_sphere.root); for (size_t i = 0; i < tri_mesh_cube.vertices.count; i++) { while (!stack.empty()) { cg::Octant* node = stack.top(); if (!node) break; stack.pop(); musa::Ray ray; ray.origin = { tri_mesh_cube.vertices[i] }; ray.dir = { 1,0,0 }; musa::Intersection_Points pts = {}; pts = musa::ray_box_intersection(ray, node->region); if (pts.count >= 1) { musa::Intersection_Points t = {}; auto vertices = node->faces; for (size_t j = 0; j < vertices.count; j += 3) { musa::Triangle tri{ vertices[j], vertices[j + 1], vertices[j + 2] }; t = musa::ray_triangle_intersection(ray, tri); if (t.count == 1) { mn::buf_push(intersected_octant_faces, tri); } } } for (auto& n : node->octants) { stack.push(n); } } } Right now I get just two faces as shown in the figure and not sure where is the problem.

General and Gameplay Programming Programming

Started by AhmedSaleh February 19, 2021 09:10 PM

48 comments, last by JoeJ 3 years, 4 months ago

AhmedSaleh

192

Author

February 22, 2021 06:30 PM

@joej

How would tesselation work ? the line segments are in 3D… all triangulation algorithms are in 2D.. would you elaborate more ?

Game Programming is the process of converting dead pictures to live ones .

JoeJ

4,266

February 22, 2021 06:31 PM

For a first step, it would be nice to visualize the intersection segments as lines. You can verify if they whole intersection path shows up already.

AhmedSaleh

192

Author

February 22, 2021 06:32 PM

@Joejl

Yes and then how would I tesselate them ?

Game Programming is the process of converting dead pictures to live ones .

JoeJ

4,266

February 22, 2021 06:40 PM

AhmedSaleh said:
How would tesselation work ? the line segments are in 3D… all triangulation algorithms are in 2D.. would you elaborate more ?

Any triangle is flat, so you could project it to the normal plane to turn it 2D.

Though, personally i stick at 3D - working in 2D does not make the problem easier.

Thinking about it, i have this idea:

Every side of the segment has to connect to a triangle vertex.

Every edge of the triangle has to connect to one vertex of the segment.

… hardest part seems to avoid edge crossings…

JoeJ

4,266

February 22, 2021 06:49 PM

…better idea, maybe:

Every side of the line segment has to connect to one triangle edge to form a quad (which we triangulate later).
We pick the triangle edge which is the most contained in the half space defined by the segment.

picture shows how to find the best edge for the blue quad.

One edge remains unconnected, so we connect it to the line end which connects to two different edges. We get the final orange triangle.

Seems nice, but i'm not sure if it works for all cases.

AhmedSaleh

192

Author

February 22, 2021 06:52 PM

@joej

Looks very complicated. I surrender ? Thanks for your help.

I got the intersection, but can't get the inside outside or how to tesselate at all.

Game Programming is the process of converting dead pictures to live ones .

AhmedSaleh

192

Author

February 22, 2021 07:56 PM

@joej

I got it working at least the blue triangles are drawn now, seems the triangle to triangle intersect check was a flaw

but I get broken rectangles behind

current code, please check it

while (!stack.empty())
		{
			cg::Octant* node = stack.top();
			stack.pop();

			if (box_box_intersect(musa::triangle_bounding_box(triB), node->region))
			{
				auto vertices = node->faces;

				for (size_t a = 0; a < vertices.count; a += 3)
				{
					musa::Triangle triA{ vertices[a], vertices[a + 1], vertices[a + 2] };

					musa::Intersection_Segments sgs = musa::triangle_triangle_coplanar_intersection(triA, triB);
					
					mn::buf_push(self->modelIntersection.points, sgs.segments[0].start);

					mn::buf_push(self->modelIntersection.points, sgs.segments[0].end);

					mn::buf_push(self->modelIntersection.points, triB.p0);

					mn::buf_push(self->modelIntersection.points, triB.p1);

					mn::buf_push(self->modelIntersection.points, triB.p2);

					

				}

				for (auto& n : node->octants)
				{
					if (n == nullptr)
						continue;
					stack.push(n);
				}
			}
		}

Game Programming is the process of converting dead pictures to live ones .

AhmedSaleh

192

Author

February 22, 2021 08:05 PM

I fomulated and I get this now

while (!stack.empty())
		{
			cg::Octant* node = stack.top();
			stack.pop();

			if (box_box_intersect(musa::triangle_bounding_box(triB), node->region))
			{
				auto vertices = node->faces;

				mn::buf_push(self->modelIntersection.points, triB.p0);

				mn::buf_push(self->modelIntersection.points, triB.p1);

				mn::buf_push(self->modelIntersection.points, triB.p2);

				for (size_t a = 0; a < vertices.count; a += 3)
				{
					musa::Triangle triA{ vertices[a], vertices[a + 1], vertices[a + 2] };

					musa::Intersection_Segments sgs = musa::triangle_triangle_intersection(triA, triB);

					mn::buf_push(self->modelIntersection.points, sgs.segments[0].start);
					mn::buf_push(self->modelIntersection.points, sgs.segments[0].end);
				}

				for (auto& n : node->octants)
				{
					if (n == nullptr)
						continue;
					stack.push(n);
				}
			}

Game Programming is the process of converting dead pictures to live ones .

AhmedSaleh

192

Author

February 22, 2021 08:59 PM

Now I get it working, I think I need the in/out side test…

I'm doing the intersection into two iterations..

	auto tri_mesh_a = cg::trimesh_from_indexed_mesh(sphere_indexed_mesh);
	auto tri_mesh_b = cg::trimesh_from_indexed_mesh(cube_indexed_mesh);
	auto octree_a = cg::octree_from_mesh(tri_mesh_a);
	auto octree_b = cg::octree_from_mesh(tri_mesh_b);

	std::stack < cg::Octant*> stack;
	int num_indices = 0;
	std::vector<musa::Intersection_Points> segm;
	std::vector<std::vector<Point_>> polygon;
	for (size_t i = 0; i < tri_mesh_a.vertices.count; i+=3)
	{
		musa::Triangle triB{ tri_mesh_a.vertices[i], tri_mesh_a.vertices[i + 1], tri_mesh_a.vertices[i + 2] };
		stack.push(octree_b.root);

		while (!stack.empty())
		{
			cg::Octant* node = stack.top();
			stack.pop();
		
			if (box_box_intersect(musa::triangle_bounding_box(triB), node->region))
			{
				auto vertices = node->faces;

				mn::buf_push(self->modelIntersection.points, triB.p0);
			 

				mn::buf_push(self->modelIntersection.indices, num_indices++);
				mn::buf_push(self->modelIntersection.points, triB.p1);

				mn::buf_push(self->modelIntersection.indices, num_indices++);
				mn::buf_push(self->modelIntersection.points, triB.p2);

				mn::buf_push(self->modelIntersection.indices, num_indices++);
			

				for (auto& n : node->octants)
				{
					if (n == nullptr)
						continue;
					stack.push(n);
				}
			}
		}
	}



	for (size_t i = 0; i < tri_mesh_b.vertices.count; i += 3)
	{
		musa::Triangle triB{ tri_mesh_b.vertices[i], tri_mesh_b.vertices[i + 1], tri_mesh_b.vertices[i + 2] };
		stack.push(octree_a.root);

		while (!stack.empty())
		{
			cg::Octant* node = stack.top();
			stack.pop();

			if (box_box_intersect(musa::triangle_bounding_box(triB), node->region))
			{
				auto vertices = node->faces;
			
				for (size_t a = 0; a < vertices.count; a += 3)
				{
					musa::Triangle triA{ vertices[a], vertices[a + 1], vertices[a + 2] };
					if (musa::triangle_triangle_intersection_check(triA, triB))
					{
						mn::buf_push(self->modelIntersection.points, triB.p0);


						mn::buf_push(self->modelIntersection.indices, num_indices++);
						mn::buf_push(self->modelIntersection.points, triB.p1);

						mn::buf_push(self->modelIntersection.indices, num_indices++);
						mn::buf_push(self->modelIntersection.points, triB.p2);

						mn::buf_push(self->modelIntersection.indices, num_indices++);
					}
				}


				for (auto& n : node->octants)
				{
					if (n == nullptr)
						continue;
					stack.push(n);
				}
			}
		}
	}