Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki

Aktuelle Zeit: Sa Sep 23, 2017 22:48

Foren-Übersicht » English » English Programming Forum
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 12 Beiträge ] 
Autor Nachricht
 Betreff des Beitrags: Intersection segment of two 3D quads
BeitragVerfasst: Mi Mär 15, 2017 10:18 
Offline
DGL Member

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.

Thank you for help.


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mi Mär 15, 2017 13:58 
Offline
DGL Member
Benutzeravatar

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

you seem a bit unclear to me, so please add a more detailed description with images.

In general: 3D intersections are very easy as well, so don't worry about the details yet :)

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mi Mär 15, 2017 15:02 
Offline
DGL Member

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.

Looks easy but I fail in first point :(

Any tips?
Thanks!


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mi Mär 15, 2017 17:57 
Offline
DGL Member

Registriert: Mo Nov 09, 2009 12:01
Beiträge: 196
3D triangle-ray-intersection !?
http://paulbourke.net/geometry/pointlineplane/


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Mär 16, 2017 07:12 
Offline
DGL Member

Registriert: So Jan 15, 2017 18:52
Beiträge: 14
Programmiersprache: Delphi
Jens01 hat geschrieben:
3D triangle-ray-intersection !?
http://paulbourke.net/geometry/pointlineplane/


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.


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Mär 16, 2017 08:28 
Offline
DGL Member
Benutzeravatar

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 :)

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Mär 16, 2017 08:51 
Offline
DGL Member

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


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Mär 16, 2017 10:22 
Offline
DGL Member
Benutzeravatar

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.


https://github.com/TTimo/GtkRadiant/blo ... inding.cpp

The function you would be looking for is called "Winding_Clip"

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Mär 16, 2017 11:07 
Offline
DGL Member

Registriert: So Jan 15, 2017 18:52
Beiträge: 14
Programmiersprache: Delphi
I think I not understand. Clip winding ... is something different.


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Mär 16, 2017 12:41 
Offline
DGL Member
Benutzeravatar

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.

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Mär 16, 2017 14:04 
Offline
DGL Member

Registriert: So Jan 15, 2017 18:52
Beiträge: 14
Programmiersprache: Delphi
Thank you for explain...
I do not understand it. This method not looks well for me. I think i will go with 3D -> 2D.


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Di Mär 28, 2017 19:30 
Offline
DGL Member

Registriert: Fr Mai 11, 2012 13:25
Beiträge: 194
Programmiersprache: c++, c, JavaScript
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.


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 12 Beiträge ] 
Foren-Übersicht » English » English Programming Forum


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 0 Gäste


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.

Suche nach:
Gehe zu:  
cron
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.030s | 16 Queries | GZIP : On ]