• ### What is your GameDev Story?

#### Archived

This topic is now archived and is closed to further replies.

# Lightmapping Algorithm

This topic is 6196 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I''m working on an anlgorithm for using lightmaps in my engine. I want to send a vector, from the light source, to the direction. Then I check each point lying on the vector, if the distance to an object is smaller, for example, 1. And then I draw the lightmap on this triangle. My Problem is, how can i follow up a vector till it has reached its destiantion and check every point on this vector?

##### Share on other sites
OK, what you're talking about is a technique called raycasting. Now, you have the x, y, z position of your light and it's direction, as a unit normal. Now, to make your vector stretch out from the light source in the direction of the light, use this algorithm:

NewRayPosition.x = LightPosition.x + (t * RayDirection.x)
NewRayPosition.y = LightPosition.y + (t * RayDirection.y)
NewRayPosition.z = LightPosition.z + (t * RayDirection.z)

t can be any number, and by incrementing it, you can make the vector longer, by finding the next position on the line. You can then test the NewRayPosition against the LastRayPosition (which you'd have saved before changing NewRayPosition with the above algorithm) to see if the ray passed through one of your polygons.

Hope this helps some. You might want to look on this site, or on NeHe's (nehe.gamedev.net) to see if there are any useful texts on this subject. The question you've asked is very generalised, and going into depth on it would require a few pages, which have already been written by someone, so I'm not going to repeat them. Some searching will turn up what you want. It did for me.

Also, you might want to look for collision detection algorithms, which will also give you information on how to detect collisions between polygons and vector/rays...

iNsAn1tY - the place where imagination and the real world merge...
Try http://uk.geocities.com/mentalmantle - Now updated!

Edited by - iNsAn1tY on February 3, 2002 5:22:32 PM

##### Share on other sites
>>I want to send a vector, from the light source, to the direction.<<

do the opposite ie object->light not light->object
with the first method youre gonna have to do heaps of unecessary calculations + even then it mightnt be enuf

http://uk.geocities.com/sloppyturds/gotterdammerung.html

##### Share on other sites
Well,
@zedzeek:
I want to check every position on this ray, being nearer to a vertex than f.e. 0.1 and then I want to display the lightmap on the face, the vertex belongs to.
What do you mean with your method?

##### Share on other sites
If you think about it, and omni directional point light casts infinitely many rays out in every direction. However, you have only a finite amount of objects. Therefore its usually easier to cast a ray back from each object to the light source to determine if the light hits the object, than trying to cast a bunch rays out from the light to see if they hit anything.

Anyways, same thing applies with the vector. A line has infinitely many points, so you simply cannot check all of them. Instead you check each object against the line. How you do this depends on what kind of geometry you have. At the simplist level, you can check against each triangle to determine the intersection of the line and the triangle (you can get the point at which the equation of the line intersects the plane spanned by the vertices of the triangle and then determine if the point is inside the triangle). Of course with a lot of triangles, thats extremely slow, so you want to speed it up a bit, depending on how you have your data structures arranged. For instance, you can also check the intersection of the ray and a bounding structure (sphere, ellipsoid, box, etc.)to trivially reject entire objects (if your geometry is organized properly). You can also loss out everything that is behind the plane formed my the light and the normal corresponding to the ray, and everything behind the plane formed by the point of the object and the normal corresponding to the ray (basically everything behind the light or the surface). If you have some kind of spacial partioning, octree, quad tree, etc, you can similarly use it here to toss out irrelavant pieces of geometry. The list goes on. It really depends how your scene data is organized.

##### Share on other sites
>>I want to check every position on this ray<<

if i understand right youre dividing the ray up into say 100points + then checking each of these points against the worlds scenery.
(2 big problems, A its not accurate, B its very very slow(
do this instead check the WHOLE ray against all the world scenery eg do a ray->triangle intersection test (theres plenty of examples on the net) for each triangle. also do what invective saiz put bounding shapes around your objects + do ray->shape test first

http://uk.geocities.com/sloppyturds/gotterdammerung.html

##### Share on other sites
Pseudocode:

  For each face F in scene For each texel T on face For each light source L in scene { Vector ray = CalculateRay(T, L) bool occluded = false; For each object O in scene if(intersect(ray, O)) { occluded = true break } if(!occluded) { float cosAngle = DotProduct(F.normal, ray.normalized()) float intensity = cosAngle / square(ray.magnitude()) T.r += L.r * intensity T.g += L.g * intensity T.b += L.b * intensity } }

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 11
• 9
• 38
• 16
• ### Forum Statistics

• Total Topics
634128
• Total Posts
3015693
×