Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I think this can be fairly easily solved by slicing the object up, removing the unwanted section, and then gluing the leftover pieces back together by merging faces.</p> <p>Assuming you are modelling your object as a fully-linked graph</p> <ul> <li>A list of vertices, each with a list of edges</li> <li>A list of edges, each with references to two vertices and two faces</li> <li>A list of faces, each with a list of edges</li> </ul> <p>As long as you are careful in maintaining and manipulating this graph, it holds all the information needed to quickly cut and merge your objects.</p> <p>You can use the algorithm described in <a href="https://stackoverflow.com/questions/4646738/detecting-arbitrary-shapes/5105357#5105357">this answer</a> to compute the new face resulting from the cut.</p> <p>So: your inputs to the algorithm are a list of cutting planes and a list of objects - initially there is only one. For each cutting plane, slice each object in the list object into two and put them back into the list. The two faces that are added (one on each of the new objects) should keep a reference to the cutting plane that produced them. For faces that are cut in half by a plane, remember that the two new faces produced should inherit this reference if it exists. The new objects should keep a record of which side of the plane they lie (just a boolean meaning 'keep' or 'discard')- these records should also be maintained as the objects are further subdivided.</p> <p>Once all the cuts have been made, you'll have a list of objects, each of which has a list of records detailing on which side of the cutting planes they lie. Find the objects where all of those records are 'discard' and throw them away.</p> <p>We now have to stick the objects back together.</p> <p>Start by trivially merging the object graphs - simply combine all of the vertex, edge and face lists into one object. We now examine the two faces that were created by the same cutting plane:</p> <ul> <li>If the two faces are identical (i.e.: they share the same set of vertices) then both faces and all associated edges can be removed.</li> <li>If the vertex set of one face is larger than the other, then remove the smaller face and all shared edges.</li> </ul> <p>You should now have a merged object, but with some extraneous vertices. Simple iterate through the vertices and remove those that only have two associated edges.</p> <p>Here's an example of how the cutting would work:</p> <pre><code> : a---1-:---b | : | 2 X : 3 | : | | : | c---4-:---d : :s </code></pre> <p>We start with one object (? denotes some edge or face not shown):</p> <pre><code>verts: a:1,2,? b:1,3,? c:2,4,? d:3,4,? edges: 1:a,b X,? 2:a,c X,? 3:b,d X,? 4:c,d X,? faces: X:1,2,3,4 ?:... </code></pre> <p>When we cut with the plane s, we end up with two objects:</p> <pre><code>a--1--e-7-b | | | 2 X 5 Y 3 | 6 | | | | c--4--f-8-d verts: verts: a:1,2,? e:1,5,6,7 e:1,5,6,7 b:3,7,? c:2,4,? d:3,8,? f:4,5,6,8 f:4,5,6,8 edges: edges: 1:a,e X,? 3:b,d Y,? 2:a,c X,? 6:e,f Y,W 4:c,f X,? 7:e,b Y,? 5:e,f X,V 8:f,d Y,? faces: faces: X:1,2,3,4 Y:3,6,7,8 V:5,... W:6,... ?:... ?:... </code></pre> <p>We've added vertices e and f, edges 5 and 6, and faces V and W. Note that edges 5 and 6 are distinct objects, sharing the same vertices but between different faces.</p> <p>When we come to merge these two objects back together, we first trivially merge the two object graphs:</p> <pre><code>verts: a:1,2,? b:3,7,? c:2,4,? d:3,8,? e:1,5,6,7 f:4,5,6,8 edges: 1:a,e X,? 2:a,c X,? 3:b,d Y,? 4:c,f X,? 5:e,f X,V 6:e,f Y,W 7:e,b Y,? 8:f,d Y,? faces: X:1,2,3,4 Y:3,6,7,8 V:5,... W:6,... ?:... </code></pre> <p>We can see that faces V and W were produced by the same cutting plane and have the same vertex set, and so they can be removed along with the associated edges. The two non-removed faces associated with a pair of coincident edges are merged.</p> <pre><code>a--1--e-7-b | | 2 X 3 | | | | c--4--f-8-d verts: a:1,2,? b:3,7,? c:2,4,? d:3,8,? e:1,7 f:4,8 edges: 1:a,e X,? 2:a,c X,? 3:b,d X,? 4:c,f X,? 7:e,b X,? 8:f,d X,? faces: X:1,2,3,4,7,8 ?:... </code></pre> <p>We can then remove the vertices with only two associated edges, and merge those edges:</p> <pre><code>verts: a:1,2,? b:1,3,? c:2,4,? d:3,8,? edges: 1:a,e X,? 2:a,c X,? 3:b,d Y,? 4:c,d X,? faces: X:1,2,3,4 Y:3,6,7,8 ?:... </code></pre> <p>What about merging these objects?</p> <pre><code>a--1--e | 5 2 X g-3-b | 6 | | 9 Y 7 c--4--f-8-d verts: verts: a:1,2,? g:3,5,6,? e:1,5,? b:3,7,? c:2,4,? d:7,8,? f:4,6,8,9,? f:4,6,8,9,? edges: edges: 1:a,e X,? 3:b,g Y,? 2:a,c X,? 9:f,g Y,W 4:c,f X,? 7:b,d Y,? 5:e,g X,V,? 8:f,d Y,? 6:f,g X,V faces: faces: X:1,2,4,5,6 Y:3,7,8,9 V:5,6,... W:9,... ?:... ?:... </code></pre> <p>We merge:</p> <pre><code>verts: a:1,2,? b:3,7,? e:1,5,? c:2,4,? d:7,8,? f:4,6,8,9,? g:3,5,6,9,? edges: 1:a,e X,? 2:a,c X,? 3:b,g Y,? 4:c,f X,? 5:e,g X,V,? 6:f,g X,V 7:b,d Y,? 8:f,d Y,? 9:f,g Y,W faces: X:1,2,4,5,6 Y:3,6,7,8 V:5,6,... W:9,... ?:... </code></pre> <p>and examine faces V and W, as they have been created by the same cut plane. This time their vertex sets are different. Remove the smaller face. In the two faces, find the edges that have the same vertices and remove them:</p> <pre><code>a--1--e | 5 2 X g-3-b | | | 7 c--4--f-8-d verts: a:1,2,? b:3,7,? e:1,5,? c:2,4,? d:7,8,? f:4,8 g:3,5,? edges: 1:a,e X,? 2:a,c X,? 3:b,g X,? 4:c,f X,? 5:e,g X,V,? 7:b,d X,? 8:f,d X,? faces: X:1,2,3,4,5,7,8 V:5,... ?:... </code></pre> <p>We can now remove the useless vertices with only two incident edges:</p> <pre><code>a--1--e | 5 2 X g-3-b | | | 7 c----4----d verts: a:1,2,? b:3,7,? e:1,5,? c:2,4,? d:4,7,? g:3,5,? edges: 1:a,e X,? 2:a,c X,? 3:b,g Y,? 4:c,d X,? 5:e,g X,? 7:b,d X,? faces: X:1,2,3,4,5,7 V:5,... ?:... </code></pre> <p>Phew! Hope this helps...</p>
    singulars
    1. This table or related slice is empty.
    1. POIntersection of two section planes
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USryanm
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POIntersection of two section planes
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COi ended using another solution, but your suggestion helped me; thanks!
      singulars
      1. PO
      1. USseb
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload