Printable View
how can i make geometry, that when it intersects other geometry, makes the intersection area not rendered?
what i'm trying to say is better explained in the following image,
the red is solid geometry, the blue is subtractive geometry, and the grey with blue lines is the intersection point that is not rendered.
What are the constraints for the geometry?
If this is 3D with arbitrary geometry, the math for something like that is beyond most people.
yup...3d....i should also add that i'm using OpenGL
-psychopath
Hmm, well, I would like to encourage you to be able to do this, but I think that the math for doing this in 3D, with *arbitrary geometry* might be a bit more complex than even college level students to be able to do, and evidently you are 13.
This is along the lines of something called 'constructive solid geometry', aka CSG for short. Although not exactly the same, CSG is a process that most map compilers use to be able to combine geometry into simpler geometry...for example if you placed to cubes right next to each other it would turn them into a single large rectangle (this means that there is less to send down the rendering pipeline later, as there are less repeating vertices). This is pertinent because it involves finding where geometry touches or intersects.
So, are you willing to put some constraints on the type of geometry you are willing to use? For example, walls can only be perpendicular, or 45 degrees to each other (or some other specific angle)...something along those lines.
Then, it makes the problem more feasible to solve.
EDIT:
If the geometry only ever looks simple, as it does in that picture you posted, then this is a pretty easy problem to solve, but you mentioned that you want this in full 3D, and it seems like you wanted it with arbitrary geometry (that's why I said what I said above).
This can be done as you render your object. It's no different than having different levels of detail for terrain. At the detail border you must take away vertices. Instead of actually dumping the vertex, you simply weld two vertices together. So where you once had a vertex you now place that vertex one left or one right of it.
You could use a D3DXSPMESH instead of a normal buffer. This interface already supports dynamic alterations to the mesh. However you will still have to tweak it a bit to accomplish what you want.
The math for this is not complex at all, it's just a matter of indexing into vertex arrays and altering indexes temporarily.
ok thanks.
after reading over both your replys and thinking everything over, i think i can probably get it to work.
example:
say i have a wall, and i want to cut a door shape into it:
psuedo code:
if (subtractive geometry intersects with solid geometry)
{
delete solid geometry();
draw solid gemetry with ends being the end of the cut geometry and the other end where the end of the gemetry present previously was();
do basicly the same thing as step two, only for what may be left on top of the cut geometry();
}
pic (red=solid, blue=cut/not rendered):
If your geometry is only ever going to be as simple as in the pictures, then Bubba is correct in saying that the math is easy, and that it's as simple as moving vertices...as Bubba said you only need to move vertices to the right or left (meaning, the blue subtractive geometry gets its X component of the endpoint vertices set equal to the value of the inner walls of the red part).
Otherwise if it is anymore complex you are dealing with 3D planes, convex volumes (convex is one of the constraints that are in 3D editors...I mentioned putting constraints on YOUR geometry, and convex is one of them...aka manifold...I can explain better if you want), and a vast world of complex algorithms that deal with 'polygon soup'.
ray trace the scene. if a ray intersects the the "subtractive" piece followed by the other geometry dont render it (colour that pixel black/background colour) otherwise, render as usual.
Way to remain basic, lets introduce ray tracing to the 13 year old amateur coder.
Next, why don't we start talking about how to numerically approximate the pressure difference and torque arm caused by exhaust shot out from the side of a basllistic missle that flies at 6,000 mph
and if you do want to take Perspective's advice, you don't need to write a real 'ray tracer' so to speak...look into the stencil buffer. It is functionality which does sort of do ray tracing, in the sense that it can update the depth buffer of a rendered object based on z distances...but it still isn't real ray tracing. However, this is not good because it implies that you are doing this in real time. It is better to pre compile all of the vertices and then render the final product, although if you are using simple data the speed hit is trivial.
I would not recommend using the stencil buffer or the depth buffer for ray casting into 3D space. There are equations for ray to triangle, ray to bounding volume intersections that are much easier. Essentially you fire off 2 or more rays and see what they hit. More rays should only be done on big rigs as this slows down the code a lot.
I do not condone using the stencil buffer OR ray tracing/casting for this trivial problem.Quote:
Originally Posted by Bubba
But I must add, that the 'ray to triangle' and 'ray to bounding volume' are not only VERY complex because you must implement it from a VERY FUNDAMENTAL level but it's much slower to execute than rendering a triangle (which is all that the stencil buffer needs to do in order to do the depth compares).
To get a ray to triangle intersection to work, you must either inflate the data using up a lot of memory to represent 3 inward pointing planes, OR you must make at least 3 sqrt and 3 acos calls to sum angles (in accordance to the algorithms I know of in order to do this).
The other less expensive ray to bounding volume algorithms are just plain complex, such as the ray to brush algorithm, and using the stencil buffer would have been easier.
But, as I said, both stencil buffer and ray casting/ray tracing are not appropriate for this problem.
So psycopath, how are things actually coming? I've seem to have stolen this thread from you :(
ugh....guess i'll stick to basics for now, but thanks anyway :)
>>So psycopath, how are things actually coming? I've seem to have stolen this thread from you<<
not at all...but anyway, things are going pretty good...so far i have
-first person camera
-Texture Mapping (with mip-mapping
-Multi-Texturing
-Light-Mapping
-Blending/Trasparency
-SkyBox
-Distance Fogging
-Dynamic Lighting
..for the GameEngine/Game Creation program...the real problem lately has been "plugging" these features into the GUI of the actual program...but at least the features are there....much more to go, as there still arn't any gameplay features yet :(
Anyway..theres more info on my site (www.psychopathproductions.tk)
Every game on the market casts rays in one form or another. You have to in order to find out bullet paths, etc. Also games cast rays towards the sun in order to find out whether or not they must render a lense flare or not. Casting rays is not that hard and it does not require all that.
But what you really want to do is portal rendering. Portal rendering is essentially what the new DOOM3 uses to render complex scenes with multiple exits in rooms. It also uses BSP/Portal rendering but I'll explain the portal rendering to you here.
First you must create a scene graph. The graph determine what rooms are connected.
Here is what you do. Each portal is a doorway or a bounding volume. Basically they are polygons that you will project into screen space to see if they overlap another volume or not. If they do, you render its associated geometry. If they dont, you don't render and you stop following the node.
Step 1:
In my example, bedroom 1 is where the camera is. Ok, so we know that all of bedroom 1's geometry must be rendered. So we render it and then we use it's portal polygon (or the poly that represents the doorway as the bounding volume or clipping volume for the next render.
Step 2:
When we leave the bedroom we are at hallway point 1. We project the hallway's bounding volume's against our bounding volume for the current room, which is the doorway for our room. Does the hallway's bounding volume overlap ours? Yes, it does so we render it and clip the geometry to our bounding volume - or the doorway to our room.
Step 3:
Now we have two paths. We can go to the hallway point 2 or bedroom 3. Performing a depth first traversal, we go to bedroom 3 and 'push' hallway point 2 onto our stack.
Step 4:
Now check bedroom 3's bounding volume against our bounding volume or portal - our doorway. Does it overlap? Yes. So we render all of bedroom 3 and clip it to hallway point 1's bounding volume or portal - essentially the doorway into bedroom 3.
Step 5:
There are no more node's for bedroom 3. We are done with this branch.
Step 6:
We pop hallway point 2 off of our stack and test. Does hallway point 2's bounding volume overlap ours?? No. Hallway point 2 will never be visible from our current location and thus none of it's nodes will be either. The scene is done.
This is just one example of a portal renderer. This is the main visiblility determination algorithm. Then when a room passes, you use the BSP algorithm to effectively render it's geometry. Using both of these combinations will result in extremely fast renders, and extremely accurate rendering.
I hope I explained it well enough.
Ray to triangle does not require 3 sqrts() or 3 arccos(). It only requires dot product.
D3DXVec3Dot().
Portal renderers aren't really the best unless you absolutely need strict culling. The reason is, a portal engine can only accept innately 'closed off regions' such as indoor environments. One of the constraints of geometry is that a region can only have portals as holes in its bounding volume. This doesn't work fast for outdoor environments, or even open-ended indoor environments.
And also, the original poster is only looking into a 'CSG subtract' operation.
And you are wrong about the ray to triangle only needing a dotproduct. If the 3 inward pointing planes are not stored, then you must calculate where the ray intersects the triangle plane, create vectors from the plane intersection to each vertex, and calculate the angles between each of these vectors which requires 3 sqrts and 3 acos calls, and must be approximately equal to 2PI radians if the ray intersects the triangle.
Otherwise you have 3 planes which point inward and in THAT case yes you only need dotproduct. You have to weigh speed versus memory because these 3 planes
a) will take up a lot of space, even for simple geometry
b) cannot be compressed easily in any sort of scheme, because you cannot assume that adjacent triangles are always coplanar (often not)
Check GPU gems. No sqrts(), no arccos().
I do not have it, would you be kind enough to post a method that only requires dotproducts?
As I've said, the only method for ray/triangle intersection that works only with dotproduct is when you store the information for 3 inward pointing planes that represent each edge of the triangle...if the ray intersects the triangle plane, and if that point is in front of all 3 other planes, then the ray intersects the triangle.
Else, you need to induce the other method I am talking about, which you evidently haven't heard of (very common for 3D graphics programmers to know about) which induces 3 sqrts and 3 acos calls.
This was taken from 3D Mathematics for Game Programming and Development. I only altered it to suit Direct3D using the D3DX library of functions. The code was also taken from an algorithm by Didier Badoul out of Graphics Gems I, pp 390-393.Code:
float RayTriangleIntersection(D3DXVECTOR3 &rayOrg,D3DXVECTOR3 &rayDelta,D3DXVECTOR3 &p0,D3DXVECTOR3 &p1,D3DXVECTOR3 &p2,float minT)
{
const float kNoIntersection=1e30f;
D3DXVECTOR3 e1,e2;
e1=p1-p0;
e2=p2-p1;
D3DXVECTOR n;
D3DXVec3Cross(&n,e1,e2);
float dot=n * rayDelta;
if (!(dot<0.0f)) return kNoIntersection;
float d=D3DXVec3Dot(&n,&p0);
float t=d-(D3DXVec3Dot(&n,&rayOrg);
if (!(t<0.0f)) return kNoIntersection;
if (!(t>=dot*minT)) return kNoIntersection;
t/=dot;
assert(t>=0.0f);
assert(t<=minT);
D3DXVector3 p;
p=rayOrg+rayDelta*t;
float u0,u1,u2;
float v0,v1,v2;
if (fabs(n.x) > fabs(n.y))
{
if (fabs(n.x)>fabs(n.z))
{
u0=p.y-p0.y;
u1=p1.y-p0.y;
u2=p2.y-p0.y;
v0=p.z-p0.z;
v1=p1.z-p0.z;
v2=p2.z-p0.z;
}
else
{
u0=p.x-p0.x;
u1=p1.x-p0.x;
u2=p2.x-p0.x;
v0=p.y-p0.y;
v1=p1.y-p0.y;
v2=p2.y-p0.y;
}
}
else
{
if (fabs(n.y)>fabs(n.z))
{
u0=p.x-p0.x;
u1=p1.x-p0.x;
u2=p2.x-p0.x;
v0=p.z-p0.z;
v1=p1.z-p0.z;
v2=p2.z-p0.z;
}
else
{
u0=p.x-p0.x;
u1=p1.x-p0.x;
u2=p2.x-p0.x;
v0=p.y-p0.y;
v1=p1.y-p0.y;
v2=p2.y-p0.y;
}
}
float temp=u1*v2-v1*u2;
if (!(temp!=0.0f)) return kNoIntersection;
temp=1.0f/temp;
float alpha=(u0*v2-v0*u2)*temp;
if (!(alpha>=0.0f)) return kNoIntersection;
float beta=(u1*v0-v1*u0)*temp;
if (!(beta>=0.0f)) return kNoIntersection;
float gamma=1.0f-alpha-beta;
if (!(gamma>=0.0f)) return kNoIntersection;
return t;
}
Assuming I made no mistakes it should work just fine.
In D3D, are the verts of visible triangles winded in clockwise or counter clockwise direction?
The portal rendering scheme only works well for inside environments which is what I thought we were talking about. For other environments you could switch to a quad tree or some type of ROAM implementation. This combined with a BSP portal renderer for interior scenes would be more than adequate. If a window or door leads to the outside you would need to switch VSDs. Or you could limit your game to either indoor only or outside only scenes. Most quake, unreal, and doom maps are exclusively indoor with outdoor areas made to look like an outdoor scene, when in actuality it is a modified indoor scene. None of the scenes stretch too far into the distance. For a better outdoor scene you would need to implement something like FarCry or some type of other VSD. There are a millions ways to do it.
It can be either. The algo above might not work for a CCW winding order. But that is easily solved.
In Direct3D winding order is controlled by:
Device->SetRenderState(D3DRS_CULLMODE,[D3DCULL_CW | D3DCULL_CCW]);
um...yea....all this goes WAY over my head at this point....i'll leave dot products and ray tracing and what ever else you mentioned for another time ;}
-psychopath
That is a very interesting algorithm. I have never seen it before, but if it really is from a book then I trust it works. I don't actually understand where all of it comes from, but if it does work with an arbitrary triangle* then it looks to be the best algorithm because it involves no square roots or acos, but also doesn't need to inflate the data with inward pointing planes.
*My only question is this: does it really work for an arbitrary triangle (i.e, the triangle doesn't have to be aligned to any specific axis or anything like that)...it seems like it does, but I just want to make sure.
According to the book, yes it does. I have not tried it yet because I'm not that far into my engine at this point.