8
\$\begingroup\$

I am working with a game engine, and my task is to add code for simulating fracture of rigid meshes.

Right now I'm only working on breaking a cube.

I am using Voronoi's algorithm to make a (realistic)fractured shard and I am using the half-plane method to generate a Voronoi cell.

to find the closest(encircled in red) points around the Voronoi(purple point)

Now the way I do this is for every seed point, I make planes that are perpendicular bisector planes(the straight black lines in the image) with rest of the seed points and I calculate the intersections of all these planes to give me distinct points(all the orange dots).

I've gotten this far.

Out of all these calculated intersection points, I only need the ones that are closest and enclosing the seed point(the points encircled in red) and I need to discard all the rest.

Information that I have :

1) Plane equations of all planes(defined by normalized normal vectors and their distance from origin)

2) Points of intersection(that I've calculated)

Can anybody help me find out how I can find the points encircled in red?

Improve this question
\$\endgroup\$
1
  • \$\begingroup\$ No answer, but that's an interesting problem! \$\endgroup\$
    – Tim Holt
    Aug 18, 2014 at 16:11

2 Answers 2

Reset to default
4
\$\begingroup\$

Following the half-plane method, you'll have found the line segments to every other point and the perpendicular bisectors of each of those

step 1: line segments step 2: perpendicular bisectors

which you then intersected to find potential vertices of the Voronoi cell.

Now, you want to exclude the ones that intersect any of the "distant" half-planes formed by the bisectors.

Two matching intersections, one unmatching

I coloured the "distant" half-planes translucent blue for clarity.

Here, the two circled red points pass the test: They're not within any half-plane. The uncircled red point does not pass, as it's within the half-plane formed toward the point in the top-right.

This effectively means testing whether each point is on the other side of every bisector line (relative to the Voronoi site) and discarding those that are. (Beware of rounding errors.)

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ This answer was very useful. To check on if both points lie on the same side of the plane I substituted the vectors in plane equations and looked out for their signs. If both were positive/negative, then they are on the same side. Else they are on opposite side. This works! My code seems to be producing correct vertices for Voronoi shards at last! \$\endgroup\$
    – nilspin
    Aug 20, 2014 at 20:37
  • \$\begingroup\$ what program did you use to generate those images in your answer? \$\endgroup\$
    – nilspin
    Jul 25, 2015 at 17:09
  • \$\begingroup\$ @nilspin Inkscape. \$\endgroup\$
    – Anko
    Jul 25, 2015 at 18:59
3
\$\begingroup\$

You may simply iterate over edges and filter out all vertices that are not in same half-plane with point of interest.

As optimisation, iterate from nearest edges to farthest. I think you may even filter vertices while generating slices.

It is like slicing pie with endless knife, until only small piece left with cherry on it. If you like analogies. Just cut and see which part will be taken and which will be discarded.

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .