Frustum Culling

Blitz3D Forums/Blitz3D Programming/Frustum Culling

EmerGki (Posted 2005) [#1]

Somebody have any example of Frustum Culling? Thanks' Emerson Gresoski Dynamic Games Entertainment www.dynamicgames.com.br/novo or www.dynamicgames.com.br (for english)

big10p (Posted 2005) [#2]

Blitz3D automatically perform frustum culling on a per-entity basis, but if the camera can see a single pixel on an entity then the whole thing gets rendered. Performing culling on a per-triangle basis isn't easy and I don't *think* anyone has done it successfully in B3D. The processing time needed to perform the cull is normally longer that it would take to render all entities anyway, so it's not worth it. Someone correct me if I'm wrong, here. :)

Andy (Posted 2005) [#3]

>Blitz3D automatically perform frustum culling on a per- >entity basis, but if the camera can see a single pixel on >an entity then the whole thing gets rendered. I know that's the prevalent wisdom on the subject, but I've experienced some weird things which lead me to believe that it is not entirely accurate. For example, I made a very long landing strip(two triangles) for a makeshift flight sim. Regardless of camerange it would sometimes simply disappear if I wasn't looking directly at it, even if it was still in the field of vision. I didn't look into it, but at the time, I assumed that B3D culled not based on entity pixels, but based on entity center. Andy

big10p (Posted 2005) [#4]

Hmmm. It can't cull simply on mesh coords (centre), otherwise you'd see entities suddenly pop into view as you looked around a scene. Can't think what the problem was you were having, though. :)

jhocking (Posted 2005) [#5]

@andy: I don't know if this is relevant to your prob (probably not) but note that Blitz culls based on an entity's first frame of animation. Thus, if the mesh is located far from that first frame, it can appear to pop in and out as the coordinates from that first frame move into and out from the camera view. I don't know of any way around this, such as forcing Blitz to always render a given entity regardless, but I may just be forgetting how to do that.

sswift (Posted 2005) [#6]

This is my frustrum culling library which I use in my shadow system: ; ----------------------------------------------------------------------------------------------------------------------------------- ; PolyClip - Swift Polygon Clipping System - Copyright 2004 Shawn Swift ; ----------------------------------------------------------------------------------------------------------------------------------- ; ; Find out more about my shadow, and other systems, here: ; ; Shadows, Terrains, GUI/HUD/2D Overlays in 3D: ; <a href="http://www.blitzbasic.com/logs/userlog.php?user=963&log=147" target="_blank">http://www.blitzbasic.com/logs/userlog.php?user=963&log=147</a> ; ; 2D sprite system for all versions of Blitz with five blending modes including alpha, add, and multiply: ; <a href="http://www.blitzbasic.com/toolbox/toolbox.php?tool=58" target="_blank">http://www.blitzbasic.com/toolbox/toolbox.php?tool=58</a> ; ; I accept payment via Paypal, Western Union, personal checks made out in US dolalrs, and bank transfers. ; Paypal is the preffered method. If you wish to pay via paypal, send payment to scswift@... ; ; ----------------------------------------------------------------------------------------------------------------------------------- ; ; This system supports polygons with any number of sides, but it defaults to a max of 4 sides per input poly. The output polygons ; may have up to 10 sides. Change the constant CLIP_MAX_POLY_SIDES to increase the number of sides you can use on input polygons. ; And keep in mind that if you clip a polygon and then re-input it into the system for additional clipping, you'll have to make ; sure that CLIP_MAX_POLY_SIDES is large enough to support the potentially much larger resulting polygon. ; ; The system also defaults to allowing only six clipping planes, which may not be enough if you want to clip polygons against shapes ; other than cubes. Again, increasing CLIP_MAX_POLY_SIDES will increase this value. See CLIP_MAX_POLY_SIDES for more details. ; ; ; What can you do with this system? ; ; 1. Cut a polygon with a plane, returning only the half on the inside side of the plane. (Side facimg away from plane's normal) ; 2. Clip a polygon to the viewport by specifying a iew frustrum with 4, 5 or 6 planes. ; 3. Quickly determine if an individual triangle is in a frustrum or other polyhedra formed by planes, without having to set up ; a polygon or delete the returned data. ; ; Instructions: ; ; If you want to clip a polygon, create some planes like so: ; ; TopPlane.CLIP_Plane = CLIP_CreatePlane(A#, B#, C#, D#) ; ; Then create a polygon like this: ; ; ThisPoly.CLIP_Poly = CLIP_CreateTri(X1#, Y1#, Z1#, X2#, Y2#, Z2#, X3#, Y3#, Z3#) ; ; Or, create one manually with the CLIP_CreatePoly() and CLIP_AddVertex() commands. ; You can also adjust the values for a vertex. If a polygon has 4 vertcies, you can index them with the values 0..3. ; AddVertex also returns the index number of the most recently created vertex if you would like to use that. ; ; Why set the normal, color, alpha, or texture coordinates of a vertex? ; ; When the system clips a polygon, it creates a new polygon, sometimes with additional vertices. By specifying these values, ; you can have all of them automaitcally interpolated and computed for all the vertices in the new polyon! ; ; And finally, call ClipPoly to clip an individual polygon, or ClipPolys to clip all polygons at once. ; ; You can also skip the polygon creation steps and test tris against a region bounded by planes with CLIP_TriInFrustum(). ; ; ----------------------------------------------------------------------------------------------------------------------------------- ; ; This system uses the Sutherland-Hodgeman polygon clipping algorithm. ; ; Here is some pseudocode that describes the algorithm: ; ; ; CURRENT_POLYGON = Polygon to be clipped. ; ; For each plane in the frustum: ; ; For each pair of vertices (v1,v2) forming an edge of CURRENT_POLYGON: ; ; (Inside means a vertex is on the side of the current plane that faces away from the plane's normal.) ; ; If v1 inside, v2 inside = output v2 ; If v1 inside, v2 outside = output intersection ; If v1 outside, v2 outside = no output ; If v1 outside, v2 inside = output v2 and intersection ; ; Next ; ; CURRENT_POLYGON = Polygon formed by vertcies output from for loop. ; If no vertcies in CURRENT_POLYGON exit loop. ; ; Next ; ; Resulting polygon is clipped to frustum. ; ; Returned points will have same winding as input points. In other words, if input polygon is wound counterclockwise, ; resulting polygon will also have its vertices wound counterclockwise. ; ; If no vertices in resulting polygon, polygon was completely outside frustum. ; ; ----------------------------------------------------------------------------------------------------------------------------------- ; ; Rather than use this system to do all your clipping as-is, you should use it in conjunction with a hash-table using ; "clipping flags" for each vertex, and use that to determine if you should send the triangle to this system. You can do the ; vertex text with the CLIP_Point_Inside_Plane() function after you have set up your planes. ; ; Read this article for more info: ; <a href="http://www.gamasutra.com/features/19990507/polygon_clipping_01.htm" target="_blank">http://www.gamasutra.com/features/19990507/polygon_clipping_01.htm</a> ; ; ----------------------------------------------------------------------------------------------------------------------------------- ; CLIP_MAX_POLY_SIDES is the maximum number of sides a polygon can have. ; It must ALWAYS be larger than the total number of sides on the polygons you input into the system! ; ; You can calculate this number like so: (Max sides on input polygon) + (Max number of clipping planes) ; ; The default value of 10 assumes that the input polygon will have 3 or 4 sides, (tri or quad) and that there will be ; a maximum of 6 clipping planes. Const CLIP_MAX_POLY_SIDES = 10 Type CLIP_Plane Field A# Field B# Field C# Field D# End Type ; 564 bytes Type CLIP_Poly Field Vertices Field Vx#[CLIP_MAX_POLY_SIDES] Field Vy#[CLIP_MAX_POLY_SIDES] Field Vz#[CLIP_MAX_POLY_SIDES] Field Vnx#[CLIP_MAX_POLY_SIDES] Field Vny#[CLIP_MAX_POLY_SIDES] Field Vnz#[CLIP_MAX_POLY_SIDES] Field Vu0#[CLIP_MAX_POLY_SIDES] Field Vv0#[CLIP_MAX_POLY_SIDES] Field Vu1#[CLIP_MAX_POLY_SIDES] Field Vv1#[CLIP_MAX_POLY_SIDES] Field Vr#[CLIP_MAX_POLY_SIDES] Field Vg#[CLIP_MAX_POLY_SIDES] Field Vb#[CLIP_MAX_POLY_SIDES] Field Va#[CLIP_MAX_POLY_SIDES] End Type ; These variables will contain the output from CLIP_Line_Intersect_Plane() Global CLIP_Intersect_X# Global CLIP_Intersect_Y# Global CLIP_Intersect_Z# Global CLIP_Intersect_U# ; These variables will contain the output from CLIP_InterpolateNormal() Global CLIP_Normal_X# Global CLIP_Normal_Y# Global CLIP_Normal_Z# ; These variables will contain the output from CLIP_CalculateTriPlane() and CLIP_Calculate2DLine(). Global CLIP_A# Global CLIP_B# Global CLIP_C# Global CLIP_D# ; These variables will contain the output from CLIP_CalculateTriNormal() Global POLY_Temp.CLIP_Poly = New CLIP_Poly ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function creates a new clipping plane with the specified plane equation. ; ; Returns a pointer to the plane, but you don't need to save it because there is no function in the system you need to pass ; that pointer to. It is just there for future expansion. ; ; Use CLIP_FreePlanes() to free all the planes you've created when you're done with them and want to make new ones. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_CreatePlane.CLIP_Plane(A#, B#, C#, D#) Local NewPlane.CLIP_Plane NewPlane = New CLIP_Plane NewPlane\A# = A# NewPlane\B# = B# NewPlane\C# = C# NewPlane\D# = D# Return NewPlane End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function creates a new triangle and returns a pointer to it. ; ; It does not matter if polygons in this system are wound clockwise or counterclockwise. ; They are all clipped the same, and the resulting polygon will have the same winding as the original. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_CreateTri.CLIP_Poly(X1#, Y1#, Z1#, X2#, Y2#, Z2#, X3#, Y3#, Z3#) Local NewPoly.CLIP_Poly NewPoly = New CLIP_Poly CLIP_AddVertex(NewPoly, X1#, Y1#, Z1#) CLIP_AddVertex(NewPoly, X2#, Y2#, Z2#) CLIP_AddVertex(NewPoly, X3#, Y3#, Z3#) Return NewPoly End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function creates a new quad and returns a pointer to it. ; ; It does not matter if polygons in this system are wound clockwise or counterclockwise. ; They are all clipped the same, and the resulting polygon will have the same winding as the original. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_CreateQuad.CLIP_Poly(X1#, Y1#, Z1#, X2#, Y2#, Z2#, X3#, Y3#, Z3#, X4#, Y4#, Z4#) Local NewPoly.CLIP_Poly NewPoly = New CLIP_Poly CLIP_AddVertex(NewPoly, X1#, Y1#, Z1#) CLIP_AddVertex(NewPoly, X2#, Y2#, Z2#) CLIP_AddVertex(NewPoly, X3#, Y3#, Z3#) CLIP_AddVertex(NewPoly, X4#, Y4#, Z4#) Return NewPoly End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function creates a new polygon and returns a pointer to it. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_CreatePoly.CLIP_Poly() Return New CLIP_Poly End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function adds a vertex to a polygon, and returns its index number. ; ; Vertices must be added in order, and if wound in a clockwise direction the face normal will point towards you. ; ; Vertex indices range from 0 to vertices-1. ; ; Poly is the polygon to add the vertex to. ; XYZ is the vertex position. (Optional) ; Vertex color defaults to 255,255,255. ; Vertex alpha defaults to 1. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_AddVertex(Poly.CLIP_poly, X#=0, Y#=0, Z#=0) Local Index Index = Poly\Vertices Poly\Vertices = Poly\Vertices + 1 Poly\Vx#[Index] = X# Poly\Vy#[Index] = Y# Poly\Vz#[Index] = Z# Poly\Vr#[Index] = 255 Poly\Vg#[Index] = 255 Poly\Vb#[Index] = 255 Poly\Va#[Index] = 1 Return Index End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function sets the position of a vertex. ; ; Poly is the poly which contains the vertex. ; Index is the vertex index returned from CLIP_AddVertex(). ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_SetVertexPosition(Poly.CLIP_Poly, Index, X#, Y#, Z#) Poly\Vx#[Index] = X# Poly\Vy#[Index] = Y# Poly\Vz#[Index] = Z# End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function sets the normal of a vertex. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_SetVertexNormal(Poly.CLIP_Poly, Index, Nx#, Ny#, Nz#) Poly\Vnx#[Index] = Nx# Poly\Vny#[Index] = Ny# Poly\Vnz#[Index] = Nz# End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function sets the texture coordinates of a vertex. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_SetVertexUV(Poly.CLIP_Poly, Index, U#, V#, Coord_Set=0) If Coord_Set = 0 Poly\Vu0#[Index] = U# Poly\Vv0#[Index] = V# Else Poly\Vu1#[Index] = U# Poly\Vv1#[Index] = V# EndIf End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function sets the color of a vertex. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_SetVertexColor(Poly.CLIP_Poly, Index, R#, G#, B#) Poly\Vr#[Index] = R# Poly\Vg#[Index] = G# Poly\Vb#[Index] = B# End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function sets the alpha of a vertex. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_SetVertexAlpha(Poly.CLIP_Poly, Index, Alpha#) Poly\Va#[Index] = Alpha# End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function gets the position of a vertex. ; Set XYZ to 0 if you want the X component, 1 for Y, and 2 for Z. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_GetVertexPosition#(Poly.CLIP_Poly, Index, XYZ) Select XYZ Case 0 Return Poly\Vx#[Index] Case 1 Return Poly\Vy#[Index] Case 2 Return Poly\Vz#[Index] End Select End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function gets the normal of a vertex. ; Set XYZ to 0 if you want the X component, 1 for Y, and 2 for Z. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_GetVertexNormal#(Poly.CLIP_Poly, Index, XYZ) Select XYZ Case 0 Return Poly\Vnx#[Index] Case 1 Return Poly\Vny#[Index] Case 2 Return Poly\Vnz#[Index] End Select End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function gets the texture coordinates of a vertex. ; ; Set UV to 0 to get the U component, and 1 to get the V. ; Set Coord_Set to 0 to get the first set of UV coordinates, and 1 to get the second. (Optional) ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_GetVertexUV#(Poly.CLIP_Poly, Index, UV, Coord_Set=0) If Coord_Set = 0 If UV = 0 Then Return Poly\Vu0#[Index] If UV = 1 Then Return Poly\Vv0#[Index] Else If UV = 0 Then Return Poly\Vu1#[Index] If UV = 1 Then Return Poly\Vv1#[Index] EndIf End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function gets the color of a vertex. ; ; Set RGB to 0 if you want the R component, 1 for G, and 2 for B. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_GetVertexColor#(Poly.CLIP_Poly, Index, RGB) Select RGB Case 0 Return Poly\Vr#[Index] Case 1 Return Poly\Vg#[Index] Case 2 Return Poly\Vb#[Index] End Select End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function gets the alpha of a vertex. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_GetVertexAlpha#(Poly.CLIP_Poly, Index) Return Poly\Va#[Index] End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function deletes all planes that have been added to the system. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_FreePlanes() Local LOOP_Plane.CLIP_Plane For LOOP_Plane = Each CLIP_Plane Delete LOOP_Plane Next End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function deletes all polygons that have been added to the system. ; CLIP_TriInFrustum does NOT leave any polygons lying around that you need to delete later. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_FreePolys() Local LOOP_Poly.CLIP_Poly For LOOP_Poly = Each CLIP_Poly Delete LOOP_Poly Next ; Recreate the polygon that we use for scratch. POLY_Temp = New CLIP_Poly End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function frees Kevin Mitnick and returns a pointer to a high profile computer security job. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_FreeKevinMitnick() End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function returns TRUE if the specified triangle is intersecting/inside the region bounded by the clipping planes. ; CLIP_TriInFrustum does NOT leave any polygons lying around that you need to delete later. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_TriInFrustum(X1#, Y1#, Z1#, X2#, Y2#, Z2#, X3#, Y3#, Z3#) Local POLY_Input.CLIP_Poly ; Do a quick but inaccurate test first. ; If this test is positive, triangle MAY be inside frustum. If CLIP_FastTriInFrustum(X1#, Y1#, Z1#, X2#, Y2#, Z2#, X3#, Y3#, Z3#) ; Quick test says triangle MAY be inside frustum. ; Do slower, accurate test. ; Create the triangle. POLY_Input = New CLIP_Poly POLY_Input\Vertices = 3 POLY_Input\Vx#[0] = X1# POLY_Input\Vy#[0] = Y1# POLY_Input\Vz#[0] = Z1# POLY_Input\Vx#[1] = X2# POLY_Input\Vy#[1] = Y2# POLY_Input\Vz#[1] = Z2# POLY_Input\Vx#[2] = X3# POLY_Input\Vy#[2] = Y3# POLY_Input\Vz#[2] = Z3# ; Clip the triangle. CLIP_ClipPoly(POLY_Input, False) ; Was the polygon in the frustum? If POLY_Input\Vertices > 0 ; Poly has vertices. ; Tri was inside or intersecting the frustum. Delete POLY_Input Return True Else ; Poly has no vertices. ; Tri was completely outside the frustum. Delete POLY_Input Return False EndIf Else ; Quick test says triangle was DEFINITELY outside the frustum. Return False EndIf End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function is a fast test that returns TRUE if a triangle is MIGHT be in a frustum. ; Note that this test is INACCURATE, and will only tell you for sure that a triangle is NOT in the frustum. ; A more accurate test needs to be done after to say for sure that the triangle IS in the frustum. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_FastTriInFrustum(X1#, Y1#, Z1#, X2#, Y2#, Z2#, X3#, Y3#, Z3#) Local LOOP_Plane.CLIP_Plane Local A#, B#, C#, D# For LOOP_Plane = Each CLIP_Plane A# = LOOP_Plane\A# B# = LOOP_Plane\B# C# = LOOP_Plane\C# D# = LOOP_Plane\D# ; Are all three vertcies of this triangle outside this plane? If (X1#*A# + Y1#*B# + Z1#*C# + D#) > 0 If (X2#*A# + Y2#*B# + Z2#*C# + D#) > 0 If (X3#*A# + Y3#*B# + Z3#*C# + D#) > 0 ; Yes. ; Triangle is DEFINITELY outside frustum! Return False EndIf EndIf EndIf Next ; Triangle MAY be inside frustum, but we can't be sure. Return True End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function is a fast test that returns TRUE if a triangle is MIGHT be in a frustum. ; Note that this test is INACCURATE, and will only tell you for sure that a triangle is NOT in the frustum. ; A more accurate test needs to be done after to say for sure that the triangle IS in the frustum. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_FastPolyInFrustum(Poly.CLIP_poly) Local LOOP_Plane.CLIP_Plane Local A#, B#, C#, D# Local LOOP_Vertex Local Outside For LOOP_Plane = Each CLIP_Plane Outside = True ; For each vertex in the polygon... For LOOP_Vertex = 0 To Poly\Vertices-1 ; Is this vertex inside this plane? If (Poly\Vx#[LOOP_Vertex]*LOOP_Plane\A# + Poly\Vy#[LOOP_Vertex]*LOOP_Plane\B# + Poly\Vz#[LOOP_Vertex]*LOOP_Plane\C# + LOOP_Plane\D#) < 0 ; Vertex is inside plane. ; Polygon cannot be outside this plane. Skip rest of vertices, and check poly against next plane. Outside = False Exit Else ; Vertex is outside plane. EndIf Next If Outside ; All vertcies were outside the last plane. ; Polygon is DEFINITELY outside frustum. Return False EndIf Next ; Polygon was not outside any planes. ; Polygon MAY be inside frustum, but we can't be sure. Return True End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function returns the distance of a point from a plane. ; ; If the point is in front of the plane, this distance will be positive. ; If the vertex is behind the plane, the distance will be negative. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_Point_Distance_From_Plane(X#, Y#, Z#, A#, B#, C#, D#) Return (X#*A# + Y#*B# + Z#*C# + D#) End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function returns true if a point is on the back side of a plane. ; A plane's front side is the direction in which its normal points. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_Point_Inside_Plane(X#, Y#, Z#, A#, B#, C#, D#) If (X#*A# + Y#*B# + Z#*C# + D#) < 0 Then Return True Return False End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function returns TRUE if the specified sphere is intersecting/inside the region bounded by the clipping planes. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_PointInFrustum(X#, Y#, Z#) Local LOOP_Plane.CLIP_Plane ; For each clipping plane... For LOOP_Plane = Each CLIP_Plane If Not ((X#*LOOP_Plane\A# + Y#*LOOP_Plane\B# + Z#*LOOP_Plane\C# + LOOP_Plane\D#) < 0) Then Return False Next Return True End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function returns true if a sphere is intersecting or behind the specified plane. ; ; XYZ = Sphere center ; Radius = Sphere radius ; ABCD = Plane equation ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_Sphere_Inside_Plane(X#, Y#, Z#, Radius#, A#, B#, C#, D#) If (X#*A# + Y#*B# + Z#*C# + D#) < Radius# Then Return True Return False End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function returns TRUE if the specified sphere is intersecting/inside the region bounded by the clipping planes. ; ; This function is sloppy. While it finds all spheres inside/intersecting the region, it may also give false positives for ; some spheres outside the region but near it's corners. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_SphereInFrustum(X#, Y#, Z#, Radius#) Local LOOP_Plane.CLIP_Plane Local A#, B#, C#, D# ; For each clipping plane... For LOOP_Plane = Each CLIP_Plane ; Store this clipping plane's equation. A# = LOOP_Plane\A# B# = LOOP_Plane\B# C# = LOOP_Plane\C# D# = LOOP_Plane\D# If Not CLIP_Sphere_Inside_Plane(X#, Y#, Z#, Radius#, A#, B#, C#, D#) Then Return False Next Return True End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function takes a line segment and a plane as input, and outputs: ; ; 1. The global position at which the line intersects the plane, in CLIP_Intersect_XYZ#. ; ; 2. The line-relative position, in CLIP_Intersect_U#, where a value of 0..1 means the intersection point lies between V1 and V2, ; and a value less than 0 or greater than 1 means the intersection occured at a location outside the line segment. ; ; 3. TRUE if the line intersects the plane, and FALSE if the line runs near-parralel to the plane. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_Line_Intersect_Plane(V1x#, V1y#, V1z#, V2x#, V2y#, V2z#, Pa#, Pb#, Pc#, Pd#) Local Nx#, Ny#, Nz# Local Dot# ; Calculate the normal of the line. Nx# = V2x#-V1x# Ny# = V2y#-V1y# Nz# = V2z#-V1z# ; Calculate the dot product of the line's normal and the plane's normal. Dot# = Pa#*Nx# + Pb#*Ny# + Pc#*Nz# ; If the line is nearly parralel to the plane, they do not intersect. If (Abs(Dot#) < 0.0001) Then Return False ; Calculate the position on the line where the plane intersects it. CLIP_Intersect_U# = -(Pd# + Pa#*V1x# + Pb#*V1y# + Pc#*V1z#) / Dot# CLIP_Intersect_X# = V1x# + CLIP_Intersect_U#*Nx# CLIP_Intersect_Y# = V1y# + CLIP_Intersect_U#*Ny# CLIP_Intersect_Z# = V1z# + CLIP_Intersect_U#*Nz# ; Line intersects the plane. Return True End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function clips the specified polygon with the planes you have created. ; The original polygon's data is overwritten with the new clipped polygon. ; ; If the resulting polygon has 0 vertices, then the polygon was completely outside the region bounded by the clipping planes. ; ; Note: ; You can even call this function with a single clipping plane specified, and the polygon will be cut by that plane. ; The half which was on the inside side of the plane will be the polygon that is returned. ; ; The Fast flag allows you to enable to disable the interpolation of vertex appearance information. ; In other words, the final output polygon will have incorrect colors, normals, texture coordinates, and alpha. ; Even the original vertices will have these properties wiped out. ; The positions, however, will be correct. ; ; FAST mode is intended for use when you need to test to see if a polygon is in a frustum, but you don't care if those other ; properties are interpolated. ; ; You should also call CLIP_FastPolyInFrustum() before calling this function to check to see if the polygon is wholly outside ; the frustum, and should not be clipped at all. ; ; IMPORTANT NOTE! ; There may be a bug with interpolating UV coordinates in this function, or in the InterpolatedVertex function. ; I was getting some UV glitches and I cannot find the bug in these two functions, if there even is one. ; All other interpolations seem to work fine. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_ClipPoly(POLY_Clip.CLIP_Poly, Fast=False) Local POLY_Input.CLIP_Poly, POLY_Output.CLIP_Poly, POLY_Swap.CLIP_Poly Local LOOP_Plane.CLIP_Plane Local LOOP_Vertex Local V1_Index, V2_Index, VI_Index, VN_Index Local V1_Inside, V2_Inside Local Vertices ; Set up the input/output buffer pointers. POLY_Input = POLY_Clip POLY_Output = POLY_Temp ; For each clipping plane... For LOOP_Plane = Each CLIP_Plane ; Clear all vertcies from the output polygon. POLY_Output\Vertices = 0 ; Is the first vertex on the backside of the clipping plane? V1_Inside = CLIP_Vertex_Inside_Plane(POLY_Input, 0, LOOP_Plane) ; For each edge in the input polygon... For LOOP_Vertex = 0 To POLY_Input\Vertices-1 ; Calculate the vertices that form this edge. V1_Index = LOOP_Vertex V2_Index = LOOP_Vertex+1 If V2_Index = POLY_Input\Vertices Then V2_Index = 0 ; Is the endpoint of this edge on the back side of the clipping plane? V2_Inside = CLIP_Vertex_Inside_Plane(POLY_Input, V2_Index, LOOP_Plane) Select True ; Output V2. Case ((V1_Inside=True) And (V2_Inside=True)) ; Add V2 (endpoint of edge) to output polygon. If Fast ; Create a new vertex in the destination polygon and copy only the vertex's position. VN_Index = POLY_Output\Vertices POLY_Output\Vertices = POLY_Output\Vertices + 1 POLY_Output\Vx#[VN_Index] = POLY_Input\Vx#[V2_Index] POLY_Output\Vy#[VN_Index] = POLY_Input\Vy#[V2_Index] POLY_Output\Vz#[VN_Index] = POLY_Input\Vz#[V2_Index] Else ; Create a new vertex in the destination polygon and copy all properties. CLIP_CopyVertex(POLY_Input, V2_Index, POLY_Output) EndIf ; Output intersection point. Case ((V1_Inside=True) And (V2_Inside=False)) ; Find the point at which the edge intersects this plane. CLIP_Edge_Intersect_Plane(POLY_Input, V1_Index, V2_Index, LOOP_Plane) ; Add intersection point. If Fast VN_Index = POLY_Output\Vertices POLY_Output\Vertices = POLY_Output\Vertices + 1 POLY_Output\Vx#[VN_Index] = CLIP_Intersect_X# POLY_Output\Vy#[VN_Index] = CLIP_Intersect_Y# POLY_Output\Vz#[VN_Index] = CLIP_Intersect_Z# Else CLIP_Add_Interpolated_Vertex(POLY_Input, V1_Index, V2_Index, CLIP_Intersect_U#, POLY_Output) EndIf ; No output. Case ((V1_Inside=False) And (V2_Inside=False)) ; Both vertcies are on the outside side of the plane. ; Don't add any vertices to the polygon. ; Output Intersection point and V2. Case ((V1_Inside=False) And (V2_Inside=True)) ; Find the point at which the edge intersects this plane. CLIP_Edge_Intersect_Plane(POLY_Input, V1_Index, V2_Index, LOOP_Plane) ; Add intersection point. If Fast VN_Index = POLY_Output\Vertices POLY_Output\Vertices = POLY_Output\Vertices + 1 POLY_Output\Vx#[VN_Index] = CLIP_Intersect_X# POLY_Output\Vy#[VN_Index] = CLIP_Intersect_Y# POLY_Output\Vz#[VN_Index] = CLIP_Intersect_Z# Else CLIP_Add_Interpolated_Vertex(POLY_Input, V1_Index, V2_Index, CLIP_Intersect_U#, POLY_Output) EndIf ; Add V2. If Fast ; Create a new vertex in the destination polygon and copy only the vertex's position. VN_Index = POLY_Output\Vertices POLY_Output\Vertices = POLY_Output\Vertices + 1 POLY_Output\Vx#[VN_Index] = POLY_Input\Vx#[V2_Index] POLY_Output\Vy#[VN_Index] = POLY_Input\Vy#[V2_Index] POLY_Output\Vz#[VN_Index] = POLY_Input\Vz#[V2_Index] Else ; Create a new vertex in the destination polygon and copy all properties. CLIP_CopyVertex(POLY_Input, V2_Index, POLY_Output) EndIf End Select ; V2 will be the start of next edge, V1, so since we already checked it, use it's state in the next loop for V1. V1_Inside = V2_Inside Next ; If there are no vertices in the final polygon... If POLY_Output\Vertices = 0 ; The polygon has been completely clipped away. ; Delete all vertices from the original polygon, delete the temporary storage buffer, and exit the function early. POLY_Clip\Vertices = 0 Return EndIf ; Swap the pointers to the input polygon data and the output polygon data ; This makes the output data from the last loop the input data to the next, ; and uses the old input location to store the new output data. POLY_Swap = POLY_Output POLY_Output = POLY_Input POLY_Input = POLY_Swap Next ; If we've made it this far, we have a clipped polygon that lies within the frustum! ; Copy the final output over the original polygon data, delete the temporary storage buffer, and exit the function. ; (We swapped input and output at the end of the last loop, so input really points to the final output.) CLIP_CopyPoly(POLY_Input, POLY_Clip, Fast) Return End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function clips all polygons against the clipping planes. See CLIP_ClipPoly() for more details. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_ClipPolys() Local ThisPoly.CLIP_Poly For ThisPoly = Each CLIP_Poly CLIP_ClipPoly(ThisPoly) Next End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function copies one polygon to another. ; If fast copy is enabled, only the positions are copied. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_CopyPoly.CLIP_Poly(POLY_Src.CLIP_Poly, POLY_Dest.CLIP_Poly, Fast=False) Local LOOP_Vertex POLY_Dest\Vertices = POLY_Src\Vertices If Fast For LOOP_Vertex = 0 To POLY_Src\Vertices-1 POLY_Dest\Vx#[LOOP_Vertex] = POLY_Src\Vx#[LOOP_Vertex] POLY_Dest\Vy#[LOOP_Vertex] = POLY_Src\Vy#[LOOP_Vertex] POLY_Dest\Vz#[LOOP_Vertex] = POLY_Src\Vz#[LOOP_Vertex] Next Else For LOOP_Vertex = 0 To POLY_Src\Vertices-1 POLY_Dest\Vx#[LOOP_Vertex] = POLY_Src\Vx#[LOOP_Vertex] POLY_Dest\Vy#[LOOP_Vertex] = POLY_Src\Vy#[LOOP_Vertex] POLY_Dest\Vz#[LOOP_Vertex] = POLY_Src\Vz#[LOOP_Vertex] POLY_Dest\Vnx#[LOOP_Vertex] = POLY_Src\Vnx#[LOOP_Vertex] POLY_Dest\Vny#[LOOP_Vertex] = POLY_Src\Vny#[LOOP_Vertex] POLY_Dest\Vnz#[LOOP_Vertex] = POLY_Src\Vnz#[LOOP_Vertex] POLY_Dest\Vr#[LOOP_Vertex] = POLY_Src\Vr#[LOOP_Vertex] POLY_Dest\Vg#[LOOP_Vertex] = POLY_Src\Vg#[LOOP_Vertex] POLY_Dest\Vb#[LOOP_Vertex] = POLY_Src\Vb#[LOOP_Vertex] POLY_Dest\Va#[LOOP_Vertex] = POLY_Src\Va#[LOOP_Vertex] POLY_Dest\Vu0#[LOOP_Vertex] = POLY_Src\Vu0#[LOOP_Vertex] POLY_Dest\Vv0#[LOOP_Vertex] = POLY_Src\Vv0#[LOOP_Vertex] POLY_Dest\Vu1#[LOOP_Vertex] = POLY_Src\Vu1#[LOOP_Vertex] POLY_Dest\Vv1#[LOOP_Vertex] = POLY_Src\Vv1#[LOOP_Vertex] Next EndIf Return POLY_Dest End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function interpolates between two values. ; ; In other words, it takes two numbers, and calculates a number that is somewhere between them. ; ; A# and B# are the two numbers to interpolate between. ; Weight# is how much each affects the final output. ; ; In other words, a weight of 0 will return A#, and a weight of 1 will return B#. ; And a weight of 0.5 will give you a value halfway between them. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_Interpolate#(A#, B#, Weight#) Return (A#*(1.0-Weight#) + B#*Weight#) End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function linearly interpolates a normal. ; ; In other words, it takes two normals, and calculates a normal that is somewhere between them. ; It uses a linear interpolation, so it is slightly inaccurate, but for most things it will be good enough. ; ; N1xyz and N2xyz are the two normals to interpolate between. ; Weight# is how much each affects the final output. ; ; In other words, a weight of 0.5 will give you a normal halfway between them. A weight of 0.25 will give you a normal which is ; more like the first. And a weight of 1.0 will give you a normal which is exactly the same as Normal 2. ; ; The interpolated normal is returned in CLIP_Normal_X#, CLIP_Normal_Y#, and CLIP_Normal_Z# ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_InterpolateNormal(N1x#, N1y#, N1z#, N2x#, N2y#, N2z#, Weight#) ; Calculate interpolated normal. CLIP_Normal_X# = N1x#*(1.0-Weight#) + N2x#*Weight# CLIP_Normal_Y# = N1y#*(1.0-Weight#) + N2y#*Weight# CLIP_Normal_Z# = N1z#*(1.0-Weight#) + N2z#*Weight# ; Renormalize. (Make normal's length = 1) Length# = Sqr(CLIP_Normal_X#*CLIP_Normal_X# + CLIP_Normal_Y#*CLIP_Normal_Y# + CLIP_Normal_Z#*CLIP_Normal_Z#) If Length# > 0 CLIP_Normal_X# = CLIP_Normal_X# / Length# CLIP_Normal_Y# = CLIP_Normal_Y# / Length# CLIP_Normal_Z# = CLIP_Normal_Z# / Length# Else CLIP_Normal_X# = 0 CLIP_Normal_Y# = 0 CLIP_Normal_Z# = 0 EndIf End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function returns true if the specified vertex of the specified polygon is on the back side of the specified plane. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_Vertex_Inside_Plane(Poly.CLIP_Poly, Index, Plane.CLIP_Plane) Return CLIP_Point_Inside_Plane(Poly\Vx#[Index], Poly\Vy#[Index], Poly\Vz#[Index], Plane\A#, Plane\B#, Plane\C#, Plane\D#) End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function determines the location along a line where a polygon edge, defined by two vertices, intersects a clipping plane. ; V1 and V2 are the indices of the vertcies in the specified polygon. ; Returns the location of the intersetion in CLIP_Intersect_XYZ# and CLIP_Intersect_U# ; Returns true if an intersection actually occured. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_Edge_Intersect_Plane(Poly.CLIP_Poly, V1, V2, Plane.CLIP_Plane) Return CLIP_Line_Intersect_Plane(Poly\Vx#[V1], Poly\Vy#[V1], Poly\Vz#[V1], Poly\Vx#[V2], Poly\Vy#[V2], Poly\Vz#[V2], Plane\A#, Plane\B#, Plane\C#, Plane\D#) End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function copies the specified vertex from the specified polygon to the specified polygon, ; and returns the index of the new vertex. ; ; If FAST is enabled, only the vertex's position will be copied to the new vertex. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_CopyVertex(POLY_Src.CLIP_Poly, Src_Index, POLY_Dest.CLIP_Poly, Fast=False) Local Dest_Index Dest_Index = CLIP_AddVertex(POLY_Dest) If Fast POLY_Dest\Vx#[Dest_Index] = POLY_Src\Vx#[Src_Index] POLY_Dest\Vy#[Dest_Index] = POLY_Src\Vy#[Src_Index] POLY_Dest\Vz#[Dest_Index] = POLY_Src\Vz#[Src_Index] Else POLY_Dest\Vx#[Dest_Index] = POLY_Src\Vx#[Src_Index] POLY_Dest\Vy#[Dest_Index] = POLY_Src\Vy#[Src_Index] POLY_Dest\Vz#[Dest_Index] = POLY_Src\Vz#[Src_Index] POLY_Dest\Vnx#[Dest_Index] = POLY_Src\Vnx#[Src_Index] POLY_Dest\Vny#[Dest_Index] = POLY_Src\Vny#[Src_Index] POLY_Dest\Vnz#[Dest_Index] = POLY_Src\Vnz#[Src_Index] POLY_Dest\Vr#[Dest_Index] = POLY_Src\Vr#[Src_Index] POLY_Dest\Vg#[Dest_Index] = POLY_Src\Vg#[Src_Index] POLY_Dest\Vb#[Dest_Index] = POLY_Src\Vb#[Src_Index] POLY_Dest\Va#[Dest_Index] = POLY_Src\Va#[Src_Index] POLY_Dest\Vu0#[Dest_Index] = POLY_Src\Vu0#[Src_Index] POLY_Dest\Vv0#[Dest_Index] = POLY_Src\Vv0#[Src_Index] POLY_Dest\Vu1#[Dest_Index] = POLY_Src\Vu1#[Src_Index] POLY_Dest\Vv1#[Dest_Index] = POLY_Src\Vv1#[Src_Index] EndIf Return Dest_Index End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function adds a new vertex to the specified polygon. ; It's properties are calculated by interpolating between V1 annd V2 of the specified polygon, using the specified weighting value. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_Add_Interpolated_Vertex(POLY_Src.CLIP_Poly, Vertex1, Vertex2, Weight#, POLY_Dest.CLIP_poly) Local Vertex_I Local X#, Y#, Z# Local R#, G#, B#, A# Local U0#, V0#, U1#, V1# Local Nx#, Ny#, Nz# ; Create the new vertex. Vertex_I = CLIP_AddVertex(POLY_Dest) ; Calculate the interpolated properties of the vertex. X# = CLIP_Interpolate(POLY_Src\Vx#[Vertex1], POLY_Src\Vx#[Vertex2], Weight#) Y# = CLIP_Interpolate(POLY_Src\Vy#[Vertex1], POLY_Src\Vy#[Vertex2], Weight#) Z# = CLIP_Interpolate(POLY_Src\Vz#[Vertex1], POLY_Src\Vz#[Vertex2], Weight#) R# = CLIP_Interpolate(POLY_Src\Vr#[Vertex1], POLY_Src\Vr#[Vertex2], Weight#) G# = CLIP_Interpolate(POLY_Src\Vg#[Vertex1], POLY_Src\Vg#[Vertex2], Weight#) B# = CLIP_Interpolate(POLY_Src\Vb#[Vertex1], POLY_Src\Vb#[Vertex2], Weight#) A# = CLIP_Interpolate(POLY_Src\Va#[Vertex1], POLY_Src\Va#[Vertex2], Weight#) U0# = CLIP_Interpolate(POLY_Src\Vu0#[Vertex1], POLY_Src\Vu0#[Vertex2], Weight#) V0# = CLIP_Interpolate(POLY_Src\Vv0#[Vertex1], POLY_Src\Vv0#[Vertex2], Weight#) U1# = CLIP_Interpolate(POLY_Src\Vu1#[Vertex1], POLY_Src\Vu1#[Vertex2], Weight#) V1# = CLIP_Interpolate(POLY_Src\Vv1#[Vertex1], POLY_Src\Vv1#[Vertex2], Weight#) CLIP_InterpolateNormal(POLY_Src\Vnx#[Vertex1], POLY_Src\Vny#[Vertex1], POLY_Src\Vnz#[Vertex1], POLY_Src\Vnx#[Vertex2], POLY_Src\Vny#[Vertex2], POLY_Src\Vnz#[Vertex2], Weight#) Nx# = CLIP_Normal_X# Ny# = CLIP_Normal_Y# Nz# = CLIP_Normal_Z# ; Set the properties of the new vertex. CLIP_SetVertexPosition(POLY_Dest, Vertex_I, X#, Y#, Z#) CLIP_SetVertexColor(POLY_Dest, Vertex_I, R#, G#, B#) CLIP_SetVertexAlpha(POLY_Dest, Vertex_I, A#) CLIP_SetVertexUV(POLY_Dest, Vertex_I, U0#, V0#, 0) CLIP_SetVertexUV(POLY_Dest, Vertex_I, U1#, V1#, 1) CLIP_SetVertexNormal(POLY_Dest, Vertex_I, Nx#, Ny#, Nz#) ; Return the index number of the next vertex. Return Vertex_I End Function ; ------------------------------------------------------------------------------------------------------------------- ; This function calculates the plane equation for a triangle. ; It returns the results in the global variables CLIP_A#, CLIP_B#, CLIP_C#, and CLIP_D#. ; ; ABC is the triangle's normal. D is the distance of the plane from the origin. Distance is negative if the normal ; points away from the origin, and positive if it points toward it. ; ; The normal points in the direction the triangle is facing. ; Wind vertices clockwise to have normal point towards you. ; ; In other words, a triangle aligned with the X, Z axis, wound counterclockwise when looking down, at a height of 5, ; will have a normal pointing downwards, and a value for D# of 5. ; ------------------------------------------------------------------------------------------------------------------- Function CLIP_CalculateTriPlane(V1x#, V1y#, V1z#, V2x#, V2y#, V2z#, V3x#, V3y#, V3z#) Local Px#, Py#, Pz# Local Qx#, Qy#, Qz# Local Nx#, Ny#, Nz#, Nl# ; Create two vectors from the sides of the triangle. Px# = V1x#-V3x# Py# = V1y#-V3y# Pz# = V1z#-V3z# Qx# = V2x#-V3x# Qy# = V2y#-V3y# Qz# = V2z#-V3z# ; Compute their cross product. Nx# = (Py#*Qz#) - (Qy#*Pz#) Ny# = (Pz#*Qx#) - (Qz#*Px#) Nz# = (Px#*Qy#) - (Qx#*Py#) ; Calculate the length of the vector. Nl# = Sqr(Nx#*Nx# + Ny#*Ny# + Nz#*Nz#) ; Calculate the plane equation for the triangle. ; ABC is the triangle's normal. ; Normalize the vector so it has a length of 1. ; This is the normal of the triangle. CLIP_A# = Nx# / Nl# CLIP_B# = Ny# / Nl# CLIP_C# = Nz# / Nl# ; Calculate minimum distance of plane the triangle lies in, from the origin. ; This is the shortest distance to the surface of the plane from 0,0,0. CLIP_D# = -(CLIP_A#*V1x# + CLIP_B#*V1y# + CLIP_C#*V1z#) End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function calculates the equation of a 2D line. ; ; The equation of a 2D line is the same as the equation of a plane, except that the C component (Normal Z) is assumed to be 0. ; If facing down the line from point 1 to point 2, the line's normal will point left. ; In other words, if the line is an edge of a triangle wound clockwise, the resulting edge normals will point outwards. ; ; Function assumes positive Y is up, unlike screen coordinates. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_Calculate2DLine(X1#, Y1#, X2#, Y2#) Local Nx#, Ny#, Nl# ; Calculate the normal of the line, (A = Nx, B = Ny) and the distance of the line (D) from the origin (0,0,0). Nx# = Y2# - Y1# Ny# = X1# - X2# ; Normalize the normal. Nl# = Sqr(Nx#*Nx# + Ny#*Ny#) CLIP_A# = Nx# / Length# CLIP_B# = Ny# / Length# CLIP_D# = -(CLIP_A#*X1# + CLIP_B#*Y1#) End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function determines if a circle is intersecting a line, or on the inside side of a line. ; ; XY is the position of the circle. ; Radius is the circle's radius. ; ABD is the equation of the line. ; ----------------------------------------------------------------------------------------------------------------------------------- Function CLIP_CircleInsideLine(X#, Y#, Radius#, A#, B#, D#) If (X#*A# + Y#*B# + D#) < Radius# Then Return True Return False End Function ; ----------------------------------------------------------------------------------------------------------------------------------- ; This function determines if a circle is intersecting/inside a triangle, in 2D. ; ; XY is the position of the circle. ; Radius is the circle's radius. ; Vx, Vy are the vertices of the triangle, wound in clockwise order. ; ----------------------------------------------------------------------------------------------------------------------------------- ;Function CLIP_CircleInsideTri(X#, Y#, Radius#, Vx1#, Vy1#, Vx2#, Vy2#, Vx3#, Vy3#) ; If the circle is intersecting or on the inside side ;End Function ; ------------------------------------------------------------------------------------------------------------------- ; This function returns the X axis scale of an entity, as set by ScaleEntity(). ; ------------------------------------------------------------------------------------------------------------------- Function CLIP_EntityScaleX#(Entity) Vx# = GetMatElement(Entity, 0, 0) Vy# = GetMatElement(Entity, 0, 1) Vz# = GetMatElement(Entity, 0, 2) Scale# = Sqr(Vx#*Vx# + Vy#*Vy# + Vz#*Vz#) Return Scale# End Function ; ------------------------------------------------------------------------------------------------------------------- ; This function returns the Y axis scale of an entity, as set by ScaleEntity(). ; ------------------------------------------------------------------------------------------------------------------- Function CLIP_EntityScaleY#(Entity) Vx# = GetMatElement(Entity, 1, 0) Vy# = GetMatElement(Entity, 1, 1) Vz# = GetMatElement(Entity, 1, 2) Scale# = Sqr(Vx#*Vx# + Vy#*Vy# + Vz#*Vz#) Return Scale# End Function ; ------------------------------------------------------------------------------------------------------------------- ; This function returns the Z axis scale of an entity, as set by ScaleEntity(). ; ------------------------------------------------------------------------------------------------------------------- Function CLIP_EntityScaleZ#(Entity) Vx# = GetMatElement(Entity, 2, 0) Vy# = GetMatElement(Entity, 2, 1) Vz# = GetMatElement(Entity, 2, 2) Scale# = Sqr(Vx#*Vx# + Vy#*Vy# + Vz#*Vz#) Return Scale# End Function Free = Don't email me for support. I'm very busy! Buy a copy of my shadow system if you want help with using it. :-)

sswift (Posted 2005) [#7]

A couple more things. 1. What you want to do is use the function in the above code for determining if a sphere that encloses your object is in the frustum. It's up to to you calculate this sphere. I just figure out the smallest box that will enclose the entity, an then make a sphere with a radius from the center of the box to the corner of the box so the sphere encloses the box. 2. I make no guarantees that trying to cull objects like this will be any faster than just letting Blitz do the job. But I have known Blitz to fail to cull objects that are outside the camera view and cause slowdown as a result, such as when bulding a starfield for a 2D style shooter with a bunch of entities in a grid.

Beaker (Posted 2005) [#8]

I think Blitzs frustrum culling is based on entity centre and bounding sphere or box. Can't remember exactly. This can be a problem with animated meshes (boned/skinned B3Ds) because the mesh can animate out of the bounding shape. But, it should be fine otherwise.

Andy (Posted 2005) [#9]

>@andy: I don't know if this is relevant to your prob >(probably not) but note that Blitz culls based on an >entity's first frame of animation. I appreciate your input, but there were no animation, indeed it was simply a white quad consisting of 2 tri's. It was really weird, but could possibly be because the center of the mesh was actually behind the aircraft but the landing strip continued forwards. Andy

sswift (Posted 2005) [#10]

Best way to do frustrum culling would probably be bounding sphere and then an oriented bounding box which is scaled and rotated to fit the object as tightly as possible. I'm not sure how you would calculate that, but I'd try to figure out how I'd do it myself, and then try to construct an algorithm to do the same thing. I'll bet there are papers out there though that explain how to best fit an OBB to a cloud of points. Anyway, the above code can do that sort of culling. If you make eight quads polygons for the sides of the box and eight for the frustum, and then clip the box with the frustum, if any of the box polygons are not clipped away completely, being completely outside the frustum, then the box is in the frustum. This is plenty fast enough to do if you don't have 100,000 objects in your scene and you do the sphere check first.

bytecode77 (Posted 2006) [#11]

hi! i don't wanted to grab this thread out of his grave, but: the huge polyclip above^^ i do not understand how it works... is there any sample for this? i have seen this and i got interrested :) thanx :)

Andy (Posted 2006) [#12]

Your sig is a bit excessive. Andy

bytecode77 (Posted 2006) [#13]

grrrrrrr where did i hear the word SIG before? ah yes, the stencil shadow thread :/

ShadowTurtle (Posted 2006) [#14]

... sig=signature ... @ devilschil

bytecode77 (Posted 2006) [#15]

ok st, now lets don't make too much offtopic :) ! have you got any sample to this?

jhocking (Posted 2006) [#16]

You mean other than his shadow system?

bytecode77 (Posted 2006) [#17]

no, i mean how this polygon clipping algorithm works... because i would be interessted in that^^