My other thought was to do the same thing, but have the second volume slightly overlapping, and at the collision point testing to see if it was inside any other negative volumes, and if so trying again but ignoring the first collision object it found (and keeping tabs on which ones it is ignoring). This seems highly inefficient.
So I was wondering if anyone had any suggestions, either of solutions or links to places where I can learn about the proper way to deal with boolean volumes/ray collisions (although the cylinder surfaces definitely need to be a pure curve)
Thanks!
[Edited by - Xgkkp on September 1, 2006 3:22:48 PM]
Calculating ray intersections inside a boolean constructed volume
Author
I am constructing a simulation of particles bouncing around inside a 'container', but am having trouble calculating the next point of impact. Bear with me a minute, as I am not sure how best to explain, or ask the question.
I have the container defined as a set of 'negative volume' shapes (that is, where they are defined is empty space, and everything else is assumed to be solid - at the moment, I need not worry about positive volumes in the same space). As an example, the simple case I am working with is a large cylinder in one place, and a smaller cylinder joined and underneath for the entrance tube. I want to be able to take a position inside the structure and a vector, and calculate the point that it would next intersect with a wall.
I can do it easily enough with just the one cylinder with some basic maths, but the problem comes when I want the second to 'hollow out' a pit in the bottom. My initial idea was to iterate through all objects, try casting the ray, and taking the shortest calculated distance as the collision point (taking into account the fact that if it starts outside of a volume, it can pass through the outer walls and hit on the other inside wall). However, this obviously doesn't work in my case because the shortest collision distance happens to be the boundary between two 'negative volumes'. This is shown in the diagram below.
My other thought was to do the same thing, but have the second volume slightly overlapping, and at the collision point testing to see if it was inside any other negative volumes, and if so trying again but ignoring the first collision object it found (and keeping tabs on which ones it is ignoring). This seems highly inefficient.
So I was wondering if anyone had any suggestions, either of solutions or links to places where I can learn about the proper way to deal with boolean volumes/ray collisions (although the cylinder surfaces definitely need to be a pure curve)
Thanks!
[Edited by - Xgkkp on September 1, 2006 3:22:48 PM]
My other thought was to do the same thing, but have the second volume slightly overlapping, and at the collision point testing to see if it was inside any other negative volumes, and if so trying again but ignoring the first collision object it found (and keeping tabs on which ones it is ignoring). This seems highly inefficient.
So I was wondering if anyone had any suggestions, either of solutions or links to places where I can learn about the proper way to deal with boolean volumes/ray collisions (although the cylinder surfaces definitely need to be a pure curve)
Thanks!
[Edited by - Xgkkp on September 1, 2006 3:22:48 PM]
I see two fundamental approaches. Think about your model definition in terms of a constructive solid geometry (CSG) tree. You have a solid block world from which you are subtracting a list of empty bodies.
So, the first approach (a potentially difficult one) would be to convert your CSG tree into a boundary representation (B-rep), e.g., compute the geometric intersections amongst all the bodies, split objects along intersection boundaries, then remove faces that are coincident with another face or embedded inside another contributing body, etc. So that you're left with a set of clean boundaries, with no embedded faces. The B-rep geometry for your example case would look something like this (sorry for ASCII art):
Now, you would not get the false intersection because that embedded surface is not in the B-rep geometry you are ray tracing against!
To do the B-rep conversion can be difficult. Conceptually its easy, but there's a bunch of annoying bits, for example what if one face touches another face on edge, and that common edge fits entirely in the middle of the face...you'd have to subdivide the face in order to insert points that match the endpoint of the edge, then tessellate the face with a constraint that the intersection edge be part of the resulting tessellation. It can be severely messy. You can do this using BSP trees, but for complex worlds that can lead to a bloat of vertices/edges/faces that becomes unmanageable. (If your world is similar complexity to some of the Quake/Unreal style interior levels, then the BSP approach is probably manageable if your code is solid...)
So, the other approach is simpler, and doesn't require the B-rep conversion. The idea is that at each intersection point, keep track of what object you are moving into and out of. For that bad intersection point you would have two points actually. One to leave the large box, and a coincident point to enter the small box. When you have two coincident points, if the two objects (the one you are leaving and the one your are entering) are the same (e.g., both empty space or both solid space), then you know to skip that point, filter it out because its an embedded point.
This approach also works if one object is completely embedded inside another. Consider the case where the small box is shifted upwards and is inside the large box partially. Then, you'd find an intersection to enter the small box without a matching point to exit the large box. That too is a point to skip if the types (filled or empty) are the same.
The rule set is simple. Skip points that come in pairs between objects of the same type (empty or filled). And skip points that are embedded within another object of the same type. Keep all other points!
So, the first approach (a potentially difficult one) would be to convert your CSG tree into a boundary representation (B-rep), e.g., compute the geometric intersections amongst all the bodies, split objects along intersection boundaries, then remove faces that are coincident with another face or embedded inside another contributing body, etc. So that you're left with a set of clean boundaries, with no embedded faces. The B-rep geometry for your example case would look something like this (sorry for ASCII art):
|------------------------------------------------|| || || || || ||-------------------------------| |---| | | | | | | --------------Now, you would not get the false intersection because that embedded surface is not in the B-rep geometry you are ray tracing against!
To do the B-rep conversion can be difficult. Conceptually its easy, but there's a bunch of annoying bits, for example what if one face touches another face on edge, and that common edge fits entirely in the middle of the face...you'd have to subdivide the face in order to insert points that match the endpoint of the edge, then tessellate the face with a constraint that the intersection edge be part of the resulting tessellation. It can be severely messy. You can do this using BSP trees, but for complex worlds that can lead to a bloat of vertices/edges/faces that becomes unmanageable. (If your world is similar complexity to some of the Quake/Unreal style interior levels, then the BSP approach is probably manageable if your code is solid...)
So, the other approach is simpler, and doesn't require the B-rep conversion. The idea is that at each intersection point, keep track of what object you are moving into and out of. For that bad intersection point you would have two points actually. One to leave the large box, and a coincident point to enter the small box. When you have two coincident points, if the two objects (the one you are leaving and the one your are entering) are the same (e.g., both empty space or both solid space), then you know to skip that point, filter it out because its an embedded point.
This approach also works if one object is completely embedded inside another. Consider the case where the small box is shifted upwards and is inside the large box partially. Then, you'd find an intersection to enter the small box without a matching point to exit the large box. That too is a point to skip if the types (filled or empty) are the same.
The rule set is simple. Skip points that come in pairs between objects of the same type (empty or filled). And skip points that are embedded within another object of the same type. Keep all other points!
Author
Quote:Original post by grhodes_at_work
So, the other approach is simpler, and doesn't require the B-rep conversion. The idea is that at each intersection point, keep track of what object you are moving into and out of. For that bad intersection point you would have two points actually. One to leave the large box, and a coincident point to enter the small box. When you have two coincident points, if the two objects (the one you are leaving and the one your are entering) are the same (e.g., both empty space or both solid space), then you know to skip that point, filter it out because its an embedded point.
This approach also works if one object is completely embedded inside another. Consider the case where the small box is shifted upwards and is inside the large box partially. Then, you'd find an intersection to enter the small box without a matching point to exit the large box. That too is a point to skip if the types (filled or empty) are the same.
The rule set is simple. Skip points that come in pairs between objects of the same type (empty or filled). And skip points that are embedded within another object of the same type. Keep all other points!
This second approach definitely sounds the best - I'm not actually building a complicated game world, and it probably wouldn't get much more complicated than this (a few volumes) - it's a physical simulation. Also I wanted to avoid going the faces/subdivided surfaces route because I need purely curved surfaces, and I'm even less sure how to treat them in that case (or even if it is possible to accurately treat subdivision of curved surfaces).
So; you are suggesting that I would do something like the following:
- Collide on all surfaces regardless of coming from inside or outside the object volume
- Calculate collision points with every object, then sort them into distance
- Test each collision point, and throw it out if:
...1. It is inside a seperate, 'negative' volume
...2. It is in a 'pair' of two collisions at the same point (wouldn't this be covered by 1?)
- Have a 'safety' routine to select the last point anyway if it is the last detected collision (which would be, for instance, two volume faces occupying the same position)
This is how I understand it, I don't quite get what you mean by tracking leaving and entering each object.. because surely you would run into trouble on that in cases where you exist in multiple objects?
Also, do you have any good links where I can find out about ray-object intersection formulae/an introduction guide to it? I'm reading through a few things on google, but was wondering if there was a particularly recommended guide. My maths is strong, but I've never really covered the topic before.
You've got the basics....intersect with everything and sort by distance, then filter based on the rules. That is exactly what I meant.
A point that is part of a pair isn't necessarily the same as a point inside another negative volume since it really is on the boundary of two objects. Containment tests are notorious for returning incorrect results close to the boundary, so I don't think you can rely on containment working (but see works by Christer Ericson on how to do this robustly).
The basic idea of my filters is that they are rules to skip an intersection point that does not represent a change of material, e.g., if you hit a point that is at a boundary of empty air while you are already in empty air, you don't care about that point. If you hit a point inside a solid while you are already inside a solid, you don't care about that point. You only care about hit points that occur when the ray moves into a different material, air to solid or solid to air. Tracking entries and exits as you march along the ray is simply a way to avoid having to do containment tests, which can potentially save on computation time and avoid some robustness issues. And if you follow the two rules, I don't believe you'll have problems with being inside two overlapping objects at a given point.
For a really nice reference on collisions in general, I'd highly recommend Christer Ericson's book, "Real-time Collision Detection."
A point that is part of a pair isn't necessarily the same as a point inside another negative volume since it really is on the boundary of two objects. Containment tests are notorious for returning incorrect results close to the boundary, so I don't think you can rely on containment working (but see works by Christer Ericson on how to do this robustly).
The basic idea of my filters is that they are rules to skip an intersection point that does not represent a change of material, e.g., if you hit a point that is at a boundary of empty air while you are already in empty air, you don't care about that point. If you hit a point inside a solid while you are already inside a solid, you don't care about that point. You only care about hit points that occur when the ray moves into a different material, air to solid or solid to air. Tracking entries and exits as you march along the ray is simply a way to avoid having to do containment tests, which can potentially save on computation time and avoid some robustness issues. And if you follow the two rules, I don't believe you'll have problems with being inside two overlapping objects at a given point.
For a really nice reference on collisions in general, I'd highly recommend Christer Ericson's book, "Real-time Collision Detection."
Author
I think I get what you mean now... so would this work:
The intersection calculator notes whether each intersection is an entry or exit when it compiles a list of all possible intersections - a list of distance, entry/exit type and any other needed information (like surface normal/reflection type)
The program then goes through the list, adding one to an 'in volumes' counter every time it sees an 'entry' and subtracts one every time it sees an 'exit'.
If the 'in volumes' counter is 1 when it hits an exit, it checks to see if the next collision is a duplicate position 'entry point' (and then ignores both collisions), and otherwise returns it as the proper wall collision point.
Also unfortunately that book isn't in my university library, is there any others or perhaps websites that could be recommended?
The intersection calculator notes whether each intersection is an entry or exit when it compiles a list of all possible intersections - a list of distance, entry/exit type and any other needed information (like surface normal/reflection type)
The program then goes through the list, adding one to an 'in volumes' counter every time it sees an 'entry' and subtracts one every time it sees an 'exit'.
If the 'in volumes' counter is 1 when it hits an exit, it checks to see if the next collision is a duplicate position 'entry point' (and then ignores both collisions), and otherwise returns it as the proper wall collision point.
Also unfortunately that book isn't in my university library, is there any others or perhaps websites that could be recommended?
Yes, you have it now. If you know what type of material your starting point is in (e.g., air), all you really need to know is the type of material bounded by the triangle with which the ray intersects, and the surface normal of that triangle (assuming your triangles are ordered consistently, e.g., they always point towards the outside of a volume). So, you would be entering an object if the dot product between your ray and the intersection point normal is negative, and the triangle attributes would tell you the correct material type. Compare with where you are...you're keeping track of that at each hit point, and the filter is trivial.
Christer Ericson has a web page that is a companion to his book. It is here:
realtimecollisiondetection.net
You won't find much of the heart of the book there, but you will find his GDC 2006 slides on robustness for geometry calcs. Its a good reference in itself.
I also found these documents, which look entertaining and are certainly related!
Ray Tracing CSG Objects Using Single Hit Intersections
Ray Tracing Part 1
Ray Tracing Part 2
Christer Ericson has a web page that is a companion to his book. It is here:
realtimecollisiondetection.net
You won't find much of the heart of the book there, but you will find his GDC 2006 slides on robustness for geometry calcs. Its a good reference in itself.
I also found these documents, which look entertaining and are certainly related!
Ray Tracing CSG Objects Using Single Hit Intersections
Ray Tracing Part 1
Ray Tracing Part 2
i implemented something like ghrodes suggested once.
in terms of class structure, it looked something like this
abstract class solid
-abstract pointlist intersect(ray r)
abstract class primitive: solid
class convexhull: primitive
class sphere: primitive
class cylinder: primitive
etc..
abstract class operator : solid
-solid lefthand, righthand
class intersect: operator
class union: operator
class substract: operator
so, you can build a CSG tree out of those classes. primitives are leafnodes and operators branches. once you call intersect on the root solid with a given ray, intersect is recursively called on the whole tree. each intersection returns a list of entry and exit points sorted by the distance along the ray. so intersection with a convex primitive returns at most two points. the operators merge the left and righthand pointlist in the appropriate way, resulting in a sorted list of all entry and exit point returned by the root solid.
ofcource you are usually only interested in the first point, so why all the hassle? because otherwise you wouldnt be able to get the first point in all circumstances either (think substraction from a nonconvex solid for instance).
in terms of class structure, it looked something like this
abstract class solid
-abstract pointlist intersect(ray r)
abstract class primitive: solid
class convexhull: primitive
class sphere: primitive
class cylinder: primitive
etc..
abstract class operator : solid
-solid lefthand, righthand
class intersect: operator
class union: operator
class substract: operator
so, you can build a CSG tree out of those classes. primitives are leafnodes and operators branches. once you call intersect on the root solid with a given ray, intersect is recursively called on the whole tree. each intersection returns a list of entry and exit points sorted by the distance along the ray. so intersection with a convex primitive returns at most two points. the operators merge the left and righthand pointlist in the appropriate way, resulting in a sorted list of all entry and exit point returned by the root solid.
ofcource you are usually only interested in the first point, so why all the hassle? because otherwise you wouldnt be able to get the first point in all circumstances either (think substraction from a nonconvex solid for instance).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
