Registriert: So Jan 15, 2017 18:52 Beiträge: 14
Programmiersprache: Delphi

Dear community,

can I ask for help with intersection of two 3D quads? I have two 3D models in delphi and with this procedure I should get intersection line of both models.

I ask for help at mathematical community but noone reply with valid answer. Maybe it is hard to implement... dunno.

I think that conver both quads into XY plane, than get results in 2D and convert back to 3D will be simple and fast even for models with thousands quads.

Does anyone have some kind of this procedure? Input: 2x quad, Outpus: Array of vectors (0, 1 or 2 vectors).

I tryed it with simple segment X quad intersection for every edge of each quad. But for one quad X quad test I need to use it 8 times and it took much time.

Registriert: So Jan 15, 2017 18:52 Beiträge: 14
Programmiersprache: Delphi

Hello,

I am glad I found someone here who is willing to help. What I need is "fast" QUAD vs QUAD intersection. Result should be zero, 1 point or 2 points (segment).

At this moment I have working solution with multiple calling SEGMENT vs QUAD detection which gives me points I need BUT ... I need to call it 8 times which is time consuming.

For this reason I am try to find better solution. For example this solution should work but I not know how to do it:

1) Rotate first QUAD to XY plane (we need to get Rotation axis and Rotation angle and store it for later use) 2) Use Rotation Matrix on second QUAD (with Rotation axis and angle we got in step 1) 3) Detect where second QUAD intersect XY plane (we should get LINE which lay on XY plane) 4) Compare LINE with first QUAD (both lay on XY plane so we need to use simple 2D intersection here) 5) Apply Reverse Rotation Matrix of results from point 4

... now we should have QUAD vs QUAD intersection.

This should be fastest. Because of simple 2D intersection we should not have problems with "Epsilon" coeficient like in 3D space.

I already have some kinds of line/segment intersection between other basic geometry like line/segment/triangle/quad/polygon. Is I type before, for getting correct results for QUAD vs QUAD intersection I need to use it multiple times which need CPU time. For this reason I think project 3D into 2D (XY plane for example) will be much faster ... and I can use this to different kind of intersection because 2D is much easier.

Registriert: Mo Nov 08, 2010 18:41 Beiträge: 769
Programmiersprache: Gestern

Oh well that's easy than. Just create the helper planes for each line and than do the classic chopping-approach. This way you'll just need a few point-to-plane intersections and that's it. Everything else seems a bit too clunky for me, because you can't optimize and/or scale that well. Plus it's basically the same as your idea, just with all the useless extra removed

Registriert: Mo Nov 08, 2010 18:41 Beiträge: 769
Programmiersprache: Gestern

well i think the best example for all the poly-math thingy would be the GTK-Radiant, cause it's so simple and useful what they did there. A good start would be their windings, which is the basis for all the CSG stuff.

Registriert: Mo Nov 08, 2010 18:41 Beiträge: 769
Programmiersprache: Gestern

Oh well I think you are just a bit confused by the details here. Essentially, any kind of intersection boils down to either point-to-point or point-to-plane distance. Now the trick is pretty simple:

-first you calculate a helper plane for each side of the object "A" -than you calculate the distances between the plane and each point of your second object "B" -if the distances indicate an intersection, they calculate the new points. -if a point of object "B" is SIDE_FRONT or SIDE_ON there's nothing to do. -However if it's SIDE_BACK than there's an intersection and you need to calculate a new point ("mid").

So yeah that means: you first check if both quads are on planes that can intersect, because there's no need to do all the heavy stuff when both quads are on planes with a same / similar normal but different distances to the origin. If they are on planes that can intersect, you would just calculate the new points of intersection with the method I mentioned in order to calculate the lines.

This way you will also cover complicated cases where you would have multiple intersection lines.

Now the beauty of this idea is that it'll work with any convex object.

Do you need particular information about the intersections or do you just want to display them?

If so, how about a very easy but unprecise solution: -Draw the first one into a fbo with a floating point texture (rgb32f or rgba32f) and write the position. -Unbind the buffer/texture, so you can read it. -Now draw the second one, calculate its position in the pixelshader as you did with the first one and compare. -Wheter do a simple distance check, or if you want "more precision" you can check the pixels around with dFdX/dFdY...

This way you will only see the intersections that are not occluded by the geometry though.

_________________ "Pixel, ich bin dein Vater." -Darf Shader

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

Du darfst keine neuen Themen in diesem Forum erstellen. Du darfst keine Antworten zu Themen in diesem Forum erstellen. Du darfst deine Beiträge in diesem Forum nicht ändern. Du darfst deine Beiträge in diesem Forum nicht löschen. Du darfst keine Dateianhänge in diesem Forum erstellen.